Транслятор?

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; }
;
 
%%

Метки: , , ,

Комментариев нет »