一生二，二生三，三生万物。

语法分析

识别 和 解析

推导 ：自顶向下（术语：句型 句子，回顾形式语言与自动机课程）

归约 ：自底向上

自顶向下的语法分析

推导的两类非确定性

  • 推导哪个非终结符
  • 使用哪个产生式

对第一个不确定性进行改进：总是对最左边的非终结符推导，即最左推导

确定的自顶向下分析

要求：非终结符选择和产生式选择都是确定的，所以是无回溯的方法（预测分析）

从左往右扫描，但在扫描过程中，为了确定使用哪个产生式可能需要向前查看

分析的结果：得到唯一的最左推导，因此对文法有一定的限制，例如至少要求文法无二义性

例 对如下文法：

S→ABS\rightarrow AB
A→aAA\rightarrow aA
A→ϵA\rightarrow\epsilon
B→bB\rightarrow b
B→bBB\rightarrow bB

只需要向前看2个单词就可以确定使用的产生式：这里产生式选择的主要歧义来源于B→bB\to b和b→bBb\to bB两个产生式无法通过向前查看1个字符区分，如果将产生式优化成B→bBB\to bB和B→ϵB\to \epsilon则可以只查查看1个字符

用后面的话说，这是因为文法含有左公因子

例 对如下文法：

S→SaS\rightarrow Sa
S→bS\rightarrow b

无法通过向前查看固定数目的单词来确定使用的产生式

事实上，确定的自顶向下分析需要文法不含左递归

一个非终结符A是左递归，定义为：

∃β∈(V∪T)∗ s.t. A⇒∗Aβ\exists\beta\in (V\cup T)^*\ s.t.\ A\stackrel{*}{\Rightarrow}A\beta

FIRST和FOLLOW

FIRST(α)定义为所有可以由α推导出的串的首字符组成的集合，如果可以推导出空串，则也应包含空串

FOLLOW(A)集合定义为所有可以在某些句型中出现在A后面的终结符的集合，如果A可以作为某些句型的最右侧符号，则FOLLOW(A)包含一个特殊的符号#

FIRST集合的计算

  1. 对终结符a，则FIRST(a)={a}
  2. 对非终结符A，若A→Y1Y2...YnA\rightarrow Y_1Y_2...Y_n，假设在YkY_k之前的所有FIRST(Y)都含空串，则FIRST(A)应包含Y1Y_1至YkY_k的FIRST集合的并（但注意：空串应特殊考虑）
  3. 对串，只需要朴素地根据左侧的一些符号FIRST是否为空，类似第2步即可计算

注意 以上规则需要对每个符号反复应用，直到任何一个FIRST(X)都无法加入新的元素

FOLLOW集合的计算

类似地定义需要反复应用的规则：

  1. 将$放在FOLLOW(S)中
  2. 如果A → αBβ，则FIRST(β)中非空串元素都在FOLLOW(B)中
  3. 如果A → αB或A → αBβ但FIRST(β)含空串，则FOLLOW(A)中所有符号都在FOLLOW(B)中

LL(1)文法

定义 可以构造从左向右的只需要向前查看一个单词的预测分析器的文法

LL(1)的等价条件 LL(1)文法必须且只需满足：对任何两个不同的产生式A → α | β

  1. α和β不可推导出同首字符的串
  2. α和β至多一个可致空
  3. 如果α和β一个可致空，则另一个就不可以推导出以FOLLOW(A)中元素开头的串

预测集合 PS(A → α)定义为：

  1. 如果FIRST(α)不含空，则PS(A → α) = FIRST(α)
  2. 如果FIRST(α)含空，则PS(A → α) = (FIRST(α) - {ε})∪FOLLOW(A)

即，PS(A → α)表示所有使得当前可以选择A → α的待处理字符组成的集合，LL(1)文法的定义等价于说，文法中任何两个左端相同的产生式的预测集合无交

预测分析表

预测分析表是一个二维数组M[A,a]，其中A是非终结符，a是终结符或#，表示当前非终结符是A且输入串下一个字符是a时应采用的产生式，对每条产生式A → α，构造规则如下：

  1. 对FIRST(α)中的每一个a，A → α添加到M[A,a]中
  2. 如果FIRST(α)含空，则对FOLLOW(A)中的每一个b（可以是$），将A → α添加到M[A,b]中

根据上面对LL(1)文法的要求，容易看出，LL(1)文法构造出的预测分析表不存在某个表项有多个产生式

表驱动的LL(1)预测分析器

预测分析器维护一个栈和输入序列，二者的瞬间状态共同组成分析器的格局

预测分析器考虑当前栈顶符号和下一个输入符号，如果二者相同，消去；如果当前栈顶符号是非终结符，则使用预测分析表中的产生式；若预测分析表中对应表项为空，或二者是不同的终结符，则产生语法分析错误

递归下降LL(1)预测分析器

递归下降的预测分析器是一个基于子程序调用的预测分析模型，其入口为parseS()，根据情况选择调用诸如parseT()或matchToken('a')之类的子程序

一个非终结符的预测分析子程序的一般过程如下：

1728824376651

语法分析的错误处理

编译器错误处理原则：

  • 尽可能准确指出错误位置和错误属性
  • 尽可能进行校正

表驱动LL(1)分析中的错误处理

使用出错报告的形式：直接报告遇到的不匹配或表为空的情况

应急恢复机制：

跳过一些符号直到遇到栈顶非终结符A的同步符号：FOLLOW(A)或FIRST(A)，遇到前者则放弃A，遇到后者则处理A

递归下降LL(1)分析中的错误处理

进入和离开一个语法单元（非终结符的分析子程序）时判断当前符号是否是合理的开始符号BeginSym（即FIRST）或结束符号EndSym（可以理解为LAST），若不是，则报错（出错报告），并跳过接下来第一个BeginSym或EndSym之前的任何符号（应急恢复），遇到BeginSym则返回初始，遇到EndSym则结束

文法变换

消除左递归

直接左递归的消除

对于

P→Pα ∣ βP\rightarrow P\alpha\ |\ \beta

改写为

P→βQP\rightarrow \beta Q
Q→αQ ∣ ϵQ\rightarrow \alpha Q\ |\ \epsilon

一般左递归的消除

对于无回路（即A可推导出A，这说明文法二义）、无ε-产生式的文法，通过下列步骤消除一般左递归：

  1. 将非终结符排列成序列
  2. 对序列中每个非终结符，展开其产生式，使其中不包含序列中在其之前的符号，过程中一旦出现直接左递归则将其消除
  3. 化简文法

提取左公因子

提取左公因子规则 对于

P→αβ ∣ αγP\rightarrow \alpha\beta\ |\ \alpha\gamma

可以用以下产生式替换：

P→αQP\rightarrow \alpha Q
Q→β ∣ γQ\rightarrow \beta\ |\ \gamma

注 提取左公因子与左递归无关，进而与文法是否可以无回溯预测分析无关，但提取左公因子可以将一些非LL(1)文法转化为LL(1)文法

LL(K)文法的一些理论上的结论

可判定性

  • 给定k＞0，一个CFG是否是LL(k)文法是可判定的
  • 对于一个CFG，是否存在k＞0，使该文法是LL(k)文法，是不可判定的
  • 是否存在于文法等价的LL(k)文法，是不可判定的
  • 两个LL(k)文法的语言是否相等是可判定的

其他

  • LL(k)文法是无二义文法
  • LL(k)文法中不存在左递归的非终结符
  • 给定k＞0，不含ε产生式的LL(k)文法的语言类真包含于不含ε产生式的LL(k+1)文法的语言类