总体问题是:
怎么我的语法有看起来像允许任意嵌套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)bison语法的结构如下(呈现实际语法文件的自包含部分,简化一点):
%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令牌已经在两个地方使用,即规则中的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(并且我甚至不确定这是否真的会帮助低优先级左关联运算符).
我怀疑您将不得不在不那么依赖优先级声明的情况下执行此操作。但我还没有完全放弃希望:-)所以我将首先阐述优先级是如何工作的，通过展示为什么它不能按照您尝试使用它的方式工作。
\n关于优先级规则的基本原则非常简单：优先级比较总是涉及一个规则（或产生式，如expr: expr \'+\' expr）和一个传入标记，称为先行标记。没有例外。尽管声明优先级的形式使它看起来像是两个标记之间的比较，但这是一个方便的虚构，使其在常见情况下使用起来更方便一些。但现实是，正如我之前所说（值得重复）：优先级比较始终发生在规则和标记之间。
要理解这意味着什么，了解 LR 解析算法的本质很有用。LR 解析器是一个有限状态下推自动机，这意味着它是一个用单堆栈增强的普通有限状态机。在 LR 解析的情况下，堆栈完全由状态 ID 组成。自动机的一个状态对应于一组“项目”；项目由生产规则和生产规则中的位置组成。实际上，状态代表一组可能的解析位置，所有这些位置都在并行探索。
\n每次解析器进行普通状态转换（其中读取输入标记并使用规则移动到下一个状态）时，目标状态也会被推送到堆栈上。这称为“移位”转换，因为输入标记被移位到解析器上。仅当状态项集中存在一个或多个项时，才会发生这种情况，其中先行标记是紧跟在该位置之后的终结符，或者是可以立即启动该位置之后的非终结符的标记之一。
\n但还有另一种过渡：“减少”过渡。归约转换是解析器如何识别产生式规则已被识别的方式。（之所以称为归约，是因为它通过将产生式的右侧替换为左侧的非终结符来减少产生式的右侧。）为了执行此归约，自动机会执行两件事：首先，它会弹出对于规则右侧的每个符号，从堆栈中取出一个状态。其次，它通过使用非终结符的转换规则来移动非终结符（并且与移位一样，将结果状态 ID 推入堆栈。）
\n尽管归约转换不会吸收前瞻标记，但它确实将其考虑在内。为了使归约转换可行，必须能够在归约（或归约，因为可能不止一个）之后移动前瞻标记。这些前瞻集是在解析自动机的构建过程中计算的；状态机都是静态的。
\n因此，移位转换对应于尚不可能识别任何右侧的决策，而归约转换对应于某些产生式已被识别的决策。
\n有时会发生移位和归约都可用的情况：也就是说，解析器状态处于某些产生式的末尾，但它也处于不同产生式中的某个点，其中先行标记是可能的下一个标记之一代币。
\n这称为“移位-归约冲突”，因为移位和归约都是可能的。为了解决此冲突，解析器生成器（而不是解析器）从状态转换表中消除其中一个转换。如果没有适用的优先关系，则消除归约操作。（换句话说，解析器更喜欢移动。）但是，如果配置的优先级可用，则解析器生成器通过将可用归约的优先级与先行标记的优先级进行比较来使用它。以较大者获胜（平局通过关联性解决）。
\n如果您使用最新版本的 bison 并提供该--report=all选项，您实际上可以看到工作中的优先规则，该选项显示的信息比该选项多一些-v。（在这两种情况下，除非您提供自定义报告文件名，否则都会写入报告<filename>.output。）我鼓励您这样做。
优先级决策的静态性质的一个结果是优先级不是通过减少继承的。我们可以通过一个非常简单的例子看到这一点。
\n我们从这个简单的语法开始：
\n%token NUMBER\n%left \'+\'\n%%\nexpr: NUMBER\n | expr \'+\' expr\n这导致机器具有五个状态，其中最后一个状态特别令人感兴趣：（摘自precedence.output之后的文件bison --report=all precedence.y）
State 5\n\n 2 expr: expr . \'+\' expr\n 2 | expr \'+\' expr . [$end, \'+\']\n\n $default reduce using rule 2 (expr)\n\n Conflict between rule 2 and token \'+\' resolved as reduce (%left \'+\').\n我们在这里看到的是，解析器已经达到了这样的状态，可以.通过移动 a 来推进（代表解析进度）+，或者等到reduce之后expr \'+\' expr。因为加法是左结合的，所以归约是正确的；这将导致2 + 3 \xc2\xb7 + 4立即减少到expr \xc2\xb7 + 4，这相当于说解析是有效的(2 + 3) + 4。
现在，让我们添加一个间接级别：
\n%token NUMBER\n%left \'+\'\n%%\nexpr : NUMBER\n | left \'+\' right\nleft : expr\nright: expr \n在新机器中，状态 5 有点不同：
\nState 5\n\n 1 expr: . NUMBER\n 2 | . left \'+\' right\n 2 | left \'+\' . right\n 3 left: . expr\n 4 right: . expr\n\n NUMBER shift, and go to state 1\n\n expr go to state 6\n left go to state 3\n right go to state 7\n现在根本不存在冲突，因为left和right是不同的非终结符。所以根本不需要优先规则，而且结果也没有被使用。但请注意，在这台新机器的状态 5 中，解析器认识到它可能即将解析 aleft或即将解析 aright（在最后两条规则中编号为 3 和 4）。这是状态 6 中的问题：
State 6\n\n 3 left: expr . [\'+\']\n 4 right: expr . [$end, \'+\']\n\n $end reduce using rule 4 (right)\n \'+\' reduce using rule 3 (left)\n \'+\' [reduce using rule 4 (right)]\n $default reduce using rule 3 (left)\n一旦它成功解析了一个expr，它就需要决定它是一个还是left一个right。这里的冲突是在两个不同的归约之间，因此是归约-归约冲突。由于优先级总是将规则与终端进行比较进行比较，因此它不适用于需要比较两个规则的情况。所以冲突并没有得到优先解决。
（使用 yacc/bison 的默认减少/减少冲突解决算法来解决冲突：选择文件中最前面的规则。）
\n因此，如果操作的左右操作数+确实具有重叠的不同语法，我们将很难通过优先级声明来解决歧义。
此时，我们可能会放弃优先级（无论如何我们最终可能必须这样做），但我认为尝试一些可能有效的方法是值得的。它的效果并不完美，但这次尝试很有趣，我认为值得展示。
\n我确信您自己已经做到了这一点，因为您的语法似乎包含一些通常建议的 LR(2) 语法的解决方法。但尝试将问题减少到最低限度以便明确可能的解决方案似乎很有用。
\n事实上，这里存在三个不同的问题：
\n“短闭包”语法是 LR(2)；也就是说，它需要两个前瞻令牌来在两个不同的约简之间做出决定；
\n令牌=>以两种互不兼容的方式使用，因此有必要expr根据上下文定义两种不同的语法；
短闭包的前言——参数列表和后面的=>——具有不对称的优先级。
第三个问题与前缀运算符的语法没有太大区别yield，语法已经有解决方案（无论它是否是语言设计者和/或用户所希望的），所以我将把它留到以后（或者也许写一篇不同的文章）并关注前两个问题。[笔记2]
问题的本质在于以下两段代码（实际上，我只对下面expr的赋值运算符感兴趣，但提供完整的上下文似乎更具可读性）：
b = ( a ) + 2\nb = ( a ) => 2\n对于本次说明的其余部分，我们假设解析器刚刚读取了 token a。
这些都是特殊情况，每种都有不同的语法，大致如下：
\nexpr : expr \'+\' expr\n和
\nexpr : parameter_list "=>" expr\n为了完整起见，我们还需要看到：
\nexpr : \'(\' expr \')\'\n | ID\nparameter_list : \'(\' \')\' | \'(\' parameters \')\'\nparameters : parameters \',\' ID\n | ID\n这两种语法的其他实例没有问题：
\nb = ( a + 3 ) + 2\nb = ( a , c ) => 2\n这里( a + 3 )不能是 aparameter_list也( a , c )不能是 an expr，因此在每种情况下只有一个规则适用，并且+和,标记都足以排除其他选择。但在这种情况下( a )（解析器查看)），尚不可能知道跳转到哪个方向。
不幸的是，解析器需要知道这一点，因为它必须在以下之间进行选择：
\nexpr : ID\nparameters : ID\n它需要继续执行以下规则之一：
\nexpr : \'(\' expr \')\'\n或者
\nparameter_list : \'(\' parameters \')\'\n但要做到这一点，它必须在这两种ID削减中进行选择。由于该决定不能仅基于一个前瞻标记来做出，因此 bison 报告了一个归约/归约冲突，并且正如我们在上面所看到的，归约/归约冲突无法通过优先级声明来解决。
如果解析器可以在未来再查看一个标记，它将看到 后面的标记)，这足以做出决定：如果第二个下一个标记是=>，则它必须位于parameter_list; 否则，它必须在expr. 所以语法（或其简化版本）是 LR(2)，而不是 LR(1)。如果 bison 能够生成 LR(2) 语法就好了，但它不能。[注1]所以我们需要寻找不同的解决方案。
有一个不同的解决方案，因为不存在 LR(2)语言这样的东西。很容易证明任何具有 LR(k) 语法的语言也具有等效的 LR(1) 语法 - 等效性在于原始解析树可以从 LR(1) 的解析树机械地导出） 语法。这种等效的语法甚至可以通过算法生成，因此数学家可能会说“存在解决方案”。不幸的是，这不是一个特别实用的解决方案，因为没有任何工具（据我所知）可以真正执行转换 - 当然 bison 也不会 - 而且因为转换使语法变得非常非常大。尽管如此，LR(1) 文法必须存在这一事实使得尝试找到一个文法是值得的。
\n将 LR(2) 文法转变为 LR(1) 文法的基本方法是延迟决策。在实际语法中，问题在于解析器需要在有足够的信息之前在parameter_list和之间做出决定；expr我们可以通过重写语法来简化工作，以便稍后做出决定。
我们可以从以下最小语法开始，如上所述：
\n%token ID\n%right "=>"\n%left \'+\'\n%%\nexpr : expr \'+\' expr\n | parameter_list "=>" expr\n | \'(\' expr \')\'\n | ID\nparameter_list : \'(\' \')\' | \'(\' parameters \')\'\nparameters : parameters \',\' ID\n | ID\n与上面的“左/右”示例非常相似，此语法在状态 5 中存在归约/归约冲突：
\nState 5\n\n 4 expr: ID . [\'+\', \')\']\n 8 parameters: ID . [\')\', \',\']\n\n \')\' reduce using rule 4 (expr)\n \')\' [reduce using rule 8 (parameters)]\n \',\' reduce using rule 8 (parameters)\n $default reduce using rule 4 (expr)\n作为解决方案的第一个近似，我们可以添加一些简单的冗余规则：
\n%token ID\n%right "=>"\n%left \'+\'\n%%\nexpr : paren_id_paren\nparameter_list : paren_id_paren\nparen_id_paren : \'(\' ID \')\'\nexpr : expr \'+\' expr\n | parameter_list "=>" expr\n | \'(\' expr \')\'\n | ID\nparameter_list : \'(\' \')\' | \'(\' parameters \')\'\nparameters : parameters \',\' ID\n | ID\n通过 bison 运行它表明我们现在有一个三向冲突的状态（shift/reduce/reduce）：
\nState 6\n\n 3 paren_id_paren: \'(\' ID . \')\'\n 7 expr: ID . [\'+\', \')\']\n 11 parameters: ID . [\')\', \',\']\n\n \')\' shift, and go to state 13\n\n \')\' [reduce using rule 7 (expr)]\n \')\' [reduce using rule 11 (parameters)]\n \',\' reduce using rule 11 (parameters)\n $default reduce using rule 7 (expr)\n\'(\' ID这是解析器刚刚读取且先行标记为 的状态)。由于新语法是不明确的，因此包含该序列的每个输入都可以通过两种方式进行解析：使用移位或使用两种归约之一。解析器仍然无法判断要使用哪种归约。但移位总是有效的，并且因为 bison/yacc 的默认冲突解决算法是更喜欢移位，所以移位已被烘焙到解析自动机中。这太好了，因为这正是我们想要的。唯一的缺点是解析器生成器每次运行时都会产生警告，而有些人真的讨厌在生产构建期间看到警告。
我并不是要贬低人们对警告的厌恶；我只是想贬低人们对警告的厌恶。我分享它。但我也注意到，这种解决方案实际上是 yacc 的原作者所考虑的，甚至在 Dragon 书中关于使用 yacc 处理不明确语法的部分中也描述了一个例子。这正是 yacc 默认冲突解决算法如此工作的原因。Bison 和 yacc 甚至实现了一对指令，其目的是在预期时消除此警告。因此，我们可以就此搁置，继续讨论另一个问题（ 的双重使用=>），但是当我思考这个问题时，我突然想到，也许可以使用优先级来提供明确的解决方案，按照Bison手册的建议：
\n\n我们不建议使用
\n%expect（除了\xe2\x80\x98%expect 0\xe2\x80\x99！），因为相同数量的冲突并不意味着它们是相同的。如果可能，您应该使用优先指令来显式修复冲突。（强调原文。）
优先级声明需要优先选择移动 a)而不是减少ID。这样一来，声明就很简单了：
%token ID\n%precedence ID\n%precedence \')\'\n%right "=>"\n%left \'+\'\n%%\nexpr : paren_id_paren\nparameter_list : paren_id_paren\nparen_id_paren : \'(\' ID \')\'\nexpr : expr \'+\' expr\n | parameter_list "=>" expr\n | \'(\' expr \')\'\n | ID\nparameter_list : \'(\' \')\' | \'(\' parameters \')\'\nparameters : parameters \',\' ID\n | ID\n效果很好，所以我们可以继续讨论第二个问题，看看该解决方案是否适用于上下文。
\n仍有待继续
\n事实上，yacc 生成 LALR(1) 语法，这些语法在前瞻的使用方面稍微受到限制，但 LR(1) 和 LALR(1) 之间的差异不必在这里困扰我们。
\nBison 能够生成 GLR 语法，它可以与任何明确的语法一起使用，并且这个语法是明确的。然而，许多项目不愿意使用 GLR 语法，因为人们认为 GLR 语法效率低下并且操作受到限制。如果情况并非如此，那么使用 GLR 语法无疑是最简单的解决方案。
\n的预先存在的使用=>具有相当明确定义的优先级，该优先级由预先存在的优先级声明完全指定。