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

Question

Фон

Я работаю над компилятором для латексоподобного языка. Я уже написал файл 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.

Answer 1

Конфликт в основном является результатом обнуляемости 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 не-терминал. Если ваша грамматика сложнее, чем то, что вы показываете, этот нетерминал может вызвать конфликт, но я не вижу никакой двусмысленности в том, что вы вставили. Тем не менее, в приведенном выше примере решения я удалил избыточный нетерминал.

Answer 2

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

%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).