解析：F＃で遅延初期化と相互再帰的なモナド

Question

私はちょっとモナドなパーサーコンビネータライブラリを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は非厳密な方法で評価されているので、これはOKですが、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を投げるか「値は、独自のdefinionの一部となる」ので、それもソースをコンパイルしません。

このエラーを防ぐ最も良い方法は何ですか。デバッガは私に代わりに関数またはlazyを使用するようにアドバイスしますが、ここで何を怠けばよいでしょうか？

Answer 1

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

再帰的な値が原因でコンパイルされない場合は、「構文値」を「構文関数」に変換するだけで済みます。それは「parseInfix2」の種類が同じ関数型のいずれかの方法であるにも関わらず...（Haskellのとは違って）F＃は、時にはあなたが明示的にする必要がありますむしろ

... 
and parseInfix2 = body 
... 

使用

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

のではなく、 （上記のようにeta-conversionを実行してください）。

私は 'lazy'を挿入することについての提案を無視したいが、パーサーは実際には値ではなく関数なので、 'が実行される前に解析される文字列を渡すまで）。

StackOverflowExceptionsに関しては、スタックのループスニペットを投稿すると役立つかもしれませんが、あなた自身のために見ることができます。文法の左回帰部分があり、入力を消費せず、ループに巻き込まれた場合です。私はそれがほとんどの言語でほとんどの解析技術の簡単な落とし穴だと思う。

Answer 2

η変換は必ずしも素晴らしい解決策ではありません。これを行うと、遅延関数がたかだか1回しか実行されないことや、解析中にそれを呼び出すためのオーバーヘッドが大きくなることを証明する必要があります。

あなたはこのような何かしたい：

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 { 
     ... 
    } 

Answer 3

どちらETA：ワークフロービルダを使用している場合、

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

良い方法は、あなたのためにこれを行うには、遅延部材を定義することです怠惰な遅延も確実なものです。 F＃コンパイラは深い再帰を扱うのに苦労しているようです。私のために働いたのは、（関数を引数として再帰的に呼び出すことによって）単一のトップレベル関数に再帰を崩壊させることでした。このトップレベルはetaスタイルで書かれています。

トップレベル、私が持っている：

let rec myParser s = (parseExpr myParser) s 

注ウィキペディアは言う：「OCamlのような厳格な言語では、我々はクロージャの使用を強制することにより、無限再帰の問題を回避することができます。」。それが私のために働いたものです。