计算机编译原理课后习题及答案详细解析

在此深情而热烈的感谢沈仲秋同学的大力支持和帮助，同时希望本文档对 各位有些帮助。 一

1、画出编译程序的总体结构图，简述其部分的主要功能。

[答案]

编译程序的总框图见下图。

图 编译程序的总体结构图

其中词法分析器，又称扫描器，它接受输入的源程序，对源程序进行词法分析，识别出一个个的单词符号，其输出结果上单词符号。

语法分析器对单词符号串进行语法分析（根据语法规则进行推导或归纳），识别出程序中的各类语法单位，最终判断输入串是否构成语

语义分析及中间代码产生器，按照语义规则对语法分析器归纳出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的中间

优化器对中间代码进行优化处理。一般最初生成的中间代码执行效率都比较低，因此要做中间代码的优化，其过程实际上是对中间代码

目标代码生成器把中间代码翻译成目标程序。中间代码一般是一种与机器无关的表示形式，只有把它再翻译成与机器硬件相关的机器能

表格管理模块保持一系列的表格，登记源程序的各类信息和编译各阶段的进展状况。编译程序各个阶段所产生的中间结果都记录在表格

出错处理程序对出现在源程序中的错误进行处理。如果源程序有错误，编译程序应设法发现错误，把有关错误信息报告给用户。编译程

2、计算机执行用高级语言编写的程序有哪些途径?它们之间的主要区别是什么?

[答案]

计算机执行用高级语言编写的程序主要途径有两种，即解释与编译。

像Basic之类的语言，属于解释型的高级语言。它们的特点是计算机并不事先对高级语言进行全盘翻译，将其变为机器代码，而是每读总而言之，是边翻译边执行。

像C，Pascal之类的语言，属于编译型的高级语言。它们的特点是计算机事先对高级语言进行全盘翻译，将其全部变为机器代码，再统1.文法G[S]为： S->Ac|aB A->ab B->bc

写出L(G[S])的全部元素。

[答案]

S=>Ac=>abc 或S=>aB=>abc

所以L(G[S])={abc} 2. 文法G[N]为： N->D|ND

D->0|1|2|3|4|5|6|7|8|9 G[N]的语言是什么？ [答案]

G[N]的语言是V+。V={0,1,2,3,4,5,6,7,8,9} N=>ND=>NDD.... =>NDDDD...D=>D......D

3.已知文法G[S]：

S→dAB A→aA|a B→ε|bB

问：相应的正规式是什么？G[S]能否改写成为等价的正规文法？ [答案]

正规式是daa*b*；

相应的正规文法为(由自动机化简来)：

G[S]:S→dA A→a|aB B→aB|a|b|bC C→bC|b 也可为(观察得来):G[S]:S→dA A→a|aA|aB B→bB|ε 4.已知文法G[Z]： Z->aZb|ab 写出L(G[Z])的全部元素。

[答案]

Z=>aZb=>aaZbb=>aaa..Z...bbb=> aaa..ab...bbb L(G[Z])={ab|n>=1}

nn

5.给出语言{abc|n>=1,m>=0}的上下文无关文法。

nn

m

[分析]

本题难度不大，主要是考上下文无关文法的基本概念。上下文无关文法的基本定义是：A->β,A∈Vn，β∈（Vn∪Vt）*，注意关键问题[答案]

构造上下文无关文法如下： S->AB|A A->aAb|ab B->Bc|c [扩展]

凡是诸如此类的题都应按此思路进行，本题可做为一个基本代表。基本思路是这样的：

n

n

m

m

要求符合abc，因为a与b要求个数相等，所以把它们应看作一个整体单元进行，而c做为另一个单位，初步产生式就应写为S->AB，6.写一文法，使其语言是偶正整数集合。 要求：

(1)允许0开头； (2)不允许0开头。

[答案]

(1)允许0开头的偶正整数集合的文法，注意：0E->NT|G|SFM T->NT|G

N->0|1|2|3|4|5|6|7|8|9 D->0|2|4|6|8 G->2|4|6|8 S->NS|ε

F->1||2|3|4|5|6|7|8|9 M->M0|0

(2)不允许0开头的偶正整数集合的文法

不是正数。

E->NT|D T->FT|G

N->D|1|3|5|7|9 D->2|4|6|8 F->N|0 G->D|0

7.已知文法G： E->E+T|E-T|T T->T*F|T/F|F F->(E)|i

试给出下述表达式的推导及语法树 (1)i; (2)i*i+i (3)i+i*i (4)i+(i+i)

[答案]

(1) E=>T=>F=>i

(2)E=>E+T=>T+T=>T*F+T=>F*F+T=>i*F+T=>i*i+T=>i*i+F=>i*i+i (3)E=>E+T=>T+T=>F+T=>i+T=>i+T*F=>i+F*F=>i+i*F=>i+i*i

(4)E=>E+T=>T+T=>F+T=>i+T=>i+F=>i+(E)=>i+(E+T)=>i+(T+T)=>i+(F+T) =>i+(i+T)=>i+(i+F)=>i+(i+i)

8.为句子i+i*i构造两棵语法树，从而证明下述文法G[<表达式>]是二义的。 〈表达式〉->〈表达式〉〈运算符〉〈表达式〉|(〈表达式〉)|i 〈运算符〉->+|-|*|/ [答案]

