编译原理复习题-给学生（简）

《编译原理》复习题

51．写出C语言标识符集（字母或下划线开头的由字母、数字、下划线构成的串）的正规式。 解答：用D表示数字0-9，用L表示字母a-z|A-Z，则C语言标识符的正规式为：

（L|_）（L|D|_）*

52．有一语法制导定义如下，其中+表示符号连接运算：

S→B print B.vers B→a B.vers=a B→b B.vers=b

B→Ba B.vers=a+B.vers B→Bb B.vers=b+B.vers

若输入序列为abab，且采用自底向上的分析方法，则输出序列为（__________baba_________）。 用分析树表示求解过程。

S B B b B a B b a Print baba B.vers=baba B.vers=aba B.vers=ba B.vers=a

53．假设第一个四元式的序号是100，写出布尔表达式ae的四元式序列。

100 （j<, a, b, 106） 101 （j, _, _ , 102） 102 （jnz, c, _ ,104） 103 （j，_ ,_ ,q） 104 （j>，d, e, 106） 105 （j，_ , _ , q ） T:106 …… F:q …….

54．设有如下文法： G[E]：E→EWT|T T→T/F|F

F→（E）|a|b|c W→+|-

证明符号串a/(b-c)是句子。 解答：有推导

25

E?T?T/F?F/F?a/F?a/(E)?a/(EWT)?

a/(TWT)? a/(FWT)? a/(bWT)? a/(b-T)? a/(b-c)，即从文法开始符号E能够推导出a/(b-c)，所以a/(b-c)是文法G[E]的句子。 55．对于下列文法 G[S]： S→Sb|bA A→aA|a

（1）构造一个与G等价的LL（1）文法G′。 （2）对于文法G′,构造相应的LL（1）分析表。 解： （1）（5分）G′：S→bAS′ S′→b S′|ε

A→aA′

A′→A|ε

（2）（1分）FIRST（S）={ b } FIRST（S′）={ b，ε} FIRST（A）={a}

FIRST（A′）={a，ε} FOLLOW（S）={#} FOLLOW（S′）={#} FOLLOW（A）={b，#}

FOLLOW（A′）=（b，#）

LL（1）分析表：

a b #

S S→

bAS′

S′ S′→b S′→ε

S′

A A→

aA′

A′ A′→A A′→A′→ε

ε

56．构造下述文法的SLR（1）分析表。

G[S]：S→（A） A→ABB|B B→b 解：拓广文法：（1分） S′→S （0）

S→（A） （1） A→ABB （2）

A→B （3） B→b （4） 识别活前缀的DFA：（4分）

《编译原理》复习题

S→（L） S.num=L.num+1

(1)

0S→a S.num=0 L→L，S

(1)(1) S→.(A) L.num=if L.num>S.num then L.num else

( S.num L→S L.num= S.num

60．设有文法G[S]: ) S→aAcB|Bd I2：S→(.A) I3：S→(A.) I6： S→(A). A→.ABB A A→A.BB A→AaB|c

B I：A→AB.B B B→.b A→.B B→bScA|b 7I8：A→ABB. B→.b B→.b 该文法句型aAcbBdcc的句柄是

_______Bd_____________。 b B b 61．2．已知文法G[S]如下：构造该文法的LR（0）分析表。 I5： A→B. I4： B→b. G[S]：S→BB

FIRST集和follow集：（1分） B→aB|b

First（S）={（，c} follow( S)={#} 解：拓广文法：（1分） First（A）={b} follow(A)={b,)} （0）S?→S First（B）={b} follow(B)={b,)} （1）S→BB SLR(1)分析表：（4分） （2）B→aB

（3）B→b ACTION GOTO 识别活前缀的DFA 如下： b # S A B （ ） I：S′→.S S I：S′→S. 1 0 1 2 3 4 5 6 7 8 S2 S6 R4 R3 R2 S4 S4 R4 R3 S4 R2 Acc R1 1 3 5 7 8 a I0： S??.S S?.BB B?.ab B?.b b a I3： B?a.B B?.ab B?.b B I6： B?aB. S I1： S??S. B b I2： S?B.B B?.ab B?.b b B I5： S?BB. a b I4： B?b. 57．有一语法制导定义如下： S→bAb print “1” A→（B print “2” A→a print “3” B→aA) print “4” 若输入序列为b（a（a（aa）））b，且采用自下而上的分析方法，则输出序列为（__34242421____）。 58．写出赋值语句X= -(a+b)/(c-d)-(a+b*c)的逆波兰表示。Xab+-cd-/abc*+-= 59．为文法

G[S]：S→（L）|a L→L，S|S

写一语法制导定义，它输出句子中括号嵌套的最大层次数。

解： 使用num属性描述括号的嵌套最大层次数

S?→S print（S.num）

26

状态 LR(0)分析表如下：

Action a 0 1 2 3 4 5 6 S3 S3 S3 R3 R1 R2 b S4 S4 S4 R3 R1 R2 # acc R3 R1 R2 Goto S 1 B 2 5 6