2014年5月21日

ANTLR と Python で構文解析を試してみる

はじめに

Kompira では、ジョブフロー言語の構文解析に、PLY (Python Lex-Yacc) [1] を使用しています。PLY は Yacc/Lex という定番の構文字句解析ツールの Python による実装です。Python から利用できるパーサジェネレータは [2] のように数多くあるのですが、筆者自身が使いなれた Yacc/Lex ベースということと、Python ネイティブな実装ということで、PLY を選んでました。

今回は前から気になっていたパーサジェネレータである ANTLR [3] を使って、簡単な式言語の構文解析を実現してみようかと思います。ANTLR は、LL(*) [4] という強力なトップダウン解析手法にもとづいており、サンフランシスコ大学の Terence Parr 教授が中心となって開発しています。ちなみに Terence Parr 教授は「言語実装パターン―コンパイラ技術によるテキスト処理から言語実装まで 」の著者でもあります。Yacc系の LALR にもとづくツールでは、あいまいな文法を記述すると Shift/Reduce 衝突や Reduce/Reduce 衝突といったエラーメッセージが出ますが、メッセージからはどの構文規則が問題となっているのか直接的にわからないことが多いので、問題解決に苦労するというようなことが良くあります。その点、LL系のツールでは原因となる構文規則を指摘してくれるので、文法のデバッグが楽になるのでは、という期待があります。

トップダウン解析手法によるパーサーですと、何年か前に PEG [5] にもとづくPackrat Parsing が注目を集めていたこともありましたので、そのうち、こちらについても試してみようかと思いますが、今回は ANTLR でいきます。

ANTLR のインストール

まず、我々が普段開発で使用している CentOS 6 のサーバに ANTLR をインストールします。ちなみに、yum コマンドでもインストールできるのですが、バージョンが 2.7.7 と古いので、今回は ANTLR のサイトから必要なパッケージをダウンロードして、手作業でインストールを行います。ただし、最新のバージョン4系はまだ Python に対応していないようですので、今回は1つ前のバージョン
3系を使います。

(0) Java実行環境のインストール

ANTLR は Java で実装されているため、まずはじめに Java の実行環境をインストールします。

(1) パッケージのダウンロード

