属性文法和语法制导翻译授课：胡静语义分析面向语法的定义所处位置分析技术 LL分析方法 计算最左推导 自顶向下的构造推导 LL的分析表指出要对最左边的非终结符进行扩展时，所选的产 生式。 LR分析方法 计算最右推导 自底向上的构造推导 使用LR的状态集合和符号栈 LR分析表指出针对每一个状态，采用何种动作（移进/归约）， 并且下一个转入的状态是什么。 我们可以使用这些技术来构造 ASTAST 复习 推导：使用的产生式的序列 S E + S 1 + S 1 + E 1 + 2 分析树：描述推导的图 并不能表示产生式使用的顺序 抽象语法树 (AST)：从分析树中去掉了那些不必要的信息。潜在的AST构造 LL/LR分析技术都潜在的构造出了AST 分析树在推导过程中可以得到 LL parsing: 应用产生式的序列潜在的描述了AST LR parsing：应用归约的序列潜在的描述了AST 我们希望从分析过程中明确的创建AST： 在分析器中添加一定的代码来明确的创建ASTAST 的构造 LL分析: 对非终结符进行扩展 Example:LR分析中AST的构造问题 代码的结构混乱：进行语法分析的代码和构造AST的 代码混在一起 语法分析器的生成器： 产生的语法分析器需要包含AST的构造代码 如何使用语法分析器的自动生成器构造不同的AST数 据结构？ 我们需要在分析阶段同时的进行其他的动作。 比如，语义检查Syntax-Directed Definition 解决方法: syntax-directed definition 扩展每个文法的产生式，使得每个产生式都和语义动 作（代码）相关联： S E+S action 语法分析器的生成器将这些代码加入到生成的语法分 析器中。 当使用产生式进行归约时，对应的动作就会被执行。语义动作 动作：用程序设计语言编写的代码 和语法分析器的生成器的程序设计语言相同 例如： Yacc = actions written in C CUP = actions written in Java 动作需要访问语法分析栈！ 语法分析器的生成器将状态栈进行扩展，用那些用户定义的结构 （分析树）去替换原先的符号 动作代码应该可以引用状态 需要一套命名机制命名机制 我们需要对那些在语义动作代码中可能用到的文法的 符号进行命名。 需要分别引用出现在不同地方的同一个非终结符号 E E1 + E2 需要对左边/右边的符号进行区别 E0 E + E命名机制：Yacc Yacc: 使用关键字: $1引用右边的第一个符号，$2引用右边的 第二个符号，以此类推 关键字$引用左边的非终结符 Yacc的例子 expr := expr PLUS expr $ = $1 + $3; 构造 AST 使用语义动作构造AST AST在分析过程中自底向上的构造例子 分析栈保存了每个非终结符的值 可以使用syntax-directed定义在语法分析的时候进行 语义检查 例如，类型检查 好处：有效率 一个简单的编译过程可以完成多个任务 坏处：代码结构混乱 将语法分析和语义检查过程混在一起 当AST结构改变的时候进行检查 只能是自底向上的过程中类型声明的例子值的传递 当创建AST的时候，也要把值属性进行传递。另一个例子值的传递 值要两个方向传递：自顶向下和自底向上构造方法 从语义检查阶段可以单独的构造AST 反复检查AST并且进行语义检查 (或其他动作)只有当 树被建立起来并且他的结构是稳定的时候才能做。 这个过程有更多的灵活性，不容易出现错误属性文法属性文法 虽然形式语义学的研究已经取得了许多重大进展，但目前在实 际应用中比较流行的语义描述和语义处理的方法主要还是属性 文法和语法制导翻译。 本章研究内容： 上下文无关文法所产生的语言的翻译。 把属性附加到代表语法结构的文法符号上，可以将语义信息和程 序设计语言的结构联系起来。 属性的值是用与文法产生式相关联的“语义规则”来计算的。 涉及的概念 语法制导定义：关于语言翻译的高层次规格说明，隐蔽了具体实 现细节，不显式的说明翻译发生的顺序(属性文法) 翻译模式：指明了语义规则的计算顺序，说明实现细节。语法制导翻译在编译器中的位置 语义规则的计算完成的工作 生成代码 在符号表中保存信息 发出错误信息 对输入符号串翻译的过程就是对语义规则求值的过程 L-属性：包含了所有不必显式构造分析树即可完成的 翻译输入符号串分析树依赖图语义规格的 计算顺序属性文法 是在上下文无关文法的基础上，为每个文法符号（终 结符或非终结符）配备若干相关的“值”。 属性代表与文法符号相关的信息，如类型、值、代码 序列、符号表内容 属性可以代表任何对象：字符串，数组，类型，内存 单元或其他对象 语法制导定义=文法+符号的相关属性集 属性分为两个子集：综合属性、继承属性 如果把文法符号的结点看成记录，包含若干存储信息 的域，那么属性就相当于域的名字属性文法 分析树节点上属性值由产生式的语义规则来定义 综合属性值：通过分析树中其子节点的属性值计算出来的 继承属性值：由该节点的兄弟节点及父节点的属性值计算出来的 依赖图 语义规则建立了属性间的依赖关系，这种关系用图来表示就是依 赖图 依赖图表示了语义规则的计算顺序 注释分析数 每个节点都有属性值的分析树叫做注释分析树 计算节点属性的过程称为注释或者装饰分析树属性文法 在语法制导定义中，每个产生式A都有一个形如 b=f(c1,c2,.,ck)的语义规则语义规则 集合与之相关联联，其中f是函数，并 且满满足下面条件之一 b是A的一个综综合属性，且c1,c2,.,ck是该产该产 生式文法符号的属性 b是产产生式右部某个文法符号的一个继继承属性，且c1,c2,.,ck也是 该产该产 生式文法符号的属性 在这这两种情况下，我们说们说 属性b依赖赖于c1,c2,.,ck 。 特别别要强调调的是： 终结终结 符只有综综合属性，它们们由词词法分析器提供； 非终结终结 符既可有综综合属性也可有继继承属性，文法开始符号的所 有继继承属性作为为属性计计算前的初始值值。关于属性文法的说明 通常，这这种函数的被写为为表达式。 其他的语义规则语义规则 被写为过为过 程调调用或者程序段定义产义产 生式 左部非终结终结 符的虚综综合属性值值 一般说说来，对对于出现现在产产生式右边边的继继承属性和出现现在产产生 式左边边的综综合属性都必须须提供一个计计算规则规则 。 属性计计算规则规则 中只能使用相应产应产 生式中的文法符号的属性， 这这有助于在产产生式范围围内“封装”属性的依赖赖性。 出现现在产产生式左边边的继继承属性和出现现在产产生式右部的综综合属 性不由所给产给产 生式的属性计计算规则进规则进 行计计算，它们们由其他产产 生式的属性规则计规则计 算或由属性计计算器的参数提供。继承属性和综合属性的计算举例 对于产生式ABC来讲讲 直观观上来讲讲，这这个产产生式可以计计算A的综综合属性、B 和C的继继承属性。 那么对对于A的继继承属性，可能需要根据某个类类似于 XA的产产生式求的。 同样样的B和C的综综合属性可能需要根据某个类类似于 B，以及C 的产产生式求的。属性文法举例产生式语义规则 LEnprint(E.val)EE1 + TE.val := E1.val + T.valETE.val := T.valTT1 * FT.val := T1.val * F.val TFT.val := F.valF(E)F.val := E.valFdigitF.val := digit.lexval综合属性 S属性定义 在语法树中，一个结点的综合属性的值由其子结点的 属性值决定。 仅使用综合属性的属性文法称为S-属性定义 S属性定义的分析树的分析方法自底向上的在每个 节点用语义规则来计算综合属性值。综合属性举例Ln E产生式语义规则 LEnprint(E.val) EE1 + TE.val := E1.val + T.val ETE.val := T.val TT1 * FT.val := T1.val * F.val TFT.val := F.val F(E)F.val := E.val FdigitF.val := digit.lexval3*5+4ET+TF*TFFdigitdigitdigit.lexval=3.val=5.val=4.val=3.val=3.val=15.val=4.val=4.val=15.val=19.val=5继承属性 在语法树中，一个结点的继承属性由此结点的父结点 和/或兄弟结点的某些属性确定。 继承属性在程序设计语言中的作用 表示程序设计语言上下文结构的依赖性 对于赋值号，其左边和右边的标识符在操作的时候需要 提供的属性不同，这时候就要跟踪标识符的继承属性。 如果在赋值号左边，则需要地址，右边则需要值。 虽然我们总是可以只用综合属性来改写语法制导定义 ，但是使用带有继承属性的属性文法有时更为自然。继承属性的例子DLT产生式语义规则DTLL.in := T.typeTintT.type := integerTrealT.type := realLL1 , idL1.in := L.in addtype(id.entry, L.in)Lidaddtype(id.entry, L.in)real id1,id2,id3realid3,L.in=real.in=real.type=realid2,L.in=realid1语法制导翻译 基于属性文法的处理过程通常是： 对符号串进行语法分析， 构造语法分析树 根据需要遍历语法树并在语法树的各结点处按语义规 则进行计算。 这种由源程序的语法结构驱动的处理办法就是语法制 导翻译法。 在某些情况下，在进行语法分析的同时完成语义规则 的计算而无须明显地构造语法树或构造属性之间的依 赖图。依赖图 依赖图是有向图 表示了分析树中各节点属性间的依赖关系。其中属性包括继承属 性和综合属性 表示了节点属性的计算先后顺序。如果分析树中某个节点的属性 b依赖于属性c，那么在该节点处b的语义规则必须在c的语义规则 之后计算。 依赖图的构造方法 为每个包括过程调用的语义规则引入一个虚综合属性b，把每条 语义规则都变成b=f(c1,c2,.,ck)的形式 依赖图赖图 的每个结结点表示一个属性 边边表示属性间间的依赖赖关系。如果属性b依赖赖于属性c，那么从c到 b就有一条有向边边依赖图举例DLTrealid3,L.in=real.in=real.type=realid2,L.in=realid1DLTrealid3,Lid2,Lid1typeinyinyinyentryentryentry12345678910如果一属性文法不存在属性 之间的循环依赖关系，那么 称该文法为良定义的产生式语义规则 DTLL.in := T.type TintT.type := integer TrealT.type := real LL1 , idL1.in := L.in addtype(id.entry, L.in) Lidaddtype(id.entry, L.in)属性的计算顺序 无环有向图的拓扑排序 无环有向图中节点m1,m2,mk的拓扑排序是：若 mimj是从