自顶向下的语法分析

自顶向下分析试图从初始符号开始，给出目标句子的一个推导。

递归下降分析法

递归下降分析的实现

递归下降分析法从直观上是很好理解的，以如下文法为例：

• $E\rightarrow T|T+E$
• $T\rightarrow int|int\ast T|(E)$

定义全局指针 next 指向下一个待读入的 token，以及函数 term 来判断该 token 是否为指定类型终结符：

bool term(Token tok){
    return *next++ == tok;
}

然后根据每个产生式，定义一系列相互递归调用的函数来判断目标句子是否符合文法：

bool E1(){return T();}
bool E2(){return T()&&term(PLUS)&&E();}
bool E(){
    Token *save = next;
    return (next = save, E1())
        || (next = save, E2());
}
bool T1(){return term(INT);}
bool T2(){return term(INT)&&term(TIMES)&&T();}
bool T3(){return term(OPEN)&&E()&&term(CLOSE);}
bool T(){
    Token *save = next;
    return (next = save, T1())
        || (next = save, T2())
        || (next = save, T3());
}

初始化 next 指针后，调用 E 即可判断目标句子是否符合文法。

递归下降分析的局限性

上面展示的递归下降分析法非常便于手写实现，但是却不具有通用性，能够识别的语法也是有限的，下面介绍其几个主要的局限性。

二义性

用上面的程序分析句子 int*int 无法成功，这是因为 int 可以同时作为产生式 $T\rightarrow int$和$T\rightarrow int\ast T$的前缀，但只有后者是正确的，上述程序无法处理这种二义性。

这个问题可以通过增加回溯解决，而不增加代码编写难度的做法则是提取左因子，即将一个非终结符具有相同前缀的多个产生式进行重写。对于本例，可以将

• $T\rightarrow int|int\ast T|(E)$

改写为

• $T\rightarrow intA|(E)$
• $A\rightarrow\ast T|\varepsilon$

左递归

考虑产生式

• $S\rightarrow Sa|b$

其对应的分析函数为：

bool S(){
    Token *save = next;
    return (next = save, S()&&term(a))
        || (next = save, term(b));
}

显然这个函数会陷入无穷的递归调用而无法返回。上述现象称为直接左递归，若通过中间变量产生左递归则成为间接左递归。想要让递归下降分析法正确工作，就需要通过引入中间变量来消除左递归。

对于上述文法，可以将其改写为

• $S\rightarrow bA$
• $A\rightarrow aA|\varepsilon$

预测分析：LL分析法

递归下降分析法无法避免选择了错误的产生式后进行的大量回溯。如果能够根据后续字符选择唯一的产生式，就能够提高解析的效率。LL分析法就是这样一种预测型的自顶向下解析法：LL(k)的含义是从左向右、最左派生、根据后续的 k 个 token 来预测产生式。

具体来说，LL分析法用一个栈来存储推导过程中产生的终结符和非终结符，同时利用一张预测分析表指出在已知当前栈顶符号和下一个读入 token 的情况下应当如何对该符号进行推导。

First、Follow集

为了能够进行产生式的预测，需要考察文法中非终结符和终结符之间的关系。为此引入了$First$和$Follow$集的概念。对于非终结符$A$而言：

• $First(A)$指$A$能派生出的所有句子的第一个终结符的集合；

• $Follow(A)$指该文法派生过程中所有可能出现在$A$后的第一个终结符的集合。

注意，$\varepsilon\in First(A)$的条件较为特殊，是$A$能推导出空串。

LL(1) 分析表

藉由$First$和$Follow$集的概念，我们可以构造 LL(1) 分析表。

对每个产生式 $A\rightarrow\alpha$ 进行如下操作：

1. 对所有 $t\in First(\alpha),T[A][t]=\alpha$
2. 如果 $\varepsilon\in Fisrt(\alpha)$，对所有 $t\in Follow(A),T[A][t]=\alpha$

若某个表项有多个可用产生式，那么该文法不是 LL(1) 文法；若某个表项无可用产生式，说明 LL 分析在该状态遇到了错误，识别失败。

分析流程

1. 将#放入符号栈；
2. 将文法初始符号$S$放入符号栈；
3. 从缓冲区读入读指针指向的 token $t$;
4. 若从符号栈栈顶取出符号$A$：
   • 若$A$是终结符，且等于$t$，则$A$出栈，缓冲区读指针后移；
   • 若$A$是非终结符，且$T[A][t]=\alpha$，则$A$出栈，将$\alpha$中符号倒序入栈，缓冲区读指针不动；
   • 否则进行错误处理；
5. 若符号栈为空则已识别完成，否则回到 3。