编译原理 备课 课件 4_2.ppt

4.2 S属性定义的自下而上计算n语法树(Abstract Syntax Tree)可以作为一种中间语言表示，在分析树中去掉那些对翻译不必要的信息，从而获得更有效的源程序中间表示，在语法树中，操作符和关键字都不作为叶节点出现，而是把它们作为内部节点，即这些叶节点的父节点if-then-elseBS1S2+*2584.2.2 构造语法树的语法制导定义nmknode(op,left,right) 建立一个运算符号节点，标号是op，两个域left和right分别指向左子树和右子树nmkleaf(id,entry)建立一个标识符节点，一个域entry指向标识符在符号表中的入口nmkleaf(num,val) 建立一个数节点，标号为num，一个域val用于存放数的值n为表达式建立抽象语法树的属性文法 产生式 语义规则 EE1+T E.nptr:=mknode(+,E1.nptr,T.nptr) ET E.nptr:=T.nptr TT1*F T.nptr:=mknode(*,T1.nptr,F.nptr) TF T.nptr:=F.nptr F(E) F.nptr:=E.nptr Fid F.nptr:=mkleaf(id,id.entry) Fnum F.nptr:=mkleaf(num,num.val)a+5*b idnum 5 id到 a的表项到 b的表项* +E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum 5*+指向符号表中a的入口指向符号表中b的入口4.2.3 S属性的自下而上计算nS-属性定义：仅仅使用综合属性的属性定义n分析器可以在栈中保存与栈中文法符号有关的综合属性值，每当进行归约时，新的属性值就由栈中正在归约的产生式右边符号的属性值来计算top. . .Z Z.zY Y.yX X.xstate val若产生式A XYZ的语义规则是A.a := f (X.x, Y.y, Z.z)，那么归约后：. . . . . .AA.a. . . . . .top . . . . . .ZZ. zYY. yXX.x. . . . . .栈 state valtop产 生 式 语 义 规 则 L E n print (E.val) E E1 + T E.val :=E1 .val +T.val E T E.val := T.val T T1 * F T.val := T1.val * F.val T F T.val := F.val F (E) F.val := E.val F digit F.val := digit.lexval台式计算器的语法制导定义改成栈操作代码. . . . . .ZZ. zYY. yXX.x. . . . . .栈 state valtop产 生 式 代 码 段 L E n print (val top1 ) E E1 + T E.val :=E1 .val +T.val E T E.val := T.val T T1 * F T.val := T1.val * F.val T F T.val := F.val F (E) F.val := E.val F digit F.val := digit.lexval. . . . . .ZZ. zYY. yXX.x. . . . . .栈 state valtop产 生 式 代 码 段 L E n print (val top1 ) E E1 + T val top 2 :=val top 2+val top E T E.val := T.val T T1 * F T.val := T1.val * F.val T F T.val := F.val F (E) F.val := E.val F digit F.val := digit.lexval. . . . . .ZZ. zYY. yXX.x. . . . . .栈 state valtop产 生 式 代 码 段 L E n print (val top1 ) E E1 + T val top 2 :=val top 2+val top E T T T1 * F T.val := T1.val * F.val T F T.val := F.val F (E) F.val := E.val F digit F.val := digit.lexval. . . . . .ZZ. zYY. yXX.x. . . . . .栈 state valtop产 生 式 代 码 段 L E n print (val top1 ) E E1 + T val top 2 :=val top 2+val top E T T T1 * F val top 2 := val top 2val top T F T.val := F.val F (E) F.val := E.val F digit F.val := digit.lexval. . . . . .ZZ. zYY. yXX.x. . . . . .栈 state valtop产 生 式 代 码 段 L E n print (val top1 ) E E1 + T val top 2 :=val top 2+val top E T T T1 * F val top 2 := val top 2val top T F F (E) F.val := E.val F digit F.val := digit.lexval. . . . . .ZZ. zYY. yXX.x. . . . . .栈 state valtop产 生 式 代 码 段 L E n print (val top1 ) E E1 + T val top 2 :=val top 2+val top E T T T1 * F val top 2 := val top 2val top T F F (E) val top 2 :=val top 1 F digit F.val := digit.lexval. . . . . .ZZ. zYY. yXX.x. . . . . .栈 state valtop产 生 式 代 码 段 L E n print (val top1 ) E E1 + T val top 2 :=val top 2+val top E T T T1 * F val top 2 := val top 2val top T F F (E) val top 2 :=val top 1 F digit 。