期中考试习题集锦.docVIP

《编译原理》12-13学期期中考试试题集锦 学号： 姓名： 1（选择填空）：高级语言的语言处理程序分为解释和编译2种。编译程序分5个阶段，而解释程序通常缺少（1）和（2）。其中（1）的目的是使最后阶段产生的目标代码更高效。与编译相比，解释（3）。解释方法处理语言时，大多数采用（4）。（5）和（6）是典型的解释型语言。 可选项：（1）（2）A、中间代码生成 B、目标代码生成 C、词法分析 D、语法分析 E、代码优化 （3）A、比较简单，可移植性好，执行速度快 B、比较复杂，可移植性好，执行速度快 C、比较简单，可移植性差，执行速度慢 D、比较简单，可移植性好，执行速度慢 （4）A、源程序命令被逐个直接解释执行 B、先将源程序转化成中间代码，再解释执行 C、先将源程序解释转化为目标代码，再执行 D、以上方法都可以 （5）（6）A、C B、JAVA C、MATLAB D、C++ 2（填空）：设符号串x为ａｃ，符号串y为＊＆＆＠。 x0为（ ），y2为（ ） xyx为（ ） x3y中，长度为3的前缀为（ ），长度为4的后缀为（ ），acac＊＆＆＠（ ）x3y的子串（填“是”或“不是”）。 设集合A={ε,a,ab}，B={c,d}，则AB={ }，B0={ }，AB2={ } 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，该文法描述的语言是（ ） A、L(G[s])={bi|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} 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 A→aA|a B→bB|b B、Z→ABb A→aA|a B→aBb|b C、Z→Ab A→aAb|a D、Z→aAb 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 D→Cbc|abc 16（简答）：已知文法G[S]： S→Da D→Ab A→a|Aa （1）画出该文法的状态图； （2）写出该文法描述的语言； （3）写出相应的正则文法的V，Vn和Vt； （4）检查句子aaaba是否合法。 17