编译原理知识点.docx

编译原理知识点.docx

《编译原理知识点.docx》由会员分享，可在线阅读，更多相关《编译原理知识点.docx（11页珍藏版）》请在冰点文库上搜索。

编译原理知识点

1.解释程序：

不生成目的代码

编译程序：

生成目的代码

2.编译程序构成：

8个

分析<前端>：

（词法分析程序、语法分析程序、语义分析程序、中间代码生成程序）

综合<后端>：

（代码优化程序、目的代码生成程序）

贯穿始末：

表格管理程序、出错解决程序

3.文法四元组：

终结符号集合Vt、非终结符号集合Vn、产生式集合P、辨认符号（开始符号）S

VT∩VN＝Φ

文法->语言（推导、规约）唯一；语言->文法（凑规则）不唯一。

4.文法分类：

0型文法（短语构造文法）：

左侧至少具有一种非终结符

1型文法（上下文关于文法）：

左侧长度<=右侧长度S->ε除外，S不能出当前右侧

2型文法（上下文无关文法）：

左侧只能有一种非终结符（语法分析）

3型文法（正规文法）：

A->aBA->a右线性；（词法分析）

A->Ba或A->a左线性（看非终结符位置）

5.A*＝A0∪A+A0＝{ε}!

={}＝Φ空集

A+＝AA*＝A*A

6.句型：

符号串x是从辨认符号S推导出来，x称为一种句型

句子：

x仅由终结符号构成，仅含终结符号句型是一种句子

短语：

子树末端（叶子）从左至右连成串（涉及整棵语法树）

简朴子树：

只具有单层分枝子树

直接短语（简朴短语）：

由简朴子树叶子构成

句柄：

最左边直接短语（不一定含终结符）

素短语：

至少具有一种终结符短语，并且除它自身之外不再含任何更小素短语

最左素短语：

最左边素短语

短语：

P（相对于T、E）、P+T（相对于E）、i（相对于P、F）、P+T+i（相对于E）

直接短语：

P、i句柄：

P（最左边直接短语）

素短语：

P+T、i（至少具有一种终结符短语）最左素短语：

P+T

7.二义性文法：

有两个不同最左推导或有两个不同最右推导或能产生两棵语法树

8.文法产生式正规式

规则1A→xBB→yA=xy

规则2A→xA|yA=x*y右线性

A→Ax|yA=yx*左线性

规则3A→xA→yA=x|y

9.DFA初态唯一，转换函数为单值映射

表达方式：

转移矩阵、状态转换图

状态转换图上若存在一条从初态到某一终态道路，且这条路上所有弧标记符连成字符串为t，则称t被DFA接受。

10.NFA初态可为各种，转换函数为多值映射

拟定化：

与某一NFA等价DFA不唯一

1.状态集合Iε-闭包

2.move函数

最小化：

消除多余状态和合并等价状态

多余状态：

从自动机开始状态出发，任何输入串也不能到达那个状态；或者从这个状态没有通路到达终态。

11.左公因子

显式左公因子提取

若A→αβ1|αr，则将其改写为：

i.A→α（β1|r）

ii.或引入新非终结符A→αA’A’→β1|r

隐式左公因子:

产生式右部以非终结符开始

用该非终结符右部以终结符开始产生式去替代它，再提取

S→aSd|AcA→aS|b

把A产生式代入S中：

S→aSd|aSc|bc

S→aSS’S’→d|cS→bc

12.左递归

1.简朴左递归：

消除左递归改写为右递归

A→Aα|β

A→βA’

A’→αA’|ε

2.间接左递归

非终结符号排序（浮现频率高排背面）

左部非终结符下标>右部时改写（替代右部）

消除直接左递归

13.自顶向下：

LL

（1）

FIRST：

A→X1X2X3…Xn

若X1⇒εX2⇒εX3!

⇒ε背面不用管

则FIRST（A）=First（X1）-{ε}UFirst（X2）-{ε}First（X3）

若全能推出ε则先求所有FIRIST（X）-{ε}并集再并上{ε}

FOLLOW：

•（a）设S为开始符号，则#∈FOLLOW（S）

•（b）若有产生式A→αBβ，β!

⇒*ε，则FIRST（β）加至FOLLOW（B）

•（c）若β⇒*ε（即ε∈FIRST（β）），则FIRST（β）-{ε}和FOLLOW（A）加至FOLLOW（B）

SELECT：

A→α可选集SELECT

*α!

⇒ε，则SELECT（A→α）=FIRST（α）

*α⇒ε，则SELECT（A→α）=FIRST（α）-{ε}∪FOLLOW（A）

一种上下文无关文法G是LL

（1）文法充要条件是：

对于G每个非终结符号A任何两个不同产生式A→α，A→β满足：

▪SELECT（A→α）∩SELECT（A→β）=∅

▪α、β不同步推导出ε

LL

（1）含义：

第一种L：

从左到右扫描输入串

第二个L：

分析过程中用最左推导

1：

只需向右看1个输入符号（Lookahead）便可拟定选用哪个产生式进行推导

–LL

（1）文法是无二义。

–LL

（1）文法不含左递归。

14.自底向上：

算符优先、LR（0）、SLR

（1）、LR

（1）、LALR

（1）

15.规范归约：

最右推导逆过程（最左归约）

•最右推导是规范推导右句型（最右推导可得句型）是规范句型

•规范句型特点：

句柄后（右边）不会浮现非终结符

•规范归约中心问题是：

如何寻找或拟定一种句型句柄 。

•可归约串：

•最左素短语（算符优先分析法）

•句柄（LR分析法）

算符优先分析法不是规范归约办法。

16.若文法G中不存在右部具有相邻非终结符产生式，则G为算符文法

