parsing - LALR(1) 解析器中的冲突解决

标签 parsing grammar lalr

关于LALR(1)解析器冲突的一些问题,主要涉及解析的细节:

  • 根据教科书中描述的不同 LALR(1) 解析器,如果遇到 shift/reduce 冲突,那么这表明语法不是 LALR(1) 开始,对吗?
  • 减少/减少冲突可能出现在有效 LALR(1) 文法,因为从 LR(1) 到 LALR(1) 的状态合并,对吧?
  • YACC 和 GNU Bison 中使用的优先级和关联性是否引入了工具来帮助解决转移/减少冲突,对吗?
  • 此外,仅当冲突的移位/归约规则优先级等于前瞻符号优先级时,解析器才应检查关联性,在任何其他情况下关联性都无关紧要,对吗?

  • 我问是因为我不是 100% 确定,而且这些书没有提供关于冲突解决的太多细节,我在这个主题上找到的唯一几行是 in the GNU Bison Manual

    与上面的 Bison 手册链接相关的问题:
  • 为什么他们声称冲突规则中没有优先级前瞻标记,选择是 SHIFT?我认为如果减少规则有任何优先级,它就会在没有任何优先级的情况下击败前瞻。
  • 最佳答案

  • 如果在 LALR(k) 构造过程中发现任何冲突(shift/reduce 或 reduce/reduce),则语法不是 LALR(k)。
  • 从 LR(1) 到 LALR(1) 的状态合并不会产生 shift/reduce 冲突,所以如果有,语法也不是 LR(1)。但它会产生减少/减少冲突。如果是,则语法不是 LALR(1),即使它是 LR(1)。 (这不是真正的“有效性”问题;而是特定算法的可解析性问题。)
  • 是的,优先级(和结合性,这只是优先级的一个子案例)允许解决移位/减少冲突。
  • 优先级是产生式(左侧)和前瞻标记(右侧)之间的比较。关联性影响使用的比较运算符:≤ 或 <(或者,在 %nonassoc 的情况下,等于错误)。

  • Dragon book 中有对该算法的精彩讨论。 .然而,它并不是很复杂:如果生产“获胜”,解析器就会减少;否则它会移动。

    额外问题:仅当为产生式(通过 %prec 或,默认情况下,产生式中最后一个终端的优先级)和前瞻标记定义了优先级时,才应用优先规则。如果其中任何一个缺少优先声明,则 shift 获胜。这可能看起来不合逻辑,但事实就是如此。

    关于parsing - LALR(1) 解析器中的冲突解决,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21858092/

    相关文章:

    Java:如何使用字符串比较用户和真实答案并确保其语法正确?

    parsing - 如何将解析树简化为抽象语法树?

    parsing - Packrat 解析与 LALR 解析

    qml - QML 语法是 LALR(1) 吗?

    c - C语言中如何从字符串中提取多个数字

    java - 分割后字符串变成空白

    java - 为什么 DateTimeFormatter 没有以指定格式打印日期?

    java - 在 Eclipse 中使用 AST 处理不解析绑定(bind)

    algorithm - 这个上下文无关语言枚举器的伪代码实现是什么?

    parsing - LALR解析器生成器实现问题