编译原理：第7章-面向语法的语义描述

1、Z 语义处理的抽象描述语义处理的抽象描述- -语法制导方法语法制导方法Z 动作文法及其应用动作文法及其应用Z 属性文法及其应用属性文法及其应用Z 动作文法：动作文法：产生式右部带有动作符的文产生式右部带有动作符的文法法Z 动作符：动作符： 区别于语法符号的一种符号，区别于语法符号的一种符号， #Name#Name 可出现于产生式的右部的任何地方可出现于产生式的右部的任何地方 没有语法意义，只代表某种语义动作，可看作是没有语法意义，只代表某种语义动作，可看作是无参的语义子程序的名字无参的语义子程序的名字l动作文法的产生式：动作文法的产生式：l L 1 X1 2 X2 k Xk k+1l其中其中i

2、表示动作符，表示动作符，Xi表示语法符号，当然可表示语法符号，当然可以没有动作符以没有动作符 Z 动作文法的例子：动作文法的例子： 给定下图所示的文法给定下图所示的文法GSGS，试写出一个动作文法，试写出一个动作文法，它描述这样一个处理器：输入它描述这样一个处理器：输入0 0、1 1串，求其中串，求其中0 0和和1 1的的出现个数，并分别赋给变量出现个数，并分别赋给变量n0n0和和n1n1，最后将其结果打，最后将其结果打印出来。印出来。 S SL LL LL LDLDLD D0 0D D1 1S SLLL LL LDLDLD D00D D11:n0,n1:=0n0,n1:=0:print(n0

3、,n1)print(n0,n1):n0:=n0+1n0:=n0+1:n1:=n1+1n1:=n1+1Z动作文法的应用动作文法的应用：凡是和程序文本有关的语义凡是和程序文本有关的语义动作，均可用动作文法来描述动作，均可用动作文法来描述Z 尾动作文法：尾动作文法：动作符只出现于产生式末尾的动动作符只出现于产生式末尾的动作文法作文法Z 动作文法的实现：动作文法的实现：依赖于文法的实现方式，可依赖于文法的实现方式，可以是递归下降，以是递归下降，LL,LRLL,LR实现实现 void S()L();void S()L();void L() void L() next(chnext(ch););if (i

4、f (chch=0)L();=0)L();if (if (chch=1)L();=1)L();if (if (chch=a)returna)return;else error();else error();void void S()S()initinit;L();L();outout;void L() void L() next(chnext(ch););if (if (chch=0)=0)add0add0;L();L();if (if (chch=1)=1)add1add1;L();L();if (if (chch=a)returna)return;else error();else err

5、or(); LLLL动作文法：动作文法： 动作文法满足动作文法满足LL(1)LL(1)文法的条件。文法的条件。 实现组成：实现组成： LL(1)LL(1)分析表，分析表，LLLL驱动器，语义子程序。驱动器，语义子程序。 驱动程序的分类驱动程序的分类： 不带语义栈控制：不带语义栈控制：由用户实现语义栈的管由用户实现语义栈的管理，即将语义栈的处理写在语义子程序中。理，即将语义栈的处理写在语义子程序中。 带语义栈控制：带语义栈控制：由驱动器来控制语义栈。由驱动器来控制语义栈。LRCTLRCT指针：指针： LeftIndexLeftIndex：指向当前产生式左部符号的语义栈地址指向当前产生式左部符号的

6、语义栈地址 RightIndexRightIndex：指向当前产生式右部的语义栈基地址指向当前产生式右部的语义栈基地址 CurrentIndexCurrentIndex：指向当前符号的语义栈地址指向当前符号的语义栈地址 TopIndexTopIndex：指向当前第一自由地址指向当前第一自由地址LeftIndexLeftIndex RightIndexRightIndexCurrentIndexCurrentIndex TopIndexTopIndexSemantic StackSemantic Stack算法要点：算法要点：s 语法栈顶是终极符语法栈顶是终极符a:a:判断判断a a是否与输入流

