Gnu Bison сдвиг / уменьшение конфликтов в основанной на отступах грамматике, описывающей иерархические выражения - PullRequest
Новая
       43

Gnu Bison сдвиг / уменьшение конфликтов в основанной на отступах грамматике, описывающей иерархические выражения

1 голос
/ 06 июня 2019

Я давно не пользуюсь Bison, поэтому есть шанс, что я здесь упускаю что-то простое, однако я не могу понять, почему следующая грамматика вызывает конфликты сдвиг / уменьшение.Я думаю, что следующая грамматика не является неоднозначной.Он предназначен для разбора таких выражений, как: 

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 = $1; }

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

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

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

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

Ошибка просто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)

И, честно говоря, я не уверен, откуда возникла двусмысленность.Я был бы благодарен за любую помощь в том, как устранить конфликты в такой грамматике.

1 Ответ

2 голосов
/ 06 июня 2019

Ваша грамматика не использует INDENT_DEC; без этого вы не можете знать, где заканчивается отступ block.

По сути, это то, что говорят вам эти конфликты сдвига / уменьшения. Так как грамматика не видит INDENT_DEC, она не может различить EOL, который разделяет два expr s в одном блоке, и EOL, который завершает block. Таким образом, 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)

Так что грамматика действительно неоднозначна. Но конфликты сдвига / уменьшения не указывают прямо на неопределенность. Они указывают на проблему принятия решения о том, уменьшать или нет конструкцию до EOL, не видя символа, следующего за EOL. В этом суть ограничения LR (1): каждое сокращение должно быть выполнено до сдвига следующего символа, поэтому даже если грамматика будет однозначной, если вы сможете увидеть достаточно далеко в будущем, у нее все еще будут конфликты сдвига / уменьшения, если Решение о сокращении может пойти в любую сторону.

...