China-pub.com 第3章上下文无关文法及分析 79 下载 实际上，从刚刚给出的示例中的3个推导和分析 中已可看到这个对应了。在3个推导的第1个中给出 的是最左推导，而第2个则是最右推导（第3个推导 既不是最左推导也不是最右推导)。 再看一个复杂一些的分析树与最左和最右推导 据图31的推导为节点编了号。这个推导实际上是最 左推导，且分析树的相应编号是相反的后序编号 另一方面，图3-2中的推导是最左推导（我们期望读 者能够提供与这个推导相应的分析树的前序编号)。 图33算术表达式34-3)*42的分析树 3.3.2抽象语法树 分析树是表述记号串结构的一种十分有用的表示法。在分析树中，记号表现为分析树的树 叶（自左至右），而分析树的内部节点则表示推导的各个步骤（按某种顺序）。但是，分析树却 包括了比纯粹为编译生成可执行代码所需更多的信息。为了看清这一点，可根据简单的表达式 文法，考虑表达式3+4的分析树： ber 这是上一个例子的分析树。我们已经讨论了如何用这个树来显示每一个number记号的真 实数值（这是由扫描程序或分析程序计算的记号的一个特征）。语法引导的转换原则(principle of syntax-directed translation)说明了：如同分析树所表示的一样，串3+4的含义或语义应与其 语法结构直接相关。在这种情况中，语法引导的转换原则意味着在分析树表示中应加上数值3 和数值4。实际上可将这个树看作：根代表两个孩子xp子树的数值相加。而另一方面，每个子 树又代表它的每个numberi孩子的值。但是还有一个更为简单的方法能表示与这相同的信息， 即如树： 这里的根节点仅是被它所表示的运算标出，而叶子节点由其值标出（不是numb©x记号）。类 似地，在图33中给出的表达式(34-3)*42的分析树也可由下面的树简单表示出来：
实际上，从刚刚给出的示例中的 3个推导和分析 中已可看到这个对应了。在 3个推导的第 1个中给出 的是最左推导，而第 2个则是最右推导（第 3个推导 既不是最左推导也不是最右推导）。 再看一个复杂一些的分析树与最左和最右推导 的示例——表达式( 3 4 - 3 ) * 4 2与图3 - 1和图3 - 2中的 推导。这个表达式的分析树在图 3 - 3中，在其中也根 据图3 - 1的推导为节点编了号。这个推导实际上是最 左推导，且分析树的相应编号是相反的后序编号。 另一方面，图3 - 2中的推导是最左推导（我们期望读 者能够提供与这个推导相应的分析树的前序编号）。 3.3.2 抽象语法树 分析树是表述记号串结构的一种十分有用的表示法。在分析树中，记号表现为分析树的树 叶（自左至右），而分析树的内部节点则表示推导的各个步骤（按某种顺序）。但是，分析树却 包括了比纯粹为编译生成可执行代码所需更多的信息。为了看清这一点，可根据简单的表达式 文法，考虑表达式3 + 4的分析树： 这是上一个例子的分析树。我们已经讨论了如何用这个树来显示每一个 n u m b e r记号的真 实数值（这是由扫描程序或分析程序计算的记号的一个特征）。语法引导的转换原则（p r i n c i p l e of syntax-directed translation）说明了：如同分析树所表示的一样，串 3 + 4的含义或语义应与其 语法结构直接相关。在这种情况中，语法引导的转换原则意味着在分析树表示中应加上数值 3 和数值4。实际上可将这个树看作：根代表两个孩子 e x p子树的数值相加。而另一方面，每个子 树又代表它的每个 n u m b e r孩子的值。但是还有一个更为简单的方法能表示与这相同的信息， 即如树： 这里的根节点仅是被它所表示的运算标出，而叶子节点由其值标出（不是 n u m b e r记号）。类 似地，在图3 - 3中给出的表达式( 3 4 - 3 ) * 4 2的分析树也可由下面的树简单表示出来： 第 3章 上下文无关文法及分析 7 9 下载 图3-3 算术表达式( 3 4 - 3 ) * 4 2 的分析树
80 翁译原理及实践 China-pub.CoM 下载 在这个树中，括号记号实际已消失了，但它仍然准确地表达着从34中减去3，然后再乘以42的 语义内容。 这种树是真正的源代码记号序列的抽象表示。虽然不能从其中重新得到记号序列（不同于 分析树)，但是它们却包含了转换所需的所有信息，而且比分析树效率更高。这样的树称作抽 象语法树(abstract syntax tree)或简称为语法树(syntax tree)。分析程序可通过一个分析树表 示所有步骤，但却通常只能构造出一个抽象的语法树（或与它等同的）。 我们可将抽象语法树想象成一个称作抽象语法(abstract syntax)的快速计数法的树形表示 法，它很像普通语法结构的分析树表示法（当与抽象语法相比时，也称作具体语法(concrete svntax))。例如，表达式3+4的抽象语法可写作OpExD(Plus.ConstExp(3).ConstExp4)：而表达 式(34-3)*42的抽象语法则可写作： OpExp(Times,OpExp(Minus,ConstExp (34),ConstExp(3)),ConstExp(42)) 实际上，可通过使用一个类似BNF的表示法为抽象语法给出一个正式的定义，这就同具体语法 样。例如，可将简单的算术表达式的抽象语法的相似BNF规则写作： exp-OpExp(op.exp,exp)ConstExp (integer) op -Plus Minus Times 对此就不再进一步探讨了，我们把主要的精力放在可被分析程序利用的语法树的真正结构上， 它由一个数据类型说明给出9。例如，简单的算术表达式的抽象语法树可由C数据类型说明给出： inu,Timos】OpKind (Opkind ConstKind) YP sTreeNode typedef sTreeNode *syntaxtree 请注意：除了运算本身（加、减和乘）之外，我们在语法树节点两种不同类型（整型常数和运 算)中还使用了枚举类型。实际上是可以利用记号来表示运算，而无需定义一个新的枚举类型。 此外还能够使用一个C union类型来节省空间，这是因为节点不能既是一个算符节点，同时又 是一个常数节点。最后还要指出这些树的节点说明只包括了这些示例直接用到的特征。在实际 应用中，编译中使用的特征还会更广泛，例如：数据类型、符号表信息等等，本章后面以及以 后几章的示例都会谈到它。 下面用一些通过使用前面例子中谈到过的文法的分析树和语法树的示例来小结这一段。 例3.8考虑例3.4中被简化了的语句的文法： statementif-stmt other if-stmt -if (exp)statement if (exp)statement else statement exp→0|1 日有一些刚刚给出的抽象语法的语言在本质上是一个类型说明，参见练习
在这个树中，括号记号实际已消失了，但它仍然准确地表达着从 3 4中减去3，然后再乘以4 2的 语义内容。 这种树是真正的源代码记号序列的抽象表示。虽然不能从其中重新得到记号序列（不同于 分析树），但是它们却包含了转换所需的所有信息，而且比分析树效率更高。这样的树称作抽 象语法树（abstract syntax tree）或简称为语法树（syntax tree）。分析程序可通过一个分析树表 示所有步骤，但却通常只能构造出一个抽象的语法树（或与它等同的）。 我们可将抽象语法树想象成一个称作抽象语法（abstract syntax）的快速计数法的树形表示 法，它很像普通语法结构的分析树表示法（当与抽象语法相比时，也称作具体语法（ c o n c r e t e s y n t a x））。例如，表达式3 + 4的抽象语法可写作O p E x p(P l u s , C o n s t E x p( 3 ) ,C o n s t E x p( 4 ) )；而表达 式( 3 4 - 3 ) * 4 2的抽象语法则可写作： O p E xp (Ti m e s, O p E xp (M i n u s, ConstExp (34), ConstExp (3)), ConstExp ( 4 2 ) ) 实际上，可通过使用一个类似B N F的表示法为抽象语法给出一个正式的定义，这就同具体语法 一样。例如，可将简单的算术表达式的抽象语法的相似 B N F规则写作： exp → OpExp (o p, e x p, e x p) | ConstExp (i n t e g e r) op → Plus | Minus | Ti m e s 对此就不再进一步探讨了，我们把主要的精力放在可被分析程序利用的语法树的真正结构上， 它由一个数据类型说明给出 。例如，简单的算术表达式的抽象语法树可由C数据类型说明给出： 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; 请注意：除了运算本身（加、减和乘）之外，我们在语法树节点两种不同类型（整型常数和运 算）中还使用了枚举类型。实际上是可以利用记号来表示运算，而无需定义一个新的枚举类型。 此外还能够使用一个C u n i o n类型来节省空间，这是因为节点不能既是一个算符节点，同时又 是一个常数节点。最后还要指出这些树的节点说明只包括了这些示例直接用到的特征。在实际 应用中，编译中使用的特征还会更广泛，例如：数据类型、符号表信息等等，本章后面以及以 后几章的示例都会谈到它。 下面用一些通过使用前面例子中谈到过的文法的分析树和语法树的示例来小结这一段。 例3.8 考虑例3 . 4中被简化了的i f语句的文法： statement → if-stmt | o t h e r if-stmt → if (e x p) s t a t e m e n t | if (e x p) statement e l s e s t a t e m e n t exp → 0 | 1 串 8 0 编译原理及实践 下载 有一些刚刚给出的抽象语法的语言在本质上是一个类型说明，参见练习