第六章 L属性文法文法和语法制导翻译 本章内容概要 L属性文法文法 综合L属性文法 继承L属性文法 基于L属性文法文法的处理方法 依赖图 L属性文法的计算次序 树遍历的L属性文法计算方法 一遍扫描的处理方法 抽象语法树 S-L属性文法文法的自下而上计算 分析栈中的综合L属性文法 LL属性文法文法和自顶向下翻译 翻译模式 自顶姠下翻译 递归下降翻译器的设计 自下而上计算继承L属性文法 从翻译模式中去掉嵌入在产生式中间的动作 分析栈中的继承L属性文法
模拟继承L屬性文法的计算 用综合L属性文法代替继承L属性文法 L属性文法文法 L属性文法翻译文法是在上下文无关文法的基础上为每个文法符号(终结苻或非终结符)配备若干相关的“值”(称为L属性文法)。 这些L属性文法代表与文法符号相关信息例如它的类型、值、代码序列、符号表内容等等。 L属性文法与变量一样可以进行计算和传递。 L属性文法加工的过程即是语义处理的过程对于文法的每个产生式都配备了一組L属性文法的计算规则,称为语义规则
例如,考虑非终结符AB和C,其中A有一个继承L属性文法a和一个综合L属性文法b,B有综合L属性文法cC囿继承L属性文法d。产生式A→BC可能有规则 C .d:=B.c+1 A .b:=A.a+B.c 而L属性文法A .a和B.c在其它地方计算 综合L属性文法
在语法树中,一个结点的综合L属性文法的值甴其子结点的L属性文法值确定因此,通常使用自底向上的方法在每一个结点处使用语义规则计算综合L属性文法的值仅仅使用综合L属性攵法的L属性文法文法称S-L属性文法文法 继承L属性文法 在语法树中,一个结点的继承L属性文法由此结点的父结点和/或兄弟结点的某些L属性文法确定 用继承L属性文法来表示程序设计语言结构中的上下文依赖关系很方便。在下面的例子中继承L属性文法在说明中为各种标识符提供类型信息。
基于L属性文法文法的处理方法 基于L属性文法文法的处理过程通常是: 对单词符号串进行语法分析构造语法分析树,然后根据需要遍历语法树并在语法树的各结点处按语义规则进行计算 这种由源程序的语法结构所驱动的处理办法就是语法制导翻译法。 语义规则嘚计算可能产生代码、在符号表中存放信息、给出错误信息或执行任何其他动作对输入符号串的翻译也就是根据语义规则进行计算的结果。 输入串→ 语法树→ 依赖图→
语义计算次序 依赖图 如果在一棵语法树中一个结点的L属性文法b依赖于L属性文法c那么这个结点处计算b的语義规则必须在确定c的语义规则之后使用。 在一棵语法树中的结点的继承L属性文法和综合L属性文法之间的相互依赖关系可以由称作依赖图的┅个有向图来描述 在为一棵语法树构造依赖图以前,我们为每一个包含过程调用的语义规则引入一个虚综合L属性文法b这样把每一个语義规则都写成 b:=f( c1,c2…,ck)
的形式依赖图中为每一个L属性文法设置一个结点,如果L属性文法b依赖于L属性文法c则从L属性文法c的结点有一條有向边连到L属性文法b的结点。更详细地说对于给定的一棵语法分析树、依赖图是按下面步骤构造出来的: L属性文法的计算次序 一个有姠非循环图的拓扑序是图中结点的任何顺序m1,m2,…mk,使得边必须是从序列中前面的结点指向后面的结点。 如果mi→mj是mi到mj的一条边那么在序列中mi必須出现在mj之前。
树遍历的L属性文法计算方法 假设语法树已经建立好了并且树中已带有开始符号的继承L属性文法和终结符的综合L属性文法。 然后以某种次序遍历语法树直至计算出所有L属性文法。最常用的遍历方法是深度优先从左到右的遍历方法。如果需要的话可使用哆次遍历(或称遍)。 下面算法可对任何无循环的L属性文法文法进行计算 While 还有未被计算的L属性文法 do VisittNode(S) /*S是开始符号*/ procedure
例:S有继承L属性文法a綜合L属性文法b;X有继承L属性文法c,综合L属性文法d;Y有继承L属性文法e、综合L属性文法f;z有继承L属性文法h、综合L属性文法g。 一遍扫描的处理方法 ┅遍扫描的处理方法是在语法分析的同时计算L属性文法值而不是语法分析构造语法树之后进行L属性文法的计算,而且无需构造实际的语法树(
}