编译原理期中测试答案

编译原理期中测试答案

三、单项选择题(每题3分，共15分)

1．设有文法G[S]: S→(AS)|(b)

A→(SaA)|(a)

该文法的句型(((b)a(a))(b))有 C 个直接短语。 A.1 B. 2 C. 3 D. 4

2．如果一个文法满足 D ，则称该文法是二义性文法。 (1) 文法的某一个句子存在两个（包括两个）以上的语法树 (2) 文法的某一个句子存在两个（包括两个）以上的最左推导 (3) 文法的某一个句子存在两个（包括两个）以上的最右推导 (4) 在进行归约时，文法的某些规范句型的句柄不唯一 上述描述中的所有正确描述有：

A. (1) B. (1)(2) C. (1)(2)(3) D. (1)(2)(3)(4) 3．构造一个不带回溯的自顶向下语法分析器，要求文法满足 E 。

A. 对每个形如A→x1|x2|…|xn的产生式，要求FIRST(xi)与FIRST(xj)的交集为空集(i≠j)

B. 对每个形如A→x1|x2|…|xn的产生式，若xi?ε，则要求FIRST(xj)与FOLLOW(A)的交集为空集(i≠j) C. 不含左递归 D. A和B同时满足 E. A、B和C同时满足

*4、给定文法A→bA|cc，下列符号串中，是该文法的句子的是 C 。

① cc ② bcbc ③ bcbcc ④ bccbcc ⑤ bbbcc A① B. ①③④⑤ C. ①⑤ D. ①④⑤ 5、若一个句型中出现了某一产生式的右部，则此右部 B 是该句型的句柄。

A.一定 B. 不一定 C. 一定不 D. 无法判断 四、简述题(每题5分，共20分)

1、写一上下文无关文法,它能产生语言L?{an#bm|n,m??0}。

S→A#B A→Aa|? B→Bb|?

2、将文法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' | ε

3、什么是文法的二义性？下面的文法是二义的吗？为什么？

G[S]： S→AB | ABD A→a B→CD |D C→c D→d

答：如果一个文法存在某个句子对应两棵不同的语法树，则该文法是二义的。

是，句子acd 有两个完全不同的语法树。 4、 设文法G[A]: A→[B

B →X] | BA X →Xa | Xb | a | b

试求出文法G[A]产生的语言对应的正则式。

解: X →X(a |b) | a | b X →(a |b)?( a | b)* 代入B →X] | BA

B →(a |b)?( a | b)*] | BA B →(a |b) ( a | b)*] ?A*代入 A→[(a |b) ( a | b)*] ?A* [(a|b)(a|b)*] ([(a|b)(a|b)*])* 五、计算题(共41分) 1、已知文法G(S): S→a|∧|(T) T→T,S|S

⑴ 给出句子(a,(a,a))的最左推导并画出语法树； ⑵ 给出句型((T,S),a)的短语、直接短语、句柄。(10分) 答：最左推导：(2分)

S=>(T)=>(T,S)=>(S,S) =>(a,S)=>(a,(T))=>(a,(T,S)) =>(a,(S,S))=>(a,(a,S)) =>(a,(a,a)) 语法树：

S ( T ) T , S S a ( T S a T , ) S a

3给出与正规式R＝（ab）*（a|b*）ba等价的NFA。（5分）

答案：

4将下图的NFA确定化为DFA。（8分）

答案： 用子集法确定化如下表

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

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库编译原理期中测试答案在线全文阅读。