第4章 语法分析.ppt

1．带回溯的自上而下分析方法 假定文法G[S]为： S→xAy A→ab∣a 若输入串为xay，则其分析过程如下： (1) 首先建立根结点S。 (2) 文法关于S的产生式只有一个，也即由S生长的语法树如图3–11(a)所示，它的第一个终结符x与输入串待分析的字符x匹配。此时，下一个待分析的字符为a，期待着与语法树中在x右侧且与x相邻的叶结点A匹配。 (3) 非终结符A有两个候选式，先选用第一个候选式生长的语法树(如图3–11(b)所示)；这时语法树的第二个叶结点a恰与待分析的字符a匹配。 (4) 输入串中下一个待分析的字符为y，它期待与第三个叶结点b匹配，但匹配时发现这两个字符是不同的，即匹配失败，这是因为生成A的子树时所选用的是其第一个候选式。 (5) 因不匹配而将A所生成的这棵子树注销，即把匹配指针回退到输入串的第二个字符a，也就是恢复与A匹配时的现场，即(3)之前。 (6) 此时A选用第二个候选式并生长语法树如图3–11(c)所示，这时第二个叶结点a与输入串的第二个叶结点a匹配。 (7) 此时输入串的下一个待分析字符指向y，而语法树的下一个未匹配的叶结点也为y，两者恰好匹配。因此，图3–11(c)的语法树即为输入串xay的语法树。 2、无回溯的自上而下分析 要求文法满足下述两个条件： (1) 文法不含左递归，即不存在这样的非终结符号A：有A→A…存在或者有A Aα； (2) 无回溯，对文法的任一非终结符号，当其产生式右部有多个候选式可供选择时，各候选式所推出的终结符号串的首字符集合要两两不相交。 3．消除左递归 3.1直接消除左递归：引入一个新的非终结符，把含有左递归的产生式改为右递归。 设关于非终结符A的直接左递归的产生式形如 A→Aα∣β 其中，α、β是任意的符号串且β不以A开头。这时，可将A的产生式改写为如下的右递归形式： 例：含有直接左递归的表达式文法G[E]为： G[E]: E→E+T∣T T→T*F∣F F→(E)∣i 经过消去直接左递归后得到文法G[E]为： G[E]: E→TE E→+TE∣ε T→FT T→*FT∣ε F→(E) ∣i 一般情况下，设文法中关于A的产生式为 A→Aα1∣Aα2∣…∣Aαm∣β1∣β2∣…∣βn 其中，每个α都不等于ε且每个β都不以A开头，则消除A的直接左递归性就是将其改写为： 3.2消除文法左递归：设文法不含回路(形如A A的推导)，且产生式的右部也不含ε的候选式，算法： (1) 将文法G[S]的所有非终结符按一给定的顺序排列：A1、A2、…、An ； (2) 执行下述循环语句将间接左递归改为直接左递归： for (i=1;i=n;i++) for (j=1;j=i?1;j++) {a.把一个形如： 的产生式改写为：Ai→δ1γ∣δ2γ∣…∣δkγ∣β1∣β2∣…∣βn； b.按消除直接左递归的方法消除Ai的直接左递归； } (3) 化简由(2)所得的文法，即去掉那些从开始符号S出发，在推导中无法出现的非终结符的产生式(去掉多余产生式)。 例 4．消除回溯 回溯发生的原因在于候选式存在公共的左因子， 如产生式A如下：A→αβ1∣αβ2 设文法中关于A的产生式为 A→δβ1∣δβ2∣…∣δβi∣βi+1∣…∣βj （3.5） 那么，可以把这些产生式改写为 也可以用数学中提取公共因子的办法来提取公共左因子。如对式(3.5)提取公共(左)因子后得 A→δ(β1∣β2∣…∣β i)∣βi+1∣…∣βj (注：“(”与“)”为元语言符号) 将产生式中由“(”和“)”括起的部分以非终结符A命名则得到式(3.6)。 5．递归下降分析器 在不含左递归和每个非终结符的所有候选终结首符集都两两不相交的条件下，构造一个不带回溯的自上而下的分析程序，这个分析程序是由一组递归过程(或函数)组成的，每个过程(