7、匹配，若匹是否与输入流匹配，若匹 配：配：Sem(CSem(C):= ):= a.vala.val; C:=C+1;PopSynStack(1); C:=C+1;PopSynStack(1) 否则报错；否则报错；s 语法栈顶是非终极符语法栈顶是非终极符X:X: 对当前输入对当前输入LLLL分析表有分析表有 X X Y Y1 1Y Y2 2Y Yn n: :将将PushSynStack(Eop,YPushSynStack(Eop,Yn n, ,Y Y2 2Y Y1 1) ) 调整调整LRCTLRCT指针。指针。s 语法栈顶是动作符：语法栈顶是动作符：调用相应的语义动作子程序。调用相应的语义动作子

8、程序。s 若语法栈顶是若语法栈顶是EopEop：PopSynStack(1),PopSynStack(1),恢复恢复LRCTLRCT指针，指针， C:=C+1 C:=C+1 尾动作文法的尾动作文法的LRLR实现：实现： 不带语义栈控制：不带语义栈控制： 归约动作执行前先执行语义动作。归约动作执行前先执行语义动作。 带语义栈控制：带语义栈控制： 语法栈和语义栈同步语法栈和语义栈同步: : 移入时：移入时：输入符压入语法栈中，输入符输入符压入语法栈中，输入符 的语义信息压入语义栈中；的语义信息压入语义栈中； 归约时：归约时：执行语义动作，语法栈和语义栈同时执行语义动作，语法栈和语义栈同时 退退N

