可以在 LALR(1) 解析器 (PLY) 中解析这种看似模棱两可的问题吗？
Can this seeming ambiguity be parsed in a LALR(1) parser (PLY)?
我在 PLY (Python Lexx Yacc) 中有一个大型语法，用于一种在解析方面有一些特殊挑战的语言。该语言允许两种调用的前导语法看起来几乎相同，直到非终端调用结束。这为 reduce/reduce 冲突提供了很多机会，因为沿途令牌的语义不同，但可以由相同的终端令牌构建。我已经提取了下面语法的简单 before/after 版本，我会稍微解释一下。
最初，表达式是一个典型的 "Stratified Grammar," 接受调用和文字等到初级，然后是初级到一元，然后是二进制到一般表达式。问题是带有两个参数的 Call_expr 与以 '/' 之前的两个 ID 开头的 Iter_expr 版本冲突。冲突发生在调用中第一个参数之后的逗号上，因为最初 Expr -> ... -> Primary_expr -> Name_expr -> Id 是允许的。解析器可以将 Id 减少到 Expr 以匹配 Call_expr，或者保留它以匹配 Iter_expr。展望未来并没有帮助它做出决定。如果调用的第一个参数只是一个标识符（如变量），这是合法的歧义。考虑输入 id > id ( id , id ... .
我的方法是制作一种可以而不是只是Id的表达式。我通过所有表达式添加了生产链，为它们提供“_nn”版本--'not a name.' 然后我可以为 Call_expr 定义生产，在第一个参数中使用任何语法，使其更不仅仅是一个名称（例如操作员、呼叫等）将其减少到 BinOp_expr_nn，并且 还 允许呼叫生产仅具有 Id 作为第一个参数。这应该说服解析器只是转移，直到它可以解析 Iter_expr 或 Call_expr （或者至少知道它在哪条路径上。）
您可能已经猜到了，这把一切都搞砸了:)。修改表达式链也会修改 Primary_expr，我仍然需要将其减少到 Id。但现在，这是一个 reduce/reduce 冲突——每个 Primary_expr 都可以留在那里或继续 Unary_expr。我可以命令他们做出选择（这可能有效），但我希望我最终会追逐一个又一个。
所以，我的问题是：是否有人可以阐明如何允许相同的标记表示不同的语义（即 expr 与 id）仍然可以像 PLY 一样用 LALR(1) 解析的技术？除此之外，任何有助于解决问题的有用技巧？这可以消除歧义吗？
terminals: '+' '^' ',' '>' '(' ')' '/' ':' 'id' 'literal'
(i.e. punctuation (besides '->' and '|', initial-lower-case words)
non-terminals: initial-Upper-case words
原文语法：
S'-> S
S -> Call_expr
| Iter_expr
Expr -> BinOp_expr
BinOp_expr -> Unary_expr
BinOp_expr -> BinOp_expr '+' BinOp_expr
Unary_expr -> Primary_expr
| '^' BinOp_expr
Primary_expr -> Name_expr
| Call_expr
| Iter_expr
| Literal_expr
Name_expr -> Id
Args -> Expr
| Args ',' Expr
Call_expr -> Primary_expr '>' Id '(' ')'
| Primary_expr '>' Id '(' Args ')'
Iter_expr -> Primary_expr '>' Id '(' Id '/' Expr ')'
| Primary_expr '>' Id '(' Id ':' Id '/' Expr ')'
| Primary_expr '>' Id '(' Id ',' Id ':' Id '/' Expr ')'
Literal_expr -> literal
Id -> id
我试图消除 Call_expr 中第一个参数的歧义：
S'-> S
S -> Call_expr
| Iter_expr
Expr -> BinOp_expr_nn
| BinOp_expr
BinOp_expr -> BinOp_expr_nn
| Unary_expr
BinOp_expr_nn -> Unary_expr_nn
| BinOp_expr '+' BinOp_expr
Unary_expr -> Primary_expr
| Unary_expr_nn
Unary_expr_nn -> Primary_expr_nn
| '^' BinOp_expr
Primary_expr -> Primary_expr_nn
| Name_expr
Primary_expr_nn -> Call_expr
| Iter_expr
| Literal_expr
Name_expr -> Id
Args -> Expr
| Args ',' Expr
Call_expr -> Primary_expr '>' Id '(' ')'
| Primary_expr '>' Id '(' Expr ')'
| Primary_expr '>' Id '(' Id , Args ')'
| Primary_expr '>' Id '(' BinOp_expr_nn , Args ')'
Iter_expr -> Primary_expr '>' Id '(' Id '/' Expr ')'
| Primary_expr '>' Id '(' Id ':' Id '/' Expr ')'
| Primary_expr '>' Id '(' Id ',' Id ':' Id '/' Expr ')'
Literal_expr -> literal
Id -> id
尽管你的标题 post，但你的语法没有歧义。由于您提到的原因，它根本不是 LR(1)：输入
A ( B ,
可以是 Call_expr 或 Iter_expr 的开始。在第一种情况下，B 必须缩减为 Expr，然后再缩减为 Args；在第二种情况下，它一定不能减少，因为当right-hand侧id '(' id ',' id ':' id '/' Expr ')'减少时它仍然是id。不能简单地通过查看单个前瞻标记（、）来做出决定，因此存在 shift-reduce 冲突。
这个冲突最多可以用两个额外的先行标记来解决，因为只有在 、 后面紧跟着一个 id 和然后是 :。这样就构成了语法 LALR(3)。不幸的是，Ply 不生成 LALR(3) 解析器（yacc/bison 也不生成），但有一些替代方案。
1。使用不同的解析算法
由于语法是明确的，因此可以使用 GLR 解析器毫无问题地解析（并且无需任何修改）。 Ply 也不生成 GLR 解析器，但 Bison 可以。这不太可能对你有多大用处，但我想我应该提一下，以防你没有被限制使用 Python.
2。使用允许一些无效输入的语法，并通过语义分析丢弃它们
这几乎可以肯定是最简单的解决方案，也是我通常推荐的解决方案。如果将 Iter_expr 的定义更改为：
Iter_expr : id '(' id '/' Expr ')'
| id '(' Args ':' id '/' Expr ')'
那么它仍然会识别每个有效输入（因为 id 和 id , id 都是 Args 的有效实例）。这消除了 shift-reduce 冲突；实际上，它让解析器避免在遇到 )（表示 Call_expr）或 之前做出决定：（表示一个Iter_expr）。 （Iter_expr 的第一个替代方案没有问题，因为移动 / 而不是减少 id 的决定不需要额外的前瞻性。）
当然，Iter_expr 的第二个产生式会识别出很多不是有效迭代表达式的东西：超过 2 个项目的列表，以及包含比单个 [= 更复杂的表达式的列表19=]。但是，这些输入根本不是有效程序，因此可以在 Iter_expr 的操作中简单地拒绝它们。识别有效迭代的精确代码将取决于您如何表示 AST，但这并不复杂：只需检查以确保 Args 的长度是 1 或 2，并且列表中的每个项目都是只是一个 id.
3。使用词汇技巧
弥补前瞻信息不足的一种方法是通过将必要的前瞻信息收集到缓冲区中并将其收集在词法分析器中，并且仅在其句法类别已知时才输出词素。在这种情况下，词法分析器可以查找序列 '(' id ',' id ':' 并标记第一个 id 以便它只能在 Iter_expr 中使用。在这种情况下，语法的唯一变化是：
Iter_expr : id '(' id '/' Expr ')'
| id '(' id ':' id '/' Expr ')'
| id '(' iter_id ',' id ':' id '/' Expr ')'
虽然这在这种特殊情况下可以正常工作，但它不是很容易维护。特别是，它依赖于能够定义一个可以在词法分析器中实现的简单且明确的模式。由于该模式是语法的简化，因此未来的某些语法添加很可能会创建也与相同模式匹配的语法。 （出于某种原因，这被称为词汇“hack”。）
4。查找 LALR(1) 文法
如上所示，此语法为 LALR(3)。但是没有 LALR(3) 语言 这样的东西。或者更准确地说，如果一种语言有 LALR(k) 文法，那么它也有 LALR(1) 文法，并且可以从 LALR(k) 文法中机械地产生该文法。此外，给定 one-symbol 前瞻语法的解析，可以为原始语法重建解析树。
因为mechanically-produced文法比较多，这个程序不是很吸引人，不知道算法的实现。相反，最常见的是尝试重写语法的一部分，就像您在原始问题中尝试的那样。这当然可以做到，但最终结果并不完全直观。
然而，这并不难。例如，这里是你的语法的一个稍微简化的版本，删除了冗余的单元产生式，并修复了几个运算符优先级（可能不正确，因为我不知道你的目标是什么语义）。
名称以N结尾的产品不生产ID。对于它们中的每一个，都有一个相应的产生式，没有 N 添加了 ID。完成后，有必要重写 Args 以使用 ExprN 产生式，并允许以一两个 ID 开头的各种参数列表。 Chain 制作只是为了避免一些重复。
Start : Call
| Iter
Expr : ID
| ExprN
ExprN : UnaryN
| Expr '+' Unary
Unary : ID
| UnaryN
UnaryN : ChainN
| '^' Chain
Chain : ID
| ChainN
ChainN : PrimaryN
| Chain '>' CallIter
PrimaryN: LITERAL
| Call
| Iter
| '(' Expr ')'
Call : ID '(' ')'
| ID '(' ID ')'
| ID '(' ID ',' ID ')'
| ID '(' Args ')'
Iter : ID '(' ID '/' Expr ')'
| ID '(' ID ':' ID '/' Expr ')'
| ID '(' ID ',' ID ':' ID '/' Expr ')'
Args : ExprN ExprList
| ID ',' ExprN ExprList
| ID ',' ID ',' Expr ExprList
ExprList:
| ExprList ',' Expr
我还没有测试过这个我本来想要的，但我认为它产生了正确的语言。
我在 PLY (Python Lexx Yacc) 中有一个大型语法，用于一种在解析方面有一些特殊挑战的语言。该语言允许两种调用的前导语法看起来几乎相同，直到非终端调用结束。这为 reduce/reduce 冲突提供了很多机会，因为沿途令牌的语义不同，但可以由相同的终端令牌构建。我已经提取了下面语法的简单 before/after 版本，我会稍微解释一下。
最初，表达式是一个典型的 "Stratified Grammar," 接受调用和文字等到初级，然后是初级到一元，然后是二进制到一般表达式。问题是带有两个参数的 Call_expr 与以 '/' 之前的两个 ID 开头的 Iter_expr 版本冲突。冲突发生在调用中第一个参数之后的逗号上，因为最初 Expr -> ... -> Primary_expr -> Name_expr -> Id 是允许的。解析器可以将 Id 减少到 Expr 以匹配 Call_expr，或者保留它以匹配 Iter_expr。展望未来并没有帮助它做出决定。如果调用的第一个参数只是一个标识符（如变量），这是合法的歧义。考虑输入 id > id ( id , id ... .
我的方法是制作一种可以而不是只是Id的表达式。我通过所有表达式添加了生产链，为它们提供“_nn”版本--'not a name.' 然后我可以为 Call_expr 定义生产，在第一个参数中使用任何语法，使其更不仅仅是一个名称（例如操作员、呼叫等）将其减少到 BinOp_expr_nn，并且 还 允许呼叫生产仅具有 Id 作为第一个参数。这应该说服解析器只是转移，直到它可以解析 Iter_expr 或 Call_expr （或者至少知道它在哪条路径上。）
您可能已经猜到了，这把一切都搞砸了:)。修改表达式链也会修改 Primary_expr，我仍然需要将其减少到 Id。但现在，这是一个 reduce/reduce 冲突——每个 Primary_expr 都可以留在那里或继续 Unary_expr。我可以命令他们做出选择（这可能有效），但我希望我最终会追逐一个又一个。
所以，我的问题是：是否有人可以阐明如何允许相同的标记表示不同的语义（即 expr 与 id）仍然可以像 PLY 一样用 LALR(1) 解析的技术？除此之外，任何有助于解决问题的有用技巧？这可以消除歧义吗？
terminals: '+' '^' ',' '>' '(' ')' '/' ':' 'id' 'literal'
(i.e. punctuation (besides '->' and '|', initial-lower-case words)
non-terminals: initial-Upper-case words
原文语法：
S'-> S
S -> Call_expr
| Iter_expr
Expr -> BinOp_expr
BinOp_expr -> Unary_expr
BinOp_expr -> BinOp_expr '+' BinOp_expr
Unary_expr -> Primary_expr
| '^' BinOp_expr
Primary_expr -> Name_expr
| Call_expr
| Iter_expr
| Literal_expr
Name_expr -> Id
Args -> Expr
| Args ',' Expr
Call_expr -> Primary_expr '>' Id '(' ')'
| Primary_expr '>' Id '(' Args ')'
Iter_expr -> Primary_expr '>' Id '(' Id '/' Expr ')'
| Primary_expr '>' Id '(' Id ':' Id '/' Expr ')'
| Primary_expr '>' Id '(' Id ',' Id ':' Id '/' Expr ')'
Literal_expr -> literal
Id -> id
我试图消除 Call_expr 中第一个参数的歧义：
S'-> S
S -> Call_expr
| Iter_expr
Expr -> BinOp_expr_nn
| BinOp_expr
BinOp_expr -> BinOp_expr_nn
| Unary_expr
BinOp_expr_nn -> Unary_expr_nn
| BinOp_expr '+' BinOp_expr
Unary_expr -> Primary_expr
| Unary_expr_nn
Unary_expr_nn -> Primary_expr_nn
| '^' BinOp_expr
Primary_expr -> Primary_expr_nn
| Name_expr
Primary_expr_nn -> Call_expr
| Iter_expr
| Literal_expr
Name_expr -> Id
Args -> Expr
| Args ',' Expr
Call_expr -> Primary_expr '>' Id '(' ')'
| Primary_expr '>' Id '(' Expr ')'
| Primary_expr '>' Id '(' Id , Args ')'
| Primary_expr '>' Id '(' BinOp_expr_nn , Args ')'
Iter_expr -> Primary_expr '>' Id '(' Id '/' Expr ')'
| Primary_expr '>' Id '(' Id ':' Id '/' Expr ')'
| Primary_expr '>' Id '(' Id ',' Id ':' Id '/' Expr ')'
Literal_expr -> literal
Id -> id
尽管你的标题 post，但你的语法没有歧义。由于您提到的原因，它根本不是 LR(1)：输入
A ( B ,
可以是 Call_expr 或 Iter_expr 的开始。在第一种情况下，B 必须缩减为 Expr，然后再缩减为 Args；在第二种情况下，它一定不能减少，因为当right-hand侧id '(' id ',' id ':' id '/' Expr ')'减少时它仍然是id。不能简单地通过查看单个前瞻标记（、）来做出决定，因此存在 shift-reduce 冲突。
这个冲突最多可以用两个额外的先行标记来解决，因为只有在 、 后面紧跟着一个 id 和然后是 :。这样就构成了语法 LALR(3)。不幸的是，Ply 不生成 LALR(3) 解析器（yacc/bison 也不生成），但有一些替代方案。
1。使用不同的解析算法
由于语法是明确的，因此可以使用 GLR 解析器毫无问题地解析（并且无需任何修改）。 Ply 也不生成 GLR 解析器，但 Bison 可以。这不太可能对你有多大用处，但我想我应该提一下，以防你没有被限制使用 Python.
2。使用允许一些无效输入的语法，并通过语义分析丢弃它们
这几乎可以肯定是最简单的解决方案，也是我通常推荐的解决方案。如果将 Iter_expr 的定义更改为：
Iter_expr : id '(' id '/' Expr ')'
| id '(' Args ':' id '/' Expr ')'
那么它仍然会识别每个有效输入（因为 id 和 id , id 都是 Args 的有效实例）。这消除了 shift-reduce 冲突；实际上，它让解析器避免在遇到 )（表示 Call_expr）或 之前做出决定：（表示一个Iter_expr）。 （Iter_expr 的第一个替代方案没有问题，因为移动 / 而不是减少 id 的决定不需要额外的前瞻性。）
当然，Iter_expr 的第二个产生式会识别出很多不是有效迭代表达式的东西：超过 2 个项目的列表，以及包含比单个 [= 更复杂的表达式的列表19=]。但是，这些输入根本不是有效程序，因此可以在 Iter_expr 的操作中简单地拒绝它们。识别有效迭代的精确代码将取决于您如何表示 AST，但这并不复杂：只需检查以确保 Args 的长度是 1 或 2，并且列表中的每个项目都是只是一个 id.
3。使用词汇技巧
弥补前瞻信息不足的一种方法是通过将必要的前瞻信息收集到缓冲区中并将其收集在词法分析器中，并且仅在其句法类别已知时才输出词素。在这种情况下，词法分析器可以查找序列 '(' id ',' id ':' 并标记第一个 id 以便它只能在 Iter_expr 中使用。在这种情况下，语法的唯一变化是：
Iter_expr : id '(' id '/' Expr ')'
| id '(' id ':' id '/' Expr ')'
| id '(' iter_id ',' id ':' id '/' Expr ')'
虽然这在这种特殊情况下可以正常工作，但它不是很容易维护。特别是，它依赖于能够定义一个可以在词法分析器中实现的简单且明确的模式。由于该模式是语法的简化，因此未来的某些语法添加很可能会创建也与相同模式匹配的语法。 （出于某种原因，这被称为词汇“hack”。）
4。查找 LALR(1) 文法
如上所示，此语法为 LALR(3)。但是没有 LALR(3) 语言 这样的东西。或者更准确地说，如果一种语言有 LALR(k) 文法，那么它也有 LALR(1) 文法，并且可以从 LALR(k) 文法中机械地产生该文法。此外，给定 one-symbol 前瞻语法的解析，可以为原始语法重建解析树。
因为mechanically-produced文法比较多，这个程序不是很吸引人，不知道算法的实现。相反，最常见的是尝试重写语法的一部分，就像您在原始问题中尝试的那样。这当然可以做到，但最终结果并不完全直观。
然而，这并不难。例如，这里是你的语法的一个稍微简化的版本，删除了冗余的单元产生式，并修复了几个运算符优先级（可能不正确，因为我不知道你的目标是什么语义）。
名称以N结尾的产品不生产ID。对于它们中的每一个，都有一个相应的产生式，没有 N 添加了 ID。完成后，有必要重写 Args 以使用 ExprN 产生式，并允许以一两个 ID 开头的各种参数列表。 Chain 制作只是为了避免一些重复。
Start : Call
| Iter
Expr : ID
| ExprN
ExprN : UnaryN
| Expr '+' Unary
Unary : ID
| UnaryN
UnaryN : ChainN
| '^' Chain
Chain : ID
| ChainN
ChainN : PrimaryN
| Chain '>' CallIter
PrimaryN: LITERAL
| Call
| Iter
| '(' Expr ')'
Call : ID '(' ')'
| ID '(' ID ')'
| ID '(' ID ',' ID ')'
| ID '(' Args ')'
Iter : ID '(' ID '/' Expr ')'
| ID '(' ID ':' ID '/' Expr ')'
| ID '(' ID ',' ID ':' ID '/' Expr ')'
Args : ExprN ExprList
| ID ',' ExprN ExprList
| ID ',' ID ',' Expr ExprList
ExprList:
| ExprList ',' Expr
我还没有测试过这个我本来想要的，但我认为它产生了正确的语言。