Почему у меня всегда конфликт сдвига / уменьшения с моими терминалами EOF / перенос строки? - PullRequest
Новая
       25

Почему у меня всегда конфликт сдвига / уменьшения с моими терминалами EOF / перенос строки?

0 голосов
/ 06 ноября 2018

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

Возьмите эту маленькую грамматику в качестве примера: 

(* {2 Tokens } *)
%token EOF
%token COLON PIPE SEMICOLON
%token <string> COUNT
%token <string> IDENTIFIER

%start <AST.t> script
%start <AST.statement> statement

%%
(* {2 Rules } *)

script:
 | it = separated_list(break, statement); break?; EOF { { statements = it } }
 ;

statement:
 | COLON*; count = COUNT?; cmd = command { AST.make_statement ~count ~cmd }
 ;

command:
 | it = IDENTIFIER { it }
 ;

break:
 | SEMICOLON { }
 ;

%%
Флаг

Менгира --explain создает это описание результирующего конфликта сдвига / уменьшения. К сожалению, я не могу сделать ни головы, ни хвосты: 

** Conflict (shift/reduce) in state 3.
** Token involved: SEMICOLON
** This state is reached from script after reading:

statement 

** The derivations that appear below have the following common factor:
** (The question mark symbol (?) represents the spot where the derivations begin to differ.)

script 
(?)

** In state 3, looking ahead at SEMICOLON, shifting is permitted
** because of the following sub-derivation:

loption(separated_nonempty_list(break,statement)) option(break) EOF 
separated_nonempty_list(break,statement) 
statement break separated_nonempty_list(break,statement) 
          . SEMICOLON 

** In state 3, looking ahead at SEMICOLON, reducing production
** separated_nonempty_list(break,statement) -> statement 
** is permitted because of the following sub-derivation:

loption(separated_nonempty_list(break,statement)) option(break) EOF // lookahead token appears because option(break) can begin with SEMICOLON
separated_nonempty_list(break,statement) // lookahead token is inherited
statement .

Я провел вечер, пытаясь откопать документацию о том, что на самом деле конфликт сдвига / уменьшения является , но я должен признать, что мне действительно трудно понять, что я ' Я читаю. Может ли кто-нибудь дать мне простое (ну, насколько это возможно) объяснение сдвига / уменьшения конфликтов? В частности, используя контекст приведенного выше примера?

1 Ответ

0 голосов
/ 06 ноября 2018

Проблема в том, что, глядя на SEMICOLON, анализатор не может решить, следует ли ему ожидать EOF или остальную часть списка. Причина в том, что вы используете break в качестве необязательного терминатора вместо разделителя.

Я предлагаю вам изменить основное правило: 

script:
 | it = optterm_list(break, statement); EOF { { statements = it } }
 ;

И определите комбинатор optterm_list самостоятельно, например: 

optterm_list(separator, X):
  | separator? {[]}
  | l=optterm_nonempty_list(separator, X) { l } 
optterm_nonempty_list(separator, X):
  | x = X separator? { [ x ] }
  | x = X
    separator
    xs = optterm_nonempty_list(separator, X)
     { x :: xs }
...