第 5 回コンパイラコンパイラ

本日の内容

5-1. 拡張バッカスナウア記法
5-2. JavaCC
5-3. 数式処理

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

前回はバッカスナウア記法により文脈自由文法を記述し、さらに、その文法を処理するパーサをプログラムで作成する方法に関して議論しました。今回はまず、よく使われるバッカスナウア記法の拡張表記を説明します。その後、 Java で文脈自由文法を処理するコンパイラコンパイラである JavaCC を紹介します。

5-1. 拡張バッカスナウア記法

基本的なバッカスナウア記法では右辺に終端記号、非終端記号の連接の表現しかありませんでした。拡張バッカスナウア記法は、連接以外に正規文法の記法である、選択と繰り返しを指定できるようにしたものです。選択は |(縦棒) で右辺の表現を列挙します。一方、繰り返しに関しては多くの表現方法があります。本質的には次に示す一部が可能であれば、他の表現を実現できますが、よく使われる表現を紹介します。

(表現)*: 表現の 0 回以上の繰り返し
{表現}: 表現の 0 回以上の繰り返し
(表現)?: 表現を 0 回または 1 回
[表現]: 表現は記述しても省略してもよい(0 回または 1 回)
(表現)+: 表現の 1 回以上の繰り返し

なお、このような表記を使うため、今後、文法表記で終端記号をルールに含めるときは "" (ダブルクォーテーションマーク)で囲むことにします。

例5-1

足し算の文法 G₁ は以下の通りでした。

\begin{matrix} 和 \to 和 "+" 数 \\ 和 \to 数 \end{matrix}

これを拡張バッカスナウア記法で記述すると次のようになります。

和 \to 和 "+" 数 | 数

例5-2

G₁は左再帰性がありました。これを除去するには、繰り返し構造を見抜いて、繰り返し構文で記述します。

和 \to 数 ("+" 数) *

さらに、式の最後に =(イコール)記号をつけた文法を示します。これを G₃ とします。

和 \to 数 ("+" 数) * "="

5-2. JavaCC

バッカス・ナウア記法を与えて、それを処理するプログラムを出力する処理系をコンパイラコンパイラと言います。 java 用のコンパイラコンパイラに JavaCCというクラスライブラリがあります。 JavaCC は構文解析も字句解析もできます。また、構文解析木を出力する JJTree というツールも付属してきます。

JavaCC の基本的な利用法は、「数」や「単語」など、文法の基礎となる要素をトークン(token) として登録し、次にそのトークン間のルールを文法として記述します。

使い方

JavaCC のソースファイルのファイル名には .jj という接尾語を付けます。 javacc ファイル名.jj とすると、複数の Java のソースファイルを出力します。ソースファイル内では、文法の記述と字句の定義の他に、様々な宣言を行う部分を持っています。

なお、 jj ファイルの正確な記述法は JavaCC [tm]: Grammar Files https://javacc.dev.java.net/doc/javaccgrm.html を参照してください。また、 JavaCC FAQ http://www.engr.mun.ca/~theo/JavaCC-FAQ/という文献も参考になります。

例5-3

以下は入力した文字数だけ Hello World を出力するプログラムです。


PARSER_BEGIN(Rei)
import java.io.*;
public class Rei {
    public static void main(String[] arg) throws ParseException {
	final Rei parser = new Rei(new InputStreamReader(System.in));
	parser.start();
    }
}
PARSER_END(Rei)
SKIP: {
  " "
 | "\n"
 | "\r"
}
TOKEN: { <MOJI : ~[] >}
private void start() :
{}
{
   (<MOJI> { System.out.println("Hello World.");})*
}

これを a.jj というファイル名で保存したら、 javacc a.jj, javac Rei.java で Rei.class が出来上がります。なお、ここで、「未チェック」関連の警告が出ますが、 JavaCC の生成した Java ファイルに関しては問題ありません。できたクラスファイル Rei.class に対して、 java Rei を行うと、入力した文字数だけ Hello World. が表示されます。 Ctrl-Z や Ctrl-D で終了します。

基本構造

jj ファイルの基本書式は次のとおりです。


