nDiki : flex

flex

字句解析器生成ツール。

1999年1月20日 (水)

Perl で lex/yacc

最近 Perl で字句解析ルーチン生成系/構文解析ルーチン生成系を作ろうかな、などと考えている。 前にもやろうと思っていたのだが、なにもしていなかった。なぜ Perl でかというと、

  • C/C++言語にはすでに存在する(flex/bison)。
  • Perl にはいいものが存在しない(知らない)。
  • flex/bison はC/C++のものしか生成できない。
  • これは動的に生成し利用すること、また動的に変更することが考慮されていない。
  • Perl なら実行時にサブルーチン定義したり eval できたりする。
  • Perl なら気が楽。

などが理由であろうか。 また自分の研究で設計している言語を Scheme 上で実装しようかなと思っているが、その字句解析ルーチン生成系/構文解析ルーチン生成系が欲しい(あることにはあるが)。 一旦 Perl で生成系を自作しておけば、簡単に他の言語の解析ルーチンを生成できるように拡張できるであろう(と考えたい)。

動的な側面が念頭にあるのは、自分の研究がそういうことをやっているから。

とりあえず lex/yacc(flex/bison)互換/ライクなものを作る予定である。 これらはそれぞれ仕様記述のファイルを読み込んで解析ルーチン(解析用テーブル)を生成する。 ので、とうぜんこの仕様記述言語の字句解析ルーチン/構文解析ルーチンが必要である。 手で書いてもいいのだが、それも面倒だ。 当然字句解析ルーチン/構文解析ルーチン生成系が欲しい。 しかしまだない。 これから作ろうとしているものそのものだから。

方法としては、

  • Perl で手書きで解析ルーチンを作る。それで Perl 用生成系の仕様記述を読ませて、置き換える。
  • Perl の既存の生成系を使う。
  • flex/bison を使って C/C++ 版を作成。その後その生成系で Perl 用生成系の仕様記述を読ませる。

などが考えられる。今回はとりあえず一番最後の方法をとろうと思う。 ただし実際には完全に C/C++ で作るのではなく、字句解析/構文解析ルーチンを flex/bison で生成し、それを Perlエクステンションとして、Perl から呼べるようにすることにする。こうしておけば、

とすることができる。最初のものを全部 C/C++ で書くと、解析ルーチン生成部を C/C++Perl で2回書かなければならないが、この方法ならその部分は Perl で書いておけるので2度手間にならないであろう。

ということ一昨日は flex のコードを眺めて、昨日は Perl エクステンション書き方を調べてみている。 flex で吐いたファイルをそのまま Perl エクステンションのコードとは当然できないので、そのトランスレータをまず作ることする。

スポンサード リンク
[ 1月20日全て ]

1999年1月24日 (日)

flex から XS へ、Segmentation fault

Perl から flex の出力した yylex() を呼び出す実験。 まずは簡単な字句解析仕様記述を書いて、flex を通す。 この出力に yylexc2xs と名前をつけたスクリプトを通して XS に変換する。 これは単純に先頭に XS のためのヘッダファイルのインクルードの行を追加し、最後に Perl から yylex を呼ぶためのモジュール定義とコードを追加するだけのもの。

これをコンパイルして Perl から呼び出してみる。 Segmentation fault。 実際には Perl から l2xs_yylex() というCの関数を呼んでそこから flex の出力する yylex() を呼んでいる。 l2xs_yylex() から yylex() を呼ばないようにすると正常終了するので、やはり yylex() か、そこから先でなにかがあるようだ。

入力の問題かと yyin の値を Perl から渡すようにしたり l2xs_yylex() でファイルをオープンしてそれを設定したりしてから yylex() を呼んでも結果は同じ。

flex の出力は shared library にできないのか? Perl + shared library ということでデバッガでどうすればいいのかもわからず。

とりあえず棚上げ。 CPAN から ParseLex-2.05.tar.gz と Parse-Yapp-0.21.tar.gz をとってくる。 Perl 内で済ませられればそれでいいかな。 というかこの2つの出来がよければ自作する必要性もなくなるのだが。

[ 1月24日全て ]

1999年1月31日 (日)

flex文法定義を読む(定義節/parse.y)

字句解析系生成プログラム作成のために、flex-2.5.4a.tar.gzの文法定義を読んでみる。 まずここでは、定義節(definitions section)を読むことにする。

