Почему не удается выполнить синтаксический анализ этой программы с помощью BNFC?

Question

Дана следующая грамматика:

comment "/*" "*/" ;

TInt.  Type1 ::= "int" ;
TBool. Type1 ::= "bool" ;
coercions Type 1 ;


BTrue.   BExp   ::= "true" ;
BFalse.  BExp   ::= "false" ;

EOr.     Exp    ::= Exp  "||" Exp1 ;
EAnd.    Exp1   ::= Exp1 "&&" Exp2 ;
EEq.     Exp2   ::= Exp2 "==" Exp3 ;
ENeq.    Exp2   ::= Exp2 "!=" Exp3 ;
ELt.     Exp3   ::= Exp3 "<" Exp4 ;
EGt.     Exp3   ::= Exp3 ">" Exp4 ;
ELte.    Exp3   ::= Exp3 "<=" Exp4 ;
EGte.    Exp3   ::= Exp3 ">=" Exp4 ;
EAdd.    Exp4   ::= Exp4 "+" Exp5 ;
ESub.    Exp4   ::= Exp4 "-" Exp5 ;
EMul.    Exp5   ::= Exp5 "*" Exp6 ;
EDiv.    Exp5   ::= Exp5 "/" Exp6 ;
EMod.    Exp5   ::= Exp5 "%" Exp6 ;
ENot.    Exp6   ::= "!" Exp ;
EVar.    Exp8   ::= Ident ;
EInt.    Exp8   ::= Integer ;
EBool.   Exp8   ::= BExp ;
EIver.   Exp8   ::= "[" Exp "]" ;
coercions Exp 8 ;

Decl. Decl ::= Ident ":" Type ;
terminator Decl ";" ;


LIdent.  Lvalue ::= Ident ;

SBlock.  Stm ::= "{" [Decl] [Stm] "}" ;
SExp.    Stm ::= Exp ";" ;
SWhile.  Stm ::= "while" "(" Exp ")" Stm ;
SReturn. Stm ::= "return" Exp ";" ;
SAssign. Stm ::= Lvalue "=" Exp ";" ;
SPrint.  Stm ::= "print" Exp ";" ;
SIf.     Stm ::= "if" "(" Exp ")" "then" Stm "endif" ;
SIfElse. Stm ::= "if" "(" Exp ")" "then" Stm "else" Stm "endif" ;

terminator Stm "" ;

entrypoints Stm;

парсер, созданный с помощью bnfc, не может разобрать

{ c = a; }

хотя разбирает

c = a;

или же

{ print a; c = a; }

Я думаю, что это может быть проблемой, что парсер видит Ident и не знает, является ли это декларацией или оператором, LR и т. Д. (Все же одного токена lookeahed должно хватить??). Однако в документации BNFC я не нашел ни одной заметки, которая бы говорила, что она работает не для всех грамматик.

Есть идеи, как заставить это работать?

Answer 1

Я думаю, что вы получите отчет о сдвиге / уменьшении конфликта для этой грамматики, хотя то, где это сообщение об ошибке появляется, может зависеть от того, какой инструмент BNFC использует для генерации парсера. Насколько я знаю, все бэкэнд-инструменты имеют одинаковый подход к работе с конфликтами сдвига / уменьшения, который состоит в том, чтобы (1) предупредить пользователя о конфликте, а затем (2) разрешить конфликт в пользу сдвига.

Проблемное производство: (я пропустил аннотации типов, чтобы уменьшить беспорядок)

Stm ::= "{" [Decl] [Stm] "}" ;

Вот, [Decl] а также [Stm] являются макросами, которые автоматически создают определения для нетерминалов с этими именами (или что-то эквивалентное, что будет принято бэкэнд-инструментом). В частности, автоматически производимые производства:

[Decl] ::= /* empty */
       |   Decl ';' [Decl]

[Stm]  ::= /* empty */
       |   Stm [Stm]

(The ; в первом правиле это результат объявления "терминатора". Я не знаю, почему BNFC генерирует праворекурсивные правила, но именно так я интерпретирую справочное руководство - после очень быстрого взгляда - и я уверен, что у них есть свои причины. Для цели этой проблемы это не имеет значения.

Важно то, что оба Decl а также Stm можно начать с Ident, Итак, давайте предположим, что мы разбираем { id ...что может быть { id : ... или же { id = ..., но мы только прочитали { и жетон предвкушения id, Итак, есть две возможности:

1. id это начало Decl, Мы должны сдвинуть Ident и перейти к государству, которое включает в себя Decl → Ident • ':' Type

2. id это начало Stm, В этом случае нам нужно сократить производство [Decl] → • прежде чем мы сдвинемся Ident в Stm производство.

Таким образом, у нас есть конфликт сдвига / уменьшения, потому что мы не можем увидеть второй следующий токен (либо : или же =). И, как упомянуто выше, сдвиг обычно выигрывает в этом случае, поэтому анализатор LR(1) обязуется ожидать Decl, Как следствие, { a = b ; } не удастся.

Генератор синтаксического анализатора LR(2) вполне подойдет для этой грамматики, но найти его гораздо сложнее. (Современный бизон может производить анализаторы GLR, которые даже более мощные, чем LR(2), за счет небольшого дополнительного вычислительного времени, но не версии, требуемой инструментом BNFC.)

Возможные решения

1. Разрешить декларации смешиваться с заявлениями. Это мое предпочтение. Это просто, и многие программисты ожидают, что смогут объявить переменную при первом использовании, а не в начале включающего блока.

2. Сделайте объявление узнаваемым по первому токену, либо указав тип первым (как в C), либо добавив ключевое слово, такое как var (как в Javascript):

3. Измените грамматику, чтобы отложить взгляд. Всегда можно найти грамматику LR(1) для любого языка LR(k) (при условии, что k конечно), но это может быть утомительно. Уродливая, но эффективная альтернатива - продолжать лексическое сканирование до тех пор, пока : или какой-то другой непробельный символ найден, так что id : получает токенизацию как IdentDefine или что-то подобное. (Это решение используется bison, как это происходит. Это означает, что вы не можете поместить комментарии между идентификатором и следующим :, но есть несколько, если таковые имеются, веских причин, чтобы поместить комментарий в этом контексте.