ANTLR学习心得——抄书(4)

　　一本厚厚的305页的书，我实在是不可能都抄在这里的。只能拣最紧要的抄出来。而这个紧要的判断，也是以我在读书的过程中的理解为准，最困难的部分，自己总是想不清楚的部分，我就认为是最紧要的了。今天打算抄的是LL与LR的概念。在我看到的很多关于编译原理的书中，都会反复出现LL(1)，LR(1)这样的东西，这究竟是什么概念呢？

 

　　我们这次从第72页开始抄起：

 

　4．1　语法分析综述

　　4．1．1  语法分析程序的功能
　　语法分析(Syntax Analysis)是编译程序的核心部分。编译程序在完成了词法分析之后，就进入语法分析阶段。语法分析的任务是，按照语言既定的语法规则，对字符串形式的源程序进行语法检查，并识别出相应的语法成分。按照第三章所述的词法分析程序模型，语法分析程序处理的对象是从词法分析器输出的属性字流形式的源程序，它的处理依据是语言的文法规则，其分析结果是识别出的无语法错误的语法成分，可以用语法树的形式来表示。
　　程序设计语言作为一般形式语言的特例，语法分析的关键是句型识别问题。语法分析程序要解决的问题是：
　　设给定文法G和字符串(句子) α(α∈V_T^*)，检查、判定α∈L(G)?即检查、判定α是否是文法G所能产生的合法的句子，同时检查和处理语法错误。
　　图4．1示出语法分析器的作用及在编译程序中的位置。

 

 

　　将完成语法分析任务的程序称为语法分析程序，也称为语法分析器或简称分析器。

 

　　4．1．2语法分析方法
　　语法分析的方法多种多样，每种方法的具体实现技术更是五花八门。综合语法分析的力析途径即产生分析树的方向而言，通常将语法分析方法分为两大类，即自上而下分析与自下而上分析：
　　自上而下的分析方法．实际上是一种产生的方法，面向目标的方法。分析过程是一个推导过程。
　　自下而上方法是一种辨认方法，分析过程是归约过程。
　　1．自上而下分析方法
　　给定文汇G和源程序串$，则自上而下分析是：从G的开始符号S出发，通过反复使用产生式，逐步推导得到$，则可以确认$是文法G的合法句子。
　　例4．1 设有文法G和输入串$

　　G：S→aA|a

　　　  A→BaA|ε

　　　  B→+|-|*|,

　　$：a*a+a

　　对输入串$有如下推导过程和相应的语法树的构造如图4．2所示。
　　推导过程：

　　S=>aA=>aBaA=>a*aA=>a*aBaA=>a*a+aA=>a*a+a=$

　　语法树的从左到右叶结点＝$,则$∈L(G)。

 

　　由例4．1可见，自上而下分析的实质是，按照对输入串的扫描顺序，从文法G的开始符号S出发，通过反复使用产生式对句子中非终结符进行替换，为其建立最左推导，即选择合适的产生式进行推导，逐步使推导结果与$匹配。同样，一个句子的推导过程可以表示成一棵语法树。自上而下分析就是以文法G的开始符号为树的根结点，从此根结点出发，对任何输入字符朗，试图用一切可能的办法，自上而下地为其建立一棵语法树。
　　2．自下而上分析方法
　　所谓自下而上分析法，就是从给定的输入串$开始，不断寻找于串与文法G中某个产生式P的候选式进行匹配，并用P的左部代替之。

 

　　例4．2 设有文法G和输入串$

　　G：S→aAb|a|b

　　　  A→+|-|*|,

　　$：a*b

　　自下而上分析的过程也可以表示成语法树的生成过程。对输入串$逐步进行归约的过程及其对应的语法树的生长过程如图4．3所示。

 

(未完待续)