<编译原理>历年试题及答案
一．        （每项选择2分，共20分）选择题
1．将编译程序分成若干个“遍”是为了_b__。
a.提高程序的执行效率
b.使程序的结构更加清晰
c.利用有限的机器内存并提高机器的执行效率
d.利用有限的机器内存但降低了机器的执行效率
2．构造编译程序应掌握__d__。
a.源程序        b.目标语言
c.编译方法      d.以上三项都是
3．变量应当c＿。
a.持有左值                b.持有右值
c.既持有左值又持有右值   d.既不持有左值也不持有右值
4．编译程序绝大多数时间花在_d___上。
  a.出错处理      b.词法分析
c.目标代码生成   d.管理表格
5．词法分析器的输出结果是_c___。
a.单词的种别编码           b.单词在符号表中的位置
c.单词的种别编码和自身值   d.单词自身值
6．正规式MI和M2等价是指__c__。
a. MI和M2的状态数相等         b.Ml和M2的有向弧条数相等。
C.M1和M2所识别的语言集相等    d. Ml和M2状态数和有向弧条数相等
7．中间代码生成时所依据的是—c。
        a．语法规则   b．词法规则   c．语义规则   d．等价变换规则
  8．后缀式ab+cd+/可用表达式__b_来表示。 
      a． a+b/c+d   b． (a+b)/(c+d)    c． a+b/(c+d)   d． a+b+c/d
9．程序所需的数据空间在程序运行前就可确定，称为____c_＿管理技术。
        a.动态存储    b.栈式存储    c.静态存储    d.堆式存储
10.堆式动态分配申请和释放存储空间遵守___d____＿原则。
        a.先请先放   b.先请后放   c.后请先放   d.任意


二（每小题10分，共80分）简答题
1.画出编译程序的总体结构图，简述各部分的主要功能。
2. 已知文法G[E]:
  E→ET+|T  T→TF* | F  F→F^ | a
试证：FF^^*是文法的句型，指出该句型的短语、简单短语和句柄.

3．为正规式(a|b) *a(a|b)构造一个确定的有限自动机。
4． 设文法G(S)：
        S→(L)|a S|a
    L→L，S|S
    (1) 消除左递归和回溯；
    (2) 计算每个非终结符的FIRST和FOLLOW；
    (3) 构造预测分析表。
5．          已知文法
A->aAd| aAb|ε
判断该文法是否SLR（1）文法，若是构造相应分析表，并对输入串ab#给出分析过程。
6． 构造算符文法G[H]的算符优先关系（含＃）。
            G[H]：H→H;M|M
            M→d|aHb
7．已构造出文法G（S）
（1）S     BB
（2）B     aB
（3）B      b
1）。给出DFA图
2）.给出LR分析表
3）．假定输入串为abaab，请给出LR分析过程（即状态，符号，输入串的变化过程）。
8． 将下面的语句翻译成四元式序列：
               while A<C∧B<D do
                if A=1 then C:=C+l
                else while A≤ D do
                  A:=A+2；
9． 对下面的流图，
(1)求出流图中各结点N的必经结点集D(n)，
(2)求出流图中的回边，
(3)求出流图中的循环。

参 考 答 案
一．单项选择题
1.    b     将编译程序分成若干个“遍”是为了使编译程序的结构更加清晰，故选b。
2.    d    .构造编译程序应掌握源程序、目标语言及编译方法等三方面的知识，故选d。
3.     c   对编译而言，变量既持有左值又持有右值，故选c。
4.     d    编译程序打交道最多的就是各种表格，因此选d。
5.     c    词法分析器输出的结果是单词的种别编码和自身值，选C。
6.    c   正规式M1和M2所识别的语言集相等，故选C。
7.     c  选c。
8.     b  选b。
9.     c   选C
10.    c  堆式动态分配申请和释放存储空间不一定遵守先请后放和后请先放的原则，故选d