可为句子i+i*i构造两个不同的最右推导: 最右推导1

〈表达式〉=>〈表达式〉〈运算符〉〈表达式〉 =>〈表达式〉〈运算符〉i =>〈表达式〉* i

=>〈表达式〉〈运算符〉〈表达式〉* i =>〈表达式〉〈运算符〉i * i =>〈表达式〉+ i * i => i + i * i 最右推导2

〈表达式〉=>〈表达式〉〈运算符〉〈表达式〉

=>〈表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式> =>〈表达式〉〈运算符〉〈表达式〉〈运算符〉 i =>〈表达式〉〈运算符〉〈表达式〉 * i => 〈表达式〉〈运算符〉i * i =>〈表达式〉+ i * i => i + i * i

所以，该文法是二义的。 9. 文法G[S]为： S->Ac|aB A->ab B->bc

该文法是否为二义的？为什么？ [答案]

对于串abc (1)S=>Ac=>abc (2)S=>aB=>abc

即存在两不同的最右推导 所以，该文法是二义的。

10.考虑下面上下文无关文法： S->SS*|SS+|a

(1)表明通过此文法如何生成串aa+a*，并为该串构造语法树。 (2) G[S]的语言是什么？ [答案]

(1)此文法生成串aa+a*的最右推导如下: S=>SS*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*

(2)该文法生成的语言是即加法和乘法的逆波兰式,

11. 令文法G[E]为: E->E+T|E-T T->T*F|T/F|F F->(E)|I

证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。 [答案]

此句型对应语法树如右，故为此文法一个句型。

或者：因为存在推导序列: E=>E+T=>E+T*F，所以 E+T*F句型。 此句型相对于E的短语有:E+T*F；相对于T的短语有T*F, 直接短语为：T*F。 句柄为：T*F 。

12.已知文法G[E]:E→ET+|T T→TF* | F F→F^ | a

试证：FF^^*是文法的句型，指出该句型的短语、简单短语和句柄。 [答案]

该句型对应的语法树如下：

该句型相对于E的短语有FF^^*；相对于T的短语有FF^^*,F;相对于F的短语有F^;F^^;简单短语有F;F^;句柄为F. 13.一个上下文无关文法生成句子abbaa的推导树如下： (1)给出串abbaa最左推导、最右推导。 (2)该文法的产生式集合P可能有哪些元素？ (3)找出该句子的所有短语、直接短语、句柄。

[答案]

(1)串abbaa最左推导:

S=>ABS=>aBS=>aSBBS=>aεBBS=>aεbBS=>aεbbS=>aεbbAa=>aεbbaa 最右推导：

S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Aεbbaa=>aεbbaa (2)产生式有：S→ABS |Aa|ε A→a B→SBB|b

(3)该句子的短语有a1b1b2a2a3、a1、b1、b2、b1b2、a2a3、a2； 直接短语有a1、b1、b2、a2； 句柄是a1。

14.给出生成下列语言的上下文无关文法。

nnmm

(1){ abab |n，m>=0}

nmmn

(2){ 10 10| n，m>=0}

rr

(3){WaW|W属于{0|a}*，W表示W的逆}

[答案]

（1）{abab| n，m>=0} S->AA A->aAb|ε

nmmn

(2) { 10 10| n，m>=0} S->1S0|A A->0A1|ε

r

（3）{WaW|W属于{0|a}*，Wr表示W的逆} S->0S0|1S1|ε

15.给出生成下列语言的三型文法。

n

(1){ a|n >=0 }

nm

(2){ ab|n,m>=1 }

nmk

(3) {abc|n,m,k>=0 } [答案]

(1) { an >=0 }的三型文法为： S->aS|ε

nm

(2){ ab|n,m>=1 }的三型文法为： S->aA A->aA|bB B->bB|ε

nmk

n|nn

mm

(3){abc|n,m,k>=0 }的三型文法为:

A->aA|bB|cC|ε B->bB|cC|ε C->cC|ε 16.构造一文法产生任意长的a,b串，使得 |a|<=|b|<=2|a|

其中，“|a|”表示a字符的个数;“|b|”表示b字符的个数。 [分析]

b的个数在a与2a之间，所以应想到形如aSBS和BSaS的形式，B为1到2个b，即可满足条件。 [答案]

如分析中所述，可得文法如下： S-aSBS|BSaS|ε B->bb|b

第1个产生式为递归定义，由于在第2个产生式中B被定义为1或2个b，所以第1个产生式可以保证b的个数在|a|与2|a|之间，而17.下面的文法产生a的个数和b的个数相等的非空a,b串 S->aB|bA B->bS|aBB|b A->aS|bAA|a

其中非终结符B推出b比a的个数多1个的串，A则反之。 说明该文法是二义的。

对上述文法略作修改，使之非二义，并产生同样的语言。 （略做修改的含义是：不增加非终结符。） [答案]

句子aabbab有两种不同的推导。

S=>aB=>aaBB=>aabB=>aabbS=>aabbaB=>aabbab S=>aB=>aaBB=>aabSB=>aabbAB=>aabbaB=>aabbab 即它可以产生两棵不同的语法树，故它是二义的。

