第七章语法制导的语义计算-3.ppt

1、第七章 语法制导的语义计算,学习目标： 掌握： 属性文法 基于属性文法的语义计算 基于翻译模式的语义计算 理解：,语义分析基础,语义的种类 静态语义 即可以在程序运行之前静态确定的语义，如类型信息 编译程序进行静态语义分析 动态语义 即程序运行的时候才能确定的语义，如程序的运行结果,语义分析基础,静态语义分析 主要是类型检查，例如： 各种条件表达式的类型是不是boolean型？ 运算符的分量类型是否相容？ 赋值语句的左右部的类型是否相容？ 行参和实参的类型是否相容? 下标表达式的类型是否为所允许的类型？ 函数说明中的函数类型和返回值的类型是否一致？,语义分析基础,其它静态语义检查： VE中的V

2、是不是变量，而且是数组类型？ V.i中的V是不是变量，而且是记录类型？i是不是该记录的域名？ x+f()中的f是不是函数名？形参个数和实参个数是否一致？ 每个使用性标识符是否都有声明？有无标识符的重复声明？,语法制导的语义计算,语法制导的（Syntax-Directed）语义计算 以语法定义（上下文无关文法）为基础 由语法分析程序的分析过程来主导语义分析以及翻译的过程 语法制导的静态语义分析 语法制导的中间代码生成,语法制导的语义计算,语义计算模型 对上下文无关文法（语法定义）进行扩展 为文法符号附加语义信息 针对产生式设计语义动作 语义计算模型包括： 属性文法：侧重于语义计算规则的定义 翻译

3、模式：侧重于语义计算过程的定义,语法制导的语义计算,7.1基于属性文法的语义计算 7.2基于翻译模式的语义计算,7.1基于属性文法的语义计算,属性 对文法的每一个符号，引进一些属性，这些属性代表与文法符号相关的信息，如类型、值、存储位置等。 语义规则 为文法的每一个产生式关联的计算属性的计算规则，称为语义规则。,7.1.1 属性文法,属性文法是带属性的一种文法 它的主要思想： 首先，对于每个文法符号引进相关的属性符号； N.t表示文法符号N的属性t。属性值又称语义值 其次，对于每个产生式A写出计算属性值的语义规则，用于描述如何计算当前产生式中 文法符号的属性值或附加的语义动作,7.1.1 属性

4、文法,属性文法中允许如下语义规则 复写规则，形如 X.a := Y.b 基于语义函数的规则，形如 b:=f(c1, c2, , ck) 或 f(c1, c2, , ck) 其中，b,c1, c2, , ck是该产生式中文法符号的属性 语义函数的形式灵活,属性文法举例,识别语言 L = anbncn n 1 ?,产生式 S ABC A A1a A a B B1b B b C C1c C c,语义动作/限定条件 (A.num=B.num) and (B.num=C.num) A.num := A1.num + 1 A.num := 1 B.num := B1.num + 1 B.num := 1

5、C.num := C1.num + 1 C.num := 1 ,7.1.1 属性文法,属性文法举例,识别语言 L = aibjck i, j, k 1 不含限定条件，但显示 anbncn (n 1) 是合法的,产生式 S ABC A A1a A a B B1b B b C C1c C c,语义动作 if (A.num=B.num) and (B.num=C.num) then print(“Accepted!” ) else print(“Refused!” ) A.num := A1.num + 1 A.num := 1 B.num := B1.num + 1 B.num := 1 C.nu

