解析自定义中缀运算符 + 使用 FParsec 实现

Question

我有点停留在"真正的解析器"(如 F# 或 Haskell)解析自定义运算符的方式上。对于"普通"语言，我们只需定义一个 AST 节点，在该节点上将有预定义的运算符可能性，例如：+、-、*、==、>=、+=、...等。

但是我想知道如何在允许您创建自定义运算符的函数式语言中做到这一点，让我们以 OCaml 为例，非常接近 F#(我的实现语言)，并且非常有名。

因此，每个运算符都是一个函数，具有类型和定义，我们可以创建自己的运算符：

val (+) : 'a -> 'a -> 'a
let (+) x y = x + y
val (|>) : 'a -> ('a -> 'b) -> 'b
let (|>) x f = f x

所以我想知道它如何与解析一起工作以使其工作。

1)解析器如何知道我们要使用自定义运算符？如果我们使用一个函数，在第一个参数中接受另一个函数，在第二个参数中接受另一个元素，它怎么知道我们调用了一个函数而不是使用中缀运算符？

let example x =
// Do we add up, or do we call the function "takeOpAndOther"?
takeOpAndOther + x

2)为了回答这个问题，我想到了一种方法在F#中做到这一点，感谢FParsec。想到的第一个解决方案是简单地使用OperatorPrecedenceParser.令人担忧的是，这意味着仅适用于预定义的运算符(或者如果有一种方法可以用它做我想做的事情，我不知道怎么做)。

然后我想创建一个简单的解析器：

open FParsec
type Expression =
| Number of int
| InfixF of Expression * string * Expression
| DataName of string
| FunctionCall of string * Expression list
let ws = skipMany (pchar ' ' <|> pchar 't') <?> ""
let ws1 = skipMany1 (pchar ' ' <|> pchar 't') <?> ""
let identifier = many1Satisfy (fun c -> isLetter c || isDigit c)
let allowedSymbols =
[ '!'; '@'; '#'; '$'; '%'; '^'; '&';
'§'; '*'; '°'; '.'; '~'; ':'; '-';
'+'; '='; '?'; '/'; '>'; '<'; '|'; ]
let customOperatorIdentifier = many1SatisfyL (fun c -> allowedSymbols |> List.contains c) "valid custom operator"
// I call about this parser
let rec infixF () = parse {
let! lvalue = ws >>? expression
let! op = ws >>? customOperatorIdentifier
let! rvalue = ws >>? expression
return InfixF(lvalue, op, rvalue)
}
and number = pint32 |>> Number
and dataName = identifier |>> DataName
and functionCall () = parse {
let! id = ws >>? identifier
let! parameters = sepEndBy1 (ws >>? expression) ws1
return FunctionCall(id, parameters)
}
and expression =
attempt number <|>
attempt dataName <|>
attempt (functionCall ()) <|>
infixF ()
let test code =
match run (ws >>? expression .>>? ws .>>? eof) code with
| Success (result, _, _) -> printfn "%A" result
| Failure (msg, _, _)    -> printfn "%s" msg
test "87 + 12"

除了，正如您所料，它没有按预期工作。事实上，随着代码的呈现(因为当我单独尝试infixF并将其从expression中删除时，它就可以工作，但显然仅适用于一个表达式：x + y，但不是x + y + z)，每次都会导致溢出错误。我认为，这是我在实现中遇到的主要问题。

但是，所描述的两个解决方案不能满足我的一个问题，即发送函数运算符。

总之。。。我有一些问题想得到解释，还有一个实现问题想解决。

谢谢！:)

Answer 1

所以你是对的，困难的部分是优先权。我认为对于ML风格的语言，大约有两种方法可以处理它

1. 优先级由固定规则定义
2. 优先级由用户定义

Ocaml 执行选项 1。运算符的优先级和关联性由其第一个字符定义。

Haskell做选项2。优先级和关联性由语句定义(声明可以在使用运算符之后出现)。

了解如何解析 (1) 非常简单：您只需正常解析它，除了只允许运算符在该优先级+，而是定义任何以+开头的运算符。这就留下了一个问题，即您应该如何处理解析像a +* b +- c这样的表达式。我不知道 ocaml 会如何关联这一点，但我的猜测要么基于第二个字符，要么基于相同的优先级级别(例如，在同一优先级解析+和-并向左关联，以便a + b - c + d解析为((a + b) - c) + d)。

我认为您也有解析 (2) 的正确想法，但这很棘手。我认为你的类型有点错误，你真正想要的是这样的：

type operator = Op of string
type expression =
| Var of string
| Operator of operator
| App of expression * expression
| Tuple of expression list
| Infix of expression * (operator * expression) list

具体来说你不能有Infix of expression * operator * expression，因为那你如何解析a OP b OP c？您基本上有两个选择：

1. Infix (Infix (Var a, Op OP, Var b), Op OP, Var c)
2. Infix (Var a, Op OP, Infix (Var b, Op OP, Var c))

选项 1 等同于(a OP b) OP c并且适用于-，|>但不是 Haskell 风格的$，当然不适用于a + b * c。同样，选项 2 适用于+，但不适用于-或/。此外，在排序优先级之前仅撤消此重整是不够的，因为表达式(a OP b) OP c必须解析为选项 1，即使它已取消修改。

请注意，我们(如果我们想要ML风格的语言)需要一种方法来将运算符的函数表示为值，例如(+)，但这可以例如包含在Var中。

获得此级别的解析后，您可以等到确定运算符的任何运算符优先级规则，然后才能进行分析。

其他一些可能值得考虑的事情：

1. 前缀/后缀运算符：Ocaml 允许前缀运算符以特定符号开头，例如!.Haskell允许后缀运算符作为扩展，但只能使用切片(即扩展将(x*)的定义从(y -> (*) x y)放宽到((*) x)，因此(*)可以接受单个参数。如果您希望能够让用户定义前缀和后缀运算符，您可以更改类型以删除应用程序以及表达式之间可以只有一个运算符的规则，然后有一个步骤将expression | operator列表解析为理智的东西，例如，a * + b解析为a (*(+b))，(a) * (+b)、(a*) (+b)、(a*) + (b)还是((a*)+) b？也许这个困难对人类读者也不利。
2. 如何处理优先级？在Haskell中，您可以选择一个从0到9的整数。在 perl6 中，你只是说 例如 * 比 + 更紧密，如果两个具有未定义关系的运算符一起出现，语言需要你输入 parens。

也许值得注意的是 perl6 方式作为另一种选择。在这个中，运算符在使用之前必须定义它们的优先级和关联性/固定性，并且解析器在声明和使用它们之间动态添加这些(也可以对语言的整个语法执行此操作，因此解析未来的表达式依赖于评估早期的表达式稍微不那么疯狂)。