大学期末考试复习编译原理.docx

大学期末考试复习编译原理.docx

《大学期末考试复习编译原理.docx》由会员分享，可在线阅读，更多相关《大学期末考试复习编译原理.docx（16页珍藏版）》请在冰点文库上搜索。

大学期末考试复习编译原理

编译程序的工作一般分为五个阶段:

词法分析、语法分析、语义分析与中间代码产生、优化、目标代码产生；

上下文无关文法G是一个四元式：

终结符集合、非终结符集合、文法的开始符号、产生式集合其中：

（VTVN）*且至少含有一个非终结符；（VTVN）*

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

产生式形如：

||||，仅S例外

3型（正规文法，有限自动机）：

AB或A（VT*；A，BVN

产生式形如：

AB或A（VT*；A，BVN）

句型：

S，则称是一个句型；句子：

仅含终结符号的句型；语言：

文法G所产生的句子的全体将语言记为L（G）则：

1、以0开头、以0结尾的所有0和1的串；0（0|1）*

2、第2字符为1的0、1字符串；（0|1）*1（0|1）*

3、含有3个1的0、1字符串；0*10*10*10*

4.不包含子串011的0、1字符串；1*（00*1）*0*

5.不包含子串010的0、1字符串；1*（0|111*）0*

证明：

A*=ε│AA*

L（ε│AA*）=L（ε）∪L（AA*）=L（ε）∪（L（A）L（A*））=L（ε）∪L（A）（L（A）0∪L（A）1∪L（A）2∪...）=L（ε）∪L（A）1∪L（A）2∪L（A）3∪...）=（L（A））*=L（A*）

六．定理：

对每一个右线性正规文法G或左线性正规文法G，都存在一个有限自动机（FA）M，使得L（M）＝L（G）。

右线性文法转化为FA例题：

GR（A）：

A→0|0B|1D

B→0D|1C

C→0|0B|1D

D→0D|1D

将以上右线性文法转化为FA

FA转化为右线性文法例题：

例设DFAM=<{A,B,C,D},{0,1},,A,{B}>。

M的状态转换图如下图所示。

将此DFA转换成对应的右线形文法

A→0|0B|1D

B→0D|1C

C→0|0B|1D

D→0D|1D

例1：

将下面的FA转化为正规式

R=（a|b）*（aa|bb）（a|b）*

例2：

将下面的FA转化为正规式

R=b*a（c|da）*bb*

例3：

将下列正规式转化为FA

a（a|b）*（第三章ppt65页）

a*|（bca*（ab|ba））将以上正规式转化为FA

1.一个上下文无关文法G包括四个组成部分：

一组终结符，一组非终结符，一个（C），以及一组（B）。

A．字符串B．产生式C．开始符号D．文法

2、一个文法所描述的语言是（A），描述一个语言的文法是（B）

A．唯一的B．不唯一的C．可能唯一，也可能不唯一

3．词法分析器的输入是（B）A．单词符号串B．源程序C．语法单位D．目标程序

4．词法分析器的输出结果是（C）A．单词的种别编码B．单词在符号表中的位置C．单词的种别编码和属性值D．单词属性值

5．正规式M1和M2等价是指（C）A．M1和M2的状态数相等B．M1和M2的有向弧条数相等C．M1和M2所识别的语言集相等D．M1和M2状态数和有向弧条数相等

6.文法G：

S→xSx|y所识别的语言是（C）

A．xyxB．（xyx）*c．xnyxn（n≥0）d．x*yx*

七．左递归的消除：

P→Pa|b

P→bB

B→aB|

例文法G（E）:

E→E＋T|T

T→T*F|F

F→（E）|i

经消去直接左递归后变成：

E→TE

E→+TE|

T→FT

T→*FT|

F→（E）|i

八：

令G是一个不含左递归的文法，对G的所有非终结符的每个候选定义它的终结首符集FIRST（）为：

若=>，则规定FIRST（）。

First集是候选式推导出的第一个终结符号或ε

如果非终结符A的所有候选首符集两两不相交，即A的任何两个不同候选i和j

FIRST（i）∩FIRST（j）＝

例如：

S→α|βFirst（S）=First（α）∪First（β）

例如：

S→ABCD

A→a|

B→b|

C→c|

D→d|First（S）={a,b,c,d}

例：

计算下列文法的first集

S→AB|PQx，First（S）={x,d,a}

A→xyFirst（A）={x}

B→bcFirst（B）={b}

P→dP|First（P）={d,}

Q→aQ|First（Q）={a,}

九：

对于文法G的每个非终结符A构造FOLLOW（A）的办法是，连续使用下面的规则，直至每个FOLLOW不再增大为止：

1.对于文法的开始符号S，置＃于FOLLOW（S）中；2.若A→B是一个产生式，则把FIRST（）\{}加至FOLLOW（B）中；3.若A→B是一个产生式，或AB是一个产生式而=>（即FIRST（）），

则把FOLLOW（A）加至FOLLOW（B）中

注意：

1、Follow集合中不能有2、Follow集合是针对非终结符计算的。

例题G:

S→aD

D→STe|

T→bH|H

H→d|

计算First和Follow集，判断是否为LL

（1）文法

First集

Follow集

S

{a}

