LR(1) 解析器：为什么添加 epsilon 产生式会导致 r/r 或 s/r 冲突

Question

我想制作一个 reader 来读取类似于 mswin 的 INI 文件的配置文件。使用我制作的 lexer/parser 生成器自学是为了练习。语法是：

%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@制作上。我添加它是因为我希望我的 reader 也接受空文件。但是当 'OptionsList' 或 'OptionGroup' 包含 epsilon 产生式时，我会遇到冲突。我尝试重新排列作品中的元素，但我只会遇到冲突（r/r 或 s/r，具体取决于我所做的），除非我从我的语法中完全删除 epsilon。它消除了问题，但是......在我的逻辑中 'OptionsList' 或 'OptionGroup' 应该包含一个 epsilon，否则我接受空文件的目标没有达到.

我的解析器生成器使用 LR(1) 方法，所以我想我可以在语法中使用 epsilon 产生式。看来我擅长编写生成器，但不擅长构建无错误的语法:(。

我应该忘记 epsilons 吗？还是即使没有 epsilon 产生式，我的语法也接受空输入？

Answer 1

您的 Options 产生式允许 Options 是 OptionGroup 的序列，从空列表或由单个元素组成的列表开始。这显然是模棱两可的，因为只有一个 OptionGroup 的列表可能是：

基本情况OptionGroup
基本案例 @epsilon@ 添加了 OptionGroup。

简而言之，而不是

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

你需要

Options ::= OptionGroup Options | @epsilon@

完全匹配同一组句子，但毫不含糊。

一般而言，您通常最好为自下而上的解析器编写 左递归 规则。所以我会写

Options ::= Options OptionGroup | @epsilon@

LR(1) 解析器：为什么添加 epsilon 产生式会导致 r/r 或 s/r 冲突

LR(1) Parser: Why adding an epsilon production makes r/r or s/r conflicts

parsing

lr1

shift-reduce-conflict

reduce-reduce-conflict