修改后的无二义文法如下：

S->aBS|bAS|aB|bA B->aBB|b A->bAA|a 18.给出0，1，2，3型文法的定义。 [答案]

乔姆斯基(chomsky)把文法分成类型，即0型，1型，2型和3型，0型强于1型，1型强于2型，2型强于3型。

如果它的每个产生式α->β的结构是α∈（VnUVt）*且至少含有一个非终结符,而β∈（VnUVt）*，我们说G=（Vt，Vn，S，δ）是一个

0型文法也称短语文法。一个非常重要的理论结果是，0型文法的能力相当于图灵(Tunring)机。或者说，任何0型语言都是递归可枚举如果把0型文法分别加上以下的第i条限制，则我们就得i型文法为： 1．G的任何产生式α->β 均满足|α|<=|β|；仅仅S->ε例外， 但S不得出现在任何产生式的右部。

2．G的任何产生式为A->β，A∈Vn，β∈（VnUVt）* 3．G的任何产生式为A->aB或A->a，其中A，B∈Vn

1型文法也称上下文有关文法。这种文法意味着，对非终结符进行替换时务必考虑上下文，而且，—般不允许替换成空串。 2型文法对非终结符进行替换时无须考虑上下文， 3型文法也称线性文法。

三

1.构造正规式1(0|1)*101相应的DFA。 先构造NFA

确定化

重新命名，令AB为B、AC为C、ABY为D

DFA：

2.将下图确定化：

[答案]

重新命名，令VQ为A、QU为B、VZ为C、V为D、QUZ为E、Z为F。

DFA：

3.把下图最小化：

答案

4.构造一个DFA，它接收Σ={0,1}上所有满足如下条件的字符串： 每个1都有0直接跟在右边。并给出该语言的正规式和正规文法。 [答案]

按题意相应的正规表达式是0*(0 | 10)*0*或

0*( 100*)*0*

构造相应的DFA，首先构造NFA为

用子集法确定化

I I0 I1 S 0 1 {X,0,1,3,Y} {0,1,3,Y} {2} {1,3,Y} DFA：

{0,1,3,Y} {2} 1 2 {0,1,3,Y} {2} 2 2 {1,3,Y} / 3 4 {1,3,Y} {2} 4 4 3 3 / 3

可最小化，终态组为{1,2,4}，非终态组为{3}，

{1,2,4}0 {1,2,4}，{1,2,4}1 {3}， 所以1,2,4为等价状态，可合并。

5．给出下列文法所对应的正规式： S->0A|1B A->1S|1 B->0S|0

[答案]

解方程组S的解：

S=0A|1B A=1S|1 B=0S|0

将A、B产生式的右部代入S中

S=01S|01|10S|10=（01|10）S|（01|10） 所以：S= (01|10)*(01|10)

6.为下边所描述的串写正规式，字母表是 {a,b}. a) 以ab 结尾的所有串

b) 包含偶数个b但不含a的所有串

c) 包含偶数个b且含任意数目a的所有串 d) 只包含一个a的所有串 e) 包含ab子串的所有串 f) 不包含ab子串的所有串 [答案]

注意 正规式不唯一 a) (a|b)*ab b) (bb)*

c) (a*ba*ba*)* d) b*ab*

e) (a|b)*ab(a|b)* f) b*a*

7.请描述下面正规式定义的串. 字母表S = {0，1}. a) 0*(10+)*0*

b) (0|1)*(00|11) (0|1)* c) 1(0|1)*0 [答案]

a) 每个 1 至少有一个 0 跟在后边的串 b) 所有含两个相继的0或两个相继的1的串 c) 必须以 1 开头和0结尾的串

8. 构造有穷自动机.

a) 构造一个DFA，接受字母表??? {0, 1}上的以01 结尾的所有串

b) 构造一个DFA，接受字母表??? {0, 1}上的不包含01 子串的所有串. c) 构造一个NFA，接受字母表??? {x,y}上的正规式x(x|y)*x描述的集合

d) 构造一个NFA，接受字母表??? {a, b}上的正规式(ab|a)*b+描述的集合并将其转换为等价的DFA.以及最小状态DFA [答案]

b)

c)

9. 设有如图所示状态转换图，求其对应的正规表达式。

[答案]

可通过消结法得出正规式

R=(01)*((00|1)(0|1)*|0)

也可通过转换为正则文法，解方程得到正规式。

10. 已知正规式：

(1)((a|b)*|aa)*b； (2)(a|b)*b.

试用有限自动机的等价性证明正规式(1)和(2)是等价的，并给出相应的正规文法。

[分析]

基本思路是对两个正规式，分别经过确定化、最小化、化简为两个最小DFA，如这两个最小DFA一样，也就证明了这两个正规式是等价[答案]

状态转换表1 a 1234 1234 1234 b 124Y 124Y 124Y X124 1234 124Y

状态转换表2 1 2 3 a 2 2 2 B 3 3 3 由于2与3完全一样，将两者合并，即见下表 1 2 a 2 2 b 3 3

而对正规式(2)可画NFA图，如图所示。

X12 12 12Y a 12 12 12 b 12Y 12Y 12Y 可化简得下表 1 2 a 2 2 b 3 3 得DFA图

