ボトムアップ構文解析

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

ボトムアップ構文解析(ボトムアップこうぶんかいせき、: Bottom-up parsing)は、関係の不明なデータを解析するにあたって、最も基本的な単位を最初に識別し、より上位の構造をそこから調べていく戦略である。木構造を葉にあたる部分から根(開始記号)に向けて構築していく。自然言語コンピュータ言語の解析に使われる。計算機科学では、ボトムアップ構文解析を shift-reduce 構文解析とも呼ぶ。

プログラミング言語の場合[編集]

プログラミング言語コンパイラにおけるボトムアップ構文解析は、最初に終端記号を識別し、それらを徐々に組み合わせていって非終端記号を生成する。この過程で人間の読めるソースコードで書かれたプログラムの構文木が構築され、そこからアセンブリ言語擬似コードにコンパイルされる。

言語が異なれば構文解析技法も異なるが、実際に必要とされるより強力な構文解析技法を適用することも珍しくない。

ボトムアップ構文解析器による汎用構文解析器もあり、特定のプログラミング言語向けの構文解析器を生成するのに使われる(パーサジェネレータ)。例えば、yaccなどがある。

構文解析器を使った例[編集]

以下に簡単な例を示す。下記のような簡単な文法があるとする。

S → Ax …①
A → a  …②
A → b  …③

入力が "ax" だった場合、左端導出(トップダウン構文解析)では次のように導出される。

(1)  S ⇒        (開始記号)
(2)  Ax ⇒       (①を適用)
(3)  ax          (②を適用)

開始記号(S)以外の非終端記号が1つしかないため、右端導出でも偶然同じ導出となる。

LL(1)構文解析は開始記号(S)から開始し、「どの生成規則を適用すべきか」を判断する。この場合、生成規則の左辺に S があるものは1つしかない。次に A を置き換えるために A に対応する手続きを実施する(再帰下降構文解析の場合)。この場合、

A → a

が入力とマッチするのでこれが選択され、構文解析が完了する。導出された構文木は次のようになる。

  S
 / \\
A   x
|
a

ボトムアップ構文解析では、これを逆から行い、以下のような順で導出する。

(1) ax ⇒       (入力文字列)
(2) Ax ⇒       (②を適用)
(3) S           (①を適用)

直観的に、トップダウン構文解析は非終端記号が左辺にある生成規則を適用して、その右辺の文字列に展開していく。一方、ボトムアップ構文解析は生成規則の左辺と入力がマッチするものを選び、生成規則を逆向きに適用して最終的に開始記号(非終端記号)へと還元させる。ボトムアップ構文解析では、まず "a" を A に置換して "Ax" とし、次に "Ax" を S に置換する。入力された文字列が全体として S に還元された時点で構文解析は成功して停止する。

トップダウン構文解析のように力づくの方法でも機能する。つまり、パターンマッチする生成規則が見つかるまで次々に探索していく方法である。このような単純な例では示せないが、力任せの方法では不適切な規則の適用もあり、さらに規則を適用として後戻り(バックトラッキング)することになる。これは効率的ではない。そのような後戻りを防ぐために入力を先読みして不適切な規則を適用しないという方法もある。

トップダウン構文解析では、どの生成規則を適用するかという判断をしながら解析を進めていく。ボトムアップ構文解析では、以下のような2つの判断をする。

  1. ある時点で shift アクション(トークンをスタックに移す)をすべきか、reduce アクション(生成規則を適用)をすべきか?
  2. reduce アクションをする場合、どの生成規則を適用すべきか?

ボトムアップ構文解析器の種類[編集]

以下に主なボトムアップ構文解析手法を挙げる。

  • LR法
    • LR(0) - 先読みをしない方法
    • SLR(1) - 単純で1つだけ先読みする方法
    • LALR(1) - 完全なLR(1)ほど強力ではないが、実装が比較的単純な方法。yacc はこれを使用している。
    • LR(1) - 最も強力だが、実装も複雑になる。
    • LR(n) - n は正の整数であり、n 個のトークンを先読みすることを意味する。言語の設計によっては1より多く先読みが必要となる場合があるが、構文解析が複雑化するため、実用的な言語ではあまりそのような設計はされない。
  • 順位構文解析(Precedence parser)

典型的なボトムアップ構文解析は、shift-reduce 構文解析とも呼ばれる。これは、構文解析時に各入力トークンについて、それをスタックに移す(shift-アクション)か、あるいは生成規則を適用して右辺から左辺に置換する(reduce-アクション)ためである(詳細はLR法を参照)。

外部リンク[編集]