パーサーの作り方

パーサーを作るおおまかな手順は次のようになる。

文法を決める。
内部のデータ構造(クラス)を決める。
パースするコードを書く。

文法を決める

miniJavaでは厳密な文法は用意されていない。そこでまず厳密な文法を定める。

文法を作るときには大きな枠組みの方から順に作っていくとよい。

miniJavaではプログラムはクラス宣言の集まりとして宣言される。そこでまず次のように文法を定める。

program ::= class_dec*

これは(拡張)BNFという記法(の一種)で、「programはclass_decの0個以上の繰り返し(*で表す)である」という意味になる。

続いてクラス宣言に対応するclass_decの文法を定める。

クラス宣言は次のように定められていた。

class 識別子 {
  クラス本体
}

そこでclass_decの文法は次のようにする。

class_dec ::= "class" identifier "{" class_body "}"

これは、「class_decとは、"class"という文字列、identifier、文字列"{"、class_body、文字列"}"を並べたものである」という意味になる。

ここでは空白は省略してある。空白を明示すれば文法は次のようになる。

class_dec ::= "class" space+ identifier space* "{" space* class_body space* "}"

ここで、spaceの定義は次のようなものとする。コメントも空白のうちに入れることにする。

space ::= " " | "\t" | "\n" | "\r" | "/*" ("*/"を含まない文字列) "*/" | "//" (改行を含まない文字列) ("\n" | "\r")

これは、「spaceとは、文字列" "、または文字列"\t"(タブ)、または文字列"\n"(UNIXでの改行)、または文字列"\r"(Macでの改行)、またはコメントである」という意味になる。

また、+は1回以上の繰り返しを表す。

識別子identifierは厳密に定めようとするとやや面倒なので、1文字目がJavaのCharacter.isJavaIdentifierStartがtrueを返し、2文字目以降がCharacter.isJavaIdentifierPartがtrueを返す文字列で、予約語でないもの、とする。

class_bodyは「フィールド宣言とメソッド宣言を任意個数書くことができる」とあるので、次のようにする。

class_body ::= (field_dec | method_dec)*

method_decは次のようにする。

method_dec ::= access_cont type "(" (type identifyer ("," type identifier)*)? ")" "{" method_body "}"

access_cont ::= "public" | "protected" | "private"

type ::= identifier

(...)?というのは、(...)が省略可能である、つまり、0個か1個である、という意味である。

その他の部分の文法も同様に作る。

作った文法を提出する義務はないので、自明な部分は省略してもよい。

内部データ構造(クラス)を決める。

内部データ構造は、プログラム中の各単語(if, class, 変数名など。トークンという)を表すデータ構造と、プログラムやクラス定義を表すデータ構造を作る。

トークンを表すデータ構造は、その種類、位置などの情報を持つ。また、数や変数名に対応するトークンは、数の値や変数名の情報を持つ必要がある。

詳細は資料の四則演算のパーサーを参考にすること。

クラス定義などを表すデータ構造は文法を元に、programやclass_decなどに対応するクラスを1つ1つ作るというパターンが多いが、文法と厳密に1対1に対応している必要はない。どのように作ってもよく、後の処理がしやすい形を選ぶ。

基本的には非終端子(::=の左側のこと。programやclass_decなど)ごとにクラスを作り、ほとんど似たようなクラスは統合し、1つのクラスが複雑になったら分割する、とするのがよい。継承を上手く使うとすっきりした定義を作ることができる。

たとえばクラス宣言を表すデータ構造は次のように作ることができる。フィールド宣言とメソッド宣言の順番は意味を持たないので、後での扱いやすさを考えてそれぞれ別のリストに入れることにする。

class ClassDec {
  public ClassDec(IdentifierToken name, List<MethodDec> methodDecs, List<FieldDec> fieldDecs) {
    this.name = name;
    this.methodDecs = methodDecs;
    this.fieldDecs = fieldDecs;
  }
  public IdentifierToken name;
  public List<MethodDec> methodDecs;
  public List<FieldDec> fieldDecs;
}

List<MethodDec>というのはJava1.5で導入されたGenericsという機構の構文であり、ここではMethodDecのListという意味である。

式の部分については資料の四則演算のパーサーを参考にするとよい。

