《编译原理》课程书籍文献（编译原理及实践）第6章 语义分析

China-pub.com 第6章语义分析 213 下载 例6.6中的相关图)，例6.2中简单整数算术表达式的a1属性也是一样。 给定由分析程序构造的分析树或语法树，$属性文法的属性值可以通过对树进行简单的自 底向上或后序遍历来计算。这可以用以下递归的属性赋值程序来表示： procedure PostEval(T:treenode); begin for each child CofTdo PostEval (C): compute all synthesized attributes of T; end; 例6.11 用合成属性al考虑例6.2中简单算术表达式的属性文法。给定下列语法树（就像图6-5） 的结构 typedef enum Plus,Minus,Times OpKind typedef enum OpKind,ConstKind ExpKind: typedef struct streenode ind kind; treenode +lchild,+rchildi STreeNode typedef STreeNode *syntaxtree: PostEval程序可以转换成程序清单6-1中的C程序代码，进行从左向右的遍历。 程序清单6-1例6.11中后序属性赋值的C程序代码 iE（t->kind=oE postEval(t->rchild): switch (t->op) 【case p1Hs: t->val t->lchild->val t->rchild->val break: case Minus: t->val t->lchild->val-t->rchild->val; break; case Minus: t->val t->lchild->val t t->rchild->val; /end if )end postEval+/ 当然，不是所有的属性都是合成的， 定义一个属性如果不是合成的，则称作继承(inherited)属性

例6 . 6中的相关图），例6 . 2中简单整数算术表达式的v a l属性也是一样。 给定由分析程序构造的分析树或语法树， S属性文法的属性值可以通过对树进行简单的自 底向上或后序遍历来计算。这可以用以下递归的属性赋值程序来表示： p ro c e d u re PostEval (T: t re e n o d e); b e g i n for each child C of T d o PostEval (C); compute all synthesized attributes of T; e n d ; 例6 . 11 用合成属性val 考虑例6 . 2中简单算术表达式的属性文法。给定下列语法树 (就像图6 - 5 ) 的结构 typedef enum { Plus, Minus, Times } OpKind; typedef enum { OpKind, ConstKind } ExpKind; typedef struct streenode { ExpKind kind; OpKind op; struct streenode *lchild, *rchild; int val; } STreeNode; typedef STreeNode *SyntaxTree; P o s t E v a l程序可以转换成程序清单6 - 1中的C程序代码，进行从左向右的遍历。 程序清单6-1 例6 . 11中后序属性赋值的C程序代码 void postEval(SyntaxTree t) { int temp; if (t->kind = OpKind) { postEval(t->lchild); p o s t E v a l ( t - > r c h i l d ) ; switch (t->op) { case Plus: t->val = t->lchild->val + t->rchild->val; b r e a k ; case Minus: t->val = t->lchild->val - t->rchild->val; b r e a k ; case Minus: t->val = t->lchild->val * t->rchild->val; b r e a k ; } /* end switch */ } /* end if */ } /* end postEval */ 当然，不是所有的属性都是合成的。 定义 一个属性如果不是合成的，则称作继承( i n h e r i t e d )属性。 第 6章 语 义 分 析 2 1 3 下载

214 编译原理及实践 China-pub.C 下载 我们已经见过继承属性的例子，包括例6.3中的dpe属性和例6.4中的base属性。无论在分 析树中（使用这个名字的理由）从祖先到子孙的继承属性还是从同属的继承属性都有依赖。图6-8 a和b说明了继承属性依赖的两种基本种类。这两种类型的依赖在例6.7中的dype属性中都出现 过。这两种分类都为继承属性的原因在于计算继承属性的算法，同属继承通常是通过把属性值 经过祖先在同属中传递实现的。实际上，如果语法树的边只从祖先指向子孙（这样子孙不能直 接访问祖先或同属)这也是必要的。另一方面，在语法树中如果一些结构经过同属指针实现， 那么同属继承可以直接沿着同属链进行，如图6-8c的描述。 a) c) 图6-8不同种类的继承依赖 )从祖先到子孙的维承b)同属之间的维承©)通过同属指针的同属维承 现在回到继承属性赋值的算法方法。继承属性的计算可以通过对分析树或语法树的前序遍 历或前序仲序遍历的组合来进行。这可以用下面的伪代码来示意表示： procedure PreEval(T:treenode): begin for each child C ofT do compute all inherited autributes ofC: PreEval (C); end: 与合成属性不同，子孙继承属性计算的顺序是重要的，因为在子孙的属性中继承属性可能有依 赖关系。因此在前面的伪代码中T的每个子孙C的访问顺序必须满足这些依赖的任何要求。在 下面两个例子中，我们将使用前面例子中的dpe和base继承属性来说明这一点。 例6.12考虑例6.3的文法，它有继承属性d0p肥，其相关图例6.7中给出（见表6-3的属性文法） 首先假设从文法明确构造了分析树，为便于参考重述如下： decl→type var-.liu pe→int|f1oat var-list -id,var-list id 所有需要的节点dpe属性的递归程序的伪代码如下： procedure EvalTipe(T:treenode);

