《语法分析和语法分析程序》由会员分享，可在线阅读，更多相关《语法分析和语法分析程序（94页珍藏版）》请在金锄头文库上搜索。
1、第四章 语法分析和语法分析程序,自上而下分析 自下而上分析 分析器的自动生成,4.1 前 言,4.1.1 语法与语法分析作用,语法作用:语言设计者：提供语言的精确构成，形式化规定语言语法单位组成部分间的关系。语言使用者：使用语言，根据语法来构造合法句子。编译程序设计者：语法是进行编译程序的依据，用来构造识别语言所有句子的语法分析器。 语法分析作用：识别由词法分析给出的单词序列是否是给定文法的正确句子（程序）。即根据语言的语法规则分析源程序的语法结构（单词如何构成各种语法范畴）。,4.1.2 语法分析的方法,句型分析就是识别一个符号串是否为某文法的句型，是某个推导（归约）的构造过程。 在语言的编
2、译实现中，把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。 从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号，直到分析结束。,自上而下分析法：从文法的开始符号出发，反复使用文法的产生式，为待识别句子建立一个最左推导，以寻找与输入符号串匹配的推导。 自下而上分析法：从输入符号串开始，逐步进行归约，从叶子节点，由底上向上逐步建立一棵完整的语法树，直至归约到文法的开始符号（树根）。,分析算法分为：,4.2 自上而下分析算法,一般方法要点： 由根向下构造语法树； 构造最左推导； 推导出的终结符是否与当前输入符匹配 ？,例如：文
3、法GS:S ABA aA | B bB | b 判定符号串aaab是否合法.,S,A,B,a,A,a,A,a,A,B,SAB S ABaAB A aAaaAB A aAaaaAB A aAaaa B A aaab B b,b,自顶向下分析一般方法特点：,1.分析过程是带有预测的，对输入符号串要预测属于什么 语法成分，然后根据该语法成分的文法建立语法树。,2.分析过程是一种试探过程，是尽一切办法(选用不同规则) 设法建立语法树的过程，由于是试探过程，故难免有失败， 所以分析过程需进行回溯，因此我们也称这种方法是带 回溯的自顶向下分析方法。,3. 最左推导可以编出程序来实现，但在实际上价值不大，
4、效率低。,自顶向下分析方法的基本缺点：不能处理具有左递归性的文法,为什么自顶向下分析不能处理左递归文法？,1. 左递归文法,左递归文法回溯问题,4.2.1 一般方法面临问题及解决,在匹配输入串过程中，如果当前需要用非终结符U 直接匹配输入串，即要用U的右部符号串U去推导， 没有对当前串匹配即进行递归调用，从而陷入死循环。,例：GS: SSa|b L=ban | n1 W=baaa,如果文法具有间接左递归，则也将发生上述问题。,要实行自顶向下分析，必须要消除文法的左递归，不仅消除直接左递归，而且消除间接左递归。,2 回溯问题,什么是回溯?,分析工作要部分地或全部地退回去重做叫回溯。,文法中，对于
5、某个非终结符号的规则其右部 有多个选择，并根据所面临的输入符号不能准确 的确定所要选择时，就可能出现回溯。,严重的效率低，只有在理论上的意义而无实际意义。,U:= a1 | a 2 | a 3,造成回溯的条件?,回溯带来的问题?,1)语法分析要重做,2)语法处理工作要推倒重来,因此自顶向下的一般分析方法不能处理左递归、复杂的回溯技术、回溯导致语义工作推倒重来、难以报告出错的确切位置、效率低。 欲采用此方法，必须：1、消除左递归；2、消除回溯,效率低的原因,4.2.2 消除文法的左递归产生式,方法：改写产生式，使产生式不含左递归。 法一：PP|产生式的符号串为 . . . 引入一元语言符号，x表
6、示x可出现任意次。则： PP|改写为P 例1： SAc AAa|b 改为： SAc Aba,例2：EE+T|TTT*F|F 消除左递归： ET+T TF*F,1、消除直接左递归,法二：对左递归 AA|的非终结符A，引入一个新的非终结符A，使得：AA|,等价写成：,一般地：若,其中i均不以A打头，则：,AA AA|,规则一（提因子）,i) 已知 Uxy | xw | | xz 解： Ux ( y | w | | z )得： Ux UUy | w | | z,使用提因子法，不仅有助于消除直接左递归。而且有助于压缩文件的长度，使我们更加有效的分析句子。,ii) 已知 Ux | xy 解： Ux (
7、y |),规则二 将左递归规则改为右递归规则,若：PP| 则可改写为：P PP P| ,例 E E + T | TT T * F | F F ( E ) | id 消除左递归后文法E TE E + TE | T FT T * F T | F ( E ) | id,注意：此方法只能消除出现在产生式的全部直接左递归，不能消除经两步或多步推导所出现的一切间接左递归。,2、消除间接左递归,间接左递归产生原因： 产生式右边首符号为非终结符； (存在回路)前面非终结符引用后面非终结符，后面非终结符引用前面非终结符。 例1：SAc|c (1)ABb|b (2)BSa|a (3),对例1：BSa|a 带入(2
8、)，得 ASab|ab|b 带入S产生式，得 S Sabc|abc|bc|c对S消除直接左递归得：S(abc|bc|c)SSabcS|,消除回路的方法：找出所有引用前面非终结符的产生式进行代换，即先变换成直接左递归。,1 .以某种顺序将文法非终结符排列A1 ,A2 An 2. for i:=1 to n dobegin for j:=1 to i-1 do Aj 1| 2| k是Aj全部产生式；若文法中有形如Ai Ajr的规则；则替换成Ai1| 2r| k r；消除Ai规则的直接左递归end; 3.化简由2得到的文法,B,A,S,3,消除间接左递归算法,例：文法GSS Aa | b （1）A
9、Sd | （2）Q Aa （3）,1、S、A、Q 2、S产生式无直接左递归，A产生式含有S，则将S带入(2)，变成直接左递归: S Aa | bA Aad | bd | 3、对于A产生式，先消除直接左递归，得：S Aa | bA bd A | A A adA | 4、Q产生式右部还有A，则A bd A | A 带入得Q bd A a| Aa，无直接左递归，结束。,4.2.3 回溯的消除及LL(1)文法,无回溯指对文法的任何非终结符，当需要匹配某输入串时，能够根据所面临输入符号准确指派一个候选式执行推导，且匹配结果确信无疑。 例：SaA|bB|cC Ad|de|fBEd|hCeEf|h|d 判定
10、ade、bd是否为该文法句子,S aA,S bB, ad,选择候选式与候选式首符号或非终结符后跟符号有关。, bd, ade,bEd,bdd,1、消除回溯的途径：,改写文法,对具有多个候选式右部反复提取左因子，使其具有不同首符号,例1 UxV|xW U, V, WVn, xVt 改写为：Ux(V|W) 更清楚表示 UxZ ZV|W,注意：要进一步检查V和W 的首符号是否相交，若相交， 则要再次提取左因子。,一般的，对于有公共左因子的文法A a1 | a2| ak|，其中不以a开头， aV。提左因子：,判断adeS aA adAade,例： Ad|de|f 改为： AdA |fA |e 注意：提
11、取公因子会引入大量非终结符和产生式。,A aA | A 1 | 2 | k,若1 2k还有某些候选式有相同首符号，则依次提取，直到每个候选式的首符号不同为止。,FIRST(X)=a|aVT且X a， X，V* 特别的：X ，则FIRST (X) 对文法G的所有非终结符的每个候选式X其终结首符号集为FIRST(X)。对A的任何两个不同的选择i 和j，希望有FIRST (i ) FIRST (j ) = 此时，当要求A匹配输入串时，A就可根据所面临第一个输入符号a，准确指派某个候选式推导，该候选式即为aFIRST(X)的X候选式。,2、FIRST集,*,*,例1：文法G | begin；end b
12、eginend 是否可用自顶向下方法进行语法分析？,FIRST（） = begin FIRST（） = begin ,改写文法： begin （； end | end ） 引入 begin ； end | end,25,25,例2：文法G ：begin ； end | endreal|integer|boolean|array|function标识符|goto| begin| if | for 是否可用自顶向下方法进行语法分析？,对于： FIRST( ； end) = real, integer, boolean, array, function FIRST( end ) = 标识符，goto
13、, begin, if, for 不相交。,3、FIRST（X）构造方法,1.若XV，则FIRST(X)=X； 2.若XVN，且有Xa，则aFIRST(X)；a可为； 3.若有X Y1Y2YK ，YiVN (1i K)，则(FIRST(Y1) FIRST(X);若FIRST(Y1)，则(FIRST(Y2) FIRST(X)；同样，若FIRST(Yj)(1j A 且a FRIST()， V*， V* ； 若S = u A ，且 =，则#FOLLOW(A),4、FOLLOW集,对文法G的所有含有产生式的非终结符A定义它的FOLLOW(A)。对含有的A的所有候选式i ，希望有FIRST (i ) FOLLOW (A ) = ,*,*,*,*,*,1.文法的开始符号S，置# FOLLOW(S)；当AVN为句型的尾符号时，则#FOLLOW（A） 2. 对于BA，则(FIRST() FOLLOW(A)； 3. 对于BA，或BA而FIRST()，则把FOLLOW（B）加至FOLLOW（A）中。 反复使用2、3步，直到每个非终结符的FOLLOW集不再增大为止。,
