编译原理知识点整理
语言 (Language)
语言研究包括如下三个方面
- 语法
语言的正确形式: ; - 语义
语言的含义: ; - 语用
语言和使用者的关系: 。
编程语言 (Programming Language)
可通过时期对编程语言进行如下分类
机器语言使用计算机唯一能够识别的二进制代码指令来编写程序的语言
汇编语言又称符号语言
汇编器 (Assembler)
将汇编程序替换为机器码
汇编器生成的文件称为目标文件
助记符
链接器 (Linker)
将多个目标文件外加库链接为一个可执行文件
链接的时机如下
- 编译时
静态链接器负责: ; - 加载时
加载器负责: ; - 运行时
动态链接器负责: 。
加载器 (Loader)
将可执行文件放到内存中执行
编译器 (Compiler)
将源语言程序转换为等价的
Assembly languages have direct, one-to-one mapping to machine instruction. But, a single line of a high-level programming language might result in dozens of instructions.
编译的大体过程如下
- 词法分析
; - 语法分析
; - 语义分析
; - 中间代码生成
; - 代码优化
; - 目标代码生成
。
贯穿其中的两个逻辑部分如下
- 符号表管理
; - 错误处理
。
对输入文件从头到尾扫视
解释器 (Interpreter)
直接利用用户提供的输入执行源程序中指定的操作
在把用户输入映射为输出的过程中
解释
预处理器 (Preprocessor)
将源程序聚合在一起
乔姆斯基谱系 (Chomsky Hierarchy)
乔姆斯基将文法分为如下四种类型
其中
四种文法对应的四种语言有关系 , 。
类型 | 名称 | 产生式 |
---|---|---|
0 |
递归可枚举文法 | |
1 |
上下文有关文法 | 在 |
2 |
上下文无关文法 | |
3 |
正规文法 |
满足 |
巴科斯范式 (BNF; Backus-Naur Form)
即上下文无关文法
文法
文法
- 终结符
; - 字母表
非空有穷的基本符号集: 因此字母表中的元素称为符号, ; - 符号串
由符号组成的任何有穷序列: > 空符号串用。 表示 长度为, 符号串的。 次方幂即把符号串重复写 次 。 即 的闭包 表示, 上所有有穷长的符号串的集合 。 而 称为 的正闭包 。
- 字母表
- 非终结符
; - 产生式
形式如下, ; 其中 读作 定义为「 或」 可具有此般形式「 」 。 - 指定一个非终结符为开始符号
。
推导 (Derivation)
即从开始符号起
直接推导记为
归约
(Reduction) 即推导的逆过程 。
语言可定义为推导所得所有终结符串的集合
代表性的文法
如下的文法指明了运算符的结合性和优先级
词法分析 (Lexical Analysis)
将源代码分割为若干个词法单元的处理
词法单元 (Token)
又称记号
词法单元在形式上可表示为二元组
。
词法单元的常见类别有关键字
词素 (Lexeme)
源程序中的字符序列
词法分析器将词素分析为词法单元的实例
将词法分析工作分离的考虑如下
- 使整个编译程序的结构更简洁
清晰和条理化、 ; - 编译程序的效率会改进
; - 增强编译程序的可移植性
。
词法单元的形式化描述工具有正规文法
有穷自动机 (Finite Automata)
模式的识别装置
确定有穷自动机
- 有穷状态集
; - 输入符号字母表
; - 转换函数
是, 的映像 即定义状态关于输入符号的后继状态, ; - 初态
; - 终态集
终态又称可接受, 。
不确定有穷自动机
- 转换函数
是, 的映像 即输入可为符号串, 且相同输入的后继状态可有复数个, ; - 非空初态集
。
显然
DFA 是 NFA 的特例 对于每个 。 NFA 都存在一个与之等价的 DFA 。
子集构造 (Subset Construction) 算法
将
其中
子集指 , NFA 状态的子集 。
子集构造算法中的函数定义如下
操作 | 描述 |
---|---|
能够从 |
|
即 |
|
能够从 |
子集构造算法的伪代码如下
SUBSET-CONSTRUCTION 输入 输出 |
---|
一开始 |
任何正则语言都有一个唯一的状态数目最少的
无用状态 (Dead State)
无法到达或无法由此状态到达终态的状态
无用状态可以非常简单地被消除
等价状态 (Non-distinguishable State)
DFA
两个状态等价的条件如下
- 一致性条件
两个状态必须同时为可接受状态或不可接受状态: ; - 蔓延性条件
对于所有输入符号: 两个状态必须转换到等价的状态里, 。
可以通过不断分割
lex
自动生成词法分析器的工具
flex
是增强版的 lex 其中 , f 指快速 (Fast) 。
一个
1 | /* 定义区块 */ |
下例定义匹配实数模式串并返回实数的规则
1 | ([1-9][0-9]*)|0|([0-9]+\.[0-9]*) { |
下例忽略代码中的空白
1 | [ \t] ; |
若匹配失败则出现词法错误
.
用于匹配除换行符 \n
外的任何字符 。
1 | . { |
语法分析 (Syntax Analysis)
从词法单元构建语法树的处理
抽象语法树 (AST; Abstract Syntax Tree)
又称语法树
语法树涉及的概念如下
- 句型
在语法树生长过程的任何时刻: 所有叶子结点的排列, ; - 短语
完整语法树中一棵子树的所有叶子排列: ; - 直接短语
限制子树为仅有父子两代的一棵子树: ; - 句柄
最左的直接短语: 。
- 直接短语
自顶向下分析
从文法的开始符号出发
在上下文无关文法
操作 | 描述 |
---|---|
LL(k) 文法
从左向右扫描输入串
通常采用
文法 。
LL(1) 文法
其中
, 和 是 的两个不同产生式 。
某些非
提取左公因子
; 对于产生式
可改写为如下形式 。 不含左公因子只是
文法的必要条件 而非充分条件, 。 消除直接左递归
。 对于产生式
可改写为如下形式 。 将前述代表性的文法消除直接左递归
得到如下形式, 。 要消除间接左递归
需通过产生式置换非终结符, 转换为直接左递归后再消除, 。
预测分析表 (Transition/Parsing Table)
以前述代表性的文法为例
Nonterminal | Nullable? | ||
---|---|---|---|
✓ | |||
✓ | |||
再求出各产生式的
最后构造预测分析表
Nonterminal | ||||||
---|---|---|---|---|---|---|
自底向上分析
LR(k) 文法
向右查看
通常
。
LR(0) 文法
项 (Item)
在文法
产生式
对空产生式
有且仅有一个项即 。
增广文法 (Augmented Grammar)
在原文法
文法的规范
为了构造文法的规范
其中
是文法 的一个项目集 , 。
操作 | 描述 |
---|---|
1. 一开始 2. 3. 重复规则直至 |
|
即当前输入为 |
SLR(1) 文法
S
指 Simple 。
同时
如前述代表性的文法存在项集
不是 , 文法 。
情况 | 规则 |
---|---|
移进 | |
使用规则 |
|
使用规则 |
yacc
自动生成语法分析器的工具
yacc
指 Yet Another Compiler Compiler 。
bison
则是 yacc 的机能扩展版本 由 , GNU 项目发布 。
一个
1 | /* 定义区块 */ |
在.l
In .l file, this definition must take place before the
#include ".tab.h"
.
1 |
若要使yylval
1 | %union { |
使用%token<>
指定词法单元的类型
1 | %token <double_value> LITERAL |
使用%type<>
指定非终结符的类型
1 | %type <double_value> expr |
追加如下部分以实现错误恢复机制
其中
error
是匹配错误的特殊记号 , CR
指换行符 \n
, yyclearin
丢弃预备读入的词法单元 , yyerrok
通知 yacc 程序已经从错误状态恢复 。
1 | line : ... |
在用户代码区块定义yyerror
1 | int yyerror(const char* str) { |