一個簡單的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和vicebersa。我如何擺脫這種依賴關係？

Answer 1

遞歸解析器可以通過createParserForwardedToRef實現。這個函數返回一對解析器「句柄」，可以這麼說，還有一個可變單元，它包含解析器實現。曾經呼籲實際解析某些內容的「句柄」將會將調用轉發給實現。

獲得此對後，您可以使用「句柄」實現遞歸的另一部分，然後創建轉發的解析器的實現並將其分配給可變單元格。

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