新版编译原理课件.ppt

《新版编译原理课件.ppt》由会员分享，可在线阅读，更多相关《新版编译原理课件.ppt（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章 静态语义分析本章注重讨论 静态语义的分析方法，过程程序设计语言中典型结构的翻译方法。第2章第3章1。第四章 静态语义分析 语法制导翻译是处理语义的基本方法，它以语法分析为基础，在语法分析得到语言结构的结果时，处理此结构对应的语义，如计算表达式的值、生成中间代码等。主要内容包括：语法制导翻译的基本概念 中间代码简介 符号表简介 典型声明语句与可执行语句的翻译2。4.1 语法制导翻译简介4.1.1 语法与语义语法是指语言的结构、即语言的“样子”；语义是指附着于语言结构上的实际含意，即语言的“意义”。语法与语义的关系语义不能离开语法独立存在；语法与语义之间没有明确的界线；语义远比语法复杂；同

2、一语言结构可包含多种含意，不同语言结构可表示相同含意。3。4.1.1 语法与语义（续1）例1：程序设计语言中的分情况结构：1Linux Bash Script case condition in case1)stat1 ;case2)stat2 ;*);esac2C/C+switch(condition)case condition1:stat1;case condition2:stat2;default:break;break;例2：“猫吃老鼠”，“老鼠吃猫”4。4.1.1 语法与语义（续2）检查结构正确的句子所表示的意思是否合法；执行规定的语义动作，如：表达式求值符号表的查询/填写中间代码

3、生成等 语义分析的方法 语法制导翻译（SyntaxDirectedTranslation）语义分析的两个作用5。4.1.2 属性与语义规则 语法制导翻译的基本思想简单地讲：以语法分析为基础，伴随语法分析的各个步骤，执行相应的语义动作。具体方法：1.将文法符号所代表的语言结构的意思，用附着于该文法符号的属性表示；2.用语义规则规定产生式所代表的语言结构之间的关系（即属性之间的关系），即用语义规则实现语义(属性)计算。语义规则的执行：在语法分析的适当时刻（如推导或归约）执行附着在对应产生式上的语义规则，以实现 对语言结构语义的处理，如计算、查填符号表、生成中间代码、发布出错信息等。6。4.1.2

4、属性与语义规则（续1）属性的抽象表示：.attr例如：E.val（值）E.type（类型）E.code（代码序列）E.place（存储空间）对文法的约定本章关注的是语法分析的基础上的语义处理，忽略语法分析。为了简单，本章的文法一般为二义文法。默认解决二义的方法是规定常规意义下的优先级和结合性。7。4.1.2 属性与语义规则（续2）定义4.1 对于产生式A，其中是由文法符号X1X2.Xn组成的序列，它的语义规则可以表示为(4.1)所示关于属性的函数f：b:=f(c1,c2,.,ck)(4.1)语义规则中的属性存在下述性质与关系：(1)称(4.1)中属性b依赖于属性c1,c2,.,ck。(2)若b

5、是A的属性，c1,c2,.,ck是中文法符号的属性，或者A的其它属性，则称b是A的综合属性。(3)若b是中某文法符号Xi的属性，c1,c2,.,ck是A的属性，或者是中其它文法符号的属性，则称b是Xi的继承属性。(4)若语义规则的形式如下述(4.2)，则可将其想像为产生式左部文法符号A的一个虚拟属性。属性之间的依赖关系，在虚拟属性上依然存在。f(c1,c2,.,ck)(4.2)属性/语义规则的定义*注释树8。EE1+E2 E.val:=+（E1.val,E2.val）E的属性.val由 E1 和 E2 的相应属性计算而来，因此我们说E的属性依赖于 E1 和 E2 的属性。从定义4.1可知：语义

6、规则 就是 属性之间的计算，属性的依赖关系 决定了 计算的先后次序。例如：4.1.2 属性与语义规则（续3）9。4.1.3 语义规则的两种形式 语法制导定义(SyntaxDirectedDefinition)用抽象的属性和运算表示的语义规则；(公式，做什么)翻译方案(TranslationScheme)用具体的属性和运算表示的语义规则。(程序段，如何做)忽略实现细节，二者作用等价。（类似：概要设计与详细设计）语义规则也被习惯上称为语义动作(Semanticaction)。10。4.1.3 语义规则的两种形式（续1）例4.1 计算中缀形式的算术表达式的后缀形式，并打印。需要的语法制导定义和翻译方

7、案。产生式LEEE1+E2Enum 语法制导定义print(E.post)E.post:=E1.post|E2.post|+;E.post:=num.lexval;翻译方案1print_post(post);postk:=+;k:=k+1;postk:=lexval;k:=k+1;产生式 翻译方案2LE EE1+E2 print(+);Enum print(lexval);虚拟属性：print(E.post)可想象为：L.p:=print(E.post)返回11。4.1.3 语义规则的两种形式（续2）例4.1，自下而上计算，LR分析。（以3+5+8为例，归约时翻译）post:翻译方案中需要考虑

