bison - 如何管理相互递归，并保留关联性规则？

Question

总体问题是:

我的语法看起来如何才能允许任意嵌套的expr := '(' expr ')' => expr | expr_without_short_closure和expr_without_short_closure := [expr_without_short_closure => expr] | yield expr_without_short_closure => expr | expr_without_short_closure 'or' expr | '(' expr ')'，同时仍然允许像expr_without_short_closure 'or' expr这样的低优先级左关联运算符？

当前，LALR(1)野牛语法的结构如下(表示实际语法文件的独立部分，略有简化):

%left ','
%left T_LOGICAL_OR /* or */
%right T_YIELD
%right T_DOUBLE_ARROW /* => */
%left '+'

expr: /* entry point as well */
                expr_without_short_closure %prec ',' { $$ = $1; }
        |       expr_with_short_closure { $$ = $1; }
;

expr_with_short_closure:
                short_closure
        |       T_YIELD expr_without_short_closure T_DOUBLE_ARROW expr_with_short_closure { $$ = zend_ast_create(ZEND_AST_YIELD, $4, $2); }
;

short_closure:
                T_IDENTIFIER T_DOUBLE_ARROW expr { /* ... */ }
        |       '(' expr ')' T_DOUBLE_ARROW expr { /* ... */ }
;

expr_without_short_closure:
                T_IDENTIFIER %prec T_DOUBLE_ARROW { $$ = $1; }
        |       '(' expr ')' %prec T_DOUBLE_ARROW { $$ = $2; }
        |       T_YIELD expr_without_short_closure { $$ = zend_ast_create(ZEND_AST_YIELD, $2, NULL); }
        |       '[' array_pair_list ']' { $$ = $2; }
        |       T_YIELD expr_without_short_closure T_DOUBLE_ARROW expr_without_short_closure { $$ = zend_ast_create(ZEND_AST_YIELD, $4, $2); }
        |       expr_without_short_closure T_LOGICAL_OR expr_without_short_closure       { $$ = zend_ast_create_binary_op(ZEND_AST_OR, $1, $3); }
        |       expr_without_short_closure '+' expr_without_short_closure       { $$ = zend_ast_create_binary_op(ZEND_ADD, $1, $3); }
/*      | and about thirty similar alternate rules like the previous one */
;

non_empty_array_pair_list:
                non_empty_array_pair_list ',' array_pair { $$ = zend_ast_list_add($1, $3); }
        |       array_pair { $$ = zend_ast_create_list(1, ZEND_AST_ARRAY, $1); }
;

array_pair:
                expr_without_short_closure T_DOUBLE_ARROW expr
                        { $$ = zend_ast_create(ZEND_AST_ARRAY_ELEM, $3, $1); }
        |       expr_without_short_closure
                        { $$ = zend_ast_create(ZEND_AST_ARRAY_ELEM, $1, NULL); }
;

本质上，我正在尝试引入“箭头函数”，该函数在左侧包含一个参数列表，在右侧包含一个任意表达式，中间包含一个T_DOUBLE_ARROW。

现在的挑战是，已经在两个地方使用了T_DOUBLE_ARROW token ，即 expr_without_short_closure T_DOUBLE_ARROW expr规则中的 array_pair替换和 T_YIELD expr_without_short_closure T_DOUBLE_ARROW expr_without_short_closure中的 expr_without_short_closure。

这种当前的语法工作方式，但是(显然)无法解析例如:

[T_YIELD T_IDENTIFIER => T_IDENTIFIER => T_IDENTIFIER + T_IDENTIFIER => T_YIELD T_IDENTIFIER]
// must be grouped as:
[(T_YIELD T_IDENTIFIER => T_IDENTIFIER) => (T_IDENTIFIER + (T_IDENTIFIER => (T_YIELD T_IDENTIFIER)))]

