编译原理--期末复习

本文是我学习以下博主视频所作的笔记，写的不够清晰，建议大家直接去看这些博主的视频，他/她们讲得非常好：

基础知识+概念：
1.【【编译原理】期末复习 零基础自学】，资料

2.【编译原理—混子速成期末保过】，评论区楼主笔记

注重题型+解法：

1.【1编译原理求语法树的短语直接短语等等】， 对应的资料：链接，提取码:ozz4

2.【编译原理根据正规表达式构造NFA，到DFA，以及最后的DFA化简/最小化】，对应的资料：链接，提取码：uwud

在此对上述博主的产出表示感谢，也希望大家都能高分通过期末考试~

---

引论

一、高级语言与低级语言的定义

1. 高级语言（High-Level Language）

• 定义：
  高级语言是一种接近人类自然语言（如英语）和数学表达式的编程语言，屏蔽了计算机硬件细节（如内存地址、寄存器操作），使用更抽象的语法（如函数、类、循环）描述逻辑。
  • 例子：Python、Java、C++、C#、JavaScript、Go 等。
• 特点：
  • 可读性强：语法接近自然语言，易于理解和维护（如 if (x > 0) { ... }）。
  • 平台无关性：代码可在不同操作系统（Windows/Linux/macOS）和硬件架构上移植，无需针对底层硬件重写。
  • 抽象程度高：提供内置数据结构（数组、对象）、内存管理（自动垃圾回收）、高级控制结构（循环、递归）等。

2. 低级语言（Low-Level Language）

• 定义：
  低级语言是直接面向计算机硬件（CPU、内存、寄存器）的编程语言，贴近机器指令格式，需手动处理底层细节。
  • 分类：
    • 机器语言：由二进制指令（0/1序列）组成，是CPU唯一能直接执行的语言（如 10110000 表示加载数据到寄存器）。
    • 汇编语言：用助记符（如 MOV、ADD）替代二进制指令，需通过汇编器转换为机器语言（如 MOV AX, 1 表示将数值1存入AX寄存器）。
• 特点：
  • 可读性差：语法复杂，依赖硬件架构（不同CPU的汇编指令集不同，如x86、ARM）。
  • 平台依赖性强：代码只能在特定硬件或操作系统上运行。
  • 控制精细：可直接操作内存地址、寄存器，适合编写高性能或硬件驱动程序。

二、高级语言需要编译/链接的原因

1. 计算机只能执行机器语言

高级语言代码（如C语言的 .c 文件）无法被CPU直接执行，必须经过 翻译过程 转换为机器语言（二进制可执行文件）。这一过程通常包括 编译、链接 等步骤，目的是将抽象的高级语法转换为CPU能理解的指令序列。

2. 编译（Compilation）的作用

• 步骤：
  1. 预处理：处理 #include 头文件、#define 宏定义（如展开代码）。
  2. 编译：将高级语言代码转换为 汇编语言（中间形式）。
  3. 汇编：将汇编语言转换为 目标文件（.o 或 .obj，包含二进制机器指令，但未解决外部依赖）。
• 输出：目标文件（二进制，但可能包含未解析的符号，如调用其他文件的函数）。

3. 链接（Linking）的作用

• 解决依赖：
  目标文件可能引用其他文件的函数（如C标准库的 printf）或全局变量，链接器负责：
  1. 合并目标文件：将多个 .o 文件（如主函数和自定义函数）合并为一个整体。
  2. 解析符号引用：将未定义的符号（如函数名）映射到实际内存地址。
  3. 链接库文件：引入标准库（如C的 libc）或第三方库的代码。
• 输出：可执行文件（.exe 或无扩展名，能直接在操作系统中运行）。

三、编译型语言 vs. 解释型语言

高级语言按翻译方式分为两类：编译型 和 解释型，核心区别在于翻译过程是“一次性完成”还是“边运行边翻译”。

1. 编译型语言（Compiled Language）

• 工作流程：
  源代码 → 编译器（Compiler） → 目标代码（机器语言）→ 链接器 → 可执行文件。
