0

我真的陷入了 Goldparser 中的 Shift-Reduce 冲突。

我写了一个类似 PHP 的语法，理论上应该可以解析以下脚本：

public $Test = null;
protected $bDemo = true;

function Main()
{
}

private function Run()
{
}

在顶部，我想分配全局变量，然后是函数定义。

为了缩小问题范围，我将我的大语法减少到可以重现错误的以下几行。显然这是不完整的。这些函数没有参数，没有返回值，也没有语句......

"Start Symbol"   = <Script>

! ------------------------------------------------- Sets

{Name} = {Letter} + {Alphanumeric} + [_]

! ------------------------------------------------- Terminals

VarName        = '$'  {Name}*
FuncName       = {Name}*

! ------------------------------------------------- Rules

<Variable>       ::= VarName

<Value>          ::= 'null'
                   | 'true'
                   | 'false'

<Modifier>       ::= 'private'
                   | 'protected'
                   | 'public'

<ModifierOpt>    ::= <Modifier>
                   |

! ---------------

<GlbAssignVar>   ::= <ModifierOpt> <Variable> '=' <Value> ';'

<GlobalList>     ::= <GlobalList> <GlbAssignVar>
                   | <GlbAssignVar>

<GlobalListOpt>  ::= <GlobalList>
                   | 

! ---------------

<FuncDef>        ::= <ModifierOpt> 'function'  FuncName '('  ')' '{'  '}'

<FuncList>       ::= <FuncList> <FuncDef>
                   | <FuncDef>

<FuncListOpt>    ::= <FuncList>
                   |

! ---------------

<Script>         ::=  <GlobalListOpt> <FuncListOpt>

在构建 LALR 表时，Goldparser 告诉我：

“Shift-Reduce 冲突已修复为‘私人’、‘受保护’、‘公共’可以遵循已完成的规则​​，也可以进行转移。通过选择‘转移’操作而不是‘减少’来解决冲突。小心，一些部分语法可能无法访问。建议您尝试删除所有冲突。”

但它应用的修复使语法无法正常工作。在上面的示例中，尽管我将它们声明为可选的function Main()，但在需要 ' private'、' protected' 或 ' ' 的地方出现语法错误。public

当我<ModifierOpt>从<FuncDef>定义或定义中删除时，错误消失了<GlbAssignVar>。

我不知道如何解决这个问题。请帮忙！

4

1 回答 1

1

请记住，解析器生成器正在构建LALR(1)解析器，这意味着解析器需要能够在从左到右 ( LR) 扫描输入时决定是减少已经完成的产生式还是移动可能构成一个尚未完成的作品，只查看下一个(1)标记（这是可能被转移的标记）。

所以，假设我们只能看到第一个标记，private。现在，有两种可能性：

  1. 有一个非空GlobalList的，其中的第一个声明是private。

  2. 是空的GlobalList，但第一个函数声明FuncList是private。

这些对应于输入：

private $a = null;

private function a() {}

但我们只能看到令牌private。

我们正在制作的产品是：

<Script>         ::=  <GlobalListOpt> <FuncListOpt>

所以在第一种情况下，我们想要 shift private，因为它会成为 a 的一部分，GlbAssignVar它会启动 a GlobalList。但是，在第二种情况下，我们需要GlobalListOpt在移动 之前减少一个空private，这将是 a 的一部分FuncDef。GlobalListOpt ::= <empty>简而言之，我们需要只看令牌来决定是否减少private。而我们无法知道。

如果我们能生成一个 LALR(2) 语法，就没有问题，因为后面的记号private肯定会告诉我们它是私有全局还是私有函数。但是，由于此工具无法选择，因此我们需要避免做出决定，直到我们知道为止。

一个简单的解决方案是去掉GlobalListOpt可选性并将其折叠到 的定义中Script：

<Script>         ::=  <GlobalList> <FuncListOpt>
                   |  <FuncListOpt>

这是有效的，因为现在解析器总是可以移动private，即使它不知道最终会减少哪个生产。（这就是 LR 解析的魔力：解析器可以同时保持多个产生式处于活动状态；在实际减少产生式之前，它不需要承诺其中一个。）

当然，更简单的解决方案是只允许用户将全局定义与函数交错：

<Script>         ::= 
                   | <Script> <FuncDef>
                   | <Script> <GlbAssignVar>

它摆脱了FuncList,和FuncListOpt,但可能为用户提供了您认为过于灵活的东西。GlobalListGlobalListOpt

于 2014-03-28T02:48:20.297 回答