PARSER_BEGIN(パーサクラス名)
宣言したパーサクラスの定義
PARSER_END(パーサクラス名)
生成ルール

例えば、パーサのクラス名が P であれば、次のようになります。


PARSER_BEGIN(P)
class P {
}
PARSER_END(P)
生成ルール

トークンの登録

生成ルールのうち、文字そのものからトークンを取り出すには正規文法を使用します。 TOKEN というキーワードを使用して、トークンの名前と正規文法を対にして定義します。このトークンの名前は後で説明するバッカス・ナウア記法の記述で使用します。

トークンの登録の記法は次のようにします。


TOKEN: {
   <トークン名1 : 正規表現1 >
 | <トークン名2 : 正規表現2 >
 | ...
}

なお、正規表現は通常の Java のものと若干異なります。

文字列は ""(ダブルクォーテーションマーク)で囲む。
文字クラスでは角カッコの中の要素はすべて ""(ダブルクォーテーションマーク)で囲み、, (カンマ)で区切る。また、文字の範囲に関しては""(ダブルクォーテーションマーク)で囲んだ文字同士を-(ハイフン)でつなぐ。
除外を表す文字クラスは文字クラスの角カッコの前に ~(チルダ) を付ける。特に任意の一文字は ~[] で表す。
繰り返しを表す *, +, ? などを指定する場合は丸カッコで括る。

例えば、自然数を NUM、名前を NAME という名称でトークンを取り出したい時は次のように指定します。


TOKEN: {
  <NUM : ["1"-"9"] (["0"-"9"])* >
 |<NAME : ["A"-"Z","a"-"z"] (["0"-"9","A"-"Z","a"-"z"])* >
}

なお、空白など文法では特に処理しない、読み飛ばすための表現のために、 TOKEN キーワードの他に SKIP というキーワードが用意されています。 SKIP でトークン名称は指定しないので、次のようになります。


SKIP: {
  " "
 | "\n"
 | "\r"
}

バッカスナウア記法の指定

次にバッカスナウア記法により文法を指定します。自力でパーサを作成したのと同様に、各非終端記号ごとにメソッドを作ります。しかし、定義の書式は下記のように異なります。


メソッドのシグネチャ :
{
メソッド内のアクションで共通で使用する変数などの宣言
}
{
   <トークン名1>あるいは非終端記号に対応するメソッドの呼び出しの列 
       { Java 構文によるアクション1 }
   <トークン名2>あるいは非終端記号に対応するメソッドの呼び出しの列 
       { Java 構文によるアクション2 }
 ...
}

なお、あらかじめ用意されている暗黙のトークンとして、ファイルの終わりを意味する <EOF> があります。また、拡張バッカスナウア記法をサポートしますので、選択を表す |(縦棒) や繰り返しの表現などもサポートします。なお、空列は　| {} で指定できますが、通常は [] で括るなど、別の表現で代替可能です。

例5-4

空白で区切られた名前の集まりを認識するパーサを作ります。この文法は次のようになります。

始→(名前)*

これを JavaCC で記述すると次のようになります。


// jj ファイル(Parser.java を生成)
options
{
  static = false;
}
PARSER_BEGIN(Parser)
class Parser {
}
PARSER_END(Parser)
TOKEN: {
    <NAME : ["A"-"Z","a"-"z"] (["A"-"Z","a"-"z","0"-"9"])*>
}
SKIP:{
    " "
| "\n"
| "\r"
}
public void start() :
{}
{
    (<NAME>)*
}

import java.io.*;
class Rei {
    public static void main(String[] arg) throws ParseException {
	final Parser parser = new Parser(new InputStreamReader(System.in));
	try{
	    parser.start();
	    System.out.println("Accept");
	}catch(Exception e){
	    System.out.println("Reject");
	}
    }
}

これを実行すると、名前と空白と改行だけからなる文字列を入力すると、 Accept を表示します。なお、それ以外の入力の場合、 Exception ではなく Lexical error が発行されるため、例外処理ではなくエラーでプログラムが止まります。

例5-5

次に、同じ文法において、名前が与えられる度に「x」を表示するようなプログラムを与えます。