• 特点：
  • 一次编译，多次执行：编译后的可执行文件可直接运行，无需重新编译（如C语言的 .c 文件编译为 .exe）。
  • 执行效率高：机器语言直接由CPU执行，速度快（适合计算密集型任务，如游戏、操作系统）。
  • 平台依赖性：不同操作系统/CPU架构需重新编译（如Windows的 .exe 不能在Linux直接运行，这里如何实现跨平台，可以参考这个视频：【这个问题99%的人会答错！包括我】）。
• 例子：C、C++、Go、Rust。

2. 解释型语言（Interpreted Language）

• 工作流程：
  源代码 → 解释器（Interpreter） → 边逐行翻译边执行（不生成独立的可执行文件）。
  • 部分语言（如Java、Python）会先生成中间形式（字节码），再由虚拟机（JVM、Python解释器）解释执行。
• 特点：
  • 跨平台性强：只要目标平台安装解释器/虚拟机，代码即可运行（如Python代码在Windows/Linux上无需修改）。
  • 执行效率较低：每次运行都需翻译，速度慢于编译型语言（适合快速开发、脚本任务）。
  • 动态类型支持：变量类型在运行时确定，灵活性高（如Python的 x = 1 和 x = "hello" 无需声明类型）。
• 例子：Python、JavaScript、Ruby、PHP、Perl。

3. 混合类型（中间形式）

• Java、C#：先编译为字节码（平台无关的中间代码），再由虚拟机（JVM、.NET CLR）解释执行，兼具编译型的跨平台性和解释型的灵活性。
• Python（优化模式）：可通过 pyc 文件缓存字节码，减少重复翻译，但本质仍是解释执行。

四、核心区别对比

特性	编译型语言	解释型语言
翻译时机	运行前一次性编译为机器码	运行时逐行解释执行
执行效率	高（机器码直接执行）	低（解释器逐条翻译）
跨平台性	差（需针对不同平台重新编译）	好（依赖解释器/虚拟机）
开发效率	低（编译错误需重新编译）	高（即时反馈，无需编译步骤）
典型场景	系统级开发、高性能计算	脚本编写、Web开发、快速原型
代表语言	C、C++、Go	Python、JavaScript、Ruby

五、总结

• 高级语言 提升开发效率，屏蔽硬件细节；低级语言 控制硬件，实现高性能。
• 编译/链接 是将高级语言转换为机器可执行代码的必要步骤，解决代码依赖和平台差异。
• 编译型 vs. 解释型 的选择取决于需求：追求效率选编译型（如C），追求灵活和跨平台选解释型（如Python），而Java等语言通过中间形式平衡两者优势。
  理解这些区别有助于根据项目需求选择合适的编程语言和开发模式。

---

其中我们要学习的 编译 就是上述的一个步骤。

其中编译阶段又分为几个步骤：

词法分析（Lexical Analysis）

词法分析是编译的首个阶段，此阶段的词法分析器会把C++源代码当作字符流来处理，接着按照C++词法规则，将其转换为一系列有意义的词法单元（Token）。

• 关键作用：
  • 过滤掉注释和空白字符（像空格、换行符这类）。
  • 识别出标识符（例如变量名、函数名）、关键字（像int、if）、字面量（例如123、“hello”）以及运算符（如+、*）。
  • 进行词法错误检查，比如检测非法字符、不匹配的引号等问题。
• C++示例：
  对于源代码int a = 42 + b;，经过词法分析后会生成如下词法单元：

  [int] [标识符:a] [=] [字面量:42] [+] [标识符:b] [;]
  

语法分析（Syntax Analysis）

语法分析阶段，语法分析器会依据C++的语法规则，把词法单元构建成抽象语法树（AST）。

• 关键作用：
  • 验证代码结构是否符合C++语法规范。
  • 检测语法错误，例如括号不匹配、缺少分号、错误的if语句结构等。
  • 为后续的语义分析和代码生成搭建结构化的表示形式。
