第 4.1 回 構文解析木

本日の内容

このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。

1. 構文解析木の作成

構文木のデータ構造

さて、構文解析のプログラムから構文木を作ることを考えます。 ここでは文法 G2' のプログラムで考えます。

例1


private static boolean 始(){
   if(次 == 数){ // Director(始,和=)={数}
      if(和()){
        if(次 == '='){
          return true;
        }
      }
   }
   return false;
}
private static boolean 和(){
   if(次==数){ // Director(和,数和')={数}
      次を読む;
      if(和'()){
        return true;
      }
   }
   return false;
}
private static boolean 和'(){
   if(次=='='){ // Director(和',ε)
     return true;
   }else if(次=='+'){ // Director(和',+数和')
     次を読む;
     if(次==数){
       次を読む;
       if(和'()){
         return true;
       }
     }
   }
   return false;
}  
public static void main(String[] arg){
  次を読む;
  if(始()){
    System.out.println("Ok");
  }else{
    System.out.println("NG");
  }
}


def 始():
    if 次 == 数: # Director(始,和=)={数}
        if 和():
            if 次 == '=':
                return True
   return False

def 和():
    if 次==数: # Director(和,数和')={数}
        次を読む
        if 和'():
            return True
   return False

def 和'():
    if 次=='=': # Director(和',ε)
        return True
    elif 次=='+': # Director(和',+数和')
        次を読む
        if 次==数: 
            次を読む
            if 和'():
                return True
    return False

次を読む;
if 始():
    print("Ok")
else:
    print("NG")
この例において G2' の 終端記号に対応するメソッドは s(), wa1(), wa2() です。 このうち、 s() は構文解析が終わった後、構文木を返すこととします。 構文木とは以下のようなものです。

構文解析木

この構造を作るのに、各頂点に対応するオブジェクト型として Node 型を考 えます。 上記のように構文解析木では数だけ入っている物と、演算子が入っていて子の 頂点が 2 つある物の二種類があります。 この二種類も新たなオブジェクトとみなし、それぞれ Kazu 型と Wa 型で表す ことにします。 すると、これらはどちらも Node でもあるので両方とも is-a 関係が成立しま す。 つまり、Kazu 型、 Wa 型ともに Node 型を継承しています。 したがって、とりあえず setter, getter のみしか示しませんが、各クラスは 以下のようになります。 


class Node {
}
class Kazu extends Node {
    private int value;
    public Kazu(int n){
	value = n;
    }
}
class Wa extends Node {
    private char op;
    private Node left;
    private Node right;
    public Wa(){}
    public void setOp(char op){
	this.op = op;
    }
    public void setLeft(Node n){
	left = n;
    }
    public void setRight(Node n){
	right = n;
    }
}


class Node:
    pass
class Kazu(Node):
    def __init__(self, n):
        self.value = n

class Wa(Node):
    def setOp(self, op):
	self.op = op

    def setLeft(self, n):
	self.left = n

    def setRight(self, n):
	self.right = n

この定義では、親クラスの Node 型でメソッドが定義されていないので Wa ク ラスのメソッドが利用できなくなってしまいます。 そのため、 Node クラスには双方のメソッドを集めて abstract 宣言をしてお きます。 


abstract class Node {
    abstract public void setOp(char op);
    abstract public void setLeft(Node n);
    abstract public void setRight(Node n);
}

このようなクラスを用いて構文解析木を作ります。 まず、具体的な例として 以下の木を(手動で)作るプログラムを示します。

構文解析木 

class Rei {
    public static void main(String[] arg){
	final Node tmp = new Wa();
	tmp.setOp('+');
	tmp.setLeft(new Kazu(1));
	tmp.setRight(new Kazu(2));
	final Node root = new Wa();
	root.setOp('+');
	root.setLeft(tmp);
	root.setRight(new Kazu(3));
    }
}


tmp = Wa()
tmp.setOp('+')
tmp.setLeft(Kazu(1))
tmp.setRight(Kazu(2))
root = Wa()
root.setOp('+')
root.setLeft(tmp)
root.setRight(Kazu(3))

これで、変数 root が指しているオブジェクトとして構文解析木ができました。 最終的には、この作業を数式の構文解析プログラムに生成させます。 しかし、その前に、デバッグなどにも利用するため、構文解析木からの出力を考えます。

コンポジットデザインパターン

