top page > computer > haskell > web_lecture > for_programmer > parser_prelude.html
更新日:
文責: 重城良国

パーサ: はじめに

再帰下降構文解析

構文解析の複数の候補をリストとして返す再帰的な構文解析器を作る。バックトラックするタイプの再帰下降構文解析器だ。

Wikipedia: 再帰下降構文解析

実行効率の問題

単純な実装とする。実行効率は非常に悪くO(2^n)となる。構文解析の様々なアルゴリズムが研究されている。解析できる範囲を制限することで線形時間での解析が可能だ。

練習なので

実用性は気にせずにO(2^n)の実装とする。興味のある人は構文解析やオートマトンのディープな世界をのぞくと良い。お勧めの本は

Amazon: 川添愛「白と黒のとびら」

だ。

「構文: リスト内包表記(2)」へもどる 「パーサ: 基本的な関数」へ

正当なCSSです! HTML5 Powered with CSS3 / styling, and Semantics