编译原理：全片知识难点总结

您所在的位置：网站首页 › 编译原理好难学怎么办 › 编译原理：全片知识难点总结

编译原理：全片知识难点总结

2024-07-12 07:57| 来源: 网络整理| 查看: 265

一、概念

二、词法分析

三。自上而下分析语法——LL语法

1）消除左递归

2) 消除回溯、提左因子、 FIRST集和 FOLLOW 集

3）预测分析法与 FIRST集和 FOLLOW 集的构建。

4)预测分析法中预测分析表M的构建

四、自下而上的分析语法——算符优先分析法

1）对每个非终结符构建FIRSTVT 集和LASTVT 集

2）构造算符优先关系表

五、语义分析

1）赋值语句和的简单算数运算表达式的翻译

2)布尔表达式的翻译方法

3)典型控制语句的翻译方法

六、目标代码生成

1）基本块划分

2）寄存器选择——寄存器的待用信息与活跃信息的确定

七、中间代码的优化

(1) 基于DAG图的优化方法

一、概念

1）字母表、字符串、字符串和运算

字母表用 Σ 表示，是字符的非空有穷集合，字符是字母表Σ的元素字符串，是字母表Σ中字符组成的有穷序列，其长度用 || 表示。空串用是ε表示， |ε| = 0Σ* 指包括空串在内的Σ上所有字符串的集合。称之为字母表的闭包。字符串的方幂：例如 $a^{n} = a^{n-1}a$ ，指连续n个a字符对于集合A的正则闭包 + $A^{+} =A^{1} \bigcup A^{2} \bigcup A^{3} .... \bigcup A^{n}$ 对于集合A的闭包 * , $A^{*} =A^{0} \bigcup A^{1} \bigcup A^{2} \bigcup A^{3} .... \bigcup A^{n}$

文法分类分为0型文法，1型文法，2型文法，3型文法，分别又称为短语文法，上下文有关文法，上下文无关文法，正规文法。

0型文法，短语文法：每个产生式 α ->β 左部α中至少又一个非终结符1型文法，上下文有关文法：在0型文法的基础上，还满足 |α| β ,其中A 是非终结符， β是终结符和非终结符的闭包。3型文法：每个产生式 A->αB 或 A ->α 的形式，其中A和B 是非终结符，α是终结符

四元式：是 ( op ,arg1,arg2,result) 形式的一个对象，其中op 表示中间代码的操作符，result 表示运算结果的临时变量。

后缀式、逆波兰式：在抽象语法树中的后续遍历得到的式子。例如a+b(中序)改写成后缀式为ab+

二、词法分析

单词分为关键字、算符、标识符、常数、介符。词法分析的目标是为了将代码分解成对应的单词，并对单词打上些有意义的编码，给后续的语法分析和语义分析使用。

单词

编码

单词

编码

单词

编码

单词

编码

end

（

begin

program

）

bool

real

标识符

，

integer

整数

not

实数

；

对代码进行按行读取，判断每个单词是否属于关键字，或者介词、标识符还是标识符等。大致方式

为：按行读取，逐各读取字符并将每个字符假如一个字符缓存变量中，读取的字符如果是空格、换行、或者介词、运算符（对应表格代码是21~37）的话，则缓存变量中是一个完整的单词。对着单词表对单词打上编码，如果不存在则为标识符..

三。自上而下分析语法——LL语法 1）消除左递归

对于类似的产生式 “ A ->Aα | β ”都可以化简成

A -> βA'

A' -> αA' | ε

实际上对于产生式 $A - A \alpha _{1} | A \alpha _{2} |...| A \alpha _{n} |\beta _{1}|\beta _{2}|...|\beta _{n}$ 都可以化简成

$A - \beta _{1}A'|\beta _{2}A'|...|\beta _{n}A'$ 和

$A' - \alpha _{1}A' | \alpha _{2}A' |...| \alpha _{n }A' |\varepsilon$

2) 消除回溯、提左因子、 FIRST集和 FOLLOW 集

对所有非终结符的A的每个候选是α，定义其终结首符集，FIRST

$FIRST(A) = \{ a | A= a....., a\epsilon V_{T} \}$

