Gnu Bison 转移/减少描述层次表达式的基于缩进的语法中的冲突

Question

我已经很长时间没有使用 Bison 了，所以我有可能在这里遗漏了一些简单的东西，但是，我无法弄清楚为什么以下语法会产生 shift / reduce 冲突。我认为下面的语法没有歧义。它的目的是解析像这样的表达式：

a b
  c d
    e f
  g h

as（在伪 AST 中）：

App 
    (App a b) 
    (Seq 
        [ App 
              (App c d) 
              (Seq [App e f])
        , (App g h)
        ]
    )

语法：

%token <Token> VAR
%token <Token> EOL

%token <Token> INDENT_INC
%token <Token> INDENT_DEC

%token <AST> CONS
%token <AST> WILDCARD
%type  <AST> expr
%type  <AST> subExpr
%type  <AST> block
%type  <AST> tok

%start program

%%
program:
  expr { result = ; }

expr:
  subExpr  {$$=;}
| subExpr EOL INDENT_INC block { $$ = AST.app(,); } 

subExpr:
  tok          {$$=;}
| subExpr tok  {$$ = AST.app(,); } 

block:
  expr  {$$=;}
| block EOL expr {$$=AST.seq(,);} // causes error

tok:
  VAR { $$ = AST.fromToken(); }
%%

错误只是2 shift/reduce conflicts。在调试解析器时，我们可以观察到：

Grammar

    0 $accept: program $end
    1 program: expr
    2 expr: subExpr
    3     | subExpr EOL INDENT_INC block
    4 subExpr: tok
    5        | subExpr tok
    6 block: expr
    7      | block EOL expr
    8 tok: VAR

[...]

State 4

    2 expr: subExpr .
    3     | subExpr . EOL INDENT_INC block
    5 subExpr: subExpr . tok

    VAR  shift, and go to state 1
    EOL  shift, and go to state 7

    EOL       [reduce using rule 2 (expr)]
    $default  reduce using rule 2 (expr)

    tok  go to state 8

[...]

State 11

    3 expr: subExpr EOL INDENT_INC block .
    7 block: block . EOL expr

    EOL  shift, and go to state 12

    EOL       [reduce using rule 3 (expr)]
    $default  reduce using rule 3 (expr)

老实说，我不确定歧义从何而来。如果您能就如何消除此类语法中的冲突提供任何帮助，我将不胜感激。

Answer 1

你的语法没有使用INDENT_DEC；否则，您无法知道缩进的 block 在哪里结束。

实际上，这就是那些 shift/reduce 冲突告诉你的。由于语法没有看到 INDENT_DEC，它无法区分在同一块中分隔两个 expr 的 EOL 和终止 block 的 EOL ].因此，EOL 是不明确的（前提是至少看到了一个 INDENT_INC）。

这里有一个简单的歧义演示。要解析的表达式是：

a EOL INDENT_INC b EOL INDENT_INC c EOL d

这里有两个最左边的推导，它们的不同之处在于 d 的嵌套位置（为了简单起见，我压缩了 subexpr ⇒ var ⇒ TOK 路径）：

# Here, d belongs to the outer subexpr (effectively, a single indent)
expr ⇒ subexpr EOL INDENT_INC block
     ⇒ TOK (a) EOL INDENT_INC block
     ⇒ TOK (a) EOL INDENT_INC block                          EOL expr
     ⇒ TOK (a) EOL INDENT_INC expr                           EOL expr
     ⇒ TOK (a) EOL INDENT_INC subexpr EOL INDENT_INC block   EOL expr
     ⇒ TOK (a) EOL INDENT_INC subexpr EOL INDENT_INC expr    EOL expr
     ⇒ TOK (a) EOL INDENT_INC TOK (b) EOL INDENT_INC subexpr EOL expr
     ⇒ TOK (a) EOL INDENT_INC TOK (b) EOL INDENT_INC TOK (c) EOL expr
     ⇒ TOK (a) EOL INDENT_INC TOK (b) EOL INDENT_INC TOK (c) EOL subexpr
     ⇒ TOK (a) EOL INDENT_INC TOK (b) EOL INDENT_INC TOK (c) EOL TOK (d)

# Here, d belongs to the inner subexpr (effectively two indents)
expr ⇒ subexpr EOL INDENT_INC block
     ⇒ TOK (a) EOL INDENT_INC block
     ⇒ TOK (a) EOL INDENT_INC expr
     ⇒ TOK (a) EOL INDENT_INC subexpr EOL INDENT_INC block
     ⇒ TOK (a) EOL INDENT_INC TOK (b) EOL INDENT_INC block
     ⇒ TOK (a) EOL INDENT_INC TOK (b) EOL INDENT_INC block   EOL expr
     ⇒ TOK (a) EOL INDENT_INC TOK (b) EOL INDENT_INC expr    EOL expr
     ⇒ TOK (a) EOL INDENT_INC TOK (b) EOL INDENT_INC subexpr EOL expr
     ⇒ TOK (a) EOL INDENT_INC TOK (b) EOL INDENT_INC TOK (c) EOL expr
     ⇒ TOK (a) EOL INDENT_INC TOK (b) EOL INDENT_INC TOK (c) EOL subexpr
     ⇒ TOK (a) EOL INDENT_INC TOK (b) EOL INDENT_INC TOK (c) EOL TOK (d)

所以语法确实有歧义。但是 shift/reduce 冲突并不直接指向歧义。他们指出了在没有看到 EOL 之后的符号的情况下决定是否减少 EOL 之前的构造的问题。这是 LR(1) 限制的本质：每次归约都必须在移动下一个符号之前进行，因此即使语法是明确的，如果你能看到足够远的未来，它仍然会有 shift/reduce 冲突如果减少决定可以采取任何一种方式。

Gnu Bison 转移/减少描述层次表达式的基于缩进的语法中的冲突

Gnu Bison shift / reduce conflicts in indentation-based grammar describing hierarchical expressions

parsing

gnu

bison

flex-lexer