JavaCCによる構文記述

檜山正幸 (HIYAMA Masayuki)
Fri Mar 25 2005:start
Fri Mar 25 2005:memo

パーザー生成系JavaCCのソースコードを構文記述(文法)とみなして、その 書き方を説明する。

目次

1. はじめに

JavaCC(Java Compiler Compiler)(*注1)について調べたので、書き留めて おきます。ダウンロード元やセットアップ法は変わる可能性があるのでここに は書きませんので、検索して調べてください(*注2)。また、「JavaCCの使い 方」については、他のどなたかによる解説が(複数)あるでしょうから、ここ では、違った観点から説明します。

注1

僕は「ジャヴァ・シーシー」と呼んでいますが、「ジャック」といっている 人もいるようです。

注2

2005年3月の時点では、https://javacc.dev.java.net/ からダウンロード可 能。

その「違った観点」とは、JavaCCの構文記述の部分だけに注目して、これを 拡張BNFだとみなす立場です。JavaCCは実用的パーザー生成器なので、パーザー クラスのコードや、アクションと呼ばれる解析時動作を通常のJavaコードで記 述します。が、Javaコードの部分を取り除いた部分だけを見てみましょう、っ てことです。JavaCCの正統な(?)紹介はまったく意図してません。

例の多くは、JavaCCに付属しているJava言語の構文記述(をJavaCCで書い たもの)から拝借してます。予備知識としては、 普通の(例えば、grepやPerlで使える)正規表現とBNF(Backus Naur Form) を知っていることを仮定します。

(なぜか、「です・ます」ではじめてしまったのだが、ここから後は「だ・ である」。)

2. 実験の準備

後の説明で出てくる構文記述(字句規則と構文規則)を実際に確認するため に、簡単なソースコードひな形を示しておく。このひな形のコメントのところ を、実際の構文記述で置き換える。

/* Parser.jj */

PARSER_BEGIN(Parser)
public class Parser {
  public static void main(String[] args) throws ParseException {
    Parser parser = new Parser(System.in);
    parser.Start();
  }
}
PARSER_END(Parser)

TOKEN :
{
   // ここに最初の字句規則
 | // ここに2番目のの字句規則
 | // ここに3番目のの字句規則
 | // ...
}

void Start() : {} {
  // ここに主要な構文規則
  <EOF>
}

// ここから構文規則
// ...

次のコマンドラインを実行すれば、JavaCCによるパーザー(Javaプログラム) の生成、Javaプログラムのコンパイル、そしてその実行が行える。

 javacc Parser.jj
 javac *.java
 java Parser

例えば次は、第3節に出てくるSINGLE_LINE_COMMENT(1行コメント)について 確認するためのJavaCCソースコードである。

/* Parser.jj */

PARSER_BEGIN(Parser)
public class Parser {
  public static void main(String[] args) throws ParseException {
    Parser parser = new Parser(System.in);
    parser.Start();
  }
}
PARSER_END(Parser)

TOKEN :
{
   < #END_OF_LINE : "\n" | "\r" | "\r\n" >
 | < SINGLE_LINE_COMMENT : "//" (~["\n", "\r"])* <END_OF_LINE> >
}

void Start() : {} {
  <SINGLE_LINE_COMMENT>
  <EOF>
}

javacc、javacによりできあがったプログラムを実行すると、標準入力からの 入力を解析する。構文エラーがあると、ただちに例外が出て停止する。入力が 構文的に正しければ、何も起こらずに正常終了する。

何も起こらないではさびしい、というのであれば、次のようにデバッグ・オ プションを付け加えると、デバッグ情報が出力される。

/* Parser.jj */

/* 追加 */
options {
  DEBUG_PARSER = true;
}

PARSER_BEGIN(Parser)
public class Parser {
  public static void main(String[] args) throws ParseException {
    Parser parser = new Parser(System.in);
    parser.enable_tracing(); // 追加
    parser.Start();
  }
}
PARSER_END(Parser)

/* 以下は同じ */

3. 字句規則と構文規則

第1節で触れたように、JavaCCのソースコードには、Javaで書かれた実行コー ドを挿入できるが、それを無視すれば、「JavaCCのソースコードは構文記述で ある」といってよい。

