11

私は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

ありがとう！

4

1 に答える 1

10

ご指摘のとおり、問題は、アプリケーションのパーサーが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 ] }

...しかし、何らかの理由で、FParsec は、計算式でReturnFrom使用する場合に必要なメンバーを実装していません。return!

于 2011-06-01T01:46:22.703 に答える