软考中级
假设某程序语言的文法如下：S→a|b|(T)T→TdS|S其中：Vt＝(a，b，d，(，)}，Vn＝{S，T}，S是开始符号。考察该文法，称句型(Sd(T)db)是S的一个(48)。其中(49)是句柄：(50)是素短语；(51)是该句型的直接短语；(52)是短语。A．最左推导B．最右推导C．规范推导D．推导
题目
假设某程序语言的文法如下：
S→a|b|(T)
T→TdS|S
其中：Vt＝(a，b，d，(，)}，Vn＝{S，T}，S是开始符号。
考察该文法，称句型(Sd(T)db)是S的一个(48)。其中(49)是句柄：(50)是素短语；(51)是该句型的直接短语；(52)是短语。
A．最左推导
B．最右推导
C．规范推导
D．推导
参考答案和解析
相似问题和答案
第1题：
设语言L={w|w∈{a,b}+且w中a和b的个数相等}，产生语言L的上下文无关文法是(28)。
A．Ga=(VT={a,b}，VN={S，A，B}，S,P)，其中P为， S→a|aA|bSS A→aB|bS B→b|bA|aBB
B．Gb=(VT={a,b}，VN={S,A,B}，S,P)，其中P为， S→b|bB|aSS B→aS|bA A→a|aB|bAA
C．Gc=(VT={a,b}，VN{S,A,B}，S,P)，其中P为， S→aB|bA A→a|aS|bAA B→b|bS|aBB
D．Gd=(VT={a,b}，VN={S，A，B}，S,P)，其中P为， S→aB|bA|s A→aS|bAA B→bS|aBB
解析：字母表{a,b}上的任何非空串，从其所含a和b的个数来划分，分成下面3个集合：①a和b的个数相等：②a比b的个数多，但仅要a比b的个数多1个的那些子串；③b比a的个数多，但仅要b比a的个数多1个的那些子串。通过上面的分析，根据用文法规则产生句子的原理，设3个非终结符号，不妨称做S、A、B，它们的产生式分别完成：①用S的产生式推导出a和b的个数相等的串；②用A的产生式推导出a比b的个数多1个的串；③用B的产生式推导出b比a的个数多1个的串。根据3个非终结符号S、A、B的含义，显然，关于S的产生式应该是S→aB|bA。对于A产生的串，若第1个字符是a，则剩下的是a和b的个数相等的串：若第1个字符是b，则跟随b的是a比b的个数多2个的串，这个串是两个a比b的个数多1个的子串。根据上述分析，写出关于A的产生式A→a|aS|bAA。可以通过和A类似的分析，写出关于B的产生式B→b|bS|aBB。可以用归纳法证明上面所写的文法是正确的。现在，我们很清楚被选答案中的4个文法所描述的语言，它们分别是：L(Ga)={w|w∈{a,b}+且w中a比b的个数多一个}L(Gb)={w|w∈{a,b}+且w中b比a的个数多一个}L(Gc)={w|w∈{a,b}+且w中a和b的个数相等}L(Gd)={w|w∈{a,b}+且w中a和b的个数相等}
第2题：
假设某程序语言的文法如下：
S→SaT｜T
T→TbR｜R
T→PdR｜P P→fSg｜e
其中：VT={a，b，d，e，f，g}，VN{S，T，R，P}，S是开始符号。那么，此方法是(38 方法。这种文法的语法分析通常采用优先矩阵，优先矩阵给出了该文法中各个终结符之间的优先关系 (大于，小于，等于，无关系)。在上述文法中，某些终结符之间的优先关系如下：
b(39)a：f(40)g；a(41)a；d(42)d。
A．正规文法
B．算符文法
C．二义文法
D．属性文法
第3题：
假设某程序语言的文法如下：
S→a|b|(T)
T→TdS|S
其中，VT={a，b，d，(，))；VN={S，T}，S是开始符号。考察该文法，句型(Sd(T)db)是S的一个(28)。
其中(29)是最左素短语，(30)是该句型的直接短语。
(74)
A．最左推导
B．最右摊导
C．规范推导
D．推导
第4题：
考察下列文法：G(VT，VN，E，P)
其中：VT＝{+，*，(，)，i}
VN＝{E，T，F}
E是开始符号；
P：
E→E+T|T
T→T*F|F
F→(E)|i
F*F+T是该文法的一个句型，其中(53)是句柄，(54)是素短语。(55)是该句型的直接推导，(56)是该句型的最左推导。(57)是该文法的一个句子。
A．F
B．F*F
C．F+T
D．F*F+T
第5题：
已知文法G2=(VT={a，'，'，(,)}，VN={S，L)，S,P)，其中P为 S→(L)|a L→-L，s|s 与G2等价的不含左递归规则的文法是(29)。
A．G21=(VT={a，'，'，(,)}，VN={S，L}，S，P)，其中P为 S→(L)|a L→S，S|S
B．G22=(VT＜a，'，'，(,)}，VN={S，L，L'}，S，P)，其中P为 S→(L)|a L→SL' L'→SL'|ε
C．G23=(VT{a，'，'，(,)}，VN={S，L，L'}，S，P)，其中P为 S→(L)|a L→SL' U→,SL'|ε
D．G24=(VT=(a，'，'，(,)}，VN=＜S，L，L'}，S，P)，其中P为 S→(L)|a L→SL' L→SL'|S
解析：采用自顶向下的预测分析法首先是等价改写给定的文法，消除文法的左递归和提取产生式的公共左因子。消除直接左递归的方法如下：若A→Aα|β，其中α，β∈(VT∪VN)*，β不以A开始，则关于A的这种形式的产生式可改写成A→βA'A'→αA'|ε一般而言，假设A的产生式为A→Aα1|Aα2|…|Aαn|β1|β2|…|βm其中αI(i=1，2，…，n)不等于ε，βj(j=1，2，…，m)不以A开始，那么上述产生式可改成A→β1A'|β2A'|…|βmA'A'→α1A'|α2A'|…|αnA'|ε消除文法G2中规则的左递归后，其规则变成S→(L)|aL→SL'L'→，SL'|ε
第6题：
假设某程序语言的文法如下：
S→a｜b｜(T)
T→TdS｜S
其中：VT={a，b，d，(，)}，VN{S，T}，S是开始符号。
考查该文法，称句型(Sd(T)db)是S的一个(33)，其中，(34)是句柄：(35)是素短语；(36)是该句型的直接短语；(37)是短语。
A．最左推导
B．最右推导
C．规范推导
D．推导
第7题：
假设某程序语言的文法如下：
S→SaT|T
T→TbR|R
R→PdR|P
P→fSg|e
其中Vr＝{a，b，d，e，f，g}；Vn＝{S，T，R，P}；S是开始符号，那么，此文法是(43)文法。这种文法的语法分析通常采用优先矩阵。优先矩阵给出了该文法中各个终结符之间的优先关系(大于、小于、等于和无关系)。在上述文法中，某些终结符之间的优先关系如下：b{(44)}a；f{(45)}g；a{(46)}a；d{(47)}d。
A．五则文法
B．算符文法
C．二义文法
D．属性文法
第8题：
AS
BB
C(T)
DSD(T)
第9题：
● 对给定文法G=（VN，VT， P，S），VT={a，Λ，(，)}，VN={S，T}，S是开始符号，
P:
S→a|Λ|(T)
T→T,S|S
则（1）不是它的句子。该文法是（2）型文法。
（1）A. (a,(a,a)) B. (((a,a), Λ,(a)),a) C. ((a,a), Λ) D. ((a,a),(T))
（2）A．0型文法 B．1型文法 C．2型文法 D．正规文法
根据句子的定义，若从文法G的开始符号S能推导出的符号串成为文法的一个句型，仅含终结符的句型成为一个句子。很显然，备选答案D中含有非非终结符T，所以它不是文法的句子。
该文法是递归可枚举的，所以文法是0型文法，又文法所有产生式的右边长度大于或等于产生式左边长度，所以文法是1型文法，由于该文法的每个产生式的左边均是非终结符，所以该文法是2型文法；由于文法的两个产生式即不是右线性，也不是左线性，所以该文法不是正规型文法。