ANTLRで数式を逆ポーランド記法に変換してみた

13509 ワード
antlr antlr4 コンパイラ コンパイラ テキストリンク

はじめに

この記事はFujitsu Advent Calendar 2020 15日目の記事です。

本記事では、ANTLRというパーサジェネレータを使った言語解析の例として、数式を逆ポーランド記法に変換するプログラムを作成します。

逆ポーランド記法は、数式を後置記法で記述したものです。a+bのような演算子が被演算子の間に置かれる普通の数式は中置記法と呼ばれます。後置記法では、演算子は被演算子の後に置かれます。

[逆ポーランド記法への変換の例]
 a+b → ab+

[もう少し複雑な例]
 (a+b)*(c-d) → ab+cd-*

#実は逆ポーランド記法への変換は、スタックを使って実装する方が簡単なのですが、この記事はANTLRを使うことが目的なので、あえて面倒なことをしています。

ANTLRとは

ANTLRは、プログラミング言語のような、ある規則に基づいて記述された言語を構文解析するプログラムを自動生成するソフトウェアです。
以下の言語で構文解析プログラムを生成できます。

  • Java
  • Python
  • C#
  • JavaScript
  • Go
  • Swift
  • C++

本記事では、Java言語で構文解析プログラムを作成します。

準備

以下のリンク先のInstallationに従い、ANTLRを導入して使える状態にします。
https://github.com/antlr/antlr4/blob/master/doc/getting-started.md

数式の言語としての定義

ANTLRでは、言語の定義をEBNFに似た言語で記述します。数式を以下のように定義します。

Poland.g4
grammar Poland;

exp : SYM | NUM | exp PLUS exp | exp MINUS exp | exp MUL exp | exp DIV exp | '(' exp ')' ;
SYM : [a-zA-Z]+ ;
NUM : [0-9]+ ;
PLUS : '+' ;
MINUS : '-' ;
MUL : '*' ;
DIV : '/' ;
WS : [\t\r\n]+ -> skip;

上記の言語定義のファイルを入力にして、ANTLRを実行します。

c:\antlr>antlr4 Poland.g4

以下のファイル群が生成されます。

  • Poland.interp
  • Poland.tokens
  • PolandBaseListener.java
  • PolandLexer.interp
  • PolandLexer.java
  • PolandLexer.tokens
  • PolandListener.java
  • PolandParser.java

生成されたJavaソースファイルをコンパイルします。

c:\antlr>javac *.java

これで構文解析が実行できる状態になりました。

構文解析の確認

ANTLRでは、構文解析を対話的に試せるTestRigというツールが利用できます。準備をやっていれば、grunで実行できます。
-treeオプションを指定して実行することで、構文解析した結果の構文木を表示できます。

c:\antlr>grun Poland exp -tree
(a+b)*(c-d)

(exp (exp ( (exp (exp a) + (exp b)) )) * (exp ( (exp (exp c) - (exp d)) )))

構文木がテキストだと見辛いので、-guiオプションを指定して画像ファイルで出力します。

c:\antlr>grun Poland exp -gui
(a+b)*(c-d)

とても見やすいです。

逆ポーランド記法変換プログラムの実装

ここからはANTLRが生成した構文解析プログラムを使って、数式を逆ポーランド記法に変換するプログラムを実装していきます。
ANTLRでは、構文木のノードをたどる方法として、Listener方式とVisitor方式をサポートしています。本記事ではListener方式で実装します。

Listenerクラスの実装

ANTLRが生成した、ListenerのベースクラスであるPolandBaseListenerクラスを継承するクラスを実装します。

下図のように、構文木のノードをたどる時に、expノードから出ていく時に呼ばれるexitExpメソッドをオーバーライドして、式を表示する処理を実装します。

PolandInterfaceListener.java
import org.antlr.v4.runtime.TokenStream;
import org.antlr.v4.runtime.misc.Interval;

public class PolandInterfaceListener extends PolandBaseListener {
    PolandParser parser;

    public PolandInterfaceListener(PolandParser parser) {
        this.parser = parser;
    }

    @Override
    public void exitExp(PolandParser.ExpContext ctx) {
        if( ctx.PLUS() != null )
          System.out.print(ctx.PLUS() + " ");
        else if( ctx.MINUS() != null )
          System.out.print(ctx.MINUS() + " ");
        else if( ctx.MUL() != null )
          System.out.print(ctx.MUL() + " ");
        else if( ctx.DIV() != null )
          System.out.print(ctx.DIV() + " ");
        else if( ctx.SYM() != null )
          System.out.print(ctx.SYM() + " ");
        else if( ctx.NUM() != null )
          System.out.print(ctx.NUM() + " ");
    }
}

Mainクラスの実装

mainメソッドを持つクラスを実装します。入力となる数式は、コマンドライン引数で受け取るようにします。

PolandMain.java
import org.antlr.v4.runtime.CommonTokenStream;
import org.antlr.v4.runtime.tree.*;
import org.antlr.v4.runtime.CharStream;
import org.antlr.v4.runtime.CharStreams;

public class PolandMain {
    public static void main(String[] args) throws Exception {
        CharStream input = CharStreams.fromString(args[0]);

        PolandLexer lexer = new PolandLexer(input);
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        PolandParser parser = new PolandParser(tokens);
        ParseTree tree = parser.exp();

        ParseTreeWalker walker = new ParseTreeWalker();
        PolandInterfaceListener extractor = new PolandInterfaceListener(parser);
        walker.walk(extractor, tree);
    }
}

動作確認

PolandMainクラスを実行してみます。

c:\antlr>java PolandMain (a+b)*(b-c)
a b + b c - *

いい感じに動いているように見えますが、実は上手く動かない場合があります。「演算子の優先順位」の考慮ができていないためです。

例えば、以下の例を見てみます。

c:\antlr>java PolandMain a+b*c
a b + c *

*は+よりも優先順位が高いので、abc*+とならないといけないのですが、+が先に計算されています。

というわけで、入力は適切な優先順位で計算されるように括弧で括られているという前提にします。
#いや、そこは上手いこと解決しろよ、とツッコまれそうですが、妙案が思い浮かばなかったので。。

改めて動作確認してみます。

c:\antlr>java PolandMain a+(b*c)
a b c * +

もっと複雑な例で動かしてみます。

c:\antlr>java PolandMain ((a+b+c)*(d/e))+(f-(g*h))
a b + c + d e / * f g h * - +

いい感じになりました。これで終わりです。