解析时添加运算符

Add operators during parsing

我尝试使用 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!"

Haskell 只允许几个优先级别。所以你并不严格需要动态语法;您可以只使用 precedence-level 标记 类 而不是单个运算符来写出语法,从而使词法分析器面临将给定符号与给定优先级相关联的问题。

实际上,这将运算符的动态添加移动到词法分析器。 table 的设计决策有点令人不适,但在某些情况下实施起来可能并不难。 table 的设计令人不适,因为它需要对词法分析器进行语义反馈;至少,词法分析器需要参考符号 table 来弄清楚它正在查看的是什么类型的标记。在 Haskell 的情况下,至少,由于固定性声明是有范围的,这让 table 变得更加不舒服,所以为了跟踪固定性信息,词法分析器还需要了解范围规则。

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

做出此设计决定有几个原因:

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

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

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

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

    另一方面,正如 C++ 语法也说明的那样,语法比简单的优先级声明更通用,因为它可以表达不对称的优先级。 (语法并不总是优雅地表达这些,但它们可以被表达。)不对称优先级的一个经典示例是 lambda 构造 (λ ID expr),它向右绑定非常松散,向左绑定非常紧密: a ∘ λ b b ∘ a 的预期解析永远不会参考 ∘ 的关联性;因为 λ 介于它们之间。

实际上,以后构建树的成本非常低。构建树的算法是well-known,简单且便宜。