JFlex User's Manual

Version 1.1.2, October 12, 1998
Gerwin Klein

日本語訳(Translated by)担当
中島 祐一(Yuichi NAKAJIMA)1, 2, 6, 7
池田 幸雄(Yukio IKEDA)3
山崎 勝彦(Katsuhiko YAMAZAKI)4.1, 4.2
大宅 宏二(Koji OOYA)4.3

目次


1 イントロダクション

JFlexはJavaで書かれたJava用の字句解析ルーチン生成系(lexical analyzer generator)である。そのJFlexは、Princeton UniversityのElliot Berkによって開発された非常に有用なツールJLexの書き直しでもある。Vern Paxonが彼のC/C++ツールflex [5]について述べているように、JFlexはそれでもいかなるコードも共有していない。

JFlexの主要な設計上の目標は以下の通りである:

version 1.1 の新機能

JFlexのversion 1.1は(version 1.0に)次の新機能を追加した:

このマニュアルについて

このマニュアルは文書を与えるが、ツールJFlexの完全な記述ではない。それは、あなたが字句解析(lexical analysis)の問題に熟知していることを仮定している。[2], [1], [11] はこの話題について良いイントロダクションを提供する。

このマニュアルの次のセクションは、JFlexの[インストールの方法]を記述する。もしあなたがJLexを使って作業をしたことがないか、JLexとJFlexのスキャナの仕様書を比較したいのであれば、セクション3 [JFlexを使った作業 ― 例] を読むべきである。全てのオプションと完全な仕様書の構文は、セクション [レキサの仕様書] に示される。もしあなたが性能の考察やJLex/JFlexの速度の比較に関心があるなら、[性能について二言三言] はまさに当を得たものとなるであろう。それらの古いJLexの仕様書を使おうとする人々は、JFlexでは修正されたポータブルではない、または標準的ではない、JLexのふるまいについて起こり得る問題を避けるために、[JLexからの移植] を調べるべきである。[バグ] は現在知られているバグの一覧を与える。マニュアルはJFlexを書くために使われた[参考文献]に続き、[権利とライセンス] についての記述で結論づける。


2 JFlexのインストール

JFlexをインストールするには、以下の3つのステップに従ってください:
  1. あなたがダウンロードしたファイルを、JFlexをインストールしたいディレクトリに(Unixなら tar/unzip を、W95/98ならWinZipを使って)展開します。
    たとえば C:\ に展開したなら、以下のようなディレクトリ構造が作られているはずです(カッコ内はそのディレクトリの内容を表します):
      C:\JFlex\                          
            +--bin\                     (スタートスクリプト) 
            +--doc\                     (FAQとこのマニュアル)
            +--examples\ 
                     +--java\           (完全なJava 1.1用のレキサの仕様書) 
                     +--simple\         (簡単なスキャナ)
                     +--standalone\     (簡単なスタンドアロンスキャナ) 
            +--lib\                     (コンパイル済みのクラス) 
            +--src\ 
                +--JFlex\               (JFlexのソースコード) 
                +--JFlex\gui            (JFlexのUIクラスのソースコード)
                +--java_cup\runtime\    (java_cup.runtimeクラスのソースコード) 
    
  2. Unixなら bin/jflex を、W95/98なら bin\jflex.bat を編集します(上の例では、C:\JFlex\bin\jflex.bat になります)。そして、
  3.  
  4. あなたのパスに、JFlexの bin/ ディレクトリを追加します。 (そのディレクトリにはスタートスクリプトが入っています。例では C:\JFlex\bin です)。
これで、以下のコマンドを使ってJFlexを動作させることができます:
    jflex <inputfile>
代わりに、CLASSPATH にファイル lib\JFlex.zip を含めることで、ステップ2と3をとばすことも可能です。
そのときに、JFlexを動かすには以下のようにします: 入力ファイル(inputfile)はどちらの場合も省略可能です。もしコマンドラインでファイル名を入れなければ、JFlexはウィンドウを開いてファイル名を尋ねます。


3 JFlexの使用法 ― 例

