4

私はHaskellでのプログラミングを読んでいます.8章で、著者はパーサーを書く例を挙げています。完全なソースはここにあります: http://www.cs.nott.ac.uk/~gmh/Parsing.lhs次 の部分が理解できません: のmany 0 個以上のアプリケーションを許可しますが、少なくとも 1 つの成功したアプリケーションが必要です:pmany1

many        ::    Parser a → Parser [a ]
many p      =     many1 p +++ return [ ]
many1       ::    Parser a → Parser [a ]
many1 p     = do v ← p
                 vs ← many p
                 return (v : vs)

再帰呼び出しがどのように発生するか

vs <- many p

vsは の結果値ですがmany p、多くの p が呼び出され、その定義にはmany1 pすべてdo 記法があり、再び結果値 があります。そして、再帰呼び出しはいつ戻るのでしょうか? 次のスニペットが返されるのはなぜですか?many1vvs[("123","abc")]

> parse (many digit) "123abc"
[("123", "abc")]
4

3 に答える 3

6

再帰v <- pは行で停止します。パーサーのモナド動作は、もはや解析できない[]場合、計算の最後にa を伝搬するだけです。p

p >>= f =  P (\inp -> case parse p inp of
                        []        -> [] -- this line here does not call f
                        [(v,out)] -> parse (f v) out)

2 番目の関数は do 表記で記述されています。これは、次の構文に適しています。

many1 p = p >>= (\v -> many p >>= (\vs -> return (v : vs)))

p を解析して空のリストが生成された場合[]、関数\v -> many p >>= (\vs -> return (v : vs))は呼び出されず、再帰が停止します。

于 2011-05-21T10:07:01.543 に答える
2

最後の質問:

> parse (many digit) "123abc"
[("123", "abc")]

少なくとも 1 つの結果が回答リストに返されたため、解析が成功したことを意味します。Hutton パーサーは常にリストを返します。空のリストは解析の失敗を意味します。

結果 ("123", "abc") は、解析が 3 桁の "123" を検出し、数字ではない 'a' で停止したことを意味します。したがって、「残りの入力」は「abc」です。

many「1つ以上」ではなく、「できるだけ多く」を意味することに注意してください。「1 つ以上」の場合は、代わりに次の結果が得られます。

[("1", "23abc"), ("12", "3abc"), ("123", "abc")]

この動作は、自然言語の解析では必要になる場合がありますが、決定論的な解析にはあまり適していません。

于 2011-05-21T10:34:36.337 に答える
1

doこれを骨の折れる部分まで取り除いて、単純に命令型のコードとして読まれた場合に -blocks が誤解される理由を完全に明確にしましょう。次のスニペットを検討してください。

doStuff :: Maybe Int
doStuff = do
    a <- Nothing
    doStuff

永遠に再帰するように見えますがdoStuff、結局のところ、で終わる一連のことを行うように定義されていますdoStuff。しかし、do-block 内の一連の行は、単に順番に実行される一連の操作ではありません。-blockのポイントにいる場合do、残りのブロックの処理方法は の定義によって決まり>>=ます。私の例では、2 番目の引数>>=は、最初の引数が でない場合にのみ使用されNothingます。したがって、再帰は決して起こりません。

同様のことが多くの異なるモナドで発生する可能性があります。あなたの例はもう少し複雑です。何かを解析する方法がこれ以上ない場合、の後のもの>>=は無視されます。

于 2011-05-29T21:55:11.120 に答える