编译原理 笔记 1

自顶向下语法分析

自顶向下的核心思想是从文法的开始符号出发，每一步推导得到一个句型，最终产生一个句子即为期待的终结符串

带回溯的自顶向下分析

由于每一步推导的终结符串和使用的文法都是不确定的，因此复杂度很高，只能进行不断回溯，因此我们进行改进：每步推导总是用最左边的非终结符，产生最左推导，如果想进一步确认使用的文法，则需改进为：

确定的自顶向下分析

在从左向右扫描的过程中，向前查看常数个的单词，以确定每一步使用的文法

例如对于文法 $G$：

$$\begin{align*} S &\to AB \\ A &\to aA | \varepsilon \\ B &\to b | bB \end{align*}$$

则在自顶向下分析 $a^{n}b^{m}(n\geq 0, m > 0)$ 时，只需要向前查看2个单词，即可预测每步所应该使用的文法

如果想要实现这种分析，需要保证文法不含左递归与左公因子，否则：

考虑文法 $G$：

$$\begin{align*} S &\to Sa | b \end{align*}$$

则在分析 $ba^{n}$ 时需要向前看的单词数为 $n + 2$ 个

考虑文法 $G$：

$$\begin{align*} S &\to aAb | aAc \\ A &\to a | aA \end{align*}$$

则在分析 $a^{n}(b + c)$ 时需要向前看的单词数为 $n + 2$ 个

都不为常数，无法确定地分析

LL(1) 分析

最常用的预测分析方法，要求文法是LL(1)文法

• 从左向右扫描单词
• 每步产生最左推导
• 向前看一个单词

重要的集合

First集合

First集合定义为：

即任意句型或句子的 First 是指这个句型或句子能推导出的串中首个单词的集合

$\mathrm{First}(\alpha)$ 计算过程为：

• 先置所有 $\mathrm{First}(\alpha) = \varnothing$
• 若 $\alpha \in V_{T}\cup \{\varepsilon\}$，则$\mathrm{First}(\alpha) = \{\alpha\}$
• 若 $\alpha = X_{1}X_{2}\dots X_{k} \in (V_{T} \cup V_{N})^{*}$，则先置 $\mathrm{First}(\alpha) = \mathrm{First}(X_{1})$
  遍历 $X_{i}$，若$X_{1}\dots X_{i} \Rightarrow^{*} \varepsilon$
  则 $\mathrm{First}(\alpha) \cup= \mathrm{First}(X_{i + 1})$，其中 $X_{k + 1} = \varepsilon$
• 若 $\alpha \in V_{N}$，且$\alpha \to X_{1}X_{2}\dots X_{k}$，
  则 $\mathrm{First}(\alpha) \cup= \mathrm{First}(X_{1}X_{2}\dots X_{k})$

Follow集合

Follow集合定义为：

也即 Follow 集合被定义为可能在某些句型中紧跟在 $A$ 右边的终结符集合

$\mathrm{Follow}(A)$ 的计算方法为：

