编译原理学习笔记3（自上而下语法分析）

接上编译原理学习笔记2，继续学语法分析

3.3 自上而下语法分析

自上而下分析的基本思想是：对于任何一个输入序列，从文法的开始符号开始，进行最左推导，直到得到一个合法句子或者发现一个非法结构，自上而下建立分析树。整个分析是一个试探+回溯的过程，因此会存在一些问题。

1）如果存在递归的产生式，则会使推导陷入死循环；
2）如果多个产生式间存在公共前缀，则可能会造成大量回溯；
3）如果语法存在二义性，则多次分析可能会产生不同的结果。

为了克服以上缺点，需要采取一些优化方法对语法进行重写：

1）消除左递归；
2）提取公共左因子；
3）消除二义性。

3.3.1 消除左递归

1）消除文法的直接左递归
直接左递归，即产生式左部的非终结符出现在了产生式的右部。
算法：比如，对于仅有两个候选项的产生式A->Aα|β，可转换成 A->βA’和A’->αA’|ε 来消除左递归，可推广至更多个候选项，只需增加产生式中的β和α的个数。

该算法可以这样理解：原本的产生式对应的语言为β开头，后面跟着n个α，因此可以令一个产生式为A->βA’来创造β，另一个产生式来递归产生α，并增加一个ε来让递归得以结束。

2）消除文法的间接左递归
间接左递归，可以通过画有向图来判断，如果有环，则说明有递归。
算法：比如，对于产生式，S->Aa|b和A->Ac|Sd|ε（S的递归不直接，但是有传递性），可转换成S->Aa|b,A->bdA’|A’,A’->cA’|adA’|ε。

该算法可以这样理解：用S右部的两个产生式去替换A右部里的S，即可将A的产生式变成直接左递归的形式，便可结合前面的算法来消除。
但若文法中含有A -> A似的产生式则该算法失效。

3.3.2 提取左因子

其实就是提取公共前缀，将后面的部分变为一个新的产生式，理解起来较为简单。
一般是先进行消除左递归，通常消除之后也能消除掉部分的左因子。

3.3.3 消除二义性

若文法存在二义性，则反复执行推导会产生不同的结果，得到多种分析树，从而导致预测分析表无法正常工作，这种情况下，需要改写文法。
二义性通常是由算符的优先级和结合性导致的，因此可以人为地引导推导进行，即将产生式中算符的右边的非终结符换成一个新的非终结符，生成一个新的产生式，人为消除了左右不定。

例如：E->E+E | id 可以改写为 E->T | E+T 和 T->id

3.3.4 递归下降子程序

类似于函数调用，即对产生式中的终结符调用match()函数来匹配，而非终结符定义成为一个函数来调用。

例如：A->adSc，S->a的递归下降子程序为：
A() { match(a); match(d); S(); match; }
S() { match(a); }