• C++示例：
  对于表达式a = 42 + b;，其抽象语法树可能呈现为：

  AssignmentExpr
  ├─ Left: Identifier(a)
  └─ Right: BinaryOp(+)├─ Left: Literal(42)└─ Right: Identifier(b)
  

语义分析（Semantic Analysis）

语义分析阶段会对抽象语法树进行静态语义检查，保证代码在语义上是合法的。

• 关键作用：
  • 类型检查：保证操作数的类型是兼容的，例如int和int相加，而不是int和函数指针相加。
  • 符号表查询：确认变量和函数在使用之前已经被声明或定义。
  • 检测语义错误，例如变量未定义、类型不匹配、函数调用参数数量不对等。
• C++示例：
  • 错误示例：int a = "hello";（类型不匹配）
  • 正确示例：int a = func(42);（假设func被声明为返回int类型）

中间代码生成（Intermediate Code Generation）

该阶段会把抽象语法树转换为与机器无关的中间表示形式（IR），像三地址码、LLVM IR等。

• 关键作用：
  • 简化后续的代码优化和目标代码生成工作。
  • 支持跨平台编译，因为中间代码可以被翻译成不同架构的机器码。
• C++示例：
  对于代码a = (b + c) * d;，可能生成如下三地址码：

  t1 = b + c
  t2 = t1 * d
  a = t2
  

代码优化（Code Optimization）

代码优化阶段会对中间代码进行转换，以提升代码的执行效率，同时不会改变程序的语义。

• 关键作用：
  • 常量传播：例如把x = 5 + 3;优化成x = 8;。
  • 死代码消除：移除不会被执行的代码，如if (false) { ... }。
  • 循环不变代码外提：将循环内不会改变结果的计算移到循环外面。
  • 强度削弱：把昂贵的运算（如乘法）替换为代价更低的运算（如移位）。
• C++示例：
  原始代码：

  int a = 10;
  int b = a * 4; // 会被优化成 b = a << 2
  

  优化后的中间代码：

  a = 10
  b = a << 2  // 用移位替代乘法
  

---

一些问题：

1. 高级语言的执行都存在中间代码生成阶段。（❌）

解释：像 Python 这类解释型语言存在中间代码生成阶段，而直接编译型语言（如 C 语言）可能直接生成目标代码。

2. 中间代码所生成的依据是语法分析。(❌)

解释：在进行了语法分析和语义分析阶段的工作之后，有的编译程序将源程序变成一种内部表示形式，这种内部表示形式叫做中间语言或中间代码。

所谓“中间代码”是一种结构简单、含义明确的记号系统，这种记号系统可以设计为多种多样的形式，重要的设计原则为两点：一是容易生成；二是容易将它翻译成目标代码。

3. 词法分析中，对变量分析后的输出是该变量的值和类型。(❌)

解释：词法分析的输出是记号（Token），包含类型和属性值，并非变量的实际值与类型，变量值和类型的确定发生在语义分析阶段。

4. 源程序经词法分析后得到的中间结果是 (A)
   A. 单词(token)
   B. 四元式
   C. 语法树
   D. 语法分析程序

解释：

• 词法分析：输出 Token 序列。
• 语法分析：依据 Token 序列构建出抽象语法树（AST）。
• 中间代码生成：生成三地址码或者四元式等中间表示形式。
• 语法分析程序：属于编译程序的一个组件，并非词法分析的输出内容。

第一/二章：概述、文法和语言

• 空串，一个字符串的长度为0
• 空集，一个集合中没有任何元素（空串也是一个元素）
• 字符串的乘积，字符串直接拼接在一起
• 集合的乘积，使用前一个集合中的元素与后一个集合中元素进行拼接。
• 集合的闭包，有限个集合的乘积。

---

---

文法

分类

• 0型文法：短语文法
• 1型文法：上下文有关文法
• 2型文法：上下文无关文法
• 3型文法：正规文法

上下文无关文法

上下文无关文法，是一个四元组，包含非终结符号、终结符号、重写规则集合、识别符，可以理解为由 非终结符定义为非终结符/终结符 产生式组成的文法。