在这种情况下， expr_without_short_closure '+' expr_without_short_closure替代方法失败，因为它仅接受右侧的 expr_without_short_closure，显然不允许在那儿使用short_closure。

但是，我不能简单地用 expr_without_short_closure替换 expr，因为这与 expr_without_short_closure T_DOUBLE_ARROW expr表达式( array_pair规则)或 T_YIELD expr_without_short_closure T_DOUBLE_ARROW expr_without_short_closure表达式( expr_without_short_closure规则)冲突。

现在，我可以尝试将 expr仅放在表达式的右侧。很好，除了左联想操作。现在，突然 T_IDENTIFIER + T_IDENTIFIER T_LOGICAL_OR T_IDENTIFIER被分组为 T_IDENTIFIER + (T_IDENTIFIER T_LOGICAL_OR T_IDENTIFIER)而不是所需的 (T_IDENTIFIER + T_IDENTIFIER) T_LOGICAL_OR T_IDENTIFIER。 (为什么？)

我也很想避免 %prec中的 expr_without_short_closure %prec ','( expr规则)。由于某种原因，它是必需的(删除它会导致 expr_without_short_closure中的每个规则上的移位/减少冲突)，我想这也是问题的根源，尽管我并不十分了解为什么(搜索诸如“关联规则”这样的结果)不能通过间接访问”-但我真的看不到如何完全避免使用间接访问)。

我正在尝试使问题保持​​独立，但是如果我错过了某些内容-可以在 https://github.com/bwoebi/php-src/blob/0d98d8060bde88ac2e5904cb55ecb13d15316053/Zend/zend_language_parser.y#L898上找到实际的语法文件-我认为很明显，一个人真的不想将 expr_without_short_closure的所有规则都复制到 expr_with_short_closure(和我什至不确定这是否真的会帮助低优先级的左关联运算符。

Answer 1

我怀疑您将不得不在没有太多依赖优先级声明的情况下执行此操作。但是，我还没有完全放弃希望:-)因此，我将首先阐述优先级的工作原理，并说明为什么优先级无法以您尝试使用的方式工作。
1.规则和 token 之间总是存在优先级比较
关于优先级规则的基本原理很简单:优先级比较总是涉及一个规则(或生产，如expr: expr '+' expr)和一个传入的 token ，称为先行 token 。没有异常(exception)。尽管声明优先级的形式使它看起来像是两个 token 之间的比较，但这是一种方便的小说，使它在普通情况下使用起来更加方便。但是现实是，正如我之前说过的(并且需要重复):优先级比较总是在规则和 token 之间进行。
要了解其含义，了解LR解析算法的性质很有用。 LR解析器是一个有限状态下推自动机，这意味着它是一台普通的有限状态机，并增加了一个堆栈。在LR解析的情况下，堆栈完全由状态ID组成。自动机的状态对应于一组“项目”。一个项目由生产规则和在生产规则中的位置组成。实际上，状态代表一组可能的解析位置，所有这些解析位置都在并行探索。
每次解析器进行普通状态转换(在其中读取输入 token 并将规则用于移至下一个状态)时，目标状态也会被压入堆栈。这被称为“转移”转换，因为输入 token 已转移到解析器上。仅当状态项集中有一个或多个项时，前瞻性 token 是紧随该位置的终端，或者是可能紧随该位置启动非终端的 token 之一，才可能发生这种情况。
但是，还有另一种过渡:“减少”过渡。简化转换是解析器识别已确定生产规则的方式。 (之所以称为简化，是因为它通过用左侧的非终端替换它来减少右侧的生产。)要执行这种还原，自动机要做两件事:首先，将一个状态弹出规则右侧每个符号的堆栈数量。其次，它通过使用针对非终端的转移规则来对非终端进行移位(并且与移位一样，将结果状态ID插入堆栈)。
尽管缩减转换不会吸收前瞻性 token ，但它确实将其考虑在内。为了使缩减转换可行，必须在缩减之后(或缩减，因为可能多个以上)转移前瞻 token 。这些前瞻集是在解析自动机的构建过程中计算的；状态机都是静态的。
因此，转移过渡对应于尚无法识别任何右侧的判定，而减少过渡对应于已确认某些产量的判定。
有时会同时发生平移和减少两种情况:即解析器状态处于某些生产的末尾，但也处于另一生产中的某个时刻，在该生产中，超前标记是下一个可能的标记之一 token 。
这被称为“转移-减少冲突”，因为转移和减少都可能。为了解决此冲突，解析器生成器(而非解析器)从状态的转换表中消除了转换之一。如果没有适用的优先级关系，则消除操作被消除。 (换句话说，解析器更喜欢移动。)但是，如果配置的优先级可用，则解析器生成器通过将可用归约的优先级与先行 token 的优先级进行比较来使用它。取胜者较大(联系可以通过联系解决)。
如果您使用最新版本的bison并提供--report=all选项，则实际上可以看到工作中的优先规则，该选项显示的信息比-v选项更多。 (在两种情况下，除非您提供自定义报告文件名，否则报告都将写入<filename>.output。)我建议您这样做。
2.优先级不被继承
优先级决策的静态性质的结果是，优先级不会通过归约来继承。我们可以通过一个非常简单的示例来了解这一点。
我们从这个琐碎的语法开始:

