chpt7-2属性文法和语法制导

7 2属性文法和语法制导翻译 程序设计语言的语义静态语义是对程序约束的描述 这些约束无法通过抽象语法规则来妥善地描述 实质上就是语法规则的良形式条件 它可以分为类型规则和作用域 可见性规则两大类如 类型相容性变量先声明后引用名称相关要求动态语义程序单位描述的计算编译程序的语义处理工作静态语义审查执行动态语义 计算 生成代码 语义形式化语义建模 形式语义学 如指称语义学 公理语义学 操作语义学等 的研究已取得了许多重大的进展文法模型 属性文法命令式或操作式模型 操作语义学应用式模型 指称语义学公理式模型 公理语义学 属性文法和语法制导翻译 在实际应用中比较流行的语义描述和语义处理的方法1属性文法概述2基于属性文法的处理方法3S 属性文法的自下而上计算L 属性文法L 属性文法和自顶向下翻译自下而上的分析中实现L 属性文法 7 2 1属性文法概述 表达式文法E T T TorTT n bE T1 T2 T1 type intT2 type T1 typeE type int E T1orT2 T1 type boolT2 type T1 typeE type bool T n T type int T b T type bool input emptystring inputline line n exp n printf t 10g n 1 error n exp NUM 1 exp exp 1 3 exp exp 1 3 exp exp 1 3 exp exp 1 3 exp precNEG 2 exp exp pow 1 3 exp 2 属性文法 属性文法 attributegrammar 是一个三元组 A G V F 其中G 是一个上下文无关文法V 有穷的属性集 每个属性与文法的一个终结符或非终结符相连 这些属性代表与文法符号相关信息 如它的类型 值 代码序列 符号表内容等等 属性与变量一样 可以进行计算和传递 属性加工的过程即是语义处理的过程 F 关于属性的属性断言或一组属性的计算规则 称为语义规则 断言或语义规则与一个产生式相联 引用该产生式左端或右端的终结符或非终结符相联的属性 属性通常分为两类 综合属性和继承属性 简单地说 综合属性用于 自下而上 传递信息 而继承属性用于 自上而下 传递信息 属性文法中 对应于每个产生式A 都有一套与之相关联的语义规则 每条规则的形式为b f c1 c2 ck f是一个函数 b和c1 c2 ck是该产生式文法符号的属性 并且 1 如果b是A的一个属性 c1 c2 ck是产生式右部文法符号的属性或A的其他属性 则称b是A的综合属性 2 如果b是产生式右部某个文法符号X的一个属性 并且c1 c2 ck是A或产生式右边任何文法符号的属性 则称b是文法符号X的继承属性在两种情况下 我们都说属性b依赖于属性c1 c2 ck 一般 对出现在产生式左边的继承属性和出现在产生式右边的综合属性都必须提供一个计算规则 属性计算规则中只能使用相应产生式中的文法符号的属性 然而 出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给定的产生式的属性计算规则进行计算 它们由其它产生式的属性规则计算或者由属性计算器的参数提供 A X1X2 XnA的综合属性S A 计算公式S A f I X1 I Xn Xj的继承属性T Xj 计算公式T Xj f I A I Xn 1 非终结符既可有综合属性也可有继承属性 但文法开始符号没有继承属性 2 终结符只有综合属性 它们由词法程序提供 如非终结符A B和C 其中A有一个继承属性a和一个综合属性b B有综合属性c C有继承属性d 对产生式A BC可能有语义规则C d B c 1和A b A a B c而属性A a和B c是在其他地方计算的 语义规则所描述的工作可以包括属性计算 静态语义检查 符号表操作 代码 中间 生成等等 有些语义规则可能产生副作用 如产生代码 也可能是个函数 通常把这样的语义规则写成过程调用或过程段 一个属性文法和综合属性的例子例 1非终结符E T及F都有一个综合属性val 符号digit有一个综合属性 它的值由词法分析器提供 与产生式L E对应的语义规则仅仅是打印由E产生的算术表达式的值的一个过程 我们可认为这条规则定义了L的一个虚属性 某些非终结符加上标是为了区分一个产生式中同一非终结符多次出现 语义规则 LE EE1 T ET TT1 F TF F E Fdigit Print E 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 4 则语义动作打印数值19 L E val 19 E val 15 T val 4 T val 15 F val 4 T val 3 F val 3 F val 5 digit lexval 4 digit lexval 5 digit lexval 3 3 5 4的带注释的分析树 继承属性 一个结点的继承属性值是由此结点的父结点和 或兄弟结点的某些属性来决定的 例2继承属性L in 生产式 语义规则 D TL T int T real L L1 id L id L in T type T type integer T type real L1 in L in addtype id entry L in addtype id entry L in D L in real L in real L in real T type real real id2 id1 id3 Realid1 id2 id3每个L结点都带有继承属性的语法树 例3 P DSD varV D S V e S V x y z现在使用两个属性 name和dl 每当一个新的变量声明时 就把它的name属性附给它 name属性是综合属性 将所声明的变量都放到一个变量名字清单中 用语义函数addlist实现 用属性dl收集声明块中声明的所有变量 然后这个dl属性又作为继承属性传到后面的语句部分 每个语句用到的变量都要进行审查 看它是否在变量名字清单中P DS S dl D dl D1 varV D2 D1 dl addlist V name D2 dl D1 dl NULL S1 V e S2 check V name S1 dl S2 dl S1 dl V x y z V name x V name y V name z varx vary y e PDdl x y Sdl x y varV Ddl y V e SxvarV Ddl y y 例4 定义二进制数的CFG 1 N S S 2 S SB 3 S B 4 B 0 5 B 1 1 N S S 2 S SB 3 S B 4 B 0 5 B 1非终结符N表示整个二进制数的数值 综合属性v附加在N上 Nv非终结符B表示一个二进制数字 它有自己的值v 但该值分配给N的值与它的位置有关 是与2成比例 比例因子f是从S继承的属性 所以 Bvf非终结符S表示一个二进制数字串 它也有值 但该值与串的位置 f 有关 与串的长度l有关 Sfvl 构造数值的属性断言可以如下 N v S f1 v1 l1 S f2 v2 l2 v v1 v2 f1 1 f2 2 l2 S f v l S f1 v1 l1B f2 v2 f1 2f f2 f v v1 v2 l l1 1 B f v l 1 B f v 0 v 0 1 v f 1 N S S 2 S SB 3 S B 4 B 0 5 B 1 文法定义的二进制数的形式为dmdm 1 d1d0 pkpk 1 p1p0 其中dmdm 1 d1d0和pkpk 1 p1p0都是二进制数字 这种形式的二进制数的数值计算公式是 dm 2m dm 1 2m 1 d1 21 d0 pk 2 1 pk 1 2 2 p1 2 k p0 2 k 1 dm 2m dm 1 2m 1 d1 21 d0 pk 2k pk 1 2 k 1 p1 21 p0 2k 1 为了计算小数部分的值 需要知道二进制数字的个数 也即S定义的数串的长度 因此对非终结符S附加两个属性val和length N S1 S2 N val S1 val 2 S2 len S2 val S S1B S val 2 S1 val B val S len S1 len 1 S B S val B val S len 1 B 0 B val 0 B 1 B val 1 N v S i1 l1 S i2 l2 v i1 2 l2 i2 S i l S i1 l1B i2 i 2i1 i2 l l1 1 B i l 1 B i 0 i 0 1 i 1 7 2 2基于属性文法的处理过程 从概念上讲 基于属性文法的处理过程即语法制导翻译通常是这样的 对单词符号串进行语法分析 构造语法分析树 然后根据需要构造属性依赖图 遍历语法树并在语法树的各结点处按语义规则进行计算输入符号串 分析树 属性依赖图 语义规则的计算顺序 依赖图 由称为依赖图的一个有向图描述分析树中的继承属性和属性中间的相互依赖关系 依赖图的构造算法 for分析树中每一个结点ndofor结点的文法符号的每一个属性ado为a在依赖图中建立一个结点 for分析树中每一个结点ndofor结点n所用产生式对应的每一个语义规则b f c1 c2 ck dofori 1tokdo从ci结点到b结点构造一条有向边 依赖图 例2 例2继承属性L in 生产式 语义规则 D TL T int T real L L1 id L id L in T type T type integer T type real L1 in L in addtype id entry L in addtype id entry L in 例2Realid1 id2 id3分析树的依赖图 图中的结点用数字表示 5 6 7 8 9 10 T 4 D L L L Real type in in in 3entry 2entry entry id3 id2 id1 1 例2Realid1 id2 id3分析树的依赖图的说明 依赖图中的结点由数字来标识 从代表T type的结点4有一条有向边连到代表L in的结点5 因为根据产生式D TL的语义规则L in T type 可知L in依赖于T type 根据产生式L L1 id的语义规则L1 in L in 可知L1 in依赖于L in 所以有两条向下的有向边分别进入结点7和9 每一个与L产生式有关的语义规则addtype id Entry L in 都产生一个虚属性 结点6 8和10都是为这些虚属性构造的 良定义的属性文法 很显然 一条求值规则只有在其各变元值均已求得的情况下才可以使用 但有时候可能会出现一个属性对另一个属性的循环依赖关系 如 p c1 c2都是属性 若有下求值规则 p f1 c1 c1 f2 c2 c2 f3 p 时 就无法对p求值 如果一属性文法不存在属性之间的循环依赖关系 那么称该文法为良定义的 为了设计编译程序 我们只处理良定义的属性文法 属性的计算顺序 一个有向非循环图的拓扑序是图中结点的任何顺序m1 m2 mk 使得边必须是从序列中前面的结点指向后面的结点 也就是说 如果mi mj是mi到mj的一条边 那么在序列中mi必须出现在mj之前 一个依赖图的任何拓扑排序都给出一个分析树中结点的语义规则计算的有效顺序 这就是说 在拓扑排序中 在一个结点 语义规则b f c1 c2 ck 中的属性c1 c2 ck在计算b以前都是可用的 属性文法说明的翻译是很精确的 最基本的文法用于建立输入符号串的分析树 依赖图如上面讨论的那样建立 从依赖图的拓扑排序中 我们可以得到计算语义规则的顺序 用这个顺序来计算语义规则就得到输入符号串的翻译 再考查例2Realid1 id2 id3分析树的依赖图每一条边都是从序号较低的结点指向序号较高的结点 历此 依赖图的一个拓扑排序可以从低序号到高序号顺序写出 从这个拓扑排序中我们可以得到下列程序 用an来代表依赖图中与序号n的结点有关的属性 a4 reala5 a4addtype id3 entry a5 a7 a5 addtype id2 entry a7 a9 a7addtype id1 entry a9 这些语义规则的计算将把real类型填入到每个标识符对应的符号表项中 属性计算方法 树遍历的属性计算方法设语法树已经建立起了 并且树中已带有开始符号的继承属性和终结符的综合属性 然后以某种次序遍历语法树 直至计算出所有属性 最常用的遍历方法是深度优先 从左到右的遍历方法 如果需要的话 可使用多次遍历 或称遍 一遍扫描的处理方法与树遍历的属性计算文法不同 一遍扫描的处理方法是在语法分析的同时计算属性值 而不是语法分析构造语法树之后进行属性的计算 而且并无需构造实际的语法树 因为一遍扫描的处理方法与语法分析器的相互作用 它与下面两个因素密切相关 1 所采用的语法分析方法 2 属性的计算次序 构造数值的属性断言可以如下 N v S f1 v1 l1 S f2 v2 l2 v v1 v2 f1 1 f2 2 l2 S f v l S f1 v1 l1B f2 v2 f1 2f f2 f v v1 v2 l l1 1 B f v l 1 B f v 0 v 0 1 v f 在某些情况下可用一遍扫描实现属性文法的语义规则计算 也就是说在语法分析的同时完成语义规则的计算 无须明显地构造语法树或构造属性之间的依赖图 因为单遍实现对于编译效率非常重要具体的实现希望在单遍扫描中完成翻译研究怎样实现这种翻译器 一个一般的属性文法的翻译器可能是很难建立的 然而有一大类属性文法的翻译器是很容易建立的s 属性适用于自底向上的计算L 属性适用于自顶向下的计算 也可用于自底向上 7 2 3S 属性文法的自下而上计算 S 属性文法 它只含有综合属性 综合属性可以在分析输入符号串的同时自下而上的来计算 分析器可以保存与栈中文法符号有关的综合属性值 每当进行归约时 新的属性值就由栈中正在归约的产生式右边符号的属性值来计算 S 属性文法的翻译器通常可借助于LR分析器实现 在S 属性文法的基础上 LR分析器可以改造为一个翻译器 在对输入串进行语法分析的同时对属性进行计算 产生式语义规则 1 1 l 1 1 F F i i LR分析器可以改造为一个翻译器增加语义栈 在对输入串进行语法分析的同时对属性进行计算 分析器模型 总控程序 output Input S1 Xm S1 X1 S0 栈 状态 符号 ACTION GOTO LR分析表 产生式表 Vm V1 语义 S1 S0 Vm V1 的分析和计值过程 步骤动作状态栈语义栈 值栈 符号栈余留输入串 3 2 3 接受 BOTTOM UP语义处理是作类型检查 对二目运算符的运算对象进行类型匹配审查 LR分析 增加语义栈归约时进行语义动作 例5G E 1 E T T 2 E TorT 3 T n 4 T b E T1 T2 ifT1 type intandT2 type intthenE type intelseerror E T1orT2 ifT1 type boolandT2 type boolthenE type boolelseerror T n T type int T b T type bool G E 1 E T T 2 E TorT 3 T n 4 T b G E 1 E T T 2 E TorT 3 T n 4 T b 7 2 4L 属性文法 一个属性文法称为L 属性文法 如果对于每个产生式A X1X2 Xn 其每个语义规则中的每个属性或者是综合属性 或者是Xj 1 j n 的一个继承属性且这个继承属性仅依赖于 1 产生式Xj在左边符号X1 X2 Xj 1的属性 2 A的继承属性 S 属性文法一定是L 属性文法 因为 1 2 限制只用于继承属性 L 属性文法例 1非终结符E T及F都有一个综合属性val 符号digit有一个综合属性 它的值由词法分析器提供 与产生式L E对应的语义规则仅仅是打印由E产生的算术表达式的值的一个过程 我们可认为这条规则定义了L的一个虚属性 某些非终结符加上标是为了区分一个产生式中同一非终结符多次出现 语义规则 LE EE1 T ET TT1 F TF F E Fdigit Print E 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 产生式 L 属性文法 一个结点的继承属性值依赖于父结点的继承属性和 或左部兄弟结点的某些属性来决定的 例2继承属性L in 生产式 语义规则 D TL T int T real L L1 id L id L in T type T type integer T type real L1 in L in addtype id entry L in addtype id entry L in L 属性文法和自顶向下翻译 L 属性文法允许一次遍历就计算出所有属性值 LL 1 这种自上而下分析文法的分析过程 从概念上说可以看成是深度优先建立语法树的过程 因此 我们可以在自上而下语法分析的同时实现L属性文法的计算 例2Realid1 id2 id3分析树的依赖图 图中的结点用数字表示 5 6 7 8 9 10 T 4 D L L L Real type in in in 3entry 2entry entry id3 id2 id1 1 例6 中缀表达式翻译成相应的后缀表达式 LR分析 E EaddopTprint addop Lexeme TT numprint num val LL 1 分析 E TRR addopTR T num 9 5 2的语法树 E T E 2 T T 9 5 E 说明语义动作的语法树 print E print 9 print 5 print print 2 消除左递归 9 5 2的语法树 R R 2 说明语义动作的语法树 R R 2 print 9 T print 5 print 2 Print 翻译模式 Translationschemes 适合语法制导翻译的另一种描述形式 翻译模式给出了使用语义规则进行计算的次序 可把某些实现细节表示出来 在翻译模式中 和文法符号相关的属性和语义规则 这里我们也称语义动作 用花括号 括起来 插入到产生式右部的合适位置上 例 中缀表达式翻译成相应的后缀表达式 E TRR addopT print addop Lexeme R1 T num print num val E TRR addopTR T num E EaddopT TT num 输入串9 5 2的语法树 ETR9 TR5 TR2 输入串9 5 2的说明动作的语法树 每个语义动作都作为相应产生式左部符号的结点的儿子 把语义动作看作是终结符 按深度优先次序执行图中的动作后 打印输出95 2 ETR9print 9 Tprint R5print 5 Tprint R2print 2 L 属性文法在自顶向下分析中的实现 带左递归的文法的翻译模式E E1 T E val E1 val T val E E1 T E val E1 val T val E T E val T val T E T val E val T num T val num val 消除左递归的同时考虑属性 构造新的翻译模式 E T R i T val R E val R s R T R1 i R i T val R1 R s R1 s R T R1 i R i T val R1 R s R1 s R R s R i T E T val E val T num T val num val 计算表达式9 5 2 E R i 9 T val 5 T val 9 R i 4 R i 6 T val 2 num val 9 num val 5 num val 2 在这个翻译模式中 每个数都是由T产生的 并且T val的值就是由属性num val给出的数的词法值 子表达式9 5中的数字9是由最左边的T生成的 但是减号和5是由根的右子结点R生成的 继承属性R i从T val得到值9 通过产生式中嵌入的下面动作 R1 i R i T val 实现计算9 5并把结果4传递到中间的R结点 类似的动作把2加到9 5的值上 在最下面的R结点处产生结果R i 6 这个结果将成为根结点处E val的值 R的综合属性s在图中没有表示出来 它用来向上复制这一结果一直到树根 对于自顶向下分析 我们假设动作是在处于相同位置上的符号被展开 匹配成功 时执行的 如图中的第二个产生式中 第一个动作 对R1 i赋值 是在T被完全展开成终结符号后执行的 第二个动作是在R1被完全展开成终结符号后执行的 正如前面我们所讨论的 一个符号的继承属性必须由出现在这个符号之前的动作来计算 产生式左边非终结符的综合属性必须在它所依赖的所有属性都计算出来以后才能计算 转换左递归翻译模式的方法推广到一般 假设翻译模式1 A A1Y A a g A1 a Y y A X A a f X x 每个文法符号都有一个综合属性 用相应的小写字母表示 g和f是任意函数消除左递归 文法转换成 A XRR YR 再考虑语义动作 翻译模式变为2A X R i f X x R A a R s R Y R1 i g R i Y y R1 R s R1 s R R s R i 翻译模式1和翻译模式2的结果是一样的 可以给出串XY1Y2两棵带注释的语法树看出来 一棵是根据翻译模式1自下而上计算属性的 一棵是根据翻译模式2自上而下计算的 A A1Y A a g A1 a Y y A X A a f X x A a g g f X x Y1 y Y2 y A a g f X x Y1 y Y2A a f X x Y1X AAYAYX A X R i f X x R Y R1 i g R i Y y R A a R s R1 R s R1 s A XRR YR AXRY1RY2R AXR i f X x Y1R i g f X x Y1 y Y2R i g g f X x Y1 y Y2 y 自下而上计算继承属性 自下而上的分析中实现L 属性文法 从翻译模式中去掉嵌入在产生式中间的动作分析栈中的继承属性用综合属性代替继承属性 从翻译模式中去掉嵌入在产生式中间的动作转换方法 引入新的非终结符N和产生式N 把嵌入在产生式中间的动作用非终结符N代替 并把这个动作放在产生式后面 例 E TRR T print R1R T print R1R T num print num val 文法变换后 接受的语言相同 E TRR TMR1R TNR1R T num print num val M print N print 目的 使所有嵌入的动作都出现在产生式的末尾 可以自下而上处理继承属性 一个属性文法称为L 属性文法 如果对于每个产生式A X1X2 Xn 其每个语义规则中的每个属性或者是综合属性 或者是Xj 1 j n 的一个继承属性且这个继承属性仅依赖于 1 产生式Xj在左边符号X1 X2 Xj 1的属性 2 A的继承属性 分析栈中的继承属性 自下而上分析器对产生式A XY的右部是通过把X和Y从分析栈中移出并用A代替它们 假设X有一个综合属性X s 按照前面所介绍的方法我们把它与X一起放在分析栈中 由于X s的值在Y以下的子树中的任何归约之前已经放在栈中 这个值可以被Y继承 也就是说 如果继承属性Y i是由复写规则Y i X s定义的 则可以在需要y i值的地方使用X s的值 在自下而上分析中计算属性值时复写规则起非常重要的作用 看下面例子 标识符的类型通过继承属性的复写规则来传递 翻译模式为 D T L in T type LT int T type integer T real T type real L L1 in L in L1 id addtype id entry L in L id addtype id entry L in 回顾例2Realid1 id2 id3分析树的依赖图 5 6 7 8 9 10 T 4 D L L L Real type in in in 3entry 2entry entry id3 id2 id1 1 例2输入串realRealid1 id2 id3的分析过程当L的右部被归约时 T恰好在这个右部的下面 输入状态 符号 使用产生式Realid1 id2 id3 id1 id2 id3 realid1 id2 id3 TT real id2 id3 Tid1 id2 id3 TLL idid2 id3 TL id3 TL id2 id3 TLL L idid3 TL TL id3 TLL L id DD TL 扩充分析栈Val i 存放文法符号X的综合属性X s D TLT int Val top integer T real Val top real L L id addtype Val top Val top 3 L id addtype Val top Val top 1 用综合属性代替继承属性 有时 改变基础文法可能避免继承属性 例如 一个Pascal的说明由一标识符序列后跟类型组成 如 m n integer 这样的说明的文法可由下面形式的产生式构成D L TT integer charL L id id因为标识符由L产生而类型不在L的子树中 我们不能仅仅使用综合属性就把类型与标识符联系起来 事实上 如果非终结符L从第一个产生式中它的右边T中继承了类型 则我们得到的属性文法就不是L 属性的 因此 基于这个属性文法的翻译工作不能在语法分析的同时进行 一个解决的方法是重新构造文法 使类型作为标识符表 identifierslist 的最后一个元素 D idLL idL TT integer char这样 类型可以通过综合属性L type进行传递 当通过L产生每个标识符时 它的类型就可以填入到符号表中 Yacc或bison作为编译程序的生成工具 利用的就是语法制导翻译方法 它使用符号 表示产生式左端的属性 n表示存取产生式右端第n个文法符号相联的属性 如例3作为Yacc的输入 可写成 P DS 2 dl 1 dl D1 varV D dl addlist 2 name 4 dl dl null S1 V e S check 1 name dl 5 dl dl V x name x y name y z name z 如果数据结构attribute定义属性name和dl 可以具体化为 typestruct attribute char name struct attribute list attribute P DS 2 list 1 list D1 varV D list add to list 2 name 4 list list null S1 V e S check 1 name list 5 list list V x name x y name y z name z Review attributegrammars Weaugmenttheconventionalgrammarwithinformationtocontrolthesemanticanalysisandtranslation Suchgrammarsarecalledattributegrammars Weaugmentagrammarbyassociatingattributeswitheachgrammarsymbolthatdescribesitsproperties Anattributehasanameandanassociatedvalue astring anumber atype amemorylocation anassignedregister generatedcode whateverinformationweneed Witheachproductioninagrammar wegivesemanticrulesoractions whichdescribehowtocomputetheattributevaluesassociatedwitheachgrammarsymbolinaproduction Theattributevalueforaparsenodemaydependoninformationfromitschildrennodesbeloworitssiblingsandparentnodeabove Review synthesizedorinheritedattributes Therearetwotypesofattributeswemightencounter synthesizedorinherited Synthesizedattributesarethoseattributesthatarepassedupaparsetree i e theleft sideattributeiscomputedfromtheright sideattributes Inheritedattributesarethosethatarepasseddownaparsetree i e theright sideattributesarederivedfromtheleft sideattributes orotherright sideattributes Theseattributesareusedforpassinginformationaboutthecontexttonodesfurtherdownthetree Review Syntax dire