《编译原理》12-13学期期中考试试题集锦
学号： 姓名： 1（选择填空）：高级语言的语言处理程序分为解释和编译2种。编译程序分5个阶段，而解释程序通常缺少（1）和（2）。其中（1）的目的是使最后阶段产生的目标代码更高效。与编译相比，解释（3）。解释方法处理语言时，大多数采用（4）。（5）和（6）是典型的解释型语言。
可选项：（1）（2）A、中间代码生成 B、目标代码生成 C、词法分析 D、语法分析 E、
代码优化
（3）A、比较简单，可移植性好，执行速度快
C、比较简单，可移植性差，执行速度慢 （4）A、源程序命令被逐个直接解释执行
B、先将源程序转化成中间代码，再解释执行 C、先将源程序解释转化为目标代码，再执行
C、MATLAB
D、C++
B、比较复杂，可移植性好，执行速度快 D、比较简单，可移植性好，执行速度慢
D、以上方法都可以 （5）（6）A、C B、JAVA
2（填空）：设符号串x为ａｃ，符号串y为＊＆＆＠。 （１） x0为（ ），y2为（ ） （２） xyx为（ ）
（３） xy中，长度为3的前缀为（ ），长度为4的后缀为（
acac＊＆＆＠（ ）x3y的子串（填“是”或“不是”）。
0
2
3
），
设集合A={ε,a,ab}，B={c,d}，则AB={ }，B={ }，AB={
3（多选）：设有文法G[I]：I→I1|I0|Ia|Ic|a|b|c下列符号串中是该文法的句子有（ A、ab0 B、a0c01 C、aaa D、bc10 4（简答）：设有文法G[S]：S→a|ε|(T) T→T,S|S
}
）。
请给出句子(a,(a,a))的最左、最右推导并指出其最右推导的逆过程（即最左规约）每一步的
句柄。
5（单选）：设有文法G[S]：S→b|bB B→bS，该文法描述的语言是（
i2
A、L(G[s])={b|i>=0} B、L(G[s])={bi|i>=0} C、L(G[s])={b2i+1|i>=0} D、L(G[s])={b2i+1|i>=1}
）
6（简答）：已知文法G[P]：P→PaP|PbP|cP|Pe|f 判断该文法是否是二义性的文法，并说明理由。提示：考虑句子fbfbf
7（简答）：请根据文法的实用限制，对文法G [S]进行变换。 G [S]：S→Bab|cC B→b|bS C→Da D→Cb|CDa 8（简答）：已知状态图如右图，S为开始状态，Z为终态。 （1）写出相应的正则文法；
（2）写出该正则文法的V，Vn和Vt； （3）写出该文法描述的语言； （4）检查句子fffn是否合法。
9（简答）：设字母表∑={a,b}，现有∑上的正则表达式R=(a|b)*(aa|bb)(a|b)*， （1）构造NFA M’，使得L（M’）=L(R)
（2）将NFA M’确定化、最小化得到NFA M，使得L(M)=L(M’) 10（简答）：设有文法G[Z]：Z→aAcB|Bd A→AaB|c B→bBcA|b 1、请写出该文法中每一个非终结符的FIRST集合和Follow集合。
2、这个文法能不能使用递归下降的语法分析方法？为什么？
3、请对这个文法进行改写，使得使用递归下降方法进行分析时，没有回溯。 4、请对改写后文法，为每个非终结符设计递归下降子程序。 11（多选）：设有文法G[T]：T→T*F|F F→F↑P|P P→(T)|a 该文法句型T*P↑(T*F)的直接短语是下列符号串（ ）。 A、(T*F) B、T*F C、P D、P↑(T*F) 12（简答）：现有文法G[E]：E→E+T|E-T|T T→T*F|T/F|F
F→(E)|i
其中E是文法的开始符号。求句型（F+i)-T*(E-T)的短语、直接短语和句柄。 13（单选）：描述语言L={ambn|n>=m>=1}的文法为（ ） A、Z→ABb C、Z→Ab
A→aA|a A→aAb|a
B→bB|b
B、Z→ABb D、Z→aAb
A→aA|a
B→aBb|b
A→Ab|aAb|ε
14（简答）：已知文法G[P]：P→PaP|PbP|cP|Pe|f 判断该文法是否是二义性的文法，并说明理由。提示：考虑句子fbfbf 15（简答）：请根据文法的实用限制，对文法G [S]进行变换。 G [S]：S→aSab|bAB A→bB|b B→aA|b C→abB|baA 16（简答）：已知文法G[S]： S→Da D→Ab A→a|Aa
D→Cbc|abc
（1）画出该文法的状态图； （2）写出该文法描述的语言； （3）写出相应的正则文法的V，Vn和Vt； （4）检查句子aaaba是否合法。 17（简答）：设字母表∑={a,b}，现有∑上的正则表达式R=(a*|b*)b(ba)*， （1）构造NFA M’，使得L（M’）=L(R)
（2）将NFA M’确定化、最小化得到NFA M，使得L(M)=L(M’)
18（简答）：设有文法G[S]：S→aBc|bAB A→aAb|b B→b|ε 1、请写出该文法中每一个非终结符的FIRST集合和Follow集合。
2、为每个非终结符设计递归下降子程序 3、如果不是LL（1）文法，请对之进行改写。设计LL（1）分析表。对符号串baabbb进行分析，并写出推导使用的产生式序列 18（多选）：给定文法G[A]：A→bA|cc 下面的符号串中，为该文法的句子有（ A、cc B、bcbc C、bcbcc D、bccbcc E、bbbcc 20（简答）：给定文法G[S]：S→aAcBe A→Ab|b B→d
若有句型aAbcdc，试问b是它的直接短语吗？它的短语是什么？句柄是什么？ 21（单选）：已知语言L={anbbn|n>=1}，则下述文法中（ ）可以产生语言L。 A、Z→aZb|aAb|b A→aAb|b C、Z→AbB A→aA|a B→bB|b
B、A→aAb
D、Z→aAb
A→b A→aAb|b
）。
22（简答）：试判断文法G[S]：S→ibtSeS|ibtS|a是否为二义性的文法，并说明理由。提示：
考虑句子ibtibtaea
23（简答）：请根据文法的实用限制，对文法G [S]进行变换。 G [S]：S→aBs S→b S→cS B→ε 24（简答）：设字母表∑={a,b}，现有∑上的正则表达式R=(a|ba)*， （1）构造NFA M’，使得L（M’）=L(R)
（2）将NFA M’确定化、最小化得到NFA M，使得L(M)=L(M’)
25（简答）：设有文法G[S]：S→aAbDe|d A→BSD|e B→SAc|cD|ε D→Se|ε 1、请写出该文法中每一个非终结符的FIRST集合和Follow集合。 2、这个文法是LL（1）文法吗？为什么？
3、如果不是，请对这个文法进行改写，并为之设计LL（1）的分析表 4、对符号串adbe进行分析，并写出推导使用的产生式序列