compiler-construction - 如何使用flex/bison进行语义检查？

Question

我在 bison 中创建了上下文无关语法，并在 flex 中创建了扫描器。现在我还想进行语义检查，例如，假设输入是这样的:

int m=5;
c=c+5;

此输入在语法上是正确的，但使用了一个未声明的变量，即“c”。我怎样才能进行这样的语义检查？我应该从哪里开始？我应该用 Flex 还是 Bison 编写代码？如果有人可以提供帮助，我将不胜感激。谢谢。

Answer 1

首先要考虑的是:什么时候我们有足够的信息以便我们可以进行语义检查？

对于像 C 这样的静态语言，我们可以在解析时使用语法引导的规则(例如在 Yacc 中触发的规则)来执行此语义。

您的解析器需要维护符号表。也就是说，每当您打开一个新作用域(例如新函数体或语句 block )时，您都必须为该作用域创建一个新的符号表对象(并在某些全局解析器变量中保留指向该对象的指针作为“当前作用域”) )。该作用域还有一个指向前一个作用域的指针。当范围关闭时，您将原始范围恢复为“当前范围”。这种作用域的打开和关闭与解析器规则相关，解析器规则处理 block 构造，例如函数或语句体或结构体。

作用域包含变量名称和语义信息之间的关联，例如它是什么类型的符号，以及其他属性(例如类型)。

当您的解析器处理某种声明时，声明的名称将被引入当前符号表中，此后它就会被知道。

所以，快进到我们的问题:如何检查名称是否未定义。这并不难。在某个地方，你的解析器有这样的规则

primary_expression : '(' expression ')'
                   /* ...*/
                   | CONSTANT
                   | IDENT
                   ;

主表达式可以是标识符，例如变量、常量或函数名称。如果规则很严格，必须定义这些规则才能使用，我们可以将检查放在这里。

对于IDENT的 Action 规则，我们在当前符号表中查找标识符。如果搜索没有结果，我们会抛出一个错误，指出存在未定义的标识符。

伪代码:

primary_expression : '(' expression ')'
                   /* ...*/
                   | CONSTANT
                   | IDENT {
                       struct symbol *sym = symbol_lookup(current_scope, $1);
                       if (sym == NULL) {
                         static_error("undeclared identifier %s", $1);
                         $$ = error_node();
                       } else {
                         /* ... */
                       }
                     }

symbol_lookup函数不仅仅在当前范围内查找!如果在当前作用域中找不到标识符，它将递归到父作用域，依此类推。作用域链中的顶级作用域是文件作用域。如果在那里找到标识符，那么它是某种全局标识符。如果在那里也没有找到它，则它是未定义的。我还编了static_error；它有类似 printf 的参数，并添加文件/行号信息，并增加错误计数(这样当解析器完成时，它可以根据错误计数非零来指示失败)。我也编了error_node；它是一个函数或宏，会产生某种指示错误的节点(可能只是一个空指针)。您的解析器规则必须生成一些内容并将其存储到 $$ 中。对于不存在的标识符，我们可以在树中放入一些标记。

如果您使用 Yacc 用 C 语言编写编译器，则需要做大量工作来发明所有这些数据结构(例如符号表)并编写支持库。