• 置 $\mathrm{Follow}(S) = \{\#\}$，其他均为 $\varnothing$
• 循环直到所有集合不变：
  • 对于 $A\to \alpha B \beta$，$\mathrm{Follow}(B) \cup= \mathrm{First}(\beta) - \{\varepsilon\}$
  • 若 $\varepsilon \in \mathrm{First}(\beta)$，则 $\mathrm{Follow}(B) \cup= \mathrm{Follow}(A)$

预测集合

预测集合的定义为：

预测集合给出了读入了什么字符的时候需要采用产生式$A\to \alpha$

LL(1)文法

递归下降LL(1)分析程序

每个非终结符对应一个子程序，每个子程序的行为根据语法描述来明确：

• 根据当前非终结符的PS集合与下一个输入符号选择产生式
• 如果产生式右端遇到非终结符，则调用相应的子程序
• 如果产生式右端遇到终结符，判断当前读入的单词是否与该终结符相匹配，匹配则继续读取，反之报错

递归下降分析

实际应用中，可以将产生式的右端添加新运算，使之更加简洁，例如将 $S\to XS\quad S \to \varepsilon$ 替换为 $S\to \{X\}$ 等，具体来说：

• $\{X\} = X^{*}$
• $[X] = X \,|\, \varepsilon$
• $(X)$ 代表 $X$ 优先

表驱动LL(1)分析程序

由PS集合形成一个预测分析表，即根据非终结符和下一个单词决定产生式的表，并利用该表和一个下推栈实现：

• 将 $\#$ 和 $S$ 依次入栈
• 若栈顶为终结符，则判断读入的单词和终结符是否匹配，匹配则出栈并继续读取，反之报错
• 若栈顶为非终结符，则查表找到产生式，若为 None 则报错，反之非终结符出栈，产生式右端从右至左依次入栈，无需继续读入
• 直到栈顶和下一位输入都是 $\#$

可以证明，预测分析表的每一项都只包含一个产生式，当且仅当文法是 LL(1) 的

文法变换

主要包含消除左递归与提取左公因子两种，通常用于将一些文法转换成 LL(1) 文法

消除左递归

消除直接左递归

对 $P \to P\alpha\,|\,\beta$，$\alpha\neq\varepsilon$ 且 $\beta$ 首字符不是 $P$，则消除方法为引入新终结符 $Q$ 使得：

$$\begin{align*} P &\to \beta Q \\ Q &\to \alpha Q \,|\, \varepsilon \end{align*}$$

对于一般形式 $P \to P\alpha_{1}\,|\,\dots\,|\,P\alpha_{m}\,|\,\beta_{1}\,|\,\dots\,|\,\beta_{n}$，则：

$$\begin{align*} P &\to \beta_{1}Q\,|\,\dots\,|\, \beta_{m}Q \\ Q &\to \alpha_{1}Q \,|\,\dots\,|\,\alpha_{n}Q\,|\, \varepsilon \end{align*}$$

消除一般左递归

对于无环无 $\varepsilon$ 产生式的文法，消除一般左递归的方法为：

• 排列非终结符$A_{1}, A_{2}, \dots, A_{n}$
• for i in 1..n:
  • for j in 1..(i-1):
    • 对于形如 $A_{i} \to A_{j}r$ 的规则
    • 其中 $A_{j}$ 的全部产生式为 $A_{j} \to \alpha_{1}\,|\,\alpha_{2}\,|\,\dots\,|\,\alpha_{k}$
    • 将 $A_{i}$ 产生式替换为 $A_{i} \to \alpha_{1}r\,|\,\alpha_{2}r\,|\,\dots\,|\,\alpha_{k}r$
  • 再消除 $A_{i}$ 的直接左递归
• 化简文法

提取左公因子

对于形如 $P\to \alpha\beta \,|\, \alpha\gamma$ 的产生式，增加新非终结符 $Q$ 使得：

$$\begin{align*} P &\to \alpha Q \\ Q &\to \beta \,|\, \gamma \end{align*}$$

一般化为 $P\to \alpha\beta_{1}\,|\,\dots\,|\,\alpha\beta_{m}\,|\,\gamma_{1}\,|\,\dots\,|\,\gamma_{n}$：

$$\begin{align*} P &\to \alpha Q\,|\,\gamma_{1}\,|\,\dots\,|\,\gamma_{m} \\ Q &\to \beta_{1} \,|\,\dots\,|\, \beta_{n} \end{align*}$$

预测分析中的出错处理

处理原则：

• 尽可能准确地给出错误位置与属性
• 尽可能校正

表驱动LL(1)分析中的错误处理

对于栈顶终结符与输入不匹配，直接弹出终结符
对于栈顶非终结符与输入符号在表中找不到产生式，我们采用恐慌模式，即跳过一些符号以找到同步符号

同步符号集合的构建为：

• $\mathrm{Follow}(A)$中的所有符号都是$A$的同步符号
• 将$\mathrm{First}(B)$中的符号加入$A$同步符号，代表$A$遇到错误的时候可以从$B$开始继续分析

递归下降分析的错误处理

当递归进入某个语法单位的时候，检查当前符号是否属于该单位的开始符号，离开该语法单位的时候检查符号是否属于该单位的结束符号

若不属于则不断滤去直到到达补救集合（即开始符号与结束符号的并集）中的符号并重新判断

递归下降分析错误处理

LL(k)的结论

LL(k) 文法的定义是 LL(1) 的推广，有关的结论有：

• 给定 $k>0$，一个 CFG是否为 LL(k) 是可判定的
• 给定CFG，是否存在 $k$ 使得该文法是 LL(k) 是不可判定的
• 给定CFG，是否存在与之等价的 LL(k) 是不可判定的
• 两个 LL(k) 是否相等是可判定的
• LL(k) 无二义
• LL(k) 中不存在左递归
• 给定 $k>0$，不含 $\varepsilon$ 产生式的 LL(k) 的集合真包含于不含 $\varepsilon$ 产生式的 LL(k+1) 的集合