编译原理基础知识总结
CH1 编译概述
TODO
CH2 文法和语法的基础知识
TODO:6 文法和语言的分类
0 型文法（无限制文法）
关键在于𝜷可以为空
1 型文法（上下文有关文法）
|
|
2型文法（上下文无关文法）
CH3 词法分析与有穷自动机
词法分析程序的功能
对字符串表示的源程序从左到右进行扫描和分解，根据语言的词法规则识别出一个一个具有独立意义的单词符号。
单词符号及输出单词的形式
词法分析程序的：
- 输入：字符串形式的源程序
- 输出：单词符号 or 单词符号表示的源程序
语言的单词符号 token
语言中具有独立意义的最小语法单位，分为以下 5 种：
关键字
if else while do等标识符,比如变量名、常量名、数组名、函数名等等
常数，比如
- 整型常数 125
- 实型常数 0.718
布尔型常数
TRUE等等
运算符
+ - * / <等等界符
, ; ( ) :等等
一个程序语言的关键字、运算符和界符的个数是确定的，而对于标识符或常数的使用个数通常是不确定的。
词法分析程序输出单词的形式
二元式：
|
|
单词种别
单词种别表示单词的种类，是语法分析需要的信息。
一个语言的单词符号如何划分种类、分成几个种类、怎样编码，取决于处理方便。通常让每种单词对应一个整数码，最大限度地把各个单词区别开。
- 关键字：全体视为一种，但一般一字一种（个数确定）
- 运算符：同关键字
- 界符：同关键字
- 标识符：统归为一种
常数：可按类型（整型、实型、布尔型等等），也可统归为一种，比如
1(+|-|ɛ)dd*(.dd*|ɛ)(e(+|-|ɛ)dd*|ɛ)
单词自身的值
单词自身的值是编译中其他阶段所需要的信息。
用以下方法确定其值：
- 如果一个种别只含一个单词符号，那么对于这个单词符号，种别编码完全代表其自身的值。
如果一个种别又多个单词符号，那么对于它的每个单词符号，除了给出种别编码之外，还应
给出单词符号的自身值，以便把同一种类的单词区分开来。
标识符的自身值：标识符自身的字符串
常数自身值：常数本身的二进制数值
用指向某类表格中一个特定项目的指针值来区分同类中不同单词
标识符：在符号表的入口指针作为它自身的值
常数：在常数表的入口指针作为自身值
假设关键字、运算符和界符都是一符一种，标识符自身的值用自身的字符串表示，常数自身的值用标准二进制形式表示，则程序段if (a > 1) b = 100;在经词法分析程序扫描后，它所输出的单词符号串是：
| 二元式 | 表示的意义 |
|---|---|
| (2, ) | 基本字if |
| (29, ) | 左括号( |
| (10, ‘a’) | 标识符a |
| (11, ‘1’的二进制) | 常数1 |
| (30, ) | 右括号) |
| (10, ‘b’) | 标识符b |
| (17, ) | 赋值号= |
| (11, ‘100’的二进制) | 常数100 |
| (26, ) | 分号; |
其中，假设标识符种类编码为整数 10，常数的种类编码为整数 11，基本字if种类编码为 2，赋值号种类编码为……
语言单词符号的两种定义方式
- 正规文法
- 正规式
TODO
CH4 语法分析
文法的左递归性和回溯的消除
在自上而下分析过程中，为了避免回溯，即要求描述语言的文法是 LL(1) 文法。
LL(1) 文法的判断条件
1
设 𝜶
TBC
预测分析法与预测分析表的构造
方法
- 计算文法 G 的每一非终结符的 FIRST 集和 FOLLOW 集。
- 对文法的每个规则 𝑨⟶𝛼，若a ∈ FIRST(𝛼)，则置 M[A, a] = 𝑨⟶𝛼，显然其中 a 是终结符。
- 若 𝜺 ∈ FIRST(𝛼)，则 ∀ b ∈ FOLLOW(A)，则置 M
