Парсер Jison останавливается после первого правила

Question

У меня есть простой формат файла, который я хочу проанализировать с помощью генератора разбора jison. Этот файл может состоять из нескольких выражений в произвольном порядке и количестве. Вот файл jison для парсера:

/* lexical grammar */
%lex

%%

\s+                   /* skip whitespace */
\"(\\.|[^"])*\"          return 'STRING'

File\s*Version\s*\:      return 'FILEVERSION'
[0-9]+("."[0-9]+)?\b     return 'NUMBER'
<<EOF>>                  return 'EOF'
.                        return 'INVALID'

/lex

%start expressions

%% /* language grammar */

expressions
    : EOF
    | e expressions EOF
    ;

e
    : STRING
    | FILEID 
    ;

FILEID
    : FILEVERSION NUMBER { return $1 + $2; }
    ;

Для простоты я сократил файл, чтобы в нем были только строки и выражения идентификатора файла.

Моя проблема в том, что сгенерированный синтаксический анализатор, кажется, распознает только одно или два полных выражения, если второе выражение состоит только из одной строки, подобной токену. Например:

Версия файла: 1.0

Будет проанализирован, или

Версия файла: 1.0 "My String"

Также будет разобрано, но для

Версия файла: 1.0 "Моя строка" "Не проанализированная строка"

последняя строка не будет проанализирована.

Я пробовал этот код с отладчиком jison и на самой странице jison, но обе страницы показывают одинаковые результаты.

Мои предложения по проблеме:

1. Некоторые ошибки лексера (регулярное выражение)
2. Некоторая грамматическая ошибка (левая-правая-рекурсия)
3. Некоторое действие отсутствует в синтаксическом анализаторе (вроде { $$ = $1;})
4. Некоторая магия бизонов / джизонов

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

Answer 1

Непосредственная проблема заключается в том, что вы return от FILEID производство. return возвращает, поэтому анализ заканчивается возвращенным значением. Обычно семантические правила должны предоставлять свой результат путем присвоения переменной $$, (Это не обязательно для "правил модуля", где справа есть только один символ; перед выполнением действия парсер выполняет $$ = $1так что, если это то, что вы хотите, вы можете просто пропустить действие, как вы делаете в ваших двух FILEID правила.)

Кроме того, ваш expressions производство ничего не делает с $2, так что даже если вы исправите первую проблему, вы все равно увидите только одну e в результате.

Ваш expressions производство также неверно, так как оно требует EOF знак для каждого eВ дополнение к EOF из базового варианта. Рассмотрим, как работают производства:

expressions -> e expressions EOF
            -> e e expressions EOF EOF
            -> e e e expressions EOF EOF EOF
            -> e e e EOF EOF EOF EOF

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

Наконец, вам нужно вернуть окончательное значение, когда вы действительно достигнете конца ввода. В jison для этого обычно требуется явное правило запуска, семантическое действие которого return,

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

%start prog
%%
prog   : exprs EOF          { return $1; }
       ;
exprs  :                    { $$ = []; }
       | exprs expr         { $$.push($2); }
       ;
expr   : file_id
       | STRING
       ;
file_id: FILEVERSION NUMBER { $$ = $1 + $2; }
       ;

---

Одно замечание о вашем регулярном выражении для соответствующих строк:

\"(\\.|[^"])*\"          return 'STRING'

Хотя он, очевидно, работает в javascript (в основном; см. Ниже), он будет содержать ошибку в flex (или в Posix-совместимой библиотеке регулярных выражений). Это в основном работает в JavaScript, потому что оператор чередования регулярных выражений JavaScript | заказан; если первая альтернатива совпадает, вторая альтернатива никогда не пробуется, если остальная часть шаблона не совпадает (и в этом случае ошибка будет вызвана).

Но в (f)lex оператор чередования замечает все совпадающие альтернативы и в итоге выбирает максимально длинное совпадение. Результатом является то, что при сопоставлении "\\"...", flex будет соответствовать токену до третьей кавычки, используя [^"] соответствовать первому \, а затем \\. чтобы соответствовать \". Это позволяет ему продолжать искать заключительную цитату.

Легко написать регулярное выражение, чтобы оно работало с любой семантикой, и я настоятельно рекомендую сделать это в случае, если вы когда-нибудь захотите перейти на другой генератор синтаксического анализатора, просто убедившись, что \ не соответствует [^"]:

\"(\\.|[^\\"])*\"        return 'STRING'

Это изменение также исправит небольшую ошибку, даже в JavaScript, которая "\" считается допустимым строковым токеном, если это последняя строка во входных данных. В этом случае javascript сначала будет использовать \\. соответствовать \", но как только он это сделает, он не найдет закрывающей кавычки. Затем он вернется и попытается найти соответствие с [^"], что будет соответствовать \, что позволит кавычке быть признанной в качестве закрывающей кавычки.