Javaで字句解析器ジェネレータ

先日、Javaでパーサジェネレータの記事を書いた。その中で字句解析は、Java の StringTokenizer を使って自前で実装されていたが、StringTokenizer は単純に空白文字を区切り文字とするので、例えば 1 + 1 は処理できても 1+1 は処理できないという問題があった。

自前で書こうかと思っていたのだが気が変わって、JFlex を試しに使ってみた。 JFlex はCUP、BYACC/J、ANTLR と一緒に使えるよ、と書いてあり BYACC/J を使っていたのでちょうど良かった。

BYACC/J と一緒に使うサンプルコード calc.flex がおいてあって、以下のようなものだった

/* UserCode */
import java.io.Reader;

%%
/* Options and Macros */

/* Options */
%byaccj

/* The code between %{ and %} is copied verbatim into the generated source */
%{
  private Parser yyparser;

  public Yylex(Reader r, Parser yyparser) {
    this(r);
    this.yyparser = yyparser;
  }
%}

/* Macro Declarations */
NUM = [0-9]+(\.[0-9]+)?
NL  = \n | \r | \r\n

%%
/* Lexical Rules and Actions */

/* operators */
"+" | 
"-" | 
"*" | 
"/" | 
"^" | 
"(" | 
")"    { return (int) yycharat(0); }

/* newline */
{NL}   { return Parser.NL; }

/* float */
{NUM}  { yyparser.yylval = new ParserVal(Double.parseDouble(yytext()));
         return Parser.NUM; }

/* whitespace */
[ \t]+ { }

\b     { System.err.println("Sorry, backspace doesn't work"); }

/* error fallback */
[^]    { System.err.println("Error: unexpected character '"+yytext()+"'"); return -1; }

ルールにマッチした時に {} の Java コードが実行される。ParserVal や Parser は BYACC/J が生成するクラスで、同じ package に入れるなどして、Yylex クラス、Parser クラスで相互に参照できるようにしてコードを書く。

一緒に calc.y もおいてあって、以下のような内容になっていた。BYACC/J 単体の時はyylex()で自前で StringTokenizer で字句解析していたのが、Yylex クラスのオブジェクト lexer を使うようになっている。

%{
  import java.io.*;
%}

%token NL          /* newline  */
%token <dval> NUM  /* a number */

%type <dval> exp

%left '-' '+'
%left '*' '/'
%left NEG          /* negation--unary minus */
%right '^'         /* exponentiation        */

%%

input:   /* empty string */
       | input line
       ;

line:    NL      { if (interactive) System.out.print("Expression: "); }
       | exp NL  { System.out.println(" = " + $1); 
                   if (interactive) System.out.print("Expression: "); }
       ;

exp:     NUM                { $$ = $1; }
       | exp '+' exp        { $$ = $1 + $3; }
       | exp '-' exp        { $$ = $1 - $3; }
       | exp '*' exp        { $$ = $1 * $3; }
       | exp '/' exp        { $$ = $1 / $3; }
       | '-' exp  %prec NEG { $$ = -$2; }
       | exp '^' exp        { $$ = Math.pow($1, $3); }
       | '(' exp ')'        { $$ = $2; }
       ;

%%

private Yylex lexer;

private int yylex () {
  int yyl_return = -1;
  try {
    yylval = new ParserVal(0);
    yyl_return = lexer.yylex(); // next token
  }
  catch (IOException e) {
    System.err.println("IO error :"+e);
  }
  return yyl_return;
}

public void yyerror (String error) {
  System.err.println ("Error: " + error);
}

public void parse() {
  lexer = new Yylex(r, this);
  yyparse();
}

public static void main(String args[]) throws IOException {
  System.out.println("BYACC/Java with JFlex Calculator Demo");
  System.out.println("[Quit with CTRL-D]");
  System.out.print("Expression: ");

  Parser yyparser = new Parser(new InputStreamReader(System.in));
  yyparser.parse(); 
}

使い方

このコードを

jflex/bin/jflex calc.flex

として喰わせると、Yyflex.java が生成されるので、javac でコンパイルすれば良い。

javac Yyflex.java

.flex の構成

%% を区切り文字として以下の３つのセクションに別れる

