计算机编译原理复习题附答案

编译原理（一）

一、是非题

1、算符优先关系表不一定存在对应的优先函。………………………………………（√）

2、数组元素的地址计算与数组的存储方式有关。……………………………（√）

3、仅考虑一个基本块，不能确定一个赋值是否真是无用的。……………………（√）

4、每个文法都能改写为LL(1)文法。……………………………………………（×）

5、对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。…………（×）

二、填空题

1、从功能上说，程序语言的语句大体可分为（执行性）语句和（说明性）语句两大类。

2、扫描器的任务是从（源程序）中识别出一个个（单词符号）。

3、所谓最右推导是指：（任何一步α β都是对α中最右非终结符进行替换的）。

4、语法分析最常用的两类方法是（自上而下）和（自下而上）分析法。

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

）。

6、所谓语法制导翻译方法是（为每个产生式配上一个翻译子程序，并在语法分析的同时执行这些子程序）。

7、符号表中的信息栏中登记了每个名字的有关的性质，如（类型、种属、所占单元大小、地址）等等。

8、一个过程相应的DISPLAY表的内容为（现行活动记录地址和所有外层最新活动记录的地址）。

9、常用的两种动态存贮分配办法是（栈式）动态分配和（堆式）动态分配。

10、产生式是用于定义（语法范畴）的一种书写规则。

三、名词解释

1、遍－－_指编译程序对源程序或中间代码程序从头到尾扫描一次。

2、无环路有向图(DAG)－－如果有向图中任一通路都不是环路，则称庐有向图为无环路有向图，简称DAG。

3、语法分析－－按文法的产生式识别输入的符号串是否为一个句子的分析过程

4、短语－－—令G是一个文法。S划文法的开始符号，假定αβδ是文法G的一个句

型，如果有SαAδ且AB，则称β是句型αβ相对非终结符A的短语。

5、后缀式－－一种把运算量（操作数）写在前面把算符写在后面（后缀）的表示法。

四、简述题

1、考虑下面程序

…………

Var a：integer；

Procedure S(X)；

Var X：integer；

Begin

a：＝a＋1；

X：＝a＋X

End；

Begin

a：＝5；

S(a)；

Print(a)

End．

试问：若参数传递方式分别采取传名和传值时，程序执行后输出a的值是什么？

1、答：传名：a＝12(2分)

传值：a＝6(2分)

2、画出Pascal中实数(不带正负号，可带指数部分)的状态转换图。

3、写出表达式(a＋b*c)/(a＋b)－d的逆波兰表示及三元式序列。Yi

3、答：逆波兰表示：

abc*＋ab＋/d－(2分)

三元式序列：

① (*，b，c)

② (＋，a，①)

③ (＋，a，b)

④ (/，②，③)

⑤ (－，④，d)(2分)

4、已知文法G(S) san

S→a|∧|(T)

T→T，S|S

写出句子((a，a)，a)的规范归约过程及每一步的句柄。

4、答：句型归约规则句柄