6、m := C1.num + 1 C.num := 1 ,7.1.1 属性文法,7.1.1 属性文法,完成类型检查的属性文法，与文法符号相联的是类型属性 ET1+T2T1.tint AND T2.tint ET1 or T2T1.tbool AND T2.tbool TnumT.t :int TtrueT.t :bool TfalseT.t :bool,属性文法举例,7.1.1 属性文法,属性有两种：综合属性和继承属性 综合属性： 从语法树的角度来看，如果一个结点的某一属性值是由该结点的子结点的属性值计算来的，则称该属性为综合属性。 对关联于产生式 A 的语义规则 b:=f(c1, c2, ,

7、ck) ，如果 b 是 A 的某个属性, 则称 b 是 A 的一个综合属性 用于“自下而上”传递信息,属性文法举例,仅含综合属性的例子（开始符号S）,7.1.1 属性文法,产生式 S E E E1 + T E T T T1 F T F F ( E ) F d,语义动作 print(E.val) E.val := E1.val + T.val E.val := T.val T.val := T1.val F.val T.val := F.val F.val := E.val F.val := d.lexval ,注：d.lexval 是词法分析程序确定的属性值,综合属性代表自下而上传递的信息,对

8、表达式 3(5+4) 的分析树进行自下而上（后序）遍历， 并执行相应的语义规则， 得到该表达式的一种求值过程,7.1.1 属性文法,T,E,T,E,F,T,d,(,),d,S,E,F,F,T,d,F,d.lexval=5,d.lexval=3,d.lexval=4,F.val=5,F.val=3,T.val=3,T.val=5,E.val=5,F.val=4,T.val=4,E.val=9,F.val=9,T.val=27,E.val=27,print(27),7.1.1 属性文法,继承属性 从语法树的角度来看，若一个结点的某一属性值是由该结点的兄弟结点和（或）父结点的属性值计算来的，则称该属

9、性为继承属性。 对关联于产生式 A 的语义规则 b:=f(c1, c2, , ck) 如果 b 是产生式右部某个文法符号 X 的某个属性，则称 b 是文法符号 X 的一个继承属性 用于“自上而下”传递信息,产生式 S ABC A A1a A a B B1b B b C C1c C c,语义动作 B.in_num := A .num; C.in_num := A .num; if (B.num=0 and (C.num=0) then print(“Accepted!” ) else print(“Refused!” ) A.num := A1.num + 1 A.num := 1 B1.in_

10、num := B.in_num; B.num := B1.num-1 B.num := B.in_num -1 C1.in_num := C.in_num; C.num := C1.num-1 C.num := C.in_num -1 ,识别语言 L = aibjck i, j, k 1 显示 anbncn (n 1) 是合法的（另一种设计）,7.1.1 属性文法,属性文法举例,含继承属性的例子,产生式 S ABC A A1a A B B1b B C C1c C ,语义动作 B.in_num := A .num; C.in_num := A .num; if (B.num=0 and (C.n

11、um=0) then print(“Accepted!” ) else print(“Refused!” ) A.num := A1.num + 1 A.num := 0 B1.in_num := B.in_num; B.num := B1.num-1 B.num := B.in_num C1.in_num := C.in_num; C.num := C1.num-1 C.num := C.in_num ,其中，A .num，B.num 和 C.num 是综合属性值，而 B.in_num 和 C.in_num 是继承属性值,属性文法举例,继承属性代表自上而下传递的信息,对输入串 aabbcc

12、的分析树进行遍历， 自下而上执行综合属性相应的语义动作， 自上 而下执行继承属性相应的语义动作， 可以得到所有属性值的一个求值过程,例 描述变量类型说明的属性文法 DTL L.in:T.type Tint T.type:int Treal T.type:real LL1,id L1.in:L.in；id.in=L.in ) Lidid.in=L.in,L.in是继承属性 T.type是综合属性,int id1,id2的语法树:,用表示属性的传递情况,7.1.2 遍历分析树进行语义计算,基于属性文法的语义计算 两类计算方法： 树遍历方法 通过遍历分析树进行属性计算 单遍的方法 语法分析的同时进行

13、属性计算,基于树遍历方法的语义计算,步骤 构造输入串的语法分析树 构造依赖图 若该依赖图是无圈的，则按造此无圈图的一种 拓扑排序对分析树进行遍 历，则可以计算所有的属性,7.1.2 遍历分析树进行语义计算,基于树遍历方法的语义计算,若依赖图含有圈，则相应的属性文法不可采用这种方法进行语义计算 此类属性文法不是良定义的 所谓良定义的属性文法，当且仅当它的规则集合能够为所有分析树中的属性集确定唯一的值集。,7.1.2 遍历分析树进行语义计算,7.1.2 遍历分析树进行语义计算,依赖图 是一个有向图 描述分析树中的属性和属性间的相互依赖关系。,依赖图的构造算法 for 分析树中每一个结点n do f

14、or 结点n所用产生式的每个语义规则中涉及的每一个属性a do 为a在依赖图中建立一个结点； for 结点n所用产生式中每个形如f(c1,c2,ck)的语义规则 do 为该规则在依赖图中也建立一个结点（称为虚结点）； for 分析树中每一个结点n do for 结点n所用产生式对应的每个语义规则 b:=f(c1,c2,ck) do （可以只是f(c1,c2,ck) ，此时b结点为一个虚结点） for i :=1 to k do 从ci结点到b结点构造一条有向边,real x,y的依赖图,id(y),L,D,T,L,real,id(x),in,in,type,in,in,例 描述变量类型说明的属

15、性文法 DTL L.in:T.type Tint T.type:int Treal T.type:real LL1,id L1.in:L.in；id.in=L.in ) Lidid.in=L.in,例 简单算术表达式求值的属性文法 EE1+T E.val :E1.val +T.val ET E.val :T.val TT1*F T.val :T1.val * F.val TF T.val :F.val F(E) F.val :E.val Fdigit F.val :digit.lexval ,(34-3)*42 的依赖图,val,val,val,val,val,val,val,val,val,

