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)解析器，可能是通过修改语法在适当的位置添加括号？
回答 1
Stack Overflow用户
发布于 2016-03-15 00:56:08
LR(0)解析器有一个弱点，即它们只能解析无前缀的语言，即语言中没有任何字符串是任何其他语言的前缀的语言。这通常使得解析这样的表达式有点棘手，因为像5这样的东西是5！的前缀。这也解释了为什么很难获得正确的关联运算符-给定如下的结果
S→F|F^S
解析器在看到F后会有一个shift/reduce冲突，因为它不能判断是扩展它还是再次reduce。这与前面提到的无前缀属性有关。
LR(0)的这一弱点是人们在实践中不太使用它的原因之一。SLR(1)和LALR(1)解析器通常可以解析这些语法，因为它们有一个先行标记，让它们决定是移位还是减少。在上面的例子中，解析器不会遇到shift/reduce冲突，因为在决定是否减少F或移位a^时，它们可以看到移位^，因为没有正确的字符串，^应该出现在S之后。
https://stackoverflow.com/questions/12174926
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号