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

第 6 讲;第三章 语法分析;第三章《语法分析》 3.3 自顶向下的语法分析 递归下降分析法 LL(1)分析法（下一讲内容） 重点掌握 消除左递归 消除回溯 构建递归下降子程序 ;3.3 自顶向下的语法分析;1、不确定的自顶向下分析方法 假定文法G[S]为 　　 S?→?xAy　　?? A?→?ab | a 若输入串为xay，则其分析过程如下： (1)建立根节点S； (2)关于S的产生式只有一个，则生长语法树, 匹配语法树的第一个终结符x； (3) A?→?ab | a 有两个候选式，选择第一个, 并且匹配语法树的第二个叶子节点a； (4)输入串xay期待匹配y,而语法树中的b与之匹配失败； ;1、不确定的自顶向下分析方法 假定文法G[S]为 　　 S?→?xAy　　?? A?→?ab | a 若输入串为xay，则其分析过程如下： (5)撤销匹配a， 注销A所生成的子树，回溯； (6)选择产生式A?→?a，重新匹配a； (7) 匹配输入串的字符y；而语法树的最后 一个叶子节点也是y,因此语法树和输入串xay匹配成功。 ;小结：关于不确定的自顶向下分析方法 这种自顶向下的分析是一个不断试探的过程；即，在分析过程中，如果出现多个产生式(即候选式)可供选择，则逐一试探每一候选式进行匹配，每当一次试探失败，就选取下一候选式再进行试探； 此时，必须回溯到这一次试探的初始现场，包括注销已生长的子树及将匹配指针调回到失败前的状态。 这种带回溯的自顶向下分析方法实际上是一种穷举的试探方法，其分析效率极低，在实用的编译程序中很少使用。 ;2、确定的自顶向下分析方法 确定的自顶向下分析要求文法满足两个条件： (1) 文法不含左递归：即不存在这样的非终结符号A：有A→A…存在或者有 ； 原因：左递归的文法使自顶向下分析工作陷入无限循环 E→E+T;3、消除左递归 方法： 引入一个新的非终结符，把含有左递归的产生式改写为右递归。 ;再看下面不含A的直接左递归的产生式： A?→?βA A →?α A | ε;3、消除左递归 ;例如，含有直接左递归的表达式文法G[E]为　　 　　;;;;(2) 执行下述循环语句将消除所有左递归 for(i=1;i=n;i++) {　　 for(j=1;j=i?1;j++)　　 { 把一个形如：　　 的产生式改写为　　 Ai→δ1γ | δ2γ | … | δkγ | β1 | β2 | … | βn； 按消除直接左递归的方法消除Ai的直接左递归；　　 }　　}(3) 化简所得到的文法，去掉无用的产生式：去掉那些从开始符号S出发，推导中无法出现的非终结符产生式。;例：消除间接左递归;消除直接左递归，得到： S → abcS |bcS |cS S → abcS | ε Q → Sab|ab|b R → Sa|a ;注意1：消除左递归之前的文法不允许有ε产生式，否则无法得到等效的无左递归文法。因此，如果原文法中有ε的产生式，则需将文法改写为无ε的产生式的文法。 ;实际上，也可以用数学中的分配律来消除文法中的左递归。对文法(3.3)，首先将R的产生式代入到Q的产生式中并按分配律展开(注：“(”和“)”不是终结符)得Q?→?(Sa | a)b | b 展开后：Q?→?Sab | ab | b;4、消除回溯 回溯发生的原因在于候选式存在公共的左因子，如产生式A如下： A?→?αβ1 | αβ2 此时，如果输入串待分析的字符串前缀为α，则选用哪个候 选式以寻求与输入串匹配就难以确定。 倘若候选式不含公共左因子，则推导出的首字符能与输入串匹配的那个候选式便是惟一的匹配。 　　 S?→?xAy　　?? A?→?a | b 如何匹配 xay ？ ;4、消除回溯的方法 一般情况下，设文法中关于A的产生式为　　A?→?δβ1 | δβ2 | … | δβi | βi+1 | … | βj (3.5)　　那么，可以把这些产生式改写为