C语言表达式解析与抽象语法树构建

# C语言表达式解析与抽象语法树构建 ## 1. 表达式解析概述 C表达式构成了一种子语言，其解析函数相对容易编写。解析C表达式是分析输入程序的重要起点，相关函数会构建输入程序的内部表示，主要由抽象语法树和代码列表组成。 有四个模块协同工作，用于解析、分析和表示表达式： - `expr.c`：实现识别和翻译表达式的解析函数。 - `tree.c`：实现管理树的底层函数，树是表达式的内部中间表示。 - `enode.c`：实现类型检查函数，确保表达式的语义有效性，并导出构建和操作树的函数。 - `simp.c`：实现执行树转换的函数，如常量折叠。 ## 2. 表达式的表示 ### 2.1 抽象语法树 编译器在识别和分析表达式后，需要构建其中间表示，以便检查有效性并生成代码。抽象语法树（简称树）常被用于表示表达式，它是没有非终结符节点和无用终结符节点的解析树。在树中，节点表示运算符，其子节点表示操作数。 例如，表达式`(a+b)+b*(a+b)`的抽象语法树如下： ```plaintext ADD+I / \ ADD+I MUL+I | / \ INDIR+I INDIR+I ADD+I | | | \ ADDRG+P ADDRG+P ADDRG+P INDIR+I | | | | a b b INDIR+I | ADDRG+P | a | ADDRG+P | b ``` 树中可能包含源语言中未出现的运算符，如`INDIR+I`用于获取操作数指定地址处的整数，C语言中没有显式的“获取”运算符。还有一些转换运算符，是由于隐式转换或语义规则引入的，部分运算符在运行时没有对应的操作，仅用于方便编译。 ### 2.2 树的结构 树的节点定义如下： ```c typedef struct tree *Tree; struct tree { int op; Type type; Tree kids[2]; Node node; union { (u fields for Tree variants 168) } u; }; ``` - `op`字段：保存运算符的代码。 - `type`字段：指向一个`Type`，表示节点在运行时计算结果的类型。 - `kids`字段：指向操作数。 - `node`字段：用于在第12.2节详细描述的从树构建有向无环图（DAG）。 - `u`联合：某些运算符的树会在其`u`联合的字段中存储额外信息。 运算符是通用运算符加上类型后缀形成的，例如`ADD+I`表示整数加法。对应的节点运算符`ADDI`省略了`+`，这有助于在图和文本中区分树和DAG。类型后缀在第5.5节列出，表5.1给出了每个运算符允许的后缀。 除了表5.1中显示的运算符，树中还会出现以下六个运算符： | 运算符 | 操作 | 操作数数量 | | ---- | ---- | ---- | | AND | 逻辑与（对应`&&`） | 2 | | OR | 逻辑或（对应`||`） | 2 | | NOT | 逻辑非（对应`!`） | 1 | | COND | 条件表达式（对应`c ? e1 : e2`） | 2 | | RIGHT | 组合表达式 | 1或2 | | FIELD | 位字段引用 | 1 | ### 2.3 树的分配与操作 树的分配、初始化和返回由以下函数完成： ```c Tree tree(op, type, left, right) int op; Type type; Tree left, right; { Tree p; NEWO(p, where); p->Op = op; p->type = type; p->kids[0] = left; p->kids[1] = right; return p; } static int where = STMT; ``` 树通常在`where`指示的分配区域分配，大多数情况下是`STMT`区域。`STMT`区域分配的数据最常被释放，可能在解析完每个语句后释放。但在某些情况下，表达式的树需要在当前语句编译后保留，例如`for`循环中的增量表达式。这些表达式通过调用`texpr`函数进行解析： ```c Tree texpr(f, tok, a) Tree (*f) ARGS((int)); int tok, a; { int save = where; Tree p; where = a; p = (*f)(tok); where = save; return p; } ``` `tree.c`中的其他函数用于构造、测试或操作树和运算符，这些函数都是应用型的，即构建新树而不修改现有树。 ## 3. 表达式解析方法 ### 3.1 简化解析过程 C语言有41个运算符，分布在15个优先级级别。从包含每个优先级级别非终结符的EBNF语法开始推导解析函数是正确的方法，但比较繁琐。可以通过一个简单的语法示例来说明简化过程： ```plaintext expr: term { + term } term: factor { * factor } factor: ID | '(' expr ')' ``` 根据这个语法，可以直接编写解析函数。例如，`expr`函数的推导和简化步骤如下： ```plaintext T(expr) T(term { + term }) T(term) T({ + term }) term(); T({ +term}) term(); while (t == '+') { T(+ term)} term(); while (t == '+') { T(+) T(term)} term(); while (t == '+') { t = gettok(); T(term) } term(); while (t == '+') { t = gettok(); term(); } ``` `term`函数的主体如下： ```c void term() { factor(); while (t == '*') { t = gettok(); factor(); } } ``` `factor`函数处理基本表达式： ```c void factor(void) { if (t == ID) t = gettok(); else if (t == '(') { t = gettok(); expr(); expect(')'); } else error("unrecognized expression\n"); } ``` 对于有`n`个优先级级别的情况，通常有`n + 1`个非终结符和对应的解析函数。如果二元运算符都是左结合的，这些函数非常相似，主要区别在于期望的运算符和要调用的函数。可以利用这种相似性，用一个函数和一个按优先级递增排序的运算符表来替代1到`n`的函数。 ### 3.2 运算符优先级和结合性 C语言运算符的优先级和结合性如下表所示： | 优先级 | 结合性 | 运算符 | 用途 | 解析函数 | | ---- | ---- | ---- | ---- | ---- | | 1 | 左 | 组合 | expr | | 2 | 右 | `= += -= *= /= %= &= ^= |= <<= >>=` | 赋值 | expr1 | | 3 | 右 | `?:` | 条件 | expr2 | | 4 | 左 | `||` | 逻辑或 | expr3 | | 5 | 左 | `&&` | 逻辑与 | expr3 | | 6 | 左 | `|` | 按位或 | expr3 | | 7 | 左 | `^` | 按位异或 | expr3 | | 8 | 左 | `&` | 按位与 | expr3 | | 9 | 左 | `== !=` | 相等 | expr3 | | 10 | 左 | `< > <= >=` | 关系 | expr3 | | 11 | 左 | `<< >>` | 移位 | expr3 | | 12 | 左 | `+ -` | 加法 | expr3 | | 13 | 左 | `* / %` | 乘法 | expr3 | | 14 | 前缀 | `* & - + ! -- ++ sizeof (type)` | 一元前缀 | unary | | 15 | 后缀 | `++ --` | 一元后缀 | postfix | ### 3.3 解析函数的实现 使用`prec`数组存储运算符的优先级，`prec[t]`表示令牌代码为`t`的运算符的优先级。例如，`prec['+']`为12，`prec[LEQ]`为10。假设只有`+`、`-`、`*`、`/`和`%`运算符，`expr`和`term`函数可以用一个函数替代： ```c void expr(int k) { if (k > 13) factor(); else { expr(k + 1); while (prec[t] == k) { t = gettok(); expr(k + 1); } } } ``` 表达式解析从调用`expr(12)`开始，`factor`函数中对`expr`的调用也需要改为`expr(12)`。 ### 3.4 左右结合性处理 `expr`函数中的`while`循环处理左结合运算符，对于右结合运算符，如赋值运算符，可以在`while`循环中调用`expr(k)`而不是`expr(k + 1)`。假设每个优先级级别的运算符具有相同的结合性，可以通过表格、编写不同的解析函数或显式测试来处理。 ### 3.5 一元运算符处理 C语言中的一元运算符具有最高优先级，在解析函数的最后一级处理。例如，`expr`函数在`k`超过最高优先级时调用`factor`函数解析基本表达式。 ## 4. C表达式的完整解析 ### 4.1 C表达式的语法 C表达式的完整语法如下： ```plaintext expression: assignment-expression { , assignment-expression } assignment-expression: conditional-expression unary-expression assign-operator assignment-expression assign-operator: one of = += -= *= /= %= <<= >>= &= ^= |= conditional-expression: binary-expression [ ? expression : conditional-expression ] binary-expression: unary-expression { binary-operator unary-expression } binary-operator: one of || && | ^ & == != < > <= >= << >> + - * / % ```