分类

语法分析可以按照分析方向分为两类

自顶向下/自底向上

自顶向下的分析

从分析树的顶部向底部方向构造分析树

每一步推导需要做两个选择：

（1）需要替换哪个非终结符

（2）用哪个产生式

最左推导

在最左推导中，总是选择每个句型的最左非终结符进行替换

经过最左推导得到的句型叫做最左句型

最右推导

在自底向上的分析中，总是采用最左规约的方式，因此把最左规约称为规范规约，相对应最右推导成为规范推导

递归下降分析

由于语法分析器一般从左至右读取代码，故采用最左推导

根据输入流中的下一个终结符，选择最左非终结符的有关候选式

循环过程，每个过程对应目标句子中的非终结符

问题：可能需要回溯，导致效率低

预测分析

预测分析是递归下降分析技术的特例，通过在输入中向前看固定个数 k 个符号来选择正确的 A-产生式，称为 LL（k）文法

文法转换

含有 A → A α A \to A\alpha A→Aα的产生式的文法称为直接左递归

如果一个文法中存在非终结符 A → + A α A \to^+ A \alpha A→+Aα，那么这个文法就是左递归的

经过两步及以上产生的左递归被称为是间接左递归

左递归文法会使递归下降分析器无限循环

消除直接左递归

A → A α ∣ β ， β 不以 A 开头 A\to A\alpha | \beta \\ ，\beta 不以 A 开头 A→Aα∣β，β不以A开头

可以推导出 r = β α ∗ r = \beta\alpha^* r=βα∗

故可以写成

KaTeX parse error: Undefined control sequence: \betaA at position 6: A\to \̲b̲e̲t̲a̲A̲’

A ’ → α A ’ ∣ ϵ A’ \to \alpha A’|\epsilon A’→αA’∣ϵ

就避开了直接左递归，转换成了右递归

消除间接左递归

e.g.

S → A a ∣ b S \to A a|b S→Aa∣b

A → A c ∣ S d ∣ ϵ A \to Ac|Sd|\epsilon A→Ac∣Sd∣ϵ

在实际推导时会出现：

S = > A a S => Aa S=>Aa

= > S d a => Sda =>Sda

出现了左递归

解决方法：将 S 产生式放入 A 产生式中，然后消除 A产生式的直接左递归

消除公共前缀

LL1 文法

S_文法：每个产生式的右部都以终结符开始，同一非终结符的各个候选式的首终结符都不同

产生式的后继符号集

在某个句型中紧跟在 A 后面的终结符的集合，记为 FOLLOW 集

产生式的可选集

一个产生式的可选集指的是当选用该产生式进行推导的时候，对应输入符号的集合，

e.g. S E L E C T ( A → a β ) = a SELECT(A \to a\beta) = \\{a\\} SELECT(A→aβ)=a

q_文法：每个产生式的右部为 epsilon/首字母为终结符，且具有相同左部的产生式具有不相交的可选集

串首终结符集

串首第一个符号是非终结符，简称首终结符

给定一个文法符号串 alpha，alpha 的串首终结符集 FIRST（alpha）被定义为 alpha 推导出的所有串首终结符构成的集合

对于可选集 SELECT，

如果空字符不属于 FIRST 集， S E L E C T ( A → α ) = F I R S T ( α ) SELECT(A \to \alpha) = FIRST(\alpha) SELECT(A→α)=FIRST(α)

如果空字符属于 FIRST 集， S E L E C T ( A → α ) = ( F I R S T ( a ) − ϵ ) ∪ F O L L O W ( A ) SELECT(A \to \alpha) = (FIRST(a) - \\{\epsilon\\}) \cup FOLLOW(A) SELECT(A→α)=(FIRST(a)−ϵ)∪FOLLOW(A)

LL1 文法的定义

根据上面的概念，在文法 G 中，任意两个具有相同左部的产生式 A → α ∣ β A \to\alpha|\beta A→α∣β：

（1）如果 alpha 和 beta 均不能推出空字符，则 F I R S T ( α ) ∩ F I R S T ( β ) = ∅ FIRST(\alpha)\cap FIRST(\beta) = \varnothing FIRST(α)∩FIRST(β)=∅

（2）alpha 和 beta 至多有一个能够推导出空字符

如果 β = > ϵ \beta => \epsilon β=>ϵ，则 F I R S T ( α ) ∩ F O L L O W ( A ) = ∅ FIRST(\alpha)\cap FOLLOW(A) = \varnothing FIRST(α)∩FOLLOW(A)=∅

对于 alpha 同理

（3）不可能同时推出空字符，否则会产生二义性

