Lex和Yacc应用方法(四).语法树的应用
草木瓜 20070515
一、序
不论什么语言，语法结构总是那几种，可以想象任何程序体都可以解释成一棵语法
树，语法树的本质是递归，很显然Yacc文法的核心思想也是递归。本文就通过具体实例，
使用Yacc构建递归的语法树来解决实际问题。
比较遗憾的是，在总结的过程中想表达清楚并不容易，估且三分言传，七分会意吧。
关键在于个人去思考。
二、递归的一些思想
我们先看一个简化的C语言示例段：
i=0;
while(i<=10) {
print(i);
i=i+1;
}
print(i+i);
首先，我们将()+/* print while之类的组合称为expr(expression)，仅表示基本的表
达式，可以理解通过递归可以进行任意的运算符组合。如下面每一行都可称为expr:
i=0
while(i<=10)
print(i)
i=i+1
print(i+i)
再把expr + ;的语句行称为stmt(statement)，表示一条语句的结束。把{}引起来的多个stmt
称为stmt_list。如此，原示例段可表示为：
stmt
expr stmt_list
stmt
这样显然不符合递归法则，倘若stmt也可由expr stmt_list组合，程序则可以递归到最顶级
stmt
stmt
stmt
这也要求yacc文法定义必须可以递归到最顶级，即如上所示。
三、内存结构
编译过程必须在内存中形成一定规则且可递归的树形结构，比较容易理解对每一语句stmt
需要构建一棵语法树。
以下是我们准备采用的语法树实际示例：
Graph 0:
[=]
|
|----|
| |
idx(i) c(0)
Graph 1:
while
|
|----------------|
| |
[<=] [;]
| |
|-----| |----------|
| | | |
idx(i) c(10) print [=]
| |
| |-------|
| | |
idx(i) idx(i) [+]
|
|----|
| |
idx(i) c(1)
Graph 2:
print
|
|
|
[+]
|
|-----|
| |
idx(i) idx(i)
细心查看以上三张图，会发现每个stmt即对应一张树形图，树结点包含三种类型：操作符
(如 + = ; )，变量索引(如 idx(i))和值(如 c(10) c(1) )。对于每个操作符，需要保证一
个可递归的规则。
四、具体实例
A. node.h <树结点的定义头文件>
/* 定义树结点的权举类型 */
typedef enum { TYPE_CONTENT, TYPE_INDEX, TYPE_OP } NodeEnum;
/* 操作符 */
typedef struct {
int name; /* 操作符名称 */
int num; /* 操作元个数 */
struct NodeTag * node[1]; /* 操作元地址 可扩展 */
} OpNode;
typedef struct NodeTag {
NodeEnum type; /* 树结点类型 */
/* Union 必须是最后一个成员 */
union {
int content; /* 内容 */
int index; /* 索引 */
OpNode op; /* 操作符对象 */
};
} Node;
extern int Var[26];
[说明] Node即为定义的树形结点，结点可以是三种类型(CONTENT,INDEX,OP)。结点
如果
