1

是否可以构造一个 LR(0) 解析器来解析具有前缀和后缀运算符的语言?例如,如果我有一个带有 +(加法)和 ! (阶乘)运算符通常优先于 1+3!应该是 1 + 3!= 1 + 6 = 7,但如果解析器是 LR(0),那么当它在堆栈上有 1+3 时,它肯定会减少而不是移位?

另外,右结合运算符会带来问题吗?例如,2^3^4 应该是 2^(3^4) 但同样,当解析器在堆栈上有 2^3 时,它如何知道减少或移位?

如果这不可能,是否还有办法使用 LR(0) 解析器,可能通过更改语法在适当的位置添加括号?

4

1 回答 1

1

LR(0) 解析器的弱点在于它们只能解析无前缀语言,即语言中没有字符串是任何其他语言的前缀的语言。这通常使得解析这样的表达式有点棘手,因为像 5 是 5! 的前缀。这也解释了为什么很难获得右关联运算符 - 给定一个像

S → F | F ^ 小号

解析器在看到 F 后将发生移位/缩减冲突,因为它无法判断是扩展它还是再次缩减。这与前面提到的无前缀属性有关。

LR(0) 的这个弱点是人们在实践中很少使用它的原因之一。SLR(1) 和 LALR(1) 解析器通常可以解析这些文法,因为它们有一个前瞻标记,可以让它们决定是移位还是归约。在上述情况下,解析器不会遇到移位/缩减冲突,因为在决定是缩减 F 还是移位 ^ 时,他们可以看到移位 ^,因为在 S 之后应该出现 ^ 的位置没有正确的字符串。

于 2016-03-14T16:56:07.637 回答