编译原理样题

一、选择题

1． 正规式 M 1 和 M 2 等价是指_____。 

　A．( ) M1和M2的状态数相等   　 　       B．( ) M1和M2的有向边条数相等
　C．( ) M1和M2所识别的语言集相等 　　D．( ) M1和M2状态数和有向边条数相等

2． 文法G：S→xSx|y所识别的语言是_____。

　A．( ) xyx  　 B．( ) (xyx)* C．( ) xnyxn(n≥0)     D．( ) x*yx*

3．如果文法G是无二义的，则它的任何句子α_____。

　A．( )最左推导和最右推导对应的语法树必定相同 　　

　B．( ) 最左推导和最右推导对应的语法树可能不同 　　

　C．( ) 最左推导和最右推导必定相同   　　

　D．( )可能存在两个不同的最左推导，但它们对应的语法树相同

 

 

4．语言是

A．句子的集合                    B．产生式的集合

C．符号串的集合                  D．句型的集合

5．编译程序前三个阶段完成的工作是

A．词法分析、语法分析和代码优化

B．代码生成、代码优化和词法分析

C．词法分析、语法分析、语义分析和中间代码生成

D．词法分析、语法分析和代码优化

6．一个句型中称为句柄的是该句型的最左

 A．非终结符号    B．短语     C．句子   D．直接短语

7．下推自动机识别的语言是

A．0型语言                 B．1型语言 

C．2型语言                 D．3型语言

8．扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即

     A． 字符        B．单词          C．句子         D．句型

9．对应Chomsky四种文法的四种语言之间的关系是

     A．L0ÌL1ÌL2ÌL3           B．L3ÌL2ÌL1ÌL0

     C．L3=L2ÌL1ÌL0           D．L0ÌL1ÌL2=L3

10．词法分析的任务是

 A．识别单词                  B．分析句子的含义

 C．识别句子                  D．生成目标代码

11．常用的中间代码形式不含

 A．三元式      B．四元式     C．逆波兰式     D．语法树

12． 代码优化的目的是

 A．节省时间                  B．节省空间 

 C．节省时间和空间            D．把编译程序进行等价交换

13．代码生成阶段的主要任务是

 A．把高级语言翻译成汇编语言

 B．把高级语言翻译成机器语言

 C．把中间代码变换成依赖具体机器的目标代码

 D．把汇编语言翻译成机器语言

 

二、填空题

1．计算机执行用高级语言编写的程序主要有两种途径：___解释__和__编译___。

2．扫描器是__词法分析器___，它接受输入的__源程序___，对源程序进行___词法分析__并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。

3．自上而下分析法采用___移进__、归约、报错、___接受__等四种操作。

4．一个LR分析器包括两部分：一个总控程序和___一张分析表__。

