编译原理与实践中的赋值语句抽象语法树属性文法

这里将要介绍的图表示法包括抽象语法树与DAG两种。

1.抽象语法树

我们已经知道，遍历语法树可以计算属性值，因此，可以考虑将语法树作为一种合适的中间代码形式，而抽象语法树就是这种语法树之一，它在语法树中去掉了那些对翻译不必要的信息，从而获得更有效的中间代码表示。

构造抽象语法树的原则是：操作符和关键字都不作为叶结点，而是作为内部结点出现。例如，赋值语句a：=b*-c+b*-c的抽象语法树如图6-8所示。

图6-8　a：=b*-c+b*-c的语法分析树

为赋值语句建立抽象语法树的属性文法如表6-5所示，这里仅以+、*运算为例进行说明。

表6-5　产生赋值语句抽象语法树的属性文法(www.xing528.com)

其中，nptr是综合属性，用来表示函数调用返回的指针；place是标识符id的属性，用来表示一个指向符号表中该标识符表项的指针。很明显，这是一个S-属性文法。函数mknode（op，left，right）用来建立一个运算符号结点，op表示该结点的运算符号域，left和right是该结点的两个指针域，分别指向运算分量的左子树和右子树；函数mkleaf（id，entry）用来建立一个标识符结点，id表示该结点的标识符标号域，entry域则指向标识符在符号表中的入口。还有一个函数这里没有用到，它是mkleaf（num，value），用来建立一个数值结点，num为该结点的数值标号域，value则用来存放数的值。

2.DAG

无循环有向图（Directed Acyclic Graph），简称DAG。与抽象语法树相同的是，对于表达式中的每个子表达式，DAG中相应的都有一个结点，一个内部结点代表一个操作符，其子结点代表操作数；然而不同的是，DAG中代表公共子表达式的结点具有多个父结点，而抽象语法树中的公共子表达式被表示为重复的子树。

例如，图6-9表示的是赋值语句a：=b*-c+b*-c的DAG，其中，结点*与其父结点+之间存在两条边，可以认为*有两个父结点+，之所以会这样，是因为b*-c是该赋值语句的公共子表达式，在DAG中只能出现一次。

对于表6-5中的属性文法，如果使函数mknode（）返回一个已经存在的指针，那么，很容易将这个文法改造成生成DAG的属性文法。