编译原理期末复习

绪论

流程：词法分析 语法分析 语义分析 中间代码生成 代码优化 目标代码生成

语言和文法基础

上下无关文法（2型文法）：G=（VT,VN ,S,P）

句子：看产生式右边，只有终结符的才是

句型：看产生式右边，可以包含终结符，也可以包含非终结符，句子是句型的一种

语言：文法生成的句子的集合

*：表示>=0

+: 表示>=1

最左推导：每次对最左的非终结符替换

最右推导：每次对最右的非终结符开始替换

短语 ：

二义性：文法中某个句子对应两棵不同的语法树

​ 或者一个句子存在多个不同最左（最右）推导

0 型: 非限制文法

1 型: 上下文有关文法

3 型: 正则文法

闭包 ：

词法分析

功能：输入源程序、输出单词符号

正则文法转正则表达式：

右线性文法：

左线性文法：

FA（有限自动机）:包含DFA和NFA,

DFA:

例题：

NFA:

DFA NFA区别：

正规式转DFA M

语法分析

消除左递归：

消除回溯：

First集：（看产生式左边，然后看右边第一个是否为终结符，不为继续找）

FOLLOW集：

select集：

求LR(0)

算符优先文法：

FIRSTVT()：看产生式右边，从左往右找到第一个终结符

LASTVT(): 看产生式右边，从右往左找到第一个终结符

后续参考（图片也来着）：B站