Bison/Flex，减少/减少，不同生产中的标识符

Question

我在做野牛/ flex的分析器。

这是我的代码部分：

我要实现的任务生产，使该标识符既可以是boolean_expr或EXPR，它的类型将通过符号表进行检查。 所以它允许这样的：

int a = 1; 
boolean b = true; 
if(b) ... 

但是，降低/减少，如果我包括这两个长期和boolean_expr标识，任何解决方案来解决这个问题呢？

Answer 1

本质上，你要做的是在你的语法中注入语义规则（类型信息）。这是可能的，但这并不容易。更重要的是，这并不是一个好主意。如果语法和语义描述得很好，几乎总是最好的。

完全相同，因为呈现的语法是毫不含糊的，并且LALR(1)。但是，后一个特征很脆弱，并且在完成语法时难以维护它。

例如，您不包括你的赋值语法在你的问题，但它会

assignment: identifier '=' expr 
      | identifier '=' boolean_expr 
      ; 

不同于所示的语法部分的剩余部分，即生产是不明确的，因为：

x = y 

不知道任何关于y,y可以减少到term或boolean_expr。

一个可能更有趣的例子是在语法中增加了括号。这样做的最显而易见的方法是添加两种生产：

term: '(' expr ')' 

boolean_expr: '(' boolean_expr ')' 

产生的语法也不含糊，但它不再是LALR(1)。考虑以下两个声明：

boolean x = (y) < 7 
boolean x = (y) 

在第一个，y必须是int使得(y)可以减少到一个term;在第二个y必须是boolean，以便(y)可以减少到boolean_expr。没有歧义;一旦看到（或不看）<，就完全清楚要选择哪种减少。但是<不是超前记号，而实际上它可能是从y任意遥远：

boolean x = ((((((((((((((((((((((y... 

所以产生明确的语法不是LALR(k)任何k。你可以解决这个问题

---

的一种方法是通过给符号表扫描访问在词汇层面注入类型的信息。然后，扫描器可以在符号表中查找已扫描的标识符标记，并使用符号表中的信息来决定三种标记类型之一（或更多，如果您有更多数据类型）：undefined_variable,integer_variable和boolean_variable。然后，你将有，例如：

declaration: "int" undefined_variable '=' expr 
      | "boolean" undefined_variable '=' boolean_expr 
      ; 

term: integer_variable 
    | ... 
    ; 

boolean_expr: boolean_variable 
      | ... 
      ; 

，将工作，但它应该是显而易见的，这是不可伸缩的：每次添加一个类型的时候，你就必须扩大双方的语法和词汇的描述，因为现在的语义不仅与语法混淆，甚至还与词法分析混杂在一起。一旦你让语义脱离盒子，它往往会污染一切。

有些语言的确是最方便的解决方案：例如，如果区分typedef名称和标识符名称，C语法分析就容易得多，因此您可以判断(t)*x是演员还是乘法演员。 （但是对于C++来说这并不容易，C++有更复杂的名称查找规则，并且为了找到正确的解析也需要语义分析。）

但是，老实说，我会建议你做而不是使用C语言 - 更少的C++ - 作为如何设计语言的模型。编译器难以解析的语言对于人类来说也很难解析。该"most vexing parse"仍然是痛苦的正规来源C++新人，甚至有时会绊倒了比较有经验的程序员：

class X { 
    public: 
    X(int n = 0) : data_is_available_(n) {} 
    operator bool() const { return data_is_available_; } 
    // ... 
    private: 
    bool data_is_available_; 
    // ... 
}; 

X my_x_object(); 
// ... 
if (!x) { 
    // This code is unreachable. Can you see why? 
} 

总之，你最好用可以被解析成一个AST没有任何语言语义信息。一旦解析器产生了AST，就可以在单独的通道中进行语义分析，其中一个将检查类型约束。这是最干净的解决方案。没有显式类型，语法略有简化，因为expr现在可以是任何expr：

expr:  conjunction | expr "or" conjunction ; 
conjunction: comparison | conjunction "and" comparison ; 
comparison: product  | product '<' product ; 
product:  factor  | product '*' factor ; 
factor:  term  | factor '+' term ; 
term:  identifier 
    |  constant 
    |  '(' expr ')' 
    ; 

每个动作在上面会简单地创建一个新的AST节点并设置$$到新节点。在解析结束时，AST会走过来验证所有expr都具有正确的类型。

如果这看起来对您的项目来说太过分了，那么您可以在还原操作中进行语义检查，从而有效地将AST漫步与解析混合在一起。这对于立即评估似乎很方便，但它也需要在解析器的语义类型中包含显式类型信息，这会增加不必要的开销（并且，正如前面提到的，让语义干扰解析器的不妥当）。在这种情况下，每个动作都会看起来像这样：

expr : expr '+' expr { CheckArithmeticCompatibility($1, $3); 
         $$ = NewArithmeticNode('+', $1, $3); 
        }