编译原理期末复习试卷

1．设有文法G[I]：II1|I0|Ia|Ic|a|b|c，下列符号串中（ A ）不是该文法的句子。

A. ab0 B. a0c01 C. aaa D. bc10 2．下述正则表达式中，（ D ）与(a|b)(c|d)等价。

A. a(c|d)|b(c|d) B. a(c|d)|b(c|d) C. a(c|d)|b(c|d) D. (a|b)c|(a|b)d

3．表示在字符集{a,b}上,不是以a开头,但以aa结尾的字符串集合的正则表达式是（C ）。

A. (a|b)aa B. aa(a|b)b C. b(a|b)aa D. b(a|b)aa

4．编译程序中的语法分析器接受以（ C）为单位的输入，并产生有关信息供以后各阶段使用。

A. 表达式 B. 产生式 C. 单词 D. 语句 5．下面选项中不属于语义检查的是（B ）。

A. 赋值语句的左、右部的类型是否相容 B. 表达式的括号是否配对

C. 函数的形参和实参的类型是否相容 D. 标号是否声明

6．运行时的存储空间可以划分为目标代码区, （ B ）,寄存器区,栈区和堆区等。

A. 动态区 B. 静态区 C. 变量区 D. 数据区 7．下面信息中不属于活动记录区的内容的是（B ）。

A. 局部变量的值 B. 全局变量的值 C. 返回地址 D. 中断寄存器的值 8．在动作文法中,动作符号代表的是某种（ C ）。

A. 语法意义 B. 非终极符号 C. 语义动作 D. 符号的属性 9．-a-(b*c/(c-d)+(-b)*a)的逆波兰式是（ C ）。

A. abc*cd-b-a*+/- - B. a-bc*cd-b-a*+/- C. a-bc*cd-/b-a*+- D. a-bc*cd-b-a*+- 10．素短语是指（ D ）的短语。

A. 除自身外不再包含其他终极符 B. 除自身外不再包含其他非终极符

C. 除自身外不再包含其他短语 D. 除自身外不再包含其他素短语

**

*

*

*

*

*

*

*

*

*

*

*

二、 填空题（共10分，每空2分)

1．编译程序是一种常用的（ 系统 ）软件。

2．文法中的终极符集合和非终极符集合的交集是（ 空集 ）。

3．在C语言中，标识符的出现可分为（定义性出现 ）和（ 使用性出现 ）。 4．语法制导的编译程序能同时进行语法分析和（语义 ）分析。

三、 应用题（共55分）

1．（15分）试构造识别正则表达式 ab(a|ab)* 的NFA，并将其转换为等价的DFA。 2．（10分）假设有文法：E T|E+T|E-T

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

试写出符号串 i*(i+i) 的最左推导和语法树。 3．（20分）设当前层数为L，可用偏移量Offset值为101，且有下面程序，试画出类型表和符号表。

CONST m=123;

TYPE arr=array [1..10] of integer; rec=record i,j:real end; VAR a:arr; x:real; 4．（10分）试写出表达式 (a+b)*(c+d)-(a+b/c) 的四元式中间代码。

四、 分析题（共15分）

考虑以下文法：S aAa

A b|(B B Ab)

1．（3分）写出LL(1)文法的判定条件。 2．（12分）构造该文法的LL(1)分析表。