3

私はF＃で小さなモナディックパーサーコンビネーターライブラリー（FParsecにいくらか似ています）を書いていましたが、プログラミング言語用の小さなパーサーを実装しようとしました。

私は最初にHaskell（Parsecを使用）でコードを実装しましたが、これは完全にうまく機能しました。中置式のパーサーは、相互再帰的に設計されています。

parseInfixOp :: Parser String -> Parser Expression -> Parser Expression
parseInfixOp operatorParser subParser = ignoreSpaces $ do
                                          x <- ignoreSpaces $ subParser
                                          do
                                            op <- ignoreSpaces $ operatorParser
                                            y  <- parseInfixOp operatorParser subParser
                                            return $ BinaryOp op x y
                                           <|> return x

parseInfix :: [String] -> Parser Expression -> Parser Expression
parseInfix list = parseInfixOp (foldl1 (<|>) $ map string list)

parseExpr :: Parser Expression
parseExpr = parseInfix0

parseInfix0 = parseInfix ["==", "<>", "And", "Or", "Xor", "<", ">", "<=", ">="] parseInfix1
parseInfix1 = parseInfix ["+", "-", "Mod"] parseInfix2
parseInfix2 = parseInfix ["*", "/", "\\"] parseInfix3
parseInfix3 = parseInfix ["^"] parseInfix4
parseInfix4 = parseFactor

parseFactor :: Parser Expression
parseFactor = parseFactor' <|> (betweenChars '(' ')' parseExpr)

parseFactor' :: Parser Expression
parseFactor' = parseString
           <|> parseBool
           <|> parseNumber
           <|> parseVariable
           <|> (try parseFunCall) <|> parseIdentifier

関数の順序は重要ではなく、Haskellは厳密ではない方法で評価しているため、これは問題ありませんが、F＃は厳密に評価しています。

let rec parseExpr = parseInfix0
and parseFactor = (parseFactor') <|> (betweenChars '(' ')' parseExpr)
and parseInfix2 = parseInfix ["^"] parseFactor BinaryOp
and parseInfix1 = parseInfix ["*"; "/"] parseInfix2 BinaryOp
and parseInfix0 = parseInfix ["+"; "-"] parseInfix1 BinaryOp
and parseFunCall = parser {
        let! first = letter
        let! rest = many (letter <|> digit)
        let  funcName = toStr $ first::rest

        do! ignoreSpace
        let! args = betweenChars '(' ')' $ sepBy (parseExpr) ","

        return FunCall(funcName, args)
    }
and parseFactor' =
    parseNumber
<|> parseString
<|> parseBool
<|> parseFunCall
<|> parseIdentifier

F＃は、再帰オブジェクトについて文句を言いStackOverflowException、無限ループのために実行時にをスローするか、「値はそれ自体の定義の一部になる」ためにソースをコンパイルしません。

このエラーを防ぐための最良の方法は何ですか。デバッガーは、lazy代わりに関数またはsを使用するようにアドバイスしますが、ここで何を怠惰にする必要がありますか？

4

3 に答える 3

8

再帰オブジェクトに関する警告は何ですか? テキストを表示します。この場合、無視できる (実際、ある意味で望ましい) 警告が 1 つあります。

再帰的な値が原因でコンパイルできない場合は、単に「構文値」を「構文関数」に変換する必要があります。つまり、むしろ

...
and parseInfix2 = body
...

使用する

...
and parseInfix2 x = (body) x
...

'parseInfix2' の型はいずれにしても同じ関数型ですが... F# (Haskell とは異なり) を明示的に指定する必要がある場合があります (上記のようにeta 変換を行います)。

「lazy」の挿入に関する提案は無視します。パーサーは実際には関数であり、値ではないため、eta 変換は同じ問題をカバーします (これはまったく熱心に評価されません。合格するまですべて「待機」する必要があります)。何かが「実行」される前に解析される文字列)。

StackOverflowExceptions に関しては、スタックのループ スニペットを投稿すると役立つ場合がありますが、入力を消費せずにループに陥る文法の左再帰部分がある場合など、自分の目で確かめることができます。これは、ほとんどの言語のほとんどの解析テクノロジにとって簡単な落とし穴だと思います。

于 2009-07-05T18:14:05.137 に答える
2

η-conversion は必ずしも優れたソリューションではありません。これを行う場合、遅延関数が最大 1 回実行されることを証明するか、解析中にそれを呼び出すために多くのオーバーヘッドを支払う必要があります。

次のようなものが必要です。

let rec p1 = lazy (...)
and p2 = ... p1.Value ..

ワークフロー ビルダーを使用している場合は、これを行うために Delay メンバーを定義することをお勧めします。

type Builder() =
    member this.Delay(f: unit -> Parser<_>) : Parser<_> = 
        let promise = Lazy.Create f
        Return () |> Bind (fun () -> promise.Value)

let parse = new Builder()


let rec p1 =
    parse {
        ...
    }

and p2 =
    parse {
        ...
    }
于 2010-03-03T10:15:46.130 に答える
1

eta の書き換えも怠惰な遅延も確実なことではありません。F# コンパイラは、深い再帰を処理するのに苦労しているようです。私にとってうまくいったのは、再帰を単一のトップレベル関数に折りたたむことでした（再帰的に呼び出される関数を引数として渡すことにより）。このトップレベルは eta スタイルで書かれています。

トップレベル、私は持っています：

let rec myParser s = (parseExpr myParser) s

注 wikipedia には次のように書かれています。それが私のために働いたものです。

于 2010-11-25T10:51:49.807 に答える