4

Happy ユーザーマニュアルのセクション 2.2では、右再帰は「非効率的」であるため、右再帰ではなく左再帰を使用するようにアドバイスしています。基本的に彼らは、アイテムの長いシーケンスを解析しようとすると、右再帰は解析スタックをオーバーフローさせるのに対し、左再帰は定数スタックを使用すると言っています。与えられた標準的な例は

items : item            { $1 : [] }
      | items "," item  { $3 : $1 }

残念ながら、これはアイテムのリストが逆向きに出てくることを意味します。

これで、最後に適用するのは簡単です (ただし、パーサーが定義されている場所ではなく、パーサーが呼び出されるreverseたびにこれを行う必要があるのは非常に面倒です)。しかし、アイテムのリストが大きい場合、Haskell スタックもオーバーフローするのでしょうか? いいえ？reverse

基本的に、任意のサイズのファイルを解析し、結果を正しい順序で取得できるようにするにはどうすればよいですか?

4

1 に答える 1

4

毎回全体itemsをd にすることだけが必要な場合は、定義できますreverse

items  : items_           {reverse $1}

items_ : item             { $1 : [] }
       | items_ "," item  { $3 : $1 }

reverseスタックをオーバーフローしません。これを自分自身に納得させる必要がある場合は、評価してみてくださいlength $ reverse [1..10000000]

于 2015-11-01T18:02:27.570 に答える