DOC《第五章部分习题解答》

第五章部分习题解答 Aho:《编译原理技术与工具》书中习题 (Aho)5.

3 为下面表达式构造有向无环图,标出结点(子表达式)编号,+是左结合的 a + a + (a + a + a + (a + a + a + a)) 解: (Aho)5.5 设计语法制导定义,实现多项式(包含+和*,如x*(3*x+x*x))的求导,结果无需化简,如3*x直接翻译为3*1+0*x即可.(思路:(xy)'=x'y+y'x,(x+y)'=x'+y') 解: 综合属性diff为求导后的表示形式,val为原多项式表示形式 E→E1 + T { E.val = E1.val E.val;

E.diff = E1.diff E.diff;

} | T { E.val = T.val;

E.diff = T.diff;

} T→T1 * F { T.val = T1.val F.val;

T.diff T1.diff F.val T1.val F.diff | F { T.val = F.val;

T.diff = F.diff;

} F→ ( E ) { F.val E.val F.diff E.diff | num { F.val = num.val;

F.diff = 0;

} | x { F.val = "x";

F.diff = 1;

} 此题和后面两题均可编写Lex&Yacc程序进行验证. (Aho)5.4 设计翻译模式,实现将中缀表达式翻译为无多余括号形式 解:所谓"多余括号",可以理解为: 本该是表达式E,写成了(E)的形式, 本该是项T,写成了(T)的形式, 本该是因式F,写成了(F)的形式,因此,可写出文法和翻译模式: E→( E1 ) { E.s = E1.s;

} | E1 + T { E.s = E1.s T.s;

} | T { E.s = T.s;

} T→( T1 ) { T.s = T1.s;

} | T1 + F { T.s = T1.s F.s;

} | F { T.s = F.s;

} F→( F1 ) { F.s = F1.s;

} | ( E ) { F.s E.s | num { F.s = num.lexeme;

} | id { F.s = id.lexeme;

} 显然,这是一个二义性文法,存在移进-归约冲突和归约-归约冲突,但通过分析语法含义,可解决冲突. 我们将E→( E1 )、T→( T1 )、F→( F1 )称为"多余括号产生式".显然,"多余括号表达式"存在多个语法树,可通过"多余括号产生式"推导而得,也可仅通过"正常产生式"推导而来,这也是二义性的根源.而"无多余括号表达式"是不可能通过"多余括号产生式"推导而来的.因此,对于冲突的情况,我们可以优先选择"多余括号产生式",确定移进/归约.在Parser Generator 2工具中,移进/归约冲突总是选择移进,归约/归约冲突选择顺序靠前的产生式.如上的产生式顺序即可保证每个冲突情况都选择"多余括号产生式". (Aho)5.8 令综合属性val给出下列文法S产生的二进制数的值,例如,输入101.101时,S.val=5.625 S→ L , L | L L→ L B | B B→

0 |

1 设计语法制导定义,实现对S.val的求值,B的综合属性只允许有一个:c,表示B产生的位对最终值的贡献. S→ L1 , L2 {S.val = L1.val + L2.val / L2.f;

} | L { S.val = L.val;

} L→ L1 B { L.val = L1.val *

2 + B.c;

L.f = L1.f * 2;

} | B { L.val = B.c;

L.f = 2;

} B→

0 { B.c = 0;

} |

1 { B.c = 1;

} (Aho)5.9 重写例5.3中语法制导定义的基础文法,使得类型信息只需用综合属性来传播 解:改写后文法和语法制导定义为 L→T id { L.type = T.type;

addtype(id.entry, L.type);

} L→L1, id { L.type = L1.type;

addtype(id.entry, L.type);

} T→int { T.type = integer;

} T→real { T.type = real;

} (Aho)5.10 当下列文法产生的语句翻译为抽象机器代码时,break语句翻译为一个跳转指令,它跳转到最近的while循环.终结符expr表示表达式,other表示其他类型语句,这两个终结符都有综合属性code,表示翻译后的代码. S→ while expr do begin S end | S ;

S | break | other 试给出一个语法制导定义,将语句翻译为抽象堆栈机代码,保证break的正确翻译 解:语法制导定义如下,其中begin和next为继承属性,分别表示语句的开始和结束(下一条语句开始) S→ while expr do begin S1 end { S.begin = newlabel();