编译原理（核心速成）
文章目录
- 第一章 绪论
- 1.编译系统由哪些部分组成？
- 第二章 前后文无关文法和语言
- 1.集合
- 2.闭包
- 3.文法❓
- 3.上下文无关文法 CFG
- 4.推导和归约
- 5.语法树
- 6.二义性文法
- 7.短语和句柄
- 8.化简文法
- 第3章 词法分析及词法分析程序
- 1.右线性文法、状态转换图
- 2.NFA的确定化和最小化❓
- 3.正规语言(正规式)❓
- 第4章 语法分析和语法分析程序
- 1.自顶向下的语法分析( LL分析)、自底向上的语法分析(LR分析)
- 2.消除左递归性
- 3.FIRST集 和 FOLLOW集 ❓
- LL文法
- 1.LL(1)文法
- 1.判断是否为 LL(1)文法
- 2.LL(1)分析表 ❓
- LR文法
- 1.LR(0)文法
- 2.SLR(1)文法
- 3.LALR(1)文法
- 4.LR(1)文法
- 第5章 语法制导翻译及中间代码生成
- 1.逆波兰式 (后缀表达式)
- 2.四元式
- 3.将布尔表达式/语句 翻译成 四元式序列
第一章 绪论
1.编译系统由哪些部分组成？
答：①词法分析程序 ②语法分析程序 ③语义分析程序 ④中间代码生成 ⑤代码优化程序 ⑥目标代码生成 ⑦信息表管理程序 ⑧错误检查和处理程序
第二章 前后文无关文法和语言
1.集合
2.闭包
①正闭包
②自反传递闭包(克林闭包)
3.文法❓
(0)文法G[S] = (VN, VT, P ,S)
①VN：非终结符号集：大写字母
②VT：终结符号集：小写字母
③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：
