精品课程《编译原理第8章语法制导与中间代码生成》PPT课件.ppt
《精品课程《编译原理第8章语法制导与中间代码生成》PPT课件.ppt》由会员分享,可在线阅读,更多相关《精品课程《编译原理第8章语法制导与中间代码生成》PPT课件.ppt(88页珍藏版)》请在三一办公上搜索。
1、8.1 属性文法,语法分析后的源程序=语义处理,静态语义是对程序约束的描述,这些约束无法通过抽象语法规则来妥善地描述,实质上就是语法规则的良形式条件,它可以分为类型规则和作用域/可见性规则两大类 动态语义 程序单位描述的计算,编译程序的语义处理工作 1 静态语义审查,即验证语法结构合法的程序是否有意义 2 生成中间代码,静态语义审查(1)类型检查。根据类型相容性要求,验证程序中执行的每个操作是否遵守语言的类型系统的过程,编译程序必须报告不符合类型系统的信息。(2)控制流检查。控制流语句必须使控制转移到合法的地方。例如,在C语言中break语句使控制跳离包括该语句的最小while、for或swi
2、tch语句。如果不存在包括它的这样的语句,则就报错。,(3)一致性检查。在很多场合要求对象只能被定义一次。例如Pascal语言规定同一标识符在一个分程序中只能被说明一次,同一case语句的标号不能相同,枚举类型的元素不能重复出现等等。(4)上下文相关性检查。比如,变量名字必须先声明后引用;(5)名字的作用域分析。各变量的作用域可能是不一样的,要通过分析明确各变量的作用域。解释执行动态语义(计算)生成代码(中间代码或目标代码),例:有文法GE:E T1+T2|T1 or T2 T num|true|false对输入串 2+6 语法树如图:,E,T,+,T,2,6,ET1.t=T2.t,T,+,2
3、,6,TT2.t=int,T1.t=int,类型检查的属性文法:E T1+T2 T1.t=int AND T2.t=intE T1 or T2 T1.t=bool AND T2.t=boolT num T.t:=intT true T.t:=boolT false T.t:=bool,属性文法,语法制导翻译,属性文法A(attribute grammar)是一个三元组:A=(G,V,F),其中 G:是一个上下文无关文法,V:有穷的属性集,每个属性与文法的一终结符或非终结符相连,F:关于属性的属性断言或谓词集.每个断言与一个产生式相联.而此断言只引用该产生式左端或右端的终结符或非终结符相联的属性
4、,例如:定义表达式的文法如下:EE+E E(E)En 给出定义表达式值的属性文法。,我们为文法符号E引进属性符号val,用E.val表示E的值,属性计算规则以赋值语句的形式给出,附在每个产生式后,并用大括号括起来。为了明确E的不同出现位置,用上角标区别。终结符n的值是词法分析程序提供的,这里用n.lex表示。下面给出属性文法:EE1+E2 E.val:=E1.val+E2.val E(E1)E.val:=E1.val En E.val:=n.lex属性文法的主要思想有两点:首先对于每个文法符号引进相关的属性符号;其次对于每个产生式写出属性值计算的规则。,属性文法:允许为每个终结符和非终结符配备
5、一些属性的文法.它既能描述程序设计语言的语法,又为其语义描述提供了手段.,属性文法由于1968年引进.后来才被用于编译程序的设计。属性有不同的类型,可以象变量一样地被赋值。赋值规则附加于语法规则之上。赋值与语法同时进行,赋值过程就是语义处理过程。在推导语法树的时候,诸属性的值被计算并通过赋值规则层层传递。有的从语法规则左边向右边传,有的从右边向左边传。语法推导树最后完成时,就得到开始符号的属性值。也就是整个程序的语义.,属性分为两种:继承属性和综合属性.inherited and synthesized(derived)attribute 继承属性的计算规则由顶向下,综合属性的计算规则由底向上
6、.,例如定义表达式值的属性文法,E.val是一个综合属性的例子:EE1+E2 E.val:=E1.val+E2.val E(E1)E.val:=E1.val En E.val:=n.lex考虑句子2(31)的求值顺序,将2(31)的语法树结点改为有附加属性的结点(这样的树称为带注释的语法树):E.val=6 E.val=2+E.val=4 n.lex=2(E.val=4)E.val=3+E.val=1 n.lex=3 n.lex=1,例8.1 一个简单台式计算器的定义 综合属性val,语 义 规 则,L E,E E1+T,E T,T T1*F,T F,F(E),F digit,Print(E.
7、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:=digit.lexval,产 生 式,3*5+6的带注释的分析树,只使用综合属性.,L,E.val=21,E.val=15,T.val=6,T.val=15,F.val=6,T.val=3,F.val=3,F.val=5,digit.lexval=6,digit.lexval=5,digit.lexval=3,+,*,3*5+6的带注释的分析树,继承属性,一个结点的继承属性值是由此结点的父结点和/或兄弟结点的某些属
8、性来决定的。例8.2 添加标识符类型的语义描述:继承属性type,产生式,语 义 规 则,D TL,T int,T real,L L1,id,L id,L.type:=T.type,T.type=integer,T.type:=real,L1.type:=L.type,addtype(id.entry,L.type),addtype(id.entry,L.type),D,L.type=real,L.type=real,L.type=real,T.type=real,real,id2,id1,id3,.,.,继承属性(续)Real id1,id2,id3的带注释的语法树,8.2 语法制导概论,属
9、性文法:描述语义规则。一个属性文法包含一个上下文无关文法和一系列语义规则,这些语义规则附在文法的每一个产生式上。语法制导翻译:在语法分析的同时,执行语义子程序:1 检查静态语义 2 翻译(生成)中间(目标)代码,基于属性文法的处理过程即语法制导翻译是这样的:对符号串进行语法分析,构造语法树,然后根据需要构造属性依赖图,遍历语法树并在语法树的各结点按语义规则进行计算。,8.2.1 计算语义规则 属性依赖图是一个有向图,用于描述分析树中的属性和属性间的互相依赖关系。对于编译程序来讲,在单遍扫描中完成语义翻译工作非常重要。,8.2.2 S-属性文法和自下而上翻译 一般的属性文法的翻译器很难建立,然而
10、L-属性文法的翻译器很容易建立。,L-属性文法的一个特例叫S-属性文法。S-属性文法是只含有综合属性的属性文法。,8.2.3 L-属性文法在自下而上分析中实现 L-属性文法允许一次遍历就计算出所以的属性值。,8.3 中间代码的形式,编译程序的总任务是把源语言的程序代码(源代码)翻译成目标语言的程序代码(目标代码)。,有些编译程序直接把源代码翻译目标代码,而有些编译程序首先把源代码翻译成一种中间语言的程序代码(中间代码),再生成目标代码。,翻译方法可分为,语法制导,非语法制导,中间代码的特点:中间代码与机器无关,编译程序易于移植。中间代码级进行优化较为容易。常见的中间代码形式有逆波兰式,三元式,
11、四元式,树等。,在产生语法制导翻译程序时,完全根据文法的产生式来生成的,有时为了达到语法制导的目的,不得不对现有产生式做一些修改,这也是语法制导方法的特点。,语法制导方法是一种形式化方法。它严格依赖于产生式结构。,中间代码,概述何谓中间代码(Intermediate code)(Intermediate representation)(Intermediate language)是源程序的一种内部表示复杂性介于源语言和目标机语言之间中间代码的作用:使编译程序的逻辑结构更加简单明确利于进行与目标机无关的优化利于在不同目标机上实现同一种语言中间代码的形式:逆波兰式、四元式、三元式、间接三元式、树,
12、中间代码的层次,中间代码按照其与高级语言和机器语言的接近程度,可以分成以下三个层次:高级:最接近高级语言,保留了大部分源语言的结构。中级:介于二者之间,与源语言和机器语言都有一定差异。低级:最接近机器语言,能够反映目标机的系统结构,因而经常依赖于目标机。,不同层次的中间代码举例,8.3.1 逆波兰式,运算符跟在所有运算对象的后面的表示法写出的式子称为后缀法或逆波兰法。,例子:中缀表示:a+b 后缀表示:ab+前缀表示:+ab,若用POS(E)表示中缀式E的逆波兰式则当E=E1T时有:,POS(E)=POS(E1)|POS(T)|其中“|”表示串的“捻接”。,例:POS(A+B*C)=POS(A
13、)|POS(B*C)|+=ABC*+POS(A*B+c)=POS(A*B)|POS(C)|+=AB*C+,处理原则:运算对象出现的顺序与原来的相同 运算符按实际运算顺序出现。运算符紧跟在运算对象的后面出现,并且没有括号。,逆波兰式的优点:转换为逆波兰式的语言中间形式后,容易实现中间代码的翻译或目标指令。,逆波兰式的生成:运算对象向左移动 运算符与栈顶比较优先数 括号处理:左括号进栈,起间隔作用;右括号与左括号匹配抵消。,波兰表达式,表达式,运算符栈,运算对象,运算符,.,进栈,.,.,退栈,a*(b+c/d)#,.,.,#,例子:a*(b+c/d)abcd/+*的推导,*(b+c/d)#,.,
14、.,#,a,(b+c/d)#,.,.,*#,a,b+c/d)#,.,.,(*#,a,+c/d)#,.,.,(*#,ab,c/d)#,.,.,+(*#,ab,/d)#,.,.,+(*#,abc,d)#,.,.,/+(*#,abc,)#,.,.,/+(*#,abcd,)#,.,.,+(*#,abcd/,)#,.,.,(*#,abcd/+,#,.,.,*#,abcd/+,#,.,.,#,abcd/+*,.,.,.,abcd/+*,动画演示,8.3.2 表达式的三元式和树,一、三元式 三元式的一般形式:i:(,OPR1,OPR2)i是三元式编号,不同三元式不能有相同编号。是运算符部分。OPR1和OPR
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译原理第8章语法制导与中间代码生成 精品课程 编译 原理 语法 制导 中间 代码 生成 PPT 课件
![提示](https://www.31ppt.com/images/bang_tan.gif)
链接地址:https://www.31ppt.com/p-6012949.html