parsing - Yacc中是否定义了减少的顺序？

Question

这与其说是一个实际问题，不如说是一个“原则上”的问题。 Yacc 减少产生式并从定义的词法分析器读取新标记的顺序。也就是说，如果我有以下一组 token :

INTEGER_BEGIN
INTEGER_VALUE
LESS_THAN
INTEGER_BEGIN
INTEGER_VALUE

Yacc 是否可以在其语义范围内阅读 LESS_THAN词法分析器中的标记，在它减少之前 INTEGER BEGIN INTEGER_VALUE给一个单一的东西，给定一组产品，如:

expr : expr LESS_THAN expr
     | integer

integer : INTEGER_BEGIN INTEGER_VALUE

如果这些规则是用语义 Action 定义的，那么这个规则会改变吗？

Answer 1

是的，它可以。 Yacc 创建了一个 LALR(1) 解析器——(1) 意味着 1 个前瞻标记——所以它可以在减少规则之前提前读取超过规则标记末尾的 1 个标记。语义 Action 的存在是无关紧要的，因为语义 Action 只是在减少规则之前运行的一些 C 代码。

请注意，不能保证它总是提前读取 token 。由 yacc 或 bison 创建的解析器有时使用“默认缩减”——说明它可以缩减规则而不必先读取下一个标记。每当规则的减少独立于下一个标记时，就会发生这种情况。

在此特定示例中，可以对 integer 使用默认减少规则，所以它可能会在没有前瞻的情况下减少它，但同样不能保证——默认减少是 yacc 的一些(但不是全部)实现使用的优化。