编译原来期末复习题

编译原来期末复习题编译原来期末复习题编译原来期末复习题编译原来期末复习题编制仅供参考审核批准生效日期地址：电话：传真:邮编:1.判断下面文法是否为LL(1)文法，若是,请构造相应的LL(1)分析表。

S→aH

H→aMd|d

M→Ab|ε

A→aM|e解：首先计算文法的FIRST集和FOLLOW集如下表。文法的FIRST集和FOLLOW集非终结符FIRST集FOLLOW集S{a}.........{#}...H{a，d}.....{#}...M{a，e，ε}{d，b}A{a，e}.....{b}....由于first（H→aMd）∩first（H→d）={a}∩{d}=

first（M→Ab）∩first（M→ε）={a，e}∩{d，b}=

first（A→aM）∩first（A→e）={a}∩{e}=所以该文法是LL(1)文法，LL(1)分析表如下表。LL(1)分析表

adbe#S→aH.

H→aMd→d.

M→Ab.→ε→ε→Ab

A→aM.

→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)____。10.编译程序是指将源语言程序翻译成目标语言程序的程序。11．词法分析器的输出结果是_C___。A．单词的种别编码B．单词在符号表中的位置

C．单词的种别编码和自身值D．单词自身值12．

正规式M1和M2等价是指___C__。

A．M1和M2的状态数相等

B．M1和M2的有向边条数相等C．M1和M2所识别的语言集相等D．M1和M2状态数和有向边条数相等13．

文法G：S→xSx|y所识别的语言是___C__。A．xyx

B．(xyx)*C．xnyxn(n≥0)

D．x*yx*14．如果文法G是无二义的，则它的任何句子___A__。A．最左推导和最右推导对应的语法树必定相同B．最左推导和最右推导对应的语法树可能不同C．最左推导和最右推导必定相同

D．可能存在两个不同的最左推导，但它们对应的语法树相同15．表达式(┐A∨B)∧(C∨D)的逆波兰表示为___B__。A.┐AB∨∧CD∨B．A┐B∨CD∨∧C．AB∨┐CD∨∧

D．A┐B∨∧CD∨16、“运算符与运算对象类型不符”属于____B__。A.语法错误B.语义错误C.语用错误D.规则错误17、一个语言的文法是__B___A．惟一的B．不惟一的C.个数有限的D.以上都不对18、一个句型的最左直接短语称为该句型的__D_____。A.句型B.短语C.简单短语D.句柄19.在LR(0)分析法中，若,βV*且a则称“A.”为B项目，称“S.aβ”为项目。A．归约待归 B．归约移进C．接收移进 D．归约接收20.基本块A。A．只有一个入口语句和一个出口语句B．有一个入口语句和多个出口语句C．有多个入口语句和一个出口语句D．有多个入口语句和多个出口语句21．编译程序是对高级语言程序的解释执行。(×)22．一个有限状态自动机中，有且仅有一个唯一的终态。(×)23．语法分析时必须先消除文法中的左递归。(×)24．逆波兰表示法表示表达式时无须使用括号。(√)25．静态数组的存储空间可以在编译时确定。(×)26．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。(×)27.归约是从文法开始符号出发，推出最后的输入串。（×）*=AA+。（×）29．如果一个文法是递归的，则其产生的语言的句子是无穷个。

（√）30．仅考虑一个基本块，不能确定一个赋值是否真是无用的。（√）31.请写出由下列文法所确定的语言。S→10S01S→aAA→bAA→a解：.(10)nabma(01)n32.设有文法G[S]：S→

aBc|bABA→

aAb|bB→

b|ε（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#SS→

aBcS→

bABAA→

aAbA→

bBB→

bB→ε33.给定下面的文法S→AaAb|BbBaA→εB→ε、求出每个非终结符的FIRST和FOLLOW集合。、判断该文法是否为LL（1）文法。、构造该文法的项目集规范族。、判断该文法是否为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:S→·AaAbA→·B→·I1:S→A·aAbI2:S→Aa·AbA→·B→·I3:S→AaA·bI4:S→AaAb·(4).在项目集规范族中I0中存在归约-归约冲突，又因为FOLLOW(A)=FOLLOWW(B)={a,b}，当面临输入符