【编译原理】期末考试准备
编译系统组成
词法分析程序、语法分析程序、语义分析程序、中间代码生成、代码优化程序、目标代码生成、信息表管理程序、错误检查和处理程序
chomsky文法体系
-
0型文法：短语结构文法或无限制文法，其描述能力相当于图灵机，可使用任何的语法描述形式
-
1型文法：上下文有关文法 CSG
-
xSy -> xAy。S推导出A是和上下文x, y相关的，即S只有在上下文x, y的环境中才能推导出A
-
-
2型文法：上下文无关文法 CFG
-
S -> A。S可以无条件的推导出A，和上下文无关
-
-
3型文法：正则文法 RG
-
S -> Aa。其中最后一个a必须为非终结符
-
NFA
1. 识别同一个字符，到达的下一个状态不确定；能识别空串
2. 走错了就要回溯，效率低；符合人的思维，用起来很快，可以借助NFA构造DFA。
DFA
1. 识别同一个字符，到达的下一个状态是确定的；空串的移动严令禁止
2. 每一步是确定的，效率高
RE -> NFA Thompson构造法
NFA -> DFA 子集构造法
RE -> DFA 直接构造法
example