Как исправить этот конфликт синтаксического анализа?

У меня есть небольшая грамматика, написанная на лимоне, которая вызывает конфликт синтаксического анализа.

Это часть грамматики, которая вызывает конфликт:

selection_statement ::= KWD_IF LPAREN expression RPAREN statement.
selection_statement ::= KWD_IF LPAREN expression RPAREN statement KWD_ELSE statement.

Я видел этот ответ, но он работает только для bison/yacc. Я не могу понять, как воспроизвести его в лимоне.

Каков наилучший способ разрешить этот конфликт синтаксического анализа?

Заранее спасибо.


parsing lemon
person CoffeeTurtle    schedule 13.08.2019    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Lemon реализует правила приоритета аналогичным образом, но не полностью идентична Bison, и эту функцию можно использовать для устранения "висячего else" shift/ уменьшить конфликт, с которым вы столкнулись, как это обычно применяется в бизонах.

Есть два основных различия между объявлениями приоритета Lemon и Bison:

  1. Bison предоставляет %precedence в качестве альтернативы %left, %right и %nonassoc. Однако %nonassoc обычно можно использовать везде, где %precedence было бы более подходящим.

  2. В Bison вы можете явно объявить приоритет продукции, используя %prec TERMINAL. В Lemon вы делаете то же самое, помещая [TERMINAL] после производства. (Это объясняется в разделе правил приоритета руководства, ссылка на которое приведена выше.)

Кроме того, Bison позволяет использовать строки в двойных кавычках для терминалов, что недоступно в Lemon.

Собрав это вместе, вы можете адаптировать решение Bison к Lemon следующим образом:

/* LEMON (non-terminals abbreviated) */             /* Bison (from linked answer) */
%nonassoc KWD_IF                                    %nonassoc "then"
%nonassoc KWD_ELSE                                  %nonassoc "else"
%%                                                  %%
sel: KWD_IF LPAREN exp RPAREN stm. [KWD_ELSE]       stm: "if" "(" exp ")" stm            %prec "then"
   | KWD_IF LPAREN exp RPAREN stm KWD_ELSE stm.        | "if" "(" exp ")" stm "else" stm

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

person rici    schedule 13.08.2019

arrow_upward
1
arrow_downward

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

Вы можете исправить это следующим образом:

statement ::= open_sel
statement ::= closed_sel
statement ::= other

open_sel ::= KWD_IF LPAREN expression RPAREN open_sel
open_sel ::= KWD_IF LPAREN expression RPAREN other

closed_sel ::= KWD_IF LPAREN expression RPAREN closed_sel
closed_sel ::= KWD_IF LPAREN expression RPAREN closed_sel KWD_ELSE statement
closed_sel ::= KWD_IF LPAREN expression RPAREN other KWD_ELSE statement

это сложно и суетливо, и становится намного хуже, если у вас есть несколько видов операторов, таких как if...else, поэтому люди обычно полагаются на разрешение конфликтов по умолчанию в генераторе парсера.

Авторы инструментов генератора синтаксических анализаторов знают это, поэтому почти каждый генератор синтаксических анализаторов имеет правила разрешения конфликтов, которые заставляют if...else работать без рефакторинга грамматики, подобного этому.

person Matt Timmermans    schedule 13.08.2019