编译原理复习题

一、填空题

1、  一个名字的属性包括(类型)和（作用域）

2、  对于数据空间的存储分配，FORTRAN采用（静态分配）策略，PASCAL采用（栈式动态分配策略）策略

3、  如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（属性文法）

4、  对于文法G，仅含终结符号的句型称为（一个句子）

5、  程序语言的单词符号一般可以分为（关键字，标识符、常数、运算符、界符）等等。

6、  语法分析器的输入是（单词符号），其输出是（语法单位）。

7、  扫描器的任务是从（源程序）中识别出一个个（单词符号）。

8、  语法分析最常用的两类方法是（自上而下）和（自下而上）分析法。

9、  所谓语法制导翻译方法是（为每个产生式配上一个翻译子程序，并在语法分析的同时执行这些子程序）

10、              产生式是用于定义（语法范畴）的一种书写规则。

11、              程序语言一般分为  低级语言 和 高级语言 两大类，其中 低级语言 通常又称为面向机器的语言。面向机器语言指的是特定计算机系统 所固有的语言 ，其特点是 程序的执行效率高，编制效率低，可读性差，在此基础上产生了与人类自然语言比较接近的 高级语言。

12、              一个编译程序中，不仅包含词法分析、语法分析、中间代码生成、代码优化、目标代码生成等五个部分，还应包括  解释器   。其中，   中间代码生成  和代码优化部分不是每个编译程序都必需的，词法分析器用语识别 标识符 ，语法分析器则可以发现源程序中的 语法错误 。

二、单项选择题

1、  一般程序设计语言的定义都涉及     B     三个方面。

1语法        2语义      3语用     4程序基本符号的确定

A 123      B 124       C 134         D 234

2、  设有文法G[S]:

S::=S*S|S+S|(S)|a

该文法（  B  ）二义性文法

A 是       B 不是           C无法判断

3、  设有文法G[I]:I-àI1|I0|Ia|Ic|a|b|c

下列符号串中是该文法的句子的是(   C     )

1ab0  2a0c01  3aaa    4bc10

    A  1       B234       C  34         D1234

4、  编译过程中，语法分析器的任务是（  B  ）

1分析单词是怎样构成的

2分析单词串是如何构成语句和说明的

3分析语句和说明是如何构成程序的

4分析程序的结构

A23      B  234       C 123        D1234

5、  巴科斯-诺尔范式是一种广泛采用的（C  ）的工具。

A描述规则         B 描述语言        C描述文法         D 描述句子

6、  正则式的得“|”读作“或者”“。”读作（连接），“*”读作（并且）

A并且           B  或者          C 连接           D 闭包

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

     A表达式        B 产生式        C 单词          D 语句

8、  高级语言编译程序常用的语法分析方法中，递归下降分析法属于（自顶向下）分析法。

       A 自左至右     B自顶向下      C 自底向上      D自右至有左

9、  算符优先分析法每次都是对（最左短语）进行归约，简单优先分析法每次都是对简单短语进行归约。

      A 最左短语        B简单短语       C句柄     D素短语   E 最左素短语

三、名词解释题

1、  遍：指编译程序对源程序或中间代码程序从头到尾扫描一次

2、  无环路有向图(DAG)－－如果有向图中任一通路都不是环路，则称庐有向图为无环路有向图，简称DAG

3、  语法分析－－按文法的产生式识别输入的符号串是否为一个句子的分析过程。

4、  二义性文法------如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义性文法。

5、  代码优化---从变换后的程序出发，能生成更有效的目标代码的方法

四、简单题：

1、已知文法G(S):

S→a| (T)

T→T,S|S

的优先关系表如下：

请计算出该优先关系表所对应的优先函数表。

解：

3、何谓优化？按所涉及的程序范围可分为哪几级优化？

优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目标代码。　　　　　　　　
　　三种级别：局部优化、循环优化、全局优化

4、目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？

目标代码通常采用三种形式：机器语言，汇编语言，待装配机器语言模块。　　　　　　　　　　　　　　
　　应着重考虑的问题：
　　  (1)如何使生成的目标代码较短；
　　　(2)如何充分利用寄存器，以减少访问内存次数；
　　　(3)如何充分利用指令系统的特点。

5、  字母表为{a, b}，试写出与该字母表上所有以a为首的字组成的正规集相对应的正规式。

解：a ( a | b )*。

五、计算题：

1、  有表达式如下：

 A+B*(C-D)**N(**为幂乘)

（1）       给出该表达式的逆波兰式表示（后缀式）

（2）       给出上述表达式的四元式和三元式序列