我们已经见过继承属性的例子，包括例 6 . 3中的d t y p e属性和例6 . 4中的b a s e属性。无论在分 析树中(使用这个名字的理由)从祖先到子孙的继承属性还是从同属的继承属性都有依赖。图 6 - 8 a和 b说明了继承属性依赖的两种基本种类。这两种类型的依赖在例 6 . 7中的d t y p e属性中都出现 过。这两种分类都为继承属性的原因在于计算继承属性的算法，同属继承通常是通过把属性值 经过祖先在同属中传递实现的。实际上，如果语法树的边只从祖先指向子孙 (这样子孙不能直 接访问祖先或同属 )这也是必要的。另一方面，在语法树中如果一些结构经过同属指针实现， 那么同属继承可以直接沿着同属链进行，如图6 -8c的描述。 图6-8 不同种类的继承依赖 a) 从祖先到子孙的继承 b) 同属之间的继承 c) 通过同属指针的同属继承 现在回到继承属性赋值的算法方法。继承属性的计算可以通过对分析树或语法树的前序遍 历或前序/中序遍历的组合来进行。这可以用下面的伪代码来示意表示： p ro c e d u re P reEval (T: t re e n o d e); b e g i n for each child C of T d o compute all inherited attributes of C; P reEval ( C ); e n d ; 与合成属性不同，子孙继承属性计算的顺序是重要的，因为在子孙的属性中继承属性可能有依 赖关系。因此在前面的伪代码中 T的每个子孙C的访问顺序必须满足这些依赖的任何要求。在 下面两个例子中，我们将使用前面例子中的 d t y p e和b a s e继承属性来说明这一点。 例6.12 考虑例6 . 3的文法，它有继承属性d t y p e，其相关图例6 . 7中给出(见表6 - 3的属性文法)。 首先假设从文法明确构造了分析树，为便于参考重述如下： decl → type var- l i s t type →i n t | f l o a t v a r- l i s t →i d, v a r- l i s t | i d 所有需要的节点d t y p e属性的递归程序的伪代码如下： p ro c e d u re E v a l Type (T: t re e n o d e); 2 1 4 编译原理及实践 下载 a) c) b)

China-pub.com 第6章语义分析 215 下载 begin case nodekind of t of decl EvalType (type child ofT): Assign drype of type child ofTto var-list child ofT Eal仍pe(var--list child of T)片 pe: if child ofT=int then T.drype :=integer else T.dtype :real; var-list assign T.dtype to first child of T; if third child of T is not nil then assign T.drype to third child EvalType (third child ofT); end case: end EvalType; 注意，前序和中序操作是如何根据被处理的不同类型的节点混合的。例如，节点dc在子节点 上递归调用Eval历pe之前，要求首先计算其第1个子孙的dpe,然后分配到其第2个子孙：这是 一个中序处理。另一方面， var-list节点在进行任何递归调用之前分配dpe给其子孙：这是一 个前序处理。 在图6-9中，我们与dpe属性的相关图一起显示了字符串￡1。atx,的分析树，并且按照 上面的伪代码计算dpe的顺序给节点编了号。 ----decl ①ype drype par-it② drype drype var-list④ drype 9回 图6-9显示例6.12遍历顺序的分析树 为了给出这个例子一个完全具体的形式，我们把前面的伪代码转换成实际的C语言代码 并且，为了替代使用明确的分析树，假设已经构造了一个语法树，va-list用id节点的同属列 表表示。这样，像E1oatx,这样的声明字符串语法树如下（与图6-9比较） (doreal) dec节点的子孙赋值顺序为从左至右（首先是节点ype,然后是节点x,最后是节点y)。注意

