编译原理期中考试2009B

西北民族大学计算机科学与信息工程学院期末考试编译原理试卷（B卷）专业:计算机科学技术课程代码: 15002171学号: 姓名:一、单项选择题（在每小题的四个备选答案中，选出一个正确的答案，并将其代码填入题后的括号内。

每小空1分，共 10 分）1、一般程序设计语言的定义都涉及 B 三个方面。

(1)语法 (2)语义 (3)语用 (4)程序基本符号的确定供选答案：A. (1)(2)(3) B. (1)(2)(4)C. (1)(3)(4)D. (2)(3)(4)[能力层次：记忆] [难易度：B]2、程序语言一般分为（A）和（C）两大类，其中（C）通常又称为面向机器的语言。

面向机器语言指的是（B），其特点是（D），在此基础上产生了与人类自然语言比较接近的（D）（1）（2）（3）（6）Ａ. 高级语言Ｂ. 专用语言Ｃ. 低级语言Ｄ. 通用程序语言（4）Ａ. 用于解决机器硬件设计问题的语言Ｂ. 特定计算机系统所固有的语言Ｃ. 各种计算机系统都通用的语言Ｄ.只能在一台计算机上使用的语言（5） A. 程序的执行效率低，编制效率低，可读性差B. 程序的执行效率高，编制效率高，可读性强C. 程序的执行效率低，编制效率高，可读性强D. 程序的执行效率高，编制效率低，可读性差[能力层次：记忆] [难易度：C]3、高级语言编译程序常用的语法分析方法中，递归下降分析法属于 B 分析方法。

A.自左至右B.自顶向下C.自底向上D.自右向左[能力层次：记忆] [难易度：A]4、文法 G 产生的 D 的全体是该文法描述的语言。

A ．句型 B. 终结符集 C. 非终结符集 D. 句子[能力层次：记忆] [难易度：A]5、下列属于三性文法的是： CA．G1：S→AbB S→AAS A→Bab B→bB．G2: S→A ASA→abbSa bSA→ABB AS→aabbb A→baC．G3: S→aB S→aA A→bA B→bD．G4: S→Aa S→Babb A→Cc A→Bb B→Bb B→a C→D C→Bab D→d[能力层次：简单运用] [难易度：C]二、判断题（认为对的，在题后的括号内打“√”，认为错的打“×”。

2010级一、填空题（每小题2分，共10分）1、在C语言中,m是一个整型变量，程序编译时遇到表达式m+”test”，出现错误，此错误是编译各阶段中的阶段发现的错误。

2、设有字母表A={a,b},与A*等价的正则表达式是。

3、自底向上的语法分析方法中产生的冲突有和4、LALR(1)项目是对LR(1)项目集中的5、语法制导翻译能同时进行分析和分析二、判断题（每小题1分，共10分）（）1、将目标程序装配成可执行程序是编译程序的任务。

（）2、一棵语法树反映了其叶子结点从左到右连接成句型的任意推导情况。

（）3、NFA和DFA的区别之一是映射函数是否唯一。

（）4、任何正则语言均可用上下文无关文法来描述。

（）5、在C语言中语句int int1;经过词法分析后识别出int、int、1和;四个单词。

（）6、自上而下语法分析的“上”是指分析树的根结点或文法的开始符号（）7、每个SLR(1)文法一定是LALR(1)文法（）8、LR项目集中的待约项目不会引起冲突（）9、终结符既可有综合属性，也可以有继承属性（）10、语法制导翻译方法既可用于生成中间代码，也可用于生成目标代码。

三、简答及简单应用题（每小题5分，共计25分）1、采用语法制导翻译方式对数组引用进行翻译，设有定义int a[10][20]，写出赋值语句：x=a[i][j]；翻译后生成的中间代码?2、文法G1[S]：S→(A) A→a |Bb B→Aab，请消除其中的左递归，改写后的文法是LL(1)文法吗？为什么？3、设有如下文法G[S]：S → aAcB|Bd A → AaB|c B → bScA|b2给出句型aAcbBdcc的语法树，并写出其所有短语、素短语与句柄。

4、从运行时存储分配方面解释C语言中静态变量、局部变量的生存期与作用域。