• 终结符号，只在产生式的右边出现的符号。
• 第一条产生式的左部，是识别符。
• 通常使用大写字母表示非终结符，小写字母表示为终结符。（但并不是说，“文法中的小写字母一定是指终结符”，在文法里，习惯上用小写字母表示终结符，但这并非强制规定，具体要依据文法的定义来判断符号类型。）

• 左线性文法和右线性文法，在一个文法中同时只能出现一种，这个文法才是正规文法。
  
  

---

相关概念

所以，句子一定是句型。

---

• 子树：树根和其向下射出的部分。
• 简单子树：有且只有单层分支的子树。
• 子树的末端结支符号串是相对于子树根的短语。
• 简单子树的末端结点组成的符号串是相对于简单子树根的简单短语/直接短语。（根节点能够直接推出终结符）
• 素短语：(在短语中找，至少含有一个终结符，且不含其他更小素短语)
• 最左简单子树的末端结点组成的符号串是句柄。（句柄这个概念只会出现在最右推导/规范推导中才会出现的概念）

一个句型的最左 直接短语 称为该句型的句柄。

根据文法画出语法树，进行推导：

---

---

二义性

• 如果两种推导方式画出的树不同，则说明该文法有二义性。
• 可能存在两个不同的最左推导，但是它们对应的语法树相同。

注意错误的说法如下（充分条件和必要条件的区别）：

1. 如果文法是二义的，则最左推导和最右推导必然不同（❌）
2. 如果文法是二义的，则最左推导和最右推导对应的语法树必定相同。（❌）

---

---

二义文法由于无法进行语法分析，没有存在的必要。（❌）

解释： 二义文法并非无法进行语法分析，而是需要结合消除歧义的规则（如优先级、结合性）来唯一确定语法结构。在编译实践中，二义文法常被合理使用，以简化文法描述并保持分析的正确性，因此具有明确的存在价值。

第三章：词法分析

右线性文法

正规式

---

解析： 正规式的本质作用是定义和识别语言集合。当两个正规式 $M_1$ 和 $M_2$ 识别的语言集合相等时，即对于任意一个字符串，若$M_1$能识别（接受该字符串），$M_2$ 也能识别，反之亦然，那么就称这两个正规式等价 。

---

这一步可以先不看，先看后面的“根据正规式得到NFA”。

题型：

1. 根据正规式画出NFA图
2. 根据NFA图，使用子集构造法
3. 根据子集构造法，画出DFA（新状态集合中，凡是包含原来NFA终态的，都是新的终态）

参考视频。

根据正规式得到NFA

参考视频：【编译原理根据正规表达式构造NFA，到DFA，以及最后的DFA化简/最小化】

NFA的确定化和最小化

先以第（2）问进行讲解：


获取到确定化后的集合，也可以画出对应的图。

最小化是对已经确定好的DFA来说的，有这几个步骤：

1. 初始化，将集合换分为两个集合：一个终态集合，一个其他集合
2. 判断其他集合是否可区分：可区分就单独成一个集合。
   

最终答案：

具有ε动作的NFA确定化

这里关于第一行$q_0$状态到$q_2$中，有$S_3$状态的解释：假设a,b,c是各种票，空是免费通过，$S_2$用c票到了$S_2$，然后走免费通道到了$S_3$（必须先有一张票，才能走免费通道）

---

---

考察题目

1. 没有ε边的有限自动机一定是DFA。（❌）

解释：

• DFA 要求每个状态对每个输入符号必须有且仅有一个确定的转移。
• NFA 允许对同一输入符号存在多个转移（非确定性）或无转移，即使没有ε边也是如此。

2. 不确定的有限自动机（NFA）可能存在一个以上的起始状态。（✔）

评分标准：
(1) 正规式得2分，构造NFA得4分(共6分)
(2) 子集构造法：表格4分，DFA 4分，最简判断1分（9分）

（1）正规式： $a(a|b{)}^{\ast }b$

这里中间部分$(a|b{)}^{\ast }$的含义在前面讲解过：