パースするコードを書く

字句解析器を書く

字句解析器とは、入力文字列をトークンに分けるものである。また、コメントの除去も行うことが多い。

入力文字列をいきなり構文解析するのではなく、トークンに分けたりコメントを除去するなどの前処理を行った方がプログラムが書きやすくなる。

字句解析器であるLexerクラスは、nextメソッドを呼ぶと、次のトークンを返すことにする。

詳しくは資料の四則演算のパーサーを参考にすること。

基本的なパース方法

ここでは、パーサーの中でも簡単に実装できる再帰下降型パーサーを説明する。

基本的には非終端子(::=の左側のこと)1つに対して1つのメソッドを定義し、処理がまとめられるときにはまとめて、複雑すぎるときには分割するとよい。メソッドの中身はほとんど文法のままになるが、文法の都合上工夫が必要となる場合もある。

たとえばクラス宣言をパースするコードは次のようになる。

public static ClassDec parseClassDec(Lexer lexer) {
  IdentifierToken name;
  List<MethodDec> methodDecs = new ArrayList<MethodDec>();
  List<FieldDec> fieldDecs = new ArrayList<FieldDec>();

  Token currentToken = lexer.next();
  if (!currentToken.getType() != TokenType.IDENTIFIER
     || ((IdentifierToken)currentToken).getValue() != "class") {
    throw new RuntimeException("\"class\" expected but " + currentToken
                               + " at line " + currentToken.getLineNumber()
                               + ", column " + currentToken.getColumnNumber());
  }

  name = parseIdentifier(lexer);

  currentToken = lexer.next();

  if (currentToken.getType() != TokenType.OPEN_CURLY_BRACKET) { // '{'
    throw new RuntimeException("'{' expected but " + currentToken 
                               + " at line " + currentToken.getLineNumber()
                               + ", column " + currentToken.getColumnNumber());
  }

  currentToken = lexer.next();

  while (currentToken.getType() != TokenType.CLOSE_CURLY_BRACKET) { // '}'
    ClassMember member = parseClassMember(lexer);

    if (member instanceof MethodDec) {
      methodDecs.add((MethodDec)member);
    } else {
      fieldDecs.add((FieldDec)member);
    }

    currentToken = lexer.next();
  }

  return new ClassDec(name, methodDecs, fieldDecs);
}

MethodDecとFieldDecはClassMemberクラスのサブクラスとする。

また、ここではキーワード(ifやclassなど)のトークンも識別子のトークンと同じクラス(IdentifierToken)で表している。

基本的な流れは次のようになる。

文法で、文字列が指定されていたら("class"など)、その文字列が現在位置にあるか調べ、なかったら例外を投げる。
非終端子(identifierなど)があれば対応するメソッド(ここではparseIdentifier)を呼ぶ。
繰り返し(*)があったら、終わりを示す文字列が現れるまでwhileなどでループをする。
返り値を作り返す。

文法に「または(|)」がある場合はトークンを見て分岐を行う。

式のパース

式のパースは基本的には資料の四則演算のものを拡張すれば良い。ただし左結合の演算子と右結合の演算子があるので注意が必要である。

左結合の演算子の場合、次の疑似コードのようにパースする。

left = 優先順位が1つ高い演算子の式をパース;
while (現在位置のトークンが対象の演算子) {
  right = 優先順位が1つ高い演算子の式をパース;
  left = new 式を表すクラス(left, right);
}
return left;

右結合の演算子の場合、次の疑似コードのようにパースする。

left = 優先順位が1つ高い演算子の式をパース;
if (現在位置のトークンが対象の演算子) {
  right = 自分自身を再帰呼び出し;
  left = new 式を表すクラス(left, right);
}
return left;

発展課題で扱うキャスト演算子は特に注意が必要である。

例えば、(Foo)+(abc)という式があった場合、Fooという式とabcという式を足しているのか、(+(abc))という式をFoo型にキャストしているのか判別できない。

本物のJavaではキャスト演算子の後には単項の+や-は来ないと定義することにより、この問題を回避している。つまり、(Foo)+(abc)は常にFooという式とabcという式の和とみなされる。キャスト演算子として認識させたい場合には(Foo)(+(abc))と書く。miniJavaもこれに従う。