JFlexを使ったレキサの仕様書がどのようなものを表すのかを例示するために、この節ではJava言語に対するJFlexの仕様書の一部を取り扱う。この例では、Javaプログラムの字句構造全体は記述していないが、小さく単純化された部分だけは記述してある(キーワード、オペレータ、コメントおよび2種類のリテラル)。それはまた、LALRパーザジェネレータ CUP [8] とインタフェースする方法も示しており、それゆえに、CUPの文法の終端トークンに対する整定数が宣言される(CUPによって生成された)sym クラスを使用する。JFlexには "examples" ディレクトリが存在する。そこには小さなstandaloneスキャナーがあり、それはあなたに実例を与えるためにCUPのような他のツールを必要としない。また、"examples" ディレクトリには、C. Scott AnanianCUP [8] のwebsiteから得たJava1.1用ののCUPパーザの仕様書とともに、Javaプログラムの字句構造の完全なJFlexの仕様書が含まれている。(JFlexスキャナとインタフェースを行うために修正された)。両方の仕様書は、Java言語の仕様書 [7] と厳密に接続されている。


/* JFlex example: part of Java 1.0/1.1 language lexer specification */
import java_cup.runtime.*;

%%
%class Lexer
%unicode
%cup
%line
%column
%{
  StringBuffer string = new StringBuffer();

  private Symbol symbol(int type) {
    return new Symbol(type, yyline, yycolumn);
  }
  private Symbol symbol(int type, Object value) {
    return new Symbol(type, yyline, yycolumn, value);
  }
%}

LineTerminator = \r|\n|\r\n
InputCharacter = [^\r\n]
WhiteSpace = {LineTerminator} | [ \t\f]

/* comments */
Comment = {TraditionalComment}|{EndOfLineComment}|{DocumentationComment}

TraditionalComment = "/*" [^*] {CommentContent} "*"+ "/"
EndOfLineComment = "//" {InputCharacter}* {LineTerminator}
DocumentationComment = "/**" {CommentContent} "*"+ "/"

