第 4 回 文脈自由文法と構文解析木

本日の内容


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

4-1. 文脈自由文法

ここからは正規文法で取り扱えないような言語を取り扱うため、正規文法より 強力な文法の記述法を学びます。

文法とルール

本講義で文法とは言語を定義するようなもの一般を意味してました。 しかし、通常、文法と呼ばれるものはもう少し形式が存在します。 英文法や国文法では、単語が品詞に分類でき、さらに文において品詞の並び方 が数通りに定められているという手法で定義されます。 例えば英語では、文は次の5文型になると言われています。

S+V
例: I ski. It rains. I have returned. This class has begun.
S+V+C
例: This is a pen. I am a student. You look tired.
S+V+O
例: I love you. I am studying programming.
S+V+O+O
例: I teach you theories of programming.
S+V+O+C
例: I find you asleep.

ここで S は主語、 Vは述語、Cは補語、Oは目的語です。

正規表現などはこのような表現ではありませんでした。 今回は、上記のように、文が特定の品詞の組み合わせでできているという ような文法表示を取り扱います。 このような表現による文法表現のしかた、正規文法との関係、プログラミング について学びます。 なお、 このような表現は、プログラミング言語や通信プロトコルの仕様の記述などに も利用されます。 そのため、利用価値が高いものです。

バッカス・ナウア記法

文法の与え方にはさまざまな方法がありますが、ここではバッカス・ナ ウア記法を取り上げます。 バッカス・ナウア記法は、 非終端記号の集合 VN、 終端記号の集合 VT、 ルール P、 開始記号 SVN の 4 つ組 G= ( VN, VT, P, S) で表します。

バッカス・ナウア記法では生成する文字列を作るアルファベットを 終端記号と言います。終端記号の集合を VT で表します。 一方、それに属さない記号を非終端記号と言います。 非終端記号の集合を VN で表します。 ルールは左辺に一つの非終端記号、右辺は非終端記号と終端記号の列で表しま す。通常は左辺と右辺は ::= や → という記号で結びます。 そして最後に一つ非終端記号を開始記号として指定します。 このルールで左辺に一つだけ非終端記号がある文法を 文脈自由文法と言います。

このように定義した文法において、つぎのような手順により記号列を生成しま す。

  1. 開始記号を左辺に含むルールを一つ選ぶ
  2. 開始記号をそのルールの右辺に置き換える
  3. 置き換えたものの中から非終端記号を一つ選ぶ
  4. その非終端記号を左辺に含むルールを一つ選ぶ
  5. その非終端記号を右辺に置き換える
  6. すべてが終端記号なら終了、そうでなければ 3 に戻る

簡単のため、左辺が同じルールは、右辺を |(縦棒) で区切って列挙すること で一つにまとめることにします。

文法の例

以下に簡単な文法の例を示します。

G=({文, 主語, 述語, 補語, 名詞句, 動詞, 代名詞, 冠詞, 名詞}, {This, is, a, pen}, P, 文)

P の定義

このようなルールから、 This is a pen という記号列が導けます。

このように終端記号と言っても一文字であるとは限りません。 通常は意味のあるひとまとまりの語句(トークン)毎に文法を考え ます。

括弧の処理

正規文法では取り扱えなかった括弧も、このバッカスナウア記法では比較的簡 単に扱えます。 単純な括弧のみの言語は次のように書けます。

例4-1


S→ε
S→SS
S→(S)

演習4-1

上記の文法にさらに [](角括弧)も使えるようにしなさい

正規文法

バッカス・ナウア記法において、指定できるルールを「非終端記号→終端 記号, 非終端記号 → 終端記号 非終端記号」だけに制限した 文法を正規文法といいます。

例4-2

a*
S→ε, S→aS
[abc]
S→a,S→b,S→c
(abc|asd)
S→aA, A→bB, B→c, A→sC, C→d
.*(a|b)
(アルファベットが { a, b, c } の時) S→aS, S→bS, S→cS, S→a, S→b

定理: 文脈自由文法に制限を与えた正規文法と、前回与えた正規文法は等 価である

