下载文档原格式
《编译原理》期末试题（一）一、是非题（请在括号内，正确的划√，错误的划×）（每个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．构造编译程序应掌握______。
《编译原理》模拟试题一一、是非题(请在括号内，正确的划错误的划X)(每个2分，共20分)1•计算机高级语言翻译成低级语言只有解释一种方式。
(X)2.在编译中进行语法检查的目的是为了发现程序中所有错误。
(X)3.甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。
(丁 )4.正则文法其产生式为A->a , A->Bb, A.BGVN , a、beVT o (X)5.每个文法都能改写为LL(1)文法。
(V)6.递归下降法允许任一非终极符是直接左递归的。
(V)7.算符优先关系表不一定存在对应的优先函数。
(X)8.自底而上语法分析方法的主要问题是候选式的选择。
(X)9.LR法是自顶向下语法分析方法。
(X)10.简单优先文法允许任意两个产生式具有相同右部。
(X)二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分)1.一个编译程序中，不仅包含词法分析，_____ ,中间代码生成，代码优化，目标代码生成等五个部分。
A.()语法分析B.()文法分析C.()语言分析D.()解释分析2.词法分析器用于识别_____ oA.()字符串B.()语句C.()单词D.()标识符3 •语法分析器则可以发现源程序中的______ oA.()语义错误B.()语法和语义错误C.()错误并校正D.()语法错误4.下面关于解释程序的描述正确的是。
(1) 解释程序的特点是处理程序时不产生目标代码(2) 解释程序适用于COBOL 和FORTRAN 语言(3) 解释程序是为打开编译程序技术的僵局而开发的A. ( ) (1) (2)B. () (1)C. () (1)⑵(3)D.()⑵⑶5. _________________________________________ 解释程序处理语言时，大多数采用的是 ___________________________________ 方法。
完整word版编译原理考试试题及答案《编译原理》考试试题及答案（附录）一、判断题：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.扫描器的任务是从（）中识别出一个个（）。
编译原理试题一、填空题1、汇编程序将＿＿____＿_翻译成__＿___＿＿；编译程序将________翻译成_＿_＿＿＿__.2、编译程序工作工程可以划分为______、＿__＿__、_＿____、__＿_＿_和＿_＿＿__等5个基本阶段,同时还会伴有_＿＿___和＿__＿_＿。
3、对编译程序而言,输入数据是______,输出数据是______。
4、已知文法G[Ｅ］:Ｅ－>T|E+T|E—F,Ｔ->F|T＊Ｆ|T/Ｆ，Ｆ—＞（Ｅ)｜I,（“，"是间隔符号,不是文法中的符号）．该文法的开始符号（识别字符)是______,终结符号集合V T是____＿_，非终结符号结合V N是_＿＿___,句型Ｔ＋T*F+i的短语有__＿_＿__＿_＿__。
该文法消除直接左递归,改写后的文法为Ｅ－〉___＿__＿＿，Ｔ－〉_＿__＿___，F-＞___＿＿_＿＿.5、Cｈomsky定以来寺中形式语言的文法分别为:＿_______文法（又称____＿___文法）、______＿_文法（又称__＿＿__＿＿文法)、___＿＿＿＿_文法(又称__＿____＿文法）、＿＿______文法（又称________文法)。
6、编译过程中扫描器所完成的任务是从_＿_＿__＿_中识别出一个个具有_＿___＿_＿。
７、确定的有穷自动机是一个___＿____，通常表示为_＿_＿____.8、LL(k）分析中,第一个L的含义是_＿__＿＿__,第二个L的含义是___＿＿＿＿_,“k"的含义是_____＿__。
9、LL(１）分析中，第一个L的含义是____＿＿＿_,第二个L的含义是____＿＿__，“１"的含义是＿_＿_____。
10、LＲ(0)分析中,“L”的含义是_＿_＿＿__＿，“R”的含义是___＿____,“0”的含义是＿_＿__＿__。
1１、SLＲ(1)分析中,“L”的含义是________,“R”的含义是________,“1"的含义是_＿_____＿。
试卷（一）一、选择1.一个正规语言只能对应( B)？A 一个正规文法；B 一个最小有限状态自动机；2.文法G[A]：A→ε A→aB B→Ab B→a是( B)：A 正规文法；B 二型文法；3.下面说法正确的是( A)：A 一个SLR（1）文法一定也是LALR（1）文法；B 一个LR（1）文法一定也是LALR（1）文法4.一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL（1）文法的( A)：A 必要条件B 充分必要条件二、多项选择1.PL/0语言的目标程序解释执行时用到的数据对象有(AC)：A 目标代码CODEB 符号表TABLEC 数据栈SD 关键字表WORD2.PL/0语言编译时产生或使用的数据对象有(ABD)：A 目标代码CODEB 符号表TABLEC 数据栈SD 关键字表WORD三、问答题问答第1题(5分)将文法G[S] 改写为等价的G′[S]，使G′[S]不含左递归和左公共因子。
G[S]：S→bSAe | bAA→Ab | dS→bBB→SAe | AA→d A'A' →bA' | ε问答第2题(10分) 判断下面文法是否为LL(1)文法，若是,请构造相应的LL(1)分析表。
S→aHH→aMd | d M→Ab | ε A→aM | e首先计算文法的 FIRST 集和FOLLOW 集如下表非终结符FIRST 集 FOLLOW 集S {a}......... {# }... H {a ，d}..... {# }... M {a ，e ，ε} {d ，b} A {a ，e}..... {b}....由于select （H→aMd）∩select（H→d）={a}∩{d }=select （M→Ab）∩select（M→ε）={a ，e}∩{d ，b }= select （A→aM）∩select（A→e）={ a }∩{ e }= 所以该文法是LL(1)文法，LL(1)分析表如下表。
《计算机编译原理》试卷A1参考答案一、单项选择题（每小题1分，共25分）1、语言是＿＿＿A＿＿＿A、句子的集合B、产生式的集合C、符号串的集合D、句型的集合2、编译程序前三个阶段完成的工作是＿＿＿C＿＿＿A、词法分析、语法分析和代码优化B、代码生成、代码优化和词法分析C、词法分析、语法分析、语义分析和中间代码生成D、词法分析、语法分析和代码优化3、一个句型中称为句柄的是该句型的最左＿＿＿D＿＿＿A、非终结符号B、短语C、句子D、直接短语4、下推自动机识别的语言是＿＿＿C＿＿＿A、0型语言B、1型语言C、2型语言D、3型语言5、扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即＿＿＿B＿＿＿A、字符B、单词C、句子D、句型6、对应Chomsky四种文法的四种语言之间的关系是＿＿＿B＿＿＿A、L0⊂L1⊂L2⊂L3B、L3⊂L2⊂L1⊂L0C、L3=L2⊂L1⊂L0D、L0⊂L1⊂L2=L37、词法分析的任务是＿＿＿A＿＿＿A、识别单词B、分析句子的含义C、识别句子D、生成目标代码8、常用的中间代码形式不含＿＿＿D＿＿＿A、三元式B、四元式C、逆波兰式D、语法树9、代码优化的目的是＿＿＿C＿＿＿A、节省时间B、节省空间C、节省时间和空间D、把编译程序进行等价交换10、代码生成阶段的主要任务是＿＿＿C＿＿＿A、把高级语言翻译成汇编语言B、把高级语言翻译成机器语言C、把中间代码变换成依赖具体机器的目标代码D、把汇编语言翻译成机器语言11、一个上下文无关文法G包括四个组成部分：一组终结符，一组非终结符，一个开始符号，以及一组＿＿＿B＿＿＿。
A、字符串B、产生式C、数字符号D、文法12、程序的基本块是指＿＿＿D＿＿＿。
A、一个子程序B、一个仅有一个入口和一个出口的语句C、一个没有嵌套的程序段D、一组顺序执行的程序段，仅有一个入口和一个出口13、高级语言编译程序常用的语法分析方法中，递归下降分析法属于＿＿＿B＿＿＿分析方法。
编译原理试题及答案1. 选择题（每题4分，共40分）1) 当编译器在词法分析阶段遇到无法识别的字符时，应该采取的动作是：A. 直接忽略该字符并继续进行词法分析B. 输出错误信息并终止词法分析过程C. 将该字符标记为非法字符并继续词法分析D. 转交给语法分析器进行处理答案：B2) 下列关于语法分析器的描述中，错误的是：A. 语法分析器使用文法规则将输入的记号流转化为推导树B. 语法分析器可以通过自上而下或自下而上的方式进行解析C. LL(1)文法是一种常用于自上而下语法分析的文法形式D. 语法分析器的输入是词法分析器输出的记号流答案：A3) 以下关于语法制导翻译的说法，正确的是：A. 语法制导翻译是在语义分析阶段完成的B. 语法制导翻译通过产生式的属性传递进行信息的传递和计算C. 语法制导翻译只能用于自上而下的语法分析D. 语法制导翻译是在语法分析阶段完成的答案：B4) 在SLR分析算法中，项目集簇的构造过程中需要进行的操作是：A. 闭包操作和移进操作B. 移进操作和规约操作C. 闭包操作和规约操作D. 闭包操作、移进操作和规约操作答案：D5) 下列关于中间代码生成的叙述中，错误的是：A. 中间代码是一种类似于汇编代码的表示形式B. 中间代码可以直接被目标代码生成器所使用C. 中间代码的生成可以采用三地址码的形式D. 中间代码的生成在语法分析和语义分析之后进行答案：B2. 简答题（每题10分，共30分）1) 请简要描述编译器的主要工作流程。
答案：编译器的主要工作流程包括词法分析、语法分析、语义分析、中间代码生成、优化和目标代码生成等阶段。
在词法分析阶段，编译器将输入的源代码转化为一个个记号流。
接下来，在语法分析阶段，编译器使用文法规则对记号流进行分析，并生成语法树或推导树。
在语义分析阶段，编译器对语法树进行语义检查，并进行类型推导和符号表管理等操作。
中间代码生成阶段将经过语义分析的源代码转化为一种中间表示形式，通常是三地址码。
《编译原理》考试试题及答案（汇总）一、是非题（请在括号内，正确的划√，错误的划×）（每个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．构造编译程序应掌握______。
《计算机编译原理》试卷A1参考答案一、单项选择题（每小题1分，共25分）1、语言是＿＿＿A＿＿＿A、句子的集合B、产生式的集合C、符号串的集合D、句型的集合2、编译程序前三个阶段完成的工作是＿＿＿C＿＿＿A、词法分析、语法分析和代码优化B、代码生成、代码优化和词法分析C、词法分析、语法分析、语义分析和中间代码生成D、词法分析、语法分析和代码优化3、一个句型中称为句柄的是该句型的最左＿＿＿D＿＿＿A、非终结符号B、短语C、句子D、直接短语4、下推自动机识别的语言是＿＿＿C＿＿＿A、0型语言B、1型语言C、2型语言D、3型语言5、扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即＿＿＿B＿＿＿A、字符B、单词C、句子D、句型6、对应Chomsky四种文法的四种语言之间的关系是＿＿＿B＿＿＿A、L0⊂L1⊂L2⊂L3B、L3⊂L2⊂L1⊂L0C、L3=L2⊂L1⊂L0D、L0⊂L1⊂L2=L37、词法分析的任务是＿＿＿A＿＿＿A、识别单词B、分析句子的含义C、识别句子D、生成目标代码8、常用的中间代码形式不含＿＿＿D＿＿＿A、三元式B、四元式C、逆波兰式D、语法树9、代码优化的目的是＿＿＿C＿＿＿A、节省时间B、节省空间C、节省时间和空间D、把编译程序进行等价交换10、代码生成阶段的主要任务是＿＿＿C＿＿＿A、把高级语言翻译成汇编语言B、把高级语言翻译成机器语言C、把中间代码变换成依赖具体机器的目标代码D、把汇编语言翻译成机器语言11、一个上下文无关文法G包括四个组成部分：一组终结符，一组非终结符，一个开始符号，以及一组＿＿＿B＿＿＿。
A、字符串B、产生式C、数字符号D、文法12、程序的基本块是指＿＿＿D＿＿＿。
A、一个子程序B、一个仅有一个入口和一个出口的语句C、一个没有嵌套的程序段D、一组顺序执行的程序段，仅有一个入口和一个出口13、高级语言编译程序常用的语法分析方法中，递归下降分析法属于＿＿＿B＿＿＿分析方法。
<编译原理>历年试题及答案一．（每项选择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/d9．程序所需的数据空间在程序运行前就可确定，称为____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|aL→L，S|S(1)消除左递归和回溯；(2)计算每个非终结符的FIRST和FOLLOW；(3)构造预测分析表。
(V)编译原理》期末试题(一)LR 分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。
10．一个语义子程序描述了一个文法所对应的翻译工作。
二、选择题 (请在前括号内选择最确切的一项作为答案划一个勾，多划按错论1．词法分析器的输出结果是2. 正规式 M 1 和 M 2 等价是指( ) 可能存在两个不同的最左推导，但它们对应的语法树相同 5.构造编译程序应掌握C . ( ) 编译方法D . ( ) 以上三项都是A . ( ) 指示器 B. ( ) 临时变量C. ( ) 符号表D. ( ) 程序变量6.四元式之间的联系是通过 实现的。
一、是非题(请在括号内，正确的划V 错误的划X)每个 2 分，共 20 分)1．编译程序是对高级语言程序的解释执行。
(X)2．一个有限状态自动机中，有且仅有一个唯一的终态。
( X)3．一个算符优先文法可能不存在算符优先函数与之对应。
(V)4．语法分析时必须先消除文法中的左递归 。
(X) 5． 6．逆波兰表示法表示表达式时无须使用括号。
(V) 7．静态数组的存储空间可以在编译时确定。
( X)8．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。
( X)9． 两个正规集相等的必要条件是他们对应的正规式等价。
( X) ( X))(每个 4 分，共 40分)A ．( ) 单词的种别编码B ． ( ) 单词在符号表中的位置C ． ( ) 单词的种别编码和自身值D ． ( ) 单词自身值A . ( ) M1和M2的状态数相等B ． ( ) M1 和 M2 的有向边条数相等C ．( ) M1 和 M2 所识别的语言集相等D ．( ) M1 和 M2 状态数和有向边条数相等3.文法G : S T xSx|y 所识别的语言是A . ( ) xyxB . ( ) (xyx)*C . ( ) xnyxn(n > 0)D . ( ) x*yx*4. 如果文法G 是无二义的，则它的任何句子A . ( )最左推导和最右推导对应的语法树必定相同B . ( ) 最左推导和最右推导对应的语法树可能不同C . ( ) 最左推导和最右推导必定相同D . A . ( )源程序B . ( ) 目标语言7.表达式(「AV B) A (CV D)的逆波兰表示为 。
《编译原理》考试试题及答案（汇总）一、是非题（请在括号内，正确的划√，错误的划×）（每个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．构造编译程序应掌握______。
《编译原理》期末试题（一）一、是非题（请在括号内，正确的划√，错误的划×）（每个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．构造编译程序应掌握______。
《编译原理》期末试题（一）一、是非题（请在括号内，正确的划√，错误的划×）（每个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．构造编译程序应掌握______。
杭电编译原理试卷一及答案试卷（一）一、选择1.一个正规语言只能对应( B)？A 一个正规文法；B 一个最小有限状态自动机；2.文法G[A]：A→ε A→aB B→Ab B→a是( B)：A 正规文法；B 二型文法；3.下面说法正确的是( A)：A 一个SLR（1）文法一定也是LALR（1）文法；B 一个LR（1）文法一定也是LALR（1）文法4.一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL（1）文法的( A)：A 必要条件B 充分必要条件二、多项选择1.PL/0语言的目标程序解释执行时用到的数据对象有(AC)：A 目标代码CODEB 符号表TABLEC 数据栈SD 关键字表WORD2.PL/0语言编译时产生或使用的数据对象有(ABD)：A 目标代码CODEB 符号表TABLEC 数据栈SD 关键字表WORD三、问答题问答第1题(5分)将文法G[S] 改写为等价的G′[S]，使G′[S]不含左递归和左公共因子。
G[S]：S→bSAe | bAA→Ab | dS→bBB→SAe | AA→d A'A' →bA' | ε问答第2题(10分) 判断下面文法是否为LL(1)文法，若是,请构造相应的LL(1)分析表。
S→aHH→aMd | dM→Ab | εA→aM | e首先计算文法的 FIRST集和FOLLOW集如下表非终结符FIRST集FOLLOW集S {a}.........{# }...H {a ，d}.....{# }...M {a ，e ，ε}{d ，b}A {a ，e}.....{b}....由于select（H→aMd）∩select（H→d）={a}∩{d }=select（M→Ab）∩select（M→ε）={a ，e}∩{d ，b }=select（A→aM）∩select（A→e）={ a }∩{ e }=所以该文法是LL(1)文法，LL(1)分析表如下表。
LL(1)分析表a db e # S →aH.H →aMd→d.M →Ab.→ε→ε→AbA →aM.→e.问答第3题给出与正规式R＝（ab）*（a|b*）ba等价的NFA。
问答第4题将下图的NFA确定化为DFA。
用子集法对所给图的确定化I Ia Ib 状态{X,1,2} {1,2}..{1,2,3} X{1,2}.. {1,2,3} {1,2,Y} {1,2}..{1,2,Y}{1,2}..{1,2,3}{1,2,3}{1,2,3}123确定化后如下图问答第5题(7分)（1）给出下列PL/0示意程序中当程序执行到X过程调用Z过程后（即执行Z 过程体时）的栈式存储分配布局和用Display显示表时Z过程最新活动记录的内容。
（2）说明Display表和DL（老SP）,RA,TOP及全局Display的作用。
PL/0示意程序为：const a=80;var b,c;procedure X;var d;procedure Z;var e,g;begin (* Z *)c:=b*a；end ；(* Z *)begin (* X *)call Z;end ；(* X *)procedure Y;var f;begin (* Y *)call X;end ；(* y *)begin (* main *)call Y;end. (* main *)解：（1）当程序执行到X过程调用Z过程后（即执行Z过程体时）的栈式存储分配布局和用Display显示表时Z过程最新活动记录的内容如下图。
解：（2）Display表和DL（老SP）,RA,TOP及全局Display的作用分别说明如下：·Display表的作用是对嵌套过程语言实现对非局部变量的引用而设置的，它依次存放着包围它的外过程的最新活动记录的基地址SP值，由于，嵌套层次为i+1过程中的非局部变量可能在i，i-1，…，0层，所以，对非局部变量的引用是通过它的display表元素d[i]，d[i- 1]，…，d[0]而获得包围它的外过程的最新活动记录的基地址SP值，再加上变量在该过程（第i层）的偏移量。
如若非局部变量a是在第i层，那么引用a 时，首先从当前栈顶过程的display表中元素d[i]中取出存放的第i层最新活动记录基地址SP值，然后加上a所在过程（第i层）的偏移量，就得到a 的存放地址。
d（2）Z的SPd（1）X的SPd（0）Main的SP段基地址，用以过程执行结束释放数据空间时，恢复调用该过程前运行栈的状态。
·RA：返回地址，记录调用该过程时目标程序的断点，即调用过程指令的下一条指令的地址，用以过程执行结束后返回调用过程时的下一条指令继续执行。
·TOP：栈顶指针TOP指出了当前栈中最新分配的单元。
·全局Display是存放本过程display表的起始地址，其作用是把display地址作为连接数据之一，如过程P1调用过程P2时，这时先从 P1的全局Display找到P1的display表起始地址，然后从P1的display表中自底向上地抄录I2个单元（I2为P2的层数）再添上进入 P2后新建立的P2的SP值，就构成了P2的display表。
问答第6题(5分)给出问答第5题PL/0示意程序编译到Y过程体时TABLE表的内容。
解：PL/0示意程序编译到Y过程体时TABLE表的内容如下表。
解：TABLE表的内容name kind level val adr sizemain a b c X Y f procedureconstantvariablevariableprocedureprocedurevariable..1.80.dxdx+1过程X的入口过程Y的入口dx5...44由于Y和X是并列过程，当编译到Y过程时X过程体已经编译结束，X所定义的标识符不会再被使用，所以X定义的标识符d 、Z及Z定义的e、g都被Y过程定义的标识符覆盖。
问答第7题(10分)某语言的拓广文法G′为：(0) S′→T(1) T →aBd|ε(2) B →Tb|ε证明G不是LR(0)文法而是SLR(1)文法，请给出SLR(1)分析表。
解：在项目集I0中：有移进项目T →·aBd和归约项目T →·存在移进-归约冲突，所以G不是LR(0)文法。
若产生式排序为：(0) S'→T(1) T →aBd(2) T →ε(3) B →Tb(4) B →εG'的LR(0)项目集族及识别活前缀的DFA如下图所示：识别G′活前缀的DFA：由产生式知：Follow(T)={#,b}Follow(B)= {d}在I0中：Follow(T) ∩{a}={# ，b} ∩{a}=在I2中：Follow(B) ∩{a}= {d} ∩{a}=Follow(T) ∩{a}={# ，b} ∩{a}=Follow(B) ∩ Follow(T) = {d}∩{# ，b}=所以在I0，I2，中的移进-归约和归约-归约冲突可以由Follow集解决，所以G 是SLR(1)文法。
构造的SLR(1)分析表如下表。
nameACTION GOTOa b d # T B0 S2 r2 r2 11 acc2 S2 r2 r4 r2 4 33 S54 S65 r1 r16 r3问答第8题(5分)给出文法G[S]的LR(1)项目集规范族中I0项目集的全体项目。
G[S]为：S →BD|DB →aD|bD →BI0:解:I0问答第9题(5分)文法G[M]及其LR分析表如下，请给出对串dbba#的分析过程。
G[M]: 1) M →VbA 2) V →d3) V →ε 4) A →aACTION GOTOb d a # M A V0 r3 S3 1 21 acc2 S43 r24 r6 S5 r6 65 r4 r46 S7 r17 S88 r5 r5解：对输入串dbba#的分析过程步骤状态栈文法符号栈剩余输入符号动作1 2 3 4 00302024##d#V#Vbdbba#bba#bba#ba#移进用V →d归约移进用A →ε归约5 6 7 8 9 024602467024678024601#VbA#VbAb#VbAba#VbA#Mba#a####移进移进用A →Aba 归约用M →VbA 归约接受问答第10题（5分）文法G[E]为：E→E+T|TT→T*F|FF→(E)|i试给出句型(E+F)*i的短语，简单(直接)短语,句柄和最左素短语。
解：短语有: (E+F)*i ，(E+F) ，E+F ，F ，i简单(直接)短语有: F ，i句柄是: F最左素短语是: E+F问答第11题（6分）按指定类型给出下列语言的文法。
(1)L1={ anbm c| n≥0,m>0 } 用正规文法。
(2) L2={ a0n1n bdm | n>0，m >0} 用二型文法。
(1) 解：描述L1语言的正规文法如下：S→ aS|AA → bA|bBB →c(2) 解：描述L2语言的二型文法如下：S→ ABA →aTT →0T1|01B →bDD →dD|d问答第12题（6分）试对 if (ad) then s:=e else s:=f 的四元式序列给出第四区段应回填的指令地址，并指出真假出口链和链头及回填的次序。
应回填的值回填的次序(1) if a<b goto ( ) ( ) 真链头 E.true=(2) goto ( ) ( ) 真出口链( )(3) if a>d goto ( ) ( )(4) goto ( ) ( ) 假链头 E.false=(5) s:=e 假出口链( )(6) goto ( ) ( )(7) s:=f(8) ...解：应回填的值回填的次序(1) if a<b goto ( 3 ) ( 1 ) 真链头 E.true= 3(2) goto ( 7 ) ( 4 ) 真出口链( 3 )(3) if a>d goto ( 5 ) ( 2 )(4) goto ( 7 ) ( 3 ) 假链头 E.false= 4(5) s:=e 假出口链( 4,2 )(6) goto ( 8 ) ( 5 )(7) s:=f(8) ...。