CommentContent = ( [^*] | \*+ [^/*] )*

Identifier = [:jletter:] [:jletterdigit:]*

DecIntegerLiteral = 0 | [1-9][0-9]*

%state STRING

%%

/* keywords */
<YYINITIAL> "abstract"           { return symbol(sym.ABSTRACT); }
<YYINITIAL> "boolean"            { return symbol(sym.BOOLEAN); }
<YYINITIAL> "break"              { return symbol(sym.BREAK); }
 
<YYINITIAL> {
  /* identifiers */ 
  {Identifier}                   { return symbol(sym.IDENTIFIER); }
 
  /* literals */
  {DecIntegerLiteral}            { return symbol(sym.INTEGER_LITERAL); }
  \"                             { string.setLength(0); yybegin(STRING); }

  /* operators */
  "="                            { return symbol(sym.EQ); }
  "=="                           { return symbol(sym.EQEQ); }
  "+"                            { return symbol(sym.PLUS); }

  /* comments */
  {Comment}                      { /* ignore */ }
 
  /* whitespace */
  {WhiteSpace}                   { /* ignore */ }
}

<STRING> {
  \"                             { yybegin(YYINITIAL); return symbol(sym.STRINGLITERAL, string.toString()); }
  [^\n\r\"\\]+                   { string.append( yytext() ); }
  \\t                            { string.append('\t'); }
  \\n                            { string.append('\n'); }
  \\r                            { string.append('\r'); }
  \\\"                           { string.append('\"'); }
  \\\\                           { string.append('\\'); }
}


/* error fallback */
.|\n                             { throw new Error("Illegal character <"+yytext()+">"); }

JLexと同様に、仕様書は %% で分割された3つの部分から成り立っている:  ユーザコードオプションおよび宣言字句規則

ユーザコード

最初の節 "ユーザコード" を見てみると、'%%' で始まる最初の行からのtextは、生成されたレキサの先頭にそのままコピーされている。packageimport のステートメントのほかに、ここですべきことは通常ほとんどない。

オプションと宣言

2つ目の節 "オプションと宣言" は、もっと興味深い。それは、オプションの集合、生成されたスキャナクラスに含まれるコード、字句状態、マクロ宣言から成り立っている。JFlexの各オプションは、仕様書の行頭になければならず、'%' で始まる。この例では次のオプションが使われている: '%{' ... '%}' に含まれるコードは、生成されたレキサのクラスのソースにそのままコピーされる。この方法で、スキャナアクションの中で使われるメンバ変数や関数を宣言できる。私たちの例では、文字列リテラルの一部を格納する StringBuffer "string" と、現在のトークンの位置情報で java_cup.runtime.Symbol オブジェクトを作成する2つのヘルパー関数(helper function) "symbol" を宣言している。(パーザジェネレータCUPとインターフェイスを行う方法については [JFlex and CUP] を参照)。JFlexのオプションとして、'%{' と '%}' は、行頭になければならない。

仕様書はマクロ宣言に続く。マクロは、レキサの仕様書を理解しやすくするための、正規表現の省略形である。マクロの定義は、マクロの識別子とそれに続く '='、その識別子を表す正規表現、によって成り立っている。この正規表現は、それ自身マクロの使用を含んでいてもよい。これは仕様書スタイルのような文法を可能にするが、マクロはただの省略形であって非終端ではない ― 繰り返しや相互再帰はできない。マクロ定義の中のサイクルは、JFlexによる生成時に発見され報告される。

ここで、例のマクロをいくつか詳細にする:

レキサの仕様書の2つ目のセクションの最後の部分は、字句状態の宣言である:"%state STRING" は、仕様書の "字句規則" 部で使用できる字句状態 "STRING" を宣言する。状態の宣言は、"%state" で始まり、続いてスペースやコンマで区切られた状態の識別子のリストからなる行である。"%state" で始まる1つ以上の行を書くことができる。

字句規則

JFlexの仕様書の "字句規則" セクションは、正規表現とスキャナが関連づけられた正規表現にマッチするときに実行されるアクション(Javaのコード)を含んでいる。スキャナがその入力を読むと、すべての正規表現と接触を保ち、最長のマッチを持つ表現のアクションがアクティブになる。上の私たちの仕様書では、例として入力 "breaker" を使うと、キーワード "break" とそれに続く識別子 "er" ではなく、Identifier に対する正規表現にマッチする。なぜならば、規則 {Identifier} は、仕様書の中のいかなる他の規則よりも、一度にこの入力のより長い部分とマッチするからである(すなわち、その規則はその入力の全体とマッチする)。もし、2つの正規表現両方が、ある特定の入力の最長一致(longest match)を持っているなら、スキャナは仕様書の最初に現れる表現のアクションを選択する。この方法で、私たちは入力 "break" について、識別子 "break" ではなく、キーワード "break" を得ることができる。

正規表現のマッチに加えて、仕様書を定式化(formulate)するために字句状態を使うことができる。字句状態は開始条件(start condition)のような働きをする。もし、スキャナが字句状態 STRING にあるなら、開始条件 <STRING> を前に持つ表現のみがマッチされる。ある正規表現の開始条件は、1つ以上の字句状態を含むことができる。字句状態 "YYINITIAL" は前もって定義されており、レキサがスキャニングを開始するときの状態でもある。もしある正規表現が開始条件を持たないのであれば、それは すべての 字句状態にマッチする。

同じ開始条件を持った表現の一群を持つことがよくあるので、JFlexではUnixツールの flex と同様の省略形が可能である:
<STRING> {
  expr1   { action1 }
  expr2   { action2 }
}
は、expr1expr2 の両方が開始条件 <STRING> を持つことを意味する。

私たちの例の最初の3つの規則は、開始条件 <YYINITIAL> を前に持つ正規表現の構文の実例である。

<YYINITIAL> "abstract"           { return symbol(sym.ABSTRACT); }
は、スキャナがその開始条件 "YYINITIAL" にあるときのみ、入力 "abstract" にマッチする。文字列 "abstract" がマッチされたとき、スキャナ関数はCUPのシンボル sym.ABSTRACT を返す。もしあるアクションが値を返さないのであれば、スキャニングの処理は、アクション実行後、ただちに再開される。


<YYINITIAL> {
...
}
に囲まれた規則は、省略構文の実例であり、状態 YYINITIAL においてのみマッチされる。

これらの規則の、特に興味深いのは
  \"                             { string.setLength(0); yybegin(STRING); }
である。

もし、スキャナが状態 YYINITIAL でダブルクォーテーションにマッチするならば、私たちは文字列リテラルの開始を認識する。それゆえに、その文字列リテラルの内容を保持する StringBuffer をクリアし、字句状態 STRING に切り替えることを yybegin(STRING) を使ってスキャナに知らせる。パーザに値を返していないため、スキャナーはすぐに処理を続行する。

字句状態 STRING では、マッチした入力を参照するためのもう一つの規則を例示している:
  [^\n\r\"\\]+                   { string.append( yytext() ); }

表現 [^\n\r\"\\]+ は、次のバックスラッシュ(\n のようなエスケープシーケンスを意味する)、ダブルクォーテーション(文字列の終りを意味する)、もしくは行の終端(line terminator)(文字列リテラルの中で起こってはいけない)までの入力ですべての文字にマッチする。入力のマッチされた部分は、yytext() を使って参照され、解析された文字列リテラルの内容に追加される。

例の仕様書の最後の字句規則は、エラーフォールバック(error fallback)として使われる。それは、もう一つの規則でマッチされなかったすべての状態ですべての規則にマッチする。それは、最も低い優先順位を持ち(最後の規則であるため)、ただ1文字だけとマッチするため、他のいかなる規則とも衝突しない。
 

How to get it going:


4 レキサの仕様書

上で示したように、JFlexの字句仕様ファイルは %% で始まる行によって分割される3つの部分からなる:

ユーザコード
%%
オプションと宣言
%%
字句規則

仕様書のすべての部分において、/* コメント文 */ という形式のコメントと、// で始まるJava形式の行末コメントが考慮されている。JFlexのコメントは入れ子になる ― そのため、/* の数と */ の数はつり合わせるべきである。

ユーザコード

第1の部分はユーザコードであり、それはスキャナクラスが宣言される前に、生成されたレキサのソースファイルの先頭にそのままコピーされる。上の例で示したように、これは package 宣言と import ステートメントを置くための場所である。可能ではあるが、このセクションに(トークンクラスのような)自身のヘルパークラスを置くことは、好ましいJavaのプログラミングスタイルだとは思えない。それらのクラスは、その代わりにそれらヘルパークラス自身の .java ファイルから得るべきである。

オプションと宣言

レキサの仕様書の第2の部分は、あなたの生成されたレキサをカスタマイズするためのオプションと(JFlexの命令とJavaのコードをレキサの別々の部分に含むために)、レキサの仕様書ファイルの第3のセクション [字句規則] で使うための字句状態マクロ定義の宣言を含んでいる。
 
JFlexの各命令は、行頭に置かれ、文字 '%' で始まっていなければならない。1つ以上のパラメータを持った命令は、次のように記述される: は、%class で行を開始し、1つのスペースが続き、生成されるスキャナのクラスの名前が続くことを意味している(ダブルクォーテーション内は改行をしてはならない。仕様書 [例] を参照)。
 

クラスオプションとユーザクラスコード

これらのオプションは、生成されたスキャナクラスの名前、コンストラクタ、 関係する部分に注目する。

スキャニングメソッド

このセクションでは、スキャニングメソッドをカスタマイズする方法を示す。あなたはそのメソッドの名前と戻り値型を定義することができ、仕様書のアクションの1つで投げられる例外の宣言が可能である。もし戻り値型が記述されなければ、スキャニングメソッドはクラス Yytoken の値を返すように宣言されるだろう。

ファイルの終端(EOF)

スキャニングメソッドがEOFに到達したときに返すデフォルト値は、常に存在する。あなたは、しかしながら、EOFに到達したときに返すための特定の値と、実行されるべき特定のコードの断片を定義することができる。

EOFのデフォルト値は、スキャニングメソッドの戻り値型に依存する:

EOFで実行するユーザの値とコードは、これらの命令を使って定義することができる:

スタンドアロンスキャナ

CUPとの適合性

もしあなたが、あなたの生成されたスキャナとCUPのインターフェイスを実現する方法に興味があるのなら、セクション [協調動作:JFlexとCUP] も読むべきである。

コードの生成

JFlexがどのような種類の字句解析ルーチンを作成するのかを、次のオプションが定義する。
 

文字集合

行数、文字数、桁数の計測

もはや使われないJLexのオプション

状態の宣言

状態の宣言は、次の形式(訳註:fromはformの誤植)を持っている: それぞれ %state で始まる、1行以上の状態の宣言が存在していてもよい。状態の識別子は、文字の後に一連の文字、数字、下線が続く。状態の識別子は、空白かカンマによって区切られる。

連続した

は、{STATE1, STATE3, XYZ, STATE_10, ABC, STATE5} という識別子の集合を字句状態として宣言する。
 
マクロ定義
マクロ定義は、以下の形式を持つ これは、次のことを意味する。マクロ定義は、後でマクロを参照するために使えるマクロ識別子(文字の後に一連の文字、数字、下線が続く)、その後に続く0文字以上の空白、その後に続く "="、その後に続く0文字以上の空白、その後に続く正規表現(正規表現についてのさらなる情報についてはセクション[字句規則]を参照)から構成される。

各マクロは1つの行に収めなければならない。

右辺の正規表現は、よく形式化されて(well formed)いなければならず、^ 演算子や $ 演算子を含んでいてはならない。JLexとは違い、マクロは単なる一片のテキストではなく、コピーすることによって拡張される ― それらは構文解析され、よく形式化されていなくてはならない。

これは特徴である。それは、字句仕様の中のバグを見つけるためのいろいろな苦労を削除する(より複雑なマクロを囲む丸カッコを持たないようなこと ― JFlexではその必要がない)。JLex形式のマクロの問題のより詳細については[JLexからの移植]を参照のこと。

マクロ定義においてマクロの使用が可能であるため、要求される字句構造を記述するための表記のような文法を使うことが可能である。マクロは、しかしながら、それらを表す正規表現の単なる省略形のままである。それらは文法の非終端ではないし、どのような方法でも再帰的に使うことはできない。JFlexは、生成時にマクロ定義の中のサイクルを見つけ、それらを報告する。JFlexはまた、定義されているが仕様書の“字句規則”セクションで使われないマクロについても警告する。
 

字句規則

JFlexの仕様書の“字句規則”セクションは、正規表現の集合と、スキャナが関連づけられた正規表現にマッチした時に実行されるアクション(Javaコード)を含んでいる。
 

構文

“字句規則”セクションの構文は、以下のBNF文法によって表現される(終端記号は 'quotes' に囲まれている)。

LexicalRules ::= Rule+
Rule         ::= [StateList] ['^'] RegExp ['$'] Action
               | StateGroup
StateGroup   ::= StateList '{' Rule+ '}'
StateList    ::= '<' Identifier (',' Identifier)* '>'
Action       ::= '{' JavaCode '}'

RegExp       ::= RegExp '|' RegExp
               | RegExp RegExp
               | '(' RegExp ')'
               | RegExp ('*'|'+'|'?')
               | RegExp "{" Number ["," Number] "}"
               | '[' (Character|Character'-'Character)+ ']'
               | PredefinedClass
               | '{' Identifier '}'
   &n         | '"' StringCharacter+ '"'
               | Character

PredefinedClass ::= '[:jletter:]'
                  | '[:jletterdigit:]'
                  | '[:letter:]'
                  | '[:digit:]'
                  | '[:uppercase:]'
                  | '[:lowercase:]'
                  | '.'

文法は以下の終端記号を使用する:

\n エスケープシーケンスはASCII LFを意味する ― 行末を意味するのではない、ことに注意する。行の最後とマッチしたいならば、Javaによってサポートされたプラットフォームで異なった行末を考慮するために、表現 \r|\n|\r\n を使用すべきである。

JFlexバージョン1.1においては、空白文字 " " (space) と "\t" (tab) は、正規表現の読みやすさを改良するために使うことができる。それらはJFlexによって無視されるだろう。しかしながら、文字のクラスと文字列では、空白文字は空白そのものを表すだけである(そのため、文字列 " " は、正確な1つのスペース文字とマッチし、[ \n] はASCII LFまたはスペース文字とマッチする)。

JFlexは以下の標準的な演算子の優先順位を適用する(最上位から最下位の順):

そのため、例として、表現 a | abc | cd* は、(a|(abc)) | (c(d*)) のように解析される。

意味論

このセクションでは、ある正規表現(すなわち、で提示した文法の RegExp プロダクションによって記述される表現)によってマッチされるテキストの非公式な記述を与える。

以下のものから構成されるものだけが正規表現である。

もし ab が正規表現であるならば、 字句規則において、正規表現 r が(行頭演算子)'^' の後に続くことがある。r は、入力中の行の先頭にのみマッチする。行は、各 \n の後と入力の先頭で始まる。入力において、先行する \n は消費されず、他の規則によってマッチされる。

字句規則において、正規表現 r にはその後に(行末演算子)'$' が続くことがある。r は、入力中の行の最後にのみマッチする。行の最後は、正規表現 \r|\n|\r\n によって示される。行の最後は、消費されず、マッチされたテキストの範囲に含まれない。
 

入力はどのようにマッチされるのか

その入力を消費するとき、スキャナは入力の最も長い部分にマッチする正規表現を決定する(最長一致規則)。入力の最も長い部分にマッチする正規表現が1つ以上あるならば(すなわち、それらはすべて同じ入力にマッチする)、生成されたスキャナは、仕様書の初めに現れる正規表現を選択する。有効な正規表現を決定した後、関連づけられたアクションが実行される。もしマッチする正規表現がなければ、スキャナはエラーメッセージとともに終了する(%standalone 命令が使われたならば、スキャナはその代わりに、マッチしなかった入力を java.lang.System.out に表示し、そしてスキャニングを再開する)。

字句状態は、現在の入力にマッチする正規表現の集合を、さらに制限するために使うことができる。
 

アクションでアクセス可能なスキャナメソッドと変数

生成されたスキャナクラスの以下のメソッドとメンバ変数は、字句アクションでユーザによってアクセスされるべきものを意味する:

5 性能について二言三言

This section gives some empirical results about the speed of JFlex generated scanners in comparison to those generated by JLex, compares a JFlex scanner with a handwritten one, and presents some tips on how to make your specification produce a faster scanner.

Scanners generated by the tool JLex are quite fast: It was however possible to further improve the performance of generated scanners using JFlex. The following table shows the results that were produced by the scanner specification of a small toy programming language (it was in fact the example from the JLex website). The scanner was generated using JLex and all three different JFlex code generation methods. Then it was run on a W95 system using JDK 1.1.6 with  a sample input of about 5000 lines of code of that toy programming language. The values presented in the table denote the time from scanner object creation to returning the EOF value.
 
JLex
JFlex (default)
JFlex (%table)
JFlex (%pack)
  5000 lines, JIT
0,94 sec
0,88 sec 
6,8% faster
0,83 sec
13,2 % faster
0,83 sec
13,2 % faster
  5000 lines, no JIT
1,65 sec
1,43 sec 
15,4% faster
1,48 sec
14,9 % faster
1,49 sec
10,7 % faster
 
Since the scanning time of the lexical analyzer examined in the table above includes lexical actions that often need to create new object instances, another table shows the execution time for the same specification without lexical actions. A larger input file (about 15000 lines) has been used to reduce noise in the time measuerments.
 
 
JLex
JFlex (default)
JFlex (%table)
JFlex (%pack)
15000 lines, JIT
0,55 sec
0,44 sec
25,0 % faster
0,38 sec
44,7 % faster
0,38 sec
44,7 % faster
15000 lines, no JIT
2,52 sec
2,09 sec
20,5 % faster
2,14 sec
17,8 % faster
2,14 sec
17,8 % faster
 
It is however very difficult to optimize Java programs aggressivly, because execution time of single instructions depend on the platform and the implementation of the Java Virtual Machine the program is executed on. Therefore the tables above can not be used as a reference to which code generation method of JFlex is the right one to choose in general. The following table was produced by the same lexical specification and the same input on a Linux system using JDK 1.1.5.
 
JLex
JFlex (default)
JFlex (%table)
JFlex (%pack)
  5000 lines, 
with actions
4,25 sec
3,77 sec
12,7 % faster
3,83 sec
11,0 % faster
3,81 sec
11,5 % faster
15000 lines, 
with actions
1,33 sec
1,20 sec
10,8 % faster
1,23 sec
8,1 % faster
1,21 sec
9,9 % faster
  5000 lines, 
without actions
2,53 sec
2,09 sec
21,0 % faster
2,15 sec
17,7 % faster
2,16 sec
17,1 % faster
15000 lines, 
without actions
0,86 sec
0,75 sec
14,7 % faster
0,76 sec
13,2 % faster
0,77 sec
11,7 % faster

Although all JFlex scanners were faster than those generated by JLex, it shows slight differences between JFlex code generation methods when compared to the relations obtained on the W95 system.

It should also be stated here, that DFA based scanners like those generated by JFlex are usually faster than handwritten ones.
 
The following table compares a handwritten scanner for the Java language obtained from the website of CUP with the JFlex generated scanner for Java that comes with JFlex in the examples directory. They were tested on two different .java files on a W95 system using JDK 1.1.6.
 
handwritten scanner
JFlex generated scanner
7473 lines, JIT
2,42 sec
1,04 sec
132,6 % faster
5045 lines, JIT
1,71 sec
0,88 sec
94,3 % faster
7473 lines, no JIT
5,88 sec
1,86 sec
216,1 % faster
5045 lines, no JIT
4,01 sec
1,21 sec
231,4 % faster
 
As you can see, the generated scanner is up 230% faster than the handwritten one. The alert reader surely has noticed that execution times for the JFlex generated scanner differ only very little for a run with JIT compiler and without. With very large scanners and small input files this may even lead to the somewhat strange effect, that the scanner is faster without a JIT compiler than with the JIT switched on.

As Angelo Schneider pointed me: This is because the generated scanners are so good :-) What? Yes. Letエs take a look at the characteristics of a scanner: A scanner uses only a certain percentage X of its time for recognizing symbols, executing actions and the like. The rest of the time is spent with IO. An optimal scanner has a very small percentage X for the actual scanning and spends almost all of its time with IO. A bad scanner has a high value of X. A JIT compiler can only improve the X part of the scanner and can improve almost nothing of the IO time. So if the JFlex scanner has a low X value and is large (so it takes long for the JIT to compile it) and the input is small (so the small X that is improved can't pay off) the scanner gets slower with JIT than without (but it should still be faster than handwritten).

One example of a handwritten scanner that is considerably slower than the equivalent generated one is surely no proof for all generated scanners being faster than handwritten.It is clearly impossible to prove such a thing since you could always write the generated scanner by hand. From a software engineering point of view however, there is no excuse for writing a scanner by hand since this task takes more time, is more difficult and therefore more error prone than writing a compact, readable and easy to change lexical specification.
 

How to write a faster specification
Although JFlex generated scanners show good performance without special optimizations, there are some heuristics that can make a lexical specification produce an even faster scanner. Those are (roughly in order of performance gain):
 
Note, that writing more rules in a specification does not make the generated scanner slower (except when you have to switch to another code generation method because of the larger size).

It should be mentioned, that some of these tips contradict to a readable and compact specification style. When in doubt or when requirements are not (yet) fixed: don't use them - the specification can always be optimized in a later state of the development process.


6 JLexからの移植

JFlexは古いJLexの仕様書を変更することなく読むように、そして、JLexによって生成されたスキャナと「それよりも速い」という違いだけで、正確に同じふるまいをするスキャナを生成するように設計された。

これは、すべての「よく形式化された(well formed)」JLexの仕様書上で、 予想されるような動作をする。

上の記述がいくぶん絶対的(absolute)であることから、ここでは "well formed" が何を意味するかをちょっと調べてみよう。あるJLexの仕様書がwell formedであるのは、その仕様書が以下のようになっている場合である


7 協調動作:JFlexとCUP

JFlexの設計上のもう一つの主要な目標は、できるだけ簡単にフリーのJava構文解析ルーチン生成系(parser generator)CUP [8] とのインターフェイスを構成することである。これは、特別な意味を持った %cup 命令を与えることによって行われる。インターフェイスは、しかしながら常に2つの側面を持っている。このセクションでは、その話のCUP側に集中する:

もしあなたが、このように始まるスキャナの仕様書を持っているのであれば:


package PACKAGE;
import java_cup.runtime.*;    /* this is convenience, but not necessary */
 
%%
 
%class Lexer
%cup
..

それは次のように始まるCUPの仕様書とマッチする

package PACKAGE;

parser code {:
  Lexer lexer;

  public parser (java.io.Reader input) {
    lexer = new Lexer(input);
  }
:};

scan with {: return lexer.yylex(); :};
..



これは、生成されるパーザが parser という名前を得ることを仮定している。もしそうでなければ、あなたはコンストラクタの名前を調整しなくてはならない。

パーザはこのようなメインルーチンで開始されることがある:


..
  try {
    parser p = new parser(new FileReader(fileName));
    Object result = p.parse().value;
  }
  catch (Exception e) {
..

 
 

もしあなたが、生成されるスキャナの名前に依存しないパーザの仕様書を求めているのであれば、代わりにインターフェイス Lexer を書くことができる


public interface Lexer {
  public java_cup.runtime.Symbol yylex() throws java.io.IOException;
}

次のようにパーザのコードを変更する:

package PACKAGE;

parser code {:
  Lexer lexer;

  public parser (Lexer lexer) {
    this.lexer = lexer;
  }
:};

scan with {: return lexer.yylex(); :};

..



%implements 命令を使ってLexerインターフェイスのことをJFlexに知らせる:
..
%class Scanner     /* not Lexer now, since that is our interface! */
%implements Lexer
%cup
..

そして最後に、次のようになるようにメインルーチンを変更する


...
  try {
    parser p = new parser(new Scanner(new FileReader(fileName)));
    Object result = p.parse().value;
  }
  catch (Exception e) {
...

もしCUPが生成したパーザが提供するエラーメッセージを利用したいのであれば、CUPの仕様書の "parser code" セクションの中の report_errorreport_fatal_error メソッドを上書き(オーバライド)することもできる。新しいメソッドは、例えば、ユーザに対してもっと便利にエラーの位置を報告するために yylineyycolumn(クラス java_cup.runtime.Symbol のメンバ変数 left および right に格納されている)を使うことができる。このJFlexの配布(distribution)の examples\java\ ディレクトリの中にあるJava言語用のレキサとパーザは、この形式のエラー報告(error reporting)を使用している。これらの仕様書は、アクションの中で上のテクニックの実演も行っている。



 

8 バグ

All known bugs have been fixed in the release this manual accompanies.

If you find new ones, please report them to Gerwin Klein <kleing@informatik.tu-muenchen.de>.

Please check the FAQ and currently known bugs at the JFlex website before reporting a new bug.
 



 

9 参考文献

[1]
A. Aho, R. Sethi, J. Ullman, Compilers: Principles, Techniques, and Tools, 1986
[2]
A.W. Appel, Modern Compiler Implementation in Java: basic techniques, 1997
[3]
Elliot Berk, JLex: A lexical analyser generator for Java, http://www.cs.princeton.edu/~appel/modern/java/JLex/
[4]
K. Brouwer, W. Gellerich,E. Ploedereder, Myths and Facts about the Efficient Implementation of Finite Automata and Lexical Analysis, in: Proceedings of the 7th International Conference on Compiler Construction (CC '98), 1998
[5]
Vern Paxon, flex - The fast lexical analyzer generator, 1995
[6]
P. Dencker, K. Dürre, J. Henft, Optimization of Parser Tables for portable Compilers, in: ACM Transactions on Programming Languages and Systems 6(4), 1984
[7]
J. Gosling, B. Joy, G. Steele, The Java Language Specifcation, 1996, http://www.javasoft.com/docs/books/jls/
[8]
Scott E. Hudson, CUP LALR Parser Generator for Java, http://www.cs.princeton.edu/~appel/modern/java/CUP/
[9]
T. Lindholm, F. Yellin, The Java Virtual Machine Specification, 1996, http://www.javasoft.com/docs/books/vmspec/
[10]
R.E. Tarjan, A. Yao, Storing a Sparse Table, in: Communications of the ACM 22(11), 1979
[11]
R. Wilhelm, D. Maurer, Übersetzerbau, Berlin 19972



 

10 権利とライセンス

JFlex is free software, published under the terms of the GNU General Public License.

There is absolutely NO WARRANTY for JFlex, its code and its documentation.

The code generated by JFlex inherits the copyright of the specification it was produced from. If it was your specification, you may use the generated code without restriction.

See the file COPYING for more information.


Java is a trademark of Sun Microsystems, Inc., and refers to Sun's Java programming language. JFlex is not sponsored by or affiliated with Sun Microsystems, Inc.
introduced by JL