yacc／lex－プログラムジェネレータon UNIX 五月女健治著 啓学出版
ずいぶん前に買った本。
啓学出版が倒産したらしく書店で久しく見なかったのだがテクノプレスから同名で出版されているようだ。
yacc/lexを知ったのは1989年頃アスキーだったかCマガだったかで知った。
GNUにbison/flaxがあることが分かったのだが当時田舎では手に入れることがでなかった。
数年後PCにFreeBSDをインストールしてから使えるようになった。
その頃買ったのだと思う。
今はbaison/flexがCygwinにあるので気楽に使える。
yacc(Yet Another Compiler Compiler)は
1970にStephen C. Johnson が書いた、BNF(Backus-Naur form)風の定義からパーサジェネレータのCソースを出力するUNIXのツール。Dennis M. Ritchie がCを書いたのが1972だから、最初はBで書いたらしい。 Stephan C. Johnsonはyaccのほかにlintやspel、Portable Cも書いている有名な人。
電卓のサンプルはそこらじゅうにあるので、CSVのパーサを作ってみる。
CSVはたいていの言語で組み込み関数があったり、ライブラリが用意されていたりだ。自分で実装するのは難しくない。全ての文字を許すエスケープ･フィールド（’”’）の処理と、’”’のエスケープ処理に気をつければ良い。yaccを持ち出すより小さく書ける。 ^^)
CSVはRFC1480にある（日本語訳はここ）けど、RFCに書いてある定義はABNFなので、そのままyaccに食わせることができない。ここにあるEBNF定義をyaccが喰えるように変更する。
CVSのEBNF定義（http://fileformats.archiveteam.org/wiki/CSV）
<CSVFile> ::= <Record>*
<Record> ::= { <Field> (<Delimiter> <Field>)* } <EOL>
<Field> ::= <SimpleField> <QuotedField>
<SimpleField> :== AlphaNum* ;Any sequence of alpha-numeric characters
<QuotedField> :== <QuoteChar> <Anychar>* <QuoteChar>
<QuoteChar> :== " | ' ;but note that they generally must match
<Delimiter> :== ","
|
繰り返しを再帰で書き直してyaccのソースにして、lexを使わないでyaccだけでやってみる。
コンパイルは↓
$ yacc -dv csv.y && gcc -DYYDEBUG -DYYERROR_VERBOSE -o csv y.tab.c
csv.y
%{
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#define BUF_SIZE 1024
int Debug = 0;
#define DEBUG(l) if ((l)<=Debug)
char buf[BUF_SIZE];
char *top = buf;
FILE *yyin;
int yylineno = 1;
int fldno=1;
void yyerror(const char *msg) ;
int yylex(void) ;
%}
%union {
char *str;
char chr;
}
%start CSVFile
%type <str> CSVFile Record FieldList Field SimpleField QuotedField
%type <str> QuotedFieldBody
%type <chr> QuoteChar Anychar AlphaNum Mark CR LF
%type <chr> Space SpaceChar SpaceChars
%%
CSVFile : Record
| CSVFile Record
;
Record : EOL { $$=NULL; }
| FieldList EOL { yylineno++; fldno=1; }
;
FieldList : Field { top=buf;
printf("%d.%d:<%s>\n",
yylineno, fldno++, $1);
}
| FieldList Delimiter Field { top=buf;
printf("%d.%d:[%s]\n",
yylineno, fldno++, $3);
}
;
Field : SimpleField { $$=$1;
DEBUG(1)printf("SFld=%s\n", $1);
}
| QuotedField { $$=$1; }
;
SimpleField : AlphaNum { $$=buf; *top++=$1; *top='\0';
DEBUG(1)
printf("AlNum=%02x\n",$1);
}
| SimpleField AlphaNum { $$=buf; *top++=$2; *top='\0';
DEBUG(1)
printf("AlNum=%02x\n",$2);
}
;
QuotedField : QuoteChar QuotedFieldBody QuoteChar { $$=$2; }
;
QuoteChar : '"' { $$='"'; }
| '\'' { $$='\''; }
;
QuotedFieldBody : Anychar { $$=buf; *top++=$1; *top='\0';
DEBUG(1)
printf("QFBody=%s\n",buf);
}
| QuotedFieldBody Anychar { $$=buf; *top++=$2; *top='\0';
DEBUG(1)
printf("QFBody=%s\n",buf);
}
;
Anychar : AlphaNum | Mark | SpaceChar | CR | LF | QuoteChar QuoteChar;
Delimiter : Space ',' Space ;
EOL : CR LF | LF;
CR : '\r' { $$='\r'; } ;
LF : '\n' { $$='\n'; } ;
;
AlphaNum : '0'{$$='0';} | '1'{$$='1';} | '2'{$$='2';} | '3'{$$='3';}
| '4'{$$='4';} | '5'{$$='5';} | '6'{$$='6';} | '7'{$$='7';}
| '8'{$$='8';} | '9'{$$='9';}
| 'A'{$$='A';} | 'B'{$$='B';} | 'C'{$$='C';} | 'D'{$$='D';}
| 'E'{$$='E';} | 'F'{$$='F';} | 'G'{$$='G';} | 'H'{$$='H';}
| 'I'{$$='I';} | 'J'{$$='J';} | 'K'{$$='K';} | 'L'{$$='L';}
| 'M'{$$='M';} | 'N'{$$='N';} | 'O'{$$='O';} | 'P'{$$='P';}
| 'Q'{$$='Q';} | 'R'{$$='R';} | 'S'{$$='S';} | 'T'{$$='T';}
| 'U'{$$='U';} | 'V'{$$='V';} | 'W'{$$='W';} | 'X'{$$='X';}
| 'Y'{$$='Y';} | 'Z'{$$='Z';}
| 'a'{$$='a';} | 'b'{$$='b';} | 'c'{$$='c';} | 'd'{$$='d';}
| 'e'{$$='e';} | 'f'{$$='f';} | 'g'{$$='g';} | 'h'{$$='h';}
| 'i'{$$='i';} | 'j'{$$='j';} | 'k'{$$='k';} | 'l'{$$='l';}
| 'm'{$$='m';} | 'n'{$$='n';} | 'o'{$$='o';} | 'p'{$$='p';}
| 'q'{$$='q';} | 'r'{$$='r';} | 's'{$$='s';} | 't'{$$='t';}
| 'u'{$$='u';} | 'v'{$$='v';} | 'w'{$$='w';} | 'x'{$$='x';}
| 'y'{$$='y';} | 'z'{$$='z';}
;
Mark : '!'{$$='!';} | '#'{$$='#';}
| '$'{$$='$';} | '%'{$$='%';} | '&'{$$='&';}
| '('{$$='(';} | ')'{$$=')';} | '*'{$$='*';} | '+'{$$='+';}
| '-'{$$='-';} | '.'{$$='.';} | '/'{$$='/';} | ':'{$$=':';}
| ';'{$$=';';} | '<'{$$='<';} | '='{$$='=';} | '>'{$$='>';}
| '?'{$$='?';} | '@'{$$='@';} | '['{$$='[';} | '\\'{$$='\\';}
| ']'{$$=']';} | '^'{$$='^';} | '_'{$$='_';}
| '`'{$$='`';} | '{'{$$='{';} | '|'{$$='|';} | '}'{$$='}';}
| '~'{$$='~';}
;
Space : /* empty */ {}
| SpaceChars
;
SpaceChars : SpaceChar
| Space SpaceChar
;
SpaceChar : ' '{$$=' ';} | '\t'{$$='\t';}
;
%%
void yyerror(const char *msg) {
fprintf(stderr, "error %s : line %d\n", msg, yylineno);
}
int yylex(void) {
int c = getc(yyin);
DEBUG(1) printf("C=%02x(%c) ", c,c);
return c;
}
void help(char *cmd) {
char *p;
if ((p=strrchr(cmd, '/'))==NULL)
p = cmd;
else p++;
fprintf(stderr, "usage: %s [-hdl][csv_file]\n", p);
exit(-1);
}
int main(int ac, char **av) {
int c;
while ((c=getopt(ac,av,"Ddh"))!=-1) {
switch (c) {
case 'd' : Debug++; break;
case 'D' : yydebug = 1; break;
case 'h' :
default : help(av[0]); break;
}
}
ac -= optind;
av += optind;
if (0<ac) {
if ((yyin=fopen(av[0],"rb"))==NULL) {
perror("csv file");
exit(-2);
}
} else yyin = stdin;
return yyparse();
}
|
いやあ直接Cで書いたほうがラクじゃないか！！ということでlexと組み合わせてみる。
%{
/*-----------------------------------*/
/* csv.y */
/* Sep. 2014 / Yoshi */
/*-----------------------------------*\
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#define BUF_SIZE 1024
int Debug = 0;
#define DEBUG(l) if ((l)<=Debug)
FILE *yyin;
extern int yylineno;
int fldno=1;
void yyerror(const char *msg) ;
int yylex(void) ;
%}
%union { char *str; }
%start CSVFile
%token DELIMITER QUOTEDFIELD SIMPLEFIELD EOL
%type <str> CSVFile Record FieldList Field SIMPLEFIELD QUOTEDFIELD
%%
CSVFile : Record
| CSVFile Record
;
Record : EOL { $$=NULL; }
| FieldList EOL { yylineno++; fldno=1; }
;
FieldList : Field { printf("%d.%d:<%s>\n", yylineno, fldno++, $1); }
| FieldList DELIMITER Field
{ printf("%d.%d:[%s]\n", yylineno, fldno++, $3); }
;
Field : SIMPLEFIELD { $$=$1; }
| QUOTEDFIELD { $$=$1; }
;
%%
void yyerror(const char *msg) {
fprintf(stderr, "error %s : line %d\n", msg, yylineno);
}
void help(char *cmd) {
char *p;
if ((p=strrchr(cmd, '/'))==NULL)
p = cmd;
else p++;
fprintf(stderr, "usage: %s [-hdl][csv_file]\n", p);
exit(-1);
}
int main(int ac, char **av) {
int c;
while ((c=getopt(ac,av,"Ddh"))!=-1) {
switch (c) {
case 'd' : Debug++; break;
case 'D' : yydebug = 1; break;
case 'h' :
default : help(av[0]); break;
}
}
ac -= optind;
av += optind;
if (0<ac) {
if ((yyin=fopen(av[0],"rb"))==NULL) {
perror("csv file");
exit(-2);
}
} else yyin = stdin;
return yyparse();
}
/*==============================================================*/
%{
/*-----------------------------------*/
/* csv.l */
/* Sep. 2014 / Yoshi */
/*-----------------------------------*\
#include <stdio.h>
#include "y.tab.h"
int yywrap(void) { return 1; };
%}
%s QUOTE
ALPHNUM [a-zA-Z0-9]+
ANYCHAR ([^"]|(\"\"))*
%%
<INITIAL>, return DELIMITER;
<INITIAL>\r?\n return EOL;
<INITIAL>{ALPHNUM} yylval.str = strdup(yytext); return SIMPLEFIELD;
<INITIAL>\" BEGIN(QUOTE);
<QUOTE>{ANYCHAR} { int i, j;
for (i=j=1; i<yyleng; i++) {
if (yytext[i]!='"' && yytext[i-1]!='"')
{
yytext[j++] = yytext[i];
}
}
yytext[j] = '\0';
yylval.str = strdup(yytext);
return QUOTEDFIELD;
}
<QUOTE>\" BEGIN(INITIAL);
[ \t]+ ;
. return yytext[0];
%%
/*==============================================================*/
#
# csv.y csv.l makefile
# Sep. 2014 / Yoshi
#
RM = rm -f
LEX = flex
YACC = yacc -d
CC = gcc
TARGET = csv
CFLAGS = -DYYDEBUG -DYYEROR_VERBOSE
SRC =
all : y.tab.o lex.yy.o
$(CC) $(CFLAGS) -o $(TARGET) y.tab.o lex.yy.o
y.tab.c : $(TARGET).y
$(YACC) -v $(TARGET).y
lex.yy.c : $(TARGET).l
$(LEX) $(TARGET).l
clean:
$(RM) y.tab.c lex.yy.c $(TARGET) y.output
|
実行したところ↓行番号．フィールド番号［データ］のように表示する。
3行目の空白(’ ’)、引用符(’”’)、改行(’\n’)がちゃんと切り出されている。
$ cat test.csv
aaa,bbb,ccc
aaa , bbb , ccc
"a a", "b""", "c
"
$ ./csv test.csv
1.1:<aaa>
1.2:[bbb]
1.3:[ccc]
2.1:<aaa>
2.2:[bbb]
2.3:[ccc]
3.1:<a a>
3.2:[b"]
3.3:[c
]
|
CSVくらいの文法なら、yacc&lexを使うよりCで実装したほうが簡単かも。
アセンブラくらいになると有難さが分かる。
コメント