構文記述(文法)は、生成規則の集まりだが、JavaCCの場合、生成規則を字 句規則と構文規則の2種に分けて考えたほうがよい。‘字句規則’は、適切な 文字の塊を定義する。適切な文字の塊を‘トークン’と呼ぶ。だから言葉を換 えれば、字句規則はトークンを定義する規則である。字句規則で定義されたトー クンの列が、文などの構文要素となる。どんなトークン列が構文要素となるか を規定するのが‘構文規則’である。

字句規則の簡単な例を見てみよう。

 DECIMAL_LITERAL : ["1"-"9"] (["0"-"9"])*

これは、十進整数(の構文)を定義するものである。コロン「:」により、左 辺と右辺に区切られる。左辺は定義すべきトークンの名前、右辺には正規表現 を書く。正規表現の書き方は常識的だが、文字や文字列そのものを書くときは、 常に二重引用符が必要で、["1"-"9"] を [1-9]と は書けない(ちょっとめん どくさい)。それと、スコープを示す丸括弧は省略できないことがある。例え ば、(["0"-"9"])* を ["0"-"9"]* とは書けない(*注3)

注3

「(」と「)*」の組で1つの演算子記号を構成していると考えるとよい。

今度は、構文規則の例を見てみよう。

void VariableDeclarator() : {}{
  VariableDeclaratorId() ( "=" VariableInitilalizer() )?
}

void VariableDeclaratorId() : {}{
  <IDENTIFIER> ( "[" "]" )*
}

この例のVariableDeclaratorは、“Javaの変数宣言の一部”を定義したもの である。例えば、 「private int i, j[], k=0;」と書いたときの、「j」、 「j[]」、「k=0」の部分がVariableDeclaratorである。

構文規則も、基本的には正規表現を許したBNF(拡張BNF)なのだが、見た感じ はメソッド定義にも似ている。構文規則がJavaCCによって実際にメソッドに変 換される。その事情から、メソッド的な記法を採用している。

コロンが左辺と右辺を分けるのは字句規則と同じである。だが、字句規則と は違い、左辺に出現する名前も右辺に出現する名前も、メソッド風に直後に括 弧が必要である。右辺でトークンを参照したいときは、トークン名を「<」と 「>」で囲った形を使う。

4. 字句規則の書き方

前節で簡単に触れたように、字句規則は「トークン名 : 正規表現」の形だ。 ただし、この規則全体を「<」と「>」で囲むことになっている。さらに、その 外側を「TOKEN: {」と「}」で囲む必要がある(*注4)。よって、前節の例をちゃんと 書けば次のようになる。

TOKEN: {< DECIMAL_LITERAL : ["1"-"9"] (["0"-"9"])* >}

注4

「TOKEN:」でひとつの予約語ではない。予約語TOKENとその後に続くコロンで ある。よって、TOKENとコロンにあいだに空白類が入ってもよい。

1つの「TOKEN:{}」のなかに複数の字句規則を書きたいなら、「|」で区切る 必要がある。例えば次のようになる。

TOKEN: {
   < DECIMAL_LITERAL : ["1"-"9"] (["0"-"9"])* >
 | < OCTAL_LITERAL : "0" (["0"-"7"])* >
}

だがこの記事の例では、外側の「TOKEN:{}」は省略する。

文字や文字列をそのまま書きたいときは二重引用符で囲んだストリング形式 を使う。ストリング内では、Javaと同じエスケープ記法が使える。例えば、空 白の定義は次のようになる。

< WHITEL_SPACE : " " | "\t" | "\r" | "\n" >

1文字と文字列の区別は特にない(どちらも二重引用符でくくる)。次は予約 語の定義である。

< CLASS : "class" >

もう少し複雑な例を出す。

< SINGLE_LINE_COMMENT : "//" (~["\n", "\r"])* ("\n" | "\r" | "\r\n") >

これは、Javaの1行コメントを定義している。コメントの始まりは"//" であ る。その後に、LF、CR以外の文字達~["\n", "\r"]がいくつか続く。~[ ... ] は補集合文字クラスで、ブラケット内に列挙された文字以外の任意の文字 を表す(*注5)。1行コメントの終わりは改行だが、改行として、LFだけ、CRだ け、CR+LFが列挙されている。

注5

~[] と書くと、空集合の補集合になるので、結局、すべての文字を意味する。

他の字句規則で定義されたトークンを、右辺の正規表現内で参照したいとき は、トークン名を「<」と「>」で囲めばよい。上のSINGLE_LINE_COMMENTの例で、 改行を別なトークンとして定義しておけば見やすくなる。

   < END_OF_LINE : "\n" | "\r" | "\r\n" >
 | < SINGLE_LINE_COMMENT : "//" (~["\n", "\r"])* <END_OF_LINE> >

