Bison：在 GLR 解析器中按类型/YYERROR 区分变量

Question

我正在使用 GNU bison 开发解析器，我遇到了一个有趣的问题。我的实际问题有点不同，一般来说没那么有趣，所以我会以不同的方式陈述，这样一个答案通常会更有用。

我需要根据表达式的类型来区分表达式，例如算术表达式和字符串表达式。它们的顶级非终结符有一些共同的祖先，比如

statement
    : TOK_PRINT expression TOK_SEMICOLON {...}
;
expression
    : arithmeticexpression {...}
    | stringexpression {...}
;

现在我需要能够在两种表达式中都有变量

arithmeticexpression
    : TOK_IDENTIFIER {...}
;
stringexpression
    : TOK_IDENTIFIER {...}
;

(stringexpression只允许string类型的变量，arithmeticexpression只允许int或float类型的变量) 但这显然会导致R/R冲突，这是语言固有的——无法解决，因为语言是有歧义的。

当然我可以淡化语言，这样只有一般的 "Expression" 对象在解析堆栈上传递，但是我必须在行动，我想避免。此外，在我的真实用例中，通过语法到变量规则的路径是如此不同，以至于我不得不对语言进行大量稀释，以至于我会丢失很多语法规则（即丢失很多结构信息），并且需要手写解析引擎到一些动作中。

我已经阅读了有关 GLR 解析的内容，听起来它可以解决我的问题。我正在考虑使用此功能：在相应变量类型错误的路径中使用上述语法和 YYERROR。

arithmeticexpression
    : TOK_IDENTIFIER {
          if(!dynamic_cast<IntVariable*>(
              symbol_table[*$<stringvalue>1]))
              YYERROR;
      }
;
stringexpression
    : TOK_IDENTIFIER {
          if(!dynamic_cast<StringVariable*>(
              symbol_table[*$<stringvalue>1]))
              YYERROR;
      }
;

但是 Bison Manual 说

During deterministic GLR operation, the effect of YYERROR is the same as its effect in a deterministic parser.

The effect in a deferred action is similar, but the precise point of the error is undefined; instead, the parser reverts to deterministic operation, selecting an unspecified stack on which to continue with a syntax error.

In a semantic predicate (see Semantic Predicates) during nondeterministic parsing, YYERROR silently prunes the parse that invoked the test.

我不确定我是否理解正确 - 我是这样理解的：

这里不适用，因为 GLR 解析不是确定性的
我在上面的代码中是这样做的，但不应该这样做，因为 YYERROR 杀死哪条路径是完全随机的（如果我错了请纠正我）
不会解决我的问题，因为 semantic predicates（不是语义 actions！）必须在规则的开头（如果我错了请纠正我)，此时无法访问 TOK_IDENTIFIER 令牌中的 yylval（如果我错了请纠正我），因此我无法查看符号 table 来查找变量的类型.

有没有人遇到过这种情况？我对手册的理解有误吗？你会如何处理这个问题？对我来说，这个问题似乎很自然，我会假设人们运行经常参与其中，以至于 bison 会有一个内置的解决方案...

Answer 1

注意：至少从 bison 3.0.1 开始，从 bison 3.0.5 开始，在处理语义谓词操作时存在错误，导致 bison 输出 #line指令在一行中间，导致编译失败。 bison 存储库的 , and has been committed to the maint branch 中描述了一个简单的修复。（从存储库构建 bison 不适合胆小的人。但如果您不想自己编辑文件，从该存储库下载 data/c.m4 就足够了。）

让我们从关于 GLR 解析器中 YYERROR 的具体问题开始。

实际上，您可以在语义谓词中使用 YYERROR 以通过拒绝其所属的产生式来消除解析歧义。您不能在语义操作中执行此操作，因为在解析器决定唯一解析之前不会执行语义操作，此时不再存在歧义。

语义动作可以出现在规则的任何地方，当它们被缩减时会立即执行，即使缩减是有歧义的。因为它们是乱序执行的，所以它们不能引用任何前面的语义动作产生的值（并且语义谓词本身没有语义值，即使它们占据了堆栈槽）。此外，由于它们作为可能不是最终解析的一部分的产生式的一部分被有效地推测执行，因此它们不应改变解析器状态。

语义谓词确实可以通过变量 yychar 访问前瞻标记（如果有的话）。如果yychar既不是YYEMPTY也不是YYEOF，则关联的语义值和位置信息分别在yylval和yylloc中。（参见 Lookahead Tokens）。但是，在使用此功能之前必须小心；如果语法中的那个点没有歧义，则 bison 解析器很可能会在不读取先行标记的情况下执行语义谓词。

所以你的理解很接近，但不完全正确：