トークンの定義は scan.l で、構文の定義は parse.y でなされている。 まずは parse.y から見ていこう。 以下の引用部はすべて parse.y である。 行頭には行番号を付加してある。 また説明に不要な部分は省略してある。

以下はでのトークン名の宣言である。

     3	%token CHAR NUMBER SECTEND SCDECL XSCDECL NAME PREVCCL EOF_OP
     4	%token OPTION_OP OPT_OUTFILE OPT_PREFIX OPT_YYCLASS
     5
     6	%token CCE_ALNUM CCE_ALPHA CCE_BLANK CCE_CNTRL CCE_DIGIT CCE_GRAPH
     7	%token CCE_LOWER CCE_PRINT CCE_PUNCT CCE_SPACE CCE_UPPER CCE_XDIGIT

また以下は定義節に関係するルールの部分である。

   112	goal		:  initlex sect1 sect1end sect2 initforrule
   139			;
   141	initlex		:
   147			;
   149	sect1		:  sect1 startconddecl namelist1
   150			|  sect1 options
   151			|
   152			|  error
   154			;
   156	sect1end	:  SECTEND
   162			;
   164	startconddecl	:  SCDECL
   167			|  XSCDECL
   169			;
   171	namelist1	:  namelist1 NAME
   174			|  NAME
   177			|  error
   179			;
   181	options		:  OPTION_OP optionlist
   182			;
   183
   184	optionlist	:  optionlist option
   185			|
   186			;
   188	option		:  OPT_OUTFILE '=' NAME
   193			|  OPT_PREFIX '=' NAME
   195			|  OPT_YYCLASS '=' NAME
   197			;

goal (112行目)は開始記号である。 ここで字句解析仕様記述全体の構造を定義している。 ここでは sect1end までを見ることにする。

   141	initlex		:
   147			;

initlex (141行目)は仕様記述の先頭の部分で還元される。 ここで初期化処理が行われる。

   156	sect1end	:  SECTEND
   162			;

sect1end (156行目)トークン SECTEND を導出する。

 SECTEND は scan.l119行目の

^"%%".* のパターンで定義されるものである。 つまり、行頭の %% で 定義節が終了することを示す。

   149	sect1		:  sect1 startconddecl namelist1
   150			|  sect1 options
   151			|
   152			|  error
   154			;