次に、ANTLR v3 のダウンロードページ (http://www.antlr3.org/download.html) から jar ファイルをダウンロードして適切な場所に配置します。

(2) 起動スクリプトの作成

jar ファイルをラップする起動スクリプトを準備しておくと、あとあと楽なので以下のようなスクリプトを antlr3 というファイル名で作成しておきます。
[antlr3]
実行フラグを立てて、~/binの下に置いておきます。

(3) Python用ランタイムライブラリのインストール

次に、Python用のランタイムライブラリをインストールする必要がありますが、ダウンロードページにあるものはバージョンが少し古く、先ほどダウンロードした jar ファイルと合っていないので、ソースコードからビルドしてインストールします。
以上で、ANTLR の実行環境の準備は完了です。

式言語の定義

以下に示すような BNF で定義される簡単な式言語 explang を ANTLR で構文解析してみることにします。

■ 定義1: explang 文法

 <expression> ::= <assign_expr>
                | <arith_expr>

<assign_expr> ::= IDENT '=' <expression>

 <arith_expr> ::= <term>
                | <arith_expr> '+' <arith_expr>
                | <arith_expr> '-' <arith_expr>

       <term> ::= <factor>
                | <term> '*' <term>
                | <term> '/' <term>

     <factor> ::= IDENT
                | NUMBER
                | '(' <expression> ')'
---

ここで、IDENT は識別子を、NUMBER は非負の整数リテラルを表す終端記号とします。以下のような正規表現で定義されます。

■ 定義2: explang 字句規則

  IDENT = [a-zA-Z_][0-9a-zA-Z_]*
  NUMBER = [0-9]+
---

この式言語では、以下のような式を入力として受け付けることを想定しています。

3 * 2
x = 9 / (3 + 1)
x = y = z = 0
x = (y = 3) + 3

一方、以下のような式はシンタックスエラーとなります。

x + y = 3
(3 x)
- 9

ANTLR 向けに文法を変形する

[定義1: explang 文法] を直接 ANTLR に入力できれば良いのですが、以下に示すように左再帰の規則が含まれているので、そのままでは LL系のパーサージェネレータである ANTLR は受け付けてくれません。(ANTLR v4 では、左再帰の除去を自動的にやってくれるみたいです [6])

<arith_expr> ::= <term>
               | <arith_expr> '+' <arith_expr>
               | <arith_expr> '-' <arith_expr>

そこで、以下のように文法を変形して、左再帰を除去してやります。

<arith_expr> ::= <term>
               | <term> '+' <arith_expr>
               | <term> '-' <arith_expr>

さらに、上の3つの生成規則は、すべて <term> で始まっているため、このままでは、構文解析時にバックトラックが必要になってしまします。そこで、以下のように左端のくくりだしを行います。

<arith_expr> ::= <term> ( | ( '+' | '-' ) <arith_expr> )

これでも良いのですが、ANTLR は拡張BNFが使えるので、0回以上の繰り返しを意味する「*」を用いて以下のようにわかりやすく整理することができます。

<arith_expr> ::= <term> ( ( '+' | '-' ) <term> )*

同様にして、<term> 規則も変形を行います。最終的には以下のように explang 文法を再定義できます。

■ 定義3: ANTLR向け explang 文法

 <expression> ::= <assign_expr>
                | <arith_expr>

<assign_expr> ::= IDENT '=' <expression>

 <arith_expr> ::= <term> ( ( '+' | '-' ) <term> )*

       <term> ::= <factor> ( ( '*' | '/' ) <factor> )*

     <factor> ::= IDENT
                | NUMBER
                | '(' <expression> ')'
---

文法定義ファイルの作成

式言語 explang の文法が定義できたので、これを ANTLR に入力し、Python 実装のパーサーを生成します。以下のように ANTLR に入力する文法定義ファイルを作成します。

[explang.g]
最初の行は文法を宣言している部分で、ここでは、explang という名前を付けています。この名前はファイル名と合わせておく必要があります。

grammar explang;

次の部分はオプションを指定しているところです。デフォルトですと、Java のコードが生成されるので、ここでは、ターゲット言語を Python とするように明示的に指示しています。

options {
    language = Python;
}

次が構文規則を記述している部分です。これは、ANTLR の構文に合わせていますが、内容は [定義3] とほぼ同じです。ただし、ANTLR に開始規則を教えるために、以下のような規則を追加しています。また、空の入力も許すようにしています。

start       : ( expression )? EOF ;

最後は字句規則を記述している部分です。こちらも [定義3] の字句規則の内容を ANTLR の構文に沿って記述しています。NODIGIT と DIGIT の定義は IDENT と NUMBER の定義の中で使われるものなので、トークンとして認識されないように fragment 指定をしています。さらに、空白を読み飛ばすために、以下の定義も追加しています。

WHITESPACE : ( '\t' | ' ' | '\r' | '\n'| '\u000C' )+    { $channel = HIDDEN; } ;

アクションに $channel = HIDDEN; と記述することで、パーサーからはそのトークンが見えなくなり、結果として WHITESPACE がスキップされます。

パーサーの生成と動作確認

パーサーを生成するには、以下のようにコマンドライン引数に文法定義したファイル (explang.g) を指定して、ANTLR を起動してやれば OK です。
うまくいけば、以下の3つのファイルが生成されます。

  • explang.tokens : トークン定義のファイル
  • explangLexer.py : 字句解析ルーチン
  • explangParser.py : 構文解析ルーチン

生成された explangParser.py は簡単な対話型の処理を受け付ける main プログラムが含まれています。そこで、以下のようにオプションを付けて Python から起動すると、プロンプトが表示され、式が入力できるようになります。
そこで、以下のように explang 文法の正しい式を入力すると、何も出力されずに次のプロンプトが表示されます。
間違った式を入力すると、エラーメッセージが表示されます。
終了するには、Ctrl+D を入力します。

おわりに

ということで、ANTLR v3 を使って簡単な式言語のパーサーを作ってみました。今回は、ただ構文解析するだけでしたが、次回は実際に式を評価して結果を表示する簡単なインタプリタを実装していこうかと思います。

参考資料

[1] http://www.dabeaz.com/ply/
[2] https://wiki.python.org/moin/LanguageParsing
[3] http://www.antlr.org/
[4] Terence Parr, Kathleen S. Fisher, "LL(*): The Foundation of the ANTLR Parser Generator", PLDI '11
[5] http://ja.wikipedia.org/wiki/Parsing_Expression_Grammar
[6] https://theantlrguy.atlassian.net/wiki/display/ANTLR4/Left-recursive+rules