兰州交通大学编译原理试卷

试给出下列语句的四元式序列： for I:= 1 to 10 do A[I, 2*J] := A[I, 2*J] + 10 其中A是 10×10的数组(每维下界为1)

4、已知文法G[S] S→AB A→aA∣|a B→bB∣b 给出aaabbb的最左推导

表达式文法G: E→E＋T | T T→T*F | F F→i | (E) （1）对文法进行改写，并判断改写后的文法是否是LL(1)的？给出它的预测分析表。 （2）给出输入串i＋i*i#的分析过程，说明输入串是否为该文法的句子

1为正规式(a|b)*a(a|b)

构造等价且状态最少的确定有限自动机。

构造正规是1（0|1）*101相应的NFA，将NFA确定化

(a+b*c)/(a+b)-d的逆波兰和四元式序列

文法G[S]：S→a丨△丨（T） T→T，S丨S，给出（（（a,a),△，（a）），a）的最左推导。

1、为正规式(a|b)a(a|b)构造等价且状态最少的确定有限自动机。

（要求给出主要步骤）

*

2、有文法如下：

S → BA A → BS | d

B → aA | bS | c

(1). 计算文法的每个非终结符的FIRST和FOLLOW集合；

(2). 判断文法是否LL（1）文法，如果是，给出其预测分析表，否则说明理由。

3、对下面的拓广文法：

S’ → S S → BB B → aB | b

(1). 构造文法的识别规范句型活前缀的DFA；

(2). 判断该文法是不是SLR（1）文法。若是，给出SLR（1）分析表；若不是，说明理由。

4、有文法如下：

T → T*F | F F → P?F | P P → (T) | i

证明T*i?P是该文法的一个句型，但不是规范句型；

指出T*i?P的所有短语、直接短语、素短语、句柄。

三、应用题（1、4、5每题10分，2、3每题15分，共60分）

1、(a|b)a(a|b) 状态最少的DFA。 NFA如图（5分）： （也可是其它等价的FA） A b I *a a B a b C 用子集法得到的状态转换矩阵： 确定化（3分）后的DFA如图，已是状态最少的。如不说明是最简的扣1分。 化简（2分） Ia 1 { A} {A,B} 2 {A,B} {A,B,C} 3 {A,B,C} { A,B,C} 4 {A,C} { A,B} Ib {A} {A,C} {A,C} {A} 注：初态或终态错扣1分 a a 1 b b 2 b a 4 a b 3 2、(1)（6分） FIRST(S) ={ a,b,c )} FOLLOW(S) ={#,a,b,c,d }

FIRST(A) ={ a,b,c,d )} FOLLOW(A) ={#,a,b,c,d } FIRST(B)={ a,b,c} FOLLOW(B) ={a,b,c,d }

(2) 因为文法不含左递归，关于A的两个规则的SELECT集不相交，关于B的3个规则的SELECT集两两不相交，所以文法是LL（1）文法（2分）。 预测分析表（7分）如下： S A B

a S → BA A → BS B → aA b S → BA A → BS B → bS c S → BA A → BS B → c d A →d # 3、对文法的产生式编号：

(0) S’ → S (1) S → BB (2) B → aB (3) B → b

(1) （6分）构造文法的识别活前缀的DFA如图： I0: S’ →.S S I1: S’ →S . S →.BB B →. aB I2: S →B .B B B →. b a I3: B →a. B B →. aB B →. b a B B →. aB I5: S →BB.

b b B →. b b I4: B → b. a B I6: B →aB. (2) 因为各项目集都不含冲突,该文法是LR(0)文法，也是SLR(1)文法（2分）。 FOLLOW(S) ={#}, FOLLOW(B) ={a,b,#}, SLR(1)分析表如下：（7分） a 0 1 2 3 4 5 S3 S3 S3 r3 b S4 S4 S4 r3 ACTION # acc r3 r1 S 1 GOTO B 2 5 6

6 r2 r2 r2

4、对于符号串T*i?P存在如下推导：（或画一颗语法树证明是句型）

T ? T*F ? T*P?F ? T*P?P ? T*i?P

所以T*i?P是该文法的一个句型，但不存在一个规范推导能推导出该句型，所以不是规范句型。（5分）

短语：T*i?P、i?P、i、p 直接短语：i、p 素短语：i 句柄：i

(5分)将文法G[S] 改写为等价的G′[S]，使G′[S]不含左递归和左公共因子。 G[S]： S → bSAe | bA

A → Ab | d

解：文法G[S] 改写为等价的不含左递归和左公共因子的G'[S]为：

S → bB B → SAe | A A → d A' A' → bA' | ε 问答第2题

(10分) 判断下面文法是否为LL(1)文法，若是,请构造相应的LL(1)分析表。

S → aH

H → aMd | d M → Ab | ε A → aM | e

解：首先计算文法的 FIRST集和FOLLOW集如下表。

文法的 FIRST集和FOLLOW集 非终结符 S H M A FIRST集 {a}......... {a ，d}..... {a ，e ，ε} {a ，e}..... FOLLOW集 {# }... {# }... {d ，b} {b}.... 由于select（H→aMd）∩select（H→d）={a}∩{d }= select（M→Ab）∩select（M→ε）={a ，e}∩{d ，b }= select（A→aM）∩select（A→e）={ a }∩{ e }= 所以该文法是LL(1)文法，LL(1)分析表如下表。

LL(1)分析表 S H M a →aH. →aMd →Ab. d →d. →ε b →ε e →Ab →e. # A →aM. 问答第3题 给出与正规式R＝（ab）*（a|b*）ba等价的NFA。 解：与正规式R＝（ab）*（a|b*）ba 等价的NFA如下图

问答第4题

将下图的NFA确定化为DFA。

解：用子集法确定化如下表

用子集法对所给图的确定化 I {X,1,2} {1,2}.. {1,2,3} {1,2,Y} 确定化后如下图

Ia {1,2}.. {1,2}.. {1,2,Y} {1,2}.. Ib {1,2,3} {1,2,3} {1,2,3} {1,2,3} 状态 X 1 2 3

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