自顶向下

递归下降分析

由一组过程组成，每个过程对应一个非终结符。
缺点：需要回溯，效率低。

预测语法分析

  1. 含义：通过在输入中向前看 k 个符号来选择正确的产生式，以此避免回溯。

对于大多数编程语言来说，k = 1 足够了。

  1. 预测语法分析的关键是构造语法分析表。

文法修正

消除二义性

通过引入新的非终结符消除。

消除左递归

  1. 消除直接左递归：

image.png

  1. 消除间接左递归：代入法得到直接左递归，按照上述消除直接左递归的方法。

提取左公因子

image.png

构造语法分析表

构建分析表的两大函数：FIRST、FOLLOW、SELECT

FIRST

FIRST(A)：表示由 A 推导能推出的所有文法符号串的首终结符的集合，若 A 能推出 ε，那么 ε 也在 FIRST(A) 中。
例如：语法分析 - 图3
则 FIRST(S) = {a, b, c}，即由 S 能够推出的所有文法符号串为：abc, bc, c，它们的首终结符集合为 {a, b, c}。
计算方法：对于产生式：语法分析 - 图4计算 FIRST(A)

  1. 首先 FIRST(A) = FIRST(X1) - {ε}
  2. 若 X1 能够推出 ε，则再把 FIRST(X2) - {ε} 加入 FIRST(A)
  3. 若 X2 能够推出 ε，则再把 FIRST(X3) - {ε} 加入 FIRST(A)
  4. 依次类推，若直至 Xn 也能推出 ε，则把 ε 加入 FIRST(A)

FOLLOW

FOLLOW(A)：可能在某个句型中紧跟在非终结符 A 后边的终结符 a 的集合。
什么时候使用空产生式 语法分析 - 图5 取决于非终结符 A 后面可以紧跟哪些终结符，即要计算 FOLLOW(A)。
计算方法：
image.png
注意对于最右符号要加入终结符 $

SELECT

产生式 A→β 的可选集是指可以选用该产生式进行推导时对应的输入符号的集合，记为 SELECT( A→β )
例如：SELECT(A→aβ) = {a} 的意思是只有当遇到输入符号为 a 时才可以选择产生式 A→aβ
计算方法：对于 SELECT(A→β)

  • 若 β 不能推出 ε，则 SELECT(A→β) = FIRST(β)
  • 若 β 能够推出 ε，则 SELECT(A→β) = (FIRST(β) - {ε})∪FOLLOW(A)

利用 SELECT 集合构造语法分析表
image.png
SELECT(E -> TE’) = { (, id } ，表示当非终结符 E 遇到终结符 ( 或 id 时可以采用 E -> TE’ 产生式。

LL(1) 文法

image.png
image.png
因为 LL(1) 文法的目的就是通过计算 SELECT 集合构造语法分析表，因此对相同左部的产生式来说，它们的 SELECT 集合不能相交，否则计算机不知道选择哪个产生式。
例如 SELECT(A→α) = SELECT(A→β) = {a, b}，计算机在对于输入符号 a 时将无法确定选用哪个产生式。

实现方法

递归法

image.png
在原始的递归下降分析法中把文法修正为 LL(1) 文法，加入了语法分析表避免回溯。

非递归法

image.png
正则表达式（有穷自动机）具有局限性，无法描述上下文无关文法 CFG，因此利用一个栈把它升级为下推自动机。例如正则表达式无法描述具有对称性的、平衡性的语言，如图中 L 表示的语言要求 a 的个数和 b 的个数相同，因为有穷自动机没有存储器，无法记住遇到了多少个 a，因此不能识别 L 语言。

分析过程很简单，简单一句话“查表推导”

错误处理

错误检测

  1. 栈顶是终结符，与当前输入符号不匹配。
  2. 栈顶是非终结符，但是根据当前输入符号去查表，对应的表项为空。

恐慌恢复

image.png
重点：

  1. 可以利用非终结符的 FOLLOW 集合作为同步词法单元集合。

image.png
重点：

  1. 分析表的 3 点使用方法。

image.png

自底向上

方法：最左规约，逆向得出最右推导。
分析框架：移入-归约分析。
移入规约的关键问题：识别句柄。根据功能是否强大，实现是否复杂分为 4 类 LR(0) 分析、SLR 分析、LR(1) 分析和 LALR 分析，功能逐渐增强，实现逐渐复杂。

句柄定义

短语、直接短语、句柄
从语法分析树的角度来说：
短语：每一个以非终结符为根的子树的叶节点从左到右排列得到的符号串。
直接短语：只有父子关系的子树的叶节点从左到右排列得到的符号串。
句柄：也称最左直接短语，最左边的父子关系子树的叶节点从左到右排列得到的符号串。

识别句柄

可行前缀（活前缀）

移动-归约分析正确时，栈中的内容即活前缀。
LR(0) 自动机可以识别所有可行前缀，因此画出 LR(0) 自动机即可。

LR(0) 分析

识别方法：有穷自动机，LR(0) 自动机。
项目：标有圆点的产生式。
项目集闭包：等价项目的集合，对应自动机的一个状态。
增广文法：在原文法中引入一个新的开始符号 S’ 和产生式 S’ -> S，目的是使文法开始符号仅出现在一个产生式的左边，从而使分析器只有一个接收状态。
规范 LR(0) 项集族：C = 项目集闭包的集合。
LR(0) 分析表构造方法：CLOSURE 函数和 GOTO 函数。CLOSURE 函数的作用是求一个项目的项目集闭包，GOTO 函数是求一个项目的后继项目的的项目集闭包。
LR(0) 分析冲突：移入-归约冲突、归约-归约冲突。
LR(0) 文法：文法对应的 LR(0) 分析表中没有语法分析动作冲突，因此不是所有 CFG 文法都是 LR(0) 文法。

SLR 分析

LR(0) 分析存在冲突的原因是未能正确识别句柄，而 SLR 分析利用 FOLLOW 集合来判断采用何种分析动作。image.png
SLR 分析冲突：仍然存在移入-归约冲突，要移入的符号恰好在相应产生式的 FOLLOW 集中。

LR(1) 分析

SLR 只借助产生式的 FOLLOW 集合来判断采用何种分析动作，而在特定位置时，某个产生式的后继符只是 FOLLOW 集的一个子集。
LR(1) 项目：引入一个展望符。
image.png
等价项目的展望符：
image.png
同心项目集：除展望符不同之外，其他都相同的两个 LR(1) 项目集。
LR(1) 分析根据展望符的不同把 LR(0) 项目分裂，产生更多状态。

LALR 分析

合并同心项目集：

  1. 在 LR(1) 分析的基础上，把没有语法分析动作冲突的同心项目集进行合并。
  2. 合并过程中可能出现归约-归约冲突，但不会产生移入-归约冲突，因为合并的本质是合并展望符，展望符在移入动作时是无效的。
  3. 合并同心项目集可能会导致推迟错误的发现，但不会忽略错误。

特点：

  1. 形式上与 LR(1) 相同；
  2. 大小上与 LR(0) 相当；
  3. 分析能力 SLR ≤ LALR(1) ≤ LR(1)；
  4. 合并后的展望符集合仍然是 FOLLOW 集的子集。

LR 分析的错误处理

恐慌模式错误恢复

丢弃若干输入符号。

短语层次错误恢复

为 LR 分析表中每个报错条目构造根据程序员可能犯下的错误一个恢复过程。

二义性文法的 LR 分析

image.png
image.png