5、文法G3[S]S → S；G | G G → G（T）| H H→a | (S) T→T+S | S[S]如下：四、文法G4S→DSD |2D→0|1设计属性文法,使其能判断一个句子是否为回文数,并输出判断（8分）五、给定文法G5[S]：S→aA|a A→cAd | ε(1)给出G的LR(1)项目集规范族（包括项目集和有穷状态自动机）（12分）(2) 说明文法是否为LR(1)文法，为什么？如果文法是LR(1)文法，构造其SLR(1)分析表(8分)六、设∑={a,b}，L={(a|b)*|不包含子串aab的字符串}(1)给出L的正则表达式；（5分）(2)构造识别此语言集合的的DFA；（10分）(3)构造生成此语言集合的3型文法。

《编译原理》考试试题及答案(汇总)一、是非题（请在括号内，正确的划√，错误的划×）（每个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．构造编译程序应掌握______。

完整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.文法G所描述的语言是的集合。

A.文法G的字母表V中所有符号组成的符号串B.文法G的字母表V的闭包V*中的所有符号串C.由文法的开始符号推出的所有符号串D.由文法的开始符号推出的所有终结符串2．有文法G[I]：I→I1|I0|Ia|Ib|Ic|a|b|c ,下列符号串中是该文法的句子的有①ab0 ②a0c01 ③aaa ④bc10 可选项有：。

A.②③④B.①C.③D.①②③④3.词法分析所依据的是。

A.语义规则B.构词规则C.语法规则D.等价变换规则4.如果L(M) = L(M’)，则M与M’。

A.等价B.M与M’都是二义的C.M与M’都是无二义的D.它们的状态数相等5．下面状态转换图接受的字集为。

1A.以0开头的二进制数组成的集合B.以0结尾的二进制数组成的集合C. 含奇数个0的二进制数组成的集合D.含偶数个0的二进制数组成的集合6.文法G[E]：E→T|E+T T→F|T*F F→a|(E)该文法句型E+F*(E+T)的直接短语是下列符号串的。

①(E+T) ②E+T ③F ④F*(E+T)可选项有：A.①③B.②③C.③④D.③7. 有限状态自动机能识别。

A.上下文无关文法B.上下文有关文法C.正规文法D.短语文法8. 如果文法G是无二义的，则它的任何句子 。

A.最左推导和最右推导对应的语法树必定相同B.最左推导和最右推导对应的语法树可能不同C.最左推导和最右推导必定相同D.可能存在两个不同的最左推导，但他们对应的语法树相同9．产生正规语言的文法为文法A ． 0型B .1型 C.2型 D.3型10、素短语是指_______的短语。

《编译原理》期中独立作业班级：学号：姓名：成绩一、填空题（20分）1、扫描器的任务是从源程序中识别出一个个字符。

2、最右推导是指：对于一个推导序列中的每一直接推导，被替换的总是当前符号串中的最右非终结符号。

3语法分析最常用的两类方法是自顶向下和自底下上分析法。

4、一个上下文无关文法所含四个组成部分是非终结符集、产生式集、一组终结符号，一个开始符号。

5、如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是有二义性的。

6、对于文法G，仅含终结符号的句型称为G产生的句子。

7、产生式是用于定义语言中的语法范畴的一种书写规则二、名词解释（20分）1、遍对源程序或源程序中间表示的一次扫描，每一遍读入一个文件，执行一个或几个阶段的编译操作，并输出源程序的一个中间表示2、语法分析在词法分析的基础上将单词序列组合成各类语法短语3、短语若Z加推出xAy 加推出xay任一子树的树叶全体(具有共同祖先的叶节点符号串)皆为短语。

4、中间代码优化5、句柄一个句型的最左简单短语称为该句型的句柄。

三、简答题1、已知文法G(S)S→a|∧|(T)T→T，S|S写出句子((a，a)，a)的规范推导过程(10分)解：句型归约规则句柄((a，a)，a) S→a a((S，a)，a) T→S S((T，a)，a) S→a a((T，S)，a) T→T，S T，S((S)，a) T→S S((T)，a) S→S(T)(T)(S，a) T→S S(T，a) S→a a(T，S) T→T，S T，S(T) S→(T)(T)S2、已知文法G(E)（10分）E→T|E＋TT→F|T * FF→(E)|i(1) 给出句型(T * F＋i)的语法树；(2) 给出句型(T * F＋i)的短语、句柄。