まず、このルールから非決定性オートマトンを構成できることを示します。 各非終端記号をそれぞれ一つのオートマトンの状態とします。 そして、開始記号である非終端記号を表す状態を開始状態とします。 また、別に終了状態を作っておきます。 A→bC 型の遷移規則に関しては、状態 A から入力 b で状態 C に遷移するよ うにします。 一方、 A→b 型の遷移規則に関しては状態 A から入力 b で終了状態に遷移す るようにします。 この様に構成するとすべてのルールは非決定性オートマトンの遷移規則に変換 できます。 さらに、構成した非決定性オートマトンがもとの文脈自由文法と同じ言語を受 理することが明かです。

逆に非決定性オートマトンがすべてこの文脈自由文法に変換できることを示す ことで、最終的に両者が等価であることを示します。 これは、上記の変換が一対一で行えることから、逆もまた可能であることを示 せば充分です。 つまり、任意の非決定性オートマトンに対して、状態 A から入力 b で状態 C に遷移するなら、非終端記号 A と C と終端記号 b に対して A→bC というルー ルを対応付ければ良いということです。 なお、受理状態への遷移に関しては、受理状態からεの入力を加えれば良いで す。 つまり A→bC というルールで C が受理状態なら、さらに C→ε を加えます。

以上により、この表記法と、以前に定義した正規表現が等価であることが示せ ました。

演習4-2

整数をこのバッカス・ナウア記法による正規文法により表現しなさい。

4-2. 構文解析木

一般のバッカス・ナウア記法による記号列の生成では、一つの非終端記号が複数の 非終端、終端記号に対応します。そして、それに含まれる非終端記号がまた複 数の非終端、終端記号に対応します。 この導出の流れを図にすると、一つの非終端記号が複数の非終端、終端記号に 対応するので、木の構造になります。

A→bCD というルールの場合
ルールの図示

根は開始記号になり、葉は終端記号、葉以外の頂点は非終端記号になります。 与えられた記号列に対して、それの生成手順に対応した木を構文解析木 と言います。 例えば、上の This is a pen という記号列は次のような構文解析木を持ちま す。

This is a pen の構文解析木

一つの記号列について、複数の構文解析木を持つ文法をあいまい であると言います。あいまいな文法はコンピュータで機械的に処理することが できません。 因みに英語はあいまいです。 次の文章の解釈はなんと 4 通りあります。

Time flies like an arrow.

これは、動詞として Time, flies, like の三通りが考えられ、しかも Time が動詞の時は、 like an arrow の前が名詞になるので副詞句の他に形容詞句 になる可能性があるからです。

動詞 like an arrow 構文解析木
Time 副詞句 矢のように蝿の所要時間を計りなさい 矢のように蝿の所要時間を計りなさい
Time 形容詞句 矢に似ている蝿の所要時間を計りなさい 矢に似ている蝿の所要時間を計りなさい
flies 副詞句 時間は矢のように飛ぶ 時間は矢のように飛ぶ
like 時間蝿は一本の矢が好きである 時間蝿は一本の矢が好きである

英語の場合、前後の文章や蝿、矢などに関する知識などを利用してふさわしい 訳を選ぶ必要があります。

演習4-3

自然言語の構文解析はとても難しいです。 次の日本語の構文解析木を書きなさい。

  1. これはペンです
  2. すもももももももものうち
  3. きしゃのきしゃはきしゃできしゃした
  4. きしゃできしゃしたのはきしゃのきしゃです(汽車で帰社したのは貴社の 記者です)。

演習4-4

次の日本語を、前後関係などで構文を意識して、英訳しなさい

  1. わたしはうなぎです。

    これは、料理屋で注文を確認された時に、発言した言葉です。

  2. 私の娘は男だった。

    これは孫の誕生を話題にしている人同士の会話です。

足し算の文法

足し算だけの数式を解釈する文法を考えます。 最初に次の文法を考えます。

文法 G0

=({和},{数, +}, P0, 和)

+

この文法では、 1+1 のような式は解釈できますが、 1+2+3 は駄目です。そこ で、足し算がいくつつながっていても解釈可能な文法を考えます。 数式は、一般に左から右へ解釈します。したがって、 1+2+3 は 1+2 を解釈し た後、その和に対して +3 を加えたものを新しい和とします。 つまり、次のようなルールが必要になります。

+

このルールがあれば、一番左の項以外はこれで解釈できます。 一番左の項はそれだけで和とみなせば 1+2+3 を解釈できます。

文法 G1

=({和},{数, +}, P1, 和)

+
和の構文解析木1

