ANTLR による構文解析の始め方

Java

f:id:Naotsugu:20200301165547p:plain


ANTLR とは

ANTLR (ANother Tool for Language Recognition) は構文解析器を生成するパーサジェネレータで、yacc や JavaCC などと同じ類いのものです。 BNF のような文法定義から、ソースコードなどを処理するコードを生成します。

プログラム言語の入力部であったり、DSL や コード解析、設定ファイルの読み込みなどの構造を持った入力テキストの処理を簡単に実現することができます。

例えば、Hibernate の HQL(Hibernate Query Language) では ANTLR による構文解析が使われています。

ここでは、ANTLR 4 の使い方について簡単に見ていきます。


ANTLR の導入

ここでは、Java と Gradle を使って進めていきます。

Gradle の init タスクなどでプロジェクトを作成したら、antlr プラグインを追加します。

plugins {
    id 'java'
    id 'application'
    id 'antlr'
}

repositories {
    jcenter()
}

dependencies {
    antlr "org.antlr:antlr4:4.8-1"
}

application {
    mainClassName = 'com.mammb.er.App'
}

generateGrammarSource {
    outputDirectory = file("src/main/java")
}

dependencies に antlr として使用する antlr のバージョンを指定します(ここでは最新の 4.8-1 を指定しました)。

generateGrammarSource としてパーサの出力先を指定しています。指定しない場合は、build/generated-src に生成されます。


antlr プラグインでは src/main/antlr に配備した文法ファイルを入力にパーサを生成します。

文法ファイルは以下で多くの言語向けのものが公開されています。

github.com

ここでは、SQLite 向けの文法ファイル SQLite.g4 をサンプルとして使用します。

このファイルをダウンロードして、src/main/antlr/com/mammb/er/parser/SQLite.g4 として保存します。

このファイルにより生成したソースはパッケージ宣言が付与されないので、grammar の後に @header で出力するパッケージを追加しておきます。

grammar SQLite;

@header {
package com.mammb.er.parser;
}
...

または、build.gradle にて以下のように指定することもできます。

generateGrammarSource {
    arguments += ['-package', 'com.mammb.diagram.parser']
    // ...
}

これで準備は整いました。


ANTLR の実行

antlr プラグインを導入することで generateGrammarSource タスクが追加されます。 このタスクを実行しても良いですし、compileJava タスクの依存先になっているので、単に build すれば ANTLR によりパーサが生成されます。

実行してみましょう。

$ ./gradlew generateGrammarSource

以下のようなファイルが生成されます。

f:id:Naotsugu:20200301154714p:plain

SQLiteLexer が字句解析器で、入力ファイルの内容を字句単位に分割する前処理を行います。

SQLiteParser が構文解析器で、前処理された字句から抽象構文木を作成します。

作成された抽象構文木は、SQLiteListener とその実装である SQLiteBaseListener にて構文木の内容を処理することができます。


ANTLR による構文解析

構文解析器が生成できたので、それを利用してみましょう。

操作の流れは以下のようになります。

f:id:Naotsugu:20200301150144p:plain


ここではなるべく簡単な例を見たいので、以下のような create table 文を扱うことにします。

create table employee (id bigint not null, name varchar(50), primary key (id));
create table department_employees (department_id bigint not null, employees_id bigint not null);
create table employee (id bigint not null, name varchar(50), primary key (id));


入力文字列を SQLiteLexer に与え、トークンストリームを得ます。

CharStream cs = CharStreams.fromString(
    "create table employee (id bigint not null, name varchar(50), primary key (id));" +
    "create table department_employees (department_id bigint not null, employees_id bigint not null);" +
    "create table employee (id bigint not null, name varchar(50), primary key (id));"
);
SQLiteLexer lexer = new SQLiteLexer(cs);
CommonTokenStream tokens = new CommonTokenStream(lexer);


トークンストリームから SQLiteParser を生成して ParseTree を得ます。

SQLiteParser parser = new SQLiteParser(tokens);
ParseTree tree = parser.parse();


ParseTree を辿る中で行う処理を SQLiteBaseListener を継承したクラスで定義します。

static class Listener extends SQLiteBaseListener {

    @Override
    public void enterCreate_table_stmt(SQLiteParser.Create_table_stmtContext ctx) {

        System.out.println(ctx.table_name().getText());

        for (SQLiteParser.Column_defContext cd : ctx.column_def()) {
            System.out.println(
                "  " + cd.column_name().getText() + " " + cd.type_name().getText());
        }
    }
}


ParseTreeWalker に作成した Listener のインスタンスと構文木を渡します。

ParseTreeWalker.DEFAULT.walk(new Listener(), tree);


まとめると以下のようになります。

public class App {

