parsing - 解析时添加运算符

Question

我尝试了一些 Haskell 的解析器生成器，这里使用 Happy。我以前使用解析器组合器，例如 Parsec，现在我无法实现的一件事是动态添加(在执行期间)新的外部定义运算符。例如，Haskell 有一些基本的运算符，但我们可以添加更多，赋予它们优先级和固定性。所以我想知道如何使用 Happy 重现这个，遵循 Haskell 设计(查看下面要解析的示例代码)，如果它不是平凡可行的，或者它是否应该通过解析器组合器完成。

-- Adding the new operator
infixl 5 ++

(++) :: [a] -> [a] -> [a]
[]     ++ ys = ys
(x:xs) ++ ys = x : xs ++ ys

-- Using the new operator taking into consideration fixity and precedence during parsing
example = "Hello, " ++ "world!"

Answer 1

Haskell 只允许几个优先级。所以你并不严格需要动态语法；您可以只使用优先级标记类而不是单个运算符写出语法，让词法分析器解决将给定符号与给定优先级相关联的问题。

实际上，这将运算符的动态添加移动到词法分析器。这是一个有点不舒服的设计决定，尽管在某些情况下它可能不太难实现。这是一种令人不舒服的设计，因为它需要对词法分析器进行语义反馈；至少，词法分析器需要查阅符号表来弄清楚它正在查看的是什么类型的标记。至少在 Haskell 的情况下，固定性声明是有范围的这一事实让这变得更加不舒服，因此为了跟踪固定性信息，词法分析器还需要了解范围规则。

在实践中，大多数允许程序文本定义运算符和运算符优先级的语言的工作方式与 Haskell 编译器的工作方式完全相同:表达式被语法解析为一个简单的项目列表(其中带括号的子表达式算作一个项目)，并且在后来的语义分析中，考虑到优先级和关联性规则，使用调车场算法的简单版本将列表重新排列成实际的树。 (这是一个简单的版本，因为它不需要处理带括号的子结构。)

这个设计决定有几个原因:

1. 如上所述，词法分析器要弄清楚符号的优先级(或者即使符号是具有优先级的运算符)需要词法分析器和解析器之间的密切合作，很多人会说违反了关注点分离。更糟糕的是，如果没有小的固定前瞻，就很难或不可能使用解析技术，例如 GLR 解析器。

2. 许多语言的优先级都高于 Haskell。在某些情况下，甚至优先级的数量也没有由语法定义。例如，在 Swift 中，您可以声明自己的 precedence levels ，并且您定义的级别不是用数字而是与另一个先前定义的级别进行比较，从而导致优先级之间的部分顺序。

   恕我直言，这实际上是一个比 Haskell 更好的设计决策，部分原因是它避免了同时具有左结合运算符和右结合运算符的优先级的歧义，但更重要的是因为相对优先级声明既避免了魔数(Magic Number)又允许解析器来标记来自不同模块的运算符的模糊使用。换句话说，它不会强制优先声明机械地应用于任何一对完全不相关的运算符；从这个意义上说，它使运算符声明更容易编写。

3. 语法要简单得多，而且可以说更容易理解，因为大多数人无论如何都依赖优先表而不是分析语法产生式来弄清楚运算符如何相互作用。从这个意义上说，由语法设置优先级比文档更能分散注意力。将 C++ 语法作为优先表比语法更易于阅读的一个很好的例子。

   另一方面，正如 C++ 语法也说明的那样，语法比简单的优先级声明更通用，因为它可以表达不对称的优先级。 (语法并不总是优雅地表达这些，但它们是可以表达的。)非对称优先级的一个经典示例是 lambda 构造 (λ ID expr)，它非常松散地绑定(bind)到右边并且非常紧靠左边:a ∘ λ b b ∘ a 的预期解析永远不会引用 ∘ 的结合律，因为 λ 位于它们之间。

实际上，以后构建树的成本非常低。构建树的算法众所周知、简单且廉价。