编译原理-第4章+语法分析.ppt

第四章 语法分析 §4.1 引言 §4.2 自顶向下语法分析 §4.3 自底向上语法分析 §4.4 语法分析程序的自动生成 §4.1 引言 一、语法分析任务 1.语法检查 2.根据语法符号进行一定处理加工 二、语法分析方法 1.自顶向下语法分析方法 2.自底向上语法分析方法 一、语法分析任务 词法分析阶段，主要介绍了单词符号的结构、识别（用状态转换图），描述（通过正规式）以及有限自动机DFA和NFA。 在一个编译程序对某个源程序完成了词法工作以后,就进入了语法分析阶段。由词法分析程序所产生的单词符号流，作为语法分析程序的输入串，按文法规则分析检查是否构成了合法的句子。 首先来了解一下语法分析的任务。 二、语法分析方法 语法分析方法很多，但能够产生计算机程序并能得到广泛应用的主要有两大类，按照生成语法树的顺序，分别称为自顶向下和自底向上分析方法。 §4.2 自顶向下语法分析 一、消除左递归 二、消除回溯 三、递归下降分析法 四、LL(1)分析法 一、消除左递归 就一般而言，关于Ａ的规则具有下面形式： Ａ∷＝Ａα１｜Ａα２｜…｜Ａαn｜β１｜β２｜…｜βn 这时可改写成如下形式： Ａ∷＝A(α１｜α２｜…｜αn｜) ｜β１｜β２｜…｜βn 由消除直接左递归方法，得 Ａ ∷＝ (β１｜β２｜…｜βn)Ａ′ Ａ′∷＝ (α１｜α２｜…｜αn)Ａ′｜ε 上述两种方法可消除任意直接左递归，但不能消除间接左递归 例如，有文法Ｇ［Ｓ］ Ｓ∷＝Ｑc｜c Ｑ∷＝Ｒb｜b Ｒ∷＝Ｓa｜a 该文法无直接左递归，但有间接左递归，例如有 Ｓ? Ｑc ? Ｒbc ? Ｓabc 即Ｓ?＋Ｓabc 3）消除间接左递归 对于间接左递归先将间接左递归变成直接左递归，然后再消除直接左递归 例如；A ∷＝aB|Bb (1) B ∷＝Ac|d (2) 先将（1）代入（2）中，得 B ∷＝Bbc|aBc|d (3) 由此将(3)改写为； B ∷＝（aBc|d)B’ B’∷＝bcB’|? 加入文法开始符号的产生式得消除左递归后的等价文法为： A ∷＝aB|Bb B ∷＝(aBc|d)B’ B’∷＝bcB’|? 4) 消除文法递归的一般算法 要求：文法不含形如Ａ? ＋Ａ的推导，也不存在Ａ∷＝ε这样规则，算法思想如下： ①将文法Ｇ的所有非终结符整理成某种顺序Ｕ１，Ｕ２，…Ｕn ②从U1开始消除U1规则的直接左递归 ③用左部为U1的所有规则右部替换左部为U2，右部以U1开始的规则中的U1，并消除U2规则的直接左递归。 ④用类似的方法用U1，U2的右部替换左部为U3，右部以U1，U2开始的规则中，消除U3规则中的直接左递归。 ⑤重复上一步，直到最后把左部为U1，U2，…Un-1的右部带入Un规则中，并消除Un中的直接左递归。 ⑥消除多余规则 ① 将文法Ｇ的所有非终结符整理成某种顺序Ｕ１，Ｕ２，…Ｕn，然后按此顺序执行下一步； ② 执行循环语句： ＦＯＲ i:＝１ ＴＯ n ＤＯ ＢＥＧＩＮ ＦＯＲ j∶＝１ ＴＯ i-1 ＤＯ ＢＥＧＩＮ 把形如 Ｕi∷＝Ｕjy的规则改写成 Ui∷＝x１y｜x２y｜…｜xky 其中Uj∷＝x１｜x２｜…｜xk 是Uj的所有规则 ＥＮＤ 消除关于Ui规则中直接左递归 ＥＮＤ ③ 去掉多余规则（如果有的话） 例4.2设有文法Ｇ［Ｓ］ Ｓ∷＝Ａa｜b Ａ∷＝Ａc｜Ｓd｜e 应用上述算法，将非终结符排列Ｓ，Ａ。然后执行循环语句 ＦＯＲ i∶＝１ ＴＯ 2 ＤＯ ＢＥＧＩＮ ＦＯＲ j∶＝１ ＴＯ i-１ ＤＯ ＢＥＧＩＮ … ＥＮＤ 消除Ui规则中直接左递归 ＥＮＤ 当i＝１时，上述语句对文法Ｇ不产生影响。 当i＝２时，应改写规则Ａ∷＝Ｓd， 因为Ｓ∷＝Ａa｜b， 所以Ａ∷＝Ａad｜bd， 此时文法Ｇ变换成为 Ｓ∷＝Ａa｜b Ａ∷＝Ａc ｜Ａad｜bd｜e 消除关于Ａ的直接左递归即可。 Ｓ∷＝Ａa｜b Ａ∷＝bdＡ’｜eＡ’ Ａ’∷＝cＡ’