User Code: 生成されるソースコードの先頭に差し込まれる import などを記述する
Options and Macros: JFlex のオプション、ユーザコード、マクロ定義を記述する
Lexical Rules: 語彙のルールと、マッチした場合のアクション(Javaコード)を記述す

Options and Macros: Options

Manual.html#ExampleOptions にいくつか書いてある。BYACC/J 用に出力したい場合は、%byaccj を書いておくようだ。

Options and Macros: ユーザコード

%{
  private Parser yyparser;

  public Yylex(Reader r, Parser yyparser) {
    this(r);
    this.yyparser = yyparser;
  }
%}

%{ と %} の間のコードは生成されるクラスコードに挿入される。この例ではメンバ yyparser とコンストラクタを追加して、BYACC/J で生成されるクラス Parser のインスタンスを受け取れるようにしている。

Options and Macros: Macro Declarations

NUM = [0-9]+(\.[0-9]+)?
NL  = \n | \r | \r\n

次の Lexical Rules に直接正規表現などを書いても良いが、ここでマクロを定義しておくこともできる。

Lexical Rules and Actions

語彙のルールと、マッチした場合のアクション (Javaコード) を記述する。

/* operators */
"+" | 
"-" | 
"*" | 
"/" | 
"^" | 
"(" | 
")"    { return (int) yycharat(0); }

/* newline */
{NL}   { return Parser.NL; }

/* float */
{NUM}  { yyparser.yylval = new ParserVal(Double.parseDouble(yytext()));
         return Parser.NUM; }

/* whitespace */
[ \t]+ { }

\b     { System.err.println("Sorry, backspace doesn't work"); }

/* error fallback */
[^]    { System.err.println("Error: unexpected character '"+yytext()+"'"); return -1; }

Yylex クラスの yylex() メソッドを呼ぶと、ルールに則って次のトークンを見つけ、そのトークンに対応するアクションの Java コードが実行される。calc.y の int yylex() の実装は次のようになっていて、

private Yylex lexer;

private int yylex () {
  int token = -1;
  try {
    yylval = new ParserVal(0);
    token = lexer.yylex(); // next token
  }
  catch (IOException e) {
    System.err.println("IO error :"+e);
  }
  return token;
}

Yylex クラスの yylex() メソッドを読んでその値を返すようにしているので、int yylex() のインターフェースにあわせて、yylval の値を設定し、int な token の値を return してあげればよい。

文字列リテラル

エスケープを許可してクォーテーションで囲む 'foo\'bar' のような文字列リテラルを扱えるようにしたくてどう書けば良いのか調べた。次のようにすれば良いようだ。

%%
%byaccj

%{
  StringBuffer string = new StringBuffer();

  private Parser yyparser;
  public Yylex(String str, Parser yyparser) {
    this(new java.io.StringReader(str));
    this.yyparser = yyparser;
  }
%}

%state STRING

StringChar = [^\r\n\'\\]+

%%

<YYINITIAL> {
  \' { yybegin(STRING); string.setLength(0); }
}

<STRING> {
  \' { yybegin(YYINITIAL); yyparser.yylval = new ParserVal(string.toString()); return Parser.STRING; }
  {StringChar}+ { string.append( yytext() ); }
  /* escape sequences */
  "\\b"  { string.append( '\b' ); }
  "\\t"  { string.append( '\t' ); }
  "\\n"  { string.append( '\n' ); }
  "\\f"  { string.append( '\f' ); }
  "\\r"  { string.append( '\r' ); }
  "\\\"" { string.append( '\"' ); }
  "\\'"  { string.append( '\'' ); }
  "\\\\" { string.append( '\\' ); }

  /* error cases */
  \\.    { throw new RuntimeException("yylex: Illegal escape sequence \""+yytext()+"\""); }
}

StringBuffer string を用意して、' が見つかった時点で初期化し、STRING state に遷移させる。

エスケープした文字列 \' を許容するために

"\\'" { string.append( '\'' ); }

のルールを明示的に追加している。

STRING state 内で再度 \' が見付かったら YYINITIAL state に戻し、StringBuffer から文字列を取り出す。

おわりに

調べたのは文字列リテラルの表現方法ぐらいで、他は直感的に書けた。これを使うだけで 1+1 のような空白文字のないパターンでも解析できるようになったので良い。また、曖昧な定義だったら warning を出して教えてくれるのが自分で書くよりも良いと感じた。

sonots:blog