Уменьшите / уменьшите конфликт в грамматике клика в jison

Question

Я работаю над компилятором языка клик, используя пакет Jison. Я пошел очень хорошо, пока я не ввел классы, таким образом, Type может быть LITERAL сейчас. Вот упрощенная грамматика:

%lex

%%
\s+                       /* skip whitespace */

int                       return 'INTEGER'
string                    return 'STRING'
boolean                   return 'BOOLEAN'
void                      return 'VOID'
[0-9]+                    return 'NUMBER'
[a-zA-Z_][0-9a-zA-Z_]*    return 'LITERAL'
"--"                      return 'DECR'
<<EOF>>                   return 'EOF'
"="                       return '='
";"                       return ';'


/lex

%%

Program
  : EOF
  | Stmt EOF
  ;

Stmt
  : Type Ident ';'
  | Ident '=' NUMBER ';'
  ;

Type
  : INTEGER
  | STRING
  | BOOLEAN
  | LITERAL
  | VOID
  ;

Ident
  : LITERAL
  ;

И конфликт Джизона:

Conflict in grammar: multiple actions possible when lookahead token is LITERAL in state 10
- reduce by rule: Ident -> LITERAL
- reduce by rule: Type -> LITERAL
Conflict in grammar: multiple actions possible when lookahead token is = in state 10
- reduce by rule: Ident -> LITERAL
- reduce by rule: Type -> LITERAL

States with conflicts:
State 10
  Type -> LITERAL . #lookaheads= LITERAL =
  Ident -> LITERAL . #lookaheads= LITERAL =

Я нашел довольно похожий вопрос, на который не было ответа, есть ли у кого-нибудь подсказки, как решить эту проблему?

Answer 1

Это очевидно ошибка в jison, так как грамматика, безусловно, LALR(1), и обрабатывается без проблем бизоном. По-видимому, Jison неправильно вычисляет прогноз состояния, в котором возникает конфликт. (Обновление: похоже, ошибка 205, о которой сообщалось в январе 2014 года.)

Если вы попросите jison создать синтаксический анализатор LR (1) вместо грамматики LALR(1), тогда он правильно вычислит прогнозные значения, и грамматика пройдет без предупреждений. Однако я не думаю, что это устойчивое решение.

Вот еще один обходной путь. Decl а также Assign производства не нужны; "исправить" было удалить LITERAL от Type и добавить отдельное производство для него.

Program
  : EOF
  | Stmt EOF
  ;

Decl
  : Type Ident ';'
  | LITERAL Ident ';'
  ;

Assign
  : Ident '=' NUMBER ';'
  ;

Stmt
  : Decl
  | Assign
  ;

Type
  : INTEGER
  | STRING
  | BOOLEAN
  | VOID
  ;

Ident
  : LITERAL
  ;

Возможно, вы захотите рассмотреть возможность признания нескольких утверждений:

Program
  : EOF
  | Stmts EOF
  ;

Stmts
  : Stmt
  | Stmts Stmt
  ;