为了提高效率，GLR 解析器会识别解析中何时没有歧义，并在这些点使用正常的直接移位归约算法。在大多数语法中，歧义很少见并且会被迅速解决，因此这种优化意味着对于大多数解析而言，可以避免与维护多个备选方案相关的开销。在这种模式下（当然，如果可能存在歧义，则不适用），YYERROR 会导致标准错误恢复，就像在 shift-reduce 解析器中一样，在动作的减少点。
由于延迟操作在歧义被解决之前不会运行，因此延迟操作中的YYERROR将有效地执行，就好像它处于确定性状态一样，如上一段。即使有自定义合并过程也是如此；如果正在进行自定义合并，所有参与自定义合并的备选方案将被丢弃。之后，将继续正常的错误恢复算法。我不认为错误恢复点是 "random"，但预测错误恢复点并不容易。
如上所述，语义谓词可以出现在规则中的任何位置，并且可以访问先行标记（如果有的话）。（Bison 手册在这里有点误导：语义谓词不能包含 YYERROR 的调用，因为 YYERROR 是一个语句，而语义谓词块的内容是一个表达式。如果语义谓词为假，则解析器执行 YYERROR 操作。）

实际上，这意味着您可以使用语义谓词代替（或同时使用）动作，但基本上按照您建议的方式：

arithmeticexpression
    : TOK_IDENTIFIER %?{
          dynamic_cast<IntVariable*>(symbol_table[*])
      }
stringexpression
    : TOK_IDENTIFIER %?{
          dynamic_cast<StringVariable*>(symbol_table[*])
      }

注意： 我从 $<stringvalue>1 中删除了类型声明，因为：

基本看不懂，至少对我来说，
更重要的是，与显式转换一样，它不是类型安全的。

您应该声明您的标记的语义类型：

%type <stringvalue> ID

这将允许 bison 进行类型检查。

为此目的使用语义谓词是否是个好主意是另一个问题。

Answer 2

此处的示例有效，但是当我将其与的解决方案放在一起时，我运行遇到以下问题：

变量可以由多个标识符确定。您可以有一个数组索引，也可以是另一个对象的成员。我通过使用另一个像

这样的非终端来模拟这种情况

lvalue
    : TOK_IDENTIFIER
    | lvalue '[' arithmeticexpression ']'
    | lvalue '.' TOK_IDENTIFIER

但是当我现在有了

arithmeticexpression : lvalue
stringexpression : lvalue

并且（尝试）像上面那样从非终端 "lvalue" 访问对象，我遇到了分段错误。所以这里的方法好像对更复杂的情况不起作用

我现在所做的是在语义 ACTION 中访问对象，如果变量类型错误，则将 $$ 设置为 nullptr。

arithmeticexpression
    : lvalue
    {
        $$ = nullptr;
        if(dynamic_cast<IntVariable*>($lvalue->getVariable()))
            $$ = new ArithmeticExpressionIntVariable($lvalue);
    }

然后我不得不像这样传播 nullptr（这是相当多的附加代码）

arithmeticexpression
    ...
    | arithmeticexpression[left] '+' arithmeticexpressionM[right]
    {
        $$ = nullptr;
        if($left && $right)
            $$ = new ArithmeticExpressionPlus($left, $right);
    }

所以现在，在

expression
    : arithmeticexpression
    | stringexpression
(note: I have "Expression* expr;" in the "%union{" declaration
and "%type <expression> expr" in the prologue)

我有一个歧义：可以用两种不同的方式解析相同的输入文本，但只有其中一种会有值 != nullptr。在这一点上，我需要一个自定义合并过程，它基本上只选择非空值。

为此，我在我的野牛文件的序言中像这样向前声明它

static Expression* exprMerge (yy::semantic_type x0, yy::semantic_type x1);

并在结语中这样定义

static Expression* exprMerge (YYSTYPE x0, YYSTYPE x1) \
{   
    /* otherwise we'd have a legitimate ambiguity */
    assert(!x0.expr || !x1.expr);
    return x0.expr ? x0.expr : x1.expr;
}

最后，我不得不告诉 bison 使用这个程序来解决歧义，使用

expression
    : arithmeticexpression  %merge <exprMerge>
    | stringexpression %merge <exprMerge>

老实说，我认为这是相当大的努力，如果 bison 在尝试合并路径而不是规则时测试语义谓词（至少是规则后面的那些），则没有必要在它们合并之前输出路径。

但至少这是有效的，而且比收集标记并手动排序要省力得多，后者本来是替代方案。

Bison：在 GLR 解析器中按类型/YYERROR 区分变量

Bison: distinguish variables by type / YYERROR in GLR-parsers

parsing

bison

glr