5．后缀式abc-/所代表的表达式是___a/(b-c)__。

  1. 编译过程可分为 （ 词法分析） ，（语法分析），（语义分析与中间代码生成 ），（代码优化）和（目标代码生成 ）五个阶段。
  2. 如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（ 二义性的      ）。 
  3. 语法分析器的输入是（ 单词符号      ），其输出是（ 语法单位      ）。
  4. 扫描器的任务是从（ 源程序中    ）中识别出一个个（ 单词符号    ）。

 

  1. 语法分析的方法大致可分为两类，一类是（ 自上而下         ）分析法，另一类是（ 自下而上 ）分析法。
  2. 预测分析程序是使用一张（ 分析表         ）和一个（ 符号栈 ）进行联合控制的。
  3. 一张转换图只包含有限个状态,其中有一个被认为是（初）态;而且实际上至少要有一个（终 ）态。
  4. 语法分析是依据语言的（语法 ）规则进行。中间代码产生是依据语言的（语义）规则进行的。
  5. 最右推导亦称为（规范推导），由此得到的句型称为（规范）句型。
  6. 对于文法G，仅含终结符号的句型称为 ( 句子 )。
  7. 所谓自上而下分析法是指(从开始符号出发，向下推导，推出句子）
  8. 2型文法又称为（上下文无关）文法；3型文法又称为（正则 ）文法。
  9. 算符优先分析法每次都是对(最左素短语）进行归约。

19．编译程序首先要识别出源程序中每个(单词)，然后再分析每个(句子)并翻译其意义。

20．编译器常用的语法分析方法有(自底向上)和(自顶向下)两种。

21．通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的(分析)，中间代码生成、代码优化与目标代码的生成则是对源程序的(综合)。

22．对编译程序而言，输入数据是(源程序)，输出结果是(目标程序)。

 

三、判断题（请在括号内，正确的划√，错误的划×）

1.一个上下文无关文法的开始符，可以是终结符或非终结符。                           (    )

2.一个句型的直接短语是唯一的。                                                   （   ）

6.2型文法一定是3型文法。                                                        （   ）

7.一个句型一定句子。                                                              (    )

8.算符优先分析法每次都是对句柄进行归约。                                          (    )

10.编译过程中，语法分析器的任务是分析单词是怎样构成的。                           (    )

13.递归下降分析法是一种自下而上分析法。                                           (    )

14.并不是每个文法都能改写成LL(1)文法。                                            (    )

15.每个基本块只有一个入口和一个出口。                                              (    )

16.一个LL(1)文法一定是无二义的。                                                  (    )

17.逆波兰法表示的表达试亦称前缀式。                                                (    )

18.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。                        (    )

19.正规文法产生的语言都可以用上下文无关文法来描述。                                (    )

21.3型文法一定是2型文法。                                                        (    )

22.如果一个文法存在某个句子对应两棵不同的语法树，则文法是二义性的。                 (    )

答案：1.×    2.×     6.×    7.×    8.×      10.×  

   13.×   14.√   15.√   16.√   17.×   18.√   19.√     21.√   22.√

 

23．编译程序是对高级语言程序的解释执行。(× )

24．一个有限状态自动机中，有且仅有一个唯一的终态。(×)

25．逆波兰表示法表示表达式时无须使用括号。 (√ )

26．两个正规集相等的必要条件是他们对应的正规式等价。 (× )

 

 

四、简答题

1. 考虑文法 G[S]:

S → (T) | a+S | a

T → T,S | S

消除文法的左递归。

解：消除文法G[S]的左递归：
S→(T) | a+S | a
T→ST′
T′→,ST′| ε
 

2. 试为表达式 w+(a+b)*(c+d/(e-10)+8) 写出相应的逆波兰表示。

解： w a b + c d e 10 - / + 8 + * +

 

3. 已知文法 G[S] 为 S → aSb|Sb|b ，试证明文法 G[S] 为二义文法。

证明： 　　　
　　由文法G[S]：S→aSb|Sb|b，对句子aabbbb对应的两棵语法树为：
　　
因此，文法G[S]为二义文法。 　　

 

4．简述词法分析程序的功能。

答：略

 

 

  1. 目标代码有哪几种形式？每种形式的特点是？

答：目标代码通常采用三种形式：机器语言，汇编语言，待装配机器语言模块。其特点是：

(1)可直接运行；

(2)需要汇报程序的汇编；

(3)需要通过连接装配程序的连接和装配才能运行。

 

  1. 写出表达式a＋b*(c-d)/e的逆波兰式。

答：逆波兰式: abcd-*e/+

 

  1. 写出表达式a:=(b+c)*e+(b+c)/f的逆波兰式。

答：逆波兰式  abc+e*bc+f/+:=

 

 

8、对于文法G(E):

E®T|E+T

T®F|T*F

F®(E)|i

1）写出句型(T*F+i)的最右推导并画出语法树。

2）写出上述句型的短语，直接短语、句柄和素短语。

 

 

答：

1）

EÞTÞFÞ(E) Þ(E+T) Þ(E+F) Þ(E+i) Þ(T+i) Þ(T*F+i)

 

2）

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

直接短语：T*F, i

句柄：T*F

素短语：T*F, i

 

 

 

 

9、设有如下文法G（S），试消除其左递归。

G（S）：S—>Ac|c

       A—>Bb|b

       B—>Sa|a

解：S→abcS′|bcS′|cS′,  S′→abcS′|

 

 

10、写出一个文法，该文法产生的语言是{anbnan,n>0}

答：略。

11、对于文法G(E):

E®T|E+T

T®F|T*F

F®(E)|i

计算非终结符号E,T的first集合。

答：略。

 

五.综合题

1. 画出正规表达式（a|b）*的e-NFA。

2. 对1中的e-NFA进行确定化。
 

 

第1页共6页