编译原来期末复习题

1、1.判断下面文法是否为LL(1)文法，若是,请构造相应的LL(1)分析表。S aH H aMd | d M Ab | A aM | e解：首先计算文法的 FIRST集和FOLLOW集如下表。文法的 FIRST集和FOLLOW集 非终结符FIRST集FOLLOW集Sa.# .Ha ，d.# .Ma ，e ，d ，bAa ，e.b.由于first（HaMd）first（Hd）=ad = first（MAb）first（M）=a ，ed ，b = first（AaM）first（Ae）= a e = 所以该文法是LL(1)文法，LL(1)分析表如下表。 LL(1)分析表adbe#SaH.HaMdd.

2、MAb.AbAaM.e.2.给出与正规式R（ab）*（a|b*）ba等价的NFA。解：与正规式R（ab）*（a|b*）ba 等价的NFA如下图3进行确定的自上而下语法分析要求语言的文法是无左递归和公共左因子的。4常用的优化技术包括：删除公共子表达式 、 代码外提、强度削弱、复写传播、归纳变量删除 等。5局部优化是在_ 基本块_范围内进行的一种优化。6.源程序中使用的标识符及其属性放在 符号表 中。7.一个上下文无关文法所含四个组成是 开始符号 、 产生式集合 、 终结符号集合 、 非终结符号集合 。8对于文法G，仅含终结符号的句型称为 句子 。9、后缀式abc-/所代表的表达式是_a/(b-c

3、)_ _。10.编译程序是指将 源语言 程序翻译成 目标语言 程序的程序。11词法分析器的输出结果是_C_。A 单词的种别编码 B 单词在符号表中的位置C单词的种别编码和自身值 D单词自身值12正规式 M 1 和 M 2 等价是指_C_。A M1和M2的状态数相等 B M1和M2的有向边条数相等C M1和M2所识别的语言集相等 D M1和M2状态数和有向边条数相等13文法G：SxSx|y所识别的语言是_C_。A xyx B (xyx)* C xnyxn(n0) D x*yx*14如果文法G是无二义的，则它的任何句子_A_。A最左推导和最右推导对应的语法树必定相同 B 最左推导和最右推导对应的语

4、法树可能不同 C最左推导和最右推导必定相同 D可能存在两个不同的最左推导，但它们对应的语法树相同15表达式(AB)(CD)的逆波兰表示为_B_。A. ABCD B ABCDC ABCD D ABCD16、“运算符与运算对象类型不符”属于_B_。A.语法错误 B. 语义错误 C. 语用错误 D.规则错误17、一个语言的文法是_B_A惟一的 B不惟一的 C.个数有限的 D.以上都不对18、一个句型的最左直接短语称为该句型的_D_。 A.句型 B.短语 C.简单短语 D.句柄 19. 在LR(0)分析法中，若a,V*且a则称“A a.”为 B 项目，称“S a.a”为 项目。A归约 待归 B归约 移

5、进C接收 移进 D归约 接收20. 基本块 A 。A只有一个入口语句和一个出口语句 B有一个入口语句和多个出口语句C有多个入口语句和一个出口语句 D有多个入口语句和多个出口语句21编译程序是对高级语言程序的解释执行。( ) 22一个有限状态自动机中，有且仅有一个唯一的终态。( ) 23语法分析时必须先消除文法中的左递归 。 ( ) 24逆波兰表示法表示表达式时无须使用括号。 ( ) 25静态数组的存储空间可以在编译时确定。 ( ) 26进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。 ( ) 27.归约是从文法开始符号出发，推出最后的输入串。（ ）28.A*=AA+

6、。（ ）29如果一个文法是递归的，则其产生的语言的句子是无穷个。（ ）30仅考虑一个基本块，不能确定一个赋值是否真是无用的。（ ）31.请写出由下列文法所确定的语言。S10S01SaAAbAAa解：.(10)nabma(01)n32.设有文法GS：SaBc|bABAaAb|bBb|（1）、计算每个非终结符的FIRST集合和FOLLOW集合。（2）、构造文法的LL(1)分析表。解：(1) FIRST(S)=a,b FOLLOW(S)=# FIRST(A)=a,b FOLLOW(A)=b,#FIRST(B)=,b FOLLOW(B)=c(2)abc#SSaBcSbABAAaAbAbBBbB33.给

7、定下面的文法SAaAb|BbBa A B（1） 、求出每个非终结符的FIRST和FOLLOW集合。（2） 、判断该文法是否为LL（1）文法。（3） 、构造该文法的项目集规范族。（4） 、判断该文法是否为SLR(1)的。解：（1）FIRST(S)=a,b FOLLOW(S)=#FIRST(A)= FOLLOW(A)= a,b FIRST(B)= FOLLOW(B)= a,b (2).该文法不含左递归；.对于S的两个候选其中FIRST(AaAb)=a, FIRST(BbBa)= b,首符集无交集。所以该文法是LL(1)文法。（3）I0:SAaAbABI1: SAaAbI2: SAaAbABI3: SAaAbI4: SAaAb(4).在项目集规范族中I0中存在归约-归约冲突，又因为FOLLOW(A)=FOLLOWW(B)=a,b，当面临输入符号a或b时，不能选择用哪个产生式进行归约，即冲突不能解决，所以该文法不是SLR(1)的。34. 请对下面的流图进行