编译原理计算题

1. 按指定类型给出下列语言的文法。 (1) L1={ canbm| n≥0,m>0 } 用正规文法。

答案：S→cA A→aA|aB|a B→bB|b 2．文法G[S]为： S→SdT | T T→T

试给出句型adT<(S)的短语、简单(直接)短语、句柄和最左素短语

答案：短语：a, T, (S), T<(S), adT<(S) 直接短语：a, (S) 句柄：a 最左素短语：a

3．证明下述文法G：S?aSbS|aS|d 是二义性文法。

答：一个文法，如果存在某个句子有不只一棵语法分析树与之对应，那么称这个文法是二义性文法。句子aadbd有两棵语法树。如下图： S S a S S a S b

S a a S b d S

d d d

(1) (2)

由此可知，S?aSbS|aS|d定义的文法是二义性文法。

4．对于文法G[S]：S?AB，A?Aa|bB，B?a|Sb求句型baSb的全部短语、直接

短语和句柄？

句型baSb的语法树如图五(2)所示。 S

图五(2) 句型baSb的的语法树

A B

b B S b

a 答案：

baSb为句型baSb的相对于S的短语，ba为句型baSb的相对于A的短语，Sb为句型baSb的相对于B的短语，且为直接短语，a为句型baSb的相对于B的短语，且为直接短语和句柄。

5．设有非确定的有自限动机NFA M=({A，B，C}，{0，1}，?，{A}，{C})，其中：? (A，0)={C} ? (A，1)={A，B} ? (B，1)={C} ? (C，1)={C}。请画出状态转换距阵和状态转换图。 答案：状态转换距阵为：

? A 0 C 1 A，B B C

状态转换图为：

S→[A

1 ? ? 1 ABC C 1 1 C10 6. 将文法G[S] 改写为等价的G'[S]，使G'[S]不含左递归和左公共因子。（5分）

A→B]|AS

B→aB|+a

答案：S→[A A→B]A’ A’ →SA’|ε B→aB|+a

7 对给定正则表达式(d|ad)(b|ab)+ 构造其DFA M

adbabdabb 8 构造正规式1（0 |1）*101的DFA（书中68页题）

7将下图的NFA确定化为DFA。（P59）

2 ε ε b a ε b X 0 1 3 Y a b NFA：

{X,0,1,3} {0,2,1,3} {3,Y} {1,3,Y} a {0,2,1,3} {0,2,1,3} Ф {2} b {3,Y} {1,3,Y} {Y} {Y} DFA：

S A B a A A b B C D Ф C E D 8. 设有文法G1 G1：S→SaQ ∣ Q

Q→QbR ∣ R R→cSd ∣ e

（1）证明句型 QbRae 是规范句型

（2）给出句型 QbRae 的语法树和句柄：

证：（1）因为句型 QbRae 可由文法开始符S经过规范推导产生，推导过程如下：S => SaQ => SaR => Sae => Qae => QbRae 所以句型 QbRae 是规范句型 （2）语法树：略 句柄：QbR

9 已知文法G[S]: S→aBc|bAB

A→aAb|b B→b|ε

（1） 构造其LL（1）分析表；

判断符号串baabbb是否为该文法的句子（写出含有符号栈、输入串和规则的分析过程）。 其中判断“baabbb是该文法句子”为2分，其他错一个扣0.5分，扣完为止 符号栈 $S $BAb $BA $BbAa $BbA $BbbAa $BbbA $Bbbb $Bbb $Bb $b $ 输入串 baabbb$ baabbb$ aabbb$ aabbb$ abbb$ abbb$ bbb$ bbb$ bb$ b$ $ $ 规则 S→bAB A→aAb A→aAb A→b B→ε success 9． （共15分）已知文法G[E]:

E→ETE|（E）|i T→*|+

（1）文法存在左递归（P87），消除左递归后的文法为：

E→(E)E’|i E’（2分） E’→TEE’|ε （2分） T→*|+ （1分）

（2）(5分)没考虑#扣0.5分，其它错或少写一个扣0.5分 FIRST(E)={(,i} FIRST(E’)={*,+, ε} FIRST(T)={*,+} FOLLOW(E)={),*,+,#} FOWLLOW(E’)= {),*,+,#} FOLLOW(T)={(,i} （3）每错一个扣0.5分，全错或不写不得分，扣完为止，共5分 E E’ ( ) i * + # E→(E)E’ E’→ ε E→iE’ E’→TEE’ E’→TEE’ E’ →ε E’ →ε E’ →ε T→+ T T→* 10. 判断下面文法是否为LL(1)文法，若是，请构造相应的LL(1)分析表，并写出aabbb的分析过程。

S→aD D→STe|ε T→bM M→bH H→M|ε

答案：

S D T M H 步骤 0 1 2 3 4 栈 #S #Da #D #eTS a S→aD b e # D→ε D→STe D→ε 输入串 aabbb# abbb# abbb# abbb# T→bM M→bH H→M H→ε 动作(规则右部逆序入栈) Push S→aD Pop a Push D→STe Push S→aD Pop a #eTDa abbb# 5 6 7 8 9 10 11 12 13 #eTD #eT #eMb #eM #eHb #eH #eM #eHb #eH bbb# bbb# bbb# bb# bb# b# b# b# # Push D→ε Push T→bM Pop b Push M→bH Pop b Push H→M Push M→bH Pop b 出错，故句子不合法 11、考虑以下文法: D → T V

T → int | float V → id ,V | id

a. 在该文法中提取左公因子。

b. 为所得的文法的非终结符构造First集合和Follow集合。 c. 说明所得的文法是LL(1)文法。 d. 为所得的文法构造LL(1)分析表

e. 假设有输入串 int x,y,z 写出相应的LL(1)分析程序的动作 答案：a. 文法存在左公因子，提取左公因子后的文法为： D → T V

T → int | float V → id V' V'→ ,V |ε

b. 非终结符 D T V V' First集合 { int , float } { int , float } { id } { , , ε } Follow集合 { $ } { id } { $ } { $ } c. (1) First ( TV ) = { int , float }

First(int) ∩ First(float)={int}∩{float}=φ; First(id V')={id}；

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