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

Question

我在野牛中创建了上下文无关文法，在Flex中创建了扫描仪。现在我还想进行语义检查，例如，假设输入是这样的：

int m=5;
c=c+5;

该输入在语法上是正确的，但是使用了一个未声明的变量，即“ c”。我该如何进行语义检查？我应该从哪里开始？我应该用flex还是野牛写代码？如果有人可以提供帮助，我深表感谢。谢谢。

Answer 1

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

对于像C这样的静态语言，我们可以在语法分析时使用语法指导的规则（例如，在Yacc中触发的规则）立即执行此语义。

您的解析器需要维护符号表。也就是说，无论何时打开新的作用域（例如新的函数主体或语句块），都必须为该作用域创建一个新的符号表对象（并在某个全局解析器变量中将指向该对象的指针保留为“当前作用域”）。 ）。该范围还具有指向先前范围的指针。合并范围关闭时，将原始合并范围还原为“当前合并范围”。此作用域的打开和关闭与解析器规则相关，解析器规则处理诸如功能或语句主体或结构体之类的块结构。

范围包含变量名和语义信息之间的关联，例如符号是什么类型，以及其他属性（例如类型）。

当您的解析器处理某种类型的声明时，则将声明的名称引入当前的符号表中，然后再知道该名称。

因此，快速解决我们的问题：如何检查未定义名称。这并不困难。在某个地方，您的解析器具有如下规则

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

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

对于的操作规则IDENT，我们在当前符号表中查找标识符。如果搜索没有任何结果，则会引发错误，即存在未定义的标识符。

伪代码：

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编写编译器，则需要做很多工作来发明所有这些数据结构（例如符号表）并编写支持库。