自顶向下分析概述
引言
在第一章绪论中曾介绍过语法分析的基本任务就是根据给定的文法，识别输入句子中的各类短语，并构造它的分析树
如果输入串的各个单词恰好自左至右的在分析树的各个叶结点上，那么这个子串就是该语言的一个句子，否则就不是。
按照分析树的构造方向，我们可以把语法分析分为两类。
- 第一类是从分析树顶部的根节点向底部的叶节点方向构造分析树，这种方法称为自顶向下的分析方法。
第二类是从分析树底部的叶节点向顶部的根节点方向构造分析树，这种方法称为自底向上的分析方法。
自顶向下分析
从分析树的顶部 (根节点) 向底部 (叶节点) 方向构造分析树
由于分析树的根节点对应文法的开始符号，分析树的叶节点对应输入串的各个单词，因此自顶向下分析可以看成是从文法开始符号 S 推导出词串 w 的过程。
【例】最左推导和最右推导
每一步推导中，都需要做两个选择
- 替换当前句型中的哪个非终结符
- 用该非终结符的哪个候选式进行替换
- 在最左 (右) 推导中，总是选择每个句型的最左 (右) 非终结符进行替换
- 在自底向上的分析中，总是采用最左归约的方式，因此把最左归约称为规范归约，而最右推导相应地称为规范推导
最左推导和最右推导具有唯一性
自顶向下的语法分析采用最左推导方式
- 总是选择每个句型的最左非终结符进行替换
- 替换时根据输入流中的下一个终结符，选择最左非终结符的一个候选式
递归下降分析
计算机如何实现自顶向下的语法分析：递归下降分析
- 递归下降分析 (Recursive-Descent Parsing)
- 由一组过程组成，每个过程对应一个非终结符
- 也就是说文法中有多少个非终结符，就有多少个过程
- 从文法开始符号 S 对应的过程开始，其中递归调用文法中其它非终结符对应的过程。如果 S 对应的过程体恰好扫描了整个输入串，则成功完成语法分析
- 由一组过程组成，每个过程对应一个非终结符
对应于非终结符 A 的过程：
| 1 2 3 4 5 6 7 8 9 10 11 | void A( ) { 选择一个A产生式：A → X1 X2 …… Xk; // 对产生式右部的每一个符号进行操作 for ( i = 1 to k ) { if (Xi是一个非终结符号) 递归调用过程Xi(); else if (Xi等于当前的输入符号a) // 匹配成功 读入下一个输入符号; else / 发生了一个错误 / ; } } |
|---|---|
Copy
在 A 的工作过程中，虽然我们是根据输入符号来选择产生式，但是我们仍然会遇到一些不确定的情况。
- 比如说：对于当前的输入符号 a，存在多个以终结符 a 打头的候选式时我们就不能确定选择哪一个。
- 解决方法：我们按照某一顺序逐个尝试，如果尝试失败，则退回上一步，然后看是否还有其他候选式。这个退回上一步再重新尝试的步骤就叫做回溯。
回溯会导致分析器的效率降低。需要回溯的分析器叫做不确定的分析器。
如果在分析的过程中，我们能预测出正确的产生式，那么就不需要回溯，这种分析叫做预测分析。
预测分析是递归下降分析技术的一个特例，通过在输入中向前看固定个数 (通常是一个) 符号来选择正确的 A - 产生式。
- 可以对某些文法构造出向前看 k 个输入符号的预测分析器，该类文法有时也称为 LL(k) 文法类
文法转换
事实上，并不是所有的文法都适合自顶向下的分析。但可以通过改造文法使其适合自顶向下的分析，这就叫做文法转换。
【问题 1】文法中的某个符号存在多个公共前缀导致回溯
提取左公因子
算法
消除左递归
消除直接左递归
消除间接左递归
算法
LL(1) 文法
递归下降分析可能会遇到回溯，回溯会影响分析器的效率。如果在分析的每一步我们都能预测到正确的选择的话，我们就不需要回溯。这样的分析叫做预测分析。下面介绍的 LL(1) 文法就可以使用预测分析技术。
S_文法
【例】
由文法中的 156 式可以看出，B 后面可以出现的终结符：c、a
非终结符的后继符号集
产生式的可选集
为了叙述上的方便，引入产生式的可选集 SELECT 这一概念
也就是说当输入符号在可选集中时，就可以使用该产生式进行推导
- 对于拥有相同左部的各个产生式，它们的 SELECT 集互不相交的话，我们就可以做出确定的分析。因此，我们给出 q_文法的定义。
-
串首终结符
q文法对产生式的右部限制依然非常严格，它不允许产生式的右部以非终结符打头，这限制了q文法的应用范围。因此我们引入功能更加强大的 LL(1) 文法。
在 LL(1) 文法中，允许产生式的右部以非终结符打头，这就增加了计算可选集 SELECT 的复杂性。由此，我们引入串首终结符集 FIRST 这一概念。
LL(1) 文法
LL(1) 文法 第一个 “L” 表示从左向右扫描输入
- 第二个 “L” 表示产生最左推导
“1” 表示在每一步中只需要向前看一个输入符号来决定语法分析动作
FIRST 集和 FOLLOW 集的计算
FIRST 集的计算
-
算法
串
FOLLOW 集的计算
要先求出 FIRST 集
E → TE’
- E 可以是某个句型的最右符号，所以将$加入 FOLLOW(E)；
- E’的 FIRST 集中所有终结符可以跟在 T 后面，所以将 FIRST(E’) 中的+加入 FOLLOW(T)；
- 由于 E’的 FIRST 集中存在空串，也就是说 E’可以是空串，那么 E 和 T 等价，能跟在 E 后面的终结符就能跟在 T 后面，所以将 FOLLOW(E) 中$符号加入 FOLLOW(T) 中；
- E’是产生式右边最后一个符号，也就是说能跟在 E 后面的终结符就能跟在 E‘后面，因此将 FOLLOW(E) 中$符号加入 FOLLOW(E’) 中；
- 此时 FOLLOW(E) = {$}，FOLLOW(T) = {+ $}，FOLLOW(E’) = {$}
- E’→ +TE’ | ε
- TE’所处位置与第一个产生式类似，所以分析结果与第一个产生式相同
- T → FT’
- T’的 FIRST 集中所有终结符可以跟在 F 后面，所以将 FIRST(T’) 中的*加入 FOLLOW(F)；
- 由于 T’的 FIRST 集中存在空串，也就是说 T’可以是空串，那么 T 和 F 等价，能跟在 T 后面的终结符就能跟在 F 后面，所以将 FOLLOW(T) 中+和$符号加入 FOLLOW(F) 中；
- T’是产生式右边最后一个符号，也就是说能跟在 T 后面的终结符就能跟在 T’后面，因此将 FOLLOW(T) 中+和$符号加入 FOLLOW(T’) 中；
- 此时 FOLLOW(E) = {$}，FOLLOW(T) = {+ $}，FOLLOW(E’) = {$}，FOLLOW(F) = {* + $}，FOLLOW(T’) = {+ $}
- T’→ *FT’ | ε
- FT’所处位置与第三个产生式类似，所以分析结果与第一个产生式相同
F → (E) | id
- E 后面跟着终结符)，所以将)加入 FOLLOW(E) 中
- 由于 FOLLOW(E’)、FOLLOW(T) 依赖于 FOLLOW(E)，所以将)加入 FOLLOW(E’)、FOLLOW(T) 中
- 由于 FOLLOW(T’)、FOLLOW(F) 依赖于 FOLLOW(T)，所以将)加入 FOLLOW(T’)、FOLLOW(F) 中
- 此时 FOLLOW(E) = {$ )}，FOLLOW(T) = {+ $ )}，FOLLOW(E’) = {$ )}，FOLLOW(F) = {* + $ )}，FOLLOW(T’) = {+ $ )}
算法
SELECT 集的计算
要先求出 FIRST 集和 FOLLOW 集
第一个产生式的开头是一个非终结符，所以它的 SELECT 集应该是产生式右部第一个非终结符 T 的 FIRST 集中的终结符
- 第二个产生式开头是+，所以第二个产生式的 SELECT 集就是终结符+
- 第三个产生式是一个空产生式，所以它的 SELECT 集就是 E’的 FOLLOW 中的终结符
- ……
- 第二个产生式和第三个产生式具有相同的左部，且它们的 SELECT 集互不相交；第五个产生式和第六个产生式具有相同的左部，且它们的 SELECT 集也互不相交；所以这个文法是一个 LL(1) 文法
对于 LL(1) 文法，可以根据产生式的 SELECT 集来构造文法的预测分析表，预测分析表的每一行对应一个非终结符，每一列对应一个输入符号。
预测分析法可分为
- 递归的预测分析法
-
递归的预测分析法
【例】递归的预测分析法
除了 47 的产生式是空串，其他的产生式都以终结符开头，所以除 47 外的其他产生式的 SELECT 集就是其开头的终结符
- 47 产生式是空串，所以它们的 SELECT 集就是 FOLLOW 集中的终结符
- 由产生式 12 可知产生式 4 的 FOLLOW 集中包含:
- 由产生式 15 可知产生式 7 的 FOLLOW 集中包含end
- procedure过程、recursive descent递归下降
- 文法中每一个非终结符都对应一个过程
非递归的预测分析法
- 预测分析器由一个输入带、一个读头和一个带有预测分析表的控制器构成，与第三章词法分析中介绍的有穷自动机不同的是，这个自动机增加了个栈，也叫下推存储器，它起到记忆的作用。因此这个自动机也叫下推自动机。
- 下推自动机比有穷自动机的预测功能更强，因为下推自动机的记忆功能更强。
例如：有一个语言，它的句子是由n个符号a连接同样个数n个符号b构成。
初始时，输入带上存放的是待分析的输入串，输入串结尾连接结束符号$。同时，将$也作为栈底的标记 (栈顶在左侧，栈底在右侧)。初始时，栈中只有唯一的符号，也就是文法的开始符号E。
- 栈顶是符号E，当前输入指针指向符号id，通过查预测分析表得知，需要选择产生式E→TE’，用TE’来替换E。因此栈顶元素E出栈，TE’进栈，并且输出产生式E→TE’。
- ……
- 输出的产生式序列就对应一个最左推导
递归与非递归的对比
| 递归的预测分析法 | 非递归的预测分析法 | |
|---|---|---|
| 程序规模 | 程序规模较大，不需载入分析表 | 主控程序规模较小，需载入分析表 (表较小) |
| 直观性 | 较好 | 较差 |
| 效率 | 较低 | 分析时间大约正比于待分析程序的长度 |
| 自动生成 | 较难 | 较易 |
- 由于递归的预测分析法需要为文法中的每一个非终结符编写一个递归下降过程。因此它的程序规模较大，但它不需要载入分析表。
- 由于递归的预测分析法是根据产生式的右部来编写程序，因此它的直观性比较好。
- 由于高深度的递归调用需要在递归子程序间进行连接，因此分析器的效率会降低。
由于递归的预测分析法需要根据产生式的右部来编写过程，因此比较难自动生成。而非递归地预测分析法采用自动机的方式，因此比较容易自动生成。
预测分析法的总结
总结预测分析法的实现步骤：
构造文法
- 改造文法：消除二义性、消除左递归、消除回溯
- 求每个变量的 FIRST 集和 FOLLOW 集，从而求得每个候选式的 SELECT 集
- 检查是不是 LL(1) 文法。若是，构造预测分析表
对于递归的预测分析，根据预测分析表为每一个非终结符编写一个过程；对于非递归的预测分析，实现表驱动的预测分析算法
预测分析中的错误检测
两种情况下可以检测到错误
栈顶的终结符和当前输入符号不匹配
- 栈顶非终结符与当前输入符号在预测分析表对应项中的信息为空
解决办法
- 恐慌模式
-
恐慌模式
恐慌模式：忽略输入中的一些符号，直到输入中出现合法的词法单元。事实上，设计者可以事先设定同步词法单元，一旦输入中出现同步词法单元，就可以立即进行同步。
忽略输入中的一些符号，直到输入中出现由设计者选定的同步词法单元 (synchronizing token) 集合中的某个词法单元
synch表示该终结符是对应非终结符的同步词法单元
- 分析表的使用方法
- M[A,a]中的A表示栈顶符号，a表示输入符号，M是预测分析表
【例】预测分析表工作过程
- M[E,+]为空，忽略+
- M[F,+]是synch，弹出F
若有收获，就点个赞吧
0 人点赞