%token NUMBER
%left '+'
%%
expr: NUMBER
    | expr '+' expr

这导致一台机器具有五个状态，其中最后一个状态特别令人感兴趣:(摘自 precedence.output之后的文件 bison --report=all precedence.y)

State 5

    2 expr: expr . '+' expr
    2     | expr '+' expr .  [$end, '+']

    $default  reduce using rule 2 (expr)

    Conflict between rule 2 and token '+' resolved as reduce (%left '+').

我们在这里看到的是，解析器已经达到一种状态，可以通过移动 .来推进 +(代表解析进度)，或者等待直到减小 expr '+' expr之后。因为加法是左关联的，所以减法是正确的。这将导致 2 + 3 · + 4立即减少为 expr · + 4，这等效于说该解析实际上是 (2 + 3) + 4。
现在，让我们添加一个间接级别:

%token NUMBER
%left '+'
%%
expr : NUMBER
     | left '+' right
left : expr
right: expr 

在新机器中，状态5有所不同:

State 5

    1 expr: . NUMBER
    2     | . left '+' right
    2     | left '+' . right
    3 left: . expr
    4 right: . expr

    NUMBER  shift, and go to state 1

    expr   go to state 6
    left   go to state 3
    right  go to state 7

现在完全没有冲突了，因为 left和 right是不同的非终结符。因此，根本不需要优先级规则，并且事实证明它没有被使用。但是请注意，在此新计算机的状态5中，解析器识别出它可能将要解析 left或即将解析 right(在最后两个规则(编号为3和4)中)。这是状态6中的问题:

State 6

    3 left: expr .  ['+']
    4 right: expr .  [$end, '+']

    $end      reduce using rule 4 (right)
    '+'       reduce using rule 3 (left)
    '+'       [reduce using rule 4 (right)]
    $default  reduce using rule 3 (left)

一旦它成功解析了 expr，就需要确定它是 left还是 right。这里的冲突是两个不同归约之间的冲突，因此它是一个归约还原冲突。并且由于优先级始终将规则与终端进行比较，因此它不适用于需要比较两个规则的情况。因此，冲突无法优先解决。
(使用yacc/bison的默认解析算法来解决冲突，以减少/减少冲突:选择文件中最先出现的规则。)
因此，如果 +操作的左右操作数确实具有不同的语法，它们相互重叠，我们将很难解决带有优先权声明的歧义。
在这一点上，我们可能只是放弃优先级(无论如何我们最终都必须这样做)，但我认为尝试一些可行的方法是值得的。它不能很好地工作，但是这种尝试很有趣，以至于我认为值得介绍。
3.对问题的简要探讨
我相信您自己已经走了这么远，因为您的语法似乎包括了一些有关LR(2)语法的通常建议的解决方法。但是尝试将问题减少到最小程度以弄清楚可能的解决方案似乎很有用。
实际上，这里存在三个不同的问题:

