编译原理语法3(自顶向下语法分析：递归下降).ppt

第 6 讲,编译原理,西北农林科技大学本科教程,主讲教师：赵建邦,第三章 语法分析,3.1 文法和语言 3.2 推导与语法树 3.3 自顶向下的语法分析 3.4 自底向上的语法分析 3.5 规范规约的自底向上语法分析方法,第三章语法分析 3.3 自顶向下的语法分析 递归下降分析法 LL(1)分析法（下一讲内容） 重点掌握 消除左递归 消除回溯 构建递归下降子程序,本讲目标,3.3 自顶向下的语法分析,算法思想： 从文法的开始符号出发，向下推导，如果推导出的句子恰好为输入符号串，则输入符号串为符合该文法的句子； 或者：开始符号作为根节点，向下生长出一棵语法树，其叶子节点组成的句子恰好为输入符号串。这里的每一步“生长”对应一次直接推导。 自顶向下分析方法: 1、不确定的自顶向下分析 2、确定的自顶向下分析 递归下降分析法 LL(1)分析法,1、不确定的自顶向下分析方法 假定文法GS为 S xAy A ab | a 若输入串为xay，则其分析过程如下： (1)建立根节点S； (2)关于S的产生式只有一个，则生长语法树, 匹配语法树的第一个终结符x； (3) A ab | a 有两个候选式，选择第一个, 并且匹配语法树的第二个叶子节点a； (4)输入串xay期待匹配y,而语法树中的b与之匹配失败；,S,A,y,a,b,x,3.3 自顶向下的语法分析,1、不确定的自顶向下分析方法 假定文法GS为 S xAy A ab | a 若输入串为xay，则其分析过程如下： (5)撤销匹配a， 注销A所生成的子树，回溯； (6)选择产生式A a，重新匹配a； (7) 匹配输入串的字符y；而语法树的最后 一个叶子节点也是y,因此语法树和输入串xay匹配成功。,S,A,y,a,b,x,a,3.3 自顶向下的语法分析,小结：关于不确定的自顶向下分析方法 这种自顶向下的分析是一个不断试探的过程；即，在分析过程中，如果出现多个产生式(即候选式)可供选择，则逐一试探每一候选式进行匹配，每当一次试探失败，就选取下一候选式再进行试探； 此时，必须回溯到这一次试探的初始现场，包括注销已生长的子树及将匹配指针调回到失败前的状态。 这种带回溯的自顶向下分析方法实际上是一种穷举的试探方法，其分析效率极低，在实用的编译程序中很少使用。,3.3 自顶向下的语法分析,2、确定的自顶向下分析方法 确定的自顶向下分析要求文法满足两个条件： (1) 文法不含左递归：即不存在这样的非终结符号A：有AA存在或者有 ； 原因：左递归的文法使自顶向下分析工作陷入无限循环 EE+T,3.3 自顶向下的语法分析,(2) 无回溯，对文法的任一非终结符号，当其产生式右部有多个候选式可供选择时，各候选式所推出的终结符号串的首字符集合要两两不相交,原因：会导致先前做的一大堆语法工作和语义工作(指中间代码产生工作和各种表格的簿记工作)推倒重来,3、消除左递归 方法： 引入一个新的非终结符，把含有左递归的产生式改写为右递归。,设关于非终结符A的直接左递归的产生式形如 A A | 其中，、是任意的符号串且不以A开头。该产生式所能推导的句子如下：,3.3 自顶向下的语法分析,再看下面不含A的直接左递归的产生式： A A A A | ,这两个产生式所能推导的句子如下：,可见，两种产生式所推导的结果相同：都能描述正规表达式*,3.3 自顶向下的语法分析,3、消除左递归,规则：将产生式 A A | 改写为： A A A A | 其中， A是新引入的非终结符。 不可缺少，否则推导过程无法结束。,3.3 自顶向下的语法分析,例如，含有直接左递归的表达式文法GE为,GE:E E+T | T T T*F | F F (E) | i,E TE E +TE | ,(3.2),经过消去直接左递归后得到文法GE为,T FT T *FT | ,GE:,F (E) | i,3.3 自顶向下的语法分析,3、消除左递归 一般情况下，设文法中关于A的产生式为 A A1 | A2 | | Am | 1 | 2 | | n 其中，每个都不等于且每个都不以A开头，则消除A的直接左递归性就是将其改为： 例如，对产生式 EE+T | E-T | T，消除直接左递归后为,3.3 自顶向下的语法分析,R = (1 | 2 | | n)(1 | 2 | | m)*,E TE E +TE | -TE | ,3、消除间接左递归 注意：也有些文法是含有间接左递归的，如下述文法GS: GS: S Q c | c Q R b | b R S a | a (3.3) 中的S、Q、R都具有间接左递归,3.3 自顶向下的语法分析,3、消除间接左递归 如何消除一个文法的一切左递归呢？如果一个文法不含回路(形如A=A的推导)，且产生式的右部也不含的候选式，那么，下述算法将消除文法的左递归： (1) 将文法GS的所有非终结符按一给定的顺序排列：A1、A2、An；,+,3.3 自顶向下的语法分析,(2) 执行下述循环语句将消除所有左递归 for(i=1;i=n;i+) for(j=1;j=i1;j+) 把一个形如： 的产生式改写为 Ai1 | 2 | | k | 1 | 2 | | n； 按消除直接左递归的方法消除Ai的直接左递归； (3) 化简所得到的文法，去掉无用的产生式：去掉那些从开始符号S出发，推导中无法出现的非终结符产生式。,3.3 自顶向下的语法分析,例：消除间接左递归,GS: S Q c | c Q R b | b R S a |a （3.3）,消除文法（3.3）的左递归：,解答,1、令3个非终结符的排列顺序为R、Q、S， 2、由于R不存在直接左递归，不需要进行操作； 当i=2,j=1时，将 Q R b | b 替换成 Q Sab | ab | b （不需要消除直接左递归）,当i=3,j=2时，将S Q c | c 替换成 S Sabc | abc | bc | c (含有直接左递归),消除直接左递归，得到： S abcS |bcS |cS S abcS | Q Sab|ab|b R Sa|a,例：消除间接左递归,3、显然：后两条产生式为多余的产生式，从S出发的推导无法到达。因此，经化简后得到的文法是： S abcS |bcS |cS S abcS | ,注意1：消除左递归之前的文法不允许有产生式，否则无法得到等效的无左递归文法。因此，如果原文法中有的产生式，则需将文法改写为无的产生式的文法。,关于消除间接的特别说明,(消除产生式的算法请查看参考书P27算法2.5：消除空规则）,注意2：此外，此算法并未对非终结符的排列顺序加以规定，如果非终结符排列的顺序不同，最后得到的文法形式不同，但是这些文法都是等价的。但是必须确保S不被消除。,实际上，也可以用数学中的分配律来消除文法中的左递归。对文法(3.3)，首先将R的产生式代入到Q的产生式中并按分配律展开(注：“(”和“)”不是终结符)得 Q (Sa | a)b | b 展开后：Q Sab | ab | b,再将改变后Q的产生式代入到S的产生式中并按分配律展开得S (Sab | ab | b)c | c 展开后：S Sabc | abc | bc | c 在消除S的直接左递归后同样得到文法(3.4)。,例：消除间接左递归,4、消除回溯 回溯发生的原因在于候选式存在公共的左因子，如产生式A如下： A 1 | 2 此时，如果输入串待分析的字符串前缀为，则选用哪个候 选式以寻求与输入串匹配就难以确定。 倘若候选式不含公共左因子，则推导出的首字符能与输入串匹配的那个候选式便是惟一的匹配。 S xAy A a | b 如何匹配 xay ？,3.3 自顶向下的语法分析,4、消除回溯的方法 一般情况下，设文法中关于A的产生式为 A 1 | 2 | | i | i+1 | | j (3.5) 那么，可以把这些产生式改写为 (3.6) 经过反复提取左因子，就能把每个非终结符(包括新引进者)的所有候选首字符集变为两两不相交(即不含公共左因子)。,3.3 自顶向下的语法分析,4、消除回溯的方法 也可以用数学中提取公共因子的办法来提取公共左因子。如对式(3.5)提取公共(左)因子后得 A 1 | 2 | | i | i+1 | | j A (1 | 2 | | i ) | i+1 | | j 将产生式中由“(”和“)”括起的部分以非终结符A 命名则得到式(3.6) (3.6) 例如，对文法GA: A aAB | a | b提取公共左因子后的文法GA为?,3.3 自顶向下的语法分析,GA: A aA | b A AB | ,4、递归下降分析器 递归下降分析法：是确定的自上而下分析法。它的基本思想是，对文法中的每个非终结符编写一个函数（或子程序），每个函数的功能是识别由该非终结符所表示的语法成分。 由于描述语言的文法经常是递归定义的，因此相应的这组函数也必然以互相递归的方式进行调用，所以这种分析方法称为递归子程序法或递归下降分析法 递归下降分析程序也称为递归下降分析器，对文法的要求是： 1、文法不含左递归 2、每个非终结符的所有候选终结首字符集两两不相交(候选式不含公共左因子),3.3 自顶向下的语法分析,递归下降分析器的设计示例,GE:E TE E +TE | T FT T *FT | F (E) | i （3.2）,GE:E E+T | T T T*F | F F (E) | i （3.1）,可以通过文法(3.2)构造递归下降分析器： (1)文法(3.2)无左递归 (2) E 、 T 、F的候选式首字符无交集,4、递归下降分析器 void match(token t) / 匹配终结符(t：终结符) / lookahead:程序的单词指针 if (lookahead = t) / 判断当前终结符是否匹配 lookahead = nexttoken; / 读入下一个终结符 else error(); E TE void E() / 每个非终结符对应一个子程序 / 按照产生式顺序调用 T(); /原则1：遇到非终结符T，调用T() E(); ,3.3 自顶向下的语法分析,4、递归下降分析器 E +TE | void E() if (lookahead = +) /原则2：遇到终结符+, 调用match() match(+); T(); E(); / 原则3：候选式是，E认为自动获得匹配，不返回error ,3.3 自顶向下的语法分析,4、递归下降分析器 F (E) | i void F() / 原则4：确保候选式的唯一匹配，需要if -else if (lookahead = i) match(i); else if (lookahead = () match(); E(); if(lookahead = ) match(); else error(); /不是) else error() / 既不是i ，也不是( / F(),3.3 自顶向下的语法分析,4、递归下降分析器 根据图3-14,可以画出递归下降分析法分析句子所对应的语法树。可知，递归子程序法对应的是最左推导过程 还可以用另一种表示法得到递归下降分析器，即将文法的每一个非终结符用VTVN上的一个正规表达式来定义，然后将其用状态转换图表示，并借助于这种转换图来得到递归下降分析器,3.3 自顶向下的语法分析,E E+T | T T T*F | F F (E) | i (3.2),ET+T TF*F Fi | (E) (3.7),3.3 自顶向下的语法分析,在此，“”表示闭包运算*，且文法(3.2)与文法(3