第6章 语法制导与属性文法.ppt

第5章小结 自底向上的语法分析从给定的输入符号串w出发，自底向上地为其建立一棵语法分析树。 移进-归约分析是最基本的分析方式，分为优先法和状态法。 算符优先分析法是一种有效的方法，通过定义终结符号之间的优先关系来确定移进和归约。 LR分析法有着更宽的适应性。该方法通过构建识别规范句型活前缀的DFA来设计分析过程中的状态。可以将LR分析法分成LR(0)、SLR(1)、LR(1)、LALR(1)。 通过增加附加的信息可以解决一些二义性问题。 Yacc是LALR(1)语法分析器的自动生成工具。 第6章?语法制导翻译与属性文法 6.1 语法制导翻译概述 6.2 语法制导定义 6.3 属性计算 6.4 翻译模式 6.5 本章小结 为什么进行词法和语法分析？ 用A→α进行归约表达的是什么意思？ 看：operand+term E→E1+T E1的值+T的值的结果作为E的值——即：取来E1的值和T的值做加法运算，结果作为E的值 E.val=E1.val+T.val 6.1 语法制导翻译概述 为了提高编译程序的可移植性，一般将编译程序划分为前端和后端。 前端通常包括词法分析、语法分析、语义分析、中间代码生成、符号表的建立，以及与机器无关的中间代码优化等，它们的实现一般不依赖于具体的目标机器。 后端通常包括与机器有关的代码优化、目标代码的生成、相关的错误处理以及符号表的访问等。 6.1 语法制导翻译概述 语义分析器的主要任务是检查各个语法结构的静态语义 ，称为静态语义分析或静态检查 类型检查：操作数和操作符的类型是否相容； 控制流检查：控制流转向的目标地址是否合法； 惟一性检查：对象是否被重复定义； 关联名检查：同一名字的多次特定出现是否一致。 将静态检查和中间代码生成结合到语法分析中进行的技术称为语法制导翻译 。 6.1 语法制导翻译概述 语法制导翻译的基本思想 在进行语法分析的同时，完成相应的语义处理。也就是说，一旦语法分析器识别出一个语法结构就要立即对其进行翻译，翻译是根据语言的语义进行的，并通过调用事先为该语法结构编写的语义子程序来实现。 对文法中的每个产生式附加一个/多个语义动作(或语义子程序)，在语法分析的过程中，每当需要使用一个产生式进行推导或归约时，语法分析程序除执行相应的语法分析动作外，还要执行相应的语义动作(或调用相应的语义子程序)。 6.1 语法制导翻译概述 语义子程序的功能 指明相应产生式中各个文法符号的具体含义，并规定了使用该产生式进行分析时所应采取的语义动作(如传送或处理语义信息、查填符号表、计算值、生成中间代码等)。 语义信息的获取和加工是和语法分析同时进行的，而且这些语义信息是通过文法符号来携带和传递的。 6.1 语法制导翻译概述 一个文法符号X所携带的语义信息称为X的语义属性，简称为属性，它是根据翻译的需要设置的(对应分析树结点的数据结构)，主要用于描述语法结构的语义。 一个变量的属性有类型、层次、存储地址等 表达式的属性有类型、值等。 6.1 语法制导翻译概述 属性值的计算和产生式相关联，随着语法分析的进行，执行属性值的计算，完成语义分析和翻译的任务。 E→E1 + E2 E.val:=E1.val+E2.val 语法结构具有规定的语义 问题：如何根据被识别出的语法成分进行语义处理？ 亦即怎样将属性值的计算及翻译工作同产生式相关联？ 典型处理方法一 语法制导定义 通过将属性与文法符号关联、将语义规则与产生式关联来描述语言结构的翻译方案 对应每一个产生式编写一个语义子程序，当一个产生式获得匹配时，就调用相应的语义子程序来实现语义检查与翻译 E→E1 + T {E.val:=E1.val+T.val} T→T1 * F {T.val:=T1.val*F.val} F →digit {F.val:=digit.lexval} 适宜在完成归约的时候进行 典型处理方法二 翻译模式 通过将属性与文法符号关联，并将语义规则插入到产生式的右部来描述语言结构的翻译方案 在产生式的右部的适当位置，插入相应的语义动作，按照分析的进程，执行遇到的语义动作 D → T { L.inh := T.type } L T → int { T.type := integer } T → real { T.type := real } L → { L1.inh := L.inh }L1,id{addtype(id.entry,L.inh) } L → id{addtype(id.entry,L.inh)} 适宜在进行推导时完成 6.2 语法制导定义 语法制导定义是附带有属性和语义规则的上下文无关文法 属性是与文法符号相关联的语义信息 语义规则是与产生式相关联的语义动作 语法制导定义是基于语言结构的语义要求设计的，类似于程