中间部分的正规式可以表示为(a|b)*，但需要注意，这里中间部分可能为空，即允许字符串长度为2的情况（如ab）。因此，整个正规式可以写成：a(a|b)*b。这个表达式表示以a开头，中间有零个或多个a或b，最后以b结尾的所有字符串。

（2）得到NFA：

（3）根据子集构造法，得到最简DFA：
ε-CLOSURE{S} = {S}

$I_{\epsilon }$	$I_a$	$I_b$
$q_0${S}	{A, B, C} $q_1$	∅
$q_1${A, B, C}	{B, C} $q_2$	{B, C, Z} $q_3$
$q_2${B, C}	{B, C} $q_2$	{B, C, Z} $q_3$
$q_3${B, C, Z}	{B, C} $q_2$	{B, C, Z} $q_3$

• 始态：$q_0$
• 终态：$q_3$

π = { {$q_0$，$q_1$，$q_2$}，{$q_3$}}

{$q_0$，$q_1$，$q_2$}不可区分：

第四章：自顶向下语法分析方法

First和Follow集

求这两个集合是后续做题的基础，所以必须会！！！

• First(A)：要找到左边等于A的产生式，然后看产生式的右部可能出现的终结符。空串也属于符号集。
• Follow(A)：要找到产生式右部含有A的产生式，然后查看A右边的情况，找出该非终结符后面所能跟随的所有终结符：
  • 如果A右边是空，则将Follow(左部非终结符) 添加到结果集中
  • 否则求出A右边符号串的First集 - 空串。

LL(1)文法

当需要选用自顶向下分析技术时（文法到字符串），必须判别所给文法是否是LL(1)文法。因而对任给文法需首先计算FIRST、FOLLOW、SELECT集合，进而判别文法是否为LL(1)文法。

LL (1) 中第一个 L 表示从左到右扫描输入串，第二个 L 表示最左推导，1 表示向前看一个终结符。

判断一个文法是否是LL(1)文法，有两种方式（在使用这两个方法之前，还必须要消除文法的左递归和回溯）：

First集的交集为空集

对于一个非终结符有多个产生式，才需要求出该非终结符的First集。

select集

选择符号集：

1. 右部推导不出空串，就是First集
2. 右部可以推导出空串，就是First集-空串，左部的Follow集。

---

所以说，判断一个文法是否是LL(1)文法，只需要求出 “一个非终结符号有多于两个的产生式” 的非终结符的select集。

非LL(1)文法到LL(1)文法的等价变换

以下这两个步骤，都是在考察LL(1)文法时要进行的第一步操作，类似于：

提取左公共因子

消除左递归

1. 与E无关是β，这里是T
2. 与E相关，出现在右边的是α

---

LL(1)分析的实现

表驱动分析程序/LL(1)分析表

1. 先求出First集，如果一个非终结符能推出$\epsilon$，就需要求出Follow集
2. 将产生式写到 行是非终结符，其First集为终结符的列 处
   
   

递归向下分析方法

• 一个非终结符对应一个子程序
• 根据产生式的右部来设计：
  • 每遇到一个终结符，判断当前读入的单词是否与终结符匹配，如果匹配则继续读下一个单词；如果不匹配则进行错误处理。
  • 每遇到一个非终结符，则调用对应的子程序

分析过程

---

考察题目

评分标准：文法5+集合10+分析表3+分析过程2=20

（1）消除左递归和左公因子后的文法：

• $A\to a{A}^{\prime }$
• $A^{\prime }\to ABc|\epsilon$
• $B\to d{B}^{\prime }$
• $B^{\prime }\to b{B}^{\prime }|\epsilon$
  

（2）改造后的文法是LL(1)文法。预测分析表如下：

非终结符	a	b	c	d	#
A	$A\to a{A}^{\prime }$
A’	$A^{\prime }\to ABc$			$A^{\prime }\to \epsilon$	$A^{\prime }\to \epsilon$
B				$B\to d{B}^{\prime }$
B’		$B^{\prime }\to b{B}^{\prime }$	$B^{\prime }\to \epsilon$

