Конфликт при разборе набора выражений

Question

Я хотел бы разобрать набор выражений: R[3]C, R[2]C, R[3]C-R[2]C... Есть конфликт, который я не могу решить...

Вот часть lexer.mll:

  rule token = parse
  | 'R'            { R }
  | 'C'            { C }
  | "RC"           { RC }
  | ['0'-'9']+ as lxm { INTEGER (int_of_string lxm) }
  | '+'            { PLUS }
  | '-'            { MINUS }
  | '['            { LBRACKET }
  | ']'            { RBRACKET }
  | eof            { EOF }
  ...

Часть parser.mly:

main:
   e_expression EOF                { $1 };

e_expression:
| ec = e_cell { EE_rc (Rc.Cell ec) }
| e_expression MINUS e_expression { EE_string_EEL ("MINUS", [$1; $3]) }

e_cell:
| R LBRACKET r = index RBRACKET C c = index { (Rc.I_relative r, Rc.I_absolute c) }
| R LBRACKET r = index RBRACKET C { (Rc.I_relative r, Rc.I_relative 0) }

index:
| INTEGER { $1 }
| MINUS INTEGER { Printf.printf "%n\n" 8; 0 - $2 }

Этот код любопытно не работает с R[3]C-R[2]C, вот parser.conflicts, что я не могу понять.

Если я прокомментирую строку строки | R LBRACKET r = index RBRACKET C c = index ... в e_cellкод может разобрать R[3]C-R[2]C, где 3 а также 2 являются index, `R[3]C а также R[2]C являются e_cell, а также R[3]C-R[2]C является e_expression,

Кто-нибудь может помочь?

Answer 1

Таким образом, проблема заключается в том, что когда он видит маркер "-" после a ], анализатор не уверен, создает ли он индекс или разделяет два выражения.

т.е. когда синтаксический анализатор достигает R[3]C-, он не уверен, нужно ли ему ждать, пока INTEGER завершит e_cell и уменьшит или уменьшит сейчас и начнет работу над другим e_expression.

Лучшим способом решения этой проблемы, вероятно, будет перемещение отрицательного целочисленного кода в лексер. У меня нет удобной установки ocamllex, но я думаю, что изменение

['0'-'9']+

в

'-'? ['0'-'9']+ 

будет работать, а затем удалить регистр отрицательного целого числа из индекса (очевидно, это вызовет проблему с оператором Printf, но вы можете сделать внутреннюю логику более сложной, чтобы учесть это.

Answer 2

Ваша грамматика не LALR(1), На самом деле, это даже не LR(1),

Считайте следующие два действительными e_expressions:

R[1]C-R[2]C
R[1]C-1-R[2]C

В первом случае, после того как мы сдвинули Cмы достигнем следующего:

R [ index ] C -R[2]C

и тогда мы хотим уменьшить его:

e_cell -R[2]C

и уменьшите снова до

e_expression -R[2]C

а потом

e_expression - e_expression

Во втором случае мы доберемся до:

R [ index ] C -1-R[2]C 

а потом

R [ index ] C - 1-R[2]C
R [ index ] C index -R[2]C
e_cell -R[2]C

(на данный момент мы достигли позиции, аналогичной первой, поэтому я пропущу следующие шаги).

Итак, после того как мы сдвинем Cпредвкушение -и нам нужно либо:

1. уменьшить R [ index ] C в e_cell, или же

2. сдвинуть -, давая R [ index ] C -

Мы не можем сказать, что без еще одного взгляда: следующий токен должен быть либо R (случай 1) или INTEGER (случай 2).

Таким образом, мы можем сказать, что грамматика - это LALR(2), за исключением того, что существует еще один конфликт с уменьшением сдвига относительно знака минус, который делает грамматику неоднозначной и, следовательно, не LALR(k) для любого k. Возможно, вы уже имели дело с этим, используя объявления приоритетов операторов, но на всякий случай:

Предположим, вы достигли:

e_expression - e_expression

и предвкушение -, Теперь это может уменьшить e_expression - e_expression в e_expression а затем сдвинуть -, в результате чего:

e_expression -

Или это может просто сдвинуть -:

e_expression - e_expression -

Независимо от того, сколько прямого контекста мы читаем, невозможно выбрать между этими двумя, потому что они оба приводят к действительным анализам. Первый разбор сделаю - левоассоциативная, а вторая правосторонняя.

Если вы не решите это с помощью деклараций предшествования, вы можете выбрать одно из следующих, вместо e_expression: e_expression MINUS e_expression:

e_expression: e_cell MINUS e_expression
e_expression: e_expression MINUS e_cell

Теперь, как решить оригинальную проблему:)

Самое простое решение, если - в -1 можно рассматривать как часть отрицательного целого числа, это позволить лексеру справиться с этим. Тогда парсер не увидит MINUS в R[-1]C-1поэтому он не будет пытаться уменьшить R[-1]C,

Другим решением было бы использование парсера GLR (очевидно, для OCaml он есть, но я ничего не знаю об этом).

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