なお、次のようにしてしまうと和の優先順序を指定できず、あいまいになりま す。

文法 G1x

=({和},{数, +}, P1x, 和)

+
あいまいな文法 あいまいな文法

演習4-5

括弧を加えるにはどうしたら良いか考えなさい。

4-3. 文法を解釈するプログラム

さて、文法からそれを解釈するプログラムを作 る手法を学びます。 なお、構文解析のことをparse、構文解析をするプログラムなどを parserといいます。

素朴な解析法

バッカス・ナウア記法の素朴な解析法として次のようなものがあります。 すべての非終端記号に対して、関数を作ります。 そして、左辺の非終端記号を関数呼び出しとし、右辺は関数の内部処理としま す。 そして、終端記号に対しては文字を認識し、非終端記号に関しては、それに対 応した関数を(再帰的に)呼び出します。 例えば、 A→bCD で A,C,D が非終端記号、 b が終端記号だった時、 関数 A を次のように作ります(あらかじめ文字を一つ読んでおきます)。


private boolean A(){
   if(記号 b を認識できたら){
     次の文字を読み込む
     if(C()){
       if(D()){
         return true;
       }
     }
   }
   return false;
}

def A():
    if 記号 b を認識できたら:
        次の文字を読み込む
        if C():
            if D():
                return True
    return False

そして非終端記号 C, D に対しても同様に関数を作ります。 このようにすると構文木通りに関数が呼び出されて、与えられた記号列を処理 できる場合があります。 しかし、実際は一つの非終端記号から複数の導出規則が存在します。 例えば、下の例では状態 S で文字 a を読み込んだ時、 A か B のどちらを導 出するかはすぐには決められません。

S→A|B
A→ab
B→ac

素朴な方法としては、適当に導出規則を選び、途中で失敗したら別の導出規則 を選ぶ方法が考えられます。これをバックトラックと言います。 確かにこの方法でも構文解析できますが、しかし、キューを実装しているよう に、途中の入力を全て覚える必要があります。 また、考え得る全ての構文木を一つ一つ生成しては比較するようなものなので、 効率が悪いです。

例4-3

A()||B() は A() を実行して true が返ってきたら B() は実行 されず true になります。 A() が false が返されたときだけ、 B() が実行されて、その値が返されます。


import java.io.*;
class Parser {
    public Parser(Reader r){
	reader = new BufferedReader(r);
    }
    final private BufferedReader reader;
    public boolean S() throws IOException{
	if(A() || B()){ // A がだめなら B
	    return true;
	}else{
	    return false;
	}
    }
    private boolean A() throws IOException{
	reader.mark(2); // 2 文字読んだあと戻す可能性がある
        if(reader.read()=='a' && reader.read()=='b'){
          return true;
        }
        reader.reset();
	return false;
    }
    private boolean B() throws IOException{
	reader.mark(2);
        if(reader.read()=='a' && reader.read()=='c'){
          return true;
        }
        reader.reset();
	return false;
    }
}
class Rei {
    public static void main(String[] arg) throws IOException{
	Parser parser = new Parser(new InputStreamReader(System.in));
	if(parser.S()){
	    System.out.println("Ok");
	}else{
	    System.out.println("NG");
	}
    }
}

class Parser:
    def __init__(self, string):
        self.list= list(string)
        self.pointer = 0
    def __iter__(self):
        return self
    def __next__(self):
        if self.pointer >= len(self.list):
            raise StopIteration()
        result = self.list[self.pointer]
        self.pointer += 1
        return result
    def mark(self):
        self.m = self.pointer
    def reset(self):
        self.pointer = self.m
def S():
    if A() or B():
        return True
    else:
        return False
def A():
    reader.mark()
    if next(reader)=='a' and next(reader)=='b':
        return True
    reader.reset()
    return False
def B():
    reader.mark()
    if next(reader)=='a' and next(reader)=='c':
        return True
    reader.reset()
    return False;

reader = Parser(input())
if S():
    print("Ok")
else:
    print("NG")

バックトラックを避け、効率良く構文解析するためにはどのようなことが考え られるでしょうか? 一つの考え方として、次に読み込む記号から必ず導出規則が一つ決定できるよ うな文法が与えられたとします。 そのような文法では文字を読み込みながら if 文でどちらの導出規則を選択で きるため、バックトラックを行わずに済みます。 この、どんな非終端記号に対しても、入力を左から読んでいき、次の先頭の文 字を読むだけで一意に導出が可能な文法を LL(1)文法 と言います。 (Left to Right, Leftmost derivation)