さて、ここで、このような状況に適合するデザインパターンを学びます。 上記の構文木は各 Node オブジェクト同士が互いに関連づいています。 この様な、同一のクラスのオブジェクトが関連付けられているような再帰的な 構造に対して、各オブジェクトから情報収集をするなど、次々とメソッドを動 作させるテクニックがコンポジットデザインパターンです。 なお、特に構文解析木から値など意味を抽出するために構文木から情報収集す る場合にインタプリタデザインパターンと言います。

コンポジットデザインパターンでは、線形リストや木構造などのデータ構造に おいて、すべての頂点が特定の親クラスを継承しているものとします。 そして、関係するすべてのクラスで同一メソッドを実装します。 その時、子の頂点に対して同一のメソッドを呼び出すことで再帰的にメソッド を実行します。 また、頂点のオブジェクト型に応じてポリモーフィズムが行われ、各頂点にふ さわしい動作が選択されます。

さて上記の構文木からもとの数式を取り出すことを考えます。 もとに戻してしまうため、一見何の意味もないように感じてしまいますが、 取り出せれば、構文解析のプログラムのチェックに使うことができます。 さて、これを実現するために、 Node, Wa, Kazu の各クラスに共通したメソッドを定義します。 ここでは、定義するのは showExpression メソッドとしましょう。 Kazu クラスでは単に保存されている数値を表示させることとします。 一方、 Wa クラスでは、演算子の左側の数式を表示してから、演算子を表示し、演算 子の右側をカッコを付加して表示します。 この様に実装したものを次に示します。 


abstract class Node {
    abstract public void showExpression();
}
class Kazu extends Node {
    @Override
    public void showExpression(){
	System.out.print(value);
    }
}
class Wa extends Node {
    @Override
    public void showExpression(){
	System.out.print('(');
	left.showExpression();
	System.out.print(op);
	right.showExpression();
	System.out.print(')');
    }
}


class Node:
    def showExpression(self):
        pass
# 実はこの空のメソッド定義は無くても動く
class Kazu(Node):
    def showExpression(self):
        print(self.value)
class Wa(Node):
    def showExpression(self):
        print('(')
	self.left.showExpression()
	print(self.op)
	self.right.showExpression()
	print(')')

さて、同 様にしてデータ構造とアルゴリズム I で取り上げた逆ポーランド記法の表現 ができます。 では、ここで式の記述法について復習をしましょう。 通常の数式は演算子の両側に数値を記入します。 しかし、この演算子と二つに数値の関係に関して意味を変えず、表現を変える ことができます。

例えば、「add 1 and 2」など演算子を前に書くのを「前置記法」と言います。 これは例えば ((1 + 2) + 3) なら (+ (+ 1 2) 3) と書けます。 この記法は通常のコンピュータのプログラムに多い「命令 引数1 引数2」の記 法と共通です。 そのため構文としてこれしか持たないような Lisp などの言語で使われていま す。

一方、演算子を後ろに書くのが「後置記法」ですが、これは特に 逆ポーランド記法と呼ばれます。 例えば ((1 + 2) + 3) なら ((1 2 +) 3 +) となります。 この記法の特徴は、演算子の直後に閉じ括弧があるということです。 これは、演算子があれば、そこで注目すべき演算が完結することを意味します。 そのため、直前の二つの確定した値を引数にして演算を実行すれば計算ができ ます。 さらに、このため、上記の数式の表現に対してすべてのカッコを取っても演算 のしかたに曖昧さが生じません。 つまり 1 2 + 3 + などと表現すればよいことになります。 また、直近の値を取り出せば数式を計算できるため、スタックというデータ構 造を使えば数式の値を計算できます。

では、上記のデータ構造に対して逆ポーランド記法を出力するメソッド rpn (reverse Polish notation)プログラムを示します。 これは単に表示順序を「(左+右)」から「左 右 +」に変更するだけなので、下 記のようになります。 


abstract class Node {
    abstract public void rpn();
}
class Kazu extends Node {
    @Override
    public void rpn(){
	System.out.print(value+" ");
    }
}
class Wa extends Node {
    @Override
    public void rpn(){
	left.rpn();
	right.rpn();
	System.out.print(op+" ");
    }
}


class Node:
    def rpn(self):
        pass
# 実はこの空のメソッド定義は無くても動く
class Kazu(Node):
    def rpn(self):
        print(self.value+" ")

class Wa(Node):
    def rpn(self):
        self.left.rpn()
        self.right.rpn()
        print(self.op+" ")

