lambda - 带有 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和反之亦然。我怎样才能摆脱这种依赖？

Answer 1

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

获得这对之后，就可以使用“句柄”来实现递归的另一部分，然后创建转发的解析器的实现并将其分配给可变单元格。

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