CFG構文解析

構文解析とは

コンピュータプログラムのコンパイラやインタプリタには、一定の規則(形式文法)に従って書かれたソースプログラムを解釈し、 そこから構文木と呼ばれる木構造を抽出する構文解析器(パーサ)と呼ばれるプログラムが必ず含まれています。

パーサの構成方法は、プログラムを定義する形式文法の種類(文法クラス)に応じて様々なものが知られており、 2010年代に入ってからも、新しい構文解析手法が提案されています。 とりわけ、文脈自由文法(CFG)と呼ばれる文法クラスは、C++やJavaをはじめとして一般的なプログラミング言語の大多数を 定義するに足る表現力を持つとされており、CFGに基づく構文解析法が数多く見出されてきました。

CFG構文解析の2つの流派

CFG構文解析の手法は、大きく分けてトップダウン法とボトムアップ法に分類されます。 いずれも最終的にソースプログラム(記号列)から文法構造を表現した木構造(抽象構文木、AST)を生成する点では共通していますが、 トップダウン法が木構造を根から組み立てていくのに対して、ボトムアップ法が葉から組み立てていくという大きな違いがあります。 根を上に、葉を下にしてASTを表現したとき、トップダウン法は字義通り上から下へ、反対にボトムアップ法は下から上へ 構築が行われます。

トップダウン法とボトムアップ法にはそれぞれ長所と短所があり、 また各手法を実装したひとつひとつの構文解析プログラムにも、用途によって得手不得手が存在します。 わたしたちは、トップダウン法がもたらす様々な利点に着目し、 この手法に新機軸を取り入れた構文解析アルゴリズムとその実装を提案することを通じて 汎用的な構文解析ソフトウェアの応用を広げることを目標として研究を進めています。

CFG構文解析の動作

中置記法(二項演算子が項の間に置かれる数式の表現方法)に基づく簡単な数式の文法を用いて、 CFG構文解析の基本的な動作を説明します。

CFG構文解析が対象とする形式文法は、各記号から記号列への変換規則(生成規則)の集合として表現されますが、 文法をテキストファイルとして各種プログラムに読み込ませるときは、 通常EBNF(拡張バッカス＝ナウア記法)と呼ばれる形式に従って記述します。 たとえば中置記法を解釈する文法は次のように書くことができます。

1. E -> E + E
2. E -> E - E
3. E -> E * E
4. E -> E / E
5. E -> ( E )
6. E -> 0..9

文法中のEは記号(symbol)と呼ばれますが、記号は必ずしも123やABCのような文字列に対応するとは限らず、 たとえば上の例の場合、Eは1+2のような式を表す仮想的な記号として扱われることもあります。 直接123やABCのような文字列を表す記号を終端記号(terminal)、 1+2のような抽象的な意味を持つ記号を非終端記号(nonterminal)と呼びます。

例中の各行はひとつの生成規則に対応しています。 例えば1行目のE -> E + Eは、左辺の記号Eから、右辺の記号列E + Eが「生成」されることを表します。 左辺から右辺に矢印が伸びていますが、 これは実際のアルゴリズムにおいて必ずしも左辺の記号から右辺の記号列が生み出されるような因果的な関係が存在することを示すものではなく、 あくまで慣例です。

トップダウン構文解析器は、ある入力記号列と開始記号が与えられたとき、 開始記号に文法中の生成規則を適用して左辺の記号を右辺の記号列で置き換えることを繰り返し、 最終的に入力記号列と一致する記号列を得ることを目指します。

一方でボトムアップ構文解析器は、ある入力記号列と開始記号が与えられたとき、 入力記号列に文法中の生成規則を「逆向きに」適用して右辺の記号列を左辺の記号で置き換えることを繰り返し、 最終的に開始記号を得ることを目指します。

トップダウン構文解析において入力記号列と一致する記号列が得られたとき、 もしくは、ボトムアップ構文解析において開始記号が得られたとき、 与えられた記号列は文法に従っていると見なされ、構文解析は終了します。

トップダウン法の動作

入力記号列

1 + 2 * 3

を検証するトップダウン構文解析器の動作概略について、順を追って説明します。

トップダウン構文解析は開始記号から始めます。

E

記号Eに生成規則1を適用することで、左辺の記号Eが右辺の記号列E+Eに置き換わります。

  E
  |
+-+-+
|   |
V   V
E + E

さらに右側の記号Eに生成規則3を適用することで、入力記号列と一致する記号列を得ます。

    E
    |
  +-+-+    生成規則1を適用
  |   |
  V   V
  E + E
      |
    +-+-+  生成規則3を適用
    |   |
    V   V