句型T*F+I的短语为i、T*F、T*F+i; 简单短语为i、T*F;句柄为第一个T*f。

3、设Σ={x,y},Σ上的正规表达式e=yxy*(xy|yx)x*y*,请构造一个NDFA M，使L（M）=L（e）(10分)4、设文法G(S)：(15分)S→AA→BHH →iBH|εB →CKK →+CK|εC→)A*|(计算每个非终结符的FIRST和FOLLOW；构造LL(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．构造编译程序应掌握。

《编译原理》期中及期末习题第一章高级语言与编译程序概述典型例题:单项选择题1.1.1．将编译程序分成若干个“遍”是为了___。

a.提高程序的执行效率b.使程序的结构更加清晰c.利用有限的机器内存并提高机器的执行效率d.利用有限的机器内存但降低了机器的执行效率1.1.2．构造编译程序应掌握____。

（陕西省2000年自考题）a.源程序b.目标语言c.编译方法d.以上三项都是1.1.3．变量应当＿。

a.持有左值b.持有右值c.既持有左值又持有右值d.既不持有左值也不持有右值1.1.4．编译程序绝大多数时间花在____上。

（陕西省1998年自考题）a.出错处理b.词法分析c.目标代码生成d.管理表格1.1.5．____不可能是目标代码。

( 陕西省1997年自考题)a.汇编指令代码b.可重定位指令代码c.绝对指令代码d.中间代码1.1.6．数组A[1…20,1…10]的首地址偏移量为0，按列存储，每个元素占一个字节，存储器按字节编址，则A[i,ｊ］的偏移地址为____。

a.(i-1)X10+（j-1）b.(i-1)X20+(j-1)c. (i-1)＋(j-1)X10d.(i-1)+(j-1)X201.1.7.使用____可以定义一个程序的意义。

a.语义规则b.词法规则c.产生规则d.左结合规则1.1.8．表达式X:=5中，变量x____。

a.只有左值b.只有右值c.既有左值又有右值d.没有左值也没有右值1.1.9．词法分析器的输入是__。

a.单词符号b.源程序c.语法单位d.目标程序1.1.10．中间代码生成时所遵循的是＿。

a.语法规则b.词法规则c.语义规则d.等价变换规则1.1.11．编译程序是对__。

a.汇编程序的翻译b.高级语言程序的解释执行c.机器语言的执行d.高级语言的翻译1.1.12．词法分析应遵循＿。

（陕西省2000年自考题）a.语义规则b.语法规则c.构词规则d.等价变换规则多项选择题：1.2.1 编译程序各阶段的工作都涉及到___。

《编译原理》期中及期末习题第⼀章⾼级语⾔与编译程序概述典型例题:单项选择题1.1.1．将编译程序分成若⼲个“遍”是为了___。

a.提⾼程序的执⾏效率b.使程序的结构更加清晰c.利⽤有限的机器内存并提⾼机器的执⾏效率d.利⽤有限的机器内存但降低了机器的执⾏效率1.1.2．构造编译程序应掌握____。

（陕西省2000年⾃考题）a.源程序b.⽬标语⾔c.编译⽅法d.以上三项都是1.1.3．变量应当＿。

a.持有左值b.持有右值c.既持有左值⼜持有右值d.既不持有左值也不持有右值1.1.4．编译程序绝⼤多数时间花在____上。

（陕西省1998年⾃考题）a.出错处理b.词法分析c.⽬标代码⽣成d.管理表格1.1.5．____不可能是⽬标代码。

( 陕西省1997年⾃考题)a.汇编指令代码b.可重定位指令代码c.绝对指令代码d.中间代码1.1.6．数组A[1…20,1…10]的⾸地址偏移量为0，按列存储，每个元素占⼀个字节，存储器按字节编址，则A[i,ｊ］的偏移地址为____。

a.(i-1)X10+（j-1）b.(i-1)X20+(j-1)c. (i-1)＋(j-1)X10d.(i-1)+(j-1)X201.1.7.使⽤____可以定义⼀个程序的意义。

a.语义规则b.词法规则c.产⽣规则d.左结合规则1.1.8．表达式X:=5中，变量x____。

a.只有左值b.只有右值c.既有左值⼜有右值d.没有左值也没有右值1.1.9．词法分析器的输⼊是__。

a.单词符号b.源程序c.语法单位d.⽬标程序1.1.10．中间代码⽣成时所遵循的是＿。

a.语法规则b.词法规则c.语义规则d.等价变换规则1.1.11．编译程序是对__。

a.汇编程序的翻译b.⾼级语⾔程序的解释执⾏c.机器语⾔的执⾏d.⾼级语⾔的翻译1.1.12．词法分析应遵循＿。

（陕西省2000年⾃考题）a.语义规则b.语法规则c.构词规则d.等价变换规则多项选择题：1.2.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．构造编译程序应掌握______。

湖北第二师范学院2014－2015学年度第二学期《编译原理》课程考试答案(B卷) 院系：计算机学院专业班级：学生姓名：学号：考试方式：闭卷………………………………………………………………………………………………………………一、填空题（每空1分，共10分）1．从编译系统的方式看，有两种编译方式，一种是（解释）方式，另一种是（编译）。

2．编译的过程一般讲，有（词法分析），（语法分析），（语义分析），（中间代码生成），（中间代码优化）和（目标代码生成）。

3．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即（静态存储分配）方案和（动态存储分配）方案。

二、综合题（共90分）1．（5分）构造语言｛a3n|n≥1｝的文法答案：其文法是（5分）P（A）：A→aaa|aaaA2．（5分）给出下面表达式的逆波兰表示：a*b+(c-d)/e答案：ab*cd-e/+ （5分）3．（30分）给定文法 G[E] ：E → E+T | TT → T*F | FF → (E) | i该文法是 LL(1) 文法吗？为什么？不是的能否改造为LL（1）文法，如果能够改造，给出改造后的文法，并给出改造后文法是LL（1）文法的证明过程。

无论改造前还是改造后的文法，如果是LL（1）文法，则给出（i+i）*i的分析过程（要求给出详细过程，并给出LL（1）的分析表）答案：（1）该文法不是LL（1）文法，因为文法的产生式含有左递归（2分）（2）该文法可改造为LL（1）文法，即消除左递归，改造后的文法是（3分）E → TE’E’→ +TE’ | εT → FT’T’→ *FT’ |εF → (E) | i证明改造后的文法是LL（1）文法的过程A.求可达ε的非终结符（1分）可达的是E’,T’B.求每个非终结符的First集合（3分）First(E)={ (,i}First(E’)={+}First(T)={ (,i}First(T’)={*}First(F)={ (,i}C.求每个产生式右部字符串的First集合（3分）First(TE’)={ (,i}First(+TE’)={+}First(FT’)={ (,i}First(*FT’)={*}First((E))={ ( }First(i)={ i }First(ε)={ ε}D.求每个非终结符的Follow集合（3分）Follow(E)={$,)}Follow(E’)= Follow(E)={$,)}Follow(T)=First(E’) ∪ Follow(E)={$,+,)}Follow(T’)= Follow(T)={$,+,)}Follow(F)= First(T’) ∪ Follow(T)={$,+, *,)}E.求每个非终结符的Select集合（5分）Select(E → TE’)=First(TE’)={ (,i }Select(E’→ +TE’)=First(+TE’)={ + }Select(E’→ε)=First(ε)-{ ε} ∪ Follow(E’)={ $,) }Select(T → FT’)=First(FT’)={ (,i }Select(T’→ *FT’)=First(*FT’)={ * }Select(T’→ε)=First(ε)-{ ε} ∪ Follow(T’)={ $,+,) }Select(F → (E))=First((E))={ ( }Select(F → i)=First(TE’)={ i }F.求有多个产生式的非终结符Select集合的交集（2分）显然有Select(E’→ +TE’) ∩Select(E’→ε)=ΦSelect(T’→ *FT’) ∩Select(T’→ε)= ΦSelect(F → (E))= ∩Select(F → i)= Φ所以改造后的文法是LL（1）文法（3）、根据E给出预测分析表（4分）符号串（i+i）*i的分析过程（4分）4．（10分）对下面的DFA进行最简化答题：第1步：确定化过程（5分）将7个状态分成两个状态集，终态集[q5,q6],非终态集[q0,q1,q2,q3,q4,q7]根据上表命名不可分割的终态集，及到达状态第2步：最小化的DFA5．（15分）给定文法 G[E] ：E → E+T | TT → T*F | FF → (E) | i该文法是算符优先文法吗？是，则构造该文法的算符优先关系矩阵，并给出（i+i）*i的分析过程（要求给出详细过程）答案：（1）该文法是算符优先文法（1分）（2）构造该文法的算符优先矩阵A.求各非终结符的FirstVT集合（3分）FirstVT（E）=｛+，*，（，i｝FirstVT（T）=｛*，（，i｝FirstVT（F）=｛（，i｝B.求各非终结符的LasttVT集合（3分）LastVT(E)={ +，*，)，i }LastVT(T)={ *，)，i }LastVT(F)={ )，i }C.构造优先关系表（4分）6．（25分）给定文法 G[E] ：E → E+T | TT → T*F | FF → (E) | i该文法是LR（0）文法吗？是，则构造该文法的LR（0）分析表，并给出（i+i）*i的分析过程，不是的，是SLR（1）文法吗，是，则构造该文法的SLR（1）分析表，并给出（i+i）*i的分析过程。

编译原理B卷编译原理试卷B⼀、选择题（每空2分，共20分）1.下⾯说法正确的是：BA⼀个正规式只能对应⼀个确定的有限状态⾃动机；B ⼀个正规语⾔可能对应多个正规⽂法；2. 表达式E*(F-C*(C/D))的逆波兰表⽰为（ B ）A. EFC-CD/**B. EFCCD/*-*C. EFC-*CD/*D. 前三个选项都不对3.下⾯说法正确的是：AA Lex是⼀个词法分析器的⽣成器B Y acc是⼀个语法分析器4．⽂法G产⽣的（D ）的全体是该⽂法描述的语⾔。

A句型 B 终结符集 C ⾮终结符集 D 句⼦5．若⽂法G定义的语⾔是⽆限集，则⽂法必然是（A）。

A递归的 B 前后⽂⽆关的 C ⼆义性的 D ⽆⼆义性的6．⼀个⽂法所描述的语⾔是（A）；描述⼀个语⾔的⽂法是（ B ）。

A惟⼀的 B 不惟⼀的7. Chomsky定义的四种形式语⾔⽂法中，0型⽂法⼜称为（A）⽂法；1型⽂法⼜称为（C ）⽂法；2型⽂法可由（G ）识别。

A短语结构⽂法 B 前后⽂⽆关⽂法 C 前后⽂有关⽂法 D 正则⽂法E 图灵机F 有限⾃动机G 下推⾃动机⼆、问答题第1题(10分) 将⽂法G[S] 改写为等价的G'[S]，使G'[S]不含左递归和左公共因⼦。

G[S]：S→SAe|AeA→dAbA|dA|d答: ⽂法G[S] 改写为等价的不含左递归和左公共因⼦的G'[S]为：S →AeS'S' →AeS'|εA →dA'A' →AB|εB →bA |ε第2题(20分) 判断下⾯⽂法是否为LL(1)⽂法，若是，请构造相应的LL(1)分析表。

S→aDD→STe|εT→bH|HH→d|ε第2题⾸先计算⽂法的 FIRST集和FOLLOW集如下表。

⽂法的FIRST集和FOLLOW集由于select（D→STe）∩se lect（D→ε）={a}∩{# ，b ，d ，e }= select（T→bH）∩select（T→H）={b}∩{e }= select（H→d）∩select（H→ε）={ d }∩{ e }=所以该⽂法是LL(1)⽂法，LL(1)分析表如下表。

一、答复以下问题：(30分)1．什么是属性文法？什么是属性文法？它们之间有什么关系？解答：属性文法是只含有综合属性的属性文法。

〔2分〕属性文法要求对于每个产生式A X1X2…，其每个语义规那么中的每个属性或者是综合属性，或者是的一个继承属性，且该属性仅依赖于：（1）产生式的左边符号X12…1的属性；（2）A的继承属性。

〔2分〕属性文法是属性文法的特例。

〔2分〕2．什么是句柄？什么是素短语？一个句型的最左直接短语称为该句型的句柄。

〔3分〕素短语是这样的一个短语，它至少包含一个终结符并且不包含更小的素短语。

〔3分〕3．划分程序的根本块时，确定根本块的入口语句的条件是什么？解答：〔1〕程序第一个语句，或〔2〕能由条件转移语句或无条件转移语句转移到的语句，或〔3〕紧跟在条件转移语句后面的语句。

4．(6分)运行时的表的内容是什么？它的作用是什么？答：表是嵌套层次显示表。

每当进入一个过程后，在建立它的活动记录区的同时建立一张嵌套层次显示表.假定现在进入的过程层次为i，那么它的表含有1个单元，自顶向下每个单元依次存放着现行层、直接外层、…、直至最外层(主程序，0层)等每层过程的最新活动记录的起始地址。

通过表可以访问其外层过程的变量。

5．(6分)对以下四元式序列生成目标代码：*C*2其中，H是根本块出口的活泼变量，R0与R1是可用存放器答：R0，BR0，CR1，ER1，FR0，R1R0，2R0，H二、设={0，1}上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的。

(8分)答：构造相应的正规式：(0|1)*1(0|1) (3分): (2分)1 11012340 0确定化：(3分)I0I1I{0,1,2}{1,2}{1,2,3}{1,2}{1,2}{1,2,3}{1,2,3} {1,2,4} {1,2,3,4} {1,2,4} {1,2} {1,2,3} {1,2,3,4}{1,2,4}{1,2,3,4}10 1 0 00 1 1 1 三、写一个文法使其语言为L(G)={ | ≥1}。

（B ）编译程序处理的对象是源语言 词法分析无法自动进行C. a 500b 60aab 2aD. a（画出DFA6.哪个不是DFA 的构成成分 A.有穷字母表B.C. 终止状态集合D. 100 40- 10b ab aa初始状态集合有限状态集合 (B )A.单词符号串B.源程序 C .语法单位 D. 目标程序(C )常数编译原理试题B、单项选择题（每题1分，共20 分）1、对编译系统有关概念描述正确的是 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. 1010001001101B.0101001110010010C. 1101010011110111D.1010011101101010 (可画出DFA 验证) 5. 文法 G[S]: S — aA|bC|a A — aS|bB B — aC|bA|bC — aB|bS ,则不是L(G)句子的是.100 50. 10^_1000 500 . A. a b ab B. ab aba7•词法分析器的输入是8.在词法分析阶段不能识别的是A.标识符B. 运算符C .四元式 D.9.设有一段C语言程序while（i&&++j）(A ),贝U FIRST(Ap)为 .{a,c} D.(C ) 其他.素短语A.语法规则换规则B . 词法规则C .语义规则 D. 等价变{c=2.19;j+=k；i++；},经过词法分析后可以识别的单词个数是（B ）A. 19B.20 C . 21 D.2310•自上而下语法分析的主要动作是（B ）A.移进B. 推导 C .规约 D. 匹配11.下面不属于LL（1）分析器的自称部分是（D ）A. LL（1）总控程序B. 分析表C.分析栈D. 源程序串12. 设有文法G[S]为S— AB|bC, Ar |b , Bf |aD , C— AD|b, D^aS|c 贝U FOLLOW(A为A. {a,c,#}B.{c,#} C . {a,#} D.{#}13. 设有文法G[S]:S—Ap|Bq, A—a|cA , B—b|dBA. {p,q}B. {b,d} C14. 自下而上语法分析的主要分析动作是（D ）A.推导B. 规约 C .匹配 D. 移进-规约15. 算法优先分析中，可规约串是A.句柄 B .活前缀 C .最左素短语 D16. 设有文法 G={{S},{a},{S — SaS| £},S},该文法是（B ）A. LL（1）文法 B .二义性文法C. SLR（1）文法 D .算法优先文法17、中间代码生成时所以据的是（C ）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 •便于目标代码优化 的组织C •便于目标代码的移植B •便于存储空间D .便于编译程序的移植.简答（每题3分，共12分）20.中间代码是介于源语言程序和什么之间的一种代码（D ）A.源代码B.机器语言C.汇编语言 D. 目标代码解释程序也是一种翻译程序，它将源程序作为输入并执行之，即边解释边执行2•词法分析器的主要任务是什么？词法分析器的主要任务是逐步扫描和分解构成源程序的字符串， 识别出一个一个 的单词符号。

第一章1.编译程序绝大多数时间花在（ B ）上。

A 出错处理B 词法分析C 目标代码生成D 表格管理2.编译方式与解释方式的根本区别在于_ 是否有目标代码生成______.3.编译程序是对_____A____A 汇编语言的翻译B 高级语言程序的解释执行C 机器语言的执行D 高级语言的翻译第二章1. 令∑={a，b}，∑上的正规式和相应的正规集的例子有：正规式正规集a {a}a∣b {a,b}ab {ab}(a∣b)(a∣b) {aa,ab,ba,bb}a *{ε,a,a, ……任意个a的串}(a∣b)*{ε,a,b,aa,ab ……所有由a和b组成的串}(a∣b)*(aa∣bb)(a∣b)*{∑*上所有含有两个相继的a或两个相继的b组成的串} 2.设∑={a,b,c}，则aa*bb*cc*是∑上的…..正规式，它所表示的正规集为L={a m b n c l| m,n,l>=1}1.DFA M接受的字集为_______。

A 以0开头的二进制数组成的集合B 以0结尾的二进制数组成的集合C 含奇数个0的二进制数组成的集合D 含偶数个0的二进制数组成的集合构造下列正规式相应的NFA(1)(a|b)*abb(2)(a|b)*a(a|b)(3)(a|b)*(aa|bb)(a|b)*随堂练习已知一状态转换图如图所示，且假定I=ε_{0}={0}，试求从状态0出发经过一条有向边b而能到达的状态集J和ε_CLOSURE(J)。

例2.8 正规表达式（a∣b）*(aa∣bb)(a∣b)*的NFA M如图2–14所示，试将其确定化为DFA M'。

图2–14 例2.8的NFA M表2.4 例2.8的转换表表2.5 例2.8的状态转换矩阵图2–15 例2.8未化简的DFA M′第三章随堂练习(一）设字母表 ={a，b}，试设计一个文法，描述语言L={a2n,b2n|n≥1}分析：n=1 L={aa,bb}n=2 L={aaaa,bbbb}n=3 L={aaaaaa,bbbbbb}L=,aa,bb,aaaa,bbbb,aaaaaa,bbbbbb, …-文法G=(V T,V N,S, ξ)V T={a,b} V N={S,A,B}方法一：ξ: S→aa|aaA|bb|bbBA→aa|aaAB→bb|bbB方法二：ξ: S→A|BA→aa|aAaB→bb|bBb注意：ξ: S→aa|bb|Saa|Sbb是否可行？随堂练习（二）给出下面语言相应的文法(1)L1={a m b n | m,n≥1}G(S): S→ABA→a|AaB→b|bB(2)L2={a n b n c i | n ≥1,i≥0}G(S): S→ABA→ab|aAbB→ξ|cB(3)L3={a n b n c m d m | n ≥1,m≥1}G(S): S→ABA→ab|aAbB→cd|cBd(4)L4={a2n+1 | n ≥0}S→a|aAA→aS或者S→a|aSa随堂练习1. 文法G:S→xSx|y 所识别的语言是______.A xyxB (xyx)*C x n yx n(n≥0)D x*yx*2.文法G[N]=（{b}，{N，B}，N，{N→b│bB，B→bN}），该文法所描述的语言是__________。

编译原理试题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)文法 BC．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. 什么是解释程序？解释程序也是一种翻译程序，它将源程序作为输入并执行之，即边解释边执行。