编译器笔记8-语法分析
语法分析的基本任务就是根据给定的文法识别数据中的各类短语并构造它的分析树。如果输入串的各个单词恰好自左向右地分布在分析树的各个叶节点上。那么这个词串就是这个语言的句子否则就不是。
自顶向下分析概述
- 自顶向下的分析(Top-Down Parsing)
从分析树的顶部（根节点）向底部（叶节点）方向构造分析树，可以看成是从文法开始符号S推导出词串w的过程。
例.png
每一步推导中，都需要做两个选择
- 替换当前句型中的哪个非终结符
- 用该非终结符的哪个候选式进行替换
- 最左推导(Left-most Derivation)
在最左推导中，总是选择每个句型的最左非终结符进行替换。
推导过程.png
- 最右推导 (Right-most Derivation)
在最右推导中，总是选择每个句型的最右非终结符进行替换。
例.png
在自底向上的分析中，总是采用最左归约的方式，因此把最左归约称为规范归约，而最右推导相应地称为规范推导。
- 最左推导和最右推导的唯一性
最左推导和最右推导的唯一性.png
- 自顶向下的语法分析采用最左推导方式
- 总是选择每个句型的最左非终结符进行替换。
- 根据输入流中的下一个终结符，选择最左非终结符的一个候选式。
例.png
- 自顶向下语法分析的通用形式
递归下降分析（Recursive-Descent Parsing）
- 由一组过程组成，每个过程对应一个非终结符。
- 从文法开始符号S对应的过程开始，其中递归调用文法中其他非终结符对应的过程。如果S对应的过程体恰好扫描了整个输入串，则成功完成语法分析。
Recursive-Descent Parsing.png
缺点：当A对应多个产生式时，可能会发生回溯。
- 预测分析(Predictive Parsing)
预测分析是递归下降分析技术的一个特例，通过在输入中向前看固定个数（通常是一个）符号来选择正确的A-产生式。
ps: 可以对某些文法构造出向前看k个输入符号的预测分析器，该类文法有时也称为LL(k)文法类，预测分析不需要回溯，是一种确定的自顶向下分析方法。
文法转换
事实上并不是所有文法都适合自顶向下的分析，可以改造文法使其适合自顶向下分析。
问题1.png
左递归文法会使递归下降分析器陷入无限循环，例子如下：
问题2.png
- 消除直接左递归
消除直接左递归.png
消除直接左递归的一般形式.png
- 消除间接左递归
消除间接左递归.png
- 消除左递归算法
消除左递归算法.png
- 提取左公因子
Left Factoring.png
说明：假设输入的是acd,则在读到a文法G中S有两种选择如果选择错误就要回溯效率降低。但读到a时文法G`中S开始不用做选择,并在读到c时 S'中可以根据c作出正确的选择。因此达到推迟决定的作用以避免不必要的回溯。
提取左公因子算法
提取左公因子算法.png
LL(1) 文法
要想分析器以预测分析法的方式去工作，我们希望文法最好符合S文法。
预测分析法的工作过程：
从文法开始符号出发，在每一步推导过程中根据当前句型的最左非终结符A 和当前输入符号a ，选择正确的A-产生式。为保证分析的确定性，选出的候选式必须是唯一的。
S_文法（简单的确定性文法）
- 每个产生式的右部都以终结符开始
- 同一非终结符的各个候选式的首终结符都不相同（S_文法不含ε产生式）
说明：
- 根据上述的文法，当前的输入符号最多能选择一个候选式就不会产生冲突。
- S_文法简单来说就是同一非终结符的各个候选式的首终结符都不同，并且产生式不包含ε。
- 候选式的首终结符不同，保证了选出的候选式都是唯一的。
- 如果S_文法包含ε产生式，那么就保证不了选出的候选式是惟一的。例如a可以匹配以a开头的产生式的右部，也可以匹配右部为ε的产生式。
问题：若S_文法包含ε产生式会产生什么问题？
例.png
问：什么时候使用ε 产生式？
答：如果当前某非终结符A与当前输入符a不匹配时，若存在A→ε ，可以通过检查a是否可以出现在A的后面，来决定是否使用产生式A→ε（若文法中无A→ε，则应报错）。
说明: 以上输入ade例子说明空产生式不是什么情况都可以使用的。可见空产生式的使用取决于当前非终结符后面都紧跟哪些终结符。由此我们引入非终结符的后继符号集的概念。
非终结符的后继符号集
非终结符A的后继符号集
可能在某个句型中紧跟在A后边的终结符a的集合，记为FOLLOW(A)
FOLLOW(A)={a|S =>* αAaβ, a∈VT, α,β∈(VT ∪ VN)*}
例.png
说明：由于B的三个候选式是不相交的，因此可以做出唯一的选择。若当前输入符号为b时选用第二个产生式，若当前输入符号为c时选择第三个产生式，若当前输入为a或c时选择第四个产生式。为了叙述上的方便下面引入产生式的可选集这个概念。
产生式的可选集
产生式A→β的可选集是指可以选用该产生式进行推导时对
应的输入符号的集合，记为SELECT( A→β )
1. SELECT( A → aβ ) = { a }
2. SELECT( A → ε ) = FOLLOW( A )
说明：
1式表示只有遇到a终结符时才能选用产生式SELECT( A → aβ)
2式表示产生式的右部是空串的话只有遇到A的FOLLOW集的时候才能用产生式SELECT(A → ε)
对于具有相同左部的各个产生式，如果他们的SELECT集互不相交的话我们就可以做出确定的分析。因此我们给出q_文法的定义。
q_ 文法
- 每个产生式的右部为ε或以终结符开始。
- 具有相同左部的产生式有不可相交的可选集（q_文法不含右部以非终结符打头的产生式）。
ps: q_文法的第二点要注意跟 s_文法的 “同一非终结符的各个候选式的首终结符都不相同” 区分开。举例说明假设存在如下产生式
...
B → {b，c, d}
B → {b}
...
由于产生式的右部允许ε因此产生式对应的终结符集可能包含多个字符，显然B-产生式并不符合q_文法因为这两个具有相同的左部的产生式右部有相交的可选集b。也很显然q_文法的第二点也满足 s_文法的 “同一非终结符的各个候选式的首终结符都不相同” 这个限制。
说明： q_文法相对于S_文法功能更加强大因为它允许产生式的右部为空串ε，但是q_文法它对产生式的右部限制依然非常严格它不允许产生式的右部以非终结符打头，这限制了它的应用因此我们需要功能更加强大的文法就是接下来要介绍的LL(1)文法。而在LL(1)方法中允许产生式右部以非终结符打头，这就增加了可选集的复杂性，由此我们要引入串首终结符的概念。有此q_文法产生式对可选集的限制比s_文法更强。
串首终结符集
串首终结符：串首第一个符号并且是终结符，简称首终结符。
给定一个文法符号串α，α的串首终结符集FIRST(α)被定义为可以从α 推导出的所有串首终结符构成的集合。如果α =>* ε，那么ε 也在FIRST(α) 中。
对于 ∀α∈(VT∪VN)+, FIRST(α)={a | α =>* aβ，a∈VT，β∈(VT∪VN)*}
如果 α =>* ε ， 那么 ε ∈FIRST(α)
产生式A→α 的可选集SELECT
如果ε ∉ FIRST(α), 那么SELECT(A→α) = FIRST(α)
如果ε ∈ FIRST(α), 那么SELECT(A→α) = (FIRST(α)-{ε}) ∪ FOLLOW(A)
例子说明：
若α文法字符串为Ab，假设A-产生式不包含A->ε包含A->eD，A->fD；
那么α =>* eDb，α =>* fD；
那么SELECT(A) = FIRST(A) = {e, f}；
那么FIRST(α ) = {e, f}；
PS：串首终结符的出现是为了让LL(1)文法产生式的右部可以以非终结符打头。
LL(1)文法
文法G是LL(1)的，当且仅当G的任意两个具有相同左部的产生式A → α | β 满足下面的条件：
- 如果α和β均不能推导出ε，则FIRST(α) ∩ FIRST(β) = Φ
- α和β至多有一个能推导出ε
- 如果 β =>* ε ，则FIRST(α) ∩ FOLLOW(A) = Φ
如果 α =>* ε ，则FIRST(β) ∩ FOLLOW(A) = Φ
LL(1)含有：
- 第一个“L” 表示从左向右扫描输入
- 第二个“ L” 表示产生最左推导
- “1” 表示在每一步中只需要向前看一个输入符号来决定语法分析动作
概要
需要注意的是，并不是所有的语言都可以用LL(1)文法来描述，而且不存在判定某语言是否是LL(1)文法的算法。也就是说，确定的自顶向下分析只能实现一部分上下文无关语言的分析，这就是LL(1)文法所产生的语言。另外，在上述LL(1)文法的条件中，要求：ε ∈ FIRST(α1)，ε ∈ FIRST(α2)，…ε ∈ FIRST(αn) 中至多有一个成立。
