编译原理期末考试复习题
编译原理参考题目
第一套
一、判断题
1．用高级语言书写的源程序都必须通过编译,产生目标代码后才能投入运行”这种说法。( N) 2．若一个句型中出现了某产生式的右部，则此右部一定是该句型的句柄。( N)
3．一个句型的句柄一定是文法某产生式的右部。(Y )
4．在程序中标识符的出现仅为使用性的。( N)
5．仅考虑一个基本块，不能确定一个赋值是否真是无用的。(Y )
6．削减运算强度破坏了临时变量在一基本块内仅被定义一次的特性。(Y )
7．在中间代码优化中循环上的优化主要有不变表达式外提和削减运算强度。(N )
8．算符优先关系表不一定存在对应的优先函数。( N)
9．数组元素的地址计算与数组的存储方式有关。(N )
10．编译程序与具体的机器有关,与具体的语言无关。(N )
参考答案：
1、×
2、×
3、√
4、×
5、√
6、√
7、×
8、×
9、×10、×
二、选择题
1．通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括_____。
A．模拟执行器B．解释器
C．表格处理和出错处理D．符号执行器
2．文法G[N]= （{b} ，{N ，B} ，N ，{N→b│bB ，B→bN} ），该文法所描述的语言是
A．L(G[N])={bi│i≥0} B．L(G[N])={b2i│i≥0}
C．L(G[N])={b2i+1│i≥0} D．L(G[N])={b2i+1│i≥1}
3．一个句型中的最左_____称为该句型的句柄。
A．短语B．简单短语C．素短语D．终结符号
4．设G 是一个给定的文法，S 是文法的开始符号，如果S->x( 其中x∈V*), 则称x 是文法G 的一个_____。
A．候选式B．句型C．单词D．产生式
5．文法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．③
6．若一个文法是递归的，则它所产生的语言的句子_____。
A．( ) 是无穷多个B．( ) 是有穷多个
C．( ) 是可枚举的D．( ) 个数是常量
7．词法分析器用于识别_____。
A．( ) 句子B．( ) 句型C．( ) 单词D．( ) 产生式
8．在语法分析处理中，FIRST 集合、FOLLOW 集合、SELECT 集合均是_____。
A. ( ) 非终极符集B．( ) 终极符集C．( ) 字母表 D. ( ) 状态集
9．在自底向上的语法分析方法中，分析的关键是_____。
A.( ) 寻找句柄
B.( ) 寻找句型
C.( ) 消除递归
D.( ) 选择候选式
10．在LR 分析法中，分析栈中存放的状态是识别规范句型_____的DFA 状态。
A.( )句柄
B.( ) 前缀
C.( )活前缀
D.( ) LR(0) 项目
参考答案：
1、C
2、C
3、B
4、B
5、B
6、A
7、C
8、B
9、D 10、C
三、填空题
1．设G是一个给定的文法，S是文法的开始符号，如果S->x( 其中x∈VT*), 则称x是文法的一个__句子___。
2．递归下降法不允许任一非终极符是直接左递归的。
3．自顶向下的语法分析方法的基本思想是：从文法的_开始符号__开始，根据给定的输入串并按照文法的产生式一步一步的向下进行_直接推导_，试图推导出文法的__句子__，使之与给定的输入串_匹配_。
4．自底向上的语法分析方法的基本思想是：从输入串入手，利用文法的产生式一步一步地向上进行_直接规约_ ，力求归约到文法的__开始符号___。
5．常用的参数传递方式有_传地址_，传值和传名。
6．在使用高级语言编程时,首先可通过编译程序发现源程序的全部_语法__错误和语义部分错误。
参考答案：
1．句子
2．左
3．开始符号直接推导句子匹配
4．直接归约开始符号
5．传地址
6．语法
四、简答题
1. 已知文法G[S] 为：
S→dAB
A→aA|a
B→Bb|ε
G[S] 产生的语言是什么？
参考答案：
答：G[S]产生的语言是L(G[S])={danbm│n≥1,m≥0}。
2. 简述DFA 与NFA 有何区别?
参考答案：
答：DFA与NFA的区别表现为两个方面:一是NFA可以若干个开始状态，而DFA仅只一个开始状态。另一方面，DFA的映象M是从K×∑到K，而NFA的映象M是从K×∑到K 的子集，即映象M将产生一个状态集合（可能为空集），而不是单个状态。
5. 何谓优化？按所涉及的程序范围可分为哪几级优化？
参考答案：
(1)优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目标代码。
(2) 三种级别：局部优化、循环优化、全局优化。
五.计算题（10分）
对下面的文法G ：
E->TE'
E'->+E| ε
T->FT'
T' ->T| ε
F-> PF'
F'-> *F'| ε
P->(E)|a|b|^
(1)计算这个文法的每个非终结符的FIRST 集和FOLLOW 集。
参考答案：
解：（1）计算这个文法的每个非终结符的FIRST集和FOLLOW集。
FIRST集合有：
FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^};
FIRST(E')={+,ε}
FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^};
FIRST(T')=FIRST(T)∪{ε}={(,a,b,^,ε};
FIRST(F)=FIRST(P)={(,a,b,^};
FIRST(F')=FIRST(P)={*,ε};
FIRST(P)={(,a,b,^};
FOLLOW集合有：
FOLLOW(E)={),#};
FOLLOW(E')=FOLLOW(E)={),#};
FOLLOW(T)=FIRST(E')∪FOLLOW(E)={+,),#};//不包含εFOLLOW(T')=FOLLOW(T)=FIRST(E')∪FOLLOW(E)={+,),#}; FOLLOW(F)=FIRST(T')∪FOLLOW(T)={(,a,b,^,+,),#};//不包含εFOLLOW(F')=FOLLOW(F)=FIRST(T')∪FOLLOW(T)={(,a,b,^,+,),#}; FOLLOW(P)=FIRST(F')∪FOLLOW(F)={*,(,a,b,^,+,),#};//不包含ε
(2)证明这个方法是LL(1)的。
各产生式的SELECT集合有：
SELECT(E->TE')=FIRST(T)={(,a,b,^};
SELECT(E'->+E)={+};
SELECT(E'->ε)=FOLLOW(E/)={),#}
SELECT(T->FT')=FIRST(F)={(,a,b,^};
SELECT(T'->T)=FIRST(T)={(,a,b,^};
SELECT(T'->ε)=FOLLOW(T/)={+,),#};
SELECT(F->PF')=FIRST(P)={(,a,b,^};
SELECT(F'->*F')={*};
SELECT(F'->ε)=FOLLOW(F')={(,a,b,^,+,),#};
SELECT(P->(E))={(}
SELECT(P->a)={a}
SELECT(P->b)={b}
SELECT(P->^)={^}
可见，相同左部产生式的SELECT集的交集均为空，所以文法G[E]是LL(1)文法。
(3)构造它的预测分析表。
文法G[E]的预测分析表如下：
第二套
一、判断题
1．对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。( N)
2．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。( N)
3．递归下降分析法是自顶向上分析方法。( Y)
4．产生式是用于定义词法成分的一种书写规则。(N )
5．LR 法是自顶向下语法分析方法。(Y )
6．在SLR （1 ）分析法的名称中，S的含义是简单的。(Y )
7．综合属性是用于“自上而下”传递信息。(N )
8．符号表中的信息栏中登记了每个名字的属性和特征等有关信息，如类型、种属、所占单元大小、地址等等。(N )
9．程序语言的语言处理程序是一种应用软件。( N)
10．解释程序适用于COBOL 和FORTRAN 语言。( N)
二、选择题
1．文法G 产生的_____的全体是该文法描述的语言。
A．( ) 句型B．( ) 终结符集C．( ) 非终结符集D．( ) 句子
2．若文法G 定义的语言是无限集，则文法必然是_____。
A．( ) 递归的B．( ) 前后文无关的
C．( ) 二义性的D．( ) 无二义性的
3．四种形式语言文法中，1型文法又称为_____文法。
A．( ) 短语结构文法B．( ) 前后文无关文法
C．( ) 前后文有关文法D．( ) 正规文法
4．一个文法所描述的语言是_____。
A．( ) 唯一的B．( ) 不唯一的
C．( ) 可能唯一，好可能不唯一D．( ) 都不对
5．_____和代码优化部分不是每个编译程序都必需的。
A．( ) 语法分析B．( ) 中间代码生成
C．( ) 词法分析D．( ) 目标代码生成
6．_____是两类程序语言处理程序。
A．( ) 高级语言程序和低级语言程序B．( ) 解释程序和编译程序
C．( ) 编译程序和操作系统D．( ) 系统程序和应用程序
7．数组的内情向量中肯定不含有数组的_____的信息。
A. ( ) 维数B．( ) 类型C．( ) 维上下界D．( ) 各维的界差
8. 一个上下文无关文法G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组_____。
A．( ) 句子B．( ) 句型
C．( ) 单词D．( ) 产生式
9．文法分为四种类型，即0型、1型、2型、3型。其中2型文法是_____。
A. ( ) 短语文法B．( ) 正则文法
C．( ) 上下文有关文法D．( ) 上下文无关文法
10．文法G 所描述的语言是_____的集合。
A. ( ) 文法G 的字母表V 中所有符号组成的符号串
B．( ) 文法G 的字母表V 的闭包V* 中的所有符号串
C．( ) 由文法的开始符号推出的所有终极符串
D. ( ) 由文法的开始符号推出的所有符号串
参考答案：
1、D
2、A
3、C
4、A
5、B
6、B
7、A
8、D
9、D 10、C
三、填空题
1．一个句型中的最左简单短语称为该句型的__句柄___。
2．对于文法的每个产生式都配备了一组属性的计算规则，称为_语义规则_ 。
3．一个典型的编译程序中，不仅包括__词法分析___、_语法分析_、_中间代码生成_、代码优化、目标代码生成等五个部分，还应包括表格处理和出错处理。
4．从功能上说，程序语言的语句大体可分为_执行性_语句和_说明性_语句两大类。5．扫描器的任务是从_源程序_中识别出一个个_单词符号_。
6．产生式是用于定义_语法范畴_的一种书写规则。
参考答案：
1．句柄
2．语义规则
3．词法分析语法分析中间代码生成
4．执行性说明性
5．源程序单词符号
6．语法范畴
四、简答题
1. 写一个文法，使其语言是奇数集，且每个奇数不以0开头。
参考答案：
解：文法G(N)：
N→AB|B
A→AC|D
B→1|3|5|7|9
D→B|2|4|6|8
C→0|D
五、计算题
已知NFA= （{x,y,z},{0,1},M,{x},{z} ），其中：
M(x,0)={z},M(y,0)={x,y},M(z,0)={x,z},M(x,1)={x}, M(y,1)= φ,M(z,1)={y}, 构造相应的DFA并最小化。
参考答案：
解：根据题意有NFA图:
下表由子集法将NFA转换为DFA：
下面将该DFA最小化：
(1) 首先将它的状态集分成两个子集：P1={A,D,E},P2={B,C,F}
(2) 区分P2:由于F(F,1)=F(C,1)=E,F(F,0)=F并且F(C,0)=C,所以F，C等价。由于F(B,0)=F(C,0)=C, F(B,1)=D,F(C,1)=E,而D，E不等价（见下步），从而B与C，F可以区分。有P21={C,F},P22={B}。
(3) 区分P1:由于A，E输入0到终态，而D输入0不到终态，所以D与A，E可以区分，有P11={A,E},P12={D}。
(4) 由于F(A,0)=B,F(E,0)=F,而B，F不等价，所以A，E可以区分。
(5) 综上所述，DFA可以区分为P={{A}，{B}，{D}，{E}，{C，F}}。所以最小化的DFA 如下：
第三套
一、判断题
1．一个LL(l)文法一定是无二义的。( N)
2．正规文法产生的语言都可以用上下文无关文法来描述。( N)
3．一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。( Y) 4．目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。( N)
5．逆波兰法表示的表达式亦称前缀式。(Y )
6．如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。(Y ) 7．LR 法是自顶向下语法分析方法。( N)
8．数组元素的地址计算与数组的存储方式有关。( N)
9．算符优先关系表不一定存在对应的优先函数。(N )
10．对于数据空间的存贮分配，FORTRAN 采用动态贮存分配策略。(N )
参考答案：
1、×
2、×
3、√
4、×
5、√
6、√
7、×
8、×
9、×10、×
二、选择题
1．词法分析器用于识别_____。
A．( ) 字符串B．( )语句
C．( )单词D．( )标识符
2．文法分为四种类型，即0型、1型、2型、3型。其中0型文法是_____。
A. ( ) 短语文法B．( ) 正则文法
C．( ) 上下文有关文法D．( ) 上下文无关文法
3．一个上下文无关文法G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组_____。
A．( ) 句子B．( ) 句型C．( ) 单词D．( ) 产生式
4．_____是一种典型的解释型语言。
A．( ) BASIC B．( ) C C．( ) FORTRAN D．( ) PASCAL
5．与编译系统相比，解释系统_____。
A．( ) 比较简单, 可移植性好, 执行速度快
B．( ) 比较复杂, 可移植性好, 执行速度快
C．( ) 比较简单, 可移植性差, 执行速度慢
D．( ) 比较简单, 可移植性好, 执行速度慢
6．用高级语言编写的程序经编译后产生的程序叫_____。
A．( ) 源程序B．( ) 目标程序C．( ) 连接程序D．( ) 解释程序
7．词法分析器用于识别_____。
A. ( ) 字符串B．( ) 语句C．( ) 单词D．( ) 标识符
8．编写一个计算机高级语言的源程序后, 到正式上机运行之前，一般要经过_____这几步:
(1) 编辑(2) 编译(3) 连接(4) 运行
A. ( ) (1)(2)(3)(4) B．( ) (1)(2)(3) C．( ) (1)(3) D．( ) (1)(4)
9．把汇编语言程序翻译成机器可执行的目标程序的工作是由_____完成的。
A．( ) 编译器B．( ) 汇编器
C．( ) 解释器D．( ) 预处理器
10．文法G 所描述的语言是_____的集合。
A. ( ) 文法G 的字母表V 中所有符号组成的符号串
B．( ) 文法G 的字母表V 的闭包V* 中的所有符号串
C．( ) 由文法的开始符号推出的所有终极符串
D. ( ) 由文法的开始符号推出的所有符号串
参考答案：
1、C
2、A
3、D
4、A
5、D
6、B
7、C
8、B
9、B 10、C
三、填空题
1．语法分析是依据语言的_语法__规则进行的，中间代码产生是依据语言的_语义_规进行的。2．语法分析器的输入是单词符号串_，其输出是_语法单位_。
3．一个名字的属性包括_类型__和_作用域_。
4．产生式是用于定义_语法成分__的一种书写规则。
5．逆波兰式ab+c+ d*e- 所表达的表达式为(a+b+c)*d-e __ 。
6．语法分析最常用的两类方法是_自上而下_和_自下而上_分析法。
参考答案：
1．语法语义
2．单词符号串语法单位
3．类型作用域
4．语法成分
5．(a+b+c)*d-e
6．自上而下自下而上
四、简答题
1. 写出下列表达式的三地址形式的中间表示。
(1) 5+6 *(a + b);
(2)for j:=1 to 10 do a[j + j]:=0。
参考答案：
答：(1)100: t1:=a+b
101: t2:=6*t1
102: t3:=5+t2
(2)100: j:=1
101: if j>10 goto NEXT
102: i:=j+j
103: a[i]:=0
3. 写出表达式(a+b)/(a-b)-(a+b*c)的三元序列及四元序列。参考答案：
解：（1）三元式：
①（＋，a，b）
②（－，a，b）
③（/，①，②）
④（*，b，c）
⑤（＋，a，④）
⑥（－，③，⑤）
（2）四元式：
①（＋，a，b，T1）
②（－，a，b，T2）
③（/，T1，T2，T3）
④（*，b，c，T4）
⑤（＋，a，T4，T5）
⑥（－，T3，T5，T6）
4. 写一个文法使其语言为偶数集，且每个偶数不以0开头。
参考答案：
解：文法G（S）：
S→AB|B|A0
A→AD|C
B→2|4|6|8
C→1|3|5|7|9|B
D→0|C
5. 设文法G （S ）：
S→S ＋aF|aF| ＋aF
F→*aF|*a
（1）消除左递归和回溯；
（2）构造相应的FIRST 和Follow 集合。
参考答案：
（1）
S->aFS'|＋aFS'
S'->＋aFS'|ε
F->*aF'
F'->F|ε
（2）
FIRST（S）＝｛a，+｝FOLLOW（S）＝｛＃｝FIRST（S'）＝｛+，ε｝FOLLOW（S'）＝｛＃｝FIRST（F）＝｛*｝FOLLoW（F）＝（+，＃｝FIRST（F'）＝｛*，ε｝FOLLOW（+，＃｝
第四套
一、判断题
1．编译程序是对高级语言程序的解释执行。( N)
2．一个有限状态自动机中，有且仅有一个唯一的终态。( N)
3．一个算符优先文法可能不存在算符优先函数与之对应。( Y)
4．语法分析时必须先消除文法中的左递归。(N )
5．LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。(Y ) 6．逆波兰表示法表示表达式时无须使用括号。(Y )
7．静态数组的存储空间可以在编译时确定。(X )
8．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。
(X )
9．两个正规集相等的必要条件是他们对应的正规式等价。( Y)
10．一个语义子程序描述了一个文法所对应的翻译工作。( X)
参考答案：
1、×
2、×
3、√
4、×
5、√
6、√
7、×
8、×
9、×10、×
二、选择题
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．构造编译程序应掌握______。
A．( )源程序B．( ) 目标语言
C．( ) 编译方法D．( ) 以上三项都是
6．四元式之间的联系是通过_____实现的。
A．( ) 指示器B．( ) 临时变量
C．( ) 符号表D．( ) 程序变量
7．表达式(┐A∨B)∧(C∨D)的逆波兰表示为_____。
A. ( ) ┐AB∨∧CD∨B．( ) A┐B∨CD∨∧
C．( ) AB∨┐CD∨∧D．( ) A┐B∨∧CD∨
8. 优化可生成_____的目标代码。
A．( ) 运行时间较短B．( ) 占用存储空间较小
C．( ) 运行时间短但占用内存空间大D．( ) 运行时间短且占用存储空间小
9．下列______优化方法不是针对循环优化进行的。
A. ( ) 强度削弱B．( ) 删除归纳变量
C．( ) 删除多余运算D．( ) 代码外提
10．编译程序使用_____区别标识符的作用域。
A. ( ) 说明标识符的过程或函数名
B．( ) 说明标识符的过程或函数的静态层次
C．( ) 说明标识符的过程或函数的动态层次
D. ( ) 标识符的行号
参考答案：
1、C
2、C
3、C
4、A
5、D
6、B
7、B
8、D
9、C 10、B
三、填空题
1．计算机执行用高级语言编写的程序主要有两种途径：_解释__和_编译_。
2．扫描器是_词法分析器_，它接受输入的_源程序_，对源程序进行_词法分析_并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。
3．自上而下分析法采用_移进_、归约、错误处理、_接受_等四种操作。
4．一个LR分析器包括两部分：一个总控程序和_一张分析表_。
5．后缀式abc-/所代表的表达式是_ a/(b-c)_。
6．局部优化是在基本块_范围内进行的一种优化。
参考答案：
1．解释编译
2．词法分析器源程序词法分析
3．移进接受
4．一张分析表
5．a/(b-c)
6．基本块
四、简答题
1. 简要说明语义分析的基本功能。
参考答案：
答：语义分析的基本功能包括: 确定类型、类型检查、语义处理和某些静态语义检查。2. 考虑文法G[S]:
S →(T) | a+S | a
T →T,S | S
消除文法的左递归及提取公共左因子。
参考答案：
解：消除文法G[S]的左递归：
S→(T) | a+S | a
T→ST′
T′→,ST′| ε
提取公共左因子：
S→(T) | aS′
S′→+S | ε
T→ST′
T′→,ST′| ε
3. 试为表达式w+(a+b)*(c+d/(e-10)+8) 写出相应的逆波兰表示。
参考答案：
解：w a b + c d e 10 - / + 8 + * +
第五套
一、判断题
1．设r和s分别是正规式，则有L(r|s)=L(r)L(s)。(N )
2．确定的自动机以及不确定的自动机都能正确地识别正规集。(Y )
3．词法分析作为单独的一遍来处理较好。(N )
4．构造LR分析器的任务就是产生LR分析表。(Y )
5．规范归约和规范推导是互逆的两个过程。(N )
6．同心集的合并有可能产生新的“移进”/“归约”冲突。(N )
7．LR分析技术无法适用二义文法。(N )
8．树形表示和四元式不便于优化，而三元式和间接三元式则便于优化。( N) 9．程序中的表达式语句在语义翻译时不需要回填技术。(Y )
10．对中间代码的优化依赖于具体的计算机。(N )
参考答案：
1、×
2、√
3、×
4、√
5、×
6、×
7、×
8、×
9、√10、×
二、选择题
1．编译程序绝大多数时间花在_____ 上。
A．( ) 出错处理B．( ) 词法分析
C．( ) 目标代码生成D．( ) 表格管理
2．编译程序是对_____。
A．( ) 汇编程序的翻译B．( ) 高级语言程序的解释执行
C．( ) 机器语言的执行D．( ) 高级语言的翻译
3．采用自上而下分析，必须_____。
A．( ) 消除左递归B．( ) 消除右递归
C．( ) 消除回溯D．( ) 提取公共左因子
4．在规范归约中，用_____来刻画可归约串。
A．( )直接短语B．( )句柄
C．( )最左素短语D．( )素短语
5．若a为终结符，则A->α·aβ为_____项目。
A．( )归约B．( ) 移进C．( ) 接受D．( ) 待约
6．间接三元式表示法的优点为_____。
A．( ) 采用间接码表，便于优化处理B．( ) 节省存储空间，不便于表的修改
C．( ) 便于优化处理，节省存储空间D．( ) 节省存储空间，不便于优化处理7．基本块内的优化为_____。
A. ( ) 代码外提，删除归纳变量B．( ) 删除多余运算，删除无用赋值
C．( ) 强度削弱，代码外提D．( ) 循环展开，循环合并
8. 在目标代码生成阶段，符号表用_____。
A．( ) 目标代码生成B．( ) 语义检查
C．( ) 语法检查D．( ) 地址分配
9．若项目集Ik含有A->α·，则在状态k时，仅当面临的输入符号a∈FOLLOW(A)时，才采取“A->α·”动作的一定是_____。
A. ( ) LALR文法B．( ) LR(0)文法
C．( ) LR(1)文法D．( ) SLR(1)文法
10．堆式动态分配申请和释放存储空间遵守_____原则。
A. ( ) 先请先放B．( ) 先请后放
C．( ) 后请先放 D. ( ) 任意
参考答案：
1、D
2、D
3、C
4、B
5、B
6、A
7、B
8、D
9、D 10、D
三、填空题
1．词法分析基于_正则__文法进行，即识别的单词是该类文法的句子。
2．语法分析基于_上下文无关__文法进行，即识别的是该类文法的句子。语法分析的有效工具是_语法树_。
3．分析句型时，应用算符优先分析技术时，每步被直接归约的是_最左质短语_，而应用LR 分析技术时，每步被直接归约的是_句柄( 最左简单短语)_。
4．语义分析阶段所生成的与源程序等价的中间表示形式可以有_逆波兰表示_、_四元式表示_与_三元式表示_等。
5．按Chomsky分类法，文法按照规则定义的形式_进行分类。
6．一个文法能用有穷多个规则描述无穷的符号串集合（语言）是因为文法中存在有_递归_定义的规则。
参考答案：
1．正则
2．上下文无关语法树
3．最左质短语句柄( 最左简单短语)
4．逆波兰表示四元式表示三元式表示
5．规则定义的形式
6．递归
四、简答题
1. 文法G[S] 为：
S->Ac|aB
A->ab
B->bc
写出L(G[S]) 的全部元素。
参考答案：
解：S=>Ac=>abc
或S=>aB=>abc
所以L(G[S])={abc}
2. 构造正规式1(0|1)*101 相应的DFA。
参考答案：
解：先构造NFA：
确定化：
重新命名，令AB为B、AC为C、ABY为D得：
所以，可得DFA为：
3. 文法
S->a|^|(T)
T->T,S|S
对(a,(a,a) 和(((a,a),^,(a)),a) 的最左推导。
参考答案：
解：对(a,(a,a)的最左推导为：
S=>(T) =>(T,S) =>(S,S) =>(a,S)
=>(a,(T)) =>(a,(T,S)) =>(a,(S,S))
=>(a,(a,S)) =>(a,(a,a))
对(((a,a),^,(a)),a) 的最左推导为：
S=>(T) =>(T,S) =>(S,S) =>((T),S)
=>((T,S),S) =>((T,S,S),S) =>((S,S,S),S)
=>(((T),S,S),S) =>(((T,S),S,S),S) =>(((S,S),S,S),S)
=>(((a,S),S,S),S) =>(((a,a),S,S),S) =>(((a,a),^,S),S) =>(((a,a),^,(T)),S) =>(((a,a),^,(S)),S) =>(((a,a),^,(a)),S) =>(((a,a),^,(a)),a)
4. 文法：
S->MH|a
H->LSo| ε
K->dML| ε
L->eHf
M->K|bLM
判断G 是否为LL(1) 文法，如果是，构造LL(1) 分析表。
参考答案：
解：各符号的FIRST集和FOLLOW集为：
预测分析表为：
由于预测分析表中无多重入口，所以可判定文法是LL(1)的。
编译原理期末考试习题及答案
一、填空题|（每题4分，共20分） 1. 乔母斯基定义的3型文法（线性文法）产生式形式 A→Ba|a,或A→aB|a，A，B∈Vn, a,b∈Vt 。 2.语法分析程序的输入是单词符号，其输出是语法单位。 3 型为 B → .aB 的LR（0）项目被称为移进项目，型为 B → a.B 的LR（0） 项目被称为待约项目， 4.在属性文法中文法符号的两种属性分别为继承属性和综合属性。 5、运行时存贮管理方案有静态存储分配、动态存储分配和堆式存储分配和方案。 二.已知文法 G(S) (1) E → T | E+T (2) T → F | F*F (3) F →（E）| i （1）写出句型（T*F+i）的最右推到并画出语法树。（4分） （2）写出上述句型的短语，直接短语和句柄。（4分） 答：（1）最右推到（2分） E ==> T ==> F ==> (E) ==> (E+T) ==> (E+F) ==> (E+i) ==> (T+i) ==> (T*F+i) (2) 语法树（2分） （3）（4分） 短语：（T*F+i），T*F+i ，T*F ， i 直接短语：T*F ， i 句柄：T*F 三. 证明文法G(S) ：S → SaS |ε是二义的。（6分） 答：句子aaa对应的两颗语法树为：
因此，文法是二义文法 四.给定正规文法G（S）： (1) S → Sa | Ab |b (2) A → Sa 请构造与之等价的DFA。（6分） 答：对应的NFA为：（6分） 状态转换表： a b {F} Φ{S} {S} {S,A} Φ {S,A} {S,A} {S} 五. 构造识别正规语言b*a(bb*a)*b* 最小的DFA（要求写出求解过程）。（15分）答：（1）对应的NFA（5分） a b {0} {1，3} {0} {1,3} Φ{2，3} {2,3} {1,3} {2,3} （5分） 六. 已知文法G(S) : (1) S → ^ | a | (T) (2) T → T,S | S 试：（1）消除文法的左递归；（4分） （2）构造相应的first 和 follow 集合。（6分） 答：（1）消除文法的左递归后文法 G’（S）为： (1) S → ^ | a | (T)
四川大学编译原理期末复习总结
一、简答题 1.什么是编译程序 答：编译程序是一种将高级语言程序(源程序)翻译成低级语言(目标程序)的程序。 将高级程序设计语言程序翻译成逻辑上等价的低级语言(汇编语言,机器语言)程序的翻译程序。 2.请写出文法的形式定义 答：一个文法G抽象地表示为四元组 G=（Vn,Vt,P,S） –其中Vn表示非终结符号 –Vt表示终结符号，Vn∪Vt=Ｖ(字母表)，Vn∩Vt=φ –S是开始符号， –P是产生式，形如：α→β(α∈V+且至少含有一个非终结符号，β∈V*) 3.语法分析阶段的功能是什么 答：在词法分析的基础上，根据语言的语法规则，将单词符号串分解成各类语法短语(例：程序、语句、表达式)。确定整个输入串是否构成语法上正确的程序。 4.局部优化有哪些常用的技术 答：优化技术1—删除公共子表达式 优化技术2—复写传播 优化技术3—删除无用代码 优化技术4—对程序进行代数恒等变换（降低运算强度） 优化技术5—代码外提 优化技术6—强度削弱 优化技术7—删除归纳变量 优化技术简介——对程序进行代数恒等变换（代数简化） 优化技术简介——对程序进行代数恒等变换（合并已知量） 5．编译过程分哪几个阶段 答：逻辑上分五个阶段：词法分析、语法分析、语义分析与中间代码生成、代码优化、目标代码生成。每个阶段把源程序从一种表示变换成另一种表示。 6. 什么是文法 答：文法是描述语言的语法结构的形式规则。是一种工具，它可用于严格定义句子的结构； 用有穷的规则刻划无穷的集合；文法是被用来精确而无歧义地描述语言的句子的构成方式；文法描述语言的时候不考虑语言的含义。 7. 语义分析阶段的功能是什么 答：对语法分析所识别出的各类语法范畴分析其含义，进行初步的翻译(翻译成中间代码)； 并对静态语义进行审查。 8.代码优化须遵循哪些原则 答：等价原则：不改变运行结果 有效原则：优化后时间更短，占用空间更少 合算原则：应用较低的代价取得较好的优化效果 9.词法分析阶段的功能是什么 答：
编译原理期末复习
编译原理期末复习 鉴于编译原理马上就要期末考试，我将手中集中的一些资料上的题目进行了整理归类，每种类型题目给出了所涉及到的基本知识，然后对每类题目中的第一道例题进行了做法进行了讲解，剩下的例题请给大家作为练习，答案也都给出，希望对大家复习有所帮助，最后由于时间很紧，整理的有些仓促，整理中难免有遗漏或错误，请大家见谅。 注：下面出现的字母中，若无特别说明，小写英文字母为终结符，大写英文字母为非终结符，希腊字母为终结符与非终结符的任意组合。 1、简答题（或者名词解释） 下面涉及到的概念中，加下划线的都是在以往一些试卷中出现的原题，务必掌握。 注：这类题目老师说答案不会超过一百个字，否则写的再多也不给分，有些点到即可，不要重复啰嗦。（1）简述编译程序的概念及其构成 答：1）编译程序：它特指把某种高级程序设计语言翻译成等价的低级程序设计语言的翻译程序。 2)构成： （2）简述词法分析阶段的主要任务（也有可能问语法分析阶段主要任务）答：词法分析的任务是输入源程序，对源程序进行扫描，识别其中的单词符号，把字符串形式的源程序转换成单词符号形式的源程序。 语法分析的主要任务是对输入的单词符号进行语法分析（根据语法规则进行推导或者归约），识别各类语法单位，判断输入是不是语法上正确的程序 (3) 简述编译程序的构造过程（这个大家看看，是对（1）和（2）的综合） 答：1）构造词法分析器：用于输入源程序进行词法分析，输出单词符号； 2）构造语法分析器：对输入的单词符号进行语法分析，识别各类语法单位，判断输入是不是语法上正确的程序 3）构造语义分析和中间代码产生器：按照语义规则对已归约出的语法单位进行语义分析并把它们翻译成中间代码。 4）构造优化器：对中间代码进行优化。 5) 构造目标代码生成器：把中间的代码翻译成目标程序。 6) 构造表格管理程序：登记源程序的各类信息和编译各阶段的进展情况。 7)构造错误处理程序：对出错进行处理。 (4) 说明编译和解释的区别： 1)编译要程序产生目标程序，解释程序是边解释边执行，不产生目标程序； 2)编译程序运行效率高而解释程序便于人机对话。 （5）文法：描述语言语法结构的形式规则，一般用一个四元式表示： G=(V T，V N，S，P)，其中V T：终结符集合(非空) V N：非终结符集合(非空)，且V T ?V N=? S：文法的开始符号，S?V N P：产生式集合(有限)。
《编译原理》考试题
《编译原理》考试题 一、选择题：（每题2分，共20分） 1.文法G所描述的语言是的集合。 A）文法G的字汇表V中所有符号组成的符号串 B）文法G的字汇表V的闭包V*中的所有符号串 C）由文法的识别符号推出的所有符号串 D）由文法的识别符号推出的所有终结符号串 2.设有文法G[S]=（{b}，{S，B}，S，{S→b|bB，B→bS}），试问该文法所描述的语言是。 A）L（G[S]）={b i|i≥0} B）L（G[S]）={b2i|i≥0} C）L（G[S]）={b2i+1|i≥0} D）L（G[S]）={b2i+1|i≥1} 3.一个句型中的最左称为该句型的句柄。 A）短语B）简单短语 C）素短语D）终结符号 4. 正则文法能产生下面的语言：L={a n b n|n≥1}。 A）存在一个B）存在多个 C）不存在D）无法判断 5.编译程序中的语法分析器接受以为单位的输入，并产生有关信息供以后各阶段使用。 A）表达式B）产生式 C）单词D）语句 6.编译方法中，自顶向下的语法分析方法有。 A）简单优先分析方法B）算符优先分析方法 C）SLR方法D）LL（1）分析方法 7.简单优先分析法每次都是对进行归约。 A）最左短语B）简单短语C）句柄D）最左素短语 8.LR语法分析栈中存放的状态是识别的DFA状态。 A）前缀B）可归前缀 C）项目D）句柄 9.表达式-（a+b）/（c-d）-（a+b*c）的逆波兰表示是（@代表单目运算-）。 A）ab+cd-/@bc*a+- B）ab+/cd@bc*a+-- C）ab+@cd-/abc*+- D）ab+cd-/abc*+@- 10.乔姆斯基（Chomsky）把文法分成四种类型，即0型、1型、2型和3型。其中，3型文法是。 A）上下文无关文法B）上下文有关文法 C）正则文法D）短语文法 二、填空题：（每空1分，共20分） 1.假设G是一个文法，S是文法的开始符号，如果S *x，则称x是。 2.已知文法G[E]：E→E+T|T，T→T*F|F，F→（E）|i；该文法的开始符号是，终结符号集合V T是，非终结符号集合V N 是，句型T+T*F+i的短语有T+T*F+i，第一个T，T*F和。 3.确定的有限自动机DFA是一个，通常表示为。 4.LL（1）分析法中，第一个L的含义是，第二个L的含义是，“1”的含义是。 5.自底向上语法分析方法的基本思想是：从待输入的符号串开始，利用文法的规则步步向上进行，试图到文法的。 6.在编译程序中安排中间代码生成的目的是和。 7.文法符号的属性有两种，一种称为，另一种称为。 8.一个程序是正确的，包含两层含义：一是；二是。 9.文法G产生的全体是该文法描述的语言。 三、判断题：（每题2分，共20分） 1.符号就是字符。 2.移进—归约法是一种语法分析方法。 3.每一个NFA都对应有唯一的一个最小化的DFA。
编译原理期末考试题目及答案
一、填空题（每空2分，共20分） 1．编译程序首先要识别出源程序中每个单词，然后再分析每个句子并翻译其意义。 2．编译器常用的语法分析方法有自底向上和自顶向下两种。 3．通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的分析，中间代码生成、代码优化与目标代码的生成则是对源程序的综合。 4．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即静态存储分配方案和动态存储分配方案。 5．对编译程序而言，输入数据是源程序，输出结果是目标程序。 1．计算机执行用高级语言编写的程序主要有两种途径：解释和编译。 2．扫描器是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。 3．自下而上分析法采用移进、归约、错误处理、接受等四种操作。 4．一个LL（1）分析程序需要用到一张分析表和符号栈。 5．后缀式abc-/所代表的表达式是a/(b-c)。 二、单项选择题（每小题2分，共20分） 1．词法分析器的输出结果是__C。 A．单词的种别编码B．单词在符号表中的位置 C．单词的种别编码和自身值D．单词自身值 2．正规式M 1 和M 2 等价是指__C_。 A．M1和M2的状态数相等 B．M1和M2的有向边条数相等 C．M1和M2所识别的语言集相等D．M1和M2状态数和有向边条数相等 3．文法G：S→xSx|y所识别的语言是_C____。 A．xyx B．(xyx)* C．xnyxn(n≥0) D．x*yx* 4．如果文法G是无二义的，则它的任何句子α_A____。 A．最左推导和最右推导对应的语法树必定相同B．最左推导和最右推导对应的语法树可能不同 C．最左推导和最右推导必定相同D．可能存在两个不同的最左推导，但它们对应的语法树相同5．构造编译程序应掌握____D__。 A．源程序B．目标语言C．编译方法D．以上三项都是 6．四元式之间的联系是通过__B___实现的。 A．指示器B．临时变量C．符号表D．程序变量 7．表达式(┐A∨B)∧(C∨D)的逆波兰表示为__B___。 A．┐AB∨∧CD∨B．A┐B∨CD∨∧ C．AB∨┐CD∨∧D．A┐B∨∧CD∨ 8. 优化可生成__D___的目标代码。 A．运行时间较短 B．占用存储空间较小 C．运行时间短但占用内存空间大D．运行时间短且占用存储空间小 9．下列___C___优化方法不是针对循环优化进行的。 A. 强度削弱B．删除归纳变量C．删除多余运算D．代码外提 10．编译程序使用_B_区别标识符的作用域。 A. 说明标识符的过程或函数名B．说明标识符的过程或函数的静态层次 C．说明标识符的过程或函数的动态层次 D. 标识符的行号 三、判断题（对的打√，错的打×，每小题1分，共10分） 2．一个有限状态自动机中，有且仅有一个唯一的终态。x
《编译原理》模拟期末试题汇总 6套,含答案
《编译原理》模拟试题一 一、是非题（请在括号内，正确的划√，错误的划×）（每个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．( ) 语法分析B．( )文法分析C．( )语言分析D．( )解释分析 2．词法分析器用于识别_____。 A．( ) 字符串B．( )语句 C．( )单词 D．( )标识符 3．语法分析器则可以发现源程序中的_____。 A．( ) 语义错误 B．( ) 语法和语义错误 C．( ) 错误并校正D．( ) 语法错误 4．下面关于解释程序的描述正确的是_____。
(1) 解释程序的特点是处理程序时不产生目标代码 (2) 解释程序适用于 COBOL 和 FORTRAN 语言 (3) 解释程序是为打开编译程序技术的僵局而开发的 A．( ) (1)(2) B．( ) (1)C．( ) (1)(2)(3) D．( ) (2)(3) 5．解释程序处理语言时 , 大多数采用的是_____方法。 A．( ) 源程序命令被逐个直接解释执行 B．( ) 先将源程序转化为中间代码 , 再解释执行 C．( ) 先将源程序解释转化为目标程序 , 再执行 D．( ) 以上方法都可以 6．编译过程中 , 语法分析器的任务就是_____。 (1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的 (3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构 A．( ) (2)(3) B．( ) (2)(3)(4) C．( ) (1)(2)(3) D．( ) (1)(2)(3)(4) 7．编译程序是一种_____。 A. ( ) 汇编程序B．( ) 翻译程序 C．( ) 解释程序 D．( ) 目标程序 8．文法 G 所描述的语言是_____的集合。 A. ( ) 文法 G 的字母表 V 中所有符号组成的符号串 B．( ) 文法 G 的字母表 V 的闭包 V* 中的所有符号串 C．( ) 由文法的开始符号推出的所有终极符串 D. ( ) 由文法的开始符号推出的所有符号串 9．文法分为四种类型，即0型、1型、2型、3型。其中3型文法是_____。 A. ( ) 短语文法 B．( ) 正则文法 C．( ) 上下文有关文法 D．( ) 上下文无关文法 10．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 _____。 A．( ) 句子B．( ) 句型 C．( ) 单词 D．( ) 产生式 三、填空题(每空1分，共10分)
编译原理试题(卷)汇总-编译原理期末试题(卷)(8套含答案解析-大题集)
编译原理考试题及答案汇总 一、选择 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/d 6．一个编译程序中，不仅包含词法分析，_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___。 (1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的 (3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构 A．( ) (2)(3) B．( ) (2)(3)(4)C．( ) (1)(2)(3) D．( ) (1)(2)(3)(4) 12．编译程序是一种___C__。 A. ( ) 汇编程序 B．( ) 翻译程序 C．( ) 解释程序 D．( ) 目标程序 13．文法 G 所描述的语言是_C____的集合。 A. ( ) 文法 G 的字母表 V 中所有符号组成的符号串 B．( ) 文法 G 的字母表 V 的闭包 V* 中的所有符号串 C．( ) 由文法的开始符号推出的所有终极符串 D. ( ) 由文法的开始符号推出的所有符号串 14．文法分为四种类型，即 0 型、1 型、2 型、3 型。其中 3 型文法是___B__。 A. ( ) 短语文法 B．( ) 正则文法 C．( ) 上下文有关文法 D．( ) 上下文无关文法15．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 __D___。 A．( ) 句子 B．( ) 句型 C．( ) 单词 D．( ) 产生式 16．通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括_C____。
期末考试编译原理试卷及答案
一． 填空题（每空2分，共20分） 1. 不同的编译程序关于数据空间的存储分配策略可能不同，但大部分编译中采用的方案有两种：静 态存储分配方案和动态存储分配方案，而后者又分为（1） 和 （2） 。 2. 规范规约是最（3）规约。 3. 编译程序的工作过程一般划分为5个阶段：词法分析、（4） 、语义分析与中间代码生成，代码优化及（5） 。另外还有（6）和出错处理。 4．表达式x+y*z/(a+b)的后缀式为 （7） 。 5．文法符号的属性有综合属性和 （8）。 6．假设二位数组按行存放，而且每个元素占用一个存储单元，则数组a[1..15,1..20]某个元素a[i ，j]的地址 计算公式为（9）。 7．局部优化是局限于一个（10）范围内的一种优化。 二． 选择题（1-6为单选题，7-8为多选题，每问2分，共20分） 1. 一个上下文无关文法G 包括四个组成部分：一组终结符，一组非终结符，一个（ ），以及一组 （ ）。 A ． 字符串 B ． 产生式 C ． 开始符号 D ． 文法 2.程序的基本块是指（ ）。 A ． 一个子程序 B ． 一个仅有一个入口和一个出口的语句 C ． 一个没有嵌套的程序段 D ． 一组顺序执行的程序段，仅有一个入口和一个出口 3. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于（ ）分析方法。 A ． 自左向右 B ． 自顶向下 C ． 自底向上 D ． 自右向左 4．在通常的语法分析方法中，（ ）特别适用于表达式的分析。 A ． 算符优先分析法 B ． LR 分析法 C ． 递归下降分析法 D ． LL （1）分析法 5．经过编译所得到的目标程序是（ ）。 A ． 四元式序列 B ． 间接三元式序列 C ． 二元式序列 D ． 机器语言程序或汇编语言程序 6． 一个文法所描述的语言是（ ）；描述一个语言的文法是（ ）。 A ． 唯一的 B ． 不唯一的 C ． 可能唯一，也可能不唯一 7． 如果在文法G 中存在一个句子，当其满足下列条件（ ）之一时，则称该文法是二义文法。 A ． 其最左推导和最右推导相同 B ． 该句子有两个不同的最左推导 C ． 该句子有两个不同的最右推导 D ． 该句子有两棵不同的语法树
编译原理试题
中间语言与语法制导翻译重点与难点 重点：语法制导翻译的基本思想，属性文法，翻译模式，说明语句的翻译方案。 三地址码，各种语句的目标代码结构、属性文法与翻译模式。 难点：属性的意义，对综合属性，继承属性，固有属性的理解，属性计算，怎么通过属性来表达翻译。布尔 表达式的翻译，对各种语句的目标代码结构、属性文法与翻译模式的理解。 基本要求 掌握语法制导翻译的基本思想，属性文法，综合属性，继承属性，固有属性，属性计算，s_属性文法, L_属性文法，说明语句的翻译方案，翻译模式、属性文法的实现 掌握中间语言与语义分析的基本概念；熟练掌握语法(结构)树、三地址代码、赋值与控制语句的翻译、 说明语句的翻译；掌握组合数据说明的翻译、过程调用翻译。 例题解析 例1 给定文法E --> T { R.i := T.p } R { E.p := R.s } R --> addop T { R1.i := mknode( addop.val, R.i, T.p ) } R { R.s := R1.s } R --> : { R.s := R1.s } T --> ( E ) { T.p := E.p } T --> id { T.p := mkleaf( id, id.entry) } T --> num { T.p := mkleaf( n um, n um.val ) } (1) 指岀文法中的各非终结符具有哪些综合属性和哪些继承属性 ⑵ 画岀按本翻译模式处理表达式 a + 20 + ( b - 10 ) 时所生成的语法树 【解】 (1)E的综合属性p，R的继承属性i，综合属性s ; T的综合属性p ⑵处理表达式a + 20 + ( b - 10 ) 时所生成的语法树如下 例2定义一个计算器的属性文法，完成一个输入表达式值的计算和显示 【解】计算器的文法 L T E E T E1 + T | T T T T1 * F | F F T ( E ) | digit
编译原理期末复习题
3.2是非判断，对下面的述，正确的在述后的括号写T，否则写F。 (1)有穷自动机接受的语言是正则语言。（） (2)若r1和r2是Σ上的正规式，则r1|r2也是。（） (3)设M是一个NFA，并且L(M)＝{x,y,z}，则M的状态数至少为4个。（） (4)令Σ＝{a,b}，则Σ上所有以b为首的字构成的正规集的正规式为b*(a|b)*。（） (5)对任何一个NFA M，都存在一个DFA M'，使得L(M')=L(M)。（） (6)对一个右线性文法G，必存在一个左线性文法G'，使得L(G)=L(G')，反之亦然。（） 答案 (1) T (2) T (3) F (4) F (5) T (6) T 3.3描述下列各正规表达式所表示的语言。 (1) 0(0|1)*0 (2) ((ε|0)1*)* (3) (0|1)*0(0|1)(0|1) (4) 0*10*10*10* (5) (00|11)*((01|10)(00|11)*(01|10)(00|11)*)* 答案 (1) 以0开头并且以0结尾的，由0和1组成的符号串。 (2) {α|α∈{0,1}*} (3) 由0和1组成的符号串，且从右边开始数第3位为0。 (4) 含3个1的由0和1组成的符号串。{α|α∈{0,1}+，且α中含有3个1 } (5) {α|α∈{0,1}*,α中0和1为偶数} 3.4对于下列语言分别写出它们的正规表达式。 (1) 英文字母组成的所有符号串，要求符号串中顺序包含五个元音。 (2) 英文字母组成的所有符号串，要求符号串中的字母依照词典顺序排列。 (3) Σ={0,1}上的含偶数个1的所有串。 (4) Σ={0,1}上的含奇数个1的所有串。 (5) 具有偶数个0和奇数个1的有0和1组成的符号串的全体。 (6) 不包含子串011的由0和1组成的符号串的全体。 (7) 由0和1组成的符号串,把它看成二进制数，能被3整除的符号串的全体。 答案 (1) 令Letter表示除这五个元音外的其它字母。 ((letter)*A(letter)*E(letter)*I(letter)*O(letter)*U(letter))* (2) A*B*....Z* (3) (0|10*1)* (4) (0|10*1)*1
《编译原理》期末考试复习题
《编译原理》期末考试复习题 一、是非题（请在括号内，正确的划√，错误的划×）（每个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．简单优先文法允许任意两个产生式具有相同右部。 () 三、填空题(每空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分，共20分） ×1．对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。() ×2．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。() √3．递归下降分析法是自顶向上分析方法。() ×4．产生式是用于定义词法成分的一种书写规则。() √5．LR 法是自顶向下语法分析方法。() √6．在SLR （1 ）分析法的名称中，S的含义是简单的。() ×7．综合属性是用于“ 自上而下” 传递信息。() ×8．符号表中的信息栏中登记了每个名字的属性和特征等有关信息，如类型、种属、所占单元大小、地址等等。() ×9．程序语言的语言处理程序是一种应用软件。() ×10．解释程序适用于COBOL 和FORTRAN 语言。() 三、填空题(每空1分，共10分) 1．一个句型中的最左简单短语称为该句型的___句柄__。
(2020年整理)编译原理期末总复习题(含答案).doc
第八节习题一、单项选择题 1、将编译程序分成若干个“遍”是为了 b 。 a．提高程序的执行效率 b．使程序的结构更加清晰 c．利用有限的机器内存并提高机器的执行效率 d．利用有限的机器内存但降低了机器的执行效率 2、构造编译程序应掌握 d 。 a．源程序b．目标语言 c．编译方法d．以上三项都是 3、变量应当 c 。 a．持有左值b．持有右值 c．既持有左值又持有右值d．既不持有左值也不持有右值 4、编译程序绝大多数时间花在 b 上。 a．出错处理b．词法分析 c．目标代码生成d．管理表格 5、 d 不可能是目标代码。 a．汇编指令代码b．可重定位指令代码 c．绝对指令代码d．中间代码 6、使用 a 可以定义一个程序的意义。 a．语义规则b．词法规则 c．产生规则d．词法规则 7、词法分析器的输入是 a 。 a．单词符号串b．源程序 c．语法单位d．目标程序 8、中间代码生成时所遵循的是- d 。 a．语法规则b．词法规则 c．语义规则d．等价变换规则 9、编译程序是对 d 。 a．汇编程序的翻译b．高级语言程序的解释执行 c．机器语言的执行d．高级语言的翻译 10、语法分析应遵循 b 。 a．语义规则b．语法规则 c．构词规则d．等价变换规则 解答 1、将编译程序分成若干个“遍”是为了使编译程序的结构更加清晰，故选b。 2、构造编译程序应掌握源程序、目标语言及编译方法等三方面的知识，故选d。 3、对编译而言，变量既持有左值又持有右值，故选c。 4、编译程序打交道最多的就是各种表格，因此选d。 5、目标代码包括汇编指令代码、可重定位指令代码和绝对指令代码3种，因此不是目标代码的只能选d。 6、词法分析遵循的是构词规则，语法分析遵循的是语法规则，中间代码生成遵循的是语义规则，并且语义规则可以定义一个程序的意义。因此选a。 7、b 8、c 9、d 10、c 二、多项选择题
编译原理考试试卷
南京工业大学继续教育学院编译原理期末考试试卷 (2012-2013学年) A卷 一、选择题（每题2分，共20分） 得分 1. 一个上下文无关文法G包括四个组成部分：一组终结符，一组非终结符，一个_____，以及一组产生式。 A．字符串 B．运算符号 C．开始符号 D．文法 2.程序的基本块是指_____。 A．一个子程序 B．一个仅有一个入口和一个出口的语句 C．一个没有嵌套的程序段 D．一组顺序执行的程序段，仅有一个入口和一 个出口 3. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于_____分析方法。 A．自左向右 B．自顶向下 C．自底向上 D．自右向左 4．经过编译所得到的目标程序是_____。 A．四元式序列 B．间接三元式序列 C．二元式序列 D．机器语言程序或汇编语言程序 5．运行阶段的存储组织与管理的目的是_____。 ①提高编译程序的运行速度②节省编译程序的存储空间 ③提高目标程序的运行速度④为运行阶段的存储分配做准备 A. ①② B. ②③ C. ③④ D. ④②6．词法分析器的输出结果是_____。 A．( ) 单词的种别编码B．( ) 单词在符号表中的位置C．( ) 单词的种别编码和自身值D．( ) 单词自身值 7．正规式M 1 和M 2 等价是指_____。
A．( ) M1和M2的状态数相等B．( ) M1和M2的有向边条数相等 C．( ) M1和M2所识别的语言集相等D．( ) M1和M2状态数和有向边条数相等 8．文法G：S→xSx|y所识别的语言是_____。 A．( ) xyx B．( ) (xyx)* C．( ) xnyxn(n≥0) D．( ) x*yx* 9．语言是_____。 A．句子的集合B．产生式的集合 C．符号串的集合D．句型的集合 10．编译程序前三个阶段完成的工作是 A．词法分析、语法分析和代码优化 B．代码生成、代码优化和词法分析 C．词法分析、语法分析、语义分析和中间代码生成 D．词法分析、语法分析和代码优化 二、名词解释（每题2分，共20分） 得分 1.最左推导： 2.语法： 3.文法： 4.基本块： 5.语法制导翻译： 6.短语： 7.规范句型：
编译原理考试试题1
编译原理 一、(5×6分)回答下列问题： 1．什么是S-属性文法？什么是L-属性文法？它们之间有什么关系？ 2．什么是句柄？什么是素短语？ 3．划分程序的基本块时，确定基本块的入口语句的条件是什么？ 4．运行时的DISPLAY 表的内容是什么？它的作用是什么？ 5．对下列四元式序列生成目标代码： A:=B*C D:=E+F G:=A+D H:=G*2 其中，H 是基本块出口的活跃变量， R0和R1是可用寄存器 二、(8分)设∑={0，1}上的正规集S 由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA 。 三、(6分)写一个文法使其语言为L(G)={ a n b m a m b n | m,n ≥1}。 四、(8分)对于文法G(E): E →T|E+T T →F|T* F F →(E)|i 1. 写出句型(T*F+i)的最右推导并画出语法树。 2. 写出上述句型的短语，直接短语、句柄和素短语。 五、(12分)设文法G(S)： ( |*)B B |B A A A |SiA S A →+→→ 1．构造各非终结符的FIRSTVT 和LASTVT 集合； 2．构造优先关系表和优先函数。 六、(9分)设某语言的do-while 语句的语法形式为 S → do S (1) While E 其语义解释为： 真 假 S (1)的代码 E 的代码
针对自下而上的语法分析器，按如下要求构造该语句的翻译模式： (1) 写出适合语法制导翻译的产生式； (2) 写出每个产生式对应的语义动作。 七、(8分)将语句if (A
编译原理试题及答案(期末复习版).pdf
<编译原理>历年试题及答案 一．（每项选择 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^^*是文法的句型，指出该句型的短语、简单短语和句柄.
编译原理期末试题及答案
2、写出表达式a＋b*(c-d)/e的逆波兰式和三元序列。 3、写出表达式a:=(b+c)*e+(b+c)/f的逆波兰式和三元序列。 4、已知文法G(S)及相应翻译方案 S→aAb {print “1”} S→a {print “2”} A→AS {print “3”} A→c {print “4”} 输入acab, 输出是什么 5、已知文法G(S) S→bAa A→(B | a B→Aa) 写出句子b(aa)b的规范归约过程。 6、已知文法G[S] S→S*aF | aF | *aF F→+aF | +a 消除文法左递归。 1、设文法G(S): S→^ | a | (T) T→T,S | S ⑴消除左递归； ⑵构造相应的FIRST和FOLLOW集合； ⑶构造预测分析表 2.语句if E then S (1) 改写文法，使之适合语法制导翻译； (2) 写出改写后产生式的语义动作。 4.设某语言的for语句的形式为 for i:＝E(1) to E(2) do S 其语义解释为 i:＝E(1) LIMIT:＝E(2) again: if i＜＝LIMIT then Begin S; i:＝i＋1 goto again End; （1）写出适合语法制导翻译的产生式； （2）写出每个产生式对应的语义动作。 7.已知文法G(S) S→a | ^ | (T) T→T,S | S (1) 给出句子(a,(a,a))的最左推导； (2) 给出句型((T,S),a)的短语, 直接短语，句柄。 8.对于C 语言do S while E语句 (1)改写文法，使之适合语法制导翻译；
(2)写出改写后产生式的语义动作。 9.已知文法G(S) S→aAcBe A→Ab| b B→d (1)给出句子abbcde的最左推导及画出语法树； (2)给出句型aAbcde的短语、素短语。 10.设文法G(S): S→(T) | aS | a T→T,S | S ⑴消除左递归和提公共左因子； ⑵构造相应的FIRST和FOLLOW集合； ⑶构造预测分析表。 12.已知文法G(S) E→E+T | T T→T*F| F F→(E)| i (1) 给出句型(i+i)*i+i的最左推导及画出语法树； (2) 给出句型(E+T)*i+F 的短语，素短语和最左素短语。 答案： (1)消除左递，文法变为G’[S]： S→^ | a | (T)' T→ST’ | S T’→,ST’ |ε 此文法无左公共左因子。 (2)构造相应的FIRST和FOLLOW集合： FIRST(S)={a, ^, (}，FOLLOW(S)={#, ,, )} FIRST(T)={a, ^, (} ，FOLLOW(T)={}} FIRST(T’)={,, ε} ，FOLLOW(F)={)} (3) C→if E then S→CS(1) (2) C→if E then {BACK, NXQ); :=} S→CS(1) {:=MERG, S(1). Chain)} 4. (1) F→for i:=E(1) to E(2) do S→FS(1) (2)F→for i:=E(1) to E(2) do {GEN(:=, E(1).place, _, entry(i)); :=entry(i);
(完整word版)编译原理期末试题(二)含答案,推荐文档
《编译原理》期末试题（二） 一、是非题： 1.一个上下文无关文法的开始符，可以是终结符或非终结符。 ( ) 2.一个句型的直接短语是唯一的。（） 3.已经证明文法的二义性是可判定的。（） 4.每个基本块可用一个DAG表示。（） 5.每个过程的活动记录的体积在编译时可静态确定。（） 6.2型文法一定是3型文法。（） 7.一个句型一定句子。 ( ) 8.算符优先分析法每次都是对句柄进行归约。 X ( ) 9.采用三元式实现三地址代码时，不利于对中间代码进行优化。（） 10.编译过程中，语法分析器的任务是分析单词是怎样构成的。 ( ) 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.×7.×8.× 9.√10.× 11.× 12.√ 13.× 14.√ 15.√ 16.√ 17.× 18.√19.√ 20.×21.√22.√ 二、填空题： 2.编译过程可分为（词法分析），（语法分析），（语义分析与中间代码生成），（优化）和（目标 代码生成）五个阶段。 3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（二义性的）。 4.从功能上说，程序语言的语句大体可分为（执行性）语句和（说明性）语句两大类。 5.语法分析器的输入是（单词符号），其输出是（语法单位）。 6.扫描器的任务是从（源程序中）中识别出一个个（单词符号）。 7.符号表中的信息栏中登记了每个名字的有关的性质，如(类型、种属、所占单元大小、地址）等等。 8.一个过程相应的DISPLAY表的内容为(现行活动记录地址和所有外层最新活动记录的地址) 10.常用的两种动态存贮分配办法是（栈式）动态分配和（堆式）动态分配。 11.一个名字的属性包括( 类型)和(作用域 )。 12.常用的参数传递方式有(传地址），（传值），（传名） 13.根据优化所涉及的程序范围，可将优化分成为(局部优化），（循环优化），（全局优化）三个级别。 14.语法分析的方法大致可分为两类，一类是（自上而下）分析法，另一类是（自下而上） 分析法。 15.预测分析程序是使用一张（分析表）和一个（符号栈）进行联合控制的。 17.一张转换图只包含有限个状态,其中有一个被认为是（初）态;而且实际上至少要有一个（终）态。 19.语法分析是依据语言的（语法）规则进行。中间代码产生是依据语言的（语义）规则进行的。 21.一个文法G，若它的预测分析表M不含多重定义，则该文法是（LL(1) 文法）文法。 22.对于数据空间的存贮分配， FORTRAN采用( 静态策略， PASCAL采用( 动态)策略。
- 编译原理试题汇总+编译原理期末试题(8套含标准答案+大题集)
- 编译原理期末试题8套含答案大题集
- 编译原理期末考试试卷及答案62172
- 编译原理期末考试题汇总
- 编译原理期末考试题目及答案
- 编译原理期末考试习题及答案
- 编译原理试题答案
- 编译原理期末试题及答案
- 编译原理试题
- 编译原理期末试题
- 编译原理期末考试习题及答案
- 编译原理试题(卷)汇总-编译原理期末试题(卷)(8套含答案解析-大题集)
- 编译原理期末考试试题
- 编译原理期末试题答案
- 《编译原理》模拟期末试题汇总套含答案
- 编译原理期末试题及答案
- 编译原理2008期末考试试卷答案
- 期末考试编译原理试卷及答案
- 编译原理期末试题(8套含答案+大题集)
- 编译原理期末考试试卷A卷