lex & yaccことはじめ

とある図書館でlex & yaccという本が廃棄処理扱いされていたので、もらってきたのですが消化していなかったので、消化をかねてlex & yaccについての調査などしてみました。

ネットでの資料としては Lex and Yacc Primerの資料が秀逸で、とりあえずここに書いている事を理解すれば最低限lex & yaccを使えるようになるかと思います。

lex & yacc において、言語処理を作るにあたりどっちが重要かという事になるとやはりyaccの方が重要！！　というのはlexってのは字句解析なので頑張れば自分でも構築可能だからです。yaccの構文解析も頑張れば無理じゃないかもしれませんがきついと思います。

とっつきやすいのはどちらかというとlexの方ですね。lexは単体でも字句解析ができたりするので、lex単体でもちょっとした事はできるのですが、yaccの場合は処理内容は構文解析であるので、字句解析の処理はしないので外部プログラムが頼りになるからです。まぁyaccを使う際には字句解析も必要となるという訳なのですよ。というわけで、yaccを使う際にはlexとか自作？字句解析を使う必要があるのですよね。

実際の言語処理だとyacc用のファイルはあるけれどもlex用のは無いというパターンが多い？感じがしますね、はい。　というわけでyacc重要。 LR LR !!!

とりあえずlexからいじってみる。

lexのプログラムは単純で、正規表現を利用して字句解析をするだけです。

以下は簡単なサンプル

%{                                                                                                                                                         
#include <stdio.h>                                                                                                                                         
%}                                                                                                                                                         
                                                                                                                                                           
%%                                                                                                                                                         
                                                                                                                                                           
tukasa  printf("barusamikosu~~\n");                                                                                                                        
kagami  printf("kagaminmin\n");;                                                                                                                           
konata  printf("konatanntann\n");                                                                                                                          
                                                                                                                                                           
%%   

で、このファイルをtest.lとして保存し以下のようにコンパイルすると

gcc -o test test.l -ll

testバイナリができるので、字句解析が出来ているか調べる. tukasa, kagami, konataといった感じで入力すると以下のような感じになるはず

./test

tukasa
barusamikosu~~

kagami
kagaminmin

konata
konatanntann

とりあえずlexの最低限度の動作が確認できたら次はyaccとの連携を行う。

yaccとlexとの連携に関してlexで行う事はというと、yaccで定義したトークンというものをlex内部で字句解析を行い返して、yaccではその返り値(トークン)をもとにyacc内部で定義した文法定義を元に色々と処理をしていく！！！　という感じ。　

というわけでlex内部では、yaccで定義した定義を参考するためにyaccファイルをyaccコマンドを行った際に現れる、y.tab.hをインクルードする必要があるという訳なんですよね。主従関係的に考えるとyaccの方が上的なポジションといってよさそうですね。

一方、yaccはというと、こっちは文法を定義して構文解析を行うといます。

とりあえず簡単なサンプルソースを作ったので掲載など

とりあえずファイル名はtete.l tete.y とする

tete.l

%{                                                                                                                                                         
#include <stdio.h>                                                                                                                                         
#include "y.tab.h"                                                                                                                                         
%}                                                                                                                                                         
                                                                                                                                                           
                                                                                                                                                           
%%                                                                                                                                                         
                                                                                                                                                           
tukasa  return TUKASA;                                                                                                                                     
kagami  return KAGAMI;                                                                                                                                     
konata  return KONATA;                                                                                                                                     
[0-9]+  yylval=atoi(yytext); return NUMBER;                                                                                                                
                                                                                                                                                           
%% 

ちなみにreturnをかえしているNUMBERとかはyaccファイル内部で定義しています

tete.y

%{                                                                                                                                                         
#include <stdio.h>                                                                                                                                         
#include <string.h>                                                                                                                                        
                                                                                                                                                           
void yyerror(const char *str)                                                                                                                              
{                                                                                                                                                          
    fprintf(stderr,"error: %s\n",str);                                                                                                                     
}                                                                                                                                                          
                                                                                                                                                           
int yywrap()                                                                                                                                               
{                                                                                                                                                          
    return 1;                                                                                                                                              
}                                                                                                                                                          
                                                                                                                                                           
main()                                                                                                                                                     
{                                                                                                                                                          
    yyparse();                                                                                                                                             
}                                                                                                                                                          
                                                                                                                                                           
%}                                                                                                                                                         
                                                                                                                                                           
%token TUKASA KAGAMI KONATA NUMBER                                                                                                                         
                                                                                                                                                           
%%                                                                                                                                                         
                                                                                                                                                           
commands:                                                                                                                                                  
    | commands command                                                                                                                                     
    ;                                                                                                                                                      
                                                                                                                                                           
                                                                                                                                                           
command:                                                                                                                                                   
    TUKASA NUMBER                                                                                                                                          
    {                                                                                                                                                      
        printf("\tTUKASA is %d\n",$2);                                                                                                                     
    }                                                                                                                                                      
    ;                                                                                                                                                      

とまぁこんな感じでとりあえず作成しています。yaccの文法定義はTUKASA NUMBERだけなので、この文法にあえばTUKASA is %d(なんか数字) が出力されます。

とりあえずコンパイル

yacc -d tete.y
flex tete.l
gcc -o tete y.tab.c lex.yy.c -ll

で、バイナリを実行する. テストとしてtukasa 1, tukasa 3, tukasa 33などと入力してみる

./tete

tukasa 1
TUKASA is 1

tukasa 3
TUKASA is 3

tukasa 33
TUKASA is 33

とまぁこんな感じで出力されるはずです。これで最低限度lex & yaccの連携ができたので後はこれを拡張すれば簡単な言語処理とかできるかも！！　というわけですね。

参考リンク:

• Lex and Yacc Primer
• およびサンプルソース
  • LexとYaccを早習するのに秀逸なサイト。これをやっておけば最低限lexとyaccが使えるようになるはず！！

• プログラミング言語処理
  • 筑波の資料 tinyCというCライクな言語処理系をyaccを使う事で作っている。

• Cコンパイラ設計(yacc lexの応用
  • Cコンパイラを作りたいときに役立つかと