两图完全一样，故两个自动机完全一样，所以两个正规文法等价。 对相应正规文法,令故为： A->aA|bB|b B->aA|bB|b

即为S->aS|bS|B,此即为所求正规文法。

A对应1，B对应2

四 1.文法

S->a|^|(T) T->T,S|S

(1) 对(a,(a,a)和(((a,a),^,(a)),a)的最左推导。

(2)对文法G改写，然后对每个非终结符写出不带回溯的递归子程序。 (3)经改写后的文法是否为LL（1）的？给出它的预测分析表。 (4)给出输入串(a,a)#的分析过程，并说明该串是否为G的句子。

[答案]

(1) 对(a,(a,a)的最左推导为： S=>(T) =>(T,S) =>(S,S) =>(a,S) =>(a,(T)) =>(a,(T,S)) =>(a,(S,S)) =>(a,(a,S)) =>(a,(a,a))

对(((a,a),^,(a)),a) 的最左推导为： S=>(T) =>(T,S) =>(S,S) =>((T),S) =>((T,S),S) =>((T,S,S),S) =>((S,S,S),S) =>(((T),S,S),S) =>(((T,S),S,S),S) =>(((S,S),S,S),S) =>(((a,S),S,S),S) =>(((a,a),S,S),S) =>(((a,a),^,S),S) =>(((a,a),^,(T)),S) =>(((a,a),^,(S)),S) =>(((a,a),^,(a)),S) =>(((a,a),^,(a)),a) (3)改写文法为： 0) S->a 1) S->^

2) S->( T ) 3) T->S N2 4) N2->, S N2 5) N2->ε

对左部为N2的产生式可知：

FIRST （->, S N2）={，} FIRST （->ε）={ε} FOLLOW N2）={)}（

{，}∩ {)}=? 所以文法是LL(1)的。

可见输入串（a,a）#是文法的句子。

2．已知文法G[A]如下，试用类C或类PASCAL语言写出其递归下降子程序.(主程序不需写) G[A]: A→[B B→X]{A} X→(a|b){a|b} [答案]

不妨约定:在进入一个非终结符号相应的子程序前，已读到一个单词.word：存放当前读到的单词，Getsym()为一子程序，每调用一次，完成读取一单词的工作。error()为出错处理程序.FIRST(A)为终结符A的FIRST集. 类C程序如下：

3．文法：

S->MH|a H->LSo|ε K->dML|ε L->eHf M->K|bLM 判断G是否为LL(1)文法，如果是，构造LL(1)分析表。 [答案]

源文法G展开为： 0） S->M H 1） S->a

2） H->L S o 3） H->ε 4） K->d M L 5） K->ε 6） L->e H f 7） M->K

8） M->b L M

由预测分析表中无多重入口判定文法是LL(1)的。 4．设有文法G[A]的产生式集为:

A→BaC|CbB B→Ac|c C→Bb|b 试消除G[A]的左递归。 [答案]

提示：不妨以A、B、C排序.先将A代入B中，然后消除B中左递归；再将A、B代入C中。再消除C中左递归。 最后结果为:G[A]:

A→BaC|CbB B→CbBcB'|cB' B'→aCcB'|ε C→cB'bC'|bC' C'→bBcB'bC'|ε

五

1、对于文法S ? ( L ) | a L ? L, S | S

(1)给出句子(a, ((a, a), (a, a)))的一个最右推导，并指出右句型的句柄； (2)按照(1)的最右推导，说明移进－归约分析器的工作步骤。 [答案]

(1)S => ( L ) => (L, S) => (L, (L)) => (L, (L, S)) => (L, (L, (L))) => (L, (L, (L, S)))=> (L, (L, (L, a))) => (L, (L, (S, a))) => (L, (L, (a, a))) => (L, (S, (a, a)))=> (L, ((L), (a, a))) => (L, ((L, S), (a, a))) => (L, ((L, a), (a, a))) => (L, ((S, a), (a, a))) => (L, ((a, a), (a, a))) => (S, ((a, a), (a, a))) => (a, ((a, a), (a, a))) (注：句柄下面有下划线) (2)

步骤 1 2 3 4 5 6 7 8 9 # #( #(a #(S #(L 栈 输 入 (a, ((a, a), (a, a)))# a, ((a, a), (a, a)))# , ((a, a), (a, a)))# , ((a, a), (a, a)))# , ((a, a), (a, a)))# ((a, a), (a, a)))# (a, a), (a, a)))# a, a), (a, a)))# , a), (a, a)))# , a), (a, a)))# , a), (a, a)))# a), (a, a)))# ), (a, a)))# ), (a, a)))# , (a, a)))# , (a, a)))# (a, a)))# a, a)))# , a)))# , a)))# , a)))# a)))# )))# 动 作 移进 移进 归约，S?a 归约，L?S 移进 移进 移进 移进 归约，S?a 归约，L?S 移进 移进 归约，S?a 移进 归约，L?S 移进 移进 移进 归约，S?a 归约，L?S 移进 移进 归约，S?a #(L, #(L, ( #(L, (( #(L, ((a 10 #(L, ((S 11 #(L, ((L 12 #(L, ((L, 13 #(L, ((L, a 14 #(L, ((L, S 15 #(L, ((L 16 #(L, ((L) 17 #(L, (S 18 #(L, (L 19 #(L, (L, 20 #(L, (L, ( 21 #(L, (L, (a 22 #(L, (L, (S 23 #(L, (L, (L 24 #(L, (L, (L, 25 #(L, (L, (L, a 26 #(L, (L, (L, S 27 #(L, (L, (L 28 #(L, (L, (L) 29 #(L, (L, S 30 #(L, (L 31 #(L, (L) 32 #(L, S 33 #(L ), (a, a)))# 归约，L?L, S , (a, a)))# 归约，S?(L) )))# 归约，L?L, S )))# 移进 ))# 归约，S?(L) ))# 归约，L?L, S ))# 移进 )# 归约，S?(L) )# 归约，L?L, S )# 移进 34 #(L) 35 #S # 归约，S?(L) # 接受 2、已知文法G[S]为： S?a|^|(T) T?T,S|S (1)计算G[S]的FIRSTVT和LASTVT。