演習1

前置記法を表示するメソッドを作成しなさい。

Visitorデザインパターン

コンポジットデザインパターンでは、木構造を作る親クラスNode以下、全 ての子クラスに目的の処理をするメソッドを埋め込んで実装しました。 数式を表示させたり、 逆ポーランド記法にしたり、計算したりなど、 様々な機能について、それを各クラスに書き込んでいました。 それで、目的は達成できますが、Nodeクラス以下、さまざまなクラスの複 雑度が増します。さらにNodeクラス以下は構文解析木を表現するのが責務 であって、 それのアプリケーションまで実装するのは、単一責務の原則に反している 気もします。

これに対して、木構造を作るクラスについてはなるべく手を加えずに、 様々な処理をオブジェクトとして作用させて作ることができれば、 単一責務の原則も満たすことになるため、重要なテクニックとなります。 Visitorデザインパターン はそれを満たすデザインパターンです。

Visitorデザインパターンの基本的な考え方は、構文解析木を表現してい るオブジェクトの集まりに対して、showExpression や RPN を表示させる ようなVisitor クラスを作成して、構文解析木にそのクラスを作用させて、処理結 果を得るというものです。

Kazuクラス Waクラス
showExpression に関する visitor 数の文字列を返す "(左側の式 + 右側の式)"の文字列を返す
RPN に関する visitor 数の文字列を返す "左側の式 右側の式 + "の文字列を返す
計算に関する visitor 数を返す 左側の式+右側の式を計算して値を返す

この仕組みは、構文解析木を構成する各オブジェクトごとに、さらに、Visitor クラスのオブジェクトごとに、異なる処理を実施する必要があります。 つまり二つのオブジェクトにより定められるメソッドを実行する必要があります。 この二つのクラスに依存したメソッド実行を ダブルディスパッチ と言います。 通常の、オブジェクト.メソッド(引数)のようなメソッド呼び 出しは、一つのオブジェクトにだけ依存した呼び出しなので、シングルディ スパッチと呼びます。

Visitorデザインパターンにおいて、 ダブルディスパッチを実行するには、 Visitor オブジェクトを引数にして、各 Node 以下のクラスが、それぞれ 対応する visitor のメソッドを呼び出せる accept メソッドだけを追加 し、 実際の機能を実現するのは、各Nodeクラスごとに別々に実装された Visitor クラス内の visit メソッドになります。 


