时间戳

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

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

问题描述

我想制作一个阅读器，它可以读取类似于 mswin 的 INI 文件的配置文件。使用我制作的词法分析器/解析器生成器自学是为了锻炼。语法是：

%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，取决于我所做的），除非我从语法中完全删除 epsilon。它消除了这个问题，但是......在我的逻辑中，“OptionsList”或“OptionGroup”之一应该包含一个 epsilon，否则我接受空文件的目标就不会实现。

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

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

标签： parsingshift-reduce-conflictreduce-reduce-conflictlr1

解决方案

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

  • 基本情况OptionGroup
  • @epsilon@添加了 OptionGroup.

简而言之，而不是

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

你需要

Options ::= OptionGroup Options | @epsilon@

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

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

Options ::= Options OptionGroup | @epsilon@

推荐阅读