LR(0)解析器中的后缀和右关联运算符



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

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

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

LR(0)解析器的弱点在于,它们只能解析无前缀语言,即语言中没有任何字符串是任何其他语言的前缀的语言。这通常会使解析这样的表达式变得有点棘手,因为像5这样的东西是5!的前缀!。这也解释了为什么在这样的产品中很难找到正确的关联运算符

S→F|F^S

解析器在看到一个F之后会有一个shift/reduce冲突,因为它无法判断是扩展还是再次减少。这与前面提到的无前缀属性有关。

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

最新更新