带有 FParsec 的简单 lambda 演算解析器

Question

我是 F# 的新手，遇到了一个非常烦人的问题。我想解析以下语法：

Application := Expression Expression
Expression  := "(" "lambda" Name "." Application ")"
             | Name
Name        := [a-z]+

这将匹配 (lambda x. (lambda y. x y)) z 和 (lambda x. x) y。

我的问题是两个规则相互依赖：

let popen = pchar '('
let pclose = pchar ')'
let pname = many1 letter |>> Seq.toArray |>> System.String |>> NameNode
let plambda = pstring "lambda"
let pdot = pchar '.'
let phead = plambda >>. pname .>> pdot
let pexpression = 
        popen >>. pname .>>. papplication .>> pclose |>> ExpressionNode
    <|> pname
let papplication = pexpression .>>. pexpression

pexpression 取决于 papplication 和 vicebersa。我怎样才能摆脱这种依赖？

Answer 1

递归解析器可以通过createParserForwardedToRef实现。这个函数 returns 一对解析器 "handle"，可以这么说，以及一个包含解析器实现的可变单元格。 "handle"，一旦被调用实际解析某些东西，就会将调用转发给实现。

获取这对后，您可以使用 "handle" 实现递归的另一部分，然后创建转发解析器的实现并将其分配给可变单元格。

let pexpression, pexpressionImpl = createParserForwardedToRef()
let papplication = pexpression .>>. pexpression
pexpressionImpl := 
       popen >>. pname .>>. papplication .>> pclose |>> ExpressionNode
   <|> pname

带有 FParsec 的简单 lambda 演算解析器

A simple lambda calculus parser with FParsec

lambda

f#

fparsec