abstract class Node {
    abstract <T> T accept(Visitor<T> visitor);
}
class Kazu extends Node {
    @Override
    <T> T accept(Visitor<T> visitor) {
        return visitor.visit(this);
    }
}
class Wa extends Node {
    @Override
    <T> T accept(Visitor<T> visitor) {
        return visitor.visit(this);
    }
}
interface Visitor<T> {
    T visit(Kazu node);
    T visit(Wa node);
}
class ShowExpressionVisitor implements Visitor<String> {
  String visit(Kazu node){
    return node.値を取り出して文字列にする;    
  String visit(Wa node){
    String left = nodeの左側のnode.accept(this);
    String right = nodeの右側のnode.accept(this);
    return "("+left+"+"+right+")";
}
...


class Node:
    def accept(self, visitor):
        pass
class Kazu(Node):
    def accept(self, visitor):
        return visitor.visit_kazu(self)
#python はオーバライドできないので、visit メソッド名はすべて型を含める
class Wa(Node):
    def accept(self, visitor):
        return visitor.visit_wa(self)
#Visitor では Node の実装クラス全部の visit メソッドを実装する
class ShowExpressionVisitor:
    def visit_kazu(self, node):
        return node.値を取り出して文字列にする
    def visit_wa(self, node):
        left = nodeの左側のnode.accept(self)
        right = nodeの右側のnode.accept(self)
        return f"({left}+{right})"
...

実際のVisitorデザインパターンの実装は次の通りです

  1. 抽象クラス Visitor クラスは、訪問すべき全てのクラスのオブジェ クトに対して、それを引数とする visit メソッドを用意する。 なお、戻り値の型は処理結果となる。そのため、総称型として良い。 一方、Python 言語のようなオーバーロードが効かないプログラミング 言語では、メソッド名を visit_型名(self, その型の引数) のように定義する。
  2. データを作っている方の親クラスNodeには、最小限のメソッドとして、 引数visitorで、visitorと同じ戻り値の型である accept(Visitor)メソッ ドだけを追加します。
  3. Nodeのサブクラスにはvisitor.visit(自身のオブジェクト) を返す accept メソッドを実装します。
  4. Visitor のサブクラスは各 visit メソッドを実装します。 計算には引数の node を、それぞれのメソッドごとに処理を書きます。

構文解析プログラムによる構文解析木

さて、構文解析の手続きにおいて、前節で定義したデータ構造による構文解析 木を返すプログラムを考えます。 これは構文に意味を与えることになります。

始めに G1 を考えます。 各ルールで、次のように木が作られます。

ルール 機械的な構文解析木 数式の構造
和→和+数 ルール1の導出木 ルール1での計算
和→数 ルール2の導出木 ルール2の導出木

和の部分を考えると、導出により木の下の方に移動していくので、上から下へ 木を作っていきます。 もし、この形で構文解析出来るのであれば、プログラムは単純になります。 というのは、 + の両側が一つのルールの中で完結するからです。 


/* G1 による構文解析木(ただし動作しない) 
   エラー処理はかなり適当
*/
class Parser {
    public Node wa(){
        if(入力が適合){
           Node result = new Wa();
           result.setLeft(wa());
           result.setOp(lastChar);
           nextChar();
           result.setRight(kazu());
           return result;
        }
        return null;
    }
    public Node kazu(){
        if(入力が適合){
           return new Kazu(lastChar);
        }
        return null;
    }
}


# G1 による構文解析木(ただし動作しない) 
# エラー処理はかなり適当
class Parser:
    def wa(self):
        if 入力が適合:
            result = Wa()
            result.setLeft(wa())
            result.setOp(Parser.lastChar)
            Parser.nextChar()
            result.setRight(kazu())
            return result
        else:
            return null
    def kazu(self):
        if 入力が適合:
           return Kazu(Parser.lastChar)
                }
        return null

しかし、これは左再帰性があるため、動作しません。

一方 G2 は次のように木が作られます。

ルール 機械的な構文解析木 数式の構造
和→数和' ルール1の導出木 ルール1の計算
和'→ + 数和' ルール2の導出木 ルール2の計算
和'→ε そのまま

G2は左側に終端記号が来ます。 文字列は左から読むのでこれはどんどん木に対して終端記号を対応づけていく ことになります。 つまり G2では、下から上へ木を作ることになります。 また、一つの非終端記号のルールで演算子の左右が導出されません。 特に「和'」では ε か +数和' のどちらかになりますが、 ε では数式は終了しますが、 + があれば新しい親ノードが生成されなければな りません。 これは作りかけの構文解析木に対して、それで終了するか、それを左側にした 新たな親ノードを作るかです。 これを実現させるには、木の根の参照を書き換える必要があるので、構文解析 木の管理においてメソッドから書き換え可能になっている必要があります。 そのため、 Parser のメンバ変数で持つことにします。 また、木の参照を与えると、その木を左に持つような親頂点を返すような頂点 のファクトリメソッドを作ります。

それでは話をまとめます。 まず、 Parser のメンバ変数として、 Node 型の変数 root を持つことにしま す。 そして、 Wa クラスに次のようなファクトリを用意します。 


class Wa extends Node {
    public static Node connectToLeft(Node n){
        final Wa result = new Wa();
        result.setLeft(n);
        return result;
    }
}


class Wa(Node):
    @classmethod
    def connectToLeft(cls,n):
        result = Wa()
        result.setLeft(n)
        return result

そして、上記の処理を実装したのが以下のプログラムになります。 これにより、数式を逆ポーランド記法に変換するなどが可能になります。 なお、トークンの取り出しはやっていないので、数値は 1 桁のみしか取り出 せません。 


import java.io.*;
class Parser {
    final private Reader reader;
    public Parser(Reader r) throws IOException{
	reader = r;
	c = reader.read();
    }
    private int c;
    private Node root;
    public Node s() throws IOException{
	if(Character.isDigit(c)){
	    if(wa1()){
		if(c=='='){
		    c = reader.read();
		    return root;
		}
	    }
	}
	return null;
    }
    private boolean wa1() throws IOException{
	System.err.println("called wa1.");
	if(Character.isDigit(c)){
	    root = new Kazu(c-'0');
	    c = reader.read();
	    if(wa2()){
		return true;
	    }
	}
	return false;
    }
    private boolean wa2() throws IOException{
	System.err.println("called wa2.");
	if(c=='='){
	    return true;
	}
	if(c=='+'){
            char op = (char) c;
	    c = reader.read();
	    if(Character.isDigit(c)){
		root = Wa.connectToLeft(root);
	        root.setOp(op);
		root.setRight(new Kazu(c-'0'));
		c = reader.read();
		if(wa2()){
		    return true;
		}
	    }
	}
	return false;
    }
	
}
class Rei {
    public static void main(String[] arg) throws IOException{
	final Reader r = new InputStreamReader(System.in);
	final Parser parser = new Parser(r);
	Node tree = parser.s();
	if(tree !=null){
	    tree.showExpression();
	    tree.rpn();
	}
    }
}


class Reader:
    def __init__(self, string):
        self.l = list(string)
        self.p = 0

