0

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

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

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

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

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

（在 stringexpression 情况下只允许使用 string 类型的变量，在算术表达式情况下只允许使用 int 或 float 类型的变量）但这显然会导致 R/R 冲突，这是语言中固有的 -这是不可能解决的，因为语言是模棱两可的。

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

我读过关于 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;
      }
;

但野牛手册说

  1. 在确定性 GLR 操作期间，YYERROR 的效果与其在确定性解析器中的效果相同。
  2. 延迟动作的效果是类似的，但是错误的精确点是不确定的；相反，解析器恢复到确定性操作，选择一个未指定的堆栈以继续出现语法错误。
  3. 在非确定性解析期间的语义谓词（请参阅语义谓词）中，YYERROR 默默地修剪调用测试的解析。

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

  1. 不适用于此处，因为 GLR 解析不是确定性的
  2. 是我在上面的代码中的方式，但不应该这样做，因为 YYERROR 杀死的路径是完全随机的（如果我错了，请纠正我）
  3. 不会解决我的问题，因为语义谓词（不是语义动作！）必须在规则的开头（如果我错了，请纠正我），此时来自 TOK_IDENTIFIER 令牌的 yylval 不可访问（纠正我如果我错了），所以我无法查看符号表来查找变量的类型。

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

4

2 回答 2

1

注意：至少从 bison 3.0.1 开始，从 bison 3.0.5 开始，在处理语义谓词操作时存在一个错误，导致 bison#line在一行中间输出指令，导致编译失败。此答案中描述了一个简单的修复程序，并已提交到野牛存储库的maint分支。（从存储库构建野牛不适合胆小的人。但data/c.m4如果您不想自己编辑文件，从该存储库下载就足够了。）

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

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

语义动作可以出现在规则中的任何地方，并且在它们被归约时会立即执行，即使归约是模棱两可的。因为它们是乱序执行的，所以它们不能引用任何前面的语义动作产生的值（并且语义谓词本身没有语义值，即使它们占用了一个栈槽）。此外，因为它们作为可能不是最终解析的一部分的生产的一部分被有效地投机执行，所以它们不应该改变解析器状态。

语义谓词确实可以通过变量访问前瞻标记（如果有的话）yychar。如果yychar既不是YYEMPTY也不是YYEOF，则相关的语义值和位置信息分别在yylval和yylloc中。（请参阅前瞻令牌）。但是，在使用此功能之前必须小心；如果语法中的那个点没有歧义，那么野牛解析器很可能已经执行了语义谓词而没有读取前瞻标记。

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

  1. 为提高效率，GLR 解析器识别出解析中何时没有歧义，并在这些点使用普通的直接移位归约算法。在大多数语法中，歧义很少见并且可以快速解决，因此这种优化意味着在大多数解析中可以避免与维护多个备选方案相关的开销。在这种模式下（当然，如果可能存在歧义，则不适用）YYERROR会导致标准错误恢复，就像在移位归约解析器中一样，在动作归约点。

  2. 由于在解决歧义之前不会运行延迟操作，因此YYERROR延迟操作将有效地执行，就好像它处于确定性状态一样，如前一段所示。即使有自定义合并过程也是如此；如果正在进行自定义合并，则参与自定义合并的所有备选方案都将被丢弃。之后，将继续正常的错误恢复算法。我不认为错误恢复点是“随机的”，但是预测它会发生在哪里并不容易。

  3. 如上所述，语义谓词可以出现在规则中的任何位置，并且可以访问前瞻令牌（如果有的话）。（这里的 Bison 手册有点误导：语义谓词不能包含YYERROR因为YYERROR是语句的调用，而语义谓词块的内容是表达式。如果语义谓词的值为 false，则解析器执行YYERROR行动。）

实际上，这意味着您可以使用语义谓词而不是（或以及）动作，但基本上以您建议的方式：

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

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

  1. 它基本上是不可读的，至少对我来说，

  2. 更重要的是，就像显式转换一样，它不是类型安全的。

您应该声明令牌的语义类型：

%type <stringvalue> ID

这将允许野牛进行类型检查。

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

于 2018-06-13T18:12:33.823 回答
0

此处的示例有效，但是当我将它与Bison 的解决方案放在一起时：GLR-parsing of valid expression failed without error message我遇到了以下问题：

该变量可以由多个标识符确定。您可以有一个数组索引，也可以是不同对象的成员。我通过使用另一个非终端来模拟这种情况

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

但是当我现在有

arithmeticexpression : lvalue
stringexpression : 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)

我有一个歧义：相同的输入文本可以用两种不同的方式解析，但其中只有一种会有 value != 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;
}

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

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

老实说，我认为这是相当多的努力，如果野牛在尝试合并路径时测试语义谓词（至少是规则后面的那些），而不是在合并之前排除路径，这将是不必要的.

但至少这是可行的，而且比手动收集令牌并对其进行排序要省力得多，后者本来可以替代。

于 2018-08-21T08:41:57.193 回答