LR (1) Parser: почему добавление эпсилон-продукции вызывает конфликты r / r или s / r - PullRequest
Новая
       61

LR (1) Parser: почему добавление эпсилон-продукции вызывает конфликты r / r или s / r

1 голос
/ 20 апреля 2020

Я хотел создать ридер, который читает файлы конфигурации, аналогичные INI-файлам для mswin. Это упражнение, чтобы научить себя, используя генератор лексера / парсера, который я сделал. Грамматика: 

%lexer
HEADER ::= "\\[[0-9a-zA-Z]+\\]"
TRUE ::= "yes|true"
FALSE ::= "no|false"
ASSIGN ::= "="
OPTION_NAME ::= "[a-zA-Z][0-9a-zA-Z]*"
INT ::= "[0-9]+"
STRING ::= "\"(\\\"|[^\"])*\""
CODE ::= "<{(.*)}>"
BLANK ::= "[ \t\f]+" :ignore
COMMENT ::= "#[^\n\r]*(\r|\n)?" :ignore
NEWLINE ::= "\r|\n"
%parser
Options ::= OptionGroup Options | OptionGroup | @epsilon@
OptionGroup ::= HEADER NEWLINE OptionsList 
OptionsList ::= Option NEWLINE OptionsList | Option 
Option ::= OPTION_NAME ASSIGN OptionValue
OptionValue ::= TRUE | FALSE | INT | STRING | CODE

Проблема заключается в @epsilon@ продукции. Я добавил его, потому что хочу, чтобы мой читатель также принимал пустые файлы. Но у меня возникают конфликты, когда «OptionsList» или «OptionGroup» содержат продукцию epsilon. Я пытался переставить элементы в продуктах, но у меня возникают только конфликты (r / r или s / r, в зависимости от того, что я сделал), если я не удаляю эпсилон полностью из моей грамматики. Это устраняет проблему, но ... в моих логиках c один из 'OptionsList' или 'OptionGroup' должен содержать эпсилон, иначе моя цель принять пустые файлы не будет достигнута.

Мой генератор синтаксических анализаторов использует метод LR (1), поэтому я подумал, что могу использовать в своей грамматике произведения epsilon. Кажется, я хорош в написании генераторов, но не в построении безошибочных грамматик :(.

Должен ли я забыть о эпсилонах? Или моя грамматика принимает пустые входные данные, даже если нет производства эпсилонов?

1 Ответ

2 голосов
/ 20 апреля 2020

Ваше производство Options позволяет Options быть последовательностью OptionGroup s, начиная с пустого списка или списка, состоящего из одного элемента. Это, очевидно, неоднозначно, потому что список из ровно одного OptionGroup может быть:

  • Базовый случай OptionGroup
  • Базовый случай @epsilon@ с добавлением OptionGroup.

Короче, вместо 

Options ::= OptionGroup Options | OptionGroup | @epsilon@

вам нужен 

Options ::= OptionGroup Options | @epsilon@

, который соответствует точно тому же набору предложений, но однозначно.

В общих чертах вам обычно лучше писать рекурсивные правила для восходящих парсеров. Так я бы написал 

Options ::= Options OptionGroup | @epsilon@
...