    def read(self):
        if self.p >= len(self.l):
            raise StopIteration()
        result = self.l[self.p]
        self.p += 1
        return result
    
class Parser:
    def __init__(self, r):
        self.reader = r
        self.c = self.reader.read()

    def s(self):
        if self.c.isdecimal():
            if self.wa1():
                if self.c=='=':
#                    self.c = self.reader.read()
                    return self.root
        return None
    def wa1(self):
        print("called wa1.")
        if self.c.isdecimal():
            self.root = Kazu(int(self.c))
            self.c = self.reader.read()
            if self.wa2():
                return True
        return False

    def wa2(self):
        print("called wa2.")
        if self.c=='=':
            return True
        if self.c=='+':
            op = self.c;
            self.c = self.reader.read()
            if self.c.isdecimal():
                self.root = Wa.connectToLeft(self.root)
                self.root.setOp(op)
                self.root.setRight(Kazu(int(self.c)))
                self.c = self.reader.read()
                if self.wa2():
                    return True
        return False

r = Reader(input())
parser = Parser(r)
tree = parser.s()
if tree != None:
    tree.showExpression()
    print()
    tree.rpn()
    print()

演習2

以上の議論により、数式(足し算のみ)を前置記法に変換するプログラ ムを作りなさい。

2. コンパイラコンパイラのインストール

次回は JavaCC を使います。 インストールしておいてください。

NetBeans でのインストール方法

  1. https://javacc.org/download から JavaCC をダウンロードし、任意のフォルダに展開する。
  2. javacc-6.0/bin のフォルダ内に javacc.bat という次の内容のファイル を作る 
        
@echo off
java -classpath (JavaCCを展開したフォルダの絶対パス)\bin\lib\javacc.jar javacc %1 %2 %3 %4 %5 %6 %7 %8 %9
  3. NetBeans 用のプラグインサイトより プラグイン をダウンロードする。 2018年5月4日現在、ファイル名は 1275348047830_org-javaccnb.nbm。
  4. NetBeans を起動する。
  5. ツール→プラグインでプラグインのツールを起動。
  6. 「ダウンロード済み」タブを選び、「プラグインの追加」ボタンを押し、 ダウンロードしたプラグインファイル(.nbm)を選択し、「インストール」 ボタンを押す。
  7. ライセンス条項を承認し、「インストール」ボタンを押す。署名の検証で 警告が出るが、承認する。 インストールに成功すると、「今すぐIDEを再起動」が選択されているの で「終了」ボタンを押す。
  8. ツール→オプションでオプションを起動する。
  9. その他タブのJAVACC タブを選択し、JavaCC Path に作成した javacc.bat の絶対パスを指定し、「Ok」を押す。
  10. Java のプロジェクト内で src フォルダで右クリックし、 「新規ファイ ル」を選択する。 「その他」のカテゴリ内に Empty JavaCC File というファイルタイプが含まれている。 「次へ」ボタンを押すとフォルダとファイル 名を聞いてくる。 それに答えて Ok を押すと、Hello World の雛形の jj ファイルが追加される。
  11. jj ファイルを右クリックし、「Java CC Compile」を選ぶと、 Java のソー スコードが生成される。

Intellij IDEA でのインストール方法

残念ながら、2019年5月現在、Intellij IDEA で JavaCC を起動できません。 単にソースコードに色を付けることができるだけです。

  1. Intellij IDEA で File→Settings を選び Plugins を選ぶ。
  2. Market place タブで 「Search plugins in marketplace」の欄で「javacc」を入れ、検索をす る
  3. JavaCC と JavaCC Plugin の2つが見つかる。 これはどちらもソースコードに色を付ける程度の Plugin。 見た目は違うので、両方インストールして、 どちらか一方を好みで有効にすれば良い。

JavaCC の運用