b e g i n case nodekind of T o f decl : E v a l Type (type child of T ); Assign dtype of type child of T to var-list child of T; E v a l Type (v a r- l i s t child of T ); type : if child of T = i n t then T.dtype := i n t e g e r else T.dtype := re a l; v a r- l i s t : assign T.dtype to first child of T; if t h i rd child of T is not nil t h e n assign T.dtype to third child; E v a l Type (t h i rd child of T ); end case: end E v a l Ty p e; 注意，前序和中序操作是如何根据被处理的不同类型的节点混合的。例如，节点 d e c l在子节点 上递归调用E v a l Ty p e之前，要求首先计算其第1个子孙的d t y p e，然后分配到其第2个子孙；这是 一个中序处理。另一方面， v a r- l i s t节点在进行任何递归调用之前分配 d t y p e给其子孙；这是一 个前序处理。 在图6 - 9中，我们与d t y p e属性的相关图一起显示了字符串float x,y的分析树，并且按照 上面的伪代码计算d t y p e的顺序给节点编了号。 图6-9 显示例6 . 1 2遍历顺序的分析树 为了给出这个例子一个完全具体的形式，我们把前面的伪代码转换成实际的 C语言代码。 并且，为了替代使用明确的分析树，假设已经构造了一个语法树， v a r- l i s t用i d节点的同属列 表表示。这样，像float x,y这样的声明字符串语法树如下(与图6 - 9比较) d e c l节点的子孙赋值顺序为从左至右 (首先是节点t y p e，然后是节点 x，最后是节点 y)。注意， 第 6章 语 义 分 析 2 1 5 下载

216 编译原理及实践 China-pub.co 下载 在这个树中已经包括了dpe节点和e节点，假定在语法分析时已经预先计算了。 语法树的结构用下面的C语言声明给出： enum deel,type,id nodekind struct treede +lchild,+rchild,*sibling; typekind dtype; for type and id nodes/ chart name: /★for1 d nodes on1y*/ 】*SyntaxTree: 相应地EvalType程序的C代码如下： void evalType(SyntaxTree t) switch (t->kind) case decli t- rchild->dtype t->1child->dtype break t- sibling t->dtype 】/:end switch*/ )/end evalType + 这段代码可以用下列非递归程序简化，其操作全部在根节点(ecl)层次上进行： (t->k hile p->sibling->dtype =p->dtype p=p->sibling; )/end if )end evalrype/ 例6.13考虑例6.4的文法，它具有继承属性base(相关图在例6.8中给出)。这里将那个例子的 文法重述如下： based-num-num basechar basechar→o|d nm一num digit|digit 91871间532110

在这个树中已经包括了d t y p e节点和t y p e节点，假定在语法分析时已经预先计算了。 语法树的结构用下面的C语言声明给出： typedef enum { decl, type, id } nodekind; typedef enum { integer, real } typekind; typedef struct treeNode { nodekind kind; struct treeNo d e *lchild, *rchild, *sibling; typekind dtype; /* for type and id nodes */ char * name; /* for id nodes only */ } * SyntaxTree; 相应地E v a l Ty p e程序的C代码如下： void evalType(SyntaxTree t) { switch (t->kind) { case decl: t->rchild->dtype = t->lchild->dtype; e v a l T y p e ( t - > r c h i l d ) ; b r e a k ; case id: if (t->sibling != NULL); { t->sibling->dtype = t->dtype; e v a l T y p e ( t - > s i b l i n g ) ; } b r e a k ; } /* end switch */ } /* end evalType */ 这段代码可以用下列非递归程序简化，其操作全部在根节点 (d e c l)层次上进行： void evalType(SyntaxTree t) { if (t->kind == decl) { SyntaxTree p = t->rchild; p->dtype = t->lchild->dtype; while (p->sibling != NULL) { p->sibling->dtype = p->dtype; p = p->sibling; } } /* end if */ } /* end evalType */ 例6.13 考虑例6 . 4的文法，它具有继承属性base (相关图在例6 . 8中给出)。这里将那个例子的 文法重述如下： b a s e d-n u m → n u m b a s e c h a r b a s e c h a r → o | d n u m → n u m d i g i t | d i g i t d i g i t →0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 2 1 6 编译原理及实践 下载