16、val,val,val,val,val,综合属性的计算通过自下而上（后根）遍历语法树 Procedure PostEval (T : treenode); Begin For each child C of T do PostEval(C); Compute all synthesized attributes of T; End,7.1.2 遍历分析树进行语义计算,继承属性的计算通过先根遍历，或者结合先根遍历和中根遍历语法树 procedure PreEval(T:treenode); begin for each child C of T do compute all inherited

17、attributes of C; PreEval(C); end;,7.1.2 遍历分析树进行语义计算,产生式 N S1.S2 S S1B S B B 0 B 1,语义动作 N.v := S1.v+S2.v; S1.f :=1; S2.f :=2-S2.l S1.f := 2*S.f; B.f : =S.f; S.v := S1.v+B.v; S.l := S1.l +1 S.l := 1 ; S.v := B.v ; B.f := S.f B.v := 0 B.v := B.f ,例：该属性文法可用于将二进制无符号小数转化为十进制小数,考虑输入串 10.01 的语义计算过程,步骤一 构造输入

18、串10.01的语法分析树,S,S,N,S,B,0,.,B,1,S,B,1,B,0,7.1.2 遍历分析树进行语义计算,步骤二 为分析树中所有结点的每个属性建立一个 依赖图中的结点，并给定一个标记序号,S,S,N,S,B,0,.,B,1,S,B,1,B,0,7.1.2 遍历分析树进行语义计算,步骤三 根据语义动作，建立依赖图中的有向边,S,S,N,S,B,0,.,B,1,S,B,1,B,0,1：v,N S1.S2 N.v := S1.v+S2.v ,N S1.S2 S2.f :=2-S2.l ,S S1B S.l := S1.l +1 ,S S1B S.v := S1.v+B.v ,B 1 B.

19、v := B.f ,S S1B S1.f := 2S.f; B.f : =S.f ,S B S.v := B.v ,S B B.f := S.f ,步骤四 该依赖图是无圈的，因此存在拓扑排序. 依任何一个拓扑排序，都能够顺利完成 属性值的计算 如下是一种可能的计算次序： 3,5,2,6,10,8,9,7,11,4,15,12,13,16,20,18,21,19,17,14,1,S,S,N,S,B,0,.,B,1,S,B,1,B,0,1：v,步骤五 依计算次序，根据语义动作求出各结点对应的属性值 对如下结点次序进行计算： 3,5,2,6,10,8,9,7,11,4,15,12,13,16,20,

