下载文档原格式
《编译原理》考试试题及答案（附录）一、判断题：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.扫描器的任务是从（）中识别出一个个（）。
东 北 大 学秦 皇 岛 分 校课程名称： 编译原理 试卷： (B )答案 考试形式： 闭卷授课专业： 计算机科学与技术 考试日期： 年 月 日 试卷：共 2 页 题号 一 二 三 四 总分得分 阅卷人一、填空题（每空2分，共30分）1、编译程序的整个过程可以从逻辑上划分为词法分析、 语法分析 、语义分析、中间代码生成、 代码优化 和目标代码生成等几个阶段，另外还有两个重要的工 作是 理 和出错处理。
表格管2、规范规约中的可归约串是 句柄 ，算符优先分析中的可归约串是 最左素短语 。
3、语法分析方法主要可分为 自顶向下 和 自底向上 两大类。
4、LR （0）文法的项目集中不会出现 移进-归约 冲突和 归约-归约 冲突。
5、数据空间的动态存储分配方式可分为 栈式 和 堆式 两种。
6、编译程序是指能将 源语言 程序翻译成 目标语言 程序的程序。
7、确定有穷自动机DFA 是 NFA 的一个特例。
8、表达式 (a+b)*c 的逆波兰表示为 ab+c* 。
二、选择题（每题2分，共20分）1、LR 语法分析栈中存放的状态是识别 B 的DFA 状态。
A 、前缀B 、可归前缀C 、项目D 、句柄 2、 D 不可能是目标代码。
A 、汇编指令代码B 、可重定位指令代码C 、绝对机器指令代码D 、中间代码 3、一个控制流程图就是具有 C 的有向图A 、唯一入口结点B 、唯一出口结点C 、唯一首结点D 、唯一尾结点 4、设有文法G[S]：S →b|bBB →bS ，则该文法所描述的语言是C 。
A 、L （G ）={b i |i ≥0}B 、L （G ）={b 2i |i ≥0}C 、L （G ）={b 2i+1|i ≥0}D 、L （G ）={b 2i+1|i ≥1}5、把汇编语言程序翻译成机器可执行的目标程序的工作是由 B 完成的。
A 、编译器B 、汇编器C 、解释器D 、预处理器 6、在目标代码生成阶段，符号表用于 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．构造编译程序应掌握______。
此文档下载后即可编辑编译原理考试题及答案汇总一、选择1．将编译程序分成若干个“遍”是为了_B__。
A . 提高程序的执行效率B.使程序的结构更加清晰C. 利用有限的机器内存并提高机器的执行效率D.利用有限的机器内存但降低了机器的执行效率2．正规式 MI 和 M2 等价是指__C__。
A . MI 和 M2 的状态数相等和 M2 的有向弧条数相等。
C .M1 和 M2 所识别的语言集相等 D. Ml 和 M2 状态数和有向弧条数相等3．中间代码生成时所依据的是 _C_。
A．语法规则 B．词法规则 C．语义规则 D．等价变换规则4．后缀式 ab+cd+/可用表达式__B_来表示。
A． a+b/c+d B．(a+b)/(c+d) C． a+b/(c+d) D． a+b+c/d6．一个编译程序中，不仅包含词法分析，_A____，中间代码生成，代码优化，目标代码生成等五个部分。
A．( ) 语法分析 B．( )文法分析 C．( )语言分析 D．( )解释分析7．词法分析器用于识别__C___。
A．( ) 字符串 B．( )语句 C．( )单词 D．( )标识符8．语法分析器则可以发现源程序中的___D__。
A．( ) 语义错误 B．( ) 语法和语义错误C．( ) 错误并校正 D．( ) 语法错误9．下面关于解释程序的描述正确的是__B___。
(1) 解释程序的特点是处理程序时不产生目标代码(2) 解释程序适用于 COBOL 和 FORTRAN 语言(3) 解释程序是为打开编译程序技术的僵局而开发的A．( ) (1)(2) B．( ) (1) C．( ) (1)(2)(3) D．( ) (2)(3)10．解释程序处理语言时 , 大多数采用的是__B___方法。
A．( ) 源程序命令被逐个直接解释执行B．( ) 先将源程序转化为中间代码 , 再解释执行C．( ) 先将源程序解释转化为目标程序 , 再执行D．( ) 以上方法都可以11．编译过程中 , 语法分析器的任务就是__B___。
注意：答案请写在考试专用答题纸上，写在试卷上无效。
（本卷考试时间100分钟）一、填空题（每小题2分，共20分）1. 若源程序是用高级语言编写的，目标程序是_机器语言程序_则其翻译程序是_编译程序_。
2. 编译程序的工作有六个阶段，同时还拌有_表格处理_和_出错处理_。
3. 一个句型中的最左_简单短语_称为该句型的句柄。
4. α是符号串集，则{ε}α=__________=__________。
5. A是符号串集，而A的二次方幂为{aa,ab, ______ba____, _______bb___}，其中A={a,b}。
6. 有文法：Z→ABC , C→a , A→a , B→bB|Bb|b，则终极符为：_____ab_____，非终极符为：_____AB_____。
7. 四种文法的关系：____0型包含1型包含2型包含3型_____。
8. 自底向上分析又可分为__优先分析_和_ LR分析_。
9. 自顶向下分析法也称为面向目标的分析法，其又可分为___确定__和____不确定______两种。
10. 请写出表达式：a+b*(c+d/e)的逆波兰式：__ abcde/+*+_。
二、选择题（每小题2分，共20分）1. 下列有关标识符和名字的叙述中，正确的为【】A. 标识符有一定的含义B. 名字是一个没有意义的字符序列C. 名字有确切的属性D. 都不对2. 编译过程中，词法分析阶段的任务是【】A. 识别表达式B. 识别语言单词C. 识别语句D. 识别程序3. 设有一文法G[E]: 【】E→E+T|E-T|TT→T*F|T/F|FF→(E)|i该文法句型E+T*F的句柄是：______A. EB. E+TC. T*FD. E+T*F4. 程序基本块是指：【】A. 一个子程序B.一个仅有一个入口和一个出口的语句C. 一个没有嵌套的程序段D.一组顺序执行的程序段，仅有一个入口和一个出口5. 过程调用时，参数的传递方法通常有：【】①传值; ②传地址; ③传结果; ④传名A. ①②B. ①②③C. ①②④D. ①②③④6. 程序设计语言的词法分析器可用______来实现。
《编译原理》期末试题（一）一、是非题（请在括号内，正确的划√，错误的划×）（每个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．构造编译程序应掌握______。
编译原理试题B一、单项选择题（每题1分，共20分）1、对编译系统有关概念描述正确的是（ B）A．目标程序只能是机器语言 B. 编译程序处理的对象是源语言C．解释程序属于编译程序 D. 词法分析无法自动进行2. 设有表达式a*b-c，将其中a*b识别为表达式的编译阶段是什么（B）A．词法分析 B. 语法分析C．语义分析 D. 代码生成3. 下面不能用于对文法进行描述的是（A ）A．源语言 B. EBNF C．BNF D. 语法图4. 设有文法G[S]: S→0S|1A|0，A→1|1S|0B，B→1A|0B，下列符号串中是该文法的句子的是（）？A．1010001001101 B.0101001110010010C．1101010011110111 D.1010011101101010(可画出DFA验证)5. 文法G[S]:S→aA|bC|aA→aS|bBB→aC|bA|bC→aB|bS ,则不是L(G)句子的是（ B ）A．a100b50ab100 B. a1000b500abaC．a500b60aab2a D. a100b40ab10aa（画出DFA）6. 哪个不是DFA的构成成分（B）A．有穷字母表 B. 初始状态集合C．终止状态集合 D. 有限状态集合7.词法分析器的输入是（ B ）A．单词符号串 B.源程序 C．语法单位 D.目标程序8.在词法分析阶段不能识别的是（C ）A．标识符 B. 运算符 C．四元式 D. 常数9.设有一段C语言程序while(i&&++j){c=2.19;j+=k;i++;} ,经过词法分析后可以识别的单词个数是（B ）A．19 B.20 C．21 D.2310．自上而下语法分析的主要动作是（ B ）A．移进 B. 推导 C．规约 D. 匹配11.下面不属于LL(1)分析器的自称部分是（ D ）A．LL(1)总控程序 B. LL(1)分析表C．分析栈 D.源程序串12.设有文法G[S]为S→AB|bC， A→ε|b，B→ε|aD，C→AD|b，D→aS|c则FOLLOW(A)为（A ）A．{a,c,#} B.{c,#} C．{a,#} D.{#}13.设有文法G[S]:S→Ap|Bq，A→a|cA，B→b|dB ，则FIRST(Ap)为（ C ）A．{p,q} B. {b,d} C．{a,c} D. 其他14.自下而上语法分析的主要分析动作是（D ）A．推导 B. 规约 C．匹配 D. 移进-规约15.算法优先分析中，可规约串是（ C ）A．句柄 B．活前缀 C．最左素短语 D．素短语16. 设有文法G={{S},{a},{S→SaS|ε},S}，该文法是（ B ）A．LL(1)文法 B．二义性文法C．SLR(1)文法 D．算法优先文法17、中间代码生成时所以据的是（C ）A．语法规则 B．词法规则 C．语义规则D．等价变换规则18、给定文法G: E→E+T|T，T→T*F|F，F→i|(E)则L(G)中的一个句子i+i+(i*i)*i的逆波兰表示为（ C ）A．iii*i++ B．ii+iii**+ C．ii+ii*i*+ D．其他19．在编译程序中与生成中间代码的目的无关的是（B ）A．便于目标代码优化 B．便于存储空间的组织C．便于目标代码的移植 D．便于编译程序的移植20．中间代码是介于源语言程序和什么之间的一种代码（ D）A．源代码 B. 机器语言 C. 汇编语言 D. 目标代码二．简答（每题3分，共12分）1. 什么是解释程序？解释程序也是一种翻译程序，它将源程序作为输入并执行之，即边解释边执行。
编译原理考试题及答案汇总一、选择1．将编译程序分成若干个“遍”是为了_B__。
A . 提高程序的执行效率B.使程序的结构更加清晰C. 利用有限的机器内存并提高机器的执行效率D.利用有限的机器内存但降低了机器的执行效率2．正规式 MI 和 M2 等价是指__C__。
A . MI 和 M2 的状态数相等 B.Ml 和 M2 的有向弧条数相等。
C .M1 和 M2 所识别的语言集相等 D. Ml 和 M2 状态数和有向弧条数相等3．中间代码生成时所依据的是 _C_。
A．语法规则 B．词法规则 C．语义规则 D．等价变换规则4．后缀式 ab+cd+/可用表达式__B_来表示。
A． a+b/c+d B．(a+b)/(c+d) C． a+b/(c+d) D． a+b+c/d6．一个编译程序中，不仅包含词法分析，_A____，中间代码生成，代码优化，目标代码生成等五个部分。
A．( ) 语法分析 B．( )文法分析 C．( )语言分析 D．( )解释分析7．词法分析器用于识别__C___。
A．( ) 字符串 B．( )语句 C．( )单词 D．( )标识符8．语法分析器则可以发现源程序中的___D__。
A．( ) 语义错误 B．( ) 语法和语义错误C．( ) 错误并校正 D．( ) 语法错误9．下面关于解释程序的描述正确的是__B___。
(1) 解释程序的特点是处理程序时不产生目标代码(2) 解释程序适用于 COBOL 和 FORTRAN 语言(3) 解释程序是为打开编译程序技术的僵局而开发的A．( ) (1)(2) B．( ) (1) C．( ) (1)(2)(3) D．( ) (2)(3)10．解释程序处理语言时 , 大多数采用的是__B___方法。
A．( ) 源程序命令被逐个直接解释执行B．( ) 先将源程序转化为中间代码 , 再解释执行C．( ) 先将源程序解释转化为目标程序 , 再执行D．( ) 以上方法都可以11．编译过程中 , 语法分析器的任务就是__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)构造预测分析表。
考试试卷
开课单位：计算机科学与技术学院考试课程：编译原理考试学年、学期：2010-2011-1 试卷编号：200811114320-01
试卷类型：B卷试卷页数：8
命题教师：秦沿海任课教师：秦沿海
学生姓名：行政班：软工08级班座位号：学号：
题号一二三四五六七八九十总分得分
评卷教师
一填空题 (20分，1分/空)
1、编译程序的工作过程一般划分为五个阶段，包括：词法分析、语法分析、语
义分析与中间代码产生、代码优化和。
2、从文法产生句子的思想和方法是推导。
推导指的是：从文法的出
发，反复连续使用适当的 , 对非终结符施行替换和展开，一直到得到的符号串只含有 (即语言的句子)为止。
3、二义文法是指的文法。
4、程序语言的单词符号一般分为五种，有：、标识符、字面常数、
运算符和分界符。
5、正规式ε表示的正规集是；正规式 0|1 表示的正规集是。
6、规范归约是一个归约序列，每次归约都对句型中的进行归约。
7、如果一个文法G中的任何终结符号对(a, b)至多只满足下述三种关
系之一： a =·b, a<·b, a·>b ，则称G是一个文法。
8、右部符号串某个位置标有“.”的产生式称为相应文法的LR(0) 项目。
项目
考试试卷
考试课程：编译原理行政班：软工08级班
学生姓名：
S→aBB. 称为项目；S→.bBB 称为项目。
产生式S→ε只有一个项目：。
9、在上下文无关文法的基础上为每个文法符号X配备若干个相关的“值”---
这些“值”称为X的。
语义规则指的是。
10、S-属性文法是的属性文法，可用于一遍扫描的自下而上分析。
11、编译过程中需要各种表格。
表格有多种,各阶段使用的表格也有不同,最重要的表格是。
12、存储分配策略一般有：，栈式分配策略和堆式分配策略。
13、对程序进行各种等价变换，使得从变换后的程序出发，能生成更有效的目标代码，通常称这种变换为。
二单项选择题 (20分，2分/空)
1、文法G=({0,1},{S,A},S,{S→1A,A→0A|0}),它描述的语言是。
A. {10n|n>=1}
B. {0n1|n>=1}
C. {10n|n>=0}
D. {01n|n>=1}
2、设句型α=BabAbca，其中Ab是句柄，则不是句型的活前缀。
A. Ba
B. BabA
C. BabAbc
D. ε
3、文法G为：I→L| LS S→T|ST T→L| D
L→a|b|…|z D→0|1|…|9
产生式包含直接左递归。
A. I→L|LS
B. S→T|ST
C. T→L|D
D. D→a|b|…|z
4、文法G为：E→E+T| T T→T*F| F F→（E）| i
则句型E+T*F+F中的最左素短语是。
A. E+T
B. T*F
C. F
D. E
5、合并已知量属于。
考 试 试
卷
考试课程：编译原理 行政班：软工08级 班
学生姓名：
A. 局部优化
B. 全局优化
C. 循环优化
D. 寄存器优化 6、文法: S →ABS|AB AB →BA A →0 B →1 是Chomsky 的 型文法。
A. 0
B. 1
C. 2
D. 3
7、数组A[4:8,-3:5]的首地址为140，按行存储，每个元素占4个字节，存储器按字节编址，则数组元素A[7,4]的地址为 。
A. 100
B. 140
C. 176
D. 276
8、设文法 G ： S →（L ）| aS|a L →L*S|S 则句型（S*（a ））的句柄是 。
A. S
B. （a ）
C. a
D. S*（a ） 9、在LR 分析表中, S i 表示 。
A. 移进当前符号,转向第i 个产生式
B. 移进当前符号,转向第i 个状态
C. 用第i 个产生式归约
D. 转向第i 个状态 10、如图的状态转换图接受的字集为 ____ 。
A. 含奇数个0的二进制数组成的集合 B 含偶数个0的二进制数组成的集合 C. 以0开头的二进制数组成的集合 D. 以0结尾的二进制数组成的集合
三 判断题 (10分，1分/小题)
1、赋值号左边的变量只持有左值，不持有右值。
2、标识符用来表示名字，因此标识符和名字没有区别。
3、设有r 和s 分别是正规式，则有L(r|s) = L(r) L(s)。
4、对任意一个右线性文法G ，都存在一个NFA M ，满足L(M)=L(G)。
5、欲构造行之有效的自上而下分析器，则必须消除左递归和回溯。
6、在自下而上的语法分析中，语法树和分析树一定相同。
Y
X
1
考试试卷
考试课程：编译原理行政班：软工08级班
学生姓名：
7、LR文法肯定是无二义的，一个二义文法决不会是LR文法。
8、非终结符可以有继承属性，但不能有综合属性。
9、对某变量A赋值后，在该A值被引用前又对A重新赋值，则可以删除原来对A的赋值。
这叫删除无用赋值。
10、动态变量和动态数组需要在运行阶段分配存储空间。
四简答题 (26分，前4题每题4分，后2题每题5分)
1、构造产生语言：L={a2n+1|n≥0}的文法。
解:
2、给出字母表{a,b}上的正规表达式：以b开头，后跟若干个ab(至少1个)的符号串的集合。
解：
3、文法G[S]: S→LU
L→Ui:|ε
U→e=i|ε
计算: FIRST(S)；FOLLOW(U)。
解:
4、写出赋值句的后缀式和抽象语法树: x := （-a）-(b*c/(c-d) + (-b)*a)。
考试试卷
考试课程：编译原理行政班：软工08级班学生姓名：
解：逆波兰表示为：抽象语法树为：
5、翻译以下句子生成四元式，四元式序号从100开始：
if a>b or c＜d and e=f then
while x＜y do z := y*z
解:
6、文法G及相应的翻译模式如下:
P→bQb { print(“1”)}
Q→cR { print(“2”)}
Q→a { print(“3”)}
R→Qa { print(“4”)}
对于输入符号串bccaaab，该翻译模式的输出是什么？
解:
考试试卷
考试课程：编译原理行政班：软工08级班学生姓名：
五综合题 (24分，8分/小题)
1、构造与正规式 a* b(ba)*等价的确定有限自动机。
解：
2、以下文法是否LR(0)文法？是否SLR(1)文法？
考试试卷
考试课程：编译原理行政班：软工08级班学生姓名：
G(S):S→A | B
A→aAc|a
B→bBd | b
解：
3、设文法G(E): E→EaT|T
考试试卷
考试课程：编译原理行政班：软工08级班学生姓名：
T→FbT|F
F→cEd|e
消除文法G的左递归后得到的等价文法设为G’，G’是不是LL(1)文法？解：。
