清华大学1997年研究生入学考试编译原理试题

《编译原理》考试试题及答案（附录）一、判断题：1.一个上下文无关文法的开始符，可以是终结符或非终结符。

( X )2.一个句型的直接短语是唯一的。

( X )3.已经证明文法的二义性是可判定的。

（ X ）4.每个基本块可用一个DAG表示。

（√）5.每个过程的活动记录的体积在编译时可静态确定。

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

（ x ）7.一个句型一定句子。

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

(应是最左素短语) ( X )9.采用三元式实现三地址代码时，不利于对中间代码进行优化。

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

( x )11.一个优先表一定存在相应的优先函数。

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

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

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

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

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

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

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

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

( )20.一个优先表一定存在相应的优先函数。

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

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

( )二、填空题：1.( 最右推导 )称为规范推导。

2.编译过程可分为（词法分析），（语法分析），（语义分析和中间代码生成），（代码优化）和（目标代码生成）五个阶段。

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

4.从功能上说，程序语言的语句大体可分为（）语句和（）语句两大类。

5.语法分析器的输入是（），其输出是（）。

6.扫描器的任务是从（）中识别出一个个（）。

清华大学1997硕士入学编译原理试题清华大学1997年研究生入学考试编译原理试题（共50分）1．(8分)已知正规式（1）(（a|b）* |aa)*b和正规式（2）（a|b）*b,试用有限自动机的等价性证明正规式（1）和（2）是等价的,给出相应的正规文法。

2．(8分)已知文法G [A ]为：A→aABl|aB→Bb|d① 试给出与G[A]等价的LL（1）文法G[A]② 构造G'[A]的预测分析表给出输入串aade#的分析过程。

3．(8分)有文法G[S]为：S→a|b|（A）A→SdA|S完成下列算符优先关系表，并判断G[S]是否为算符优先文法。

G[S]的算符优先关系表表1 算符优先关系表① 给出句型（sdsds）的短语，简单短语句柄，素短语和最大素短语。

② 给出输入串（adb）＃的分析过程。

4． (8分)已知文法G[S]为：S→aAd|；Bd|aB↑|；A↑A→aB→a① 试判断G[S]是否为LALR（1）文法② 当一个文法是LR（1）而不是LALR（1）时，那么LR（1）项目集的同心集合并后会出现哪几种冲突，请说明理由。

5．(6分)试对下面基本块进行优化① 应用DAG对该基本块进行优化，给出优化后的语句序列。

② 给出当只有L在基本块出口后为活跃时的优化结果。

基本块为：X=B＊CY=B/CZ=X+YW=9＊Z6．(6分)已知文法G[S]为：S→dABA→aA|aB→Bb|ε① 试向G[S]是否为正规文法，为什么？② G[S]新产生的语言是什么？G[S]能否改写为等价的正规文法？7．(6分)某语言允许过程嵌套定义和逆归调用（如PACAL语言），若在栈式动态存分配中采用嵌套层次显示表Display解决对非局部变量的引用问题，试给出下列程序执行到语句“b：=10；”时运行栈及Display 表的示意图。

var x, y;procedurc p;var a;procedure q;var b;begin(q)b : =10;end (q);procedure s;var c,d;procedure r;var e, f;begin (r)call q;edn (r);begin (s)call r;end (s);begin (p)call s;end (p);begin (main)call p;end (main).。

1、已知文法：A → aAd|aAb|ξ判断该文法是否是SLR（1）文法，若是构造相应分析表，并对输入串 #ab# 给出分析过程。

解：(0) A’→ A(1)A → aAd(2) A → aAb(3) A →ξ构造该文法的活前缀DFA：由上图可知该文法是SLR（1）文法。

构造SLR（1）的分析表：3、考虑文法：S →AS|b A→SA|aFollow(A) = first(S) = {b}+first(A)= {a,b}(1)列出这个文法的所有LR（0）项目(2)按（1）列出的项目构造识别这个文法活前缀的NFA，把这个NFA确定化为DFA，说明这个DFA的所有状态全体构成这个文法的LR（0）规范族。