20、18,21,19,17,14,1,S,S,N,S,B,0,.,B,1,S,B,1,B,0,1：v,4：v,3：f,2：l,5：l,6：f,7：v,8：f,9：v,10：f,11：v,18：f,19：v,15：l,16：f,17：v,12：l,13：f,14：v,20：f,21：v,1,1,2,2,1,2,2,2,0,2,1,2,0.25,0.5,0.25,0.5,0.25,0,0,0.25,2.25,语法分析树中各结点属性值的计算过程被称为对语 法分析树的标注 用带标注的语法分析树表示属性值的计算结果,带标注的语法分析树,S,S,N,S,B,0,.,B,1,S,B,1,B,0,f=1,l=1,

21、l=2,f=2,l=2,f=2,v=2,v=2,v=0,v=2,f=1,l=2,f=0.25,f=0.5,f=0.25,f=0.5,v=0.25,v=0,v=0,v=0.25,v=2.25,单遍的方法,语法分析遍的同时进行属性计算 自下而上方法 自上而下方法 在语法分析过程中，随着分析的步步进展，每当使用一条产生式进行推导（对于自上而下分析）或归约（对于自下而上分析），就执行该产生式所对应的语义动作,基于属性文法的语义计算,例 简单算术表达式求值的属性文法 EE1+T E.val :E1.val +T.val ET E.val :T.val TT1*digit T.val :T1.val *

22、digit.lexval Tdigit T.val :digit.lexval ,2+3*5的语法树：,T.val=2,T.val=3,T.val=15,E.val=2,E.val=17,语法制导的语义计算：,一旦语法分析确认输入符号串是一个句子，它的值也同时由语义规则计算出来,单遍的方法,只适用于特定文法 S-属性文法 L-属性文法,基于属性文法的语义计算,S-属性文法,只包含综合属性,L-属性文法,如果对其中每一个产生式A X1X2Xn，其每个语义动作所涉及的属性或者是综合属性，或者是某个Xi（1in）的继承属性，而这个继承属性只能依赖于 （1）Xi左边的符号X1,X2,Xi-1的属性；

23、（2）A的继承属性 S-属性文法是L-属性文法的一个特例,7.1.3 S-属性文法和L-属性文法,通常采用自下而上的方式进行 采用LR分析进行S-属性文法的语义计算 扩充分析栈中的域，增加语义栈存放综合属性的值，多项语义值可用多个语义栈,7.1.4 基于S-属性文法的语义计算,在每一步归约之前，调用语义规则，计算相应产生式左部文法符号的综合属性值,扩充语义栈的LR分析模型,7.1.4 基于S-属性文法的语义计算,分析栈,分析表,产生式（含语义动作）表,分析引擎,状态,符号,语义,例如，假设有相应于产生式 AXYZ 的语义规则 A.a := f（X.x, Y.y, Z.z） 在 XYZ 归约为

24、A 之前，Z.z, Y.y, 和 X.x 分别存放 于语义栈的 top，top-1 和 top-2 的相应域中，因 此 A.a 可以顺利求出 归约后，X.x, Y.y, Z.z 被弹出，而在栈顶 top 的位 置上存放 A.a。,采用LR分析进行S-属性文法的语义计算,语义动作中的综合属性可以通过当前语义栈 栈顶的属性进行计算,7.1.4 基于S-属性文法的语义计算,产生式 S E E E1 + T E T T T1 F T F F ( E ) F d,语义动作 print(E.val) E.val := E1.val + T.val E.val := T.val T.val := T1.va

25、l F.val T.val := F.val F.val := E.val F.val := d.lexval ,举例,通过下列S-属性文法GS为常量表达式求值,7.1.4 基于S-属性文法的语义计算,文法GS 的LR分析表,状态,ACTION,GOTO,d,+,(,),#,E,T,F,0,1,2,3,4,5,6,7,8,9,10,11,1,2,3,acc,s6,s7,r2,r2,r2,r4,r4,r4,s4,s5,s5,s4,8,2,3,r4,r6,r6,r6,r6,s5,s4,9,3,s5,s4,10,s11,s7,r1,r1,r1,r3,r3,r3,r3,r5,r5,r5,r5,s6,（

