欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

动手实现编译器(三)——语义分析

程序员文章站 2022-03-30 20:41:22
...

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

相关标签: 编译器 编译器