的“短闭包”语法是LR(2);也就是说，它需要两个先行标记才能在两个不同的折减之间做出决定；

=> token 以两种互不兼容的方式使用，因此有必要根据上下文定义两种不同的expr语法；

简短闭包的序言-参数列表和后面的=>-具有不对称的优先级。

第三个问题与 yield前缀运算符的语法没有太大不同，后者的语法已经有了解决方案(无论它是否是语言设计者和/或用户所希望的)，因此我将将其留待以后(或可能发表另一篇论文)，并专注于前两个问题。 [笔记2]
问题的实质在于以下两个代码段(实际上，我只对赋值运算符后面的 expr感兴趣，但提供完整的上下文似乎更易读):

b = ( a ) + 2
b = ( a ) => 2

在本博览会的其余部分中，我们将假定解析器刚刚读取了 token a。
这些都是特殊情况，每种都有不同的语法，大致是:

expr : expr '+' expr

和

expr : parameter_list "=>" expr

为了完整起见，我们还需要查看:

expr           : '(' expr ')'
               | ID
parameter_list : '(' ')' | '(' parameters ')'
parameters     : parameters ',' ID
               | ID

这两种语法的其他实例都没有问题:

b = ( a + 3 ) + 2
b = ( a , c ) => 2

此处 ( a + 3 )不能是 parameter_list，而 ( a , c )不能是 expr，因此每种情况下仅适用一个规则，并且 +和 ,标记都足以排除另一种选择。但是，对于 ( a )(解析器查看 ) token )，尚无法知道跳转的方式。
不幸的是，解析器需要知道这一点，因为它必须在以下两者之间进行选择:

expr       : ID
parameters : ID

它需要遵循以下规则之一:

expr           : '(' expr ')'

或者

parameter_list : '(' parameters ')'

但要这样做，它必须在两个 ID缩减中的一个进行选择。由于不能仅基于一个前瞻标记来做出该决定，因此，野牛报告了减少/减少冲突，并且如上所述，减少/减少冲突无法通过优先级声明来解决。
4.部分解决方案
如果解析器将来可以再看一个 token ，它将在 )之后看到该 token ，这足以做出决定:如果第二个下一个 token 是 =>，则它必须在 parameter_list中；否则，它必须在 expr中。因此，语法(或其简化版本)是LR(2)，而不是LR(1)。如果bison可以生成LR(2)语法，那将是很好的选择，但事实并非如此。 [注1]因此，我们需要找到其他解决方案。
有一个不同的解决方案，因为没有像LR(2)这样的语言。容易证明任何具有LR(k)语法的语言也具有等效的LR(1)语法-从原始解析树可以机械地从LR(1)语法的解析树派生的意义上说，这是等效的。该等效语法甚至可以通过算法生成，因此数学家可能会说“存在解决方案”。不幸的是，这不是一个特别实用的解决方案，因为没有工具(据我所知)实际进行转换-无疑是bison不能-并且因为转换使语法大得多。尽管如此，LR(1)语法必须存在这一事实使得值得一试。
将LR(2)语法转换为LR(1)语法的基本方法是延迟决策。在实际的语法中，问题在于解析器需要先在 parameter_list和 expr之间进行决策，然后才能拥有足够的信息。我们可以通过重写语法来简化工作，以便稍后做出决定。
我们可以从下面的最小语法开始，如上所述:

%token ID
%right "=>"
%left '+'
%%
expr           : expr '+' expr
               | parameter_list "=>" expr
               | '(' expr ')'
               | ID
parameter_list : '(' ')' | '(' parameters ')'
parameters     : parameters ',' ID
               | ID

