04 语法分析 | 《编译原理》笔记

本系列是编译原理 (哈工大陈鄞、郭勇)视频课的课堂笔记，主要是课堂 PPT 和部分讲授内容的文字版，仅供参考。

自顶向下分析概述

对于每一棵分析树，其最左推导和最右推导都是唯一的，因为在推导的每一步，当前句型的最左非终结符和最右非终结符都是唯一的。

自顶向下的语法分析采用最左推导方式：

• 总是选择每个句型的最左非终结符进行替换
• 根据输入流中的下一个终结符，选择最左非终结符的一个候选式

需要回溯的分析器叫做不确定的分析器。如果能在分析的过程中预测出正确的产生式，就不需要回溯，即预测分析。

文法转换

不是所有文法都适合自顶向下分析，本节将说明自顶向下分析会有什么问题，然后介绍如何改造使其适合自顶向下分析。

LL(1) 文法

回溯会影响分析器的效率，如果在分析的每一步都可以预测出正确的选择便可以提高效率，这就是预测分析。LL 分析器是一种自顶向下的上下文无关语法分析器。因为它从左到右处理输入，对句型进行最左推导构建出语法树。能以此方法分析的文法称为 LL 文法。一个 LL 分析器若被称为 LL(k) 分析器，表示它使用 k 个词法单元作向前探查。对于某个文法，若存在一个分析器可以在不用回溯法进行回溯的情况下处理该文法，则称该文法为 LL(k) 文法。

LL(1) 文法的分析方法主要包括递归的预测分析法和非递归的预测分析法。

FIRST 集和 FOLLOW 集的计算

• 如果产生式的右部是以一个终结符开头，这个终结符就是串首终结符（如产生式2、4、5）
• 如果非终结符可以推导出空串，那么空串也是串首终结符（如产生式 2、4）
• 如果产生式的右部以非终结符开头，那么产生式右部开头的非终结符的 FIRST 集就是产生式左部非终结符 FIRST 集的子集（如产生式 1、3）

产生式右部第一个非终结符的 FIRST 集中的终结符。

判断一个文法是不是 LL(1) 文法，就要看相同左部的产生式的 SELECT 集是否不相交。

根据 SELECT 集可以得到预测分析表。预测分析表中的每一行对应一个非终结符，每一列对应一个输入符号：

预测分析法

自底向上分析概述

在任何时刻，栈内符号串 + 剩余输入 = 规范句型。

分析失败。

直接短语是产生式的右部，但是产生式的右部不一定是直接短语，直接短语是分析树中某个高度为 2 的子树的边缘。

在这个例子中，iB 虽然是某个产生式的右部，但是在分析树种它不是某个高度为 2 的子树的边缘，因此 iB 不是直接短语。

事实上，当前这个句型（上图中使用红线标出的那一行）有两个直接短语，在下图中分别使用红色和蓝色标出：

所以最左直接短语就是红色的那个。

LR 分析法概述

LR(0) 分析

LR(0)分析表构造算法

SLR 分析

LR(1)分析

LALR 分析法

二义性文法的 LR 分析

LR 分析中的错误处理

LL 分析与 LR 分析

选择 LR 分析法还是 LL 分析法取决于文法的复杂性和实际应用需求。LR 分析法在处理较复杂的文法和语言时通常更有优势，而 LL 分析法则在简单的文法和自顶向下分析时更容易实现。

在现代编译器中，通常会使用 LR 分析法，尤其是 LR(1)、LALR(1) 等强大的 LR 分析器，因为它们具有更强大的分析能力，能够处理复杂的上下文无关文法。LR 分析法的特点是自底向上分析，可以处理更广泛的文法，包括一些对 LL 分析法来说较为困难的情况，例如处理左递归和处理移进-规约冲突等。

另外，LR 分析法的产生式规约决策通常基于后看符号，这使得它可以更好地处理语法上下文的推断，这在编程语言编译器中是非常重要的。因此，LR 分析法在实际编译器中更为常见。