算符优先分析可归约串是句型最左素短语。

起决定作用是相邻两个终结符优先关系

a≡b当且仅当G中存在产生式规则A→…ab…，或A→…aBb…

a<⋅b当且仅当G中存在产生式规则A→…aB…，且B⇒+b…或B⇒+Cb…

a⋅>b当且仅当G中存在产生式规则A→…Bb…，且B⇒+…a或B⇒+…aC

不容许有a<·b、a≡b、a·>b中两种关系同步存在

17.FIRSTVT计算如下：

若有产生式A→a…或A→Ba…

则a∈FIRSTVT（A）A左侧终结符

若a∈FIRSTVT（B）且有产生式A→B…（B背面没有紧跟一种终结符）

则a∈FIRSTVT（A）

A->a.......，即以终结符开头，该终结符入Firstvt

A->B.......，即以非终结符开头，该非终结符Firstvt入AFirstvt

A->Ba.....，即先以非终结符开头，紧跟终结符，则终结符入Firstvt

LASTVT计算如下：

若有产生式A→…a或A→…aB

则a∈LASTVT（A）A右侧终结符

若a∈LASTVT（B）且有产生式A→…B

则a∈LASTVT（A）

A->.......a，即以终结符结尾，该终结符入Lastvt

A->.......B，即以非终结符结尾，该非终结符Lastvt入ALastvt

A->.....aB，即先以非终结符结尾，前面是终结符，则终结符入Lastvt

18.LR分析法归约过程是规范推导逆过程，因此LR分析过程是一种规范归约过程

无回溯“移进-归约”办法

符号栈中符号是规范句型前缀，且不含句柄后来任何符号（活前缀）

ACTION移进归约接受出错

ACTION[i,a]=空白出错

ACTION[i,a]=acc符号栈中仅有#和文法开始符号S，输入串仅为#，分析结束。

19.一种句型某个前缀后缀是该句型句柄，则这个前缀称为该句型可归前缀。

一种规范句型一种前缀，若不含句柄之后任何符号，则称它为该句型一种活前缀。

S->aAc.Be项目中.之前aAc为活前缀

20.A→α⋅aβ,a∈VT移进项目

A→α⋅Bβ,B∈VN待归约项目

A→α⋅归约项目

特别地：

A→ε只有A→⋅

S’→S，S’→S⋅接受项目

以上项目称作LR（0）项目。

21.LR（0）项目集规范族（辨认G活前缀DFA）

如果不存在移进-归约冲突，归约-归约冲突，则称它是LR（0）文法。

拓展文法目：

使文法只有一种以辨认符号作为左部产生式，从而使构造出来分析器有唯一接受状态。

22.对给定文法，运用LR（0）办法判断符号串与否为该文法句子：

1.扩充文法为拓广文法；

2.构造辨认此文法所有活前缀DFA，即构造LR（0）项目集规范族；

3.判断与否为LR（0）文法；

4.是构造LR（0）分析表运用LR分析算法分析符号串。

5.否，做其她解决。

23.SLR

（1）对所有非终结符都求出其FOLLOW集合

发生冲突时，归约项目左部终结符FOLLOW集与移进项目.后终结符交集为空时，才干按此规约项目产生式进行归约。

–LR（0）分析对所有终结符均采用归约动作

–SLR

（1）分析参照FOLLOW集，以拟定归约动作。

24.Follow集无法解决移进-归约冲突或归约-归约冲突，考虑后继符

25.归约动作选取：

a）LR（0）分析考虑所有终结符

b）SLR

（1）分析参照FOLLOW集，为了拟定归约

c）LR

（1）分析仅考虑LR

（1）项目中后继符（归约展望集，向前搜索符）

拓展文法后继符为#，即[S’->S，#]为初态集初始项目，S后first（ε，#）={#}

LR

（1）项目集规范族中，每个状态中添加新产生式时，需求产生式左部字母背面First集作为新产生式后继符;否则后继符照抄前一种状态

I：

A->a.BβB->.e，需求出First（β）作为B->.e后继符

26.任何二义文法决不是一种LR文法

LL（k）文法都是LR（k）文法。

27.a=b*c+b*d逆波兰式：

abc*bd*+=（算符优先一种应用）

无括号；运算对象顺序不变；运算符号位置反映运算顺序。

◆三元式运算成果用三元式编号表达

b*c（*，b，c）

◆四元式运算成果用暂时变量表达

b*c（*，b，c，t）

a:

=b*c+b*d三元式表达a:

=b*c+b*d四元式表达

注意最后一步写法

四元式直观写法：

t1:

=b*ct2:

=b*dt3:

=t1+t2a:

=t3

中间代码优化解决时，四元式比三元式以便多

28.终结符只有综合属性，由词法程序提供；非终结符可有综合也可有继承属性，但文法开始符号无继承属性。

29.按优化所涉及程序范畴可分为三种级别：

局部优化、循环优化、全局优化。

局部优化指在只有一种入口一种出口基本块内进行优化。

30.鉴定入口语句规则：

（a）代码序列第1个语句。

（b）条件或无条件转移语句转移目的语句。

If…gotoGoto

（c）紧跟在无条件转移语句或条件转移语句背面语句。

例：

B1->

（1）readx

（2）ready

B2->（3）r:

=xmody

（4）ifr=0goto（8）

B3->（5）x:

=y

（6）y:

=r

（7）goto（3）

B4->（8）writey

（9）halt

基本块i和基本块j满足如下条件之一,则从i引一条有向边到j。

1.j紧跟在i之后,且i出口语句不是goto或停语句，可以是ifgotoS语句如B2到B3

2.i出口语句是gotoS语句或“[if]gotoS”语句,而S是j入口语句，i是j前驱结点。