E + E * E
|   |   |
V   V   V  生成規則6を適用
1 + 2 * 3

図のように生成規則の適用によって記号が記号列に展開されていく様子を木構造として記録することで、 入力記号列の「意味」に対応するASTを自動的に得ることができます。 中置記法のパーサでは、ASTと算術木が直接的に対応します。1

ボトムアップ法の動作

ボトムアップ構文解析器は、トップダウン法とは逆に入力記号列から検証を始めます。 動作の詳細については省略します。最終的に算術木に対応するASTが得られる点は同じです。

1 + 2 * 3
|   |   |
V   V   V  生成規則6をそれぞれ適用
E + E * E
    |   |
    +-+-+  生成規則3を適用
      |
      V
  E + E
  |   |
  +-+-+    生成規則1を適用
    |
    V
    E

トップダウン・ボトムアップ構文解析器の実装

トップダウン法もしくはボトムアップ法に基づく構文解析器を実際にコンパイラ等に実装するためには、 構文解析器の動作を決定性のプログラムとして記述しなければなりません。

構文解析の各段階における記号列を人間が見て、 どの位置の部分記号列にどの生成規則を適用すれば「正しい」結果が得られるか判断することは容易ですが、 これをアルゴリズムとして記述することは容易ではありません。

2018年現在、CFGに属するすべての文法を理解できて、かつ線形時間で動作するアルゴリズムは存在しません2。

あまり正確な表現ではありませんが、 これまでに提案された数多くのCFG構文解析手法(CFG構文解析アルゴリズム)の違いは、 主に「どの段階でどの部分記号列にどの生成規則を適用するか」を判断する部分にあると言えるでしょう。

LR(1)構文解析法

2018年現在、最も広く普及しているボトムアップ構文解析法はLR(1)の亜種です。 主要なプログラミング言語処理系の多くで、LR(1)の亜種に基づくパーサジェネレータが使われています。

LR(1)構文解析器の特徴は次の通りです。

  • 入力記号列を左(先頭)から右(末尾)へ、記号ひとつ分ずつ読み込む。
  • 現在の読み込み位置で終わる部分記号列(読み込み位置直前の部分記号列)に生成規則を適用する。
  • 適用する生成規則は、現在の読み込み位置にある記号で表引きを行って決定する。

LR(1)構文解析器の動作について、中置記法パーサの例を用いて説明します。

LR(1)構文解析器は入力記号列を読み込みながら、適用可能な生成規則の候補を絞り込みます。 ある記号を読み込んだ時点で、現在位置直前の部分記号列に適用可能な生成規則がひとつしかなければそれをただちに適用します。3

LL(k)構文解析法

LL(k)はトップダウン構文解析法の中で最も広く使われている手法のひとつです。 主要な軽量スクリプト言語の多くは、LL(k)構文解析器で解釈できることをひとつの指標として設計されていると言われています4。

LL(k)構文解析器の特徴は次の通りです。

  • 入力記号列を左(先頭)から右(末尾)へ、記号ひとつ分ずつ読み込む。
  • 適用する生成規則は、現在の読み込み位置からk個の記号で表引きを行って決定する。

LL(*)構文解析法

LL(*)はLL(k)の拡張として、Parrらによって2011年に提案された構文解析法です。 ANTLR(バージョン3)はLL(*)の著名な実装として知られています。

LL(*)構文解析器の特徴は次の通りです。

  • 入力記号列を左(先頭)から右(末尾)へ、記号ひとつ分ずつ読み込む。
  • 適用する生成規則は、現在の読み込み位置から任意個の記号をDFA(有限状態機械)に入力して決定する。

汎用データ処理へのCFG構文解析器の応用

わたしたちは、LL(*)構文解析器をコンピュータプログラムの処理ではなく 汎用的な文字列データ処理に応用することで、従来の手法とは一線を画した拡張性、実用性ならびに柔軟性の実現を目指しています。

  1. ただし実際の構文解析では自動的に構成されるASTでは不十分であるため、多くの実用的な構文解析ソフトウェアでは、構文解析中のAST生成をコントロールする機能が備わっています。 ↩

  2. CFGに属するすべての文法を理解できて、かつ実用上は線形時間で動作する構文解析器は存在しますが、これらは線形時間アルゴリズムと多項式・指数時間アルゴリズムを動的に切り替えています ↩

  3. あらゆる入力についてこのように生成規則を決められる場合、その文法はLR(0)文法クラスに属します。LR(0)の0は、先読みに0個の記号が用いられることを示します ↩

  4. ただし実際にはPythonなど、純粋なLL(k)ではないことも往々にしてあります ↩