再帰下降パーサーの実行時間についてもっと知りたいです。また、再帰下降パーサーが使用するスタックスペース（およびランタイムとスタックスペースの間のトレードオフ）にも興味があります。 いくつかの良い情報源は何ですか？
ウィキペディアの記事を読み、Webを検索しましたが、詳細な情報は見つかりませんでした。
1 に答える
2
再帰下降構文解析のランタイムはかなり高速です。一般に、マシンのCALL/RET命令を使用して再帰を実装します。後戻りしたり先を見越したりしない手書きのバージョンは、通常、非常に高速である必要があります。しかし、重要なのはトークンストリームを解析する時間ではありません。重要なのは、トークンを構築するための文字の処理、および/またはセマンティックチェック/コード生成に費やされる時間です。なんで心配なの？
スタックスペースは、基本的に、プログラムの解析に必要な最も深いネストによって決定されます。パーサーが式で（...）を受け入れ、誰かが50,000個のネストされた括弧を使用して式を作成した場合、再帰下降構文解析は50,000回再帰します。パーサーの再帰をどれだけ深くできるかについて任意のルールを作成することで、この動作を防ぐことができます（ほとんどの人がそうします）。100レベルで、驚くほど複雑なプログラムを処理できることがわかりました。
于 2011-10-11T19:13:44.400 に答える