【编译原理】语法制导的语义计算——注释分析树

记住下面八个字,所有题目引刃而解 —— 向上综合,向下继承
由于【综合属性】【继承属性】【注释分析树】的概念过于抽象,本文通篇采用立例题的形式。
文章末尾给出手绘答案(图解)

▍1·简单的向上综合

给出G[S]的一个属性文法,且注释分析树已经画好。补全注释分析树即可:

S →( L ) {S.num := L.num + 1;} S → a {S.num := 0;} L → L₁, S {L.num := L₁.num + S.num;} L → S {L.num := S.num}

▍2·简单的向上综合

给出G[S]的一个属性文法,且注释分析树已经画好。请画出3 * (5 + 4)的注释分析树:

S→E {print(E.val)} E → E₁ + T {E.val := E₁.val + T.val} E → T {E.val := T.val} T → T₁ * F {T.val := T₁.val * F.val} T → F {T.val := F.val} F → (E) {F.val := E.val} F → d {F.val := d.lexval}

▍3·向上综合 + 向下继承,比较经典的题目

给出G[S]的一个属性文法,且注释分析树已经画好。请画出3 + 4 - 5的注释分析树:

E → TR {R.in := T.val;   E.val := R.val} R → +TR₁ {R₁.in := R.in + T.val;  R.val := R₁.val} R → -TR₁ {R₁.in := R.in - T.val;  R.val := R₁.val} R → ε {R.val := R.in} T → num {T.val := lexval(num)}

▍4·这有什么用呢?通过这个题目你就能明白

对于语言L = {aⁿbⁿcⁿ | n>=1},根据如下的语义计算模型,验证aaabbbccc是否被接受:

S → ABC {B.in := A.n; C.in := A.n; if(B.n = 0 and C.n = 0) then print(“Accept”) else print(“Refused”)} A → A₁a {A.n := A₁.n + 1} A → a {A.n := 1} B → B₁b {B₁.in := B.in;  B.n := B₁.n - 1} B → b {B.n := B.in - 1} C → C₁c {C₁.in := C.in;  C.n := C₁.n - 1} C → c C.n := C.in - 1}

▍清晰答案

本文题目引用/改编自: 《编译原理(第三版)》清华大学出版社

对应页码/题号(按顺序): P189 T2,P199 T3,P199 T4,P162 例7.2

再次加深记忆: 向上综合,向下继承

E N D END END

经验分享 程序员 微信小程序 职场和发展