jacc について


jacc は BNF とそれに対する動作記述から、 Java 言語の構文解析系(パーサ)を自動生成するプログラムです。 jacc のソースファイル(通常 .jacc という拡張子をつける)は、 次のように書きます。 (これは通常の四則演算の式の文法です。 この例では単項の「-」はサポートしていないので、 -1+22*(-3) のような式は構文解析できません。 単項の「-」を扱う方法は yacc (bison) の入門書を調べて下さい。)


%{
/* import宣言はここに書く */
import static java.lang.Character.isDigit;
import java.io.IOException;
import java.io.PushbackInputStream;
%}

// 生成されるクラス名
%class MyParser   
// 次のトークンを返す式
%next yylex()
// 直前のトークンを表す式
%get  token 
// 属性値の型と式
%semantic double: yylval

%token NUMBER EOL  /* jacc cannot handle '\n' properly */
 /* 演算子の優先順位 */
%left  '+' '-'
%left  '*' '/'

%%
   /* 文法記述とそれに対する動作(還元時に実行されるプログラム) */
   /* 通常の BNF の → の代わりに : を書く。各 BNF は ; で区切る。 */
   /* 最初に start symbol を書く */
input  :   /* 空 */
       | input line EOL    {}
       ;

   /* $$ は左辺の属性値、$n は右辺の n 番目の文法要素の属性値を表す。 */
line   :               { System.exit(0); }
       |  expr         { System.out.printf("\t%g%n", $1); }
       ;

expr : expr '+' expr    { $$ = $1 + $3; }
     | expr '-' expr    { $$ = $1 - $3; }
     | expr '*' expr    { $$ = $1 * $3; }
     | expr '/' expr    { $$ = $1 / $3; }
     | '(' expr ')'   { $$ = $2; }
     | NUMBER         { $$ = $1; }
     ;

%%
  /* フィールドやメソッドの定義はここに書く */

  // エラーのときに呼ばれるメソッド
  private void yyerror(String msg) {
      System.out.println("ERROR: " + msg);
      System.exit(1);
  }

  private int token;
  private double yylval;

  // unread()(Cの ungetc())をするため
  private PushbackInputStream in = new PushbackInputStream(System.in);

  // scanf("%lf", ...) の代わりのメソッド
  double myParseDouble() throws IOException {
      double ret = 0;
      int c;

      while (isDigit(c=in.read())) {
          ret = 10 * ret + (c-'0');
      }
      if (c=='.') {
          c = in.read(); 
      } else {
          in.unread(c);
          return ret;
      }
      double x = 0.1;
      while (isDigit(c=in.read())) {
         ret += x * (c-'0');
         x *= 0.1;
      }
      in.unread(c);
      return ret;
  }

  // yylex(字句解析)メソッドを jflex を使わず定義している。yylex の戻り値は、トークン。    
  int yylex() {
      try {
          int c;  
          do {
              c = in.read();
          } while (c == ' ' || c == '\t' || c == '\r');


          if (isDigit (c) || c == '.') {
              in.unread(c);
              yylval = myParseDouble();
              /* トークンの属性値は yylval というフィールドに代入しておく。*/
              return token=NUMBER;
              /* NUMBER というトークンを返す。*/
          } else if (c == '\n') {
              return token=EOL; 
          } else if (c == -1) {
              return token=0; /* 終了を表す。*/
          }
          /* 上のどの条件にも合わなければ、文字をそのまま返す。*/
          return token=c;  
      } catch (IOException e) {
          return token=0;  
      }
  }

  public static void main(String[] args) {
      MyParser calc = new MyParser();
      calc.yylex();    // 最初のトークンを読んでおく
      calc.parse();    // parse the input
  }

説明

jacc の核心部分は BNF とそれに付随するアクションです。 アクションは還元時に実行されるプログラムのことです。アクションの中身は通常属性値(意味値)の計算です。 属性値は解析木の各節(枝分れの部分)に関連付けられる“値” です。

終端記号(トークン)は 1文字からなるトークンの場合は 通常、文字コードそのまま、2文字以上からなるトークンの場合は %token で宣言されたマクロです。

終端記号(トークン)の属性値は、 字句解析器から yylval という大域変数に代入されて受け渡されます。

例えば、入力が “(12+34)*56\n” という文字列の場合、 yylex() の戻り値とそのときの yylval の値は次のようになります。

1回目2回目3回目4回目5回目6回目7回目8回目
yylex()'('NUMBER'+' NUMBER')''*'NUMBER'\n'
yylval 12.0  34.0  56.0 

還元時(つまり、解析木の節を作るとき)に対応するアクションが実行されます。

非終端記号の属性値は、各部分木の属性値から計算されます。 $$ が還元される生成式の左辺の属性値、 $1, $2, … が 右辺の 1 番目、2 番目、… の文法要素の属性値を表します。 例えば、 $$ = $1 * $3 というアクションでは、 1 番目と 3 番目の部分木の属性値の積が、節の非終端記号の属性値となります。

生成

このファイル(ファイル名を MyParser.jacc とする)から Java ソースファイルを生成するには

  java -jar jacc.jar MyParser.jacc

というコマンドを実行します。 これで MyParser.java という名前の Java ソースファイルができます。
(jacc ソース中の %class オプションで指定したクラス名の Java ソースファイルが生成されます。)

この Java ソースファイル(MyParse.java)を コンパイルすると、クラスファイルが生成されます。

  javac MyParser.java

次のコマンドで実行できます。

  java MyParser
コンパイラのホームページ
Koji Kagawa