RPN калькулятор на flex и bison

calc.l

%{
#include <cstdlib>
#include "calc_defines.h"
%}

%option noyywrap
%option debug

digit [0-9]
nl    [\r\n]

%%

"+"                     return PLUS;
"-"                     return MINUS;
{digit}*\.?{digit}+     {
                            yylval.dval = std::atof(yytext);
                            return NUM;
                        }
{nl}                    return NL;
.                       /* ignore */

calc.y

%{
#include <iostream>

int yylex(void);
void yyerror(char const *);
%}

%defines "calc_defines.h"

%union {
    double dval;
}

%token PLUS
%token MINUS
%token MULT
%token DIV
%token NL
%token <dval> NUM
%type <dval> exp

%%

input   : /* empty */
        | input line
        ;

line    : NL
        | exp NL { std::cout << "result = " << $1 << std::endl; }
        ;

exp     : NUM { $$ = $1; }
        | exp exp PLUS { $$ = $1 + $2; }
        | exp exp MINUS { $$ = $1 - $2; }
        ;

%%

void yyerror(char const *s)
{
    fprintf(stderr, "%s\n", s);
}

int main(void)
{
    return yyparse();
}

Makefile

calc: calc.y calc.l
    bison -o calc_parser.cpp calc.y
    flex -o calc_lexer.cpp calc.l
    g++ calc_parser.cpp calc_lexer.cpp -o calc

RPN калькулятор с переменными

calc.l

Добавим два новых токена для имен переменных и для присваивания.

%{
#include <cstdlib>
#include "calc_defines.h"
%}

%option noyywrap
%option debug

digit [0-9]
char  [a-zA-Z_]
nchar [a-zA-Z_0-9]
nl    [\r\n]

%%

"+"                     return PLUS;
"-"                     return MINUS;
"="                     return EQ;
{digit}*\.?{digit}+     {
                            yylval.dval = std::atof(yytext);
                            return NUM;
                        }
{char}{nchar}*          {
                            yylval.sval = new std::string(yytext);
                            return ID;
                        }
{nl}                    return NL;
.                       /* ignore */

calc.y

Добавим словарь variables, возможность сохранения имен переменных в %union, дополнительные токены и обработку переменных в грамматику.

%code requires {
#include <string>
}

%code {
#include <iostream>
#include <map>

int yylex(void);
void yyerror(char const *);

std::map<std::string, double> variables;
}

%defines "calc_defines.h"

%union {
    double dval;
    std::string* sval;
}

%token PLUS
%token MINUS
%token MULT
%token DIV
%token NL
%token EQ
%token <sval> ID
%token <dval> NUM
%type <dval> exp

%%

input   : /* empty */
        | input line
        ;

line    : NL
        | exp NL { std::cout << "result = " << $1 << std::endl; }
        | assign NL
        ;

assign  : ID EQ NUM { variables[*$1] = $3; delete $1; }
        ;

exp     : ID { $$ = variables[*$1]; delete $1; }
        | NUM { $$ = $1; }
        | exp exp PLUS { $$ = $1 + $2; }
        | exp exp MINUS { $$ = $1 - $2; }
        ;

%%

void yyerror(char const *s)
{
    fprintf(stderr, "%s\n", s);
}

int main(void)
{
    return yyparse();
}

Makefile

Добавим в Makefile создание calc.html и calc.xml с подробным описанием сгенерированного bison парсера.

calc: calc.y calc.l
    bison -o calc_parser.cpp calc.y
    flex -o calc_lexer.cpp calc.l
    g++ calc_parser.cpp calc_lexer.cpp -o calc

calc.html: calc.y
    bison -x -o calc_parser.cpp calc.y
    xsltproc /opt/local/share/bison/xslt/xml2xhtml.xsl calc.xml > calc.html

Домашнее задание

Компилятор из лямбда выражений с +, -, *, /, let, read, print в программу на языке C. Пример входа (не обязательно делать в точности так, воспринимайте просто как иллюстрацию):

(let ((a 1)(b (read))) (print (a) ))
(let ((a (read))(b (+ 1 3 4))) (print (+ a b)))