编译原理复习

题型介绍

• 单项选择题：(每题2分，10题，共20分)
• 小的简单解答题：(每题约5-10分，2-3题)
• 大的综合解答题： (每题约12-20分，3-4题)
  • 两种解答题共6题

第一章

理解：什么是编译器

掌握：编译器的几个阶段

您应该熟悉编译器的每个阶段，并用图形或文本描述整个过程。

前端：语言

中间：IR与编辑器优化技术

后端：目标平台（指令集，芯片）的可执行代码

什么是编译器？

编译器是将程序从一种语言翻译成另一种语言的计算机程序

前端：语言

中间：IR与编辑器优化技术

后端：目标平台（指令集，芯片）的可执行代码

从描述到实现

• Lexcal analysis(Scanning)【词法分析】：识别描述的逻辑部分【产生token】
• Syntax analysis(Parsing)【语法分析】：确定这些片段之间的关系【产生语法树】
• Semantic analysis【语义分析】：确定整体结构的含义，主要做类型检查【产生注释分析树】
• IR Generation【IR生成】：设计一种可能的结构【中间代码生成】
• IR Optimization【IR优化】：简化预期结构【中间代码优化】
• Generation：生成目标代码
• Optimization：优化目标代码

前四个为Front End，后三个为Back End

符号表管理：编译器的重要功能之一是记录源程序中使用变量的名字，并收集每个名字的各种属性有关的信息，用于快速存放和快速获取记录数据

将多个步骤组合成趟：多个步骤的活动可以组合成一趟（pass）比如前四个步骤为前端趟。

解释器和编译器的区别

• 解释器：解释器在翻译过程中执行源程序【词法分析，语法分析，语义分析之后就开始执行代码了，不需要转化为目标代码】
• 编译器：在转化过程中执行目标代码

相同点：他们都是语言实现系统

---

第二章

理解：正则表达式概念，NFA,DFA

要求掌握：写正则表达式，NFA，DFA，DFA最小生成树，词法分析器的生成

熟悉R.E.的表达，了解R.E.和C.F.G.的区别，能相互翻译。在给定R.E时，知道如何绘制NFA和DFA，以及如何最小化它。

大纲

• 扫描
• 正则
• NFA和DFA
• RE to NFA
• from NFA to DFA
• 最小化DFA

一些概念

词素【lexemes】

• 我们制作token的原始程序片段成为词素（lexeme），然后和某个词法单元的模式匹配
• while就是一个词素，和词法单元while模式匹配
• 有时候我们也会丢弃一个词素，而不是存储起来以后使用，比如空格和注释，它和源程序的意义无关

词法单元【token】

• 我们可以视为一个枚举类型，表示我们从源代码中读取的逻辑实体，一般一个token对应一个模式

• 某些词法单元可以具有存储额外数据的属性【当然也可以没有】，比如下面代码：

  while(137 < i){
      ++i;
  }

  我们肯定是需要找一个词法单元来表示137，因此我们使用T_Int来作为词法单元，然后137为词法单元的属性

词素集【set of lexemes】

• 将一组词素与每个标记关联起来
  • 我们可以将Number和集合{0, 1, 2..., 12}直接关联
  • 我们可以将String和集合{“sqfq”, "fnsod"}直接关联

解析器parser【语法分析之前的部分】

• 解析器可以使用词法单元序列【token】来恢复程序结构

解析器使用词法单元序列来恢复程序结构

词法分析的目的

• 将程序转化为词法单元序列
• 每一个词法单元表示源文件的一个逻辑判断、关键字、或者变量名称等
• 表示特定的字符模式，比如标识符必须以字母开头等等
  • 标识符是一个字符串，通常由字母和数字构成
  • 比如a > b，a为一个词素，然后经过词法分析器变成词法单元时，作为标识符
• 都与一个词素相关联
• 每个词法分析单元都可以具有可选属性
• 词法分析单元序列将会被用于解析器进行语法分析，恢复程序结构

正则表达式

形式语言【formal languages】

用于描述与每种token相关联的词素集

形式语言是一组字符串

许多无限语言都有有限描述

• automation【使用自动机定义】
• grammar【使用语法定义】
• regular expression【使用正则表达式定义】

字符串和语言

• Alphabet：任何有限的符号集，比如：{‘a’, ‘b’, ‘c’}

• String：某些字符串基于Alphabet组成的有限序列，比如：”acacb”【集合为{‘a’, ‘b’, ‘c’}】

  • 注意：空字符串不属于空字符集。

• Language：基于Alphabet组成的有限序列的字符串的集合
  $$
  \epsilon记为空字符，{ \epsilon }为Language，但并非与\Phi({})相等，但两者也为Language
  $$

正则表达式相关

• 定义：是一类可以捕获语言某个特定字段的描述，通常十分简洁易读

