Ein einfacher Lambda-Kalkül-Parser mit FParsec

Question

Ich bin neu in F # und habe ein ziemlich nerviges Problem. Ich möchte folgende Grammatik analysieren:

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

, dass Dinge wie (lambda x. (lambda y. x y)) z und (lambda x. x) y entsprechen würde.

Mein Problem ist, dass zwei Regeln voneinander abhängig ist:

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 auf papplication und vicebersa abhängt. Wie kann ich diese Abhängigkeit loswerden?

Answer 1

Rekursive Parser können über createParserForwardedToRef implementiert werden. Diese Funktion gibt sozusagen ein Parser-Paar "handle" und eine veränderbare Zelle zurück, die die Parser-Implementierung enthält. Der "Handle", der einmal aufgerufen wurde, um etwas zu parsen, leitet den Anruf an die Implementierung weiter.

Nachdem Sie dieses Paar erworben haben, können Sie den anderen Teil der Rekursion mit dem "Handle" implementieren und dann die Implementierung des weitergeleiteten Parsers erstellen und sie der veränderbaren Zelle zuweisen.

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