消除直接左递归时语义规则的处理 假设 A→A1Y A.a=8(A1.a,Y.y） -A→X A.a=f(X.x) 。那么 A→XR R.i=f(X.x);A.a=R.s R→YR1 R1i=8(R.i,Y.y);R.S=R1.s R→e R.s=R.i R即是我们以前消除左递归时引入的A' 16
消除直接左递归时语义规则的处理 • 假设 – A → A1 Y A.a = g(A1 .a, Y.y) – A → X A.a = f(X.x) • 那么 – A → X R R.i = f(X.x); A.a = R.s – R → Y R1 R1 .i = g(R.i, Y.y); R.s = R1 .s – R → ε R.s = R.i 16 R即是我们以前消除左递归时引入的 南大编译许畅 A
SDD的求值顺序 ·在对SDD的求值过程中 如果结点N的属性a依赖于结点M1的属性a1,M2的属性 2,…那么我们必须先计算出M;的属性a,才能计算N 的属性a 。使用依赖图来表示计算顺序 这些值的计算顺序形成一个偏序关系，如果依赖图中 出现了环，表示属性值无法计算 17
SDD的求值顺序 • 在对SDD的求值过程中 – 如果结点N的属性a依赖于结点M1的属性a1，M2的属性 a2，…那么我们必须先计算出Mi的属性ai，才能计算N 的属性a • 使用依赖图来表示计算顺序 – 这些值的计算顺序形成一个偏序关系，如果依赖图中 出现了环，表示属性值无法计算 17 南大编译许畅
依赖图 描述了某棵特定的分析树上各个属性之间的信息 流（计算顺序） 从实例a1到实例a2的有向边表示计算a2时需要a1的值 对于分析树结点N,与N关联的每个属性都对应 依赖图的一个结点N.a 产生式 语义规则 E→E1+T E.val E.val +T.val E val E val 十 val 图5-6E.val由E1.val和 T.val综合得到 18
依赖图 • 描述了某棵特定的分析树上各个属性之间的信息 流 (计算顺序) – 从实例a1到实例a2的有向边表示计算a2时需要a1的值 • 对于分析树结点N，与N关联的每个属性a都对应 依赖图的一个结点N.a 18 南大编译许畅
依赖图的例子 。3*2的注释分析树 产生式 语义规则 1)T→FTm T',inh F.val T→FT T.val T'.syn T".inh F.val 2)T'→*FT T.inh=T.imh×F.val T.val T.syn T'.syn T1.syn 3) T'.syn=T'.inh 边e1,e2 4)F→digit F.val =digit.lexval T 9 val e2 el F 3 val 0b5` digit 1 lexval F 4 val digit 2 lexval 19
依赖图的例子 • 3 * 2的注释分析树 • T → F T' – T'.inh = F.val – T.val = T'.syn – 边e1, e2 19 南大编译许畅
属性值的计算顺序 各个属性值需要按照依赖图的拓扑顺序计算 如果依赖图中存在环，则属性计算无法进行 。 给定一个SDD,很难判定是否存在一棵分析树， 其对应的依赖图包含环 但是特定类型的SDD一定不包含环，且有固定的 计算顺序 如：S属性的SDD,L属性的SDD 20
属性值的计算顺序 • 各个属性值需要按照依赖图的拓扑顺序计算 – 如果依赖图中存在环，则属性计算无法进行 • 给定一个SDD，很难判定是否存在一棵分析树， 其对应的依赖图包含环 • 但是特定类型的SDD一定不包含环，且有固定的 计算顺序 – 如：S属性的SDD，L属性的SDD 20 南大编译许畅