• 原子正则表达式【atomic regular expressions】：任何符号仅与自己相同的字符来匹配

• 复合正则表达式【Compound Regular Expressions】：

  • concatenation【串联】：R1R2
  • union【组合并联】：R1|R2
  • Kleene closure【Kleene闭包】：R*【表示所有由R字符表构成的串的集合，包括空串】
  • closure【正闭包】：R_+【和Kleene closure只相差R_0】，如果空串不属于R*，那么空串一定不属于R_+
  • same：(R)

• 运算符优先级：() > * > concatenation > union

  • {}：表示重复次数(a | b)(a | b) = (a | b){2}

  • ?：表示可以有或者可以没有(0 | \epsilon) = 0?

  • []：表示范围[a-z] = a | b | c ... | z

NFA->DFA

正则表达式主要用有限自动机来实现

NFAs：非确定有限自动机【可以有多个转换】

DFAs：确定性有限自动机【只能有一个转换】

对于长度为m的字符串和具有n个状态的自动机，NFA为O(mn^2)，DFA为O(m)

RE to NFA 【正则转化成NFA】

使用归纳法：【Inductive method】

NFA转换为DFA，重要的一点就是需要DFA来模拟NFA

我们需要做的，就是消除\epsilon跃迁

• closure与move的计算，得到X个状态，再进行配置重排
  • closure：计算该点下一个目标为空字符串的集合【包括自己】
  • move(I, a)：计算点集I中，指向为a的结果点集
• 判断是否为Accept点，只需看最后得到的DFA中的重构结点，有没有NFA之前的尾节点

最小化DFA

就是求出等价的最小DFA,下图就是一个最小化DFA的过程

可以采用分割法来求：

以NFA->DFA为例：

0123分为一个集合A，4分为一个集合B

0a1A 1a1A 2a1A 3a1A

0b2A 1b3A 2b2A 3b4B

因此第一次，将3划分出去

{012} = C {3} = D

0a1C 1a1C 2a1C

0b2C 1b3D 2b2C

因此第二次，将1划分出去

{02} = E {1} = F

0a1F 2a1F

0b2E 2b2E

因此02不可再分，两个是同一个状态，可以合并

词法歧义【Lexing Ambiguities】

使用NFA/DFA即可

当应用两个正则表达式时，请选择“优先级”较高的正则表达式

一般，会添加一个任何字符匹配的【全部捕获规则】并报告错误

---

第三章

理解：上下文无关语法，派生，解析树，抽象语法树，歧义语法

熟悉C.F.G的语法，知道如何进行最左/最右的派生。给定一组语法和一个表达式，可以画出解析树和抽象语法树。

大纲

• 语法分析的形式
  • 上下文无关文法【Context-Free Grammars，也称作CFG】
  • CFG和语法
  • 派生【Derivations】
  • 具体和抽象语法树【Concrete and Abstract Syntax Trees】
  • 歧义【Ambiguity】
• 解析算法
  • 自顶向下Derivations
  • 自下而上Reductions

什么是语法分析

• 在词法分析之后，我们有一token序列
• 在语法分析【或者解析】中，我门需要解释这些token的含义
• 恢复token序列描述的结构
• 如果这些标记没有正确的编码结构就会报错

输入：解析器调用scanner过程来获取下一个令牌

输出：需要构造显式或隐式语法树。语法树的每个节点都包含编译过程其余部分所需的属性

形式语言

• 字母表【alphabet】：字母表是一组构成字符串最小粒度的字符集，我们记为\Sigma
• 语言【language】：是字母表内部符号构成的一组字符串

上下文无关文法

语言的定义

$$
如果S\Rightarrow^\alpha,\alpha\in(V_T\cup V_N)^,则称\alpha是G的一个句型
$$

• 一个句型既可以包含终结符，也可以包含非终结符，也可能是空串

$$
如果S\Rightarrow^\alpha,\alpha\in(V_T)^,则称\alpha是文法G的一个句子，我们可以定义为L(G)
$$

• 句子是不包含非终结符的句型
• 语言的运算

产生式的定义

$$
G = (V_{T}, V_{N}, P, S)
$$

• V_{T}为终结符号【比如<apple>】
• V_{N}为非终结符号【比如<动词><名词><形容词>】
• P为产生式【a->b读作a定义为b】：<名词短语> -> <形容词><名词短语>
• S为开始符号，表示的是该文法中最大的语法成分

其中这里面，满足：
$$
V_{N} \cap V_{T} = \varnothing
$$

$$
当产生式满足:\forall\alpha\rightarrow\beta,\alpha\in V_{N},\beta\in(V_N\cup V_T)^*
$$

则为上下文无关文法(CFG)

文法的分类

• unrestricted
• CSG
• CFG
• regular

一些限制

