编译原理 笔记 1

自顶向下语法分析

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

带回溯的自顶向下分析

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

确定的自顶向下分析

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

例如对于文法$G$：

$$\begin{align*} S &\to AB \\ A &\to aA | \epsilon \\ 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 \{\epsilon\}$，则$\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^{*} \epsilon$
  则$\mathrm{First}(\alpha) \cup= \mathrm{First}(X_{i + 1})$，其中$X_{k + 1} = \epsilon$
• 若$\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) - \{\epsilon\}$
  • 若$\epsilon \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 \epsilon$替换为$S\to \{X\}$等，具体来说：

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

表驱动LL(1)分析程序

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

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

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

文法变换

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

消除左递归

消除直接左递归

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

$$\begin{align*} P &\to \beta Q \\ Q &\to \alpha Q \,|\, \epsilon \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\,|\, \epsilon \end{align*}$$

消除一般左递归

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

• 排列非终结符$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$的产生式，增加新终结符使得：

$$\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_{n} \\ Q &\to \beta_{1} \,|\,\dots\,|\, \beta_{m} \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$，不含$\epsilon$产生式的LL(k)的集合真包含于不含$\epsilon$产生式的LL(k+1)的集合