Преобразование расширенной BNF в грамматику Bison, но с ошибками сдвига/уменьшения

Фон

Я работаю над компилятором для латексного языка. Я уже написал файл lex, и пока он работает так, как должен. Однако теперь, когда я работаю над грамматикой в ​​файле .y, у меня возникли проблемы.

Проблема

Я воспроизвел часть грамматики, которая, как я считаю, отвечает за то, что поставила меня в тупик:

%start document
%%
document: BEGINDOCUMENT documentbody ENDDOCUMENT;
documentbody: contentseq | ws MAKETITLE contentseq | MAKETITLE contentseq;
contentseq: | contentseq content;
content: STRING | ws;
ws: WHITESPACE;

Пробелы в этом контексте — это, по сути, любое сочетание пробелов, табуляций и новых строк.

Насколько я понял из файла y.output, ошибка сдвига/уменьшения возникает из-за правила

documentbody: ... | ws MAKETITLE contentseq | ...

Учитывая токен WHITESPACE, Bison не знает, является ли он частью «контента» терминала или вместо него будет следовать токен MAKETITLE. Оба являются абсолютно допустимыми входными данными, и я не уверен, как решить эту проблему.

Для ясности парафраз оригинальной спецификации EBNF:

document: BEGINDOCUMENT [ws] [MAKETITLE] contentseq ENDDOCUMENT

Другими словами, терминал ws и MAKETITLE необязательны.

Пример ввода

BEGINDOCUMENT WHITESPACE MAKETITLE STRING ENDDOCUMENT
BEGINDOCUMENT WHITESPACE STRING ENDDOCUMENT
BEGINDOCUMENT MAKETITLE STRING ENDDOCUMENT
BEGINDOCUMENT STRING ENDDOCUMENT

Все вышеперечисленное должно быть принято грамматикой.

Что я пробовал

Я знаю, что многие конфликты можно сгладить с помощью приоритета, но ничто из того, что я пробовал в этом ключе, не сработало. Я пробовал назначать маркерам MAKETITLE и WHITESPACE любой приоритет, но это не решило проблему.

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

Одно из решений, о котором я думал, но не пробовал, - это возиться с файлом lex, но это кажется довольно странным решением, и я бы предпочел найти какой-нибудь способ сделать это в yacc.


parsing ebnf yacc bison
person NMR-3    schedule 25.07.2018    source источник
comment
Я вообще не вижу смысла в пробелах в грамматике. Просто удалите его. Пусть лексер потребляет его.   -  person user207421    schedule 26.07.2018

Ответы (2)


arrow_upward
2
arrow_downward

Конфликт в основном возникает из-за обнуления contentseq. Это заставляет синтаксический анализатор распознавать пустой contentseq до того, как он распознает более длинный contentseq. И это приводит к конфликту, когда ввод начинается с BEGINDOCUMENT WHITESPACE, потому что в точке перед WHITESPACE неизвестно, нужно ли уменьшать это пустое contentseq.

Вы можете легко решить эту проблему, сделав contentseq необнуляемым (contentseq: content | contentseq content) за счет необходимости явно обрабатывать пропущенные последовательности:

documentbody: %empty | contentseq | maketitle optionalcs
contentseq: content | contentseq content
optionalcs: %empty | contentseq
maketitle: WHITESPACE MAKETITLE | MAKETITLE

Это общая проблема с преобразованием необязательного синтаксиса EBNF [ x ], особенно когда x повторяется. Вы не всегда можете полагаться на определение optional-x; вам часто приходится создавать две правые части, одну с x, а другую без.

Я не вижу смысла в ws: WHITESPACE; вы можете просто использовать токен WHITESPACE вместо нетерминала ws. Если ваша грамматика сложнее, чем то, что вы показываете, этот нетерминал может вызвать конфликт, но я не вижу никакой двусмысленности в том, что вы вставили. Тем не менее, в приведенном выше примере решения я удалил избыточный нетерминал.

person rici    schedule 25.07.2018

arrow_upward
0
arrow_downward

Лично я предпочитаю избегать трюков, специфичных для этого инструмента, и определять грамматику для более точного описания того, что мы хотим распознать. Я считаю, что грамматика в этом порядке распознает документы, которые вы хотите:

%start document
%token BEGINDOCUMENT ENDDOCUMENT MAKETITLE STRING WS
%%
document: BEGINDOCUMENT documentbody ENDDOCUMENT
        ;

documentbody: prefix title contents
            ;

prefix: 
        | WS
        ;

title: 
    | MAKETITLE
    ;

contents: 
        | STRING contentseq
        ;

contentseq: 
          | contentseq content
          ;

content: STRING 
        | WS
        ;

Итак, мы начинаем с необязательного префикса некоторого пробела. Затем следует необязательный заголовок. За ним следует содержимое, которое (поскольку мы уже распознали начальный пробел) либо пусто, либо представляет собой строку, за которой следуют либо строки, либо пробелы.

Простой, понятный и легкий для понимания практически всем (конечно, при условии, что они вообще распознают нотацию yacc).

person Jerry Coffin    schedule 30.08.2018