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のようなものにマッチします：私は、次の文法を解析します。

私の問題は、2つのルールがお互いに依存していることである：

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で実装できます。この関数は、言い換えれば、パーサの「ハンドル」と、パーサの実装を保持する変更可能なセルのペアを返します。実際に何かを解析するために呼び出された「ハンドル」は、呼び出しを実装に転送します。

このペアを取得した後、「ハンドル」を使用して再帰の他の部分を実装し、転送されたパーサの実装を作成し、それを変更可能なセルに割り当てることができます。

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