在Bison中，如何确定与非终端的关联性? [英] in Bison, how can I specity left associativity for a non-terminal?

问题描述

我有以下Bison语法片段:

I have the following Bison grammar snippet:

binary_op:         BINARY_OP
                    {
                        ...
                    }
                    | '|' %prec BINARY_OP
                    {
                        ...
                    }
;

non_keyword_expr:   non_keyword_expr binary_op non_keyword_expr %prec BINARY_SEND_PREC %dprec 2
                    {
                        ...
                    }
;

|在我的语法中具有重载的含义，因此我不能仅从我的词法分析器中将其作为令牌BINARY_OP返回.取决于上下文，它可能是一个不同的令牌.

| has overloaded meaning in my grammar, so I can't just return it as token BINARY_OP from my lexer. It could be a different token depending on context.

如果我使用它作为输入:

If I use this as my input:

4 OR 5 OR 6

我可以成功解析它(词法分析器将OR识别为BINARY_OP令牌).

I can parse it successfully (OR is recognized as a BINARY_OP token by the lexer).

但是，如果我的输入是这样的话:

If, however, my input is this:

4 | 5 | 6

我得到一个模棱两可的语法错误. (|未被识别为左关联)

I get an ambiguous grammar error. (the | isn't being recognized as left associative)

如何在 non_keyword_expr 中使 binary_op 保持左关联? binary_op 第二条规则的%prec语句似乎无效.

How can I get binary_op to be left-associative within non_keyword_expr? the %prec statement on the second rule for binary_op seems to have no effect.

编辑:这是用于GLR解析器

edit: this is for a GLR parser

推荐答案

简单答案:您不能.优先级(和关联性)仅适用于产品(左侧)和终端(右侧).它们不适用于非终端.

Simple answer: You cannot. Precedence (and associativity) only apply to productions (on the left) and terminals (on the right). They do not apply to non-terminals.

这不是一个任意的决定；这是野牛处理转移/减少冲突的方式所固有的.在每个解析步骤中，必须最终移动超前令牌(终端)，但是有可能在终端移动之前会减少产量.如果未立即执行还原操作，则将永远不会执行还原操作. LR(1)语法允许解析器根据当前的解析堆栈和前瞻标记来决定是否应执行缩减或是否应立即转换前瞻标记.如果两种动作都可行，那么该语法就被认为具有移位/减少冲突，而且严格来说并不是LR(1).

That's not an arbitrary decision; it's inherent to the way bison handles resolution of shift/reduce conflicts. At every parsing step, the lookahead token (a terminal) must either eventually be shifted, but it is possible that there is a production which could be reduced before the terminal is shifted. If the reduction is not performed immediately, it will never be performed. An LR(1) grammar allows the parser to decide based on the current parse stack and the lookahead token whether a reduction should be performed or whether the lookahead token should be immediately shifted. If both actions are possible, then the grammar is said to have a shift/reduce conflict, and it is not strictly speaking LR(1).

优先级和关联性规则用于解决移位/减少冲突.生产可能具有隐式或显式优先级:显式优先级由%prec声明提供；否则，将使用生产中最后一个终端的优先级.在发生班次/减少冲突的情况下，将可以减少的生产优先级与可以转移的先行终端的优先级进行比较，以优先级较高者为准.而已.优先级不会保留或继承.实际上，比较优先级是不正确的，因为在解析过程中不会发生这种情况.解析器具有一个动作或转换表，该动作或转换表定义了在特定堆栈配置(状态")和超前标记的情况下的操作，并且优先级信息在生成解析器时用于填充动作表中的条目否则将是模棱两可的.

Precedence and associativity rules are used to resolve shift/reduce conflicts. Productions may have an implicit or explicit precedence: the explicit precedence is provided by the %prec declaration; otherwise the precedence of the last terminal in the production is used. In the event of a shift/reduce conflict, the precedence of the production which could be reduced is compared to the precedence of the lookahead terminal which could be shifted, and whichever has the greater precedence wins. That's it. The precedence is not retained or inherited. In fact, it is inaccurate to say that the precedences are compared, since that doesn't happen during the parse; the parser has an action or transition table which defines what to do in the case of a particular stack configuration ("state") and lookahead token, and the precedence information is used at parser-generation time to fill in the entries in the action table which would otherwise be ambiguous.

在您的作品中

binary_op: '|' %prec BINARY_OP

%prec声明是无用的，因为必须始终立即减小binary_op；它不能参与转变/减少冲突.移位/减少冲突与non_keyword_expression生产一起出现，该产品标记有(不同的)%prec声明，并且该声明将用于该生产.

the %prec declaration is useless, because binary_op must always be reduced immediately; it cannot participate in a shift/reduce conflict. The shift/reduce conflict comes with the non_keyword_expression production, which is marked with a (different) %prec declaration, and that is the declaration which will be used for that production.

non_keyword_expression的产生式没有终端，因此也没有隐式优先级.通常这不是您想要的，而是使用类似这样的产品

The production for non_keyword_expression does not have a terminal, so it has no implicit precedence either. That's generally not what you want, and the use of productions like:

binary_op: '|' | "OR" ;

与使用优先级来解决解析冲突并不真正兼容.

are not really compatible with the use of precedence to resolve parsing conflicts.

注1:如果要求使用GLR解析器，则情况并非完全如此. GLR解析器可以执行移位和归约操作，因为它(有效)同时维护了许多解析器状态.最终，除了其中一种状态外，所有其他状态都必须消除.否则，解析是模棱两可的. GLR解析器使用优先级(和%prec声明)的方式与非GLR解析器完全相同.通过优先级消除的解析器动作实际上是消除的，并且不会导致并行状态.但是，GLR解析器还可以处理减少/减少冲突，其中存在两种可能的减少(可能是同一非终端).这些冲突可以使用%dprec(动态优先级")声明来解决.

Note 1: This is not completely true if you ask for a GLR parser. The GLR parser can perform both the shift and the reduce, because it (effectively) maintains a number of parser states at the same time. Eventually, all but one of these states must be eliminated; otherwise, the parse is ambiguous. GLR parsers use precedence (and %prec declarations) in precisely the same way that non-GLR parsers do; a parser action eliminated by precedence is really eliminated and does not lead to parallel states. However, a GLR parser can also deal with reduce/reduce conflicts, in which there are two possible reductions (possibly to the same non-terminal). These conflicts can be resolved using %dprec ("dynamic precedence") declarations.

这篇关于在Bison中，如何确定与非终端的关联性?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！