China-pub.com 第6章语义分析217 下载 这个文法有两个新特性。首先，它有两个属性，合成属性al以及val依赖的继承属性base。其 次，base属性是从based-mum左边的子孙向右边的子孙继承的（即从basechar到mm)。因此，在这科 情况下，我们必须从右向左而不是从左向右给based-num的子孙赋值。我们继续给出EvalWithBase 程序的伪代码用以计算base和val。对于这种情况，在一遍中base用前序道历计算，而val则用后序 遍历计算后面即将讨论多属性和多遍问题。这段伪代码如下参见表64的属性文法)： procedure EvalWithBase(T:treenode); begin case nodekind ofTof based-num: EvalWithBase right child of T); assign base of right child ofTto base of lef child EvalWithBase left child ofT); assign val of left child of T to T.val assign T.base to base of left child of T; EvalWithBase (left child ofT); if right child of T is not nil then if vals of left and right childrenerror then T.val :=T.base*val of left child)+val ofright child; else T.val :error; else Tyal:=val of left childa basechar: if child ofT=o then T.base :=8 else T.base :=10; digit: if T.base :=8 and child ofT=8 or 9 then T.val :error else T.val :=nmval child ofT); end case: end EvalWithBase; 我们把相应的语法树C语言声明的构造和将EvalWithBase伪代码转换为C语言代码的工作留作 练习。 在组合合成和继承属性的属性文法中，如果合成属性依赖于继承属性（及其他合成属性），但 继承属性不依赖于任何合成属性，那么就可能在分析树或语法树的一遍遍历中计算所有的属性 上例就是这一点很好的一个例子，赋值顺序可以组合PostEval和PreEval伪代码程序进行概括： procedure CombinedEval(T:treenode ) begin for each child CofT do compute all inherited attributes of C;

这个文法有两个新特性。首先，它有两个属性，合成属性v a l以及v a l依赖的继承属性b a s e。其 次，b a s e属性是从b a s e d-n u m左边的子孙向右边的子孙继承的(即从b a s e c h a r到n u m)。因此，在这种 情况下，我们必须从右向左而不是从左向右给b a s e d-n u m的子孙赋值。我们继续给出E v a l Wi t h B a s e 程序的伪代码用以计算b a s e和v a l。对于这种情况，在一遍中b a s e用前序遍历计算，而v a l则用后序 遍历计算(后面即将讨论多属性和多遍问题)。这段伪代码如下(参见表6 - 4的属性文法)： p ro c e d u re E v a l WithBase (T: t re e n o d e); b e g i n case nodekind of T o f b a s e d-n u m: E v a l WithBase ( right child of T ); assign base of right child of T to base of left child; E v a l WithBase ( left child of T ); assign val of left child of T to T. v a l; n u m: assign T.base to base of left child of T; E v a l WithBase ( left child of T ); if right child of T is not nil t h e n assign T.b a s e t o b a s e of right child of T; E v a l WithBase ( right child of T ); if vals of left and right childre n≠e rro r t h e n T.val := T.b a s e* ( val of left child ) + val of right child; else T.val := e rro r; else T.val := val of left child; b a s e c h a r: if child of T = o then T. b a s e := 8 else T. b a s e := 10; d i g i t: if T. b a s e := 8 and child of T = 8 or 9 then T.val := e rro r else T.val := n u m v a l ( child of T ); end case; end E v a l Wi t h B a s e; 我们把相应的语法树C语言声明的构造和将E v a l WithBase 伪代码转换为C语言代码的工作留作 练习。 在组合合成和继承属性的属性文法中，如果合成属性依赖于继承属性(及其他合成属性)，但 继承属性不依赖于任何合成属性，那么就可能在分析树或语法树的一遍遍历中计算所有的属性。 上例就是这一点很好的一个例子，赋值顺序可以组合PostEval 和PreEval 伪代码程序进行概括： p ro c e d u re CombinedEval ( T:t reenode ); b e g i n for each child C of T d o compute all inherited attributes of C; 第 6章 语 义 分 析 2 1 7 下载