编译原理语法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为 SxAyAab|a 若输入串为xay，则其分析过程如下：(1)建立根节点S；(2)关于S的产生式只有一个，则生长语法树,匹配语法树的第一个终结符x；(3)Aab|a 有两个候选式，选择第一个,并且匹配语法树的第二个叶子节点a；(4)输入串xay期待匹配y,而语法树中的b与之匹配失败；,S,A,y,a,b,x,3.3 自顶向下的语法分析,1、不确定的自顶向下分析方法假定文法GS为 SxAyAab|a 若输入串为xay，则其分析过程如下：(5)撤销匹配a，注销A所生成的子树，回溯；(6)选择产生式Aa，重新匹配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的直接左递归的产生式形如AA|其中，、是任意的符号串且不以A开头。该产生式所能推导的句子如下：,3.3 自顶向下的语法分析,再看下面不含A的直接左递归的产生式：AA A A|,这两个产生式所能推导的句子如下：,可见，两种产生式所推导的结果相同：都能描述正规表达式*,3.3 自顶向下的语法分析,3、消除左递归,规则：将产生式 AA|改写为：AA A A|其中，A是新引入的非终结符。不可缺少，否则推导过程无法结束。,3.3 自顶向下的语法分析,例如，含有直接左递归的表达式文法GE为,GE:EE+T|T TT*F|F F(E)|i,ETE E+TE|,(3.2),经过消去直接左递归后得到文法GE为,TFTT*FT|,GE:,F(E)|i,3.3 自顶向下的语法分析,3、消除左递归一般情况下，设文法中关于A的产生式为 AA1|A2|Am|1|2|n其中，每个都不等于且每个都不以A开头，则消除A的直接左递归性就是将其改为：例如，对产生式 EE+T|E-T|T，消除直接左递归后为,3.3 自顶向下的语法分析,R=(1|2|n)(1|2|m)*,ETEE+TE|-TE|,3、消除间接左递归 注意：也有些文法是含有间接左递归的，如下述文法GS:GS:SQ c|c QR b|b RS 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:SQ c|cQR b|b RS a|a（3.3）,消除文法（3.3）的左递归：,解答,1、令3个非终结符的排列顺序为R、Q、S，2、由于R不存在直接左递归，不需要进行操作；当i=2,j=1时，将 QR b|b 替换成 Q Sab|ab|b（不需要消除直接左递归）,当i=3,j=2时，将SQ 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 展开后：QSab|ab|b,再将改变后Q的产生式代入到S的产生式中并按分配律展开得S(Sab|ab|b)c|c 展开后：SSabc|abc|bc|c在消除S的直接左递归后同样得到文法(3.4)。,例：消除间接左递归,4、消除回溯回溯发生的原因在于候选式存在公共的左因子，如产生式A如下：A1|2 此时，如果输入串待分析的字符串前缀为，则选用哪个候 选式以寻求与输入串匹配就难以确定。倘若候选式不含公共左因子，则推导出的首字符能与输入串匹配的那个候选式便是惟一的匹配。SxAyAa|b如何匹配 xay？,3.3 自顶向下的语法分析,4、消除回溯的方法一般情况下，设文法中关于A的产生式为A1|2|i|i+1|j(3.5)那么，可以把这些产生式改写为(3.6)经过反复提取左因子，就能把每个非终结符(包括新引进者)的所有候选首字符集变为两两不相交(即不含公共左因子)。,3.3 自顶向下的语法分析,4、消除回溯的方法也可以用数学中提取公共因子的办法来提取公共左因子。如对式(3.5)提取公共(左)因子后得 A1|2|i|i+1|j A(1|2|i)|i+1|j 将产生式中由“(”和“)”括起的部分以非终结符A 命名则得到式(3.6)(3.6)例如，对文法GA:AaAB|a|b提取公共左因子后的文法GA为?,3.3 自顶向下的语法分析,GA:AaA|b AAB|,4、递归下降分析器递归下降分析法：是确定的自上而下分析法。它的基本思想是，对文法中的每个非终结符编写一个函数（或子程序），每个函数的功能是识别由该非终结符所表示的语法成分。由于描述语言的文法经常是递归定义的，因此相应的这组函数也必然以互相递归的方式进行调用，所以这种分析方法称为递归子程序法或递归下降分析法递归下降分析程序也称为递归下降分析器，对文法的要求是：1、文法不含左递归2、每个非终结符的所有候选终结首字符集两两不相交(候选式不含公共左因子),3.3 自顶向下的语法分析,递归下降分析器的设计示例,GE:ETE E+TE|TFT T*FT|F(E)|i（3.2）,GE:EE+T|T TT*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();ETE 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 自顶向下的语法分析,EE+T|TTT*F|FF(E)|i(3.2),ET+TTF*FFi|(E)(3.7),3.3 自顶向下的语法分析,在此，“”表示闭包运算*，且文法(3.2)与文法(3.7)是等价的，文法(3.7)不含左递归。根据文法(3.7)可得到如图3-14所示一组描述非终结符E、T和F的状态转换图,因此，前面的递归下降分析器程序可以删除函数E()和T(),4、递归下降分析器 ET+T void E()T();while(lookahead=+)/原则5：闭包对应while循环 match(+);T();/候选式是，接收非+，E认为自动获得匹配，不返回error/E()TF*F 可以仿照E编写程序T(),F()不做修改,3.3 自顶向下的语法分析,
