2014年编译原理期中试题1

一、填空题（每空1分，共15分）

1、文法的类型有 种， 单词用 型文法描述。

2、你学过的语法分析算法主要有 LL(1) 、简单优先、 、 、 3、在词法分析阶段不能识别的是（ ）

A、标识符 B、运算符 SLR(1) 、 LR(1) 、 LALR(1) 。

3、程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即 方案和 方案。

4、简单优先分析法归约的对象是 ，算符优先分析法归约的对象是 。

5、编译程序分为6个阶段分别是： 、 语法分析 、 语义分析、中间代码生成、 、目标代码生成。

6、对编译程序而言，输入数据是源程序，输出结果是 。 7、你所知道的词法分析和语法分程序自动构造工具有 。 8、C语言运行时栈式内存分配的活动记录内容一般包括： 。

9、自下而上语法分析方法LR(0)与SLR(1)之间的关系为 。 10、表达式(a+b)*c的逆波兰表示为： 。 二、选择题（每题2分，共20分） 1、哪个不是DFA的构成成分（ ）

A、 有穷字母表 B、初始状态集合 C、 终止状态集合 D、有限状态集合 2、词法分析器的输入是（ ）

A、单词符号串 B、源程序 C、语法单位 D、目标程序

C、四元式 D、常数 4、自上而下语法分析的主要动作是（ ）

A、移进 B、推导 C、规约 D、匹配

5、文法[S]为S→AB|bC，A→ε|b，B→ε|aD，C→AD|b，D→aS|c，FOLLOW(A)为（ ） A、{a,c,#} B、{c,#} C．、{a,#} D、{#} 6、.设有文法G[S]: S→Ap|Bq，A→a|cA，B→b|dB ，则FIRST(Ap)为（ ）

A、{p,q} B、{b,d} C、{a,c} D、 其他 7、中间代码生成时所以据的是（ ）

A、语法规则 B、 词法规则 C、语义规则 D、等价变换规则

8、在编译程序中与生成中间代码的目的无关的是（ ）

A、便于目标代码优化 B、便于存储空间的组织 C、便于目标代码的移植 D、便于编译程序的移植 9、一个S属性文法一般采用的语法制导翻译方法（ ）。

A. LL(1) B. 算符优先 C、LR方法 D.以上三种都可以

10、中间代码是介于源语言程序和什么之间的一种代码（ ）

A、源代码 B、机器语言 C、汇编语言 D、 目标代码

- 1 -

三、综合题（共65分）

1、构造正规式1（0︱1）*101的DFA。（5分）

2. 判断文法G[S]：S→MH|a H→LSo|ε K→dML|ε L→eHf M→K|bLM是否是LL（1）文法，如果是，构造其LL（1）预测分析表（10分） 3.文法G[S ] （10分） (1) S→aAcBe (2) A→b (3) A→Ab (4) B→d

(1)构造文法的LR(0)分析表；（5分）

(2)给出分析输入串abbcde#是否为句子的LR(0)分析过程。（5分） 4. （共10分）对算数表达式文法G[E]:

E→E+T|T T→T*F|F F→(E)|i

(1) 构造算符优先关系表和LR分析表；（5分）

(2) 分别使用两种表对分析符号串i+i*i#是否为该文法句子。（5分） 5. （共10分）证明任何SLR(1)文法一定是LR(1)文法。

6.（共10分）(1)将语句if w<1 then a=b*c+d else while( a<0 ) do a=a-1 ;翻译为四元式序列（5分）

(2)采用语法制导翻译思想，表达式E的值描述如下：（5分） S’?E print(E?val)

E ?E1+ E2 E ?val := E1 ? val+ E2 ? val E ?E1* E2 E ?val := E1 ? val* E2 ? val E ?(E1) E ?val := E1? val

E ?i E ?val := i?lexval

给出表达式(6+3)*8+20的LR分析语法树并在各结点注明语义值。 7.代码局部优化优化（5分） G:

① T0=3.14② T1=2*T0 ③ T2=R+r ④ A=T1*T2 ⑤ B=A ⑥ T3=2*T0 ⑦ T4=R+r ⑧ T5=T3*T4 ⑨ T6=R-r ⑩ B=T5*T6

假设T0、T1、T2、T3、T4、T5、T6在后面的基本块中都不使用。

8. （共5分）对如下程序，当主程序调用过程语句y时，给出以下时刻 数据栈的情况。(1)已经开始但尚未执行完标号为15的语句；（5分） (2)已经开始但尚未执行完标号为16的语句；（5分） Program main；

Var a,b,c:real; Procedure y; Var d,e;real; Procedure x; Var f,g:real; Begin… end；｛x｝ Procedure z； Var h,i,j:real;

Begin… end;｛z｝

Begin …

15:y;… 16:z;… end;｛y｝

Begin…x;…end.｛main｝

- 2 -

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