    public static void main(String[] args) {

        CharStream cs = CharStreams.fromString(
                "create table employee (id bigint not null, name varchar(50), primary key (id));" +
                "create table department_employees (department_id bigint not null, employees_id bigint not null);" +
                "create table employee (id bigint not null, name varchar(50), primary key (id));"
        );

        SQLiteLexer lexer = new SQLiteLexer(cs);
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        SQLiteParser parser = new SQLiteParser(tokens);
        ParseTree tree = parser.parse();
        ParseTreeWalker.DEFAULT.walk(new Listener(), tree);
    }

    static class Listener extends SQLiteBaseListener {
        @Override
        public void enterCreate_table_stmt(SQLiteParser.Create_table_stmtContext ctx) {
            System.out.println(ctx.table_name().getText());
            for (SQLiteParser.Column_defContext cd : ctx.column_def()) {
                System.out.println("  " + cd.column_name().getText() + " " + cd.type_name().getText());
            }
        }
    }
}

実行すると、以下のような出力がを得ることができます。

employee
  id bigint
  name varchar(50)
department_employees
  department_id bigint
  employees_id bigint
employee
  id bigint
  name varchar(50)

例えばこれを使い、DDL からテーブル定義書などを生成したりといったことにも活用できますね。


ANTLR の文法ファイルと生成ファイルの関係

SQLite.g4 の冒頭部分を見てみましょう。

parse
 : ( sql_stmt_list | error )* EOF
 ;

parse は、sql_stmt_list か error で構成される という定義になっています。

これに対応するのが SQLiteParser の内部クラスとして以下のように出力されます。

public static class ParseContext extends ParserRuleContext {
  public TerminalNode EOF() { return getToken(SQLiteParser.EOF, 0); }
  public List<Sql_stmt_listContext> sql_stmt_list() {
    return getRuleContexts(Sql_stmt_listContext.class);
  }
  public List<ErrorContext> error() {
    return getRuleContexts(ErrorContext.class);
  }
 // ...
}

先の例を再掲すると、

SQLiteParser parser = new SQLiteParser(tokens);
ParseTree tree = parser.parse();

parser.parse() は、ここで定義されたものを呼び出していることになります。


sql_stmt_list の定義は以下のようになっており、sql_stmt が繰り返される という定義になっています。

sql_stmt_list
 : ';'* sql_stmt ( ';'+ sql_stmt )* ';'*
 ;

これに対応する Sql_stmt_listContext クラスが以下のように定義されます。

public static class Sql_stmt_listContext extends ParserRuleContext {
  public List<Sql_stmtContext> sql_stmt() {
    return getRuleContexts(Sql_stmtContext.class);
  }
  // ...
}


sql_stmt は(大幅に省略しますが) 各 SQLの文法となり、

sql_stmt
 : ( K_EXPLAIN ( K_QUERY K_PLAN )? )? ( alter_table_stmt
                                      | create_index_stmt
                                      | create_table_stmt
                                      // ...
                                      | vacuum_stmt )
 ;

create_table_stmt は以下のような文法となっています。

create_table_stmt
 : K_CREATE ( K_TEMP | K_TEMPORARY )? K_TABLE ( K_IF K_NOT K_EXISTS )?
   ( database_name '.' )? table_name
   ( '(' column_def ( ',' column_def )*? ( ',' table_constraint )* ')' ( K_WITHOUT IDENTIFIER )?
   | K_AS select_stmt
   )
 ;

これに対応する Create_table_stmtContext クラスが(こちらも大幅に省略しますが)以下のように定義されます。

public static class Create_table_stmtContext extends ParserRuleContext {
  public Table_nameContext table_name() {
    return getRuleContext(Table_nameContext.class,0);
  }
  public List<Column_defContext> column_def() {
    return getRuleContexts(Column_defContext.class);
  }
  // ...
}

Listener の定義を再掲します。

static class Listener extends SQLiteBaseListener {

    @Override
    public void enterCreate_table_stmt(SQLiteParser.Create_table_stmtContext ctx) {
        System.out.println(ctx.table_name().getText());
        // ...
    }
}

create_table_stmt として文法定義されたものが Create_table_stmtContext として得られるので、文法ファイル上の table_name に該当する public Table_nameContext table_name() にてテーブル名称を取得できる という流れになります。


まとめ

ここでは ANTLR の導入として、簡単な ANTLR の使い方について見てきました。

次回はもう少し詳細な活用例について見ていきます。




The Definitive ANTLR 4 Reference

The Definitive ANTLR 4 Reference

  • 作者:Parr, Terence
  • 発売日: 2013/01/25
  • メディア: ペーパーバック

言語実装パターン ―コンパイラ技術によるテキスト処理から言語実装まで

言語実装パターン ―コンパイラ技術によるテキスト処理から言語実装まで

  • 作者:Terence Parr
  • 発売日: 2011/12/24
  • メディア: 大型本

Go言語でつくるインタプリタ

Go言語でつくるインタプリタ

  • 作者:Thorsten Ball
  • 発売日: 2018/06/16
  • メディア: 単行本（ソフトカバー）