左再帰性の除去

さて、足し算の文法をプログラムで表現する手法を考えます。 まず、前回の足し算の文法は以下の通りです。

文法 G1

=({和},{数, +}, P1, 和)

+

この文法は LL(1) ではありません。 つまり、この文法では上で述べたように、文字を読んでも次の導出規則を決 めることはできません。 なぜならば、入力列に対して + というルールを適応するには、その先頭部分が「和」の形になってい るかどうかを調べる必要があります。そして、そのためにはその先頭部分が 「和」の形になっているかどうかを調べる必要があります。 このように解釈が巡回してしまい、結論にはたどり着けません。 つまり、左辺と同じ非終端記号が右辺の先頭に来ていると、入力 列を順に読む構文解析ができなくなります。 これを左再帰性と言います。

この左再帰性は次のようにすれば除去できます。 例えば、次のような左再帰性を持つ生成規則があったとします。

AAα|β

A は非終端記号で、α と β は非終端記号、終端記号からなる列を 表し、β は A で始まらないとします。 これは β, βα, βαα, ... という列を表 します。 この時、次のように書き直すと左再帰性がなくなります。

AβA' A' αA' | ε

上の足し算を解釈する文法G1の左再帰性を除去すると次のように なります。

文法 G2

=({和, 和'},{数, +}, P2, 和)

' '+ '|ε

さて、数式を計算させ、答えを求めたい場合、数式の最後を明白にする記号と して、 = を入力するというルールを追加します。 このルールを含めた文法 G1, G2 をそれぞれ G1', G2' とします。

文法 G1'

=({和, 始},{数, +, =}, P1', 始)

= +

文法 G2'

=({始, 和, 和'},{数, +, =}, P2', 始)

= ' '+ '|ε

再帰的下向き構文解析法

文法に対して、左辺から右辺への導出が、次の一文字を読むだけで決定できれ ば、その文法をLL(1) 文法と言います。 これは、開始記号から導出を始め、一番左の非終端記号を次の入力文字から導 出ルールを一意に決められれば良いというルールです。 各非終端記号 A に対して、その導出規則が A→α と A→β であったと仮定します。 この時、 Director(A,α) を A→α において、この規則によ り一番左側に導出される可能性のある終端記号の集合とします。 この時、どの非終端記号 A に対して、 Director(A,α)∩Director(A,β)=∅という関係が全ての A からの導出規則について成立すれば、得られた終端記号列から一意にプログ ラムで構文解析ができます。


private boolean A(){
  if(文字∈Director(A,α)){
    return αの処理が成功したか;
  }else if(文字∈Director(A,β)){
    return βの処理が成功したか;
  }...

  return false;
}

def A():
    if 文字∈Director(A,α):
        return αの処理が成功したか
    elif 文字∈Director(A,β):
        return βの処理が成功したか
    ...
    return False
}

ここで、Director 内で重複する終端記号はありませんので、文字はどこか一 つの Director にだけ属するだけです。 そのため、 α の処理などが失敗してもバックトラックの必要がありま せん。

さて、このような Director 集合の計算方法を与えます。 なおプログラムの処理では次の一文字を読んで次の動きを決めます。 そのため、終了判定を行うには終了したことがわかるように、入力文 字が終ったことを示す特殊な文字を考えることがあります。

LL(1)文法は次のように形式化できます。 α は非終端記号、終端記号からなる列とします。 また A は非終端記号とします。 この時 First(α), Follow(A), Director(A,α) を次のように定義 します。

First(α):
導出ルールの右辺 α に対して、 α から導出可能な列の先頭になりうる終端記号の集合。 もし、α から ε へ導出可能なら、ε も含めます。
Follow(A):
非終端記号 A に対して、開始記号から導出をした時に、 A の直後になり うる終端記号の集合。
Director(A,α):
各導出規則 A → α に対して、 Director(A,α) = First(α) 但し、 α から ε へ 導出可能ならFollow(A) も含めます。 この様に定義することで A→α の導出で、先頭に来る終端記号の候 補を得ることができます。

例4-4

文法 G2'についてこれらを計算すると次のようになります。

First ( = ) = { } First ( ' ) = { } First ( + ' ) = { + } First ( ε ) = { ε } Follow ( ) = { ε } Follow () = { = } Follow (') = { = } Director( =) = { } Director( ') = { } Director( ' +') = { + } Director( ' ε ) = { = }

このように各非終端記号に対して、その生成規則を示す Director 同士 に共通部分がない文法を LL(1) 文法と言います。 G2' は 計算した Director に共通部分がないので LL(1) 文法です。 実際、Director(和',⋅) は {+} と {=} なので共通部分はありません。

参考

なお G1' についても同様に計算すると次のようになります。

First ( = ) = { } First ( + ) = { } First() = { } Follow() = { ε } Follow() = { = } Director( =) = { } Director( +) = { } Director( ) = { }

このように非終端記号「和」に対して、 Director(和, ・) に重複がありますの で、 LL(1)文法ではありません。

LL(1) 文法は、先に示した素朴な関数呼出による構文解析に対して、次に来る ものを判断して構文規則を変えることで構文解析ができるようになります。

  1. 各非終端記号に対応した関数を作ります。ここでは A とし、作る関数を A() とします。
  2. Director(A,・)に応じてプログラムを書きます。 Director(A, B)={x,y}, Director(A, zuCw)={z} の時、次のようになります。
    
    import java.util.Arrays;
    private boolean isContained(char c, char[] set){
    // set はソートされている必要あり
      return Arrays.binarySort(set,c)>=0;
    }
    
    private boolean A(){
       if(isContaind(文字,new char[]{'x','y'}){
         return B();
       }else if(isContaind(文字, new char[]{'z'}){
         次の文字を読む;
         if(文字 == 'u'){
           次の文字を読む;
           if(C()){
             if(文字 == 'w'){
               return true;
             }
           }
         }
       }
       return false;
    }
    
    
    def A():
        if 文字 in {'x','y'}:
            return B()
        elif 文字 in {'z'}:
            次の文字を読む
            if 文字 == 'u':
                次の文字を読む
                if C():
                    if 文字 == 'w':
                        return True
        return False
    

例4-5

G2' は LL(1) 文法なので、プログラムで構文解析できます。 同様に Director により次のように計算できます(わ かりやすいように日本語を使ってますので、このままでは動きません)。


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")

例4-6

上記のプログラムにおいて、「次==数」の判定方法が自明ではありません。 これまでのまとめとして、数字一桁の足し算の式を受理する(形を認識するだ けで計算しない)プログラムを示します。 文字を読み込むタイミングが、 Director の要素の判定時ではなく、判定を通っ た後の実際のルールの解釈時であることに注意します。


import java.io.*;
class Parser {
    final private Reader reader;
    public Parser(Reader r) throws IOException{
	reader = r;
	c = reader.read();
    }
    private int c;
    public boolean s() throws IOException{
	System.err.println("called s.");
	if(Character.isDigit(c)){
	    if(wa1()){
		if(c=='='){
		    c = reader.read();
		    return true;
		}
	    }
	}
	return false;
    }
    private boolean wa1() throws IOException{
	System.err.println("called wa1.");
	if(Character.isDigit(c)){
	    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=='+'){
	    c = reader.read();
	    if(Character.isDigit(c)){
		// 足し算の処理
		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);
	if(parser.s()){
	    System.out.println("accept");
	}else{
	    System.out.println("reject");
	}
    }
}

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):
        print("called s.")
        if self.c.isdecimal():
            if self.wa1():
                if self.c=='=':
                    return True
        return False
    def wa1(self):
        print("called wa1.")
        if self.c.isdecimal():
            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=='+':
            self.c = self.reader.read()
            if self.c.isdecimal():
		# 足し算の処理
                self.c = self.reader.read()
                if self.wa2():
                    return True
        return False

r = Reader(input())
parser = Parser(r)
if parser.s():
    print("accept")
else:
    print("reject")

なお Pascal というプログラミング言語は LL(1) 言語です。 したがって、 LL(1) は制限がきついですが、そこそこ実用的な文法まで表現 できます。

トークンの切り出し

例4-3 では各関数で文字を読んでいました。 このような処理の仕方はこれまでのプログラムは構造が異なっています。 以下に構造を抽象的に示します。

前回までのプログラム


public static void main(String[] arg){
  前処理;
  while(文字を読みつづける){ // 読み込みは一ヶ所
    文字列の組み立て処理;
    文字列が完成したら出力;
  }
  後処理;
}

前処理
for 文字 in list(文字列):
    文字列の組み立て処理
    文字列が完成したら出力
後処理

今回のプログラム


class Parser { 
  private boolean 非終端記号1(){
    if(トークン∈Director(非終端記号1,α)){
       return α の処理;
    }else if(文字∈Director(非終端記号1,β)){
       return β の処理;
    }...
    return false;
  }
  private boolean 非終端記号2(){
    トークンの列に応じて他の非終端記号を呼び出す;
    return true;
  }
...
}
/*
  α や β の処理中で文字を読み、終了判定も考慮される。
*/

class Rei {
  public static void main(String[] arg){
     if(開始記号()){
       System.out.println("受理");
     }else{
       System.out.println("拒否");
     }
  }
}

class Parser:
    def 非終端記号1(self):
        if トークン in Director(非終端記号1,α):
            return α の処理
        elif 文字 in Director(非終端記号1,β):
            return β の処理
        ...
        return False
    def 非終端記号2(self):
        トークンの列に応じて他の非終端記号を呼び出す
        return True
...

# α や β の処理中で文字を読み、終了判定も考慮される。

if 開始記号():
    print("受理")
else:
    print("拒否")

プログラムの基本的なテクニックとして、入力、出力、処理を分割すると言う 考え方があります。 長きに渡って使ってきた、「ループの冒頭で文字を読み、終了条件を判定し、 ループの中で出力作業を行う」というのは、確かにプログラミングの定石の一 つではあります。 しかし、今回のように複数の関数で共通のストリームから入力を読むという処 理を付加することができません。

以前、オートマトンも主プログラムのループ内で処理してましたが、これを改 め、呼び出すと字句が得られる関数を作ると便利です。 字句を取り出す関数を getword と呼ぶことにします。 これは Java の正規表現の group メソッドのような働きをするものです。 また、さらに今回は、「演算子」「数字」など複数の種類の字句を一つの getword で取り出す必要があります。 つまり、getword の返すものは字句の種類と、実際の字句を示す文字列である とします。

字句の定義はそれぞれの種類で別々にオートマトンで定義できれば、開始状態 からε遷移により分岐すれば一つにまとめられます。 これで最長一致により入力から字句を取り出すことを考えます。 このとき、主プログラム中の入力ループによる字句の取り出しとは違い、次の ふたつの問題があります。

  1. 字句の終端をどう判定するか?
  2. ファイルの終端の処理をどうするか?

字句の終端の判定は、基本的には字句に含まれない文字を読み込んだ時になり ます。 ここで、関数としては値を返して処理を主プログラムに戻すことになるのです が、問題は「字句に含まれない文字」の取扱いです。 この文字は次の字句に含まれる可能性があります。 したがって、関数が終了しても、次に関数が呼び出されたときに処理できるよ う、関数自体がオブジェクトのように記憶領域を持ちその文字から処理を開始 できるようにします。 なお、この考え方は、入力がキューである場合は、関数が記憶領域を持たなく ても、読み過ぎた入力を元に戻すという操作で実現できます。

次にファイルの終端の処理です。 ファイルの終端を検出した場合、入力処理は終了ですが、そこで字句の検出も 終了し、関数としては返すべき値があることも考えられます。 つまり、ファイルの終端に達しても、関数は字句を戻すことがありえます。 この場合も、関数がファイルの終端を記憶しながら、字句を返し、次の呼出で、 字句を返せないことを示せばよいです。

このように、字句解析では、最長一致をするために、字句に含まれない次の文 字を読んだ後、次の呼出でもう一度読み出す必要があります。

4-4. 構文解析木の作成

構文木のデータ構造

さて、構文解析のプログラムから構文木を作ることを考えます。 ここでは文法 G2' のプログラム(例4-5, 例4-6)で考えます。 例4-5において 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:
    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:
    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+" ")

演習4-6

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

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

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

始めに 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()

演習4-7

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

4-5. JavaCC のインストール

次回は 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'は、内部コマンドまたは外部コマンド、操作可能なプログラムまた はバッチファイルとして認識されていません。」と出てくればどこかで失敗し ています。

4-6. 付録

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


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:
    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>
東京電機大学工学部情報通信工学科