定義節の中身は sect1によって導出される。 定義節は、開始条件の宣言(startconddecl namelist1 または オプション指令options の任意個の繰り返しを導出する。

   164	startconddecl	:  SCDECL
   167			|  XSCDECL
   169			;

startconddecl はトークン SCDECL または XSCDECL である。 SCDECL は scan.l108行目の ^"%s"{NAME}? で定義され、XSCDECLは109行目の ^"%x"{NAME}? である。 よって行頭から始まる %s または %x (名前として使える文字列が続いてもよい)によって始まる行が開始条件の宣言ということになる。

   171	namelist1	:  namelist1 NAME
   174			|  NAME
   177			|  error
   179			;

SCDECL または XSCDECL の次には namelist1 が次に導出される。 namelist、トークン NAME の1回以上の繰り返しである。

   181	options		:  OPTION_OP optionlist
   182			;

一方 sect1 は options も導出する。 options は、トークンOPTION_OP の後に optionlistが続くとなっている。 OPTION_OP は scan.l131行目にある ^"%option" にマッチした時返されるトークンである。 つまりオプション指令は行頭から始まる %option によって始まることを示している。

   184	optionlist	:  optionlist option
   185			|
   186			;

そして optionlist(181行目) は option の 0回以上の繰り返しである。

   188	option		:  OPT_OUTFILE '=' NAME
   193			|  OPT_PREFIX '=' NAME
   195			|  OPT_YYCLASS '=' NAME
   197			;

その option は トークンOPT_OUTFILE, OPT_PREFIX, OPT_YYCLASS のどれかの後に '=' が続き、そしてその後に NAME がくるといいうものである。OPT_OUTFILE, OPT_PREFIX, OPT_YYCLASS はそれぞれ文字列 outfile, prefix, yyclass が対応する。

これだけでは定義節のすべての文法を網羅していない。実は他の多くの部分は、字句解析で処理してしまっている。次回はscan.l についてもうすこし詳しく見てみよう。

[ 1月31日全て ]

2005年2月23日 (水)

ActivePerlMing

ActivePerlMing を使えるようにしておきたい。

Visual Studio

Ming 0.3 beta1 のソースパッケージには Visual Studio 6.0 用のプロジェクトファイルが含まれている。 Cygwin の Bison と flex があればライブラリをビルドできるようだ。 横着して Linux 側で bison と flex で生成したファイルをコピーして(それから unistd.h をインクルードしている部分を消して)、ビルドしてみたところ一応 lib ファイルは作成成功。

しかし ActivePerl 用にPerl モジュールの make は失敗。

MinGW + nmakeActivePerl のモジュールをビルドできるらしい

調べたところ ExtUtils::FakeConfig を使うと Visual Studio が無くても MinGW + nmake でモジュールをビルドできるらしい(全てではないと思うが)。

ということで MingMinGWビルドした後、そのまま ActivePerl 用モジュールの作成まで持ち込むことにしてみる。

MinGW + MSYS + GnuWin32開発環境を構築

コンパイルに必要な環境を MinGW で、configure に必要な環境を MSYS で用意する。

bison は GnuWin32

Mingビルドに必要な Bison は MinGWMSYSインストーラに含まれていない。 bison-1.875.0-2003.02.10-1.exe というのが別途あるがうまく動かない。

ソースパッケージ(bison-2.0.tar.gz、bison-1.875.tar.gz)からはビルドできず。 MinGW/MSYSのプロジェクトにある bison-1.875-2003.02.10-1-src.tar.gz はビルドできるものの make check が通らない。

とうことで GnuWin32 の bison-1.875-4.exe (インストーラ形式)をインストール。 c:/usr/local/GnuWin32インストールした後、MSYS の /etc/fstab で /GnuWin32 にマウントし、/GnuWin32/bin に PATH を通しておく。

flexソースパッケージから

flex-2.5.4a.tar.gz を展開して

 ./configure; make; make check; make install

インストール時ハードリンクが作れなくてエラーがでているようだが無視。

zlib (Ming で必要)

MSYS 上でビルドしてインストール。zlib-1.2.2.tar.gz を展開して

 ./configure; make; make check; make install

LibUnGif for Windows (Ming で必要)

MSYS 上でビルドしてインストール。 libungif-4.1.0b1-src.zip を展開して

 rm config.cache;
 config.h内の-DHAVE_VARARGS_Hをコメントアウト。
 ./configure; make; make install

make check はエラーが出るが無視。

libpng (Ming で必要)

MSYS 上でビルドしてインストール。libpng-1.2.8-config.tar.gz を展開して

 CFLAGS=-I/usr/local/include LDFLAGS=-L/usr/local/lib ./configure
 make; make check; make install

いよいよ Ming

MSYS 上でビルド。ming-0.3beta1.tar.gz を展開して

 CFLAGS=-I/usr/local/include LDFLAGS=-L/usr/local/lib make static

ActivePerl 用モジュール作成

ExtUtils::FakeConfigPPM::MakeMingSWF PPM パッケージを作成する。 (MSYSシェルではなく)コマンド プロンプトを開いて、Mingソースパッケージの中の perl_ext に移動。 MSYSMinGWnmake にPATHを通しておく。

それから Makefile.PL の実行で -lz を発見できないので、libz.a を Makefile.PL と同じディレクトリにコピーしてしまう(-L/usr/local/lib を指定しても効かなかったので)。 libpng.a、libungif.a も同じくコピーしておく。

Makefile を作成。Makefile.PL では -lz しか指定していないが、libpng と libungif も必要なのでコマンドラインオプションで指定する。ExtUtils::FakeConfig の Config_m を使用して MinGW を使用するようにする。

 perl -MConfig_m Makefile.PL LIBS="-lpng -lungif -lz"

ここで生成される Makefile の中で libperl58.a を指定している部分があるが、ActivePerl では perl58.lib になるので、エディタで書き換え。 後はいつも通り

 nmake
 nmake test
 make_ppm

PPM パッケージ作成完了。

簡単なPerlプログラムでSWFファイルが作れる事を確認。 やった。

[ 2月23日全て ]

About Me

Naney Naney (なにい)です。株式会社ミクシィで SNS 事業の部長をしています。

nDiki1999年1月に始めたコンピュータ日誌を前身とする NaneyWeb 日記(兼パーソナルナレッジベース)です。ちょっとしたノートは nNote にあります。

※内容は個人的見解であり所属組織とは関係ありません。

follow us in feedly

月別インデックス
Process Time: 0.057764s / load averages: 0.51, 0.32, 0.34
nDiki by WATANABE Yoshimasa (Naney, Google profile)
Powered by DiKicker