  1. https://javacc.org/download から JavaCC をダウンロードし、任意のフォルダに展開する。
  2. javacc-6.0/bin のフォルダ内に javacc.bat という次の内容のファイル を作る 
        
@echo off
java -classpath (JavaCCを展開したフォルダの絶対パス)\bin\lib\javacc.jar javacc %1 %2 %3 %4 %5 %6 %7 %8 %9
  3. Intellij IDEA では jj ファイルを src フォルダ内に入れる。
  4. コンパイルはIntellij IDEA からではできないので、Power Shell または コマンドプロンプトで cd IdeaProject\プロジェクト名\src に移動した後、 (JavaCCを展開したフォルダの絶対パス)\bin\javacc (jjファイル名) で、 java ファイルが生成され、 Intellij IDEA で取り扱えるようになる。

なお、javacc (jjファイル名)だけで JavaCC を起動したい時は、 「環境変数」を検索して、変更画面を出し、 Path を編集して、既に入って いる内容の後に;(JavaCCを展開したフォルダの絶対パス)\bin を追加する。

Eclipse でのインストール方法

  1. Help→ Install New Softwares
  2. Available Software ウィンドウで Add ボタンを押す
  3. Location に http://eclipse-javacc.sourceforge.net/ を入れる
  4. Java CC Eclipse Plug-in 項目が表示されたらチェックし、 Next ボタンを押す
  5. 次の確認画面でもNextボタンを押す。さらにライセンスの承認画面が出るので、accept をチェックし、Finish ボタンを押す
  6. さらに、残念なことにインストールするソフトウェアに署名されていない旨のメッセージが出るが、 Ok を押しインストールする
  7. Restartする
  8. Java のプロジェクト内で src フォルダで右クリックし、 New → Other で JavaCC の JavaCC Template File を選択するとパッケージ名やファイル 名を聞いてくる。 それに答えて Ok を押すと、数式処理の雛形の jj ファイルが追加される。

コマンドラインでのインストール方法（古）

  1. http://javacc.java.net/ から Getting the Software 中のDownloadの Older を選択し、 表示されるファイルの中から javacc-5.0.zipを選択、ダウンロードする (6.0があっても5.0を選ぶ)
  2. javacc-5.0.zip を解凍する。
  3. できたフォルダ javacc-5.0 を c:\ に移動する。
  4. dir c:\javacc-5.0\bin\javacc.* として javacc と javacc.bat が表示されればインストール成功
  5. 以下のプログラムを setup.bat というファイル名で作成し、デスクトップに 置く。 
    
@echo off
set PATH=%PATH%;c:\javacc-5.0\bin
cd \work
cmd
    なお、上記の \work は自分の作業用ディレクトリに書き換えること
  6. この setup.bat を動かして、出てきたウィンドウの中で javacc と打って、 javacc のメッセージが出てくれば成功。 「'javacc'は、内部コマンドまたは外部コマンド、操作可能なプログラムまた はバッチファイルとして認識されていません。」と出てくればどこかで失敗し ています。

python 用の文脈自由文法を処理するパッケージには様々ありますが、 本講義では Lark を使用します。

Lark はpip install larkでインストール。 なお、Lark の ホームページは https://github.com/lark-parser/lark にあり、 ドキュメントは https://lark-parser.readthedocs.io/en/stable/ を参照してください。

3. 付録

本章で説明したプログラムの動作可能版


abstract class Node {
    abstract public void setOp(char op);
    abstract public void setLeft(Node n);
    abstract public void setRight(Node n);
    abstract public void showExpression();
    abstract public void rpn();
}
class Kazu extends Node {
    private int value;
    public Kazu(int n){
	value = n;
    }
    @Override
    public void showExpression(){
	System.out.print(value);
    }
    @Override
    public void rpn(){
	System.out.print(value+" ");
    }
}
class Wa extends Node {
    private char op;
    private Node left;
    private Node right;
    public Wa(){}
    public void setOp(char op){
	this.op = op;
    }
    public void setLeft(Node n){
	left = n;
    }
    public void setRight(Node n){
	right = n;
    }
    public static Node connectToLeft(Node n){
        final Wa result = new Wa();
        result.setLeft(n);
        return result;
    }
    @Override
    public void showExpression(){
	System.out.print('(');
	left.showExpression();
	System.out.print(op);
	right.showExpression();
	System.out.print(')');
    }
    @Override
    public void rpn(){
	left.rpn();
	right.rpn();
	System.out.print(op+" ");
    }
}
import java.io.*;
class Parser {
    final private Reader reader;
    public Parser(Reader r) throws IOException{
	reader = r;
	c = reader.read();
    }
    private int c;
    private Node root;
    public Node s() throws IOException{
	if(Character.isDigit(c)){
	    if(wa1()){
		if(c=='='){
		    c = reader.read();
		    return root;
		}
	    }
	}
	return null;
    }
    private boolean wa1() throws IOException{
	System.err.println("called wa1.");
	if(Character.isDigit(c)){
	    root = new Kazu(c-'0');
	    c = reader.read();
	    if(wa2()){
		return true;
	    }
	}
	return false;
    }
    private boolean wa2() throws IOException{
	System.err.println("called wa2.");
	if(c=='='){
	    return true;
	}
	if(c=='+'){
            char op = (char) c;
	    c = reader.read();
	    if(Character.isDigit(c)){
		root = Wa.connectToLeft(root);
	        root.setOp(op);
		root.setRight(new Kazu(c-'0'));
		c = reader.read();
		if(wa2()){
		    return true;
		}
	    }
	}
	return false;
    }
	
}
class Rei {
    public static void main(String[] arg) throws IOException{
	final Reader r = new InputStreamReader(System.in);
	final Parser parser = new Parser(r);
	Node tree = parser.s();
	if(tree !=null){
	    tree.showExpression();
	    tree.rpn();
	}
    }
}



class Node:
    def showExpression(self):
        pass
    def rpn(self):
        pass

class Kazu(Node):
    def __init__(self, n):
        self.value = n
    def showExpression(self):
        print(self.value,end="")
    def rpn(self):
        print(self.value," ",end="")

class Wa(Node):
    def setOp(self, op):
        self.op = op

