3

2 つの再帰分岐を持つパーサーで問題が発生しました。問題を簡単に説明するために、例としてLuca Bolognese によって書かれた記事からラムダ計算の単純な文法を使用します。

<expression> ::= <name> | <function> | <application>  
<name> ::= non­blank character sequence  
<function> ::= \ <name> . <body>  
<body> ::= <expression>  
<application> ::= ( <function expression> <argument expression> )  
<function expression> ::= <expression>  
<argument expression> ::= <expression>

この記事のパーサーは非常に簡潔です。

let ws = " \t\n" 
let specialChars = ".)(\\\n" 

let pWs = spaces 
let pName = manyChars (noneOf (ws + specialChars)) |>> EName 

let pExpr, pExprRef = createParserForwardedToRef<Expression, Unit>() 

let curry2 f a b = f(a,b) 
let pFunction = pchar '\\' >>. pipe2 pName (pchar '.' >>. pExpr) (curry2 Function) 

let pApplication = pchar '(' >>. pipe2 pExpr (pWs >>. pExpr) (curry2 Application)
                            .>> pWs .>> pchar ')'

do pExprRef := pFunction <|> pApplication <|> pName 

let pExpressions = sepBy pExpr spaces1 

let fparseString text = 
    match run pExpressions text with 
    | Success(result, _, _)   -> result 
    | Failure(errorMsg, _, _) -> failwith (sprintf "Failure: %s" errorMsg)

pApplicationそれらは 2 つの で構成されてpExprおり、それがs でもある可能性があるため、私は興味がありpApplicationます。次のベンチマークでは、パーサーがスタック領域を使い果たしています。

let generateString level =
    let rec loop i =
        seq {
                if i < level then
                    yield "("
                    yield! loop level
                    yield " "
                    yield! loop (i+1)
                    yield ")"
                else 
                    yield "(x x)"
        }
    loop 0 |> String.concat ""

let N = 5000
let s = generateString N;; 
let _ = fparseString s;;

パーサーを末尾再帰に書き換えるにはどうすればよいですか?

Lisp に似た言語用のパーサーを作成して実際のベンチマークでテストしようとしたときに、この問題を認識しました。私はTerm、VarBinding相互に再帰的な型であり、上記letと同じ問題を示すパーサーを持っていpApplicationます。末尾再帰ではない問題に関して分析が間違っている場合に備えて、私のパーサーはgithubにあります。

4

1 に答える 1

6

FParsec のビルトイン パーサー コンビネーターは、主にエラー処理の実装方法が原因で、通常、末尾再帰パーサーの実装を許可しません。

これは、ほとんどの再帰降下パーサーの場合と同様に、FParsec パーサーの再帰の深さがスタック サイズによって制限されることを意味します。もちろん、これは 、 などのシーケンスの解析には影響しませんmany。sepByこれらchainlの FParsec コンビネータはすべて、一定のスタック スペースを使用する実装を持っているからです。

.NET のデフォルトのスタック サイズは、通常、人間が生成した入力を適切に指定された形式で FParsec で解析するには十分すぎるサイズです (組み込みのコンビネータでシーケンスを解析すると仮定します)。ただし、深くネストされた構造を持つ機械生成入力 (5000 レベルの深さの S 式など) は、簡単にスタック オーバーフローにつながる可能性があります。

入力のネストの深さが適切な値に制限されていることが事前にわかっている場合は、スタック サイズを適切な値に増やすだけで済みます。これがベンチマーク データに当てはまることを願っています。

それ以外の場合は、文法の再帰要素に対して特別な目的のパーサー関数を実装する必要がある場合があります。FParsecの低レベル APIを使用してこの関数を実装する必要があります。また、ネスティング コンテキストと中間解析結果を追跡するために、スタックではなくヒープを使用するように、この関数を実装する必要があります。

于 2012-02-12T22:33:34.503 に答える