右辺に出現するトークン参照を「<」「>」で囲むのを忘れて、裸の名前を書 いてしまうと(僕は何度もしくじった)、記述エラーになるので注意。

上のEND_OF_LINEのように、他の字句規則を見やすく記述するために導入した トークンは、構文規則では使わないことが多い。プライベート(局所的)なトー クンを定義するには、トークン名の前に「#」を置くとよい(「#」と名前のあ いだに空白を入れてもよい)。つまり、次のように記述する。

   < #END_OF_LINE : "\n" | "\r" | "\r\n" >
 | < SINGLE_LINE_COMMENT : "//" (~["\n", "\r"])* <END_OF_LINE> >

「#」が付いた字句規則で定義されたトークンは、字句規則内では参照 できるが、構文規則からの参照はできない。

前もって定義された予約トークンとして<EOF>がある。ファイルの終わりに到 達すると、<EOF>が字句解析器(*注6)から返される。

注6

通常、レクサー(lexer)とかスキャナ(scanner)と呼ばれるが、JavaCCで はトークン・マネージャと呼んでいる。

正規表現として使えるリテラルとメタ文字(構文的な演算子)について下の 表にまとめる。

TABLE: 字句規則における正規表現
表記法 意味 注記
"..." 引用符内に書かれた文字(列)と一致Javaの文字列と同じ記法
または 演算子としての優先順位はもっとも低い
[...] 文字クラス 文字クラス内でのみ使えるメタ文字がある
~[...] 補集合文字クラス 内部は文字クラスと同じ構文
- 範囲 文字クラス内でのみ(例:"a"-"z")
, 列挙 文字クラス内でのみ(例:"a", "b")
(...)? 省略可能 丸括弧が常に必要
(...)* 任意回繰り返し 丸括弧が常に必要
(...)+ 1回以上の繰り返し 丸括弧が常に必要

5. 構文規則の書き方

通常のBNFにおいて、「foo ::= 正規表現」と書かれる生成規則は、JavaCCで は次の形になる。

void foo() : {} {
  JavaCCの正規表現
}

「void foo()」はメソッド定義に似ているが、実際、「int foo(String arg)」 のような定義もできる。だが、この記事ではその点を無視して、「void」も 名前の後に付ける「()」も単なるオマジナイとして扱う。同じ理由で、コロン の直後の「{}」もオマジナイ。

これからの説明のために、構文規則で定義されるトークン列を‘構文要素’ と呼ぶことにする。この言葉を使えば、JavaCCの構文規則のパターンは次のよ うになる。

void 構文規則名() : {} {
  JavaCCの正規表現
}

字句規則の代わりに構文規則を使うこともできる。つまり、字句規則で書け ること(の一部)は、構文規則でも書くことができる(それがいいかどうかは ともかく)。次はその例である。

void BooleanLiteral() : {} {
 "true" | "false"
}

ここで出現したリテラル"true"と"false"は、JavaCCが自動的にトークン定義 してくれる。ただし、トークン名は付かないので無名のトークンとなる。もし、 "true"と"false"を字句規則で定義してあれば、そのトークン名を参照したの とまったく同じ効果が得られる。

例えば、次の字句規則があるなら、"true"と生で書いても、<TRUE>とトーク ン参照を書いても、生成されるパーザーコードは同じである。

   < TRUE : "true" >
 | < FALSE : "false" >

さて次は、while文を定義する構文規則である。

void WhileStatement() : {}{
  "while" "(" Expression() ")" Statement()
}

この例からも推測できるだろうが、構文規則の右辺(定義本体部分)で使え る正規表現では、次のものが基本となる。

  1. ストリング形式で書かれた文字列:二重引用符で囲まれた文字列。例: "while"
  2. トークン参照: 字句規則で定義された(*注7)トークン名を「<」と「>」 で囲ったもの。例:<IDENTIFIER>
  3. 構文要素名: 他の構文規則で定義された構文要素の名前。メソッド風に、 名前の後に括弧「()」が必要である。例:Expression()

構文規則で使えるメタ文字は、字句規則と基本的に同じであり、「|」、 「()?」、「()*」、「()+」である。構文規則には文字クラスがないので、ブ ラケット「[]」を「()?」と同じ意味で使える。