二．简答题
1．        【解答】
    编译程序的总体结构图如图1.2所示。
    词法分析器：输入源程序，进行词法分析，输出单词符号。
    语法分析器：在词法分析的基础上，根据语言的语法规则（文法规则）把单词符号串分
解成各类语法单位，并判断输入串是否构成语法上正确的“程序”。
    中间代码生成器：按照语义规则把语法分析器归约（或推导）出的语法单位翻译成一定
形式的中间代码，比如说四元式。
    优化：对中间代码进行优化处理。
    目标代码生成器：把中间代码翻译成目标语言程序。
    表格管理模块保存一系列的表格，登记源程序的各类信息和编译各阶段的进展情况。编
译程序各阶段所产生的中间结果都记录在表格中，所需信息多数都需从表格中获取，整个编
译过程都在不断地和表格打交道。
    出错处理程序对出现在源程序中的错误进行处理。此外，编译的各阶段都可能出现错误，
出错处理程序对发现的错误都及时进行处理。
2．        【解答】
该句型对应的语法树如下：该句型相对于E的短语有FF^^*；相对于T的短语有FF^^*,F;相对于F的短语有F^;F^^;简单短语有F;F^;句柄为F.
3．        【解答】
最简DFA如图2.66所示。

4．        　【解答】
(1)
        　S→(L)|aS’
        　S’→S|ε
        　L→SL’
        　L’→SL’|ε
      评分细则：消除左递归2分，提公共因子2分。
        (2) FIRST和FOLLOW
        　FIRST)S)＝{(，a}    FOLLOW(S)＝{#，，，)}
        　FIRST(S’)＝{，a,ε}  FOLLOW(S’)＝{#，，，)}
        　FIRST(L)＝{(，a}    FOLLOW(L)＝{ )}
        　FIRST(L’)＝{，，ε}  FOLLOW(L’〕＝{ )}
5．        【解答】
(1)拓广文法
(0)S->A  (1) A->aAd  (2)A-> aAb  (3)A->ε
(2)构造识别活前缀的DFA

FOLLOW(A)={d,b,#}
对于状态I0：FOLLOW(A)∩{a}=Ф
对于状态I1：FOLLOW(A)∩{a}=Ф
因为，在DFA中无冲突的现象，所以该文法是SLR(1)文法。
(3)SLR(1)分析表
状态        ACTION        GOTO
        a        B        d        #        A
0        S2        r3        r3        r3        1
1                                      acc           
2        S2        r3        r3        r3        3
3                  S5        S4                     
4                  r1        r1        r1           
5                  r2        r2        r2           
 
(4)串ab#的分析过程
步骤        状态栈        符号栈        当前字符        剩余字符串        动作
1        0        #        a        b#        移进
2        02        #a        b        #        归约A->ε
3        023        #aA        b        #        移进
4        0235        #aAb        #                  归约A-> aAb
5        01        #A        #                  接受
                                       
6．        【解答】
    由M→d和M→a…得：FIRSTVT(M)=｛d,a｝；
    由H-H;…得：FIRSTVT(H)=｛；｝
    由H→M得：FIRSTVT(M) cFIRSTVT(H)，即FIRSTVT(H)={;,d,a}
    由M→d和M→…b得：LASTVT(M)={d,b}；
    由H---，；m得：LASTVT(H)=｛；｝；
    由H→M得：LASTVT（M）cLASTVT(H），即LASTVT(H)=｛;,d,b}
    对文法开始符H,有#H#存在，即有＃=＃，#<FIRSTVT(H)，LASTVT(H)>#,也即＃＜；，#<d. #<a,；＞＃，d>#, b>#。
    对形如P→…ab…，或P→…aQb…，有a=b，由M→a|b得：a=b；
    对形如P→…aR…，而b∈FIRSTVT(R)，有a<b，对形如P→…Rb…，而a∈LASTVT(R)．
有a>b。
    由H→…；M得：；<FIRSTVT(M)，即：：<d，：<a
    由M→aH…得：a<FIRSTVT(H)，即：a＜；，a<d，a＜a
    由H→H；’’•得：LASTVT(H)>;，即：；＞；，d>；，b＞；
    由M→…Hb得：LASTVT(H)>b，即：；＞b，d>b，b＞b
    由此得到算符优先关系表，见表3.5。

7．        【解答】
（1）LR分析表如下：
（2）分析表

状态        ACTION        GOTO
        a        b        #        S        B
0        s3        s4                1        2
1                        acc               
2        S3        S4                        5
3        s3        s4                        6
4        r3        r3                       
5        R1        R1        r1               
6        R2        R2        R2               

(3) 句子abaab的分析过程
表:句子abaab的分析过程
步骤        状态        符号栈        输入串        所得产生式
0        #0        #        abaad#       
1        #03        #a        baad#       
2        #034        #ab        aab#        B→b
3        #036        #aB        aab#        B→aB
4        #02        #B        aab#       
5        #023        #Ba        ab#       
6        #0233        #Baa        b#       
7        #02334        #Baab        #       
8        #02336        #BaaB        #       
9        #0236        #BaB        ad#       
10        #025        #BB        ad#       
11        #01        #S        d#       
12        #        #        d#       
13        识别成功                       

8．         【解答】
该语句的四元式序列如下（其中E1、E2和E3分别对应：A<C∧B<D, A=1和A≤D并且关系运算符优先级高）：
                100 (j<,A,C,102)
                101(j,_,_,113）                  /*E1为F*/
                102 (j<,B,D,104)                 /*El为T*/源程序能直接执行吗
                103 (j,_,_,113)                  /*El为F*/
                104 (j=,A,1,106)                  /*Ez为T*/
                105 (j,_,_,108）                  /*EZ为F*/
                106 (＋,C,1,C)                     /*C:=C+1*/
                107 (j,_,_,112)                    /*跳过else后的语句*/
                108 (j≤,A,D,110)                    /*E3为T*/
                109 (j,_,_,112)                     /*E3为F*/
                110 (＋,A,2,A)                      /*A:=A+2*/
                111 (j,_,_,108)                      /*转回内层while语句开始处*/
                112(j,_,_,100)                       /*转回外层while语句开始处*/
                113
9．        【解答】
(1)流图中各结点N的必经结点集D(n)，
D(l)＝{1}，D(2)＝{1,2}，D(3)＝{1,2,3}，D(4)={1,2,3,4}，D(5)＝{1,2,5}，
D(6)＝{1,2,5,6}
(2)求出流图中的回边，
5->2，4->3
(3)求出流图中的循环:
回边5->2对应的循环：2、5、3、4；
回边4->3对应的循环：3、4
《编译原理》模拟试题一
一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分）
1．计算机高级语言翻译成低级语言只有解释一种方式。(×)
2．在编译中进行语法检查的目的是为了发现程序中所有错误。(×)
3．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。 (√ )
4．正则文法其产生式为 A->a ， A->Bb,  A,B∈VN ， a 、 b∈VT 。 (×)
5．每个文法都能改写为 LL(1) 文法。 (√)
6．递归下降法允许任一非终极符是直接左递归的。 (√)
7．算符优先关系表不一定存在对应的优先函数。 (×)
8．自底而上语法分析方法的主要问题是候选式的选择。 (×)
9．LR 法是自顶向下语法分析方法。 (×)
10．简单优先文法允许任意两个产生式具有相同右部。 (×)
二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分)
1． 一个编译程序中，不仅包含词法分析，_____，中间代码生成，代码优化，目标代码生成等五个部分。a
　A．( ) 语法分析   B．( )文法分析  C．( )语言分析　D．( )解释分析
2． 词法分析器用于识别_____。  c
　A．( ) 字符串B．( )语句C．( )单词　D．( )标识符
3． 语法分析器则可以发现源程序中的_____。d
　A．( ) 语义错误  　 B．( ) 语法和语义错误
　C．( ) 错误并校正    D．( ) 语法错误
4． 下面关于解释程序的描述正确的是_____。b
　 (1) 解释程序的特点是处理程序时不产生目标代码
　 (2) 解释程序适用于 COBOL 和 FORTRAN 语言
　 (3) 解释程序是为打开编译程序技术的僵局而开发的 
　A．( ) (1)(2)   B．( ) (1)   C．( ) (1)(2)(3)    D．( ) (2)(3)
5． 解释程序处理语言时 , 大多数采用的是_____方法。b
　A．( ) 源程序命令被逐个直接解释执行   　
  B．( ) 先将源程序转化为中间代码 , 再解释执行
　C．( ) 先将源程序解释转化为目标程序 , 再执行   　
  D．( ) 以上方法都可以
6． 编译过程中 , 语法分析器的任务就是_____。b
　 (1) 分析单词是怎样构成的     (2)  分析单词串是如何构成语句和说明的
　 (3) 分析语句和说明是如何构成程序的  (4) 分析程序的结构
　A．( ) (2)(3) B．( ) (2)(3)(4)C．( ) (1)(2)(3) D．( ) (1)(2)(3)(4)
7． 编译程序是一种_____。c
　A. ( ) 汇编程序 B．( ) 翻译程序C．( ) 解释程序  D．( ) 目标程序
8． 文法 G 所描述的语言是_____的集合。 c
　A. ( ) 文法 G 的字母表 V 中所有符号组成的符号串
　B．( ) 文法 G 的字母表 V 的闭包 V* 中的所有符号串
　C．( ) 由文法的开始符号推出的所有终极符串
　D. ( ) 由文法的开始符号推出的所有符号串
9． 文法分为四种类型，即0型、1型、2型、3型。其中3型文法是_____。b
　A. ( ) 短语文法 B．( ) 正则文法C．( ) 上下文有关文法　D．( ) 上下文无关文法
10． 一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 _____。d
　A．( ) 句子 　B．( ) 句型C．( ) 单词   　 D．( ) 产生式
三、填空题(每空1分，共10分)
1．编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析,中间代码生成,代码优化等几个基本阶段,同时还会伴有__表格处理___和 ___出错处理__。
2．若源程序是用高级语言编写的,___目标程序__是机器语言程序或汇编程序,则其翻译程序
称为 ___编译程序__ 。
3．编译方式与解释方式的根本区别在于__是否生成目标代码___。
4．对编译程序而言,输入数据是___源程序__, 输出结果是__目标程序___。
5．产生式是用于定义___语法成分__的一种书写规则。
6．语法分析最常用的两类方法是___自上而下__和___自下而上__分析法。
四、简答题（20分）
1. 什么是句子？ 什么是语言 ?
答：(1)设G是一个给定的文法，S是文法的开始符号，如果S x(其中x∈VT*),则称x是文法的一个句子。
(2)设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为： L(G)＝{x│S x,x∈VT*} 。
参考答案：
(每个2分，共4分)
答：(1)设G是一个给定的文法，S是文法的开始符号，如果S x(其中x∈VT*),则称x是文法的一个句子。
(2)设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为： L(G)＝{x│S x,x∈VT*} 。
2. 写一文法，使其语言是偶正整数的集合,要求：
   (1)允许0打头；
   (2) 不允许0打头。
解：(1)G[S]=({S,P,D,N},{0,1,2,…,9},P,S)
P:
S->PD|D
P->NP|N
D->0|2|4|6|8
N->0|1|2|3|4|5|6|7|8|9
(2)G[S]=({S,P,R,D,N,Q },{0,1,2,…,9},P,S)
P:
S->PD|P0|D
P->NR|N
R->QR|Q
D->2|4|6|8
N->1|2|3|4|5|6|7|8|9
Q->0|1|2|3|4|5|6|7|8|9
3. 已知文法 G[E] 为：
    E→T|E+T|E-T
    T→F|T*F|T/F
    F→ （ E ） |i
① 该文法的开始符号（识别符号）是什么？
② 请给出该文法的终结符号集合 VT 和非终结符号集合 VN 。
③ 出句型 T+T*F+i 的所有短语、简单短语和句柄。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。