c - 创建 AST 后进行语义检查

Question

我创建了一个扫描器和一个解析器(分别使用 flex 和 bison)以及一个 AST 来实现 Java-Python 翻译器。我不明白如何管理 AST 中的语义操作(类型检查、变量声明检查等)，即在哪里插入实现这些检查的函数以及如何将符号表(我创建的)连接到 AST。例如，考虑解析器中的产生式:

VariableDeclaration
                   : VariableName                               {$$ = varDec_new($1,NULL);}
                   | VariableName ASSIGNOP ExpressionStatement  {$$ = varDec_new($1,$3);}
                ;

在 ast.c 中定义 varDec_new 如下:

ast_node *varDec_new(ast_node *variableName, ast_node *exprStmt)
{
    ast_node *n = newast(AST_VARDEC); // ast_node allocation (in this case for the ast_node AST_VARDEC (type of ast_node)
    n->varDec.variableName = variableName; // pointer to variableName struct in AST
    n->varDec.exprStmt = expreStmt;   //pointer to expreStmt struct in AST
    return n;
}

如何管理类型检查(VariableName 和 ExpressionStatement 之间)？我是否需要使用整个 AST 类似参数(在 ast.c 中)创建一个函数，或者每当我发现需要在解析器中进行类型检查的产生式时就调用该函数？

Answer 1

在此处查看您的语义操作中可用的符号表:

• https://www.gnu.org/software/bison/manual/html_node/Pure-Calling.html
• https://www.gnu.org/software/bison/manual/html_node/Parser-Function.html

然后，这是一个赋值语义操作函数的非常简化的伪 cpp 代码，不过最好在树完成后执行此操作:

bool storeNodeType(symtable* sym, node* assignment)
{
    switch(root->RHS_node_kind):
    {
        case '+':
             left_type = getNodeType(sym, assignment->RHS->left);
             right_type = getNodeType(sym, assignment->RHS->right);
             [ ... apply_type_coercion_rules ... ]
             return sym->store(found_type,assignment->left->var);

        break;
        [... Plenty of cases]
        case t_Var:
             return symtable->store(assignment->left->var->vartype,assignment->left->var);
        break;
    }
    // each return returns if assignement vaild regarding types */;
}

1. 它假设右侧使用的任何变量都已经有类型，如果不是这种情况，则必须在 bison 完成后在第二遍中输入树的类型。
2. 您基本上执行 RHS 的后序遍历，根据每个运算符的类型强制规则推断每个子表达式的类型。叶节点可以是已知类型的变量，也可以是常量。因此，您“自下而上”输入 RHS。
3. 在 sym::store 中，您必须管理是否接受反式输入(string <- int)和/或再次管理类型强制(int <- float)。相应地返回错误。