我们在上一节中看到，语法分析器可以识别SysY语言的部分简单语法，并检查编译器的输入是否符合该语法，但不能处理不同的运算符优先级。因为，该代码将所有运算符都视为具有相同的优先级。
为了解决这个问题，我们必须在语法分析器中添加代码来执行操作符优先级。至少有两种方法可以做到这一点：
- 在语言的语法中明确运算符优先级
- 使用运算符优先级表影响现有的语法分析器
我们来看SysY语言中对于加减乘除取余的语法定义：
加减表达式 ：AddExp → MulExp | AddExp (’+’ | ‘−’) MulExp
乘除模表达式 ：MulExp → UnaryExp | MulExp (’*’ | ‘/’ | ‘%’) UnaryExp
在这里“UnaryExp”可以简单地看作是整数。
任何加法表达式实际上要么本身就是乘法表达式，要么是加法表达式，后跟“ +”或“-”运算符，然后是另一个乘法表达式。
在语法分析器中执行上述操作
正如上面所说的，实现这个功能可以有很多种方法，本文采用Pratt Parser法。Pratt Parser具有与每个单词关联的优先级值表，而不是使用具有在语法中复制显式优先级的函数。
首先，我们要确定每个单词的优先级：
// 每个单词的运算符优先级
static int OpPrec[] = { 0, 10, 10, 20, 20, 20, 0};
// 若是一个二元运算符，返回它的优先级，否则报错
static int op_precedence(int tokentype)
{
int prec = OpPrec[tokentype];
if (prec == 0)
{
fprintf(stderr, "syntax error on line %d, token %d\n", Line, tokentype);
exit(1);
}
return prec;
}
较高的数字表示优先级高于较低的数字。
在这里op_precedence()函数的作用是强制执行正确的语法语法。防止类似这样的情况出现123 456 + 789。
然后我们可以定义一个使用运算符优先级表的单一表达式函数，修改binexpr()为：
// 返回一个以二元操作符为根的树
struct ASTnode *binexpr(int pretokentype)
{
struct ASTnode *left, *right;
int tokentype;
// 获取左节点的整数，同时获取下一个单词
left = primary();
// 如果下一个单词是文件结尾，则返回左节点
tokentype = Token.token;
if (tokentype == T_EOF) return left;
// 当前单词的优先级高于前一个单词的优先级
while (op_precedence(tokentype) > pretokentype)
{
// 获取下一个单词
scan(&Token);
// 根据优先级递归生成右子树
right = binexpr(OpPrec[tokentype]);
// 从单词类型得到到节点类型，然后合并左、右子树
left = mkastnode(token_op(tokentype), left, right, 0);
// 更新当前单词的详细信息
tokentype = Token.token;
// 如果到文件结尾，则返回左节点
// 此时的左节点已经更新为合并后的树的根节点
if (tokentype == T_EOF) return left;
}
return left;
}
测试结果
修改main()函数以便于测试结果：
// 用法 compiler -o -s outfile infile
int main(int argc, char *argv[])
{
struct ASTnode *n;
if(argc != 5)
{
fprintf(stderr, "compiler -o -s outfile infile\n");
exit(1);
}
init();
if ((Infile = fopen(argv[4], "r")) == NULL)
{
fprintf(stderr, "Unable to open %s: %s\n", argv[1], strerror(errno));
exit(1);
}
scan(&Token); // 从输入中获得第一个单词
n = binexpr(OpPrec[Token.token]); // 解析表达式，修改此处
printf("%d\n", interpretAST(n)); // 计算最终的结果
}
输入：
2 + 3 * 4 / 5 % 6 - 7 + 8
输出：
int 2
int 3
int 4
3 * 4
int 5
12 / 5
int 6
2 % 6
2 + 2
int 7
4 - 7
int 8
-3 + 8
5
输入：
2 + 3 * 4 / 5 % 6 - 7 8
输出：
syntax error on line 1, token 6
总结
到目前为止，我们实现了：
- 一个词法分析器，可以识别并返回我们语言中的单词
- 一个语法分析器，可以报告语法错误和构建抽象语法树
- 一个利用优先级表的语义分析器，可以进行语义分析和处理
- 一个深度优先遍历抽象语法树并计算输入中表达式的结果的测试器
在下一节中，我们将替换测试器。我们将编写一个翻译器，为具有数学运算符的每个AST节点生成ARMv7-32汇编代码。我们还将生成一些汇编前同步码和后同步码，以支持生成器输出的汇编代码。