(2)构造G[S]的算符优先关系表并说明G[S]是否未算符优先文法。

(3)计算G[S]的优先函数。

(4)给出输入串(a,a)#和(a,(a,a))#的算符优先分析过程。

[答案]

(1) FIRSTVT和LASTVT

S T FIRSTVT a、^、（ ，、a、^、（ LASTVT a、^、） ，、a、^、) (2) 算符优先关系

a ( ) , ^ # a ≯ ≯ ≯ ( ≮ ≮ ≡ ≮ ) ≯ ≯ ≯ , ≮ ≮ ≯ ≯ ≮ ^ ≯ ≯ ≯ # ≮ ≮ ≮ (3) 对应的算符优先函数为： S T a 2 3 ( 1 3 ) 2 1 , 2 1 ^ 2 3 # 1 1 (4) 句子(a,a)#分析过程如下： 步骤 栈 1 2 3 4 5 # #( #(a #(F #(F, 优先关系 #≮( (≮a a≯, (≮, ,≮a 当前符号 剩余输入串 ( a , , A a,a)# ,a)# a)# a)# )# 移进或归约 移进 移进 归约 移进 移进 6 7 8 9 10 #(F,a #(F,F #(F #(F) #F A≯) ,≯) (≡) )≯# #≡# ) ) ) # # # # # 归约 归约 移进 归约 接受

句子(a, (a, a))分析过程如下：

步骤 栈 优先关系 当剩余输入串 移进或前归约 符号 ( a , , ( a , , a ) ) ) ) ) # # a,(a,a))# , (a,a))# (a,a))# (a,a))# a,a))# ,a))# a))# a))# ))# )# )# )# # # 移进 移进 归约 移进 移进 移进 归约 移进 移进 归约 归约 移进 归约 归约 移进 归约 接受 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 # #( #(a #(F #(F, #(F,( #(F,(a #(F,(F #(F,(F, #(F,(F,a #(F,(F,F #(F,(F #(F,(F) #(F,F #(F #(F) #F #≮( (≮a a≯, (≮, ,≮( (≮a a≯, (≮, ,≮a a≯) ,≯) (≡) )≯) ,≯) (≡) )≯# #≡# ） # 3、对题2的G[S] (1)给出(a,(a,a))和(a,a)的最右推导和规范归约过程。

(2)将(1)和题2中的(4)进行比较给出算符优先归约和规范归约的区别。

[答案]

(1) (a,(a,a))的最右推导过程：

S => ( T ) => (T, S) => (T, (T)) => (T, (T, S)) => (T, (T,a)) => (T, (S, a))=> (T, (a, a)) => (S, (a, a))

(注：句柄下面有下划线)

(a,a))的最右推导过程： S => ( T ) => (T, S) => (T, a) => (S, a)=> (a, (a, a)) (注：句柄下面有下划线)

(2) (a,(a,a))的规范归约过程。 步骤 1 2 3 4 5 6 7 8 9 栈 # #( #(a #(S #(T #(T, #(T, ( #(T, (a #(T, (S 输 入 (a, (a, a))# a, (a, a))# , (a, a))# , (a, a))# , (a, a))# (a, a))# a, a))# , a))# , a))# , a))# a))# ))# ))# ))# )# )# # # # 动 作 移进 移进 归约，S?a 归约，L?S 移进 移进 移进 归约，S?a 归约，T?S 移进 移进 归约，S?a 归约，T?T, S 移进 归约，S?(T) 移进 归约，T?T, S 归约，S?(T) 接受 10 #(T, (T 11 #(T, (T, 12 #(T, (T,a 13 #(T, (T, S 14 #(T, (T 15 #(T, (T) 16 #(T, S 17 #(T, S) 18 #(T) 19 #S (a,a)的规范归约过程。 步骤 1 2 3 栈 # # ( # (a 输 入 (a, a)# a, a)# , a)# 动 作 移进 移进 归约，S?a 4 5 6 7 8 9 #(S #(T #(T, #(T, a #(T, S #(T , a)# , a)# a)# )# )# )# # # 归约，T?S 移进 移进 归约，S?a 归约，T?T, S 移进 归约，S?(T) 接受 10 #(T) 11 # S (2)算符优先文法在归约过程中只考虑终结符之间的优先关系从而确定可归约串，而与非终结符无关，只需知道把当前可归

