FParsec中的遞歸語法

我已經決定檢查FParsec並嘗試爲λ表達式編寫解析器。事實證明，渴望使得遞歸解析變得困難。我該如何解決這個問題？FParsec中的遞歸語法

代碼：

open FParsec 

type λExpr = 
    | Variable of char 
    | Application of λExpr * λExpr 
    | Lambda of char * λExpr 

let rec FV = function 
    | Variable v -> Set.singleton v 
    | Application (f, x) -> FV f + FV x 
    | Lambda (x, m) -> FV m - Set.singleton x 

let Λ0 = FV >> (=) Set.empty 

let apply f p = 
    parse 
     { let! v = p 
      return f v } 

let λ e = 

    let expr, exprR = createParserForwardedToRef() 

    let var = lower |> apply Variable 

    let app = tuple2 expr expr 
       |> apply Application 

    let lam = pipe2 (pchar 'λ' >>. many lower) 
         (pchar '.' >>. expr) (fun vs e -> 
               List.foldBack (fun c e -> Lambda (c, e)) vs e) 

    exprR := choice [ 
        lam 
        app 
        var 
        (pchar '(' >>. expr .>> pchar ')') 
        ] 

    run expr e

謝謝！

來源

2011-05-31 Ramon Snir

+12

+1代碼中的希臘字符:) – Benjol 2011-05-31 10:46:32

好的，我終於下載FParsec :-) – 2011-06-01 01:46:42

正如你所指出的，問題是，你的應用程序調用 EXPR 解析器遞歸等有一個無限循環。解析器需要被寫入，以便它總是消耗一些輸入，然後決定要做什麼。

在演算的情況下，棘手的事情是因爲如果你有喜歡的輸入然後x...的第一個字符表明它可以是他們的認識的應用和變量。

可以合併的規則應用和可變這樣的：

let rec varApp = parse { 
    let! first = lower |> apply Variable 
    let! res = 
    choice [ expr |> apply (fun e -> Application(first, e)) 
      parse { return first } ] 
    return res }

該第一解析變量，然後或者解析的另一種表達（在這種情況下，它是一個應用程序），或者它只是返回變量（如果變量後面沒有表達式）。規則其餘的都是相似的：

and lam = 
    pipe2 (pchar 'λ' >>. many lower) 
     (pchar '.' >>. expr) (fun vs e -> 
    List.foldBack (fun c e -> Lambda (c, e)) vs e) 
and brac = pchar '(' >>. expr .>> pchar ')' 
and expr = parse.Delay(fun() -> 
    choice 
    [ lam; varApp; brac ])

我只是用parse.Delay()（這使得它可以創建遞歸值參考）避免了明確的突變的需要。在原則上，它可以寫成：

and expr = parse { 
    return! choice [ lam; varApp; brac ] }

...但由於某些原因，如果你想在計算表達式中使用return! FParsec沒有實現所需要的ReturnFrom成員。

來源

2011-06-01 01:46:22

是的！非常感謝！ – 2011-06-01 05:55:33

感謝您將此引起我的注意。從「分析」構建器對象中省略ReturnFrom成員是一種疏忽。在以前的F＃版本中，ReturnFrom是隱式定義的。（這個定義很簡單。）這應該是在FParsec 0.9中修復的，但我忘了它。我剛剛修復了BitBucket存儲庫中的問題。 – 2011-06-01 16:52:14

個人而言，由於此處描述的性能問題，我不再使用計算表達式語法來構造解析器：http://www.quanttec.com/fparsec/users-guide/where-is-the-monad.html#why-the -monadic-syntax-is-slow – 2011-06-01 16:53:37

FParsec中的遞歸語法

回答

相關問題