5

FParsec を使用して標準の単純型 (ラムダ計算の意味で) を解析しようとしていますが、特に再帰的な定義に関して、Lex/Yacc スタイルから FParsec で使用されるスタイルに移行するのに苦労しています。

私が解析しようとしている型の例は次のとおりです。

  • o
  • o -> o
  • (o -> o -> o) -> o

そして、ここに私の試みがあります：


    type SType =
      | Atom
      | Arrow of SType * SType

    let ws = spaces
    let stype, styperef = createParserForwardedToRef()

    let atom = pchar 'o' .>> ws |>> (fun _ -> Atom)

    let arrow = pipe2 (stype .>> (pstring "->" .>> ws)) 
                      stype
                      (fun t1 t2 -> Arrow (t1,t2))

    let arr = parse {
                let! t1 = stype
                do!  ws
                let! _  = pstring "->"
                let! t2 = stype
                do!  ws
                return Arrow (t1,t2)
              }

    styperef := choice [ pchar '(' >>. stype .>> pchar ')';
                         arr;
                         atom ]

    let _ = run stype "o -> o"`

これをインタラクティブにロードすると、最後の行でスタック オーバーフローが発生します (皮肉なことに、最近では検索が非常に困難です)。再帰参照があることを考えると、その理由は想像できますが、1 つのトークンの先読みでは、stype. したがって、それは を選択しているに違いないと思いarrますstype。しかし、このループを防ぐにはどうすればよいでしょうか?

ライブラリの慣用的な使用に関するコメントと、試みた解決策の修正に興味があります。

4

2 に答える 2

4

FParsec を使用する場合、左再帰の代わりにシーケンス コンビネータを使用してシーケンスを解析する必要があります。あなたの場合、たとえばsepBy1コンビネータを使用できます：

open FParsec

type SType =
     | Atom
     | Arrow of SType * SType

let ws = spaces : Parser<unit, unit>
let str_ws s = pstring s >>. ws

let stype, stypeRef = createParserForwardedToRef()

let atom = str_ws "o" >>% Atom

let elem = atom <|> between (str_ws "(") (str_ws ")") stype

do stypeRef:= sepBy1 elem (str_ws "->") 
              |>> List.reduceBack (fun t1 t2 -> Arrow(t1, t2))

let _ = run stype "o -> o"
于 2011-07-20T21:04:51.813 に答える
0

これは実行されますが、おそらく一緒にハッキングされすぎています。コンパイラ エラーを回避するためのtype Parser...ものは、FParsec ドキュメントからのものです。

type SType = 
    | Atom 
    | Arrow of SType * SType

type UserState = unit
type Parser<'t> = Parser<'t, UserState>


let ws = spaces

let atom : Parser<_> = pchar 'o' .>> ws |>> (fun _ -> Atom)

let rec term =
    parse {
        // Force something to come before another term.  Either
        // an atom, or a term in parens.
        let! first = choice [atom;
                             (pstring "(" .>> ws) >>. term .>> 
                              (pstring ")" .>> ws)]

        // Check if this is an arrow.  If not, just return first.
        let! res = choice [((pstring "->") .>> ws) >>. term |>> (fun x ->
                               Arrow (first, x));
                           preturn first]
        return res
        }
于 2011-07-20T17:13:00.490 に答える