第四章-LL(1)

知识

自顶向下解析(自底向下语法分析)

• 解析树是从上到下（从根到叶）创建的。

• 通过始终通过产生式规则替换最左边的非终端符号，我们可以保证以从左到右的方式开发与扫描输入一致的解析树。

• 自顶向下解析器

• 递归下降解析(递归下降）

  • 需要回溯（如果生产规则的选择不起作用，我们回溯尝试其他替代方案。）

  • 它是一种通用的语法分析技术，但没有得到广泛应用。

  • 效率不高

• 预测分析(可预测）

  • 没有回溯

  • 有效率的

  • 需要一种特殊形式的语法（LL（1）语法）。

  • 递归预测分析是一种特殊形式的无回溯的递归下降分析。

  • 非递归（表驱动）预测解析器也称为LL（1）解析器。

递归下降解析（使用回溯）

• 自顶向下分析的一般范畴

• 根据输入符号选择产生式规则

• 可能需要回溯来纠正错误的选择。

自上而下解析的步骤

预测解析器

在派生步骤中重新写入非终结符时，预测解析器可以通过查看输入字符串中的当前符号来唯一地选择产生式规则。

实例

stmt → if expr then stmt else stmt
|while expr do stmt
|begin stmt_list end
|for .....

• 当我们试图写入非终端stmt时，如果当前单词是if，我们必须选择第一个产生式规则。

• 当我们试图编写非终端stmt时，我们可以通过查看当前标记来唯一地选择产生式规则。

• 我们消除了语法中的左递归，并将其左因子化。但它可能不适用于预测性语法分析（不是LL（1）语法）。

递归预测分析

每个非终端对应一个程序（功能）。

A → aBb (这只是A的生产规则)

proc A {
	- match the current token with a, and move to the next token;
	- call ‘B’;
	- match the current token with b, and move to the next token;
}

A → aBb | bAB

proc A {
	case of the current token {
		‘a’: - match the current token with a, and move to the next token;
		- call ‘B’;
		- match the current token with b, and move to the next token;
	‘b’: - match the current token with b, and move to the next token;
		- call ‘A’;
		- call ‘B’;
	} 
}

A → aA | bB | ε 何时应用ε-乘积

• 如果所有其他生产都失败，我们应该应用ε-生产。例如，如果当前标记不是a或b，我们可以应用ε-乘积。

• 最正确的选择：当当前标记位于a的follow集合中时，我们应该对非末端a应用ε-产生式（哪些末端可以在句子形式中跟随a）。

实例

A → aBe | cBd | C
B → bB | ε
C → f

非递归预测解析——LL（1）解析器

• 非递归预测解析是一种表驱动的解析器，它有一个输入缓冲区、一个堆栈、一个解析表和一个输出流。

• 它也被称为LL（1）解析器。

1. 从左到右扫描输入

2. 找到最左边的派生词

LL（1）解析器

输入缓冲区

• 要分析的字符串。我们将假设它的结尾用一个特殊的符号$标记。

输出

• 表示输入缓冲区中字符串的派生序列（最左边的派生）的一个步骤的产生式规则。

堆栈 ← 语义行为

• 包含语法符号

• 在堆栈底部，有一个特殊的结束标记符号$。

• 最初，堆栈仅包含符号$和起始符号S。

  • $S ← 初始堆栈

• 当堆栈清空时（即堆栈中只剩下$），解析就完成了。

解析表

• 二维数组M[a，a]

• 每行都是一个非终端符号

• 每列都是终端符号或特殊符号$

• 每个条目都包含一条生产规则。

非递归/表驱动

一般解析器行为：X:堆栈顶部 a:当前输入

1. 当X=a=$halt，accept，success时

2. 当X=a时≠ $ , 从堆栈中弹出X，提前输入，转到1。

3. 当X为非终端时，检查M[X，a]

   • 如果是错误→ 呼叫恢复程序

   • 如果M[X，a]={X→ UVW}，POP X，PUSH W，V，U 注意推送顺序

   • 不要花费任何投入

一种非递归预测解析器模型

非递归解析算法

LL（1）解析器——示例1

S → aBa
B → bB | ε

“abba”一句是否正确

LL（1）解析表

产出

s → aBa 
B → bB 
B → bB 
B → ε

派生（最左边）

S → aBa → abBa → abbBa → abba

解析树

LL（1）解析器–示例2

E → TE’ 
E’ → + TE’ | ∈
T → FT’ 
T’ → * FT’ | ∈
F → ( E ) | id

如何构造id+id*id？

语法分析表M

预测分析器对输入id+id*id进行的移动

示例中最左边的派生

该示例最左边的推导如下：

E 
→ TE’ 
→ FT’E’ 
→ id T’E’
→ id E’
→ id + TE’
→ id + FT’E’
→ id + id T’E’
→ id + id * FT’E’ 
→ id + id * id T’E’ 
→ id + id * id E’ 
→ id + id * id

构造LL（1）解析表

构造解析表M！

第一：首先计算语法，然后再计算语法

第二：应用构造算法解析表

（我们很快就会看到）

基本功能：

FIRST：让α是一组语法符号。FIRST（α）是一个集合，它包括在α中或从α开始的任何字符串中显示最左边的每个端子。

注：如果α→ ∈, 然后∈ 是FIRST（α）。

FOLLOW：让A成为非终端。FOLLOW（A）是以某种句子形式直接出现在A右边的一组终端A。（S→ αAaβ，对于某些α和β）。

注：如果→ αA，那么$是FOLLOW（A）

计算任意字符串X的FIRST

计算FIRST（X）：所有语法符号

FIRST实例

E → TE’
E’ → +TE’ | ε
T → FT’
T’ → *FT’ | ε
F → (E) | id

FIRST(F) = {(,id}
FIRST(T’) = {*, ε}
FIRST(T) = {(,id}
FIRST(E’) = {+, ε}
FIRST(E) = {(,id}

FIRST(TE’) = {(,id}
FIRST(+TE’) = {+}
FIRST(ε) = {ε}
FIRST(FT’) = {(,id}
FIRST(*FT’) = {ε}
FIRST(ε) = {ε}
FIRST((E)) = {(}
FIRST(id) = {id}

另一种计算FIRST的方法

计算FOLLOW（对于非终端）

1. 如果S是开始符号➔ $ 位于FOLLOW（s）

最初是$S

2. 如果→ αBβ是产生式规则➔ 除ε外，第一个（β）中的一切都在（B）之后

3. 如果（A）→ αB是产生式规则）或（a→ αBβ是产生式规则，ε位于第一位（β））➔ FOLLOW（A）中的所有内容都在FOLLOW（B）中。

（无论A后面跟什么，都必须跟在B后面，因为根据产生式规则，B后面没有任何东西）

我们应用这些规则，直到不能再向任何后续集合添加任何内容。

FOLLOW伪码算法

FOLLOW实例

E → TE’ 
E’ → +TE’ | ε
T → FT’ 
T’ → *FT’ | ε
F → (E) | id

FIRST(F) = {(,id}  FOLLOW(F) = {*, +, ), $ }
FIRST(T’) = {*, ε} FOLLOW(T’) = { +, ), $ }
FIRST(T) = {(,id}  FOLLOW(T) = { +, ), $ }
FIRST(E’) = {+, ε} FOLLOW(E’) = { ), $ }
FIRST(E) = {(,id}  FOLLOW(E) = { ), $ }

FIRST和FOLLOW背后的动机

• FIRST：用于在给定堆栈顶部非端子和当前输入符号的情况下，帮助找到要遵循的适当缩减。
• FOLLOW：当FIRST发生冲突、解决选择或FIRST没有给出建议时使用。什么时候α → ∈ 或α → ∈, 然后，A后面的内容决定了下一个选择。

练习

• 考虑到以下语法：

s→aAb | Sc |ε

A→aAb |ε

• 请为每个非终端计算FIRST（）和FOLLOW（）。

Soution

FIRST(S)={a, c, ε} FOLLOW(S)={$}
FIRST(S’)={c, ε}   FOLLOW(S’)={$}
FIRST(A)={a, ε}    FOLLOW(A)={b}

构造LL（1）解析表

算法4.4：

1. 对每个规则A重复步骤2和3A→α

2. 第一个（α）中的端子a？添加一个A→α到M[A，A]

• ∈ 在FIRST（α）？添加一个A →α FOLLOW（A）中所有端子b的α至M[A，b]。

• ∈ 在FIRST（α）和FOLLOW（A）中？添加一个A →α到M[A，$]

4. 所有未定义的条目都是错误。

例子

语法分析表M

LL（1）语法

• 解析表中没有多重定义项的语法称为LL（1）语法。
• 语法的解析表可能包含多个产生式规则（即多定义项）。在这种情况下，我们说它不是LL（1）语法，比如左递归或歧义。

L：从左到右扫描输入

L：构造最左边的派生

1：使用“1”输入符号作为前瞻，与堆栈一起决定解析操作

LL（1）语法==它们在解析表中没有定义的乘法项。

LL（1）文法的性质：

• 语法不能模棱两可或重复使用

• 语法是LL（1）↔ 当A → α|β

  1. α和β不能派生以相同端子a开头的字符串

  2. α或β都可以派生∈, 但不是两者都有。

  注意：语法可能不可能被转换成LL（1）语法

LL（1）文法的性质

语法G是LL（1）当且仅当以下条件适用于两个不同的产生式规则A→ α和A→ β

1. α和β都不能派生以相同端子开头的字符串。

2. α和β中最多有一个可以导出ε。

3. 如果β可以导出ε，那么α就不能导出任何以后面（a）中的一个终端开始的字符串。

课堂练习

语法：

lexp → atom | list
atom →num | id
list → (lexp_seq)
lexp_seq → lexp_seq lexp | lexp

请先计算FIRST（）和FOLLOW（），然后构造解析表，查看语法是否为LL（1）。

消除左递归

lexp → atom | list
atom → numr | id
list → ( lexp-seq )
lexp-seq → lexp lexp-seq’
lexp-seq’ → lexp lexp-seq’ | ε

计算FIRST（）和FOLLOW（）

FIRST(lexp)={ (, num, id }
FIRST(atom)={ num, id }
FIRST(list)={ ( }
FIRST(lexp-seq)={ (, num, id }
FIRST(lexpseq’)={ (,num,id,ε}

FOLLOW(lexp-seq’)={)}

构造解析表

1 lexp → atom 5 list → ( lexp_seq )
2 lexp → list 6 lexp_seq → lexp lexp_seq’
3 atom →num   7 lexp_seq’ → lexp lexp_seq’ 
4 atom →id    8 lexp_seq’ → ε

因为表项没有冲突 ，所以该文法是LL(1)文法。

不是LL（1）的语法

• 左递归语法不能是LL（1）语法。

  • A → Aα|β

    • 出现在FIRST（β）中的任何终端也会出现在FIRST（Aα）中，因为Aα→ βα.

    • 如果β是ε，则出现在FIRST（α）中的任何端子也出现在FIRST（Aα）和后面的FOLLOW（A）中。

• 语法不是左因素，它不可能是LL（1）语法

  • A → αβ${}_1\_1$ | αβ${}_1\_1$

    • 出现在FIRST（αβ${}_1\_1$）中的任何终端也出现在第一个（αβ${}_2\_2$）中。

• 歧义语法不能是LL（1）语法。

• 如果生成的解析表包含多个定义的条目，我们必须做什么？

  • 如果我们不消除左递归，就消除语法中的左递归。

  • 如果语法不是左因子，我们必须左因子语法。

  • 如果其（新语法）解析表仍然包含多个定义的条目，则该语法是不明确的，或者它本质上不是LL（1）语法。

例子

Example:
S → i C t S E | a
E → e S | ε
C → b

FIRST(iCtSE) = {i}
FIRST(a) = {a}
FIRST(eS) = {e}
FIRST(ε) = {ε}
FIRST(b) = {b}

FOLLOW(S) = { $,e }
FOLLOW(E) = { $,e }
FOLLOW(C) = { t }

预测分析中的错误恢复

• 预测分析（LL（1）分析）中可能会发生错误

  • 如果堆栈顶部的端子符号与当前输入符号不匹配。

  • 如果堆栈顶部是非终端a，则当前输入符号是a，解析表条目M[a，a]为空。

• 在错误情况下，解析器应该做什么？

  • 解析器应该能够给出错误消息（尽可能多的有意义的错误消息）。

  • 它应该可以从错误案例中恢复，并且应该能够继续解析其余的输入。

LL（1）解析错误恢复技术中的紧急模式错误恢复

• 紧急模式错误恢复

  • 跳过输入符号，直到找到同步令牌。

• 短语级错误恢复

  • 解析表中的每个空条目都填充了一个指向特定错误例程的指针，以处理该错误情况。

• 错误产品（用于GCC等）

  • 如果我们对可能遇到的常见错误有一个很好的了解，我们可以用生成错误结构的结果来扩充语法。

  • 当解析器使用错误生成时，我们可以生成适当的错误诊断。

  • 由于几乎不可能知道程序员可能犯的所有错误，这种方法不实用。

• 全局校正

  • 理想情况下，我们希望编译器在处理不正确的输入时做出尽可能少的更改。

  • 我们必须对输入进行全局分析，以找出错误。

  • 这是一种昂贵的方法，实际上并不可行。

LL（1）解析中的紧急模式错误恢复

• 在紧急模式错误恢复中，我们跳过所有输入符号，直到找到同步单词。
• 同步单词是什么？
  • 非终端的follow集合中的所有终端符号都可以用作该非终端的同步单词集。
• 因此，为LL（1）解析提供一个简单的紧急模式错误恢复：
  • 所有空条目都标记为synch，以指示解析器将跳过所有输入符号，直到堆栈顶部的非端子a的follow集合中出现一个符号。然后解析器将从堆栈中弹出非终端A。解析将从该状态继续。
  • 为了处理不匹配的终端符号，解析器从堆栈中弹出该不匹配的终端符号，并发出一条错误消息，说明插入了该不匹配的终端。

紧急模式错误恢复-示例

短语级错误恢复

• 解析表中的每个空条目都被一个指向特殊错误例程的指针填充，该例程将处理该错误情况。

• 这些错误例程可能：

  • 更改、插入或删除输入符号。

  • 发出相应的错误消息

  • 从堆栈中弹出项目。

• 在设计这些错误例程时，我们应该小心，因为我们可能会将解析器放入无限循环中。

最终评论–自上而下解析

目前为止

• 我们研究了语法和语言理论及其与句法分析的关系
• 关键概念：将语法改写成可接受的形式

检查了自上而下的解析：

• 蛮力：转换图和递归
• 优雅：桌面驱动

我们发现了它的缺点：

• 并不是所有的语法都能成为LL（1）！
• 自下而上解析——未来

小结

• 理解递归下降的语法分析方法
• 理解递归可预测的语法分析方法
• 掌握非递归可预测的语法分析方法，即LL(1)语法分析法
• 掌握计算FIRST 和FOLLOW的算法
• 掌握LL(1)语法分析表的构造

练习

4.2设已给文法：

S→AbB|d

A→CAb|Bf

B→CSd|d

C→ed|a

试写出对符号串eddfbbd进行带回溯的自顶向下语法分析的过程。（提示：不需要消除左递归）

Solution

4.3对于如下的文法，求出各个FIRST集和FOLLOW集。

S→aAB|bA |ε

A→aAb |ε

B→bB|ε

Solution

4.4试证明： 任何具有左递归性的前后文无关文法均非LL(1)文法。

Solution

∵文法具有左递归性

∴一定存在左递归性的非终结符A，以及形如A→α|β的产生式，而且α T* Ad

∴first(Ad) ∩ first(β) ≠ Ø

∴first(α) ∩ first(β) ≠ Ø

∴文法不满足LL(1)问法条件

∴得证

4.5试证明： 任何LL(1)文法均为无二义性文法。

Solution

∵LL(1)文法的分析句子过程的每一步，永远只有唯一的分析动作可进行

假设LL(1)文法G是二义性文法

∴存在句子α，它有两个不同的语法树

∴存在句子α，它有两个不同的最左推导

∴用LL(1)方法进行句子α的分析过程中的某步中，存在两种不同的产生式替换，且均能正确进行语法分析

∴LL(1)分析动作存在不确定性

∴与LL(1)性质矛盾

∴G不是LL(1)文法

4.6验证下列文法是否为LL(1)文法。

(1)S→AB|CDa

A→ab|c

B→dE

C→eC|ε

D→fD|f

E→dE|ε

Solution

∵D产生式两个候选式fd和f的first集交集不为空

∴不是LL(1)

(2) S→aABbCD|ε

A→ASd|ε

B→Sac|eC|ε

C→Sf|Cg|ε

D→aBD|ε

Solution

∵此文法具有左递归性

根据4.4结论

∴不是LL(1)