(3)这个文法是SLR的吗？若是，构造出它的SLR分析表。

(4)这个文法是LALR或LR（1）的吗？解：（0）S’→S (1)S→AS (2)S→b (3)A→SA (4)A→a(1)列出所有LR（0）项目：S’→·S S→·b A→·a S’→ S· S→b· A→a·S →·AS A→·SAS →A·S A→S·AS →AS· A→SA·(3)构造该文法的活前缀NFA：由上可知：I1 I3 I5 中存在着移进和归约冲突在I1中含项目：S’→ S·归约项 Follow(S’)={#}A →·a 移进项 Follow(S’)∩{a}=∮S →·b 移进项 Follow(S’)∩{b}=∮在I3中含项目：A →SA·归约项 Follow(A)={a,b}S →·b 移进项 Follow(A) ∩ {b}≠∮A →·a 移进项 Follow(A) ∩ {a}≠∮在I5中含项目：S →AS·归约项 Follow(S)={#,a,b}A →·a 移进项 Follow(S) ∩ {a}≠∮S →·b 移进项 Follow(S) ∩ {b }≠∮由此可知，I3、I5的移进与归约冲突不能解决，所以这个文法不是SLR （1）文法。

第1章引论第1题解释下列术语：（1）编译程序（2）源程序（3）目标程序（4）编译程序的前端（5）后端（6）遍答案：（1） 编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。

（2） 源程序：源语言编写的程序称为源程序。

（3） 目标程序：目标语言书写的程序称为目标程序。

（4） 编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。

通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符号表管理等工作。

（5） 后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。

（6） 遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。

第2题一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。

答案：一个典型的编译程序通常包含8个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。

其各部分的主要功能简述如下。

词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。

语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。

语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。

中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代码，如三元式或四元式。

中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。

目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。

表格管理程序：负责建立、填写和查找等一系列表格工作。

表格的作用是记录源程序的各类信息和编译各阶段的进展情况，编译的每个阶段所需信息多数都从表格中读取，产生的中间结果都记录在相应的表格中。

//东南大学一、文法G1： E→ET+|T T→TF*|F F→FP↑|P P→E|i 1、试证明符号串TET+*i↑是G1的一个句型（要求画出语法树）。

2、写出该句型的所有短语，简单短句和句柄。

三、 1、试写出一个上下文无关文法G3，它能产生配对的圆括号串（例如，（），（（）），（）（（））等，甚至包含0对括号）。

2、使用文法G3给出输入串（（））（）#的自上而下分析过程。

四、已知文法G4： S→aAb|Sc|ε A→aAb|ε 1、给出G4文法的LR（0）项目集规范族； 2、构造SLR分析表； 3、G4文法所定义的语言； 4、已知有如下文法及相应的LR分析表，试给出语句01001#的LR分析过程（填写下表）。

S→AAA A→1A A→0五、 1、翻译下面语句成四元式中间代码序列和后缀式（逆波兰式）； while x+y>a do if a<10 then a：=a+1 else x：=x-1； 2、翻译布尔表达式 （a>b） or （c=d） and not （e<f） 成转移四元式序列（即四元式中仅包含（zθ，-，-，-）和（j，-，-，-）两类语句，其中θ为关系运算符。

）一、判断下列命题的真假，并简述理由：（20分） 1、文法G的一个句子对应于多个推导，则G是二义的。

2、LL（1）分析必须对原有文法提取左因子和消除左递归。

3、算符优先分析法采用“移近-归约”技术，其归约过程是规范的。

4、文法S→aA；A→Ab；A→b是LR（0）文法（S为文法的开始符号）。

5、一个BASIC解释程序和编译程序的不同在于，解释程序由语法制导翻译成目标代码并立即执行之，而编译程序需产生中间代码及优化。

二、设计一个最小状态有穷自动机，识别由下列子串组成的任意字符串。

（20分） GO，GOTO，TOO，ON 例如：GOTOONGOTOOGOON是合法字符串。

三、构造一个LL（1）文法G，识别语言L：（20分） L={ω|ω为{0，1}上不包括两个相邻的1的非空串} 并证明你的结论。

《编译原理1》习题V12一、单项选择题1.编译程序是一种（ A ）软件。

A.系统B.应用C.MISD.ERP2.BNF是一种广采用的（ C ）的工具。

A.描述规则B.描述语言C.描述文法D.描述句子3.无符号常数的识别和拼数工作通常在（B ）阶段完成。

A.词法分析B.语法分析C.语义分析D.代码生成4.“运算符与运算对象类型不匹配”属于（B ）。

A.语法错误B.语义错误C.语用错误D.词法错误5.一遍扫描的编译程序的优点是（D ）。

A.算法清晰B.便于分工C.便于优化D.编译速度快6.编译程序生成的目标代码程序（A ）是可执行的程序。

A.不一定B.一定C.一定不D.必须经链接装配后7.编译程序是对（D ）。

A.汇编程序的翻译B.高级语言的解释执行C.机器语言的执行D.高级语言的翻译8.测试一个编译程序时使用的测试数据是（A ）。

A.源程序B.中间代码C.目标代码D.任意数据9.由“非终结符→符号串”形式的规则构成的文法是（C ）。

A.0型文法B.1型文法C.2型文法D.3型文法10.文法识别符号经过任意步推导得到的结果是（A ）。

A.句型B.句柄C.句子D.短语11.关于短语和句柄，正确的描述是（B ）。

A.短语就是句柄B.直接短语才可能是句柄C.最左短语一定是句柄D.最右短语一定是句柄12.一个语言的文法是（C ）。

A.唯一的B.不唯一的C.个数有限的D.无数个13.文法G所描述的语言是（ D ）集合。

A.文法G的字母表V中所有符号组成的符号串B.文法G的字母表V的闭包V*中的所有符号串C.由文法的开始符号推出的所有符号串D.由文法的开始符号推出的所有的终结符号串14.文法分为四种类型：0型文法、1型文法、2型文法、3型文法，其中3型文法是（B）。

A.短语文法B.正规文法C.上下文有关文法D.上下文无关文法15.一个上下文无关文法包含四个部分，一组非终结符，一组终结符，一个开始符号以及一组（ C ）。

《编译原理》考试试题及答案（汇总）一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分）1.编译程序是对高级语言程序的解释执行。

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

(×)3.一个算符优先文法可能不存在算符优先函数与之对应。

(√ )4.语法分析时必须先消除文法中的左递归。

(×)5.LR 分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。

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

(√ )7.静态数组的存储空间可以在编译时确定。

(×)8.进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。

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

(× )10.一个语义子程序描述了一个文法所对应的翻译工作。

(×)二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4 分，共40 分) 1．词法分析器的输出结果是。

A．( ) 单词的种别编码B．( ) 单词在符号表中的位置C．( ) 单词的种别编码和自身值D．( ) 单词自身值2.正规式M 1 和M 2 等价是指。

A．( ) M1 和M2 的状态数相等B．( ) M1 和M2 的有向边条数相等C．( ) M1 和M2 所识别的语言集相等D．( ) M1 和M2 状态数和有向边条数相等3.文法G：S→xSx|y 所识别的语言是。

A．( ) xyx B．( ) (xyx)* C．( ) xnyxn(n≥0)D．( ) x*yx*4．如果文法G 是无二义的，则它的任何句子α。

A．( )最左推导和最右推导对应的语法树必定相同B．( ) 最左推导和最右推导对应的语法树可能不同C．( ) 最左推导和最右推导必定相同D．( )可能存在两个不同的最左推导，但它们对应的语法树相同5．构造编译程序应掌握。