parsing - 用户定义的中缀运算符的解析器

Question

我正在为一种可以将函数用作运算符的语言编写解释器。但是，函数内容只有在运行时才能知道。

为此，我考虑了两种解决方案:

解析在运行时完成，使用函数

上的运行时信息

所有用户定义的运算符都使用优先级和关联性的默认值。

我选择了后者，因为我看到了单独解析和执行的许多优点。

现在谈到实现，我很想看看有什么选择。我最初的想法是一个 shift reduce 解析器，但我在构建解析器方面经验很少。

例子:

LHS op RHS : LHS * RHS     /* define a binary operator 'op' */
var : 3                    /* define a variable */
print 5 op var             /* should print 15 */

LHS op RHS : LHS / RHS     /* Re-define op */
print var op var           /* Should print 1 */

在最后一种情况下，解析器将从词法分析器获得:“ id id id id”。只有在运行时我才知道'op' id 是一个运算符。

Answer 1

(根据要求发布评论结果。)

我同意，解决方案 #1 绝对是丑陋的、实现起来复杂且不需要的。解决方案#2 更容易实现和理解。您还可以允许运算符的自定义关联性和优先级，只要它们是静态已知的。主要的是这些事实在解析时是已知的。

至于实际解析，大多数解析器都可以正常工作，因为围绕 id 的任何两个表达式都是自定义中缀运算符的应用程序(如果您允许自定义优先级和关联性，则不太正确，在这种情况下，您需要一个允许确定的算法在解析时以每个运算符(operator)为基础)。无论哪种情况，我个人最喜欢的是“Top Down Operator Precedence Parser”或 Pratt 解析器。我发现以下资源(按对我的有用性排序，YMMV)很好地描述了它:

Simple Top-Down Parsing in Python

Pratt Parsers: Expression Parsing Made Easy

Top Down Operator Precedence

该算法的两个属性使其非常适合这个问题:

关联性(“绑定(bind)能力”)的查找针对每个标记动态发生(允许解析器允许用户为其运算符定义优先级)。

手工编写非常简单[*]，你可能不得不这样做，因为这样的动态程度超出了大多数(至少我所知道的)解析器生成器的范围。

[*] 我个人用 500 行 Python 代码和 2-3 天的工作为 Pascal 的一个非常大的(仅缺少 case 、多维数组，也许还有一些晦涩的细节)子集编写了一个解析器，剩下的只是缺失因为当时使用它的软件的其他部分更有趣，而我没有理由实现其余部分。