在表达式解析中处理不明确但破坏性的语法
Handling in-ambiguous yet breaking syntax in expression parsing
上下文
我最近遇到了一个问题，我无法在自己编写的解析器中自行解决。
这个解析器是我正在构建的编译器中的一个组件，问题是关于编程语言解析中必需的表达式解析。
我的解析器使用递归下降来解析表达式。
问题
我使用普通的常规语言解析规则解析表达式，我已经消除了所有规则中的左递归，但是有一种语法 "ambiguity" 我的解析器根本无法处理，它涉及泛型。
comparison → addition ( ( ">" | ">=" | "<" | "<=" ) addition )* ;
是我用来解析表达式中比较节点的规则
另一方面，我决定以这种方式解析泛型表达式：
generic → primary ( "<" arguments ">" ) ;
哪里
arguments → expression ( "," expression )* ;
现在由于泛型表达式具有更高的优先级，因为它们是语言结构而不是数学表达式，这会导致泛型解析器在不应该尝试解析表达式的情况下。
例如，在 a<2 中，它会将 "a" 解析为标识符类型的主要元素，之后立即找到泛型类型的语法，解析并失败，因为找不到结束标记。
遇到这种情况有什么解决办法？特别是在像 C++ 这样的语言中，如果我没记错的话，泛型也可以在其中包含表达式 arr<1<2> 可能是合法的语法。
这是特殊情况还是需要修改我不知道的语法定义？
谢谢
for example in a<2 it will parse "a" as a primary element of the identifier type, immideatly afterwards find the syntax for a generic type, parse that and fail as it cant find the closing tag
这个特殊情况可以通过回溯或无限前瞻来解决。正如您所说，当将其解释为泛型时，解析器最终会失败，因此当发生这种情况时，您可以返回并将其解析为关系运算符。前瞻变体是在看到 < 时向前看，以检查 < 是否后跟逗号分隔的类型名称和 > 并且只有在出现这种情况时才进入通用规则案.
但是，如果两种解释在语法上都有效（意味着语法实际上是模棱两可的），则该方法不再有效。一个例子是 x<y>z，它可以是 x<y> 类型的变量 z 的声明，也可以是两个比较。这个例子有点不成问题，因为后者的意思几乎从来不是预期的意思，所以总是将它解释为前者是可以的（例如，这发生在 C# 中）。
现在如果我们允许表达式，它会变得更复杂。对于 x<y>z 很容易说这不应该被解释为两个比较，因为将比较结果与其他东西进行比较是没有意义的（在许多语言中，在布尔值上使用关系运算符无论如何都是类型错误） .但是对于像 a<b<c>() 这样的东西，有两种解释可能都是有效的：要么 a 是一个用通用参数调用的通用函数 b<c 要么 b 是一个通用函数通用参数 c（并且 a 与调用该函数的结果进行比较）。在这一点上，不再可能仅通过句法规则来解决歧义：
为了支持这一点，您需要检查给定的 primary 是否引用通用函数并根据它做出不同的解析决策，或者让您的解析器生成多棵树以防出现歧义然后 select 正确的在后面的阶段。前一个选项意味着您的解析器需要跟踪当前定义了哪些泛型函数（并且在范围内），然后仅当给定的 primary 是其中一个函数的名称时才进入泛型规则。请注意，如果您允许在使用函数后定义函数，这将变得更加复杂。
所以总而言之，支持表达式作为通用参数需要您在解析时跟踪哪些函数在范围内，并使用该信息来做出解析决策（意味着您的解析器是上下文敏感的）或生成多个可能的 AST。如果没有表达式，您可以保持上下文无关和明确，但需要回溯或任意前瞻（意味着它是 LL(*)）。
由于这些都不是理想的，一些语言更改了使用显式类型参数调用泛型函数的语法，使其成为 LL(1)。例如：
- Java 将方法的通用参数列表放在方法名称之前，即
obj.<T>foo() 而不是 obj.foo<T>().
- Rust 在泛型参数列表之前需要
::：foo::<T>() 而不是 foo<T>()。
- Scala 只对泛型使用方括号（数组下标使用括号）：
foo[T]() 而不是 foo<T>()。
上下文
我最近遇到了一个问题，我无法在自己编写的解析器中自行解决。
这个解析器是我正在构建的编译器中的一个组件，问题是关于编程语言解析中必需的表达式解析。
我的解析器使用递归下降来解析表达式。
问题
我使用普通的常规语言解析规则解析表达式，我已经消除了所有规则中的左递归，但是有一种语法 "ambiguity" 我的解析器根本无法处理，它涉及泛型。
comparison → addition ( ( ">" | ">=" | "<" | "<=" ) addition )* ;
是我用来解析表达式中比较节点的规则
另一方面，我决定以这种方式解析泛型表达式：
generic → primary ( "<" arguments ">" ) ;
哪里
arguments → expression ( "," expression )* ;
现在由于泛型表达式具有更高的优先级，因为它们是语言结构而不是数学表达式，这会导致泛型解析器在不应该尝试解析表达式的情况下。
例如，在 a<2 中，它会将 "a" 解析为标识符类型的主要元素，之后立即找到泛型类型的语法，解析并失败，因为找不到结束标记。
遇到这种情况有什么解决办法？特别是在像 C++ 这样的语言中，如果我没记错的话，泛型也可以在其中包含表达式 arr<1<2> 可能是合法的语法。
这是特殊情况还是需要修改我不知道的语法定义？
谢谢
for example in a<2 it will parse "a" as a primary element of the identifier type, immideatly afterwards find the syntax for a generic type, parse that and fail as it cant find the closing tag
这个特殊情况可以通过回溯或无限前瞻来解决。正如您所说，当将其解释为泛型时，解析器最终会失败，因此当发生这种情况时，您可以返回并将其解析为关系运算符。前瞻变体是在看到 < 时向前看，以检查 < 是否后跟逗号分隔的类型名称和 > 并且只有在出现这种情况时才进入通用规则案.
但是，如果两种解释在语法上都有效（意味着语法实际上是模棱两可的），则该方法不再有效。一个例子是 x<y>z，它可以是 x<y> 类型的变量 z 的声明，也可以是两个比较。这个例子有点不成问题，因为后者的意思几乎从来不是预期的意思，所以总是将它解释为前者是可以的（例如，这发生在 C# 中）。
现在如果我们允许表达式，它会变得更复杂。对于 x<y>z 很容易说这不应该被解释为两个比较，因为将比较结果与其他东西进行比较是没有意义的（在许多语言中，在布尔值上使用关系运算符无论如何都是类型错误） .但是对于像 a<b<c>() 这样的东西，有两种解释可能都是有效的：要么 a 是一个用通用参数调用的通用函数 b<c 要么 b 是一个通用函数通用参数 c（并且 a 与调用该函数的结果进行比较）。在这一点上，不再可能仅通过句法规则来解决歧义：
为了支持这一点，您需要检查给定的 primary 是否引用通用函数并根据它做出不同的解析决策，或者让您的解析器生成多棵树以防出现歧义然后 select 正确的在后面的阶段。前一个选项意味着您的解析器需要跟踪当前定义了哪些泛型函数（并且在范围内），然后仅当给定的 primary 是其中一个函数的名称时才进入泛型规则。请注意，如果您允许在使用函数后定义函数，这将变得更加复杂。
所以总而言之，支持表达式作为通用参数需要您在解析时跟踪哪些函数在范围内，并使用该信息来做出解析决策（意味着您的解析器是上下文敏感的）或生成多个可能的 AST。如果没有表达式，您可以保持上下文无关和明确，但需要回溯或任意前瞻（意味着它是 LL(*)）。
由于这些都不是理想的，一些语言更改了使用显式类型参数调用泛型函数的语法，使其成为 LL(1)。例如：
- Java 将方法的通用参数列表放在方法名称之前，即
obj.<T>foo()而不是obj.foo<T>(). - Rust 在泛型参数列表之前需要
::：foo::<T>()而不是foo<T>()。 - Scala 只对泛型使用方括号（数组下标使用括号）：
foo[T]()而不是foo<T>()。