这是LR(2)语法,如何确定?

问题描述 投票:0回答:1

要确定我的解析器是否正常工作,我需要找到一个lr(2+)语法。经过快速研究,我发现了这种语法,我相信它是lr(2)。但是,我不确定如何确定。

Terminals: b, e, o, r, s
NonTerminals: A, B, E, Q, SL
Start: P
Productions:
P -> A
A -> E B SL E | b e
B -> b | o r
E -> e | Ɛ
SL -> s SL | s

[如果有人能够确认或否认此语法为lr(2),并且最多可以给我一个简短的解释,说明如何由我自己确定,我将感到高兴。

非常感谢!

parsing grammar computation-theory lr
1个回答
0
投票

我非常确定它是LR(2),但是我没有方便的LR(2)解析器生成器来测试它,这将是进行测试的最终方法。当然,您可以手动生成解析器表。它不是那么复杂的语法,因此它不会花费您太多时间。

肯定不是LR(1),从一对输入中可以看出:

b e
b s e

最左边的派生是:

P->A->b e
P->E B SL E->B SL E->b SL E->b s E->b s e

因此,在解析开始时,解析器可以移动b以便跟随第一个派生链,也可以将空序列减少为E以便进行第二个派生链。需要第二个令牌才能在这两个选项之间进行选择,因此至少需要提前2个。

作为旁注,为LR(2)语法挖掘StackOverflow应该非常简单;他们不时提出疑问。我通过搜索LALR(2)找到了一些:(我在site:stackoverflow.com上使用了Google搜索,因为SO自己的搜索引擎在不是单词的搜索模式上做得不好。不是说Google很好,但是做得更好。)

Solving bison conflict over 2nd lookahead

Solving small shift reduce conflict

Persistent Shift - Reduce Conflict in Goldparser

How to reduce parser stack or 'unshift' the current token depending on what follows?

我没有验证那些问题和答案中的主张,还有其他一些问题似乎没有得到明确的结果。

最经典的LALR(2)语法是Yacc本身的语法,具有讽刺意味。这是一个简化的版本:

grammar: %empty | grammar production
production: ID ':' symbols
symbols: %empty | symbols symbol
symbol: ID | QUOTED_LITERAL

该简单的语法省略了动作和可选的分号。但是,它抓住了语法的LALR(2)-ness的本质,这正是分号是可选的结果。那不是投诉;语法是明确的,因此分号确实是多余的,不应强迫任何人键入冗余令牌:-)

© www.soinside.com 2019 - 2024. All rights reserved.