// jj ファイル(Parser.java を生成)
options
{
  static = false;
}
PARSER_BEGIN(Parser)
class Parser {
}
PARSER_END(Parser)
TOKEN: {
    <NAME : ["A"-"Z","a"-"z"] (["A"-"Z","a"-"z","0"-"9"])*>
}
SKIP:{
    " "
| "\n"
| "\r"
}
public void start() :
{}
{
    (<NAME> {System.out.println("x");})*
}

このようにパターンの直後に {}(中括弧)を付け、中に Java のプログラムを書くことで、マッチしたときそのプログラムが実行できるようになります。また、この中括弧はパターンの一部になるので、この例のように繰り返しの表現などをさらに付加することができます。

例5-6

次に、同じ文法において、名前が与えられる度にその得られた名前を角括弧で[○○]のように表示するようなプログラムを与えます。


// jj ファイル(Parser.java を生成)
PARSER_BEGIN(Parser)
class Parser {
}
PARSER_END(Parser)
TOKEN: {
    <NAME : ["A"-"Z","a"-"z"] (["A"-"Z","a"-"z","0"-"9"])*>
}
SKIP:{
    " "
| "\n"
| "\r"
}
public void start() :
{
  Token name;
}
{
    (name=<NAME> {System.out.println("["+name.image+"]");})*
}

トークンを得るには Token 型の変数を用意します。メソッドのシグネチャの後の最初の {} (中括弧)の中には、そのメソッドが使用する変数などを宣言する場所になります。トークンは「変数名 = パターン」で得られます。 Token が含むフィールドは javacc を動かすと生成される Token.java を見れば厳密に分かります(javadoc 対応)が、下記のものがあります。

java.lang.String image: マッチした文字列を String 型で返す
next: 次のトークン

他に、マッチした位置に関する情報が取り出せます。

例5-7

名前と数、それぞれの出現回数を数え上げるプログラムを示します。


options {
   STATIC = false;
}
PARSER_BEGIN(Parser)
import java.io.*;
class Parser {
    private int name;
    private int num;
    public void init(){
	name=0;
	num=0;
    }
    public int getNumberOfNames(){
	return name;
    }
    public int getNumberOfNumbers(){
	return num;
    }
}
PARSER_END(Parser)
TOKEN : {
    <NAME : ["A"-"Z","a"-"z"](["A"-"Z","a"-"z","0"-"9"])*>
  | <NUM : ["1"-"9"](["0"-"9"])*>
  | <OTHER : (~[" ","\n","\r"])+>
}
SKIP : {
    " " | "\n" | "\r"
}
public void start() :
{}
{
    (<NAME> {name++;} | <NUM> {num++;} | <OTHER>)*
}

import java.io.*;
class Rei {
    public static void main(String[] arg) throws ParseException {
	final Parser parser = new Parser(new InputStreamReader(System.in));
	parser.init();
	parser.start();
	System.out.println(parser.getNumberOfNames());
	System.out.println(parser.getNumberOfNumbers());
    }
}

まず、 PARSER_BEGIN の前にオプションを与えることができます。今回は Parser クラスにデータを持たせて取り出したいために、 STATIC = false; というオプションを指定しています。通常 JavaCC では高速化のためにデフォルトではメソッドは static で作成するようです。それでは static メソッドからメンバ変数にアクセスできなくなるので、指定しました。

また、クラスの初期化を行う場合、コンストラクタは JavaCC が生成するため、変数の初期化などは別の初期化のメソッドを用意した方が簡単です。

TOKEN で定義している正規表現において、 OTHER は NAME も NUM も含んでいます。このような場合先に書いた方が優先となります。下記の定義では期待した動作にはなりません。


TOKEN : {
    <OTHER : (~[" ","\n","\r"])+>
  | <NAME : ["A"-"Z","a"-"z"](["A"-"Z","a"-"z","0"-"9"])*>
  | <NUM : ["1"-"9"](["0"-"9"])*>
}

本講義で取り上げないこと