8、的问题：1采用什么样的语法分析方法；2为属性分配存储空间；3考虑计算次序。语法制导定义算法 翻译方案程序实现，方法不唯一产生式翻译方案1LE print_post(post);EE1+E2 postk:=+;k:=k+1;Enum postk:=lexval;k:=k+1;产生式 翻译方案2LE EE1+E2 print(+);Enum print(lexval);3 5+8+k3 5+8+打印：打印：12。4.1.3 语义规则的两种形式（续3）属性作为分析树的注释 将属性附着在分析树对应文法符号上，形成注释分析树。产生式 语法制导定义 翻译方案LE print(E.post);EE1+E2

9、E.post:=E1.post|E2.post|+;print(+);Enum E.post:=num.lexval;print(lexval);例4.2 3+5+8的分析树和注释分析树：.post=3.post=5.post=8.post=35+.post=35+8+(print(35+8+)13。4.1.3 语义规则的两种形式（续4）注释分析树上看：综合属性是自下而上计算的 继承属性是自上而下计算的约定：除非特别提醒，本章讨论的语法制导翻译是综合属性；且采用LR分析。综合属性与继承属性的计算次序语义规则定义14。4.1.4 LR分析翻译方案的设计LR分析中的语法制导翻译实质上是对LR语法分

10、析的扩充：1.扩充LR分析器的功能：当执行归约的动作时，也执行相应产生式对应的语义动作。由于是归约时执行语义动作，因此限制语义动作仅能放在产生式右部的最右边；2.扩充分析栈：增加一个与分析栈并列的语义栈，用于存放分析栈中文法符号所对应的属性值。15。n 4.1.4 LR分析翻译方案的设计（续1）例如：EE1+E2 valtop:=valtop+valtop+2;En valtop:=lexval;对于表达式：5+3 求值当归约为左部E时，同时也得到了值8。5Etopval？+toptop3EE816。4.1.4 LR分析翻译方案的设计（续2）例4.3 3+5*8求值的语法制导翻译。翻译方案pr

11、int(valtop);valtop:=valtop+valtop+2;valtop:=valtop*valtop+2;valtop:=lexval;产生式LEEE1+E2EE1*E2En语法制导定义print(E.val)E.val:=E1.val+E2.val;E.val:=E1.val*E2.val;E.val:=n.lexval;17。4.1.4 LR分析翻译方案的设计（续3）（格局的变化）分析栈 语义栈输入 格局动作，语义动作#3+5*8#shift#n#+5*8#En，valtop:=lexval#E#3 +5*8#shift#E+#3?5*8#shift#E+n#3?*8#En，

12、valtop:=lexval#E+E#3?5 *8#shift#E+E*#3?5?8#shift#E+E*n#3?5?#En，valtop:=lexval#E+E*E#3?5?8#EE1*E2，valtop:=valtop*valtop+2;#E+E#3?40#EE1+E2，valtop:=valtop+valtop+2;#E#43#LE,print(valtop)#L#43#acc 修改教材 P14335818。4.1.5 递归下降分析翻译方案的设计 递归下降方法是用程序实现对非终结符的展开和对终结符的匹配。翻译方案的设计需要解决两个问题：1如何在递归下降子程序中嵌入语义动作：产生式右部的任

13、何位置；2如何为文法符号的属性设计存储空间：函数返回值、参数、变量等。例如函数绘图语言识别器语法制导翻译设计：1.递归子程序可以设计为函数，用于返回必要的属性值；2.适当设计子程序中的临时变量，用于保存属性值；3.将语义动作嵌入在子程序的合适位置，正确计算属性值。阅读：教材中相关例子例如：表达式 Expression19。/表达式的递归下降子程序struct ExprNode*Expression()struct ExprNode*left,*right;Token_Type token_tmp;left=Term();while(token.type=PLUS|token.type=MINU

14、S)token_tmp=token.type;MatchToken(token_tmp);right=Term();left=MakeExprNode(token_tmp,left,right);return left;20。void ForStatement()double Start,End,Step;struct ExprNode*start_ptr,*end_ptr,*step_ptr,*x_ptr,*y_ptr;MatchToken(FOR);MatchToken(T);MatchToken(FROM);start_ptr=Expression();MatchToken(TO);en

15、d_ptr=Expression();MatchToken(STEP);step_ptr=Expression();MatchToken(DRAW);MatchToken(L_BRACKET);x_ptr=Expression();MatchToken(COMMA);y_ptr=Expression();MatchToken(R_BRACKET);Start=GetExprValue(start_ptr);End=GetExprValue(end_ptr);Step=GetExprValue(step_ptr);DrawLoop(Start,End,Step,x_ptr,y_ptr);返回21。