不可以使用正则表达式的方法来定义文法，我们要不断解构来定义文法
$$
S\rightarrow a(b|c^*)~~~~~~~(×)
$$

$$
S\rightarrow aX
$$ {$$}

$$
X\rightarrow b|C
$$

$$
C\rightarrow Cc|\epsilon~~~~(√)
$$

解析树

功能

• 是token字符串结构的有用表示形式
• 解析树直观的表示派生

构造和特点

• 表示终结符号的叶子节点
• 表示非终结符号的中间节点
• 叶子从左往右遍历是原始输入
• 一个解析树对应许多派生
• 派生并不唯一的表示它们构造的字符串的结构，而解析树唯一表示
• 解析树表示其提取派生的基本特征，同时按顺序分解表面差异

种类

• Leftmost derivation：优先替换最左边，对应前序遍历
• Rightmost derivation：优先替换最右边，对应镜像的后序遍历

最左派生和最右派生对于他们构造的字符串是唯一的，它们与解析树唯一关联

抽象语法树

【Abstract Syntax Trees，简称AST】

为什么需要抽象语法树？

因为解析树的信息比编译器生成可执行代码所需的信息要多得多

定义

抽象语法树表示实际源代码token序列的抽象

解析器将完成解析树表示的所有步骤，但通常只需要构造抽象语法树

Ambiguity【歧义】

某些语法可能导致了有多个解析树

(int - int) - int

定义

如果存在字符串w，则语法G使得w有不同的解析树，这时我们称为Ambiguity。

解决方法

• Disambiguity rule【消歧规则】：主动添加规则，比如添加优先级* > -

  • 不改变语法
  • 语言的语法结构不再仅仅由语法给出

• Rewriting the grammar【改写语法】

  • 将语法更改为强制构造正确解析树的形式

  

  

---

第四章

掌握：LL（1）语法，递归下降解析的构造，LL（1）解析，计算第一集和跟随集

给定C.F.G，知道左因子和左递归移除，知道如何计算它的第一个/跟随集，知道判断它是否是LL（1）语法，知道构造解析表。

Top-Down Parsing：自顶向下分析

推导方式

• 自顶向下：最左非终结符替换
• 自底向上：最右非终结符规约

计算机自顶向下语法分析的通用形式

• 递归下降分析【Recursive-Descent Parsing】

  • 由一组过程组成，每个过程对应一个非终结符
  • 从文法开始符号S对应的过程开始，其中递归调用文法中其他非终结符对应的过程。如果S对应的过程恰好扫描了整个输入串，则成功完成语法分析
  • 但是可能需要回溯，会导致效率较低

• 预测分析【Predictive Parsing】

  • 预测分析是递归下降分析技术的一个特例，通过在输入中向前看固定个数符号来选择正确的产生式

  • 预测分析不需要回溯，是一种确定的自顶向下分析方法

文法转换

左递归

$$
A\rightarrow A\alpha
$$

1. 有该形式产生式的文法称为是直接左递归【immediate left recursive】

2. 如果一个文法中有一个非终结符A使得对某个串a有：

$$
A\Rightarrow^+Aa
$$

​ 那么这个文法就是左递归的

3. 经过两步及以上的推导产生的左递归叫间接左递归
4. 会使递归下降分析器进入无限循环

消除直接左递归

例子：
$$
A\rightarrow A\alpha|\beta
$$
正则表达式：
$$
r=\beta \alpha^*
$$
我们可以根据正则表达式转化：
$$
A=\beta R
$$

$$
R\rightarrow \alpha R|\epsilon
$$

这样，我们就将左递归转化成了右递归

当然，消除左递归是需要付出代价的，代价就是引进了一些非终结符和空串产生式

消除直接左递归的一般形式

$$
A\rightarrow A\alpha_{1}|A\alpha_{2}|…|A\alpha_{n}|\beta_{1}|\beta_{2}|…|\beta_{n}~|
$$

消除，则：
$$
A\rightarrow \beta_{1}G|\beta_{2}G|…|\beta_{n}G
$$

$$
G\rightarrow \alpha_{1}G|\alpha_{2}G|…|\alpha_{n}G
$$

LL(1)文法

非终结符的后继字符集

FOLLOW(A)为一个集合，为非终结符A之后会跟的终结符的集合

注意，A之前必须要有一个终结符
$$
A\rightarrow aBC
$$

$$
C\rightarrow d
$$

则FOLLOW(A) = {d}

产生式的可选集

定义：我们要选用哪一条文法，就必须要对应哪一个字符集，比如输入$a$字符集，就可以对应$A\rightarrow a\beta$，可以书写为：
$$
SELECT(A\rightarrow a\beta) = {a}
$$

$$
SELECT(A\rightarrow\epsilon) = FOLLOW(A)
$$

q_文法

