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

У меня есть простой формат файла, который я хочу проанализировать с помощью генератора парсеров 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 "Моя строка"

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

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

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

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

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

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

Я не гуру ebnf-parser, поэтому, пожалуйста, отвечайте как можно проще.


person tomvodi    schedule 27.11.2015    source источник


Ответы (1)


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

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

Ваше производство expressions также неверно, так как для каждого e требуется один токен EOF в дополнение к 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 сначала будет использовать \\. для сопоставления \", но как только он это сделает, он не найдет закрывающей кавычки. Затем он вернется и попытается сопоставить с [^"] , который будет соответствовать \, что позволит распознавать цитату как закрывающую.

person rici    schedule 27.11.2015
comment
Вау, большое спасибо за такой четкий и исчерпывающий ответ! - person tomvodi; 27.11.2015