对所有非终结符的A的每个候选是α，定义其后随符号集，FOLLOW

$FOLLOW(A) = \{ a | A =* ....Ba...., a\epsilon V_{T} \}$

3）预测分析法与 FIRST集和 FOLLOW 集的构建。

统计每个非终结符的 FIRST 和FOLLOW 集，并构建预测分析表。

例如：对应文法G[E]：

E → E + T | T

T → T * F | F

F →( E ) | i

现有输入串 i *(i + i) ，判断其语法是否正确？

首先先消除左递归，得到新文法如下

E → T E' .....①

E' → + T E' | ε .....②

T → F T' ....③

T' →*FT' |ε ....④

F →( E ) | i .....⑤

因此，有非终结符 E, E',T, T', F.构建FIRST集的过程为

自下而上遍历对应的产生式，把产生式右边的首终结符加入到产生式左边的FIRST中因此

FIRST(F) = { ( , i ...} FIRST(T') = { * , ε ...} FIRST(E’) = { + , ε ....}

对于 A →B....类似的文法应该把 FIRST(B) 也加入到 FIRST(A)中因此

FIRST(F) = { ( , i } FIRST(T') = { * , ε} FIRST(E‘) = { + , ε}

FIRST(T) ={ ( , i } FIRST (E) ={ ( , i }

构建FOLLOW集的过程为:自上而下遍历对应的产生式形如 S → ABC，

把FIRST(C) / {ε}加入到FOLLOW(B)中，如果C是终结符，那么终结符的FIRST集就是它自身，即FIRST(C) ={ C }，把 FOLLOW(S)加入到 FOLLOW(C)中，如果C 可以间接推出 ε ，即ε∈ FIRST(C),那么把 FOLLOW(S)也加入到FOLLOW(B)中，往起始产生式的FOLLOW加入 ‘#’ 起始符。

因此上述文法的

FOLLOW (E) = { # , ) } ....（第3个条件、⑤式匹配第一条件）

FOLLOW(E') = FOLLOW(E) = { # , ) } (①式匹配第4个条件)

FOLLOW(T) =FIRST(E')/{ε} ∪ FOLLOW(E) ={ + ，），# } （②式匹配第一条件，①式匹配第二条件）

同理：

FOLLOW (T' ) = FOLLOW(T) = { + ，），# }

FOLLOW(F) = FIRST(T')/{ε} ∪ FOLLOW(T) ∪ FOLLOW(T')={ * , + ，），#}

4)预测分析法中预测分析表M的构建遍历每个产生式 A ->α，对每个终结符 a ∈ FIRST(A) , 将 A->α 加入到 M[A,a]中，如果 ε ∈ FIRST(A)，则对任何终结符b ∈ FOLLOW(A），将 A->ε 加入到 M[A,B]中

因此，预测分析表如下:

i+*()#EE → T E'E → T E'E'E' → + T E'E' →εE' →εTT → F T'T → F T'T'T' →εT' →*FT'T' →εT' →εFi F →( E )

语法分析过程：

分析栈的起始状态为 # ，如果分析栈的输入串的待匹配字符和分析栈顶元素按照预测分析表进行化简，如果栈顶和待匹配字符一致则匹配，如果都不满足则输入串语法错误。

步骤分析栈输入串备注1#Ei *(i + i)#E → T E'2#E'Ti *(i + i)#T → F T'3#E'T'Fi *(i + i)#F →i 4#E'T'ii *(i + i)#匹配5#E'T'*(i + i)#T' →*FT'6#E'T'F**(i + i)#匹配7#E'T'F(i + i)#F →( E )8#E'T')E((i + i)#匹配9#E'T')Ei + i)#E → T E'10#E'T')E'Ti + i)#T → F T'11#E'T')E'T'Fi + i)#F →i 12#E'T')E'T'ii + i)#匹配13#E'T')E'T'+ i)#T' →ε14#E'T')E'+ i)#E' → + T E'15#E'T')E'T++ i)#匹配16#E'T')E'Ti)#T → F T'17#E'T')E'T'Fi)#F →i 18#E'T')E'T'ii)#匹配19#E'T')E'T')#T' →ε17#E'T')E')#E' →ε18#E'T'))#匹配16#E'T'#T' →ε17#E'#E' →ε18##匹配19语法正确

四、自下而上的分析语法——算符优先分析法

对于一个文法，如果其每个产生式的右部都不含两个相邻的非终结符，形如：S->.....QR....，则为算符文法。

假如G 是一个不含 ε 的算符文法

a =· b : 当且仅当文法G含有 S -> ...ab... 或 S -> ...aQb...

a ...aQ... 且 Q ->b... 或 Q ->Rb

a >· b : 当且仅当文法G含有 S -> ...Qb... 且 Q ->...s 或 Q ->....aR

当一个算符文法的任意终结符(a,b) 最多只满足a =· b，a · b 关系之一，则该文法为算符优先文法。也就是说，任意一对终结符，最多只有一种优先关系成立。

例如、对于文法

E' -> #E# .......①

E -> E+T |T ........②

T -> T * F | F ........③

F->P ↑ F | P .........④

P -> (E) | i ...........⑤

用算法优先分析输入串为 ( i+i )*i

1）对每个非终结符构建FIRSTVT 集和LASTVT 集

FIRSTVT(P) 和 LASTVT (P)表示非终结符P可推出产生式的第一个终结符和最后一个终结符集合

FIRSTVT (P ) = { a | P => a... 或 P => Qa.... ，a ∈ 终结符， Q∈非终结符}

LASTVT (P ) = { a | P => ....a 或 P =>.....aQ ，a ∈ 终结符， Q∈非终结符}

因此可以自下而上的用下面的规则构造FIRSTVT，

若有产生式 P->a. 或 P -> Qa.... ，则 a∈FIRSTVT (P ) 若有 a∈FIRSTVT (Q) 且有产生式 P-> Q... 则，a∈FIRSTVT (P )

同理，可以自下而上的用下面的规则构造LASTVT，

若有产生式 P->....a 或 P ->.....aQ ，则 a∈LASTVT (P ) 若有 a∈LASTVT (Q) 且有产生式 P-> ....Q 则，a∈LASTVT(P )

FIRSTVT (P) = { (,i } LASTVT(P') ={ ),i}

FIRSTVT (F) = {↑,(, i} LASTVT(F) = {↑, ),i}

FIRSTVT (T) = {*,↑,(, i} LASTVT (T) = {*,↑,), i}

FIRSTVT (E) = {+,*,↑,(, i} LASTVT (E) = {+,*,↑,), i}

FIRSTCT (E') = {#} LASTVT (E') = {#}

2）构造算符优先关系表

形如有产生式 ....aP.....,那么对任何 b ∈ FIRSTVT(P) ,都有 a · b

遍历每个产生式因此算符优先关系表如下

+*↑i()#+>···>··>·>·>·>·(·# id E.place = Entry(id) 2)布尔表达式的翻译方法

注:rel_op为布尔运算符

产生式语义动作 E -> E1 or ME2

{backpatch(E1.false, M.quad) ;

E.true := merge(E1.true , E2.true);

E.false := E2.false}

E -> E1 and ME2

{backpatch(E1.true, M.quad) ;

E.true := E2.true ;

E.false := merge(E1.false,E2.false)}

E -> not E1

E.true := E1.false ; E.false := E1.true ;

E-> ( E1 )

E.true :=E1.true ; E.false :=E.1false

E-> id rel_op id

{E.true :=nextquad ; E.false := nextquad+1 ；

Gen( "j " , id1.place , id2.place ,0 );

Gen("j" ,"_" ,"_",0);

}

E -> id

{E.true :=nexquad ; E.false := nexquad+1 ；

Gen( "jnz" , id1.place , "_" ,0 );

Gen("j" ,"_" ,"_",0);

}

M ->εM.xq =nextquad

例如：布尔表达式 “ aε ,此时nextquad下一个四元式编号是104，再接下来发生规约是E ->e < f

104 :("j" ,a,0,102)

101: (" j " ,_,_,0)

102:(" j" ,a,0,110)

107:(" j " ,_,_,108)

108:(" j

【本文地址】

公司简介

联系我们