（3）输入串 ( aadc# ) 的分析过程：

步骤	分析栈	剩余输入串	动作
1	#A	a a d c #	$A\to a{A}^{\prime }$
2	#A’a	a a d c #	匹配a
3	#A’	a d c #	$A^{\prime }\to ABc$
4	#cBA	a d c #	$A\to a{A}^{\prime }$
5	#cBA’a	a d c #	匹配a
6	#cBA’	d c #	$A^{\prime }\to \epsilon$
7	#cB	d c #	$B\to d{B}^{\prime }$
8	#cB’d	d c #	匹配d
9	#cB’	c #	$B^{\prime }\to \epsilon$
10	#c	c #	匹配c
11	#	#	匹配#，接受

输入串 ( aadc# ) 被成功分析。

第六章：LR分析

LR(0)项集规范族构造过程

1. 增广文法的变换：开始符号有多个产生式，需要对开始符号进行增广文法的变换，使新的开始符号只有一个产生式。
2. 列表的形式给出：状态、项目集、后继符号、后继状态
3. 一个状态的项目集，就是在产生式右部写一个点，如果点后面（后继符号）是非终结符，则需要在项目集中添加该非终结符的产生式（右部也需要带点）

4. 还需要求$S_0$的项集中每一个式子的闭包，就是把点向后移动一个，如果点后面是非终结符，就进行上面的步骤；如果是终结符/空，就结束。
5. 如果是空，其后继符号就是把项目集抄一下，然后在前面加上一个#
6. 如果是终结符，其后继符号就是终结符

LR(0)文法

• 如果$I_i$里同时有归约项目和移进项目，就是移进-归约冲突
• 看一个状态$I_i$里面，是不是只存在一个归约项目，如果状态里有两个归约项目，京就是归约-归约冲突
• 比如$I_i$明明是归约状态却又伸出来个箭头指向其他的状态就说明冲突了

分析表和分析过程

---

1. 遇到$r_i$时，使用第 i 个归约式进行出栈归约，并且GOTO[状态栈顶状态, 非终结符]，如GOTO[5, B] = 9
2. 将 GOTO[状态栈顶状态, 非终结符] 放到状态栈中，非终结符放到符号栈中。
3. 直到 栈顶状态，输入串 = acc，结束

SLR(1)分析

判定

冲突项目集的简单向前看1集合的交集为空集，则是SLR(1)语法：

• 归约-移进冲突：归约项的FOLLOW集，与移进项的终结符的交集。
• 归约-归约冲突：求两者FOLLOW集的交集

分析表

与LR(0)分析表不同的是，对于归约项不要将一行全使用$r_i$进行填写，而只是在FOLLOW(A)集合所在列填写。

分析过程

LR(1)文法

• 后继状态的向前搜索符，就是前一个状态的向前搜索符。
• 当前集合的扩展闭包的向前搜索符，连接字符串的First集

冲突如何解决？

• 归约-归约冲突，向前搜索符不相交，就可以解决冲突
• 归约-移进冲突，归约项看向前搜索符，移进项还是看点后面的终结符。

表格：

1. 归约项的列，由向前搜索符决定。写成$r_i$
2. 移进项的列，由点后面的终结符决定

LR1会使同心集分裂，所以它的状态数（项目集数）是最多的。

LALR(1)分析

1. 拓广文法
2. 合并同心集：产生式相同，合并向前搜索符
3. 重新构造表
   

如何区分LR文法

【11编译原理如何区别LR(0),SLR(1),LR(1),LALR(1)文法】

逆波兰表达式

找主运算符的原则：

1. 括号内的表达式要先看作一个整体；
2. 运算符优先级越低，也是主运算符；
3. 在逆波兰表达式中越是右边的，越是主运算符

对于这个中缀表达式：

1. 先将括号内部的表达式看作一个整体：$E_1=(B\ast D-C/A)$，表达式变为$A\ast E_1+B$
2. 对于$A\ast E_1+B$表达式，比较*和+的优先级，+的优先级较低，作为主运算符，写在逆波兰表达式的最后：$(A\ast E_1)B+$