{#,b,d,e}

D

{a,}

{#,b,d,e}

T

{b,d,}

{e}

H

{d,}

{e}

例：

计算下列文法的所有非终结符的Follow集

S→AB|PQx，Follow（S）={#}

A→xyFollow（A）={b}

B→bcFollow（B）={#}

P→dP|Follow（P）={a,x}

Q→aQ|Follow（Q）={x,}

G[S]:

S→SAe|Ae

A→dAbA|dA|d

将以上文法改写为等价的G’[S]，使之不含左递归和左公因子。

G’[S]:

S→AeS’

S’→AeS’|

A→dA’

A’→AB|

B→bA|

十：

考虑文法G（E）：

ET|E+T

TF|T*F

F（E）|i

和句型i1*i2+i3：

EE+TE+FE+i3T+i3

T*F+i3T*i2+i3F*i2+i3

i1*i2+i3

短语：

i1，i2，i3，i1*i2，i1*i2+i3

直接短语：

i1，i2，i3

句柄：

i1

对于句型：

E+T*F+i

短语：

E+T*F+i、E+T*F、T*F、i

直接短语：

T*F、i

句柄：

T*F

十一：

移进和归约

G（E）：

ET|E+T

TF|T*F

F（E）|i

步骤符号栈输入串动作

0#i*i+i#预备

1#i*i+i#进

2#F*i+i#归，用F→i

3#T*i+i#归，用T→F

4#T*i+i#进

5#T*i+i#进

6#T*F+i#归，用F→i

7#T+i#归，用T→T*F

8#E+i#归，用E→T

9#E+i#进

10#E+i#进

11#E+F#归，用F→i

12#E+T#归，用T→F

13#E#归，用E→E+T

14#E#接受

十二：

假定G是一个不含-产生式的算符文法。

对于任何一对终结符a、b，我们说：

1.a=b当且仅当文法G中含有形如P→…ab…或P→…aQb…的产生式；

2.ab当且仅当G中含有形如P→…Rb…的产生式，而R…a或R…aQ

如果一个算符文法G中的任何终结符对（a，b）至多只满足下述三关系之一：

a=b，a>b，a

FIRSTVT（P）

1.若有产生式P→a…或P→Qa…，则aFIRSTVT（P）；

2.若aFIRSTVT（Q），且有产生式P→Q…，则aFIRSTVT（P）。

LASTVT（P）

1.若有产生式P→…a或P→…aQ，则aLASTVT（P）；

2.若aLASTVT（Q），且有产生式P→…Q，则aLASTVT（P）。

例题：

例:

考虑下面的文法G（E）：

（1）E→E+T|T

（2）T→T*F|F

（3）F→PF|P

（4）P→（E）|i

1.计算文法G的FIRSTVT和LASTVT;2.构造优先关系表;3.G是算符优先文法吗?

例:

构造下列文法的算符优先分析表

S→iBtS|iBtAeS|a

A→iBtAe|a

B→b

Firstvt（S）={i,a}Lastvt（S）={t,e,a}

Firstvt（A）={i,a}Lastvt（A）={e,a}

Firstvt（B）={b}Lastvt（B）={b}

十三：

文法的LR（0）项目集规范族

例：

考虑文法：

S→aAc

A→ABb|Ba

B→b

构造LR（0）项目集规范族。

I0={S→·aAc}

I1=go（I0,a）={S→a·Ac,A→·ABb,

A→·Ba,B→·b}

I2=go（I1,A）={S→aA·c,A→A·Bb,B→·b}

I3=go（I1,B）={A→B·a}

I4=go（I1,b）={B→b·}

I5=go（I2,c）={S→aAc·}

I6=go（I2,B）={A→AB·b}

I4=go（I2,b）={B→b·}

I7=go（I3,a）={A→Ba·}

I8=go（I6,b）={A→ABb·}

例5.11考察下面的拓广文法：

（0）S→E

（1）E→E+T

（2）E→T

（3）T→T*F

（4）T→F

（5）F→（E）

（6）F→i

十四：

后缀式：

逆波兰表示

a*（b+c）写成：

abc+*

将中缀表示x=（a+b）/（c-d）-（a+b*c）转化为逆波兰表示：

xab+cd-/abc*+-=

将逆波兰表示xabc-*bc*de/++=转化为中缀表示

x=a*（b-c）+b*c+d/e

无循环有向图表示：

DAG、抽象语法树

四元式：

考虑如下语句:

whilea

ifc

x:

=y+z

else

x:

=y-z

While A

           If A=1 then C:

=C+1 

                Else while A≤D do A:

=A+2;

100 （j<, A,C,102）

 101 （j , _, _, 115）

 102 （j<,B,D,104）

 103 （j ,_, _, 115）

 104 （j=,A, 1, 106）

 105 （j , _, _, 109） 

106 （+, C, 1, T1）

 107 （:

=, T1,_, C） 

108 （j , _, _, 114） 

109 （j≤,A,D,111）

 110 （j , _, _, 115）

 111 （+, A, 2, T2） 

112 （:

=,T2, _, A）

 113 （j ,_, _, 109） 

114 （j , _, _,100）

 115

给定输入程序For（i=0;i<50;i++）{m=m+j;} 四元式输出为 

 ID          OP         ARG1         ARG2          RESULT 

（1）          =           0            -               i 

（2）   if  i>=50  goto  over 

（3）          +           m            j               T

 （4）          =           T            -               m 

（5）          +           i            1               i 

（6）   goto   

（2）

 （7）   over

四元式为：

1.（=，0，-，i）

2.（ifi<=50gotoover）

3.（+,m,20,T）

4.（=,T,-,m）

5.（-,i,1,i）

6.（goto

（2））

7.Over