((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)

S(4分)

5、何谓优化？按所涉及的程序范围可分为哪几级优化？

5、答：优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目标代码。(2分)

三种级别：局部优化、循环优化、全局优化。(2分)

6、目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？

答：目标代码通常采用三种形式：机器语言，汇编语言，待装配机器语言模块。(2分) 应着重考虑的问题：

(1)如何使生成的目标代码较短；

(2)如何充分利用寄存器，以减少访问内存次数；

(3)如何充分利用指仅系统的的特点。(2分)

五、计算题

1、写一个文法，使其语言是奇数集，且每个奇数不以0开头。

1、解：文法G(N)：

N→AB|B

A→AC|D

B→1|3|5|7|9

D→B|2|4|6|8

C→0|D(5分)

2、设文法G(S)：si

S→(L)|a S|a

L→L，S|S

(1) 消除左递归和回溯；

(2) 计算每个非终结符的FIRST和FOLLOW；

(3) 构造预测分析表。

2、解:(1)

S→(L)|aS'

S'→S|ε

L→SL'

L'→SL'|ε

评分细则：消除左递归2分，提公共因子2分。

(2)

FIRST)S)＝{(，a}FOLLOW(S)＝{#，，，)}

FIRST(S')＝{，a,ε}FOLLOW(S')＝{#，，，)}

FIRST(L)＝{(，a}FOLLOW(L)＝{ )}

FIRST(L')＝{，，ε}FOLLOW(L'〕＝{ )}

3、While a＞0 ∨b＜0do

Begin

X：＝X＋1；

if a＞0 then a：＝a－1

else b：＝b＋1

End；

翻译成四元式序列。

3、解：

(1) (j＞，a，0，5)

(2) (j，－，－，3)

(5) (＋，×，1，T1)

(6) (：＝，T1，－，×)

(7) (j≥，a，0，9)

(8) (j，－，－，12)

(9) (－，a，1，T2)

(10) (：＝，T2，－，a)

(11) (j，－，－，1)

(12) (＋，b，1，T3)

(13) (：＝，T3，－，b)

(14) (j，－，－，1)

(15)

评分细则：控制结构4分，其它3分。

4、已知文法G(E) wu

E→T|E＋T

T→F|T * F

F→(E)|i

(1) 给出句型(T * F＋i)的最右推导及画出语法树；

(2) 给出句型(T * F＋i)的短语、素短语。

4、解：(1) 最右推导：

ETF(E)(E＋T)(E＋F)(E＋i)

(T＋i)(T*F＋i)

(2) 短语：(T*F＋i)，T*F＋i，T*F，i(2分)

素短语：T*F,i (1分)

5、设布尔表达式的文法为

E → E(1)∨E(2)

E → E(1)∧E(2)

E → i

假定它们将用于条件控制语句中，请

(1) 改写文法，使之适合进行语法制导翻译和实现回填；

(2) 写出改写后的短个产生式的语义动作。

5、解：(1) E0→E(1)

E→E0E(2)

EA→E(1)

E→EAE(2)

E→i(3分)

(2) E→E(1)

{BACKPATCH(E(1)·FC，NXQ)；

E0·TC：＝E(1)·TC}

E→E0E(2)

{E·FC：＝E(2)·FC；

E·TC：＝MERG(E0·TC，E(2)·TC)}

EA→E(1)

{BACKPA TCH(E(1)·TC，NXQ)；

E0·FC：＝E(1)·FC}

E→EAE(2)

{E·TC：＝E(2)·TC；

E·FC：＝MERG(EA·FC，E(2)·FC}

E→i

{E·TC：＝NXQ；E·FC：＝NXQ＋1；

GEN(jn2，entry(i)，－0)；

GEN(j，－，－，0)(3分)

6、设有基本块liu

T1：＝2

T2：＝10/T

T3：＝S－R

T4：＝S＋R

A：＝T2 * T4

B：A

T5：＝S＋R

T6：＝T3 * T5

B：＝T6

(1) 画出DAG图；

(2) 假设基本块出口时只有A，B还被引用，请写出优化后的四元序列。

6、解：(1)DAG：

(2) 优化后的四元式

T3：＝S－R

T4：＝S＋R

A：＝5*T4

B：＝T3＋T4(3分)

https://www.wendangku.net/doc/6a3405800.html,/jp2005/20/kcwz/stk/mnst/mnst2.htm

编译原理（二）

一选择题

【 B 】1．词法分析器的输入是。

A．符号串B．源程序C．语法单位D．目标程序

【 C 】2．两个有穷自动机等价是指它们的。

A．状态数相等B．有向弧数相等

C．所识别的语言相等 D．状态数和有向弧数相等

【 C 】3．文法G：S → xSx | y 所识别的语言是。

A．xy*x B．(xyx)* C．xx*yxx* D．x*yx*

【】4．设a,b,c为文法的终结符，且有优先关系a≡b和b≡c，则。

A．必有a≡c B．必有c≡a

C．必有b≡a D．选项A、B和C都不一定成立

【 D 】5．若状态k含有项目“A→α.”，且仅当输入符号a∈FOLLOW(A)时，才用规则“A →α”归约的语法分析方法是。

A．LALR分析法B．LR(0)分析法

C．LR(1)分析法D．SLR(1)分析法

【 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∨

【 A 】8．基本块。

A．只有一个入口语句和一个出口语句B．有一个入口语句和多个出口语句

C．有多个入口语句和一个出口语句D．有多个入口语句和多个出口语句

二判断题

【T 】1．同心集的合并有可能产生“归约/归约”冲突。

【】2．一个文法所有句子的集合构成该文法定义的语言。

【】3．非终结符可以有综合属性，但不能有继承属性。

【】4．逆波兰表示法表示表达式时无需使用括号。

【】5．一个有穷自动机有且只有一个终态。

【】6．若过程p第k次被调用，则p的DISPLAY表中就有k+1个元素。

三填空题

1．最常用的两类语法分析方法是自上而下和自下而上分析法。

2．对于文法G[E]：E→T|E+T T→F|T*F F→P↑F|P P→(E)|i,句型T+T*F+i的直接短语为，句柄为。

V则称“A →α.”为项目，称3．在LR(0)分析法中，若α,β∈V*且a∈T

“S →α.aβ”为项目。

4．在PL/0的目标代码解释执行时，寄存器B总是指向当前执行过程活动记录的，而寄存器T总是指向。

四（7分）有穷自动机M接受字母表∑＝{0,1}上所有满足下述条件的串：串中至少包含两个连续的0或两个连续的1。请写出与M等价的正规式。qi

五（8分）构造下列文法相应的有穷自动机。ba

G[S]：S →aA | bQ

A →aA | b

B | b

B →bD | aQ

Q →aQ | bD | b

D →bB | aA

E →aB | bF

F →bD | aE | b

六（8分）写一个文法，使其语言是：

L ＝{ ambmanbn | m,n≥0 }

七（12分）已知文法

G[A]： A →aAB | a

B →Bb | d

（1）构造与G[A]等价的LL(1)文法；

（2）构造G’[A]的预测分析表。

八（12分）考虑文法

G[S]: S → AS | b A → SA | a

（1）构造文法的可归前缀图（活前缀的DFA ）； （2）判断文法是否是LR(0)文法，并说明理由。 九（7分）将下面程序段翻译成四元式序列。 er while A

procedure p(x,y,z:integer); begin y:=y+1; z:=z+x end; begin

a:=2; b:=3; p(a+b,a,a); write(a) end.

对于下列参数传递方式，分别写出执行程序后a 的输出值。 （1）传名； （2）传地址。

编 译 原 理（三）

一、:请写出由下列文法所确定的语言. 1. G1: S →10S01 S →aA A →bA A →a

2. G2: S →aSS S →a

1、解：

n m n n m n m

n

n n n n n n

a a

b A ab abA aA S S S S )01()10()01()10()01()10()01()10()01()10(010*********???????

所以语言{n

m n a ab )01()10(} n>=0,m>=0

2、解：1

2*

+??????n a S aaaaaaa

aaSSaSS S aaaaa aaSSS S aaa

S

所以语言{ 1

2+n a

} n>=0

证明文法G1和G2等价 G1：S →0S1，S →01

G2：A →0R ，A →01，R →A1

证明：n

n n n n S S S S 1010110010111

????---

n n n n n A A R A R A 10101100100100111

??????---

因为两个文法的语言相同，所以文法G1，G2等价 三、令文法G 为 E →T|E+T|E-T T →F|T*F|T/F F →（E ）|i

给出句子i+i*i 的最左推导和i*(i+i)的最右推导，并给出相应的语法树 试证明符号串T*F+i 是G 的一个句型(要求画出语法树). 写出T*F+i 句型的所有短语,直接短句和句柄.

解：i

i i F i i F

F i F T i T i T F T T T E E ****.1+?+?+?+?+?+?+?+?

)(*)(*)(*)(*)(*)(*)

(*)(*)(**i i i i i F i i T i F T i T T i E T F E T T E T E T F T T E +?+?+?+?+?+?+?+????

2、证明：i F T F F T T F T T T T E E +?+?+?+?+?***

E E + T T F

T * F i

3、短语：T*F+i,T*F,i,

直接短语：T*F,i 句柄：T*F

四、构造以下正规式相应的NFA ，再确定化 10（1|0）*11

G ：S →A|B A →aA|a B →bB|b

解：因为}{)()(}

{)()((b b B Select bB B Select a a A Select aA A aSelect A Select =→→=→→→

所以此文法不是LL （1）文法 产生式A ，B 有左公因子 提取左公因子得：

εεεε→→→?→→→→?→'''

)|(''')|(B B

B bB B B b B A A A aA A A a A

故文法为ε

ε

→→→→→→→→'''

'''B B

B bB B A A

A aA A

B S A

S

判断此文法是否为LL （1）文法

φεφεφ

===→→===→→==→→)(}{)'()()'()'()(}{)'()()'()'()()()()(S follow b B follow B first B select B B select S follow a A follow A first A select A A select B first A first B S select A S select

因为它们的SELECT 集交集为空，所以转化后的文法为LL （1）文法

编 译 原 理（四）

1．写出字母表∑ = {a, b}上语言L = {w | w 中a 的个数是偶数}的正规式，并画出接受该语言的最简DFA 。

答：1．语言L 的正规式是： (a b*a | b)* 或 b*(a b*a b*)* 接受该语言的最简DFA 是：

2．考虑下面的表达式文法，它包括数组访问、加和赋值： E → E[E] | E + E | E = E | (E) | id

该文法是二义的。请写一个接受同样语言的LR(1)文法，其优先级从高到低依次是数组访问、加和赋值，并且加运算是左结合，赋值是右结合。

2． E → T = E | T T → T + F | F F → F[E] | (E) | id

3．下面是产生字母表∑ = { 0, 1, 2}上数字串的一个文法： S → D S D | 2 D → 0 | 1

写一个语法制导定义，它打印一个句子是否为回文数（一个数字串，从左向右读和从右向左读都一样时，称它为回文数）。

3． S ' → S print(S.val) S → D1 S1 D2 S.val = (D1.val = D2.val) and S1.val S → 2 S.val = true D → 0 D.val = 0 D → 1 D.val = 1

b

《编译原理》模拟期末试题汇总 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分)

编译原理期末考试习题及答案

一、填空题|（每题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)

编译原理试题(卷)汇总-编译原理期末试题(卷)(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____。

最新编译原理试题汇总+编译原理期末试题(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．( ) 产生式

编译原理期末考试题目及答案

一、填空题（每空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 3．一个算符优先文法的每个非终结符号间都也可能存在优先关系。X 4．语法分析时必须先消除文法中的左递归。X 6．逆波兰表示法表示表达式时无须使用括号。R 9．两个正规集相等的必要条件是他们对应的正规式等价。 X 1．编译程序是对高级语言程序的编译执行。X

编译原理

一、选择 1．将编译程序分成若干个“遍”是为了_使程序的结构更加清晰__。 2．正规式 MI 和 M2 等价是指__.M1 和 M2 所识别的语言集相等_。 3．中间代码生成时所依据的是 _语义规则_。 4．后缀式 ab+cd+/可用表达式__(a+b)/(c+d)_来表示。 6．一个编译程序中，不仅包含词法分析，_语法分析 ____，中间代码生成，代码优化，目标代码生成等五个部分。 7．词法分析器用于识别__单词___。 8．语法分析器则可以发现源程序中的___语法错误__。 9．下面关于解释程序的描述正确的是__解释程序的特点是处理程序时不产生目标代码 ___。 10．解释程序处理语言时 , 大多数采用的是__先将源程序转化为中间代码 , 再解释执行___方法。 11．编译过程中 , 语法分析器的任务就是__(2)(3)(4)___。 (1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的 (3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构 12．编译程序是一种__解释程序__。 13．文法 G 所描述的语言是_由文法的开始符号推出的所有终极符串___的集合。 14．文法分为四种类型，即 0 型、1 型、2 型、3 型。其中 3 型文法是___正则文法__。 15．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 _产生式__。 16．通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括_表格处理和出错处理__。 17．文法 G[N]= （ {b} ， {N ， B} ， N ， {N→b│ bB ， B→bN} ），该文法所描述的语言是L(G[N])={b2i+1│ i ≥0} 18．一个句型中的最左_简单短语___称为该句型的句柄。 19．设 G 是一个给定的文法，S 是文法的开始符号，如果 S->x( 其中 x∈V*), 则称 x 是 文法 G 的一个__句型__。 21．若一个文法是递归的，则它所产生的语言的句子_是无穷多个___。 22．词法分析器用于识别_单词_。 23．在语法分析处理中， FIRST 集合、 FOLLOW 集合、 SELECT 集合均是_终极符集 ___。 24．在自底向上的语法分析方法中，分析的关键是_寻找句柄 ___。 25．在 LR 分析法中，分析栈中存放的状态是识别规范句型__活前缀__的 DFA 状态。 26．文法 G 产生的__句子___的全体是该文法描述的语言。 27．若文法 G 定义的语言是无限集，则文法必然是 __递归的_ 28．四种形式语言文法中，1 型文法又称为 _短语结构文法__文法。 29．一个文法所描述的语言是_唯一的__。 30． _中间代码生成___和代码优化部分不是每个编译程序都必需的。 31．_解释程序和编译程序___是两类程序语言处理程序。 32．数组的内情向量中肯定不含有数组的_维数___的信息。 33. 一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组__D___。 34．文法分为四种类型，即 0 型、1 型、2 型、3 型。其中 2 型文法是__上下文无关文法__。 35．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 __产生式___。 36．__ BASIC ___是一种典型的解释型语言。 37．与编译系统相比，解释系统___比较简单 , 可移植性好 , 执行速度慢__。 38．用高级语言编写的程序经编译后产生的程序叫__目标程序___。 39．编写一个计算机高级语言的源程序后 , 到正式上机运行之前，一般要经过__(1)(2)(3)__这几步: (1) 编辑 (2) 编译 (3) 连接 (4) 运行 40．把汇编语言程序翻译成机器可执行的目标程序的工作是由__编译器__完成的。 41．词法分析器的输出结果是__单词的种别编码和自身值__。 42．文法 G ：S→xSx|y 所识别的语言是_ xnyxn(n≥0)___。 43．如果文法 G 是无二义的，则它的任何句子α__最左推导和最右推导对应的语法树必定相同_。 44．构造编译程序应掌握___源程序目标语言编译方法___。 45．四元式之间的联系是通过__临时变量___实现的。 46．表达式( ┐ A ∨B)∧(C∨D)的逆波兰表示为___ A ┐ B∨CD∨∧__。 47. 优化可生成__运行时间短且占用存储空间小___的目标代码。 48．下列__删除多余运算 ____优化方法不是针对循环优化进行的。 49．编译程序使用__说明标识符的过程或函数的静态层次___区别标识符的作用域。 50．编译程序绝大多数时间花在___表格管理__ 上。 51．编译程序是对__高级语言的翻译___。

编译原理试题及答案3

编译原理复习题 一、填空题： 1、编译方式与解释方式的根本区别在于（是否生成目标代码）。 2、对编译程序而言，输入数据是（源程序），输出结果是（目标程序）。 3、如果编译程序生成的目标程序是机器代码程序，则源程序的执行分为两大阶段：（编译阶段）和（运行阶段）。 4、如果编译程序生成的目标程序是汇编语言程序，则源程序的执行分成三个阶段：（编译阶段）、（汇编阶段）和（运行阶段）。 5、自顶向下语法分析方法会遇到的主要问题有（回溯）和（（左递归带来的）无限循环）。 6、LL(k)分析法中，第一个L的含义是（从左到右进行分析），第二个L的含义是（每次进行最左推导），“k”的含义是（向输入串中查看K个输入符号）。 7、LL(1)分析法中，第一个L的含义是（从左到右进行分析），第二个L的含义是（每次进行最左推导），“1”的含义是（向输入串中查看1个输入符号）。 8、自顶向下语法分析方法的基本思想是：从（识别符号）出发，不断建立（直接推导），试图构造一个推导序列，最终由它推导出与输入符号相同的（符号串）。 9、自底向上语法分析方法的基本思想是：从待输入的符号串开始，利用文法的规则步步向上进行（直接归约），试图（归约）到文法的（识别符号|开始符号）。 10、LR(0)分析法的名字中，“L”的含义是（从左到右进行分析），“R”的含义是（采用最右推导的逆过程---最左归约），“0”的含义是（向貌似句柄的符号串后查看0个输入符号）。 11、LR(1)分析法的名字中，“L”的含义是（从左到右进行分析），“R”的含义是（采用最右推导的逆过程---最左归约），“1”的含义是（向貌似句柄的符号串后查看1个输入符号）。 12、SLR(1)分析法的名字中，“S”的含义是（简单的），“L”的含义是（从左到右进行分析），“R”的含义是（采用最右推导的逆过程---最左归约），“1”的含义是（向貌似句柄的符号串后查看1个输入符号）。 13、在编译过程中，常见的中间语言形式有（逆波兰表示）、（三元式）、（四元式）和（树形表示）。 14、在编译程序中安排中间代码生成的目的是（便于代码优化）和（便于目标程序的移植）。 15、表达式-a+b*(-c+d)的逆波兰表示为（a-bc-d+*+ ）。 16、表达式a+b*(c+d/e)的逆波兰表示为（abcde/+*+ ）。 17、表达式a:=a+b*c↑(d/e)/f的逆波兰表示为（aabcde/↑*f/+:= ）。 18、文法符号的属性有（继承属性）和（综合属性）两种。 19、一个文法符号的继承属性是通过语法树中它的（兄弟结点与父）结点的相应文法符号的属性来计算的。 20、一个文法符号的综合属性是通过语法树中它的（子）结点的属性来计算的。

郑州大学编译原理试卷及答案(往年试题整合)(2)

二填空题 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) 栈式动态存储分配(2) 堆式动态存储分配 (3) 左(4) 语法分析(5) 目标代码生成 (6) 表格管理 (7) xyz*ab+/+ (8) 继承属性 (9) a+(i-1)*20+j-1 (10) 基本块 8 词法规则通常可以用____正规式________，正规文法、____自动机________描述；语法规则通常用___2型文法___来描述；语义规则通常用__属性文法_____来描述。

9 编译原理的工作过程一般划分为：词法分析、语法分析、语义分析、优化和目标代码生成五个阶段。 1.( )称为规范推导。 2.编译过程可分为（），（），（），（）和（）五个阶段。 3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（）。 4.从功能上说，程序语言的语句大体可分为（）语句和（）语句两大类。 5.语法分析器的输入是（），其输出是（）。 6.扫描器的任务是从（）中识别出一个个（）。 7.符号表中的信息栏中登记了每个名字的有关的性质，如（）等等。 8.一个过程相应的DISPLAY表的内容为（）。 9.一个句型的最左直接短语称为句型的（）。 10.常用的两种动态存贮分配办法是（）动态分配和（）动态分配。 11.一个名字的属性包括( )和( )。 12.常用的参数传递方式有（），（）和（）。 13.根据优化所涉及的程序范围，可将优化分成为（），（）

编译原理试题汇总

一、选择题（每个选择题 2 分，共 20 分） 1 ．文法 G 产生的⑴ 的全体是该文法描述的语言。 A ．句型 B. 终结符集 C. 非终结符集 D. 句子 2 ．若文法 G 定义的语言是无限集，则文法必然是⑵ ： A ．递归的 B 前后文无关的 C 二义性的 D 无二义性的 3 ． Chomsky 定义的四种形式语言文法中， 0 型文法又称为⑶ 文法； 1 型文法又称为⑷ 文法； 2 型语言可由⑸ 识别。 A ．短语结构文法 B 前后文无关文法 C 前后文有关文法 D 正规文法 E 图灵机 F 有限自动机 G 下推自动机 4 ．一个文法所描述的语言是⑹ ；描述一个语言的文法是⑺ 。 A ．唯一的 B 不唯一的 C 可能唯一，好可能不唯一 5 ．数组的内情向量中肯定不含有数组的⑻ 的信息 A．维数 B.类型 C.维上下界 D.各维的界差 6 ．在下述的编译方法中，自底向上的方法有⑼ ，自顶向下的分析方法有⑽ 。 ①简单优先分析②算符优先分析③递归下降分析④预测分析技术⑤LR（K）分析 ⑥ SLR（k）分析⑦ LL（k）分析⑧LALR（K）分析 A.③④⑦ B. ③④⑧ C.①②⑧ D.③④⑤⑥⑦ E.①②⑤⑥⑦ F. ①②⑤⑥⑧ 二、简答题（每小题 5 分，共 20 分） 1 ． LL （ 1 ）分析法对文法有哪些要求？ 2 ．常见的存储分配策略有几种？它们都适合于什么性质的语言？ 3 ．常见循环优化都有哪些项目？ 4 ．什么是活动记录？它主要由哪些内容构成？ 五、（ 12 分）已给文法 G[S] ：S → SaP | Sf | P P → qbP | q 将 G[S] 改造成 LL （ 1 ）文法，并给出 LL （ 1 ）分析表。 七、（ 8 分）将下面的条件语句表示成逆波兰式和四元式序列： if a>b then x:=a+b*c else x:=b-a; 八、（ 8 分）给定基本块： A:=3*5 B:=E+F C:=A+12 D:=E+F A:=D+12 C:=C+1 E:=E+F 假定出基本块后，只有 A 、 C 、 E 是活跃的，给出用 DAG 图完成优化后的代码序列。参考答案： 一、⑴ D ⑵ A ⑶ A ⑷ C ⑸ G. ⑹ A ⑺ B ⑻ A ⑼ F ⑽ A 二、 1 ．对于 G 中的每个产生式A →γ 1 | γ 2 | … | γ m ，其各候选式均应满足：（1）不同的候选式不能推出以同一终结符号打头的符号串，即 FIRST( γ i ) ∩ FIRST( γ j )= φ（1 ≤ i ，j ≤ m ；i ≠ j ）

编译原理试题及答案

参考答案 一、单项选择题(共10小题，每小题2分，共20分) 1．语言是 A ．句子的集合 B ．产生式的集合 C ．符号串的集合 D ．句型的集合 2．编译程序前三个阶段完成的工作是 A ．词法分析、语法分析和代码优化 B ．代码生成、代码优化和词法分析 C ．词法分析、语法分析、语义分析和中间代码生成 D ．词法分析、语法分析和代码优化 3．一个句型中称为句柄的是该句型的最左 A ．非终结符号 B ．短语 C ．句子 D ．直接短语 4．下推自动机识别的语言是 A ．0型语言 B ．1型语言 C ．2型语言 D ．3型语言 5．扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即 A ． 字符 B ．单词 C ．句子 D ．句型 6．对应Chomsky 四种文法的四种语言之间的关系是 A ．L 0?L 1?L 2?L 3 B ．L 3?L 2?L 1?L 0 C ．L 3=L 2?L 1?L 0 D ．L 0?L 1?L 2=L 3 7．词法分析的任务是 A ．识别单词 B ．分析句子的含义 C ．识别句子 D ．生成目标代码 8．常用的中间代码形式不含 A ．三元式 B ．四元式 C ．逆波兰式 D ．语法树 9． 代码优化的目的是 A ．节省时间 B ．节省空间 C ．节省时间和空间 D ．把编译程序进行等价交换 10．代码生成阶段的主要任务是 A ．把高级语言翻译成汇编语言 B ．把高级语言翻译成机器语言 C ．把中间代码变换成依赖具体机器的目标代码 装 订 线

D．把汇编语言翻译成机器语言 二、填空题（本大题共5小题，每小题2分，共10分） 1．编译程序首先要识别出源程序中每个(单词)，然后再分析每个(句子)并翻译其意义。2．编译器常用的语法分析方法有(自底向上)和(自顶向下)两种。 3．通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的(分析)，中间代码生成、代码优化与目标代码的生成则是对源程序的(综合)。 4．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即(静态存储分配)方案和(动态存储分配)方案。 5．对编译程序而言，输入数据是(源程序)，输出结果是(目标程序)。 三、名词解释题(共5小题，每小题4分，共20分) 1．词法分析 词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则 从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位， 并转换成统一的内部表示(token)，送给语法分析程序。 2．LL(1)文法 若文法的任何两个产生式A →α | β都满足下面两个条件： （1）FIRST(α) ? FIRST(β ) = φ； （2）若β?* ε，那么FIRST(α) ? FOLLOW( A ) = φ。 我们把满足这两个条件的文法叫做LL(1)文法，其中的第一个L代表从左 向右扫描输入，第二个L表示产生最左推导，1代表在决定分析器的每步 动作时向前看一个输入符号。除了没有公共左因子外，LL(1)文法还有一 些明显的性质，它不是二义的，也不含左递归。 3．语法树 句子的树结构表示法称为语法树(语法分析树或语法推导树)。 给定文法G=(V N，V T，P，S)，对于G的任何句型都能构造与之关联的 语法树。这棵树具有下列特征： (1)根节点的标记是开始符号S。 (2)每个节点的标记都是V中的一个符号。 (3)若一棵子树的根节点为A，且其所有直接子孙的标记从左向右的排列 次序为A1A2…A R，那么A→A1A2…A R一定是P中的一条产生式。

基于编译原理的计算器设计与实现

基于编译原理的计算器设计与实现 首先看一下这个计算器的功能： CALC> set a = 1; b = 2 CALC> set c = 3 CALC> calc (10 + pow(b, c)) * sqrt(4) - 1 35.0 CALC> exit 如上所示，这个计算器的功能非常简单： 1.用set命令设置上下文中的变量。 2.用calc命令计算一个表达式的值。 3.用exit命令退出计算器。 我们把编译的重点放在calc命令后面的计算表达式的解析，其它的部分我们可以简单处理（如set命令可以这样简单处理：先按分号分隔得到多个赋值处理，再按等号分隔就可以在上下文中设置变量了，并不需要复杂的编译过程）。 如上的演示例子中，我们使用编译技术处理的部分是(10 + pow(b, c)) * sqrt(4) - 1，其它部分我们只使用简单的文本处理。 麻雀虽小，但五脏俱全，这个计算器包含编译技术中最必要的部分。虽然这次我们只是实现了一个计算器，但所使用的技术足以实现一个简单的脚本语言的解释器了。 这个计算器分为如下几个部分： 词法分析：把表达式的文本，解析成词法元素列表(tokenList)。 语法分析：把tokenList解析成语法树(syntaxTree)。 语义分析：把语法树转成汇编语言的代码(asm) 汇编器：把汇编代码翻译为机器码（字节码）。 虚拟机：执行字节码。 一般的编译步聚中不包含“汇编器”和“虚拟机”，而这里之所以包含这两个部分是因为：通常编译器会直接由中间代码生成机器码，而不是生成汇编代码，而这里我之所以要生成汇编代码的原因是“调试的时候汇编的可读性很好”，如果直接生成目标代码，则会非常难用肉眼来阅读。 自己实现虚拟机的原因是：现有的机器（包括物理机和虚拟机以及模拟器）的指令虽然也很丰富，但似乎都没有直接计算“乘方”或“开方”的指令，自已实现虚拟机可以任意设计计算指令，这样可以降低整个程序的复杂度。 因汇编器与虚拟机并不是编译原理的部分，所以下文中并不会描述其实现细节，但因为计算器代码编译后的目标代码就是汇编代码，所以需要把汇编指令做一下说明（以下把这个汇编语言简称为ASM）。

编译原理试题集33493

第一章引论 一.单项选择题 1. 如果一个编译程序能产生不同于其宿主机的机器代码，则称它为：___________________ 。 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. Lex是语法分析自动生成器 d. 解释程序属于编译程序 7. 目标代码生成阶段所生成的目标代码的形式不可能是____。 a. 绝对指令代码 b. 可充定位的指令代码。 c. 汇编指令代码 d. 三地址代码 8. 语义错误是指源程序中不符合语义规则的错误，不包括：____ a. 非法字符错误 b. 类型不一致错误。 c. 作用域错误 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．构造编译程序应掌握______。 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．( ) 代码外提

编译原理考试试题

一、回答下列问题：(30分) 1．什么是S-属性文法？什么是L-属性文法？它们之间有什么关系？ 解答： S-属性文法是只含有综合属性的属性文法。（2分） L-属性文法要求对于每个产生式A X1X2…Xn，其每个语义规则中的每个属性或者是综合属性，或者是Xj的一个继承属性，且该属性仅依赖于： （1）产生式Xj的左边符号X1,X2…Xj-1的属性； （2）A的继承属性。（2分） S-属性文法是L-属性文法的特例。（2分） 2．什么是句柄？什么是素短语？ 一个句型的最左直接短语称为该句型的句柄。（3分）素短语是这样的一个短语，它至少包含一个终结符并且不包含更小的素短语。（3分） 3．划分程序的基本块时，确定基本块的入口语句的条件是什么？ 解答： （1）程序第一个语句，或 （2）能由条件转移语句或无条件转移语句转移到的语句，或 （3）紧跟在条件转移语句后面的语句。 4．(6分)运行时的DISPLAY表的内容是什么？它的作用是什么？ 答：DISPLAY表是嵌套层次显示表。每当进入一个过程后，在建立它的活动记录区的同时建立一张嵌套层次显示表diaplay.假定现在进入的过程层次为i，则它的diaplay表含有i+1个单元，自顶向下每个单元依次存放着现行层、直接外层、…、直至最外层(主程序，0层)等每层过程的最新活动记录的起始地址。通过DISPLAY 表可以访问其外层过程的变量。 5．(6分)对下列四元式序列生成目标代码： A:=B*C D:=E+F G:=A+D H:=G*2 其中，H是基本块出口的活跃变量，R0和R1是可用寄存器 答： LD R0，B MUL R0，C LD R1，E ADD R1，F ADD R0，R1 MUL R0，2 ST R0，H

编译原理试题及答案——加强版

编译原理试题及答案 <高级版> 一、对于文法 G[S] ： S → 1A | 0B | ε A → 0S | 1AA B → 1S | 0BB ⑴ (3 分 ) 请写出三个关于 G[S] 的句子； ⑵ (4 分 ) 符号串 11A0S 是否为 G [S] 的句型？试证明你的结论。 ⑶ (3 分 ) 试画出 001B 关于 G [S] 的语法树。 二、请构造一个文法，使其产生这样的表达式 E ：表达式中只含有双目运算符 + 、 * ，且 + 的优先级高于 * ， + 采用右结合， * 采用左结合，运算对象只有标识符 i ，可以用括号改变运算符优先级。要求给出该文法的形式化描述。 三、设有语言 L={ α | α∈ {0,1} + ，且α不以 0 开头，但以 00 结尾 } 。 ⑴试写出描述 L 的正规表达式； ⑵构造识别 L 的 DFA （要求给出详细过程，并画出构造过程中的 NDFA 、 DFA 的状态转换图，以及 DFA 的形式化描述 ) 。 四、给定文法 G[S] ： S → AB A → a B | bS | c B → AS | d ⑴ (6 分 ) 请给出每一个产生式右部的 First 集；

⑵ (3 分 ) 请给出每一个非终结符号的 Follow 集； ⑶ (8 分 ) 请构造该文法的 LL(1) 分析表； ⑷ (8 分 ) 什么是 LL(1) 文法？该文法是 LL(1) 文法吗？为什么？ 五、给定文法 G[S] ： S → SaA|a A → AbS|b ⑴请构造该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 。 ⑵请构造该文法的 LR(0) 分析表。 ⑶什么是 LR(0) 文法？该文法是 LR(0) 文法吗？为什么？ ⑷什么是 SLR(1) 文法？该文法是 SLR(1) 文法吗？为什么？ 六、给定下列语句： if a+b>c then x := a*(b-c) + (b*c-d)/e ⑴写出其等价的逆波兰表示； ⑵写出其等价的四元式序列。 七、已知下列 C 语言程序： int * f() { int a = 100; return &a; } main()

编译原理试题A及答案 2

编译原理试题A 一、单项选择题（每题1分，共20分） 1、哪个不是编译系统的组成部分（C ） 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→S1|S0|Sa|Sc|a|b|c，下列符号串中不是该文法的句子的是 （A ） A．ab0 B. a0c01 C．aaa D. bc10 5. 文法G[S]: S→aA A→bB B→a|aS ,则L(G)为（C ）A．{(ab)n a|n≥1} B. {a (ba)n|n≥1} C．{(aba)n|n≥1} D. {(aba)n|n≥0} 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.23 10．自上而下语法分析的主要动作是（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．便于编译程序的移植