Fox*_*oxy 4 f# parsing ocaml operators fparsec
我对“真正的解析器”（例如 F# 或 Haskell）解析自定义运算符的方式有点困惑。对于“普通”语言，我们只需定义一个 AST 节点，在该节点上有预定义的运算符可能性，例如：+, -, *, ==, >=, +=, ... 等。
但我想知道如何使用允许您创建自定义运算符的函数式语言来完成此操作，让我们以 OCaml 为例，它与 F#（我的实现语言）非常接近，并且众所周知。
\n\n因此，每个运算符都是一个函数，具有类型和定义，我们可以创建自己的运算符：
\n\nval (+) : \'a -> \'a -> \'a\nlet (+) x y = x + y\n\nval (|>) : \'a -> (\'a -> \'b) -> \'b\nlet (|>) x f = f x\n所以我想知道它是如何与解析一起工作的。
\n\n1）解析器如何知道我们要使用自定义运算符？如果我们使用的函数在第一个参数中采用另一个函数，在第二个参数中采用另一个元素，那么它如何知道我们调用的是函数而不是使用中缀运算符？
\n\nlet example x =\n // Do we add up, or do we call the function "takeOpAndOther"?\n takeOpAndOther + x\n2）为了回答这个问题，我想到了一种在F#中做到这一点的方法，感谢FParsec。我想到的第一个解决方案是简单地使用OperatorPrecedenceParser. 令人担忧的是，这意味着仅适用于预定义的运算符（或者如果有办法用它来做我想做的事情，我不知道如何做）。
然后我想到创建一个简单的解析器：
\n\nopen FParsec\n\ntype Expression =\n | Number of int\n | InfixF of Expression * string * Expression\n | DataName of string\n | FunctionCall of string * Expression list\n\nlet ws = skipMany (pchar \' \' <|> pchar \'\\t\') <?> ""\nlet ws1 = skipMany1 (pchar \' \' <|> pchar \'\\t\') <?> ""\n\nlet identifier = many1Satisfy (fun c -> isLetter c || isDigit c)\n\nlet allowedSymbols =\n [ \'!\'; \'@\'; \'#\'; \'$\'; \'%\'; \'^\'; \'&\';\n \'\xc2\xa7\'; \'*\'; \'\xc2\xb0\'; \'.\'; \'~\'; \':\'; \'-\';\n \'+\'; \'=\'; \'?\'; \'/\'; \'>\'; \'<\'; \'|\'; ]\n\nlet customOperatorIdentifier = many1SatisfyL (fun c -> allowedSymbols |> List.contains c) "valid custom operator"\n\n// I call about this parser\nlet rec infixF () = parse {\n let! lvalue = ws >>? expression\n let! op = ws >>? customOperatorIdentifier\n let! rvalue = ws >>? expression\n return InfixF(lvalue, op, rvalue)\n }\n\nand number = pint32 |>> Number\n\nand dataName = identifier |>> DataName\n\nand functionCall () = parse {\n let! id = ws >>? identifier\n let! parameters = sepEndBy1 (ws >>? expression) ws1\n return FunctionCall(id, parameters)\n }\n\nand expression =\n attempt number <|>\n attempt dataName <|>\n attempt (functionCall ()) <|>\n infixF ()\n\nlet test code =\n match run (ws >>? expression .>>? ws .>>? eof) code with\n | Success (result, _, _) -> printfn "%A" result\n | Failure (msg, _, _) -> printfn "%s" msg\n\ntest "87 + 12"\n但正如您所料，它并没有按预期工作。事实上，随着代码的呈现（因为当我infixF单独尝试并将其从 中删除expression时，它会起作用，但显然仅适用于一个表达式：x + y，但不是x + y + z），每次都会导致溢出错误。我认为这是我在实施中遇到的主要问题。
然而，所描述的两种解决方案并不能满足我的问题之一，即函数运算符的发送。
\n\n简而言之......我有一些问题希望得到解释，还有一个我想解决的实施问题。
\n\n谢谢你！:)
\n所以你\xe2\x80\x99是对的，困难的部分是优先级。我认为对于 ML 风格的语言来说大约有两种处理方法
\n\nOcaml 采用选项 1。运算符的优先级和结合性由其第一个字符定义。
\n\nHaskell 采用选项 2。优先级和结合性是用语句定义的（并且声明可以在使用运算符之后出现）。
\n\n了解如何解析 (1) 非常简单：您只需正常解析它，除了不只允许+该优先级的运算符，您定义任何以 开头的运算符+。这就留下了一个问题：您应该如何处理解析像a +* b +- c. 我不\xe2\x80\x99t 知道 ocaml 如何关联它，但我的猜测要么基于第二个字符，要么处于相同的优先级（例如，像解析+并-处于相同的优先级并关联到左侧，因此a + b - c + d解析为((a + b) - c) + d）。
我认为你对解析（2）也有正确的想法，但它很棘手。我认为你的类型有点错误，你真正想要的是这样的：
\n\ntype operator = Op of string\ntype expression =\n | Var of string\n | Operator of operator\n | App of expression * expression\n | Tuple of expression list\n | Infix of expression * (operator * expression) list\n具体来说你可以\xe2\x80\x99tInfix of expression * operator * expression因为那么你如何解析a OP b OP c？你基本上有两个选择：
Infix (Infix (Var a, Op OP, Var b), Op OP, Var c)Infix (Var a, Op OP, Infix (Var b, Op OP, Var c))选项 1 相当于(a OP b) OP c并适用于-，|>但不是 Haskell 风格$，当然也不适用于a + b * c。同样，选项 2 适用于+但不适用于-or /。此外，在排序优先级之前仅撤消此损坏是不够的，因为(a OP b) OP c即使表达式未损坏，也必须将其解析为选项 1。
请注意，我们（如果我们想要一种 ML 风格的语言）需要一种将运算符的功能表达为值的方法，例如，(+)但这可以包含在Var.
一旦达到了这种级别的解析，您就可以等待，直到确定了运算符的任何运算符优先级规则，然后才可以进行解析。
\n\n其他一些可能值得考虑的事情：
\n\n!。Haskell 允许后缀运算符作为扩展，但仅使用切片（即扩展放宽了(x*)from (\\y -> (*) x y)to的定义((*) x)，因此(*)可能采用单个参数。如果您希望能够让用户定义前置和后缀运算符，您可以更改类型放弃应用程序和表达式之间可以有一个运算符的规则，然后有一个步骤将列表解析expression | operator为正常的内容，例如a * + b解析为a (*(+b)), (a) * (+b), (a*) (+b), (a*) + (b), 或((a*)+) b? 也许这个困难对人类读者来说也很糟糕。它\xe2\x80\x99s 可能值得注意的是perl6 方式作为另一种选择。在这种情况下，运算符必须在使用之前定义其优先级和结合性/固定性，并且解析器在声明和使用的它们之间动态添加这些内容（也可以使用该语言的整个语法来执行此操作，因此可以解析未来的表达式依赖于评估早期的稍微不那么疯狂）。
\n