约串归约为某一个非终结符，不必知道该非终结符的名字是什么，因此去掉了单非终结符的归约。 规范归约的可归约串是句柄，并且必4、有文法G[S]： S?V V?T|ViT T?F|T+F F?)V*|( (1) 给出(+(i(的规范推导。

(2) 指出句型F+Fi(的短语，句柄，素短语。

(3) G[S]是否为OPG？若是，给出(1)中句子的分析过程。 [答案]

(1) S=>V=>ViT=>ViF=>Vi(=>T i(=>T+F i(=>T+( i(=>F+( i(=>(+( i(

(2)句型F+Fi(的语法树：

短语：F，F+F，(，F+Fi( 句柄：F 素短语：(

(3) FIRSTVT和LASTVT S V T F FIRSTVT i,+,),( i,+,),( +,),( ),(, LASTVT i,+,*,( i,+,*,( +,(,* *,( (2)算符优先关系 i + * ( ) #

i + * ( ) # ≯ ≯ ≯ ≯ ≮ ≮ ≮ ≯ ≯ ≯ ≮ ≮ ≯ ≯ ≯ ≯ ≮ ≮ ≮ ≮ ≮ ≮ ≮ ≮ ≯ ≯ ≯ ≯ ≡ 因为该文法是OP，同时任意两个终结符的优先关系唯一，所以该文法为OPG。 (3)(+(i(的分析过程 步栈 优先关当前符剩余输入串 移进或归约 骤 系 号 1 # #≮( ( (+(i(# 移进 2 #( (≯+ + (i(# 归约 3 #F #≮+ + (i(# 移进 4 #F+ +≮( ( i(# 移进 5 #F+( (≯i i (# 归约 6 #F+F +≯i i (# 归约 7 #F #≮i i (# 移进 8 #Fi i≮( ( # 移进 9 #Fi( (≯# # 归约 10 #FiF i≯# # 归约 11 #F #≡# # 接受 5、试为下列各文法建立算符优先关系表。 E->E and T|T T->T or F|F F->not F|N N->(E)|true[答案]

算符优先关系表如下：

true false not and or ( ) # true ≯ ≯ ≯ ≯ false ≯ ≯ ≯ ≯ not ≮ ≮ ≮ ≯ ≯ ≮ ≯ ≯ and ≮ ≮ ≮ ≯ ≯ ≮ ≯ ≯ or ≮ ≮ ≮ ≮ ≯ ≮ ≯ ≯ ( ≮ ≮ ≮ ≮ ≮ ≮ ≡ ) ≯ ≯ ≯ ≯ # ≮ ≮ ≮ ≮ ≮ ≮

六

1、已知文法 :A->aAd| aAb|ε ,判断该文法是否SLR（1）文法，若是构造相应分析表，并对输入串ab#给出分析过程。

[答案] (1)拓广文法

(0)S->A (1) A->aAd (2)A-> aAb (3)A->ε (1)构造识别活前缀的DFA

FOLLOW(A)={d,b,#}

对于状态I0：FOLLOW(A)∩{a}=Ф 对于状态I1：FOLLOW(A)∩{a}=Ф

因为，在DFA中无冲突的现象，所以该文法是SLR(1)文法。 (3)SLR(1)分析表

(4)串ab#的分析过程

步骤 1 2 3 4 5 2、设文法G为 S ? A A ? BA | ε(1)证明它是LR(1)文法；

状态栈 0 02 023 0235 01 符号栈 # #a #aA #aAb #A B ? aB | b

(2)构造它的LR(1)分析表；

(3)给出输入符号串abab的分析过程。

[答案]

(1)拓广文法G’: (0) S' ? S (1) S ? A (2) A ? BA (3) A ?εFIRST(A) = {ε, a, b} FIRST(B) = {a, b} 构造的DFA如下:

(4) B ? aB (

由项目集规范族看出，不存在冲突动作。 ∴该文法是LR(1)文法。

(2)

状态 0 1 2 3 4 5 6 7 Action a S4 S4 S4 r5 r4 B S5 S5 S5 r5 r4 # r3 acc r1 r3 r5 r2 r4 S 1 Goto A 2 6 B 3 3 7 (3)输入串abab的分析过程为： 步骤 状态栈 符号栈 (1) 0 # (2) 04 #a (3) 045 #ab (4) 047 (5) 03 (6) 034 (7) 0345 (8) 0347 (9) 033 (10) 0 336 (11) 0 36 (12) 0 2 (13) 0 1 #aB #B #Ba #Bab #BaB #BB #BBA #BA # A #S 当前字符 剩余字符串 动作 a bab# 移进 b ab# 移进 a b# B?b 归约a a b # # # # # # # b# B?aB 归约b# 移进 # 移进 归约 B?b 归约 B?aB 归约 A?ε 归约 A?BA 归约 A?BA 归约 S?A acc

3、考虑文法S?A S | b A ? S A | a (1)构造文法的LR(0)项目集规范族及相应的DFA。

(2)如果把每一个LR(0)项目看成一个状态，并从每一个形如B ? α·Xβ的状态出发画一条标记为X的箭弧刀状态B ? αX·

(3)构造文法的SLR分析表。

(4)对于输入串bab，给出SLR分析器所作出的动作。 (5)构造文法的LR(1)分析表和LALR分析表。 [答案]

(1)令拓广文法G’为 (0)S’ ? S (1)S ? A S

(2)S ? b (3)A ? S A (4)A ? a

其LR(0)项目集规范族及识别该文法活前缀的DFA如下图所示： FOLLOW(S)={#,a,b} FOLLOW(A)={a,b}

(2)显然，对所得的NFA求ε闭包，即得上面的LR(0)项目集，即DFA中的状态。 故此NFA与(a)中DFA是等价的。 (3)文法的SLR分析表如下：

action A S4 S4 S4 r2 r4 S4/ r3 S4 S4 / r1 b S3 S3 S3 r2 r4 S3/r3 S3 S3 / r1 # acc r2 r4 R1 S 1 6 7 7 6 6 goto A 2 5 2 2 5 5 状态 0 1 2 3 4 5 6 7

因为I5中：FOLLOW（A）∩{a，b}≠Ф ，I7中：FOLLOW（B）∩{a，b}≠Ф 所以，该文法不是SLR（1）文法。 或者：

从分析表中可看出存在歧义，所以该文法不是SLR（1）文法。 (4)对于输入串bab，SLR分析器所作出的动作如下：

步骤 状态栈 (1) 0 (2) 03 (3) 01 (4) 014 (5) 015 (6) 02 (7) 0A2b3 (8) 027 (9) 01

（在第5个动作产生歧义）

(b)LR(1)项目集族为：

I0 : S’ ?·S, # S ?·AS, # | a | b S ?·SA, a | b

I1 : S’ ? S· A ? S·A, a | b

# #b #S #Sa #SA #A #Ab #AS #S 符号栈 当前字符 b a a b b b # # # 剩余字符串 ab# b# b# # # 动作 移进 归约 S?b 移进 归约 A?a 移进 # 归约 A?SA 归约 S?b 归约S?AS 接受 S ?·b, # | a | b A ?·a, a | b

S ?·AS, a | b

A ?·a, a | b S ?·b, a | b

I2 : S ?A·S, # | a | b I3 : S ? b·, # | a | b S ?·b, # | a | b S ?·AS, # | a | b I4 : A ? a·, a | b A ?·SA, a | b A ?·a, a | b

I5 : A ? SA·, a | b I6 : A ? S·

S ? A·S, a | b A ?·SA, a | b

S ? ·AS, a | b A ?·a, a | b S ?·b, a | b S ?·AS, a | b A ?·SA, a | b S ?·b, a | b A ?·a, a | b I7 : S ? AS·, a | b A ? S·A, a | b

A ?·SA, a | b A ?·a, a | b S ?·AS, a | b S ?·b, a | b

∵I6状态集中存在“归约――移进”冲突，故无法构造LR(1)分析表，因而也就无法构造LALR分析表。

4、对下面的文法:S->UTa|Tb T->S|Sc|d U->US|e

判断是否为LR(0),SLR(1),LALR(1),LR(1)，说明理由，并构造相应的分析表。 [答案]（1）拓广文法： (0)S’->S (1)S->UTa (2)S->Tb (3)T->S (4)T->Sc (5)T->d (6)U->US (7)U->e (2)构造识别

LR(0)项目的DFA如下：

因为I1、I8

中存在冲突，所以该文法不是LR（0）文法。

因为FOLLOW(S)={#,c,a,b,d,e},FOLLOW(T)={a,b},FOLLOW(U)={d,e} I1中FOLLOW(T)∩{c}=Ф

I8中FOLLOW(U)∩{c}=Ф,FOLLOW(T)∩{c}=Ф, FOLLOW(T)∩FOLLOW(U)=Ф

I1、I8中冲突解决，所以该文法是SLR（1）文法。

状态 0 1 2 3 4 5 6 7 8 9 10

ACTION a b r3 r3 S9 r5 r5 r4 r4 S10 S9 r3 r3 r2 r2 r1 r1 c S6 S6 r2 r1 d S5 S5 r7 r6 r2 r1 e S4 S4 r7 r6 r2 r1 # acc r2 r1 GOTO S 1 8 T 3 7 U 2 2

S T U

构造识别LR(1)项目的DFA如下：

FIRST e,d e,d e FOLLOW a,b ,d,e,#,c a,b d,e

因为不存在冲突，所以该文法是LR（1）文法。

其中I2、I9可合并，I11、I13可合并，I5、I10可合并，I6、I14可合并， I12、I16可合并，I7、I15可合并，合并后无冲突，所以

状态 0 1 2 ACTION a b r3 C S6 d S5 S10 e S4 S4 # acc GOTO S 1 8 T 3 7 U 2 9 3 4 5 6 7 8 9 10 11 12 13 14 15 16 S12 r3 r5 r4 S16 S11 r5 r4 S13 r3 r5 r2 r1 r4 S13 S14 r2 r1 r7 r6 S10 r2 r1 r7 r6 S4 r2 r1 r2 r1 8 15 9 状态 0 1 2,9 3 4 5,10 6,14 7,15 8 11,13 12,16 a r5 r4 S12,16 r3 b r3 S11,13 r5 r4 S11,13 r3 r2 r1 ACTION c d S5,10 S6 S5,10 r7 S6,14 r6 r2 r2 r1 r1 e S4 S4 r7 r6 r2 r1 # acc r2 r1 S 1 8 GOTO T U 3 2,9 7,15 2,9

七

1、对于输入的表达式(4*7+1)*2，根据下表的语法制导定义建立一棵带注释的分析树。 val:表示非终结符的整数值,综合属性,lexval 是单词 digit 的属性

语法制导定义

产生式 L ?E E ?E语义规则 print(E.val) E.val:=E.val+T.val E.val:=T.val T.val:=T.val*F.val T.val:=F.val F.val:=E.val F.val:=digit.lexval 11+T E ?T 1T ?T*F T ?F F ?(E) F ?digit 1

[答案]

2、 令

S.val为下面的文法由S生成的二进制数的值(如，对于输入101.101，S.val=5.625)；

S→L.L | L L→LB | B B→0 | 1 [答案]

val为综合属性，代表值属性

语法制导定义

产生式 语义规则 S.val:=L.val+L.val/2S.val:=L.val 12L2.length.L2 S?L S?L1 L?L1B L.val:=L.val*2+B.val 1L.length:=L1.length+1 L?B B?0 B?1 L.val:=B.val L.length:=1 B.val:=0 B.val:=1 3、下面文法产生的表达式是对整型和实型常数应用算符+形成的。当两个整数相加时,结果为整数，否则为

E→E+T | T T→num.num | num 给出语法制导定义确定每个子表达式的类型。 [答案]

设type是综合属性，代表各非终结符的“类型”属性

产生式 E?E1语义规则 IF (E.type=integer) and (T.type=integer) THEN E.type:=integer ELSE E.type:=real E.type:=T.type T.type:=real T.type:=integer 1+T E?T T?num.num T?num

4、利用下列文法 E→E+T | T T→num.num | num 把表达式翻译成前缀形式，并且决定类型。试用一元运算符inttoreal[答案]

把整型值转换为相等的实型值，以使得前缀表

为综合属性，代表各非终结符的代码属性

type为综合属性，代表各非终结符的类型属性 inttoreal把整型值转换为相等的实型值 vtochar将数值转换为字符串

语法制导定义

产生式 S->E E?E1+T 语义规则 print E.code IF (E1.type=integer) and (T.type=integer) THEN begin E.type:=integer E.code='+'||E1.code ||T.code; end ELSE begin E.type:=real IF E1.type=integer THEN begin E1.type:=real E1.val:=inttoreal(E1.val) 设code

E1.code=vtochar(E1.val) end IF T.type:=integer THEN begin T.type:=real T.val:=inttoreal(T.val) T.code=vtochar(T.val) end E.code='+'||E1.code||T.code; End E?T E.type:=T.type E.val:=T.val E.code=vtochar(E.val) T?num.num T.type:=real T.val:=num.num.lexval T.code=vtochar(T.val) T.type:=integer T.val:=num.lexva T.code=vtochar(T.val) T?num 5、请按语法制导的定义，将后缀表达式翻译成中缀表达式。注意，不允许出现冗余括号，后续表达式的文法如下： E→EE+ E→EE* E→id [答案]

产生式 S→E E→E1E2+ E→E1E2* 语义规则 print E.code E.code=E1.code||'+'||E2.code; E.op='+' IF E1.op='+' AND E2.op='+' THEN E.code=\1.code||')'||'*'||'('||E2.code||')'; E→id

ELSE IF E1.op='+'THEN E.code=\1.code||')'||'*'||E2.code; ELSE IF E2.op='+'THEN E.code=E1.code||'*'||'('||E2.code||')'; ELSE E.code=E1.code||'*'||E2.code||; E.code:=id.lexeme;

6、有文法： S→(L)|a L→L,S|S

给此文法配上语义动作子程序(或者说为此文法写一个语法制导定义)，它输出配对括号的个数。如对于句子[答案]

拓展文法：加入新开始符号S'和产生式S'→S

设num为综合属性，代表值属性

语法制导定义 产生式 S'→S S→(L) S→a L→L1,S L→S

语义规则 print(S.num) S.num:=L.num+1 S.num:=0 L.num:=L1.num+S.num L.num:=S.num

7、假设变量的说明是由下列文法生成的：

D→i L L→,i L | :T T→integer | real 1）建立一个语法制导定义，把每一个标志符的类型加在符号表中 2）为1）构造一个预翻译程序 [答案]

1)type为综合属性，代表类型属性，

函数addtype实现向符号表中i对应项填类型信息。 语法制导定义 产生式 D→i L L→,i L L→:T T→integer T→real 1语义动作 D.Type:=L.Type addtype(i.entry,D.type) L.Type:=L.Type addtype(i.entry, L.type) L.type:=T.type T.type:=integer T.type:=real 1b) 采用递归下降分析法编写预翻译程序： Procedure D; begin

if lookahead=id then begin

match(id); D.type=L;

addtype(id.entry,D.type) end

else error end Function L: DataType; begin

if lookahead=’,’ then begin

match(‘,’);

if lookahead=id then begin

match(id); L.Type=L;

addtype(id.entry,L.type); return(L.type) end

本文来源：https://www.bwwdw.com/article/pufg.html