编译原理课程总复习----贾棋解读.ppt

* * * * * * * * * * 在FRIST(T?)中，+, )和$在FOLLOW (T?) 中。 * * 在FRIST(T?)中，+, )和$在FOLLOW (T?) 中。 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 从转换表构造转换图。 * * * * * * * * * * * * * 比较手工构造的NFA和用教材上语法制导的算法构造的NFA。鼓励学生写出引入尽可能少的? 转换的语法制导的算法，在将来的解题中使用这个算法。 * 《编译原理习题精选》1.5题。 * * * * * * * * * * 例 数学排版语言EQN E sub 1 .val 产 生 式 语 义 规 则 S ? B B.ps := 10; S.ht := B.ht B ? B1 B2 B1.ps := B.ps; B2.ps := B.ps; B.ht := max(B1.ht, B2.ht ) B ? B1 sub B2 B1.ps:=B.ps; B2.ps:= shrink(B.ps); B.ht := disp (B1.ht, B2.ht ) B ? text B.ht := text.h ? B.ps E 1 .val 1. 产生式右边的符号的继承属性必须在先于这个符号的动作中计算出来。 2. 一个动作不能引用这个动作右边的符号的综合属性。 3. 产生式左边非终结符的综合属性只有在它所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常放在产生式右端的末尾。 例 数学排版语言EQN S ? {B.ps := 10 } B {S.ht := B.ht } ?B ? {B1.ps := B.ps } B1 {B2.ps := B.ps } B2 {B.ht := max(B1.ht, B2.ht ) } ?B ? { B1.ps :=B.ps } B1 sub { B2.ps := shrink(B.ps) } B2 {B.ht := disp (B1.ht, B2.ht ) } ?B ? text {B.ht := text.h ? B.ps } 例 左递归的消除引起继承属性 产 生 式 语 义 规 则 E ? E1 + T E.nptr := mknode( ‘+’, E1.nptr, T.nptr) E ? T E.nptr := T.nptr T ? T1*F T.nptr := mknode( ‘*’, T1.nptr, F.nptr) T ? F T.nptr := F.nptr F ? (E) F.nptr := E.nptr F ? id F.nptr := mkleaf (id, id.entry) F ? num F.nptr := mkleaf (num, num.val) E ? T {R.i := T.nptr} T + T + T + … R {E.nptr := R.s} R ? + T {R1.i := mknode ( ‘+’, R.i, T.nptr)} R1 {R.s := R1.s} R ? ? {R.s := R.i } T ? F {W.i := F.nptr} W {T.nptr := W.s} W ? * F {W1.i := mknode ( ‘*’, W.i, F.nptr)} W1 {W.s := W1.s} W ? ? {W.s := W.i } 消除左递归后文法 R R R + T.nptr ？ 使用继承属性构造a－4＋c的抽象语法树 E T R id To entry for a id T.nptr - T num num 4 T.nptr R. i - R + T R id To entry for c id T.nptr R. i + R. i ? R. s R. s R. s E.nptr E → T {R.i:=T.nptr} R {E.nptr:=R.s} R → + T {R1.i:=mknode(‘+’,R.i,T.nptr)} R1 {R.s:=R1.s} R → - T {R1.i:=mknode(‘－’,R.i,T.nptr)} R1 {R.s:=R.s}