Роман Химов

В самом прямом смысле! Сегодня получил первый зачет на эту сессию по «Проектированию программных систем». Сдавали последние две работы, но неспортивно, аж обидно. Когда у преподавателя болит голова, сдавать неинтересно. А то я так старался на Форте, так старался с шести часов утра… Что даже самому понравилось.

На Форте (Википедия, Wikipedia) последняя лаба была, там мы еще раз реализовывали замечательный конечный автомат, который делали еще на самой первой лабе на C или Java какой-нибудь (хи-хи, а кто-то на Ragel :)). Естественно, попутно изучали этого зверя (до этого я с ним общался года три назад, наверное, когда ковырялся с nncron). Извиняюсь, но зарулил Форт Ragel по полной программе, разница между препроцессором для C/C++/Java/т.д. и простым до безобразия, но чудовищно эффективным по сути понятием словаря с виртуальной машиной, видна сразу.

Калашникова реализовывал вот по такой простой методике. Скажите мне, в каком еще языке это вообще возможно? По сути, я начертил табличку переходов в ASCII графике, да воспользовался парой определений из указанной статьи. И все работает. Без тонны if, then, else, case, switch, goto и прочей шелухи. Очень это радостно.

Ну и зачёт, конечно. Как-никак, а ведь если призадуматься, то это последняя сессия. Дальше уже такого цирка не будет. Эх.

Встав бодренько в восемь часов утра принялся писать транслятор. Собственно, давно была идея что-нибудь этакое сваять-попробовать. Естественно, что ни о чем серьезном речи еще не идет, все что я хотел сделать — это преобразовать обычную инфиксную алгебраическую нотацию в обратную польскую.

Пример частый и популярный, собственно, я его из книжки по основам построения трансляторов и почерпнул. Там он рассматривается схематично, все очень просто и понятно, но так как надо бы уже оттачивать владение инструментами реализации всего этого безобразия (КС-грамматик), то было решено что-нибудь накорябать.

Для начала я взял полюбившийся мне 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; }
;
 
%%