与上面的“左/右”示例相似，该语法在状态5中具有减少/减少冲突:

State 5

    4 expr: ID .  ['+', ')']
    8 parameters: ID .  [')', ',']

    ')'       reduce using rule 4 (expr)
    ')'       [reduce using rule 8 (parameters)]
    ','       reduce using rule 8 (parameters)
    $default  reduce using rule 4 (expr)

作为解决方案的第一近似，我们可以添加一些简单的冗余规则:

%token ID
%right "=>"
%left '+'
%%
expr           : paren_id_paren
parameter_list : paren_id_paren
paren_id_paren : '(' ID ')'
expr           : expr '+' expr
               | parameter_list "=>" expr
               | '(' expr ')'
               | ID
parameter_list : '(' ')' | '(' parameters ')'
parameters     : parameters ',' ID
               | ID

通过野牛运行它表明我们现在具有一个三向冲突状态(shift/reduce/reduce):

State 6

    3 paren_id_paren: '(' ID . ')'
    7 expr: ID .  ['+', ')']
   11 parameters: ID .  [')', ',']

    ')'  shift, and go to state 13

    ')'       [reduce using rule 7 (expr)]
    ')'       [reduce using rule 11 (parameters)]
    ','       reduce using rule 11 (parameters)
    $default  reduce using rule 7 (expr)

这是解析器刚刚读取 '(' ID且超前标记为 )的状态。因为新语法是模棱两可的，所以可以使用两种方式来解析包含此序列的每个输入:使用移位或使用两种归约中的一种。解析器仍然无法确定要使用哪种缩减。但是这种移位总是有效的，并且由于bison/yacc的默认冲突解决算法是偏向于移位，因此这种移位已被解析为自动机。太好了，因为这正是我们想要的。唯一的缺点是解析器生成器每次运行时都会生成警告，有些人真的讨厌在生产构建期间看到警告。
我的意思不是贬低对警告的厌恶。我分享。但是我也注意到yacc的原始作者实际上已经想到了这种解决方案，甚至在Dragon书籍的有关使用yacc进行歧义语法的部分中都描述了这种解决方案的示例。这就是yacc默认冲突解决算法按其方式工作的原因。 Bison和yacc甚至实现了 pair of directives，其目的是在预期警告时使此警告静音。因此，我们可以继续讨论其他问题( =>的双重使用)，但是当我在考虑这个问题时，我想到可能可以使用优先级来提供明确的解决方案，按照《野牛手册》的建议:

we don’t recommend the use of %expect (except ‘%expect 0’!), as an equal number of conflicts does not mean that they are the same. When possible, you should rather use precedence directives to fix the conflicts explicitly. (Emphasis in original.)

优先级声明需要更喜欢将 )转换为减少 ID。这样说来，声明就很简单了:

%token ID
%precedence ID
%precedence ')'
%right "=>"
%left '+'
%%
expr           : paren_id_paren
parameter_list : paren_id_paren
paren_id_paren : '(' ID ')'
expr           : expr '+' expr
               | parameter_list "=>" expr
               | '(' expr ')'
               | ID
parameter_list : '(' ')' | '(' parameters ')'
parameters     : parameters ',' ID
               | ID

这样做很好，所以我们可以继续研究第二个问题，看看解决方案是否在上下文中成立。
仍有待续

笔记

实际上，yacc生成LALR(1)语法，在使用超前方式方面有一些限制，但是LR(1)和LALR(1)之间的区别不必在这里困扰我们。
Bison能够生成GLR语法，该语法将与任何明确的语法一起使用，并且该语法是明确的。但是，由于感觉到的效率低下和对操作的限制，许多项目都不愿使用GLR语法。如果不是这种情况，那么使用GLR语法将是最简单的解决方案。

=>的预先存在的使用具有合理定义的优先级，该优先级由预先存在的优先级声明完全指定。