S → α → ϵ , S → β → ϵ S \to \alpha \to \epsilon,S \to \beta \to \epsilon S→α→ϵ,S→β→ϵ

FIRST 集细究

对于一串产生式，寻找 FIRST 集方法如下：

E → T E ’ E \to TE’ E→TE’

E ’ → + T E ∣ ϵ E’ \to +TE|\epsilon E’→+TE∣ϵ

T → F T ’ T \to FT’ T→FT’

T ’ → ∗ F T ’ ∣ ϵ T’ \to *FT’|\epsilon T’→∗FT’∣ϵ

F → ( E ) ∣ i d F \to (E)|id F→(E)∣id

（1）查看各产生式右部第一个符号是否为终结符，如果为终结符，则直接填在对应左部的 FIRST 集中

（2）寻找空串，并将空串添加到对应的 FIRST 集中

（3）对于串首是非终结符的产生式，则看该非终结符下所具有的 FIRST 集合

不断运用这三个规则，就可以得到 FIRST 集的集合

FOLLOW 集细究

（1）首先查看开始符号的位置，开始符号算作该产生式集合所构成句型的最右符号，FOLLOW 集包含$

（2）观察每个式子的右部，两个连接的非终结符，后者 FIRST 集中的终结符则在前者的 FOLLOW 集中

（3）对于每个产生式右部的最末尾，如果其右边没有终结符，则左部的 FOLLOW 集被添加到该非终结符的 FOLLOW 集中

（4）对于 FIRST包含空字符的非终结符（且在右部末尾），其前面的非终结符填入左部非终结符的 FOLLOW 集

（5）对于右部中，一个非终结符后紧跟着一个终结符，将该终结符添加到前者的 FOLLOW 集中

重复以上几步作为一个循环，直到这些 FOLLOW 集不再发生变化，此时结束循环，认为找到了所有 FOLLOW 集

该例子最终的 FOLLOW 集如下所示

SELECT 集的细究

对于原产生式，可改写为

E → T E ’ E \to TE’ E→TE’

E ’ → + T E E’ \to +TE E’→+TE

E ’ → ϵ E’ \to \epsilon E’→ϵ

T → F T ’ T \to FT’ T→FT’

T ’ → ∗ F T ’ T’ \to *FT’ T’→∗FT’

T ’ → ϵ T’ \to \epsilon T’→ϵ

F → ( E ) F \to (E) F→(E)

F → i d F \to id F→id

在拥有了 FIRST 集和 FOLLOW 集后，判断 SELECT 集只需要以下三种分类方法：

（1）如果产生式右部第一个为终结符，则该产生式 SELECT集就为该终结符

（2）如果产生式右部第一个为非终结符，则 SELECT 集为该非终结符的 FIRST 集

（3）如果产生式右部为空字符，则 SELECT 集为产生式左部非终结符的 FOLLOW 集

遵循这三个原则，我们可以得到：

此时对于相同左部的产生式，其满足之前定义的 LL1 文法的要求，或者在此处直接观察 SELECT 集，red：SELECT 集不相交则说明其为 LL1 文法

所以上述文法是 LL1 文法

同时拥有了SELECT 集之后也可以很轻松的定义预测分析表：

预测分析表

递归的预测分析法

在递归下降分析中，编写每一个非终结符对应的过程时，根据预测分析表进行产生式的选择

e.g.

非递归的预测分析法

非递归的预测分析不需要为每个非终结符编写递归下降程序，而是根据预测分析表构造一个自动机，也叫表驱动的预测分析

类似有穷自动机，但是增加了栈，用于记忆，一方面从预测分析表中使用新产生式替换，另一方面当遇到目标输入时将当前终结符出栈，同时开始考虑下一个终结符

递归与非递归之对比

递归的预测分析表规模比较大，不需要载入预测表，而且比较直观，但是在自动生成和效率上不占优势；非递归的预测方法尽管不算特别直观且需要载入预测分析表，但是对于机器自动生成的难度来说较小，而且效率也比较高

预测分析中的错误处理

两种情况可以检测到错误

（1）栈顶的终结符和当前输入符号不匹配

（2）栈顶的非终结符与当前输入符号在预测分析表中在对应项为空

恐慌模式

忽略输入中的一些符号，直到输入中出现同步词法单元集合中的某个词法单元

一般将非终结符的 FOLLOW 集认为是同步词法单元

M（A，a），其中 A 表示当前栈顶符号，a 表示输入符号，如果 M = null，则表示检测到错误，根据恐慌模式忽略 a

如果遇到 synch，则弹出栈顶的非终结符 A，尝试继续分析后面的语法符号

如果栈顶此时为终结符且与输入符号不匹配，则弹出栈顶的终结符