Спецификация грамматики, разрешающая конфликты Shift/Reduce

Question

Я использую Jison (Bison) для создания простого языка разметки.Я явно новичок в этом, но небольшие изменения работают очень хорошо.Я просто не понимаю источник конфликта S/R.

Кажется неважным, что «Текст» возвращается двумя действиями лексера (с разными условиями запуска), и мне это нравится, потому что это, кажется, позволяет грамматике иметь меньше правил и потому что сообщения об ошибках пользователю единообразны.Я попытался сделать правило «Текст» общим независимо от контекста, а также попробовал дать каждому токену другое имя, но, похоже, это не оказывает никакого влияния на конфликты поддержки/сопротивления, когда все это вместе.

ПРЕДПОЛАГАЕТСЯ, что парсер создаст json-объект с открытым текстом, подмассивами и различными специальными узлами.

Спецификация:

/* lexical grammar */
%lex

%s bracketed

%%

<bracketed>(\\.|[^\\\,\[\]])+       { yytext = yytext.replace(/\\(.)/g, '$1'); return 'Text'; }
<INITIAL>(\\.|[^\\\[])+             { yytext = yytext.replace(/\\(.)/g, '$1'); return 'Text'; }
"["                                 { this.begin('bracketed'); return '['; }
"]"                                 { this.popState(); return ']'; }
","                                 return ','
<<EOF>>                             return 'END'

/lex

%start template

%%    

template
    : sentence END
    ;

sentence
    : /* empty */
    | sentence Text
    | sentence '[' ']'
    | sentence '[' dynamic ']'
    ;

dynamic
    : sentence
    /*| dynamic ',' sentence*/
    ;

Предупреждения:

Conflict in grammar: multiple actions possible when lookahead token is ] in state 5
- reduce by rule: sentence ->
- shift token (then go to state 6)

States with conflicts:
State 5
  sentence -> sentence [ .] #lookaheads= END Text [ ]
  sentence -> sentence [ .dynamic ] #lookaheads= END Text [ ]
  dynamic -> .sentence #lookaheads= ]
  sentence -> . #lookaheads= ] Text [
  sentence -> .sentence Text
  sentence -> .sentence [ ]
  sentence -> .sentence [ dynamic ]

Различные алгоритмы генераторов имеют те или иные проблемы, но, похоже, они все имеют проблемы.

Спасибо!

Answer 1

Конфликт в основе своей возникает из-за этих двух правил:

sentence: sentence '[' Text ']'
        | sentence '[' sentenceList ']'

Причина в том, что, увидев sentence и [ и глядя на следующий токен Text, синтаксический анализатор не знает, следует ли смещать Text, соответствующий первому правилу, или для его обработки Text как начало sentenceList собираюсь соответствовать второму правилу.

Теперь, если бы у вас был генератор синтаксического анализатора, который использует предварительный просмотр с двумя токенами, это не было бы проблемой, но Bison - это LALR(1) (1 - это просмотр с опережением на один токен).

Есть несколько вещей, которые вы можете попробовать:

• выполните дополнительный просмотр в лексере, чтобы отличить Text-followed-by-] от Text-not-followed-by-] как два разных токена, а затем перепишите правила, чтобы использовать оба этих токена.

• Используйте функцию %glr-parser от bison, чтобы использовать анализатор GLR.Это позволит проанализировать предложение в обоих направлениях, а затем отбросить то, которое не соответствует.

• рефакторинг грамматики, чтобы не требовался просмотр вперед с двумя токенами.

Одним из рефакторингов, который сработает в вашем случае, будет переписывание sentence правила, чтобы сделать их праворекурсивными, а не леворекурсивными:

sentence: /* empty */
        | Text sentence 
        | '[' ']' sentence
        | '[' Text ']' sentence
        | '[' sentenceList ']' sentence
        ;

Это позволяет избежать sentence (или любое другое правило, начинающееся с sentence такой как sentenceList) начать с нулевого уменьшения sentence: /*empty*/ правило.Таким образом, парсер может свободно перемещать Text в проблемном случае отложить сокращение до тех пор, пока не появится следующий токен.Однако это имеет последствия для использования памяти, поскольку в результате получается синтаксический анализатор, который по существу перемещает весь ввод в стек анализатора, а затем сокращает его по одному предложению за раз.

Еще один рефакторинг, который вы могли бы сделать, — это включить [Text] и [] конструирует в [sentenceList]:

sentence: /* empty */
        | sentence Text 
        | sentence '[' sentenceList ']'
        ;

sentenceList: sentence
            | sentenceList ',' sentence

Итак, теперь sentenceList одно или несколько предложений, разделенных запятыми (вместо двух и более), а в иске о sentence '[' sentenceList ']' правило, вы должны проверить sentenceList чтобы увидеть, было ли это два или более предложений, и действовать соответствующим образом.