トップダウン構文解析 - mrsekut-p

トップダウン構文解析

top-down parser

下降型構文解析、下向き構文解析ともいう

解析木の根から葉へと導出を繰り返す

まず大きな要素から開始して徐々に細部に分解していく

根から最左導出と同じ順番で解析木を生成していく

生成規則をそのままプログラムと見るのでHaskellやOCamlのような関数型の言語でParserを書くととても書きやすいし、簡潔になるmrsekut.icon

問題点

後戻りが必要になることがある

構文規則を見たときに適用すべき規則が一意に定まらない

後戻りがある状態での解決策

バックトラッキングアルゴリズム

後戻り自体を消す解決策

左括り出し

先読みをする

左再帰の除去を使って解決する

トップダウン構文解析の例

再帰下降構文解析

Pratt構文解析

末尾再帰構文解析

パックラット構文解析