    def setLeft(self, n):
        self.left = n

    def setRight(self, n):
        self.right = n
    def rpn(self):
        self.left.rpn()
        self.right.rpn()
        print(self.op," ",end="")
    def showExpression(self):
        print('(',end="")
        self.left.showExpression()
        print(self.op,end="")
        self.right.showExpression()
        print(')',end="")
    @classmethod
    def connectToLeft(cls,n):
        result = Wa()
        result.setLeft(n)
        return result
class Reader:
    def __init__(self, string):
        self.l = list(string)
        self.p = 0

    def read(self):
        if self.p >= len(self.l):
            raise StopIteration()
        result = self.l[self.p]
        self.p += 1
        return result
    
class Parser:
    def __init__(self, r):
        self.reader = r
        self.c = self.reader.read()

    def s(self):
        if self.c.isdecimal():
            if self.wa1():
                if self.c=='=':
#                    self.c = self.reader.read()
                    return self.root
        return None
    def wa1(self):
        print("called wa1.")
        if self.c.isdecimal():
            self.root = Kazu(int(self.c))
            self.c = self.reader.read()
            if self.wa2():
                return True
        return False

    def wa2(self):
        print("called wa2.")
        if self.c=='=':
            return True
        if self.c=='+':
            op = self.c;
            self.c = self.reader.read()
            if self.c.isdecimal():
                self.root = Wa.connectToLeft(self.root)
                self.root.setOp(op)
                self.root.setRight(Kazu(int(self.c)))
                self.c = self.reader.read()
                if self.wa2():
                    return True
        return False

r = Reader(input())
parser = Parser(r)
tree = parser.s()
if tree != None:
    tree.showExpression()
    print()
    tree.rpn()
    print()

Visitor版プログラム


abstract class Node {
    abstract <T> T accept(Visitor<T> visitor);
}
class NumberNode extends Node {
    private final double value;
    public NumberNode(double value) {
        this.value = value;
    }
    public double getValue() {
        return value;
    }
    @Override
    <T> T accept(Visitor<T> visitor) {
        return visitor.visit(this);
    }
}
class BinaryOperatorNode extends Node {
    private final char operator;
    private final Node left;
    private final Node right;
    public BinaryOperatorNode(char operator, Node left, Node right) {
        this.operator = operator;
        this.left = left;
        this.right = right;
    }
    public char getOperator() {
        return operator;
    }
    public Node getLeft() {
        return left;
    }
    public Node getRight() {
        return right;
    }
    @Override
    <T> T accept(Visitor<T> visitor) {
        return visitor.visit(this);
    }
}
interface Visitor<T> {
    T visit(NumberNode node);
    T visit(BinaryOperatorNode node);
}
class EvaluateVisitor implements Visitor<Double> {
    @Override
    public Double visit(NumberNode node) {
        return node.getValue();
    }