• 每个产生式的右部可能为$\epsilon$，或者以终结符开始
• 具有相同左部的产生式有不相交的可选集

【因此，q_文法不含右部以非终结符打头的产生式】

串首终结符

• 定义：串首第一个符号，并且是终结符
• 给定一个文法符号串a，a的串首终结符集$FIRST(\alpha)$

$LL(1)$文法的定义

文法$G$为$LL(1)$的，当且仅当$G$的任意两个具有相同左半部分的产生式$A\rightarrow \alpha|\beta$满足下面条件

• 给定一个文法符号串a，a的串首终结符集FIRST($\alpha$)被定义为
  • 可以从$\alpha$推导出的所有串首终结符构成的集合。如果$\alpha \Rightarrow^*\epsilon$，那么$\epsilon$也会在$FIRST(\alpha)\cap FIRST(\beta)=\Phi$中
  • $\alpha$和$\beta$至多有一个能推导出$\epsilon$
  • 如果$\beta\Rightarrow^\epsilon$或$\alpha\Rightarrow^\epsilon$，则$FIRST(\alpha)\cap FOLLOW(A)=\Phi$

这三个条件是为了保证同一非终结符的各个产生式的可选集互不相交

FIRST和FOLLOW的计算

FIRST的计算

FOLLOW的计算

• 如果A是某个句型的最右符号，则将结束符号$添加到FOLLOW(A)中

LL(1)的判断

计算出所有式子的SELECT集，然后有相同左部分的SELECT集是不相交的，就是LL(1)

预测分析表

---

第五章

掌握：$LR(0)$解析，$SLR(1)$解析

理解：正确的句子形式，可行的前缀，句柄

你一定很容易写出给定C.F.G和表达式的正确句子形式，并找出变量前缀和句柄。了解LR（0）和SLR（1）的区别。知道什么时候会出现歧义。更重要的是，给定C.F.G，能够写出其LR（0）项，绘制DFA，构造SLR（1）解析表，并知道如何根据它在堆栈表中逐步解析表达式。

自底向上分析

• 从分析树的底部向顶部方向构造分析树
• 可以看成是将输入串$\omega$规约为文法开始符号S的过程
• 自顶向下的语法分析采用最左推导方式，自底向上的语法分析采用最左规约方式
• 自底向上的语法分析的通用框架：移入—规约分析【shift-Reduce Parsing】

每次规约的符号串称为【句柄】

关键问题：移入-规约分析中容易错误识别句柄

四个动作

• 移入：将下一个输入符号移动到栈顶
• 归约：被归约的符号串的右端必然处于栈顶。语法分析器在栈中确定这个串的左端，并决定用哪个终结符来替换这个串
• 接收：宣布语法分析规程全部完成
• 报错：发现语法错误并调用错误恢复子例程

$LR(0)$分析

• L：对输入进行从左到右的扫描
• R：反向构造出一个最右推导序列

LR分析器通过自动机来进行归约分析

一些概念

• sn：将符号a，状态n压入栈中
• rn：用第n个文法的产生式进行归约

项目

右部某位置标有圆点的产生式称为响应文法的一个LR(0)项目【简称为项目】
$$
S\rightarrow b·BB
$$
产生式$A\rightarrow\epsilon$只生成一个项目$A\rightarrow·$

增广文法【Augmented Grammar】

如果G是一个以为开始符号的文法，则G的增广文法$G’$就是在G中加上新开始符号$S’$和产生式$S’\rightarrow S$得到的文法

引入该新的开始产生式的目的是使得文法开始符号只有一个在产生式的左边，从而使得分析器只有一个接收状态

后继项目

$A\rightarrow\alpha·X\beta$的后继项目为$A\rightarrow\alpha X·\beta$

LR(0)自动机

• LR(0)容易出现移进-归约冲突【指项目集有归约项目和归约中的项目，填表的时候不知是用rn归约选式子还是用下一个项目集合】
• LR(0)容易出现归约-归约冲突【指项目集中的项目不知道先归约哪一个】

例如下面的$B\rightarrow·$和$T\rightarrow·$。如果有空串，不知道先归约哪一个

SLR分析

与$LR(0)$是类似的，唯一不同的地方是对归约项目的处理上

我们需要计算$FOLLOW(A)$的值，然后再用哪个式子归约来进行一个判断

缺点：无法进行移进-冲突归约的解决

---

第六章

掌握：依赖图，属性计算算法

了解：属性语法、合成属性和继承属性

了解语义分析的任务及其实现方法。知道如何通过给定的方程式计算属性值。了解如何绘制依赖关系图，以及如何标记解析图的属性或值。

---

第七章

掌握：基本结构的中间代码生成：三地址代码；TAC表示控制结构，TAC表示表达式

给定上下文无关语法和属性语法，可以通过SDT（语法定向翻译）将源代码翻译成TAC