编译原理（核心速成）

up主：废物点心、致爱意

第一章 绪论

1.编译系统的组成

①词法分析程序
②语法分析程序
③语义分析程序
④中间代码生成
⑤代码优化程序
⑥目标代码生成
⑦符号表管理 / 信息表管理程序
⑧错误检查和处理程序

2.编译过程

第二章 前后文无关文法和语言

1.集合

2.闭包

①正闭包
②自反传递闭包(克林闭包)

3.文法❓

(0)文法G[S] = (V_N, V_T, P ,S)
①V_N：非终结符号集：大写字母
②V_T：终结符号集：小写字母
③P：产生式集
④S：开始符号

3.上下文无关文法 CFG

上下文无关文法 CFG：Context-free Grammar。指的是产生式左边只有一个非终结符字符，它可以自由地被替换为终结符，不需要考虑上下文。

跳转链接：https://blog.csdn.net/Dong_HFUT/article/details/127458798

4.推导和归约

1.自顶向下：推导

最左推导：每个步骤都替换最左侧的非终结符。
最右推导：每个步骤都替换最右侧的非终结符。(最右推导，又称规范推导)

2.自底向上：归约
①最右归约：从最右边终结符开始归约
②最左规约(规范归约)：从最左边的终结符开始归约

5.语法树

子树：任意结点及其全部后继
直接子树：如果一棵子树只有父子两代（两层结点），则称该子树为直接子树

---

例题：最左推导、最右推导、语法树

---

6.二义性文法

二义性文法：句子对应不止一个最左/最右推导(对应不止一棵语法树)

---

例题：二义性文法

答案：

---

7.短语和句柄

---

例题：语法树、最右推导、短语、句柄

答案：

---

8.化简文法

---

例题：化简文法

答案：

---

第3章 词法分析及词法分析程序

1.右线性文法、状态转换图

①右线性文法(正规文法)：左侧是终结符，右侧是空集或非终结符号集
②状态转换图：(仅右线性文法，且无空产生式才有状态转换图)。

---

例题1：状态转换图、产生式

答案：

例题2：

答案：
注意 E 和 F均为终态(接受状态)

例题3：

答案：

(3)先输入任意个b，再输入任意个a，再输入一个b，最后由任意个a,b组成的符号串结尾。

---

2.NFA的确定化和最小化❓

1.确定化（NFA→DFA）

2.最小化（对已经确定好的DFA）

---

例题1：

答案：

例题2：

答案：

例题3：

---

3.正规语言(正规式)❓

---

例题1：

答案：

---

第4章 语法分析和语法分析程序

1.自顶向下的语法分析( LL分析)、自底向上的语法分析(LR分析)

2.消除左递归性

---

例题1：

答案：

---

3.FIRST集 和 FOLLOW集 ❓

---

例题1：

---

LL文法

1.LL(1)文法

1.判断是否为 LL(1)文法

---

例题1：

答案：

---

2.LL(1)分析表 ❓

---

例题1：

---

LR文法

1.LR(0)文法

1.LR(0)项目
①归约项目：A→α· 【·在最右边】
②接受项目：S→α· 【左边是开始符号S】
③移进项目：A→α·xβ 【·在中间，·后面是终结符】
④待约项目：A→α·Xβ 【·在中间，·后面是非终结符】

2.LR(0)文法判断

3.LR(0)文法分析表
①ACTION表 (终结符、＃)：Sn、rn、acc
②GOTO表 (非终结符)：n

---

例题1：

答案：
(1)

(2)

例题2：

答案：

---

2.SLR(1)文法

1.判断

2.分析表

---

例题1：

答案：

---

3.LALR(1)文法

4.LR(1)文法

1.判断
2.分析表

项(item)

第5章 语法制导翻译及中间代码生成

1.逆波兰式 (后缀表达式)

④逻辑运算符中优化级：非 > 与 > 或

---

例题1：

答案：

---

2.四元式

3.将布尔表达式/语句 翻译成 四元式序列

jnz：jump to p, if not zero
jrop：jump to p, if A1 relationship operation A2

例题1：