编译原理期末考试习题及答案(桂电) 下载本文

.

桂 林 电 子 科 技 大 学 试 卷

2012-2013 学年第 2 学期 课号

课程名称 编译原理试题、答案和评分标准 (A卷;闭卷) 适用班级(或年级、专业) 01应本

考试时间 120 分钟 班级 学号 姓名 题 号 满 分 得 分 评卷人 一 20 二 8 三 6 四 6 五 15 六 10 七 10 八 15 九 10 十 成绩 100 一、填空题|(每题4分,共20分)

1. 乔母斯基定义的3型文法(线性文法)产生式形式 A?Ba|a,或A?aB|a,A,B∈Vn,

a,b∈Vt 。

2.语法分析程序的输入是 单词符号,其输出是 语法单位 。

3 型为 B ? .aB 的LR(0)项目被称为 移进 项目,型为 B ? a.B 的LR(0)

项目被称为 待约 项目,

4.在属性文法中文法符号的两种属性分别为 继承属性 和 综合属性 。 5、运行时存贮管理方案有 静态存储分配、动态存储分配 和 堆式存储分配 和方案。

二.已知文法 G(S)

(1) E ? T | E+T (2) T ? F | F*F (3) F ? (E)| i

(1)写出句型(T*F+i)的最右推到并画出语法树。(4分) (2)写出上述句型的短语,直接短语和句柄。(4分)

答:(1)最右推到(2分)

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

(2) 语法树(2分)

(3)(4分)

短语: (T*F+i) ,T*F+i ,T*F , i

直接短语:T*F , i 句柄:T*F

word范文

.

三. 证明文法 G(S) : S ? SaS |ε 是二义的。(6分) 答:句子 aaa对应的两颗语法树为:

因此,文法是二义文法

四.给定正规文法G(S):

(1) S ? Sa | Ab |b (2) A ? Sa

请构造与之等价的DFA。(6分) 答:对应的NFA为: (6分)

状态转换表: a b {F} Φ {S} {S} {S,A} Φ {S,A} {S,A} {S} 五. 构造识别正规语言b*a(bb*a)*b* 最小的DFA(要求写出求解过程)。(15分) 答:(1)对应的NFA(5分)

(2)将(1)所得的NFA确定化:(5分) a b {0} {1,3} {0} {1,3} Φ {2,3} {2,3} {1,3} {2,3} word范文

.

(5分)

六. 已知文法 G(S) :

(1) S ? ^ | a | (T) (2) T ? T,S | S 试:(1)消除文法的左递归;(4分)

(2)构造相应的first 和 follow 集合。(6分) 答:(1)消除文法的左递归后文法 G’(S)为:

(1) S ? ^ | a | (T)

(2) T ? ST’ | S

(3) T’ ? ,ST’ |ε (4分)

(2)(6分) first follow S a ^ ( # , ) T a ^ ( ) T’ , ε ) 七. 已知文法 G(S) :

(1) S ? SiA | A (2) A ? A+B | B (3) B ? A* | (

试构造非终止符的firstVT和lastVT集合。(10分) 答:(10分) firstVT lastVT S i , + , * , ( i , + , * , ( A + , * , ( + , * , ( B * , ( * , ( 八.已知文法 G(S) :

Follow (1) S ? B B

S # (2) B ? a B

B a,b,# (3) B ? b

的follow集合如表:

试:(1)给出该文法的LR(0)项目集规范族划分; (2)填写相应的SLR(1)的分析表。(15分) 答:(1)LR(0)项目集规范族划分(8分) I0 I2 I3

S B B S’? .S ---? I1 I1 S ? B.B ---? I5 B ? a.B ---? I6

a a S ? .BB ---B ? I2 S’? S. B ? .aB --? I3 B ? .aB --? I3

a b b B ? .aB --? I3 B ? .b --? I4 B ? .b --? I4 b B ? .b --? I4

I4 I5 I6 word范文

B ? b. S ? BB. B ? aB.

.

(2) SLR(1)分析表(7分) 状态 Action a b 0 S3 S4 1 2 S3 S4 3 S3 S4 4 R3 R3 5 6 R2 R2 Goto # Acc R3 R1 R2 S 1 B 2 5 6

九.设某语言的not-then-else 语句的语法形式为:S ? not E then S1 其语义解释为:

针对自上而下的语法分析器,

(1) 分段产生式;(3分)

(2) 写出每个产生式对应的语义动作。(7分) 答:(1)分段产生式(3分)及语义动作(7分)

(1) R ? not E then { Backpatch($2.FC ,nxq );

$$.chain = $2.Tc }

(2) S ? R S1 { Backpatch($2.chain , nxq )}

word范文

.

桂 林 电 子 科 技 大 学 试 卷

2012-2013 学年第 2 学期 课号 122239

课程名称 编译原理试题、答案和评分标准 (B卷;闭卷) 适用班级(或年级、专业) 01应本

考试时间 120 分钟 班级 学号 姓名 题 号 满 分 得 分 评卷人 一 20 二 8 三 6 四 6 五 15 六 10 七 10 八 15 九 10 十 成绩 100 一、填空题|(每题4分,共20分)

1. 乔母斯基定义的2型文法(上下文无关文法)产生式形式 A?β,A∈Vn, β∈V+。 2.词法分析程序的输入是 字符串 ,其输出是 单词符号 。

3 算符有限分析方法每次都是对 最左素短语 进行规约。型为 B ? aB. 的LR(0)项

目被称为 规约 项目。

4、写出x:=b*(d-e)/(c-d)+e的逆波兰式__xbde-*cd-/e+:=__。

5、常用的两种动态存贮分配办法是__栈式存储 分配 和 堆式存储__分配。

二.已知文法 G(S) :

(1) S ? ^ | a | (T) (2) T ? T,S | S 试:(1)写出句型(a,(a,a))的最左推到并画出语法树。(4分) (2)写出上述句子的短语,直接短语和句柄。(4分) 答:(1)最左推到(2分)

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

(2) 语法树(2分)

(3)(4分)

短语:(a,(a,a)) ,a,(a,a) , (a,a) , a,a , a 直接短语:a 句柄:a

word范文