要确定我的解析器是否正常工作,我需要找到一个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),并且最多可以给我一个简短的解释,说明如何由我自己确定,我将感到高兴。
非常感谢!
我非常确定它是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的本质,这正是分号是可选的结果。那不是投诉;语法是明确的,因此分号确实是多余的,不应强迫任何人键入冗余令牌:-)