JavaCC での日本語処理 (参考: http://www.ingrid.org/java/javacc/murata.html)
JavaCC では LL(1) 以上の複雑な文法も取り扱えること
JavaCC によるコンパイラの作成

5-3. 数式処理

本章では JavaCC による数式の処理を考えます。出力は木構造を返すこととします。

足し算

足し算の文法として下記の G₃ を JavaCC に与えます。

和 \to 数 ("+" 数) * "="

まず、木の関係のクラスは前回と同じ物を使います。但し、数を与える部分は一文字ではなく自然数としますので、その部分だけ変更します。以下に示します。

計算の木のクラスライブラリ


abstract class Node {
    abstract public void show();
    abstract public void rpn();
    abstract public void setOp(char c);
    abstract public void addLeft(Node n);
    abstract public void addRight(Node n);
}
class Num extends Node {
    public Num(int n){
	value = n;
    }
    private int value;
    @Override public void setOp(char c){}
    @Override public void addLeft(Node n){}
    @Override public void addRight(Node n){}
    @Override public void show(){
	System.out.print(value);
    }
    @Override public void rpn(){
	System.out.print(value);
    }
}
class Op extends Node{
    public static Node connectToLeft(Node n){
	final Op result = new Op();
	result.left = n;
	return result;
    }
    public Op(){}
    private char op;
    private Node left;
    private Node right;
    @Override public void setOp(char c){
	op = c;
    }
    @Override public void addLeft(Node n){
	left = n;
    }
    @Override public void addRight(Node n){
	right = n;
    }
    @Override public void show(){
	System.out.print("(");
	if(left!=null){
	    left.show();
	}
	System.out.print(op);
	if(right!=null){
	    right.show();
	}
	System.out.print(")");
    }
    @Override public void rpn(){
	if(left!=null){
	    left.rpn();
	}
	System.out.print(" ");
	if(right!=null){
	    right.rpn();
	}
	System.out.print(" ");
	System.out.print(op);
	System.out.print(" ");
    }
}

またテスト用の起動プログラムも Exception を替えただけで同様です。

起動プログラム


import java.io.*;
class Rei {
    public static void main(String[] arg) throws ParseException {
	final Reader r = new InputStreamReader(System.in);
	final Parser parser = new Parser(r);
	final Node tree = parser.start();
	if(tree !=null){
	    tree.show();
	    System.out.println();
	    tree.rpn();
	    System.out.println();
	}
    }
}

JavaCC のプログラムの作成

さて、次にこれを利用して JavaCC のプログラムを作ります。まずトークンは数と '+' 演算子と '=' 演算子になります。その定義は次のようにします。


TOKEN : {
    <NUM : ["1"-"9"](["0"-"9"])*>
  | <PLUSOP : "+">
  | <EQOP : "=">
}
SKIP : {
    " " | "\n" | "\r"
}

構文解釈では、最初の NUM で一つノードを作り、次の　PLUSOP と NUM の繰り返しで、Op.connectToLeft 静的メソッドで木をつないでいきます。最終的に EQOP を認識したら木構造を返します。そのため、 Node 型の変数 root を用意します。以上をまとめるとつぎのようになります。


options
{
  static = false;
}
PARSER_BEGIN(Parser)
import java.io.*;
class Parser {
}
PARSER_END(Parser)
TOKEN : {
    <NUM : ["1"-"9"](["0"-"9"])*>
 |  <PLUSOP : "+" > 
 |  <EQOP : "=" > 
}
SKIP : {
    " " | "\n" | "\r"
}
public Node start() :
{
    Token token;
    Node root;
}
{
    token=<NUM> {root = new Num(Integer.parseInt(token.image));}
    ( <PLUSOP> token=<NUM> {
                root = Op.connectToLeft(root);
		root.setOp('+');
		root.addRight(new Num(Integer.parseInt(token.image)));
       }
     )*
     <EQOP> { return root; }
}

積和

次に足し算と掛け算の混ざった式を考えましょう。計算は積項の和をとることで行いますので、 G₃ を書き換えた次の文法を G₄ とします。

和 \to 積 ("+" 積) * "="

積 \to 数 ("*" 数) *

なお、 jj ファイル以外は全て同じですので、ここでは jj ファイルのみを示します。

さて、ここで非終端記号が二つ現れます。そして、このプログラムの目標は式の構文解析木を得ることです。非終端記号の「積」を表すメソッドを prod とすると、この prod は構文解析木を返すことになります。そのため、 prod のシグネチャはつぎのようになります。


private Node prod() :

すると start 内の構文ルールにおいて、 prod から Node 型のオブジェクトを受けとることになります。そこで、前節では NUM というトークンから Token 型のオブジェクトを受け取ってましたが、これを全て Node に統一させた方が見通しが良くなると思います。そのため、 NUM というトークンから Node 型のオブジェクトを生成するような非終端記号を num として別に用意することにします。つまり、 num は次のようになります。


private Node num() :
{
  Token token;
}
{
  <NUM> { return new Node(Integer.parseInt(token.image));}
}

これを利用して作成したものを以下に示します。


options
{
  static = false;
}
PARSER_BEGIN(Parser)
import java.io.*;
class Parser {
}
PARSER_END(Parser)
TOKEN : {
    <NUM : ["1"-"9"](["0"-"9"])*>
 |  <PLUSOP : "+" > 
 |  <MULOP : "*" >
 |  <EQOP : "=" > 
}
SKIP : {
    " " | "\n" | "\r"
}
public Node start() :
{
    Node root, node;
}
{
    root=prod()
    ( <PLUSOP> node=prod() {
                root = Op.connectToLeft(root);
		root.setOp('+');
		root.addRight(node);
       }
     )* 
     <EQOP> { return root; }
}
private Node prod() :
{
	Node node, root;
}
{
    root=num() 
  ( <MULOP> node=num() {
                root = Op.connectToLeft(root);
		root.setOp('*');
		root.addRight(node);
     }
   )* { return root; }
}
private Node num() :
{
  Token token;
}
{
  token=<NUM> { return new Num(Integer.parseInt(token.image));}
}

カッコ付きの式

さらに括弧の処理を考えます。括弧の中にはどんな式も入ります。一方括弧はその中の値を計算したら、計算の対象となる値として数と同じように扱われます。今まで「数」という終端記号を使ってきましたが、ここで「値」という非終端記号を導入します。すると、値に関するルールは次のようになります。

値 \to 数 | "(" 和 ")"

和に = がついているとうまく行かないことに注意して作成したルールを G₅ とすると以下のようになります。

始 \to 和 "="

和 \to 積 ("+" 積) *

積 \to 値 ("*" 値) *

値 \to 数 | "(" 和 ")"

これの JavaCC ファイルは次のようになります。


options
{
  static = false;
}
PARSER_BEGIN(Parser)
import java.io.*;
class Parser {
}
PARSER_END(Parser)
TOKEN : {
    <NUM : ["1"-"9"](["0"-"9"])*>
 |  <PLUSOP : "+" > 
 |  <MULOP : "*" > 
 |  <OPEN : "(" > 
 |  <CLOSE : ")" >
 |  <EQOP : "=" > 
}
SKIP : {
    " " | "\n" | "\r"
}
public Node start() :
{
    Node root;
}
{
    root=sum()  
    <EQOP> { return root; }
}
public Node sum() :
{
    Node root, node;
}
{
    root=prod()  
    ( <PLUSOP> node=prod() {
                root = Op.connectToLeft(root);
		root.setOp('+');
		root.addRight(node);
       }
    )* { return root; }
}
private Node prod() :
{
	Node node, root;
}
{
    root=atai()
  ( <MULOP> node=atai() {
                root = Op.connectToLeft(root);
		root.setOp('*');
		root.addRight(node);
     }
   )* { return root; }
}
private Node atai() :
{ 
  Node node;
}
{
	node=num() { return node; }
   | <OPEN> node=sum() <CLOSE> {return node;}
}
private Node num() :
{
  Token token;
}
{
  token=<NUM> { return new Num(Integer.parseInt(token.image));}
}

演習5-1

引き算、割り算を付加した文法を示しなさい。
引き算、割り算も処理し、構文解析木を出力するプログラムを作りなさい。

演習5-2

構文解析木を受け取り、計算を行うプログラムを作成しなさい。

演習5-3

入力に自然数だけでなく、整数を許す数式計算プログラムを実現しなさい。

坂本直志 <sakamoto@c.dendai.ac.jp>
東京電機大学工学部情報通信工学科

第 5 回 コンパイラコンパイラ