Persistent Shift - 减少 Goldparser 中的冲突 [英] Persistent Shift - Reduce Conflict in Goldparser

问题描述

我真的被 Goldparser 中的 Shift-Reduce 冲突所困扰.

I'm really stuck with a Shift-Reduce conflict in Goldparser.

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

I wrote a PHP-like grammar that theoretically should be able to parse the following script:

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

function Main()
{
}

private function Run()
{
}

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

At the top I want to assign the global variables and after that come the function definitions.

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

To narrow down the problem I reduced my large grammar to the following lines which can reproduce the error. Obviously this is incomplete. The functions have no parameters, no return value and no statements...

"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 告诉我:

When building the LALR Table Goldparser tells me:

Shift-Reduce 冲突已修复'private', 'protected', 'public' 可以遵循完整的规则，也可以移动.通过选择转移"而不是减少"来解决冲突.请注意，某些部分语法可能无法访问.建议您尝试删除所有冲突."

但它应用的修复使得语法无法正常工作.在上面的例子中，我在 function Main() 处得到一个语法错误，它需要一个 'private'、'protected' 或 '>public' 虽然我将它们声明为可选的.

But the fix it applies makes that the grammar does not work correctly. In the above example I get a syntax error at function Main() where it expects a 'private', 'protected' or 'public' although I declared them as optional.

当我从 定义或 中删除 时，错误消失定义.

The error disappears when I remove the <ModifierOpt> from either the <FuncDef> definition or from the <GlbAssignVar> definition.

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

I have no idea how to solve this. Please help!

推荐答案

记住解析器生成器正在构建一个 LALR(1) 解析器，这意味着解析器需要能够决定同时从左到右扫描输入 (LR) 是否减少已完成的生产或移动可能构成尚未完成的生产的一部分的标记，只查看下一个 (1) 标记(这是可能被移位的标记).

Remember that the parser generator is building an LALR(1) parser, which means that the parser needs to be able to decide while scanning the input left-to-right (LR) whether to reduce an already-completed production or to shift a token which might form part of a not-already-completed production, looking only at the next (1) tokens (which is the token which might be shifted).

所以，假设我们只能看到第一个令牌，private.现在，有几种可能性:

So, let's suppose we can see only the first token, private. Now, there are a couple of possibilities:

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

1. There is a non-empty GlobalList, and the first declaration in it is private.

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

The GlobalList is empty but the first function declaration in the FuncList is private.

这些对应于输入:

private $a = null;

private function a() {}

但我们只能看到令牌private.

我们正在进行的制作是:

The production we're working on is:

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

因此，在第一种情况下，我们想要移动 private，因为它将构成 GlbAssignVar 的一部分，它将启动一个 GlobalList.但是，在第二种情况下，我们需要在移动 private 之前减少一个空的 GlobalListOpt，它将成为 FuncDef 的一部分.简而言之，我们需要决定是否减少GlobalListOpt ::= ，同时只查看令牌private.我们不知道.

So in the first case, we want to shift private, since it will form part of a GlbAssignVar which will start a GlobalList. In the second case, though, we need to reduce an empty GlobalListOpt before shifting the private, which will be part of a FuncDef. In short, we need to decide whether or not to reduce GlobalListOpt ::= <empty> while looking only at the token private. And we can't know.

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

If we could generate an LALR(2) grammar, there would be no problem, because the token following private will definitely tell us whether it's a private global or a private function. But since that's not an option with this tool, we need to avoid making the decision until we know.

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

A simple solution is to get rid of GlobalListOpt and fold the optionality into the definition of Script:

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

这是有效的，因为现在解析器总是可以移动 private，即使它不知道最终会减少哪个产品.(这就是 LR 解析的神奇之处:解析器可以同时保持多个生成式处于活动状态；在生成式实际减少之前，它不需要提交一个或另一个.)

This works because now the parser can always shift the private, even though it doesn't know which production will eventually be reduced. (That's the magic of LR parsing: the parser can keep several productions active at the same time; it doesn't need to commit to one or the other until the production is actually reduced.)

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

Of course, a simpler solution would be to just allow the user to interleave global definitions with functions:

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

摆脱了 FuncList、FuncListOpt、GlobalList 和 GlobalListOpt，但可能为用户提供什么你认为灵活性太大了.

which gets rid of FuncList, FuncListOpt, GlobalList and GlobalListOpt, but possibly provides the user with what you consider to be too much flexibility.

这篇关于Persistent Shift - 减少 Goldparser 中的冲突的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！