Определение грамматики jison приводит к неверному распознаванию токена

Недавно я нашел проект jison и изменил пример калькулятора с его сайта. ( http://zaach.github.io/jison/demos/calc/)

/* lexical grammar */
%lex
%%

"a"                   return 'TOKEN1'
"b"                   return 'TOKEN2'
<<EOF>>               return 'EOF'
.                     return 'INVALID'

/lex

%start letters

%% /* language grammar */

letters
    :
    | letters letter
    ;

letter
    : 'TOKEN1'
    | 'TOKEN2'
    ;

Анализ строки "aaabbbaaba" с помощью синтаксического анализатора, сгенерированного приведенным выше определением грамматики, приводит к

Parse error on line 1:
aaabbbaaba
^
Expecting 'TOKEN1', 'TOKEN2', got 'INVALID'

К сожалению не знаю почему TOKEN1 не найден правильно После удаления токена INVALID я получаю ошибку разбора

Unrecognized text.

Я нашел описание ошибки ассоциации, приводящей к аналогичному сообщению об ошибке, по проблеме с грамматикой Jison, странная ошибка сгенерировать dparser, но я не смог найти что-то похожее в своем коде.

Какое решение для этой проблемы?

Источник

1 ответ

Решение

Хороший вопрос.

jison В генераторе лексеров есть два режима: режим по умолчанию и немного больше flex -совместимый режим. Вы выбираете последний, поместив %options flex после %lex линия.

В режиме по умолчанию:

  1. Первый соответствующий шаблон выигрывает, даже если более поздний шаблон будет соответствовать более длинному токену; а также

  2. Шаблоны, которые заканчиваются буквой или цифрой, имеют неявный \b добавлен к ним, что ограничивает совпадение до конца на границе слова.

В flex В этом режиме шаблоны не изменяются, и применяется нормальное правило сгибания по длине. Однако сгенерированный лексер будет медленнее (см. Ниже).

Итак, в вашем определении лексера, "a" не будет соответствовать первому a во входной строке, потому что сгенерированный лексер фактически пытается соответствовать a\b - то есть, за которым следует слово граница.

Вы можете обойти эту проблему, просто заключив шаблон в круглые скобки:

("a")    { return 'TOKEN1'; }

или используя символьный класс вместо кавычки:

[a]      { return 'TOKEN1'; }

или добавив %options flex на ваш %lex раздел.

В порядке объяснения

jison, В отличие от flex, не строит ни одного лексера DFA. Вместо этого он преобразует каждый шаблон lex в закрепленное регулярное выражение javascript и при каждом запросе токена пробует все шаблоны, пока не найдет правильное соответствие.

Для реализации flex правило первого по длине матча, jison Генерируемый лексер должен пробовать каждое регулярное выражение для каждого токена, потому что он не может знать, какое совпадение самое длинное, пока не попробует их все. Правило "первого совпадения" может быть немного быстрее, особенно если общие шаблоны токенов помещаются в начале файла.

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

Следовательно, комбинация двух правил, описанных выше, означает, что обычная схема перечисления ключевых слов перед Identifier шаблон все еще будет работать. Тест границы слова предотвращает совпадение шаблонов ключевых слов с ложными префиксами.

Но если у вас много ключевых слов, это все еще много шаблонов, даже если большинство из них быстро потерпит неудачу. Так что вместо того, чтобы использовать flex конвенции:

"do"                         { return DO; }
"end"                        { return END; }
/* ... */
[[:alpha:]][[:alnum:]_]*     { return "ID"; }

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

/* Keywords and multicharacter operators in a single enormous pattern */
/* For jison mode, I added a manual \b because it won't be added 
 * automatically. In flex mode, that won't hurt, but it could be
 * removed.
 */
("do"|"else"|"end"|"if"|"then"|"while")\b|[<>!=]"=" { return yytext; }
[[:alpha:]][[:alnum:]_]*                        { return "ID"; }
[[:digit:]]+("."[[:digit:]]*)?                  { return "NUMBER"; }
[[:space:]]+                                    ;
/* All single character tokens use a fallback rule */
.                                               { return yytext; }

<<EOF>> правило

Много jison грамматики имеют явный <<EOF>> лексическое правило, которое возвращает некоторый токен как "EOF" или же "END_OF_FILE", Этот токен распознается явным дополненным началом производства, которое имеет return в своем действии:

%lex
%%
// ...
<<EOF>> { return "EOF"; }
/lex

%start input
%%
input: start EOF { return $1; }

start: /* The real start token */

Это jison специфическая идиома, которую многие считают плохим стилем flex/bison, Это позволяет сгенерированной грамматике возвращать фактическое значение, которое является результатом анализа.

Не просто добавить <<EOF>> Правило лексическим правилам. Если вы поставите свой собственный EOF токен, вы несете ответственность за его распознавание в парсере. Если парсер не имеет правила, которое соответствует EOF маркер, анализ не удастся.

Источник
Другие вопросы по тегам