代码之家 › 专栏 › 技术社区 › Alec Thilenius

LR(1)移位/减少消除歧义

lr1 rust

Alec Thilenius · 技术社区 · 6 年前

给定重复输入 BLOCK s,其中每个块都有重复 BEGIN EVENT 和 END EVENT 参赛作品( 结束事件 始终遵循 开始事件 ):

[TIMESTAMP] BLOCK
[TIMESTAMP] BEGIN EVENT
[TIMESTAMP] END EVENT
[TIMESTAMP] BEGIN EVENT
[TIMESTAMP] END EVENT
...
[TIMESTAMP] BLOCK

如何用lr(1)消除这种语法的歧义?我在用 LALRPOP ,最小的例子是:

Timestamp = "[TIMESTAMP]";
BlockHeader = Timestamp "BLOCK";
Begin = Timestamp "BEGIN" "EVENT";
End = Timestamp "END" "EVENT";

Block = BlockHeader (Begin End)+;
pub Blocks = Block*

因为lr(1)只能向前看一个标记,所以这种语法是含糊不清的,正如larpop乐于告诉您的那样(部分错误):

Local ambiguity detected

  The problem arises after having observed the following symbols in the input:
    BlockHeader (Begin End)+
  At that point, if the next token is a `"[TIMESTAMP]"`, then the parser can proceed in two different ways.

  First, the parser could execute the production at
  /home/<snip>.lalrpop:51:9: 51:32, which would consume
  the top 2 token(s) from the stack and produce a `Block`. This might then yield a parse tree like
    BlockHeader (Begin End)+ Block
    ââBlockâââââââââââââââââ¤     â
    ââBlock+ââââââââââââââââ     â
    ââBlock+ââââââââââââââââââââââ

  Alternatively, the parser could shift the `"[TIMESTAMP]"` token and later use it to construct a
  `Timestamp`. This might then yield a parse tree like
    (Begin End)+ "[TIMESTAMP]" "BEGIN" "EVENT" End
    â            ââTimestampââ               â   â
    â            ââBeginââââââââââââââââââââââ   â
    ââ(Begin End)+ââââââââââââââââââââââââââââââââ

我看到它告诉我,在分析一个blockheader之后,开始和结束它不能确定下一个标记是另一个开始,还是另一个块的开始。我在lr(1)中找不到消除这种歧义的方法,但我只能假设这是我缺乏理解,而不是lr(1)语法的继承限制?

1 回复 | 直到 6 年前

Chris Dodd 6 年前

不幸的是,如果不完全重新构造语法,这种“需要更多的前瞻性”问题很难解决,因为语法通常会丢失所需的输入结构,有时会接受原始语法将拒绝的退化输入。通常,您可以拒绝这些输入,并通过对解析树进行后处理来返回该结构,但这需要更多的工作。在您的案例中,语法:

Timestamp = "[TIMESTAMP]";
BlockHeader = Timestamp "BLOCK";
Begin = Timestamp "BEGIN" "EVENT";
End = Timestamp "END" "EVENT";
Event = Begin End;
Item = BlockHeader | Event;
pub Input = Item*

应该这样做,但问题是它会丢失块结构(而不是给您一个块头和事件的非结构化序列),并且它接受空块。通过对项目列表进行后处理,您可以轻松地处理这两个问题。

当所需的展望很小且有界时,另一种选择是在标记器中处理它。我不熟悉larpop,但是应该可以将 [TIMESTAMP] 带有紧跟关键字标记的标记(因此时间戳不会出现在语法中,而只是关键字的一个属性),在这种情况下,使用单个标记先行,一切都可以正常工作。