    @Override
    public Double visit(BinaryOperatorNode node) {
        double leftValue = node.getLeft().accept(this);
        double rightValue = node.getRight().accept(this);

        switch (node.getOperator()) {
            case '+':
                return leftValue + rightValue;
            case '-':
                return leftValue - rightValue;
            case '*':
                return leftValue * rightValue;
            case '/':
                return leftValue / rightValue;
            default:
                throw new UnsupportedOperationException("Unknown operator: " + node.getOperator());
        }
    }
}
class RPNVisitor implements Visitor<String> {
    @Override
    public String visit(NumberNode node) {
        return Double.toString(node.getValue());
    }

    @Override
    public String visit(BinaryOperatorNode node) {
        String left = node.getLeft().accept(this);
        String right = node.getRight().accept(this);
        return left + " " + right + " " + node.getOperator();
    }
}
class InfixVisitor implements Visitor<String> {
    @Override
    public String visit(NumberNode node) {
        return Double.toString(node.getValue());
    }

    @Override
    public String visit(BinaryOperatorNode node) {
        String left = node.getLeft().accept(this);
        String right = node.getRight().accept(this);
        return "(" + left + " " + node.getOperator() + " " + right + ")";
    }
}
class Main {
    public static void main(String[] args) {
        Node expression = new BinaryOperatorNode('+',
                new NumberNode(3),
                new BinaryOperatorNode('*',
                        new NumberNode(4),
                        new NumberNode(5)));

        EvaluateVisitor evaluateVisitor = new EvaluateVisitor();
        double result = expression.accept(evaluateVisitor);
        System.out.println("Result: " + result);

        RPNVisitor rpnVisitor = new RPNVisitor();
        String rpnExpression = expression.accept(rpnVisitor);
        System.out.println("RPN Expression: " + rpnExpression);

        InfixVisitor infixVisitor = new InfixVisitor();
        String infixExpression = expression.accept(infixVisitor);
        System.out.println("Infix Expression: " + infixExpression);
    }
}


class Node:
    def accept(self, visitor):
        pass
class NumberNode(Node):
    def __init__(self, value):
        self.value = value
    def accept(self, visitor):
        return visitor.visit_number(self)
class BinaryOperatorNode(Node):
    def __init__(self, operator, left, right):
        self.operator = operator
        self.left = left
        self.right = right
    def accept(self, visitor):
        return visitor.visit_binary_operator(self)
class Visitor:
    def visit_number(self, node):
        pass
    def visit_binary_operator(self, node):
        pass
class EvaluateVisitor(Visitor):
    def visit_number(self, node):
        return node.value
    def visit_binary_operator(self, node):
        left = node.left.accept(self)
        right = node.right.accept(self)
        if node.operator == '+':
            return left + right
        elif node.operator == '-':
            return left - right
        elif node.operator == '*':
            return left * right
        elif node.operator == '/':
            return left / right
class RPNVisitor(Visitor):
    def visit_number(self, node):
        return str(node.value)
    def visit_binary_operator(self, node):
        left = node.left.accept(self)
        right = node.right.accept(self)
        return f"{left} {right} {node.operator}"
class InfixVisitor(Visitor):
    def visit_number(self, node):
        return str(node.value)
    def visit_binary_operator(self, node):
        left = node.left.accept(self)
        right = node.right.accept(self)
        return f"({left} {node.operator} {right})"

expression = BinaryOperatorNode('+',
    NumberNode(3),
    BinaryOperatorNode('*',
        NumberNode(4),
        NumberNode(5)))

evaluate_visitor = EvaluateVisitor()
result = expression.accept(evaluate_visitor)
print("Result:", result)

rpn_visitor = RPNVisitor()
rpn_expression = expression.accept(rpn_visitor)
print("RPN Expression:", rpn_expression)

infix_visitor = InfixVisitor()
infix_expression = expression.accept(infix_visitor)
print("Infix Expression:", infix_expression)
坂本直志 <sakamoto@c.dendai.ac.jp>
東京電機大学工学部情報通信工学科