9、N个，将产生式左部压入语法栈，个，将产生式左部压入语法栈， 语义信息压入语义栈中。语义信息压入语义栈中。 用动作文法描述表达式计算：用动作文法描述表达式计算： Z Z E E outoutE E T TE E T+E T+E addaddT T P PT T P P* *T T multmultP P n n pushpushP P (E) (E)outout : :print(vtopprint(vtop)addadd : vtop-1:=vtop- : vtop-1:=vtop-1+vtop;top:=top-11+vtop;top:=top-1multmult:vtop-1:=vtop-

10、:vtop-1:=vtop-1+vtop;top:=top-1 1+vtop;top:=top-1 pushpush:top:top:=top+1;:=top+1; vtopvtop:=:=val_Lexval_Lex 用动作文法描述表达式抽象树的构造：用动作文法描述表达式抽象树的构造： E E T TE E E+T E+T mknode(ADD,stop-1,stop)mknode(ADD,stop-1,stop)T T P PT T T T* *P P mknode(MUL,stop-1,stop)mknode(MUL,stop-1,stop)P P n n mkleaf(n,val_Le

11、xmkleaf(n,val_Lex) )P P id id mkleaf(id,name_Lexmkleaf(id,name_Lex) )P P (E) (E) 用动作文法描述语句抽象树的构造：用动作文法描述语句抽象树的构造： S S idid:=E :=E S S idid(E(E) )S S if E then S else S if E then S else SS S while E do S while E do SS S repeat S until E repeat S until ES S NameName:=E :=E build_assbuild_assS S NameNa

12、me(E(E) ) build_callbuild_callS S if E then S else S if E then S else S build_ifbuild_ifS S while E do S while E do S build_whilebuild_whileS S repeat S until E repeat S until E build_repbuild_repName Name id id build_namebuild_name 抽象变量：抽象变量：E.valE.val = E1.val+E2.val = E1.val+E2.val 特点是：用抽象概念描述语义值

13、，不是用存储概念表示特点是：用抽象概念描述语义值，不是用存储概念表示 抽象动作文法：抽象动作文法：含有抽象变量的动作文法含有抽象变量的动作文法 特点是：抽象度高，语义表达清晰，自动化程度高特点是：抽象度高，语义表达清晰，自动化程度高 抽象尾动作文法例：抽象尾动作文法例： E E T T E.valE.val:= := T.ValT.Val E E T+E T+E1 1 E.valE.val:=T.val+E:=T.val+E1 1.val.valT T P P T.valT.val:= := P.valP.val T T P P* *T T1 1 T.valT.val:= := P.valP.

14、val* *T T1 1.val.valP P n n P.valP.val:= := n.valn.val P P (E) (E) P.valP.val:= := E.valE.val 用于描述语言的静态语义用于描述语言的静态语义 主要思想：主要思想： 对每个语法符号定义相关属性；对每个语法符号定义相关属性； 对每个产生式定义属性求值规则对每个产生式定义属性求值规则 例例：valval属性属性E E n n E.valE.val:= := n.valn.val E (EE (E1 1) )E.valE.val:= E:= E1 1.val.valE EE E1 1 + E + E2 2 E.

15、valE.val:= E:= E1 1.val+E.val+E2 2.val.val 继承属性和综合属性继承属性和综合属性 继承属性相当于输入属性，综合属性相当于输出属性继承属性相当于输入属性，综合属性相当于输出属性 从属性语法树的角度来说，结点的继承属性值由其父亲从属性语法树的角度来说，结点的继承属性值由其父亲节点和兄弟结点的属性值决定，综合属性值由本节点的节点和兄弟结点的属性值决定，综合属性值由本节点的继承属性和儿子节点的属性值决定。继承属性和儿子节点的属性值决定。 属性定义属性定义 定义属性名字定义属性名字 定义属性类型定义属性类型( (数据结构数据结构) ) 定义属性类别定义属性类别(

16、 (继承继承/ /综合综合) )l例：例： E senv :SEnv denv :DEnv l etype :EType eval :EValuel id name :Stringl n val :integer 属性变量属性变量X.aX.a, ,其中其中X X是语法符号，是语法符号，a a是是X X的一个属性符号的一个属性符号( (继承，综合继承，综合) )属性变量的类型取决于其中属性符号的类型属性变量的类型取决于其中属性符号的类型 属性规则属性规则l L X1 X2 Xk X1.i = e1l l Xk.i = ekl L.s = e0 属性规则属性规则属性规则次序没有顺序关系；属性规则次

17、序没有顺序关系；属性规则并不表示在此刻要进行属性值的计算；属性规则并不表示在此刻要进行属性值的计算；Xi的属性值可依赖于其后符号的属性值；的属性值可依赖于其后符号的属性值；没有定义产生式右部符号综合属性值的属性规则；没有定义产生式右部符号综合属性值的属性规则；没有定义产生式左部符号继承属性值的属性规则。没有定义产生式左部符号继承属性值的属性规则。 属性文法例属性文法例1(1(不带变量表达式不带变量表达式) )产生式产生式 属性规则属性规则 属性定义属性定义E PE PE.valE.val= = P.valP.valEvalEval :integer :integerPvalPval :inte

18、ger :integernvalnval :integer :integer E E1 1 E E2 2 + P + P E E1 1.val = E.val = E2 2.val + .val + P.valP.valP nP nP.valP.val= = n.valn.valP(E)P(E)P.valP.val= = E.valE.val 属性文法例属性文法例2(2(带变量表达式带变量表达式) )有变量，需要有表示变量值的环境有变量，需要有表示变量值的环境( (动态环境动态环境) )动态环境动态环境envenv是对偶是对偶( (id,vid,v) )的数组或链表的数组或链表Lookup(n

19、ame,envLookup(name,env) )表示用表示用namename去查动态环境表去查动态环境表envenv, ,结果是得到一结果是得到一个值个值EnvEnv是继承属性，需要从父亲节点即产生式左部符号那里得到是继承属性，需要从父亲节点即产生式左部符号那里得到产生式产生式属性规则属性规则属性定义属性定义E PE PE.envE.env= = P.envP.envE.valE.val= = P.valP.valEenv:DEnvEenv:DEnv valval :integer :integer Penv:DenvPenv:Denv valval :integer :integernva

20、lnval :integer :integer idnameidname :string :string E EE E1 1 + P + P E E1 1.env.env= = E.envE.envP.envP.env= = E.envE.envE.valE.val = E = E1 1.val + .val + P.valP.valP nP nP.valP.val= = n.valn.valP idP idP.valP.val= = lookup(,P.denlookup(,P.denv v) )P(E)P(E)P.valP.val= = E.valE.val 属

21、性语法树和属性依赖图属性语法树和属性依赖图根据给出的属性计算规则，对于每一条产生式根据给出的属性计算规则，对于每一条产生式可以画出一个有向图，它表示本产生式中各符可以画出一个有向图，它表示本产生式中各符号的属性之间的依赖关系图，称之为属性规则号的属性之间的依赖关系图，称之为属性规则图。图。 关于产生式关于产生式E1P+E2的属性规则的属性规则的属性规则的属性规则图图envenvvalvalE EenvenvvalvalP PenvenvvalvalE E+ + 属性语法树和属性依赖图属性语法树和属性依赖图假设给定一个属性文法，并且给定一个输入串假设给定一个属性文法，并且给定一个输入串(终极符串

22、终极符串)，则可构造出相应的一棵语法树。，则可构造出相应的一棵语法树。即带有属性的语法树。即带有属性的语法树。 表达式表达式x+y的属性语法树的属性语法树valvalS SdenvdenvvalvalE EdenvdenvvalvalP Pname:xname:xidid+ +denvdenvvalvalE EdenvdenvvalvalP Pname:yname:yidid 属性语法树和属性依赖图属性语法树和属性依赖图对于每棵属性语法树，可画出所谓的属性依赖对于每棵属性语法树，可画出所谓的属性依赖图图(属性数据流图属性数据流图)。 表达式表达式x+y的属性依赖图的属性依赖图valvalS S

23、denvdenvvalvalE EdenvdenvvalvalP Pname:xname:xidid+ +denvdenvvalvalE EdenvdenvvalvalP Pname:yname:yidid 属性计算属性计算属性计算就是根据属性数据流图计算出文法属性计算就是根据属性数据流图计算出文法开始符号结点的综合属性值。不难看出有很多开始符号结点的综合属性值。不难看出有很多计算顺序，都可以算出开始结点的综合属性值。计算顺序，都可以算出开始结点的综合属性值。合理的属性文法应不依赖于计算顺序的选择。合理的属性文法应不依赖于计算顺序的选择。 基于依赖图的计算方法基于依赖图的计算方法l对于给定输入

24、构造属性依赖图（同时计算对于给定输入构造属性依赖图（同时计算终极符结点的综合属性）；终极符结点的综合属性）； l选择一个还未被计算而可计算的属性结点，选择一个还未被计算而可计算的属性结点，并计算它；并计算它； l重复上述过程，直至全部算完为止。重复上述过程，直至全部算完为止。l例初始denv=(x,10),(y,20), ，则最终计算结果是S.val=30.l缺点是占用空间缺点是占用空间 属性文法中的属性规则部分并不表示在此处要做属性文法中的属性规则部分并不表示在此处要做语义动作；语义动作； 属性规则部分只定义了属性求值规则，而且规则属性规则部分只定义了属性求值规则，而且规则间的顺序是随便的；

25、间的顺序是随便的； 在一个产生式的属性规则中，每个属性只能被定在一个产生式的属性规则中，每个属性只能被定义一次，不能像动作子程序那样重复赋值；义一次，不能像动作子程序那样重复赋值； 属性规则中的左部能写哪些属性变量是有规定的。属性规则中的左部能写哪些属性变量是有规定的。 类型树的属性文法描述类型树的属性文法描述 表达式中间代码的属性文法描述表达式中间代码的属性文法描述 变量中间代码的属性文法描述变量中间代码的属性文法描述 语句中间代码的属性文法描述语句中间代码的属性文法描述 正则表达式到自动机转换的属性文法描述正则表达式到自动机转换的属性文法描述 S-S-属性文法属性文法是文法符号只有综合属性

26、的一是文法符号只有综合属性的一种特殊的属性文法。种特殊的属性文法。 最大特点是容易实现，而且任意一个属性最大特点是容易实现，而且任意一个属性文法都可以改写成等价的文法都可以改写成等价的S-S-属性文法。属性文法。 对于对于S-S-属性文法来说，属性计算都在产生属性文法来说，属性计算都在产生式末尾进行，因此可以用式末尾进行，因此可以用LLLL方法和方法和LRLR方法实方法实现现 LL_S_LL_S_属性文法属性文法：产生式满足产生式满足LL(1)LL(1)条件的条件的S-S-属性文属性文法称之为法称之为LL_S_LL_S_属性文法属性文法 。l递归实现原理：递归实现原理：1 1 确定计算顺序。确

27、定计算顺序。2 2 属性文法中每个属性变量对应递归程序中的一个变量：属性文法中每个属性变量对应递归程序中的一个变量：X.aX.a转转换成换成X_aX_a的形式。的形式。3 3 对于每个对于每个V VT T定义一个过程定义一个过程terminalterminal，其调用形式是，其调用形式是terminal(a,a_sterminal(a,a_s) )。 4 4 对于每个对于每个V VN N，定义一个带参数的过程，定义一个带参数的过程A(A_s1,A_s2,A(A_s1,A_s2,A_snA_sn),),其其中中A_siA_si都是引用型参数，将在别处调用时分别得到相应的综合属性都是引用型参数，将

28、在别处调用时分别得到相应的综合属性值。值。5 5 把综合属性计算部分改变为语句形式写在递归子程序的末尾。把综合属性计算部分改变为语句形式写在递归子程序的末尾。 实现例子实现例子：产生式产生式属性计算规则属性计算规则属性定义属性定义AaBBA.S = u(a.s,B.s,B.s)A s,B s,a s,b sBbB.S = r(b.s)procedure procedure A(outA(out A_sA_s) ) varvar a_sa_s, , B_sB_s, , B_sB_s; Terminal(a,a_sTerminal(a,a_s);); B(B_sB(B_s);); B(B_sB(B

29、_s);); A_sA_s:=:=u(a_s,B_s,B_su(a_s,B_s,B_s) ) Procedure Procedure B(outB(out B_sB_s) ) varvar b_sb_s; ; terminal(b,b_sterminal(b,b_s);); B_sB_s:=:=r(b_sr(b_s) ) LR_S-LR_S-属性文法转换成属性文法转换成LR_LR_尾动作文法尾动作文法 LR_S-LR_S-属性文法例属性文法例1 1产生式产生式属性计算规则属性计算规则属性定义属性定义E PE PE.valE.val= = P.valP.valEvalEval :integer

30、:integerPvalPval :integer :integernvalnval :integer :integer E EE E1 1 + P + P E.valE.val = E = E1 1.val + .val + P.valP.valEE E E1 1 - P - PE.valE.val = E = E1 1.val - .val - P.valP.valP nP nP.valP.val= = n.valn.val 属性文法的动作文法可转换成如下：属性文法的动作文法可转换成如下： 1 EP1 EP Acc:= Acc:= RvalRval 2 EE + P2 EE + P Acc

31、:= Acc+ Acc:= Acc+ RvalRval 3 EE - P3 EE - P Acc:= Acc- Acc:= Acc- RvalRval 4 4 PnPn RvalRval:= := n_valn_val LR_S-LR_S-属性文法例属性文法例2 2产生式产生式属性计算规则属性计算规则属性定义属性定义E PE PE.valE.val = = P.valP.valEvalEval :integer :integerPvalPval :integer :integernvalnval :integer :integer E P + EE P + E1 1E.valE.val = =

32、 P.valP.val + E + E1 1.val.valEE P - E P - E1 1 E.valE.val = = P.valP.val - E - E1 1.val.valP nP nP.valP.val = = n.valn.val 属性文法的动作文法可转换成如下：属性文法的动作文法可转换成如下： 1 EP1 EP semntopsemntop:= := semtopsemtop 2 EP + E 2 EP + E semntopsemntop:= semtop-2+ := semtop-2+ semtopsemtop 3 EP + E 3 EP + E semntopsemnt

33、op:= semtop-2- := semtop-2- semtopsemtop 4 4 PnPn semntopsemntop:= := semtopsemtop L-L-属性文法属性文法是属性文法的一大子类。是属性文法的一大子类。 若若AX1X2.XiXN是属性文法是属性文法AG中的任一中的任一产生式，如果它满足下面条件产生式，如果它满足下面条件, 则称则称AG为为L-属性属性文法：文法：Xi 的继承属性只依赖于的继承属性只依赖于A的继承属性和的继承属性和X1,X2,.,X(i-1)的属性；的属性；A 的综合属性只依赖于的综合属性只依赖于A的继承属性和产生式右部符号的继承属性和产生式右部符

34、号的属性。的属性。L-属性文法的最大特点就是产生式右部符号的继属性文法的最大特点就是产生式右部符号的继承属性不依赖于其右部符号的任何属性。这一特承属性不依赖于其右部符号的任何属性。这一特点决定了有可能通过一遍扫描来求出属性值，而点决定了有可能通过一遍扫描来求出属性值，而且不需要建立属性语法树。且不需要建立属性语法树。 LL_L_LL_L_属性文法属性文法：产生式满足产生式满足LL(1)LL(1)条件的条件的L-L-属性文属性文法称之为法称之为LL_L_LL_L_属性文法。属性文法。l递归实现原理：递归实现原理：1 1 属性文法中每个属性变量对应递归程序中的一个变属性文法中每个属性变量对应递归程

35、序中的一个变量：量：X.aX.a转换成转换成X_aX_a的形式。的形式。2 2 对于每个对于每个V VT T定义一个过程定义一个过程terminalterminal，其调用形式是，其调用形式是terminal(a,a_sterminal(a,a_s) )。 3 3 对于每个对于每个V VN N，定义一个带参数的过程，定义一个带参数的过程A(A_s1,A_s2,A(A_s1,A_s2,A_snA_sn),),其中其中A_siA_si都是引用型参数，将在都是引用型参数，将在别处调用时分别得到相应的综合属性值。别处调用时分别得到相应的综合属性值。4 4 把综合属性计算部分改变为语句形式写在递归子程把

36、综合属性计算部分改变为语句形式写在递归子程序的末尾。序的末尾。 实现例子实现例子： 产生式：产生式：A AaBAbaBAb 属性定义：属性定义：A h s B h1 h2 s， a s， b sl 属性计算规则：属性计算规则： B.h1 = a.s B.h2 = f(A.h) A1.h = g(A.h ,B.s) A.s = u(B.s,A1.s,b.s) procedure procedure A(inA(in A_h,outA_h,out A_sA_s) ) varvar a_sa_s, B_h1, B_h2, , B_h1, B_h2, B_s,A_hB_s,A_h, , A_sA_s,

37、 , b_sb_s; terminal(a,a_sterminal(a,a_s);); B_h1:= B_h1:=a_sa_s; ; B_h2:= B_h2:=f(A_hf(A_h);); B(B_h1,B_h2,B_s); B(B_h1,B_h2,B_s); A_hA_h:=:=g(A_h,B_sg(A_h,B_s);); A(A1_h,A1_s); A(A1_h,A1_s); terminal(b,b_sterminal(b,b_s);); A_sA_s:=u(B_s,A1_s,b_s); :=u(B_s,A1_s,b_s); 实现思想：实现思想：- 根据输入串构造分析树；根据输入串构造分

38、析树；- 按确定顺序访问结点并计算其属性值；按确定顺序访问结点并计算其属性值；- 每个内结点对应一条属性计算规则。假设当前结点为每个内结点对应一条属性计算规则。假设当前结点为N(对应对应X0),并且对应并且对应X0的如下一条规则：的如下一条规则：- X0X0X1X2X1X2XnXn / X1.h = ; / X1.h = ; Xn.hXn.h=; =; X0.s = / X0.s = /- 同时假设已算出的同时假设已算出的X0X0的继承属性值的继承属性值h,h,则访问结点函数则访问结点函数visit(N,hvisit(N,h) )将以将以h h作为作为N N结点的继承属性，通过访问其子结点的继

39、承属性，通过访问其子树的所有结点，最终计算出树的所有结点，最终计算出N N结点的综合属性值结点的综合属性值X0.s X0.s Visit(N，h)：1 把把h送入送入X0.h空间中；空间中；2 j:=1;3 计算计算N的第的第j个儿子结点的继承属性个儿子结点的继承属性Xj.h值：值：visit(child(N,j),Xj.h);5 j:=j+16 若若j n则则重复重复3-6，否则，否则7 计算结点计算结点N的综合属性的综合属性X0.s的值的值 n是是X0对应产生式右部符号的个数对应产生式右部符号的个数lp1 ABC / B.h=f(A.h); C.h=g(B.s); A.s= r(C.s)lp2 AaA1 / A1.h = u(a.s) ;A.s= q(A.h,A1.s)lfunction A(N,h) var A.h ,B.h, B.s, C.h, C.slcase production_numb(N) of l p1:A.h := h ;lB.s := B(child(N,1),f(A.h);lC.s := C(child(N,2),g(B.s);lA.s := r(C.s)lreturn A.sl p2: A.h := h;la.s := synth_val(child(N,1);lA1.s