第三章 语法分析
3.1 完成下列选择题：
(1) 文法G：S→xSx|y所识别的语言是 。 a. xyx b. (xyx)* c. xnyxn(n≥0) d. x*yx*
(2) 如果文法G是无二义的，则它的任何句子α 。 a. 最左推导和最右推导对应的语法树必定相同 b. 最左推导和最右推导对应的语法树可能不同 c. 最左推导和最右推导必定相同 d. 可能存在两个不同的最左推导，但它们对应的语法树相同 (3) 采用自上而下分析，必须 。 a. 消除左递 a. 必有ac归 b. 消除右递归 c. 消除回溯 d. 提取公共左因子 (4) 设a、b、c是文法的终结符，且满足优先关系ab和bc，则 。 b. 必有ca c. 必有ba d. a～c都不一定成立 (5) 在规范归约中，用 来刻画可归约串。 a. 直接短语 b. 句柄 c. 最左素短语 d. 素短语 (6) 若a为终结符，则A→α·aβ为 项目。 a. 归约 b. 移进 c. 接受 d. 待约 (7) 若项目集Ik含有A→α· ，则在状态k时，仅当面临的输入符号a∈FOLLOW(A)时，才采取“A→α· ”动作的一定是 。 a. LALR文法 b. LR(0)文法 c. LR(1)文法 d. SLR(1)文法 (8) 同心集合并有可能产生新的 冲突。 a. 归约 b. “移进”/“移进” c.“移进”/“归约” d. “归约”/“归约” 【解答】 (1) c (2) a (3) c (4) d (5) b (6) b (7) d (8) d 3.2 令文法G[N]为 G[N]: N→D|ND D→0|1|2|3|4|5|6|7|8|9 (1) G[N]的语言L(G[N])是什么? (2) 给出句子0127、34和568的最左推导和最右推导。 【解答】 (1) G[N]的语言L(G[N])是非负整数。 (2) 最左推导： NNDNDDNDDDDDDD0DDD01DD012D0127 NNDDD3D34
NNDNDDDDD5DD56D568 最右推导： NNDN7ND7N27ND27N127D1270127 NNDN4D434
NNDN8ND8N68D68568
3.3 已知文法G[S]为S→aSb|Sb|b，试证明文法G[S]为二义文法。
【解答】 由文法G[S]：S→aSb|Sb|b，对句子aabbbb可对应如图3-1所示的两棵语法树。 SS
aSbSb
aSbaSb SbaSb
bb
图3-1 句子aabbbb对应的两棵不同语法树
因此，文法G[S]为二义文法(对句子abbb也可画出两棵不同语法树)。 3.4 已知文法G[S]为S→SaS|ε，试证明文法G[S]为二义文法。 【解答】 由文法G[S]：S→SaS|ε，句子aa的语法树如图3-2所示。
SS
SaSSaS
SaS??SaS ???? (a)(b)图3-2 句子aa对应的两棵不同的语法树 由图3-2可知，文法G[S]为二义文法。 3.5 按指定类型，给出语言的文法。 (1) L={aibj|j＞i≥0}的上下文无关文法； (2) 字母表Σ={a,b}上的同时只有奇数个a和奇数个b的所有串的集合的正规文法； (3) 由相同个数a和b组成句子的无二义文法。 【解答】 (1) 由L={aibj|j＞i≥0}知，所求该语言对应的上下文无关文法首先应有S→aSb型产生式，以保证b的个数不少于a的个数；其次，还需有S→Sb或S→b型的产生式，用以保证b的个数多于a的个数。因此，所求上下文无关文法G[S]为 G[S]：S→aSb|Sb|b
(2) 为了构造字母表Σ={a,b}上同时只有奇数个a和奇数个b的所有串集合的正规式，我们画出如图3-3所示的DFA，即由开始符S出发，经过奇数个a到达状态A，或经过奇数个b到达状态B；而由状态A出发，经过奇数个b到达状态C(终态)；同样，由状态B出发经过奇数个a到达终态C。 由图3-3可直接得到正规文法G[S]如下： A G[S]：S→aA|bB
ba A→aS|bC|b
B→bS|aC|a ab C→bA|aB|ε SCab
ab图3-3 习题3.5的DFA B(3) 我们用一个非终结符A代表一个a(即有A→a)，用一个非终结符B代表一个b(即有B→b)；为了保证a和b的个数相同，则在出现一个a时应相应地出现一个B，出现一个b时则相应出现一个A。假定已推导出bA，如果下一步要推导出连续两个b时，则应有bAbbAA。也即为了保证b和A的个数一致，应有A→bAA；同理有B→aBB。此外，为了保证递归地推出所要求的ab串，应有S→aBS和S→bAS。由此得到无二义文法G[S]为 G[S]：S→aBS|bAS|ε
A→bAA|a B→aBB|b 3.6 有文法G[S]: S→aAcB|Bd A→AaB|c B→bScA|b (1) 试求句型aAaBcbbdcc和aAcbBdcc的句柄； (2) 写出句子acabcbbdcc的最左推导过程。 【解答】 (1) 分别画出对应句型aAaBcbbdcc和aAcbBdcc的语法树如图3-4的(a)、
S(b)所示。
SaAcB
aAcB AaBbScA bScABdc图3-4 习题3.6的语法树
Bdc b (a ) (b ) (a) aAaBcbbdcc; (b) aAcbBdcc 对树(a)，直接短语有3个：AaB、b和c，而AaB为最左直接短语(即为句柄)。对树(b)，直接短语有两个：Bd和c，而Bd为最左直接短语。 能否不画出语法树，而直接由定义(即在句型中)寻找满足某个产生式的候选式这样一个最左子串(即句柄)呢？例如，对句型aAaBcbbdcc，我们可以由左至右扫描找到第一个子串AaB，它恰好是满足A→AaB右部的子串；与树(a)对照，AaB的确是该句型的句柄。是否这一方法始终正确呢？我们继续检查句型aAcbBdcc，由左至右找到第一个子串c，这是满足A→C右部的子串，但由树(b)可知，c不是该句型的句柄。由此可知，画出对应句型的语法树然后寻找最左直接短语是确定句柄的好方法。 (2) 句子acabcbbdcc的最左推导如下： SaAcBaAaBcBacaBcBacabcBacabcbScAacabcbBdcA acabcbbdcAacabcbbdcc 3.7 对于文法G[S]: S→(L)|aS|a L→L,S|S (1) 画出句型(S,(a))的语法树； (2) 写出上述句型的所有短语、直接短语、句柄、素短语和最左素短语。 【解答】 (1) 句型(S, (a))的语法树如图3-5所示。
S
(L)
L,S
S(L)图3-5 句型(S,(a))的语法树
Sa(2) 由图3-5可知： 短语：S、a、(a)、S,(a)、(S,(a))； 直接短语：a、S； 句柄：S； 素短语：素短语可由图3-5中相邻终结符之间的优先关系求得，即： #? (?，? (?a?)?)?# 因此，素短语为a。
3.8 下述文法描述了C语言整数变量的声明语句： G[D]: D→TL T→int|long|short L→id|L,id (1) 改造上述文法，使其接受相同的输入序列，但文法是右递归的； (2) 分别用上述文法G[D]和改造后的文法G[D′]为输入序列int a,b,c构造分析树。 【解答】 (1) 消除左递归后，文法G[D′]如下： D→TL DT→int|long|short
DTLL→idL
TLintaL′
intL,c,bL′
L,b,cL′图3-6 两种文法为int a,b,c构造的分析树
a? (a ) (b ) (a) 文法G(D)； (b) 文法G′(D) 3.9 考虑文法G[S]: S→(T) | a+S | a T→T,S | S 消除文法的左递归及提取公共左因子，然后对每个非终结符写出不带回溯的递归子程序。 【解答】 消除文法G[S]的左递归： S→(T) | a+S | a T→ST′
T′→,ST′| ε 提取公共左因子： S→(T) | aS′ S′→+S | ε T→ST′
T′→,ST′| ε
改造后的文法已经是LL(1)文法，不带回溯的递归子程序如下： void match (token t) {
if ( lookahead==t) lookahead=nexttoken; else error ( ); }
void S ( ) {
if ( lookahead==′a′) match (′a′);
else if ( lookahead==′(′) {
match (′(′); T ( );
void S′( ) {
if ( lookahead==′+′) {
match (′+′); S ( ); } }
void T ( ) { S ( ); T′( ); }
void T′ ( ) {
if ( lookahead==′, ′) {
match (′, ′); S ( ); T′ ( ); } }
3.10 已知文法G[A]: A→aABl|a B→Bb|d (1) 试给出与G[A]等价的LL(1)文法G[A′]； (2) 构造G[A′]的LL(1)分析表； (3) 给出输入串aadl#的分析过程。 【解答】 (1) 文法G[A]存在左递归和回溯，故其不是LL(1)文法。要将G[A]改造为LL(1)文法，首先要消除文法的左递归，即将形如P→Pα | β的产生式改造为 P→βP′ P→αP′| ε
来消除左递归。由此，将产生式B→Bb|d改造为 B→dB′
B′→bB′| ε 其次，应通过提取公共左因子的方法来消除G[A]中的回溯，即将产生式A→aABl|a改造为 A→aA′
A′→ABl | ε
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库编译原理教程课后习题答案——第三章在线全文阅读。
相关推荐：