一个简单的lambda演算解析器与FParsec

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.这个函数返回一对解析器"handle",可以说是一个包含解析器实现的可变单元.一旦被要求实际解析某些东西,"句柄"就会将调用转发给实现.

获取此对后,您可以使用"handle"实现递归的其他部分,然后创建转发的解析器的实现并将其分配给可变单元.

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