题2
一、单项选择题
1、文法G：S→xSxy所识别的语言是。
axyx
bxyxcx
yx
≥0dxyx
2、文法G描述的语言LG是指。
aLGαSαα∈VT
bLGαSαα∈VT
cLGαSαα∈VT∪VNdLGαSαα∈VT∪VN
3、有限状态自动机能识别。
a上下文无关文法
b上下文有关文法
c正规文法
d短语文法
4、设G为算符优先文法，G的任意终结符对a、b有以下关系成立。
a若fagb，则abb若fagb，则ab
cab都不一定成立
dab一定成立
5、如果文法G是无二义的，则它的任何句子α
。
a最左推导和最右推导对应的语法树必定相同
b最左推导和最右推导对应的语法树可能不同
c最左推导和最右推导必定相同
d可能存在两个不同的最左推导，但它们对应的语法树相同
6、由文法的开始符经0步或多步推导产生的文法符号序列是。
a短语
b句柄
c句型
d句子
7、文法G：E→ETT
T→TPP
P→EI则句型PTi的句柄和最左素短语为。
aPT和ibP和PTci和PTidP和T8、设文法为：S→SAA
A→ab则对句子aba，下面是规范推导。
aSSASAAAAAaAAabAaba
bSSASAAAAAAAaAbaabacSSASAASAaSbaAbaaba
dSSASaSAaSbaAbaaba
9、文法G：S→b∧T
T→TSS
则FIRSTVTT。
ab∧
bb∧
cb∧，
db∧，
10、产生正规语言的文法为。
a0型
b1型
c2型
d3型
11、采用自上而下分析，必须。
a消除左递归
b消除右递归
c消除回溯
d提取公共左因子
12、在规范归约中，用来刻画可归约串。
a直接短语
b句柄
13、有文法G：E→ETT
T→Tii
c最左素短语
d素短语
句子1286按该文法G归约，其值为。
a23B42c3014、规范归约指。a最左推导的逆过程
d17b最右推导的逆过程
c规范推导解答
1、选c。
d最左归约的逆过程
2、选a。
3、选c。4、虽然a与b没有优先关系，但构造优先函数后，a与b就一定存在优先关系了。所以，由fagb
3
f或fagb并不能判定原来的a与b之间是否存在优先关系：故选c。5、如果文法G无二义性，则最左推导是先生长右边的枝叶：对于d，如果有两个不同的是了左
推导，则必然有二义性。故选a。6、选c。7、由图281的语法树和优先关系可以看出应选b。
E
EF
ETP
T
i
P
i图281句型PTI的语法及优先关系
8、规范推导是最左推导，故选d。
9、由T→T…和T→…得FIRSTVTT，；
由T→S得FIRSTVTSFIRSTVTT，而FIRSTVTSb∧；即
FIRSTVTTb∧，；
因r