26、0）SE （1）E E+T （2） E T （3）T TF （4） T F （5）F (E) （6）F d,LR分析过程，同时进行常量表达式2 + 3 5的求值,分析栈（状态，符号，语义值）,余留输入串,动作,语义动作,（0）SE （1）E E+T （2） E T （3）T TF （4） T F （5）F (E) （6）F d,翻译模式 适合语法制导语义计算的另一种描述形式 体现一种合理调用语义动作的翻译算法 形式上类似于属性文法，但允许由 括起来的语义规则出现在产生式右端的任何位置. 好处：显式地表达属性计算的次序，而在属性文法中不体现这种次序,7.2 基于翻译模式的语义计算,翻译模式举例,

27、识别语言 L = aibjck i, j, k 1 显示 anbncn (n 1) 是合法的,S A B.in_num := A .num B C.in_num := A .num C if (B.num=0 and (C.num=0) then print(“Accepted!” ) else print(“Refused!” ) A A1a A.num := A1.num + 1 A a A.num := 1 B B1.in_num := B.in_num B1b B.num := B1.num-1 B b B.num := B.in_num -1 C C1.in_num := C.in_

28、num C1c C.num := C1.num-1 C c C.num := C.in_num -1 ,显示描述了属性计算的次序，确定了语义动作执行的位置,受限的翻译模式 在设计翻译模式时，也须作某些限制，以确保在单遍的语义计算过程中，每个属性值，在被访问到的时候已经存在 两类受限的翻译模式 S-翻译模式 L-翻译模式,7.2 基于翻译模式的语义计算,S-翻译模式： 仅涉及综合属性的情形 将语义动作集合，置于相应产生式右端的末尾,7.2 基于翻译模式的语义计算,L-翻译模式： 既包含继承属性，也包含综合属性的情形，需满足两个条件： （1）产生式右端某个符号继承属性的计算必须位于该符号之前，其语

29、义动作不访问位于它右边符号的属性，只依赖于该符号左边符号的属性 （对于产生式左部的符号，只能是继承属性）； （2）产生式左部非终结符的综合属性的计算只能在所用到的属性都已计算出来之后进行，通常将相应的语义动作置于产生式的尾部。,7.2 基于翻译模式的语义计算,识别语言 L = aibjck i, j, k 1 显示 anbncn (n 1) 是合法的,S A B.in_num := A .num B C.in_num := A .num C if (B.num=0 and (C.num=0) then print(“Accepted!” ) else print(“Refused!” ) A

30、A1a A.num := A1.num + 1 A a A.num := 1 B B1.in_num := B.in_num B1b B.num := B1.num-1 B b B.num := B.in_num -1 C C1.in_num := C.in_num C1c C.num := C1.num-1 C c C.num := C.in_num -1 ,是L-翻译模式，num为综合属性，in_num为继承属性,仅考虑单遍的方法 自上而下的语义计算 借助预测分析技术 自下而上的语义计算 借助移进归约分析技术 仅考虑受限的翻译模式,7.2 基于翻译模式的语义计算,以递归下降分析为例，扩展：

31、 对每个非终结符 A，构造一个函数 以 A 的每个继承属性为形参 以 A 的综合属性为返回值（若 有多个综合属性，可返回记录类型的值） 与每个产生式对应的代码根据产生式右端的结构来构造，但要将语义动作嵌入其中,7.2.3 基于L-翻译模式的自顶向下语义计算,与每个产生式对应的代码根据产生式右端的结构来构造，但要将语义动作嵌入其中： 对终结符 X 将其综合属性x的值保存到为 X.x 而声明的变量；然后，判断当前读入的输入符号是否与该终结符匹配。若匹配，则读取下一个输入符号，若不匹配，则报错 对非终结符 B 执行 c:= ParseB(b1, b2, , bk)，其中变量 b1, b2, , bk 对应 B的各继承属性，变量c对应B的综合属性 对语义动作集 直接复制其中每一语义动作所对应的代码，只是需要将对属性的访问替换为对相应变量的访问。,举例：定点