Транслятор?
02.04.2006 18:11:16Встав бодренько в восемь часов утра принялся писать транслятор. Собственно, давно была идея что-нибудь этакое сваять-попробовать. Естественно, что ни о чем серьезном речи еще не идет, все что я хотел сделать — это преобразовать обычную инфиксную алгебраическую нотацию в обратную польскую.
Пример частый и популярный, собственно, я его из книжки по основам построения трансляторов и почерпнул. Там он рассматривается схематично, все очень просто и понятно, но так как надо бы уже оттачивать владение инструментами реализации всего этого безобразия (КС-грамматик), то было решено что-нибудь накорябать.
Для начала я взял полюбившийся мне Ragel, который компилятор конечных автоматов. Человек знающий улыбнется уже здесь, ну а я несколько часов все-таки постучался лбом об стену того, что анализ КС-грамматики в принципе невозможно реализовать в рамках конечного автомата, зато с помощью автомата с магазинной памятью — только так. 🙂
Впрочем, стучал не совсем без толку, поскольку на Ragel это сделать все-таки можно, он может делать «странные» переходы и КС-грамматику на его основе проанализировать можно. Можно, но очень некрасиво, а меня это совсем неустраивало.
В результате, пока я обдумывал, как бы мне начать работать с LLnextgen или Flex, правильный человек aka Дрюнь прислал мне ссылку на Bison. На который я резко и накинулся, а в «info bison» как раз обнаружился пример калькулятора что в обратной польской нотации, что в обычной инфиксной.
В общем, я взял за основу постфиксный калькулятор, описал свою грамматику (BTW, vim замечательно подсвечивает синтаксис) и получил не только «переводчик» из инфикса в постфикс, но еще и (заметьте, нахаляву!) калькулятор. По этому поводу сижу и радуюсь.
А описание получилось в таком духе:
%token NUM
%left '-' '+'
%left '*' '/'
%left NEG
%start input
%%
input : /* empty */
| input line
;
line : '\n'
| expr '\n' { printf( "\n\t%.10g\n", $1 ); }
;
expr : NUM { $$ = $1; printf("%.10g ", $1); }
| expr '+' expr { $$ = $1 + $3; printf("+ "); }
| expr '-' expr { $$ = $1 - $3; printf("- "); }
| expr '*' expr { $$ = $1 * $3; printf("* ");}
| expr '/' expr { $$ = $1 / $3; printf("/ ");}
| '-' expr %prec NEG { $$ = - $2; printf("inv ");}
| '(' expr ')' { $$ = $2; }
;
%%