动手实现编译器（三）——语义分析

我们在上一节中看到，语法分析器可以识别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汇编代码。我们还将生成一些汇编前同步码和后同步码，以支持生成器输出的汇编代码。