编译原理复习知识点
第一章
1.程序语言的分类
机器语言,汇编语言,高级语言。
2.程序翻译的方式
即席翻译:即解释,边解释,边执行;解释器把源代码文件边解释成机器语言边交给CPU执行。
书面翻译:即编译,将源程序翻译成可执行的目标代码,执行可执行程序文件,翻译与执行是分开的。
3.编译程序包含阶段,各阶段功能任务
(1)扫描源程序
将源程序字符拼装成记号
(2)语法分析程序
定义了记号元素及其关系,将记号形成句子,并形成分析树或者语法树。
语法树是对分析树的抽象精简,去掉一些冗余结点,有一定的抽象性。
(3)语义分析程序
理解语句的意思,对数据进行声明和检查,即在语法树上添加属性,形成注释树。
(4)源代码优化程序
对代码进行改进或者优化,与机器无关的优化。
多遍扫描,形成中间代码
中间代码:指一种位于源代码与目标代码之间的代码表示形式,常见的存储结构有:三元组,四元组,树型,伪代码,逆波兰。
(5)代码生成器
代码生成器得到中间代码(IR),并生成目标机器代码
(6)目标代码优化程序
与机器有关的优化,利用机器指令特征进行优化(比如cpu有了位移指令,乘2可以直接用位移指令实现)
第二章
1.正则表达式
(1)几个概念
正则表达式:表示字符串的组成。
正则表达式由它所匹配的串集来定义。
语言:串的集合
串的组合部分:字母表。
空串:不包含任何字符的串
基本正则表达式:字母表中的单个字符且自身匹配(比如L(A)={A})
(2)运算符号
选择
用元字符|表示
连结
由并置表示,不用元字符
重复或闭包
0次或多次重复,由元字符*表示
拓展:正闭包
1次或多次重复,由元字符+表示。
拓展:连字符
字符范围表示,用元字符[]表示,比如[0-9]相当于0|1|2|3|…|9
拓展:可选
表示串是可选的,用元字符?表示,比如(+|-)?
拓展:任意
表示字母表中任意一个符号,用元字符.表示,比如字母表{a,b,c},则.表示a|b|c
拓展:取反
用元字符表示,比如A,表示非A。
(3)运算优先级
闭包(*)>>连结>>选择(|)
2.DFA(确定性有穷自动机)
(1)定义
下一个状态由当前状态和当前输入字符唯一给出的自动机
(2)组成
由字母表,状态集合,转换函数,初始状态,接受状态集合组成。
(3)正则表达式转DFA
3.NFA(非确定性有穷自动机)
(1)与DFA区别
允许空转换。
允许一对多转换。
(2)正则表达式转NFA
4.正则表达式->NFA->DFA->DF最小化(重点)
(1)正则表达式转NFA:
套用3的方法,将表达式拆分成小的部分,逐个转为NFA,最后拼接起来。
比如a(a|b)*
(2)NFA->DFA
(3)DFA最小化
即,将DFA状态分为非终态和终态,对终态的转换进行判断,如果属于同一个集合,则可以合并
(4)词法分析程序生成方法
switch语句
第三章
1.几个概念
(1)推导
用“=>”表示,抽象到具体
(2)规约
推导的反过程
(3)非终结符号集VN
规则中用尖括号括起来的那些符号比如{<句子>,<主语>}
(4)终结符号集VT
组成句子的最基本符号
(5)开始符号/识别符号
语言中的句子只能从它开始推导
(6)规则/产生式
用来产生句子的组成描述
每一条规则都是用‘->’连接起来的有序对a->b
规则右边运算符:选择,并置,括号,没有闭包。
规则右边可以出现空字符。
(7)文法
用来描述语言的文法结构–四元组G=(VN,VT,P,S)
VN:非终结字符集
VT:终结字符集
S:开始符号
P:产生式集,形式为a->b
文法反应句子的构成,正则表达式反应单词的构成。
文法的关键描述在于开始符号和规则。
(8)句型
符号U是从开始符号S推导出来的,既有S=>*U,则称U为句型
‘=>*’:经过0步或者多步推导
‘='0步推导
‘=>’1步推导
‘=>+’1步或多步推导
(9)句子
仅含终结符的句型。
(10)语言
L(G)由文法G所产生的全部句子组成。即:L(G)={W|W属于VT+且S=>+W}
(W由开始符号S经过一步或多步推导,且W必须属于终结符号集VT的正闭包)
2.文法的分类
(1)0型文法
没有对规则a->b两边做限制,仅要求a至少含有一个非终结符。又称为无限制文法/短文法。
(2)1型文法
限制每个规则a->b都要满足|a|<=|b|,|a|表示串a长度,也称为上下文有关文法。
(3)2型文法
每个规则的限制特点为A->b,A为单个非终结符,b属于(VT并VN)*,也称为上下文无关文法。
(4)3型文法
每个规则特点为A->aB或A->a,其中A,B属于VN,a属于VT,都是单个字符,称为正规文法或正则文法。
3.各类文法之间的关系
0型文法包含1型文法包含2型文法包含3型文法
4.二义性
(1)定义
可生成带有两种不同分析树的串的文法称作二义性文法
(2)解决方法
A.设置一个限制规则,该规则在每个二义性情况下指定哪一个是正确的。这样的规则也称为二义性规则。
B.改造文法
例子:
E->E+E|E-E|E*E|E/E|E%E|(E)|n会有二义性
改造文法:
E->E+T|E-T|T
T->T*F|T/F|T%F|F
F->(E)|n
C.重新书写语法规则(BENF)
例子:
exp->exp addop term|term
用BENF改为exp->term {addop term}.{}闭包
if-stmt->if (exp) statement|if (exp) statement else statement
用BENF改为if->stmt->if (exp) statement [else statement].[]可选
第四章
1.自顶向下算法构造过程
每一个非终结符号对应一个分析函数。
(1)左公因子
当两个或更多文法规则共享一个通用前缀串时,提取左公因子。
(2)左递归
A.逐个逐个非终结字符进行解决
例子:A->Aa|b
a.用EBNF解决:A->b{a},
b.将左递归改为右递归:A->bA’ A’->aA’|空
如果有间接递归,才执行B,C。
B.将干净非终结字符代入未解决的非终结字符中,并将其消除干净。
C.重复以上步骤
(3)优化
A.First集合
求出每一条规则的开头非终结符号的所有打头终结符号。
求First集合时,必须先消除文法规则中的左递归和左公因子,否则无意义。
B.Follow集合
若A是开始符号,则Follow(A)=$ ($表示串结束符号)
若B->aAy,则Follow(A)=First(y)-空字符.
若B->aAy,且First(y)中含有空字符,则Follow(A)包含Follow(B)
2.LL(1)分析方法
(1)几个概念
LL(1)分析表一般称为[M,N]
M:即行,是文法的非终结符的集合。
N:即列,是文法的终结符的集合。
M[N,T]:表示非终结符N面临终结符T时该选择的规则
M[N,T]为缺省时,表示在分析中可能出现的错误。
(2)构建步骤
以文法规则:S->Ab|Bc
A-aA|dB
B->c|e为例子
A.消除左递归和左公因子。
B.将经过A得到文法规则中的非终结字符填到行(M)中,终结字符填入到列(N)中。
a | d | c | e | |
---|---|---|---|---|
S | ||||
A | ||||
B |
C.求每条规则的first集合,根据first集合填入相应的位置。比如S->Ab的first集合为{a,d},则在[S,a],[S,d]中填入
S->Ab.
a | d | c | e | |
---|---|---|---|---|
S | S->Ab | S->Ab | ||
A | ||||
B |
全部填完后如下:
a | d | c | e | |
---|---|---|---|---|
S | S->Ab | S->Ab | S->Bc | S->Bc |
A | A->aA | A->dB | ||
B | B->c | B->e |
D.如果某条规则中的first集合有空串,则需要求其Follow集合,根据Follow集合填入相应的位置。比如
S->AbB, A->aA|空,则填规则A->空时,求Follow(A),结果为{b}.则在[A,b]中填入A->空。
a | b | d | e | |
---|---|---|---|---|
S | … | … | … | … |
A | A->aA | A->空 |
(3)EBNF文法与LL(1)文法
EBNF文法满足下列条件,则其等价于LL(1)文法
A.每个产生式A->a1a2a3…an,要满足First(ai)与First(aj)交集为空。
解决方案:不为空,就是出现了左公因子,消除左公因子即可
B.每个产生式A->a1a2a3…an,若First(ai)包含了空字符,要满足First(ai)与Follow(ai)交集为空。
解决方案:不可空,则只能人为控制文法规则来消除错误。
第五章
(1)LR(0)分析
最简单的自底向上分析表
注意事项:开始文法有多条,需要扩展文法。
例子:E->E+n|n,需要扩展为
E’->E
E->E+n|n
具体步骤省略,自己看教学视频
(2)SLR(1)分析
采用LR(0)分析时出现移进和规约冲突时,尝试用SLR(1)分析表。
例子:E->E+n|E
此时,采用SLR(1)分析表,求规约对象的Follow()集合,即Follow(E’)={KaTeX parse error: Expected 'EOF', got '}' at position 1: }̲,E->E.+n的移进符号为+…规约,如果下个符号为+移进,否则出错,解决冲突。
注意:如果Follow()集合和移进集合有交集,采用最长匹配原则。
(3)LR(1)分析
如果某个状态存在A->a,B->b…两个或多个规约,且Follow(A)与Follow(B)有交集,则不能用SLR(1)分析,要用LR(1)分析
例子:
S’->S
S->id|V:=E
V->id
E->V|n
此时,采用LR(1)分析,即超前查看一个字符。
图中第一个状态中S->.id,是由S’->S延申出来的,所以其Follow(S)是求S’->S中S的Follow,所以Follow(S)={$}
图中第一个状态中V->.id,是由S->.V:=E延申出来的,所以其Follow(V)是求S->.V:=E中V的Follow,所以Follow(V)={:=}
第二个状态的超前字符依次类推。
(4)LALR(1)分析
对于LR(1),其分析能力强于LR(0),SLR(1),但状态数也增加了很多。LALR(1)是对LR(1)的一个精简,将可以合并的状态合并,但也有缺点,其发现错误相较于LR(1)会延迟,存在假规约。