Bison and Flex Assignments - Equilibrium

readme.md

Bison and Flex Assignments - Equilibrium

How to Compile

./compile_yacc.sh matrix_calculator.l matrix_calculator.y

Assignment Instruction

This chemical eq will be simplified to 2H2O2 -> 2H2O + O2. That is we won’t use subscript and ,instead, use the number directly. The output will be pairs of element and number. The listed element will be that of too much or too little in the equation. The number is greater than zero, if the corresponding element is too much in left hand side. The number is less than zero, if the corresponding element is too little in left hand side. And the magnitude will be the amount of the difference. If the difference is 0 in left hand and right hand side, the element don’t need to be listed. And also you need to print the result pairs in lexicographic order of the listed element for our judge’s easiness.

Sample 1

• Input

CH3C6H5 + 3HNO3 -> CH3C6(NO2)2 + H2O

• Output

H 6
N 1
O 4

Sample 2

• Input

C2(2O) -> C2O2

• Output

Invalid format

compile_yacc.sh

#!/bin/bash
if (("$#" < 2)) || (("$#" > 3)); then
    echo "Illegal number of arguments"
    exit 1
fi
bison -v -d -o "y.tab.c" $2
gcc -c -g -I.. "y.tab.c"
flex -o lex.yy.c $1
gcc -c -g -I.. lex.yy.c
if [ "$#" -eq 2 ]; then
    gcc -o a.out "y.tab.o" lex.yy.o -ll
elif [ "$#" -eq 3 ]; then
    gcc -o $3 "y.tab.o" lex.yy.o -ll
fi

equilibrium.lex

%{
    #include "y.tab.h"
    #include <string.h>
    void yyerror(const char *);
%}

%%
[0-9]+ {
    yylval.ival = atoi(yytext);
    return INTEGER;
}

[A-Z][a-z]? {
    yylval.elem = strdup(yytext);
    return ELEM;
}

"->" {
    return ARROW;
}

\n|"+"|"("|")" {
    return yytext[0];
}

[ \t]+ {
    ;
}

. {
    yyerror("invalid input");
}

%%

equilibrium.yacc

%{
    #include <stdio.h>
    #include <string.h>

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

/* This section defines the data type used in the `%union` section. */
%code requires {
    typedef struct {
        struct record {
            char* elem;
            int num;
        } table[100];
        size_t table_size;
    } dict;
}

/* This section defines the additional function using the data type in
 * `%code requires` section.
*/
%code provides {
    dict create_dict(void);
    void add_record(dict*, char*, int);
    dict merge_dict(dict, dict);
    dict diff_dict(dict, dict);
    void sort_dict(dict*);
    void show_dict(dict);
}

%union {
    int ival;
    char* elem;
    dict d;
}

/* declarations */
%token <ival> INTEGER
%token <elem> ELEM
%type <d> expr
%type <d> formula

/* precedences */
%left ARROW
%left '+'
%nonassoc '(' ')'
%nonassoc ELEM
%nonassoc INTEGER
%nonassoc REDUCE_FORMULA    // force `formula . formula` reduce instead of
                            // shifting

%%
line    : expr ARROW expr '\n'  {
                                    dict d = diff_dict($1, $3);
                                    sort_dict(&d);
                                    show_dict(d);
                                }
        ;

expr    : expr '+' expr         {$$ = merge_dict($1, $3);}
        | INTEGER formula       {   // factor of the compound
                                    size_t i;
                                    for (i = 0; i < $2.table_size; i++)
                                        $2.table[i].num *= $1;
                                    $$ = $2;
                                }
        | formula               {$$ = $1;}
        ;

formula : formula formula %prec REDUCE_FORMULA {
                                $$ = merge_dict($1, $2);
                                }
        | '(' formula ')' INTEGER {
                                    size_t i;
                                    for (i = 0; i < $2.table_size; i++)
                                        $2.table[i].num *= $4;
                                    $$ = $2;
                                }
        | '(' formula ')'       {$$ = $2;}
        | ELEM INTEGER          {
                                    dict d = create_dict();
                                    add_record(&d, $1, $2);
                                    $$ = d;
                                }
        | ELEM                  {
                                    dict d = create_dict();
                                    add_record(&d, $1, 1);
                                    $$ = d;
                                }
        ;

%%

void yyerror(const char *message) {
    printf("Invalid format\n");
}

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

dict create_dict(void)
{
    dict d;
    d.table_size = 0;
    return d;
}

void add_record(dict* d, char* elem, int num)
{
    size_t i;
    for (i = 0; i < d->table_size; i++)
        if (strcmp(d->table[i].elem, elem) == 0) {
            d->table[i].num += num;
            return;
        }
    // for-else (not finding the elem in table --> append new elem)
    d->table[d->table_size].elem = elem;
    d->table[d->table_size++].num = num;
}

dict merge_dict(dict d1, dict d2)
{
    size_t i;
    for (i = 0; i < d1.table_size; i++)
        add_record(&d2, d1.table[i].elem, d1.table[i].num);
    return d2;
}

dict diff_dict(dict d1, dict d2)
{
    size_t i, j;
    for (i = 0; i < d1.table_size; i++)
        for (j = 0; j < d2.table_size; j++)
            if (strcmp(d1.table[i].elem, d2.table[j].elem) == 0)
                d1.table[i].num -= d2.table[j].num;
    unsigned int in_dict;
    for (j = 0; j < d2.table_size; j++) {
        in_dict = 0;
        for (i = 0; i < d1.table_size; i++)
            if (strcmp(d1.table[i].elem, d2.table[j].elem) == 0) {
                in_dict = 1;
                break;
            }
        if (!in_dict)
            add_record(&d1, d2.table[j].elem, -d2.table[j].num);
    }
    return d1;
}

void sort_dict(dict* d)
{
    size_t i, j;
    struct record temp;
    for (i = 0; i < d->table_size - 1; i++)
        for (j = i + 1; j < d->table_size; j++)
            if (strcmp(d->table[i].elem, d->table[j].elem) > 0) {
                temp = d->table[i];
                d->table[i] = d->table[j];
                d->table[j] = temp;
            }
}

void show_dict(dict d)
{
    size_t i;
    for (i = 0; i < d.table_size; i++)
        if (d.table[i].num != 0)
            printf("%s %d\n", d.table[i].elem, d.table[i].num);
}

equilibrium_cpp.l

%{
    #include "equilibrium_cpp.tab.h"
    #include <string>
    void yyerror(const char *);
%}

%%
[0-9]+ {
    yylval.ival = atoi(yytext);
    return INTEGER;
}

[A-Z][a-z]? {
    std::string str(yytext);
    yylval.elem = str;
    return ELEM;
}

"->" {
    return ARROW;
}

\n|"+"|"("|")" {
    return yytext[0];
}

[ \t]+ {
    ;
}

. {
    yyerror("invalid input");
}

%%

equilibrium_cpp.y

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

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

    std::map<std::string, int> merge_map(std::map<std::string, int>, std::map<std::string, int>);
    std::map<std::string, int> diff_map(std::map<std::string, int>, std::map<std::string, int>);
    void print_map(std::map<std::string, int>);

    struct Type {
        int ival;
        std::string elem;
        std::map<std::string, int> dict;
    };
    
    #define YYSTYPE Type  // for cpp and c (bison itself) compatibility
}

/* This section defines the additional function using the data type in
 * `%code requires` section.
*/
%code provides {}

/* declarations */
%token <ival> INTEGER
%token <elem> ELEM
%type <dict> expr
%type <dict> formula

/* precedences */
%left ARROW
%left '+'
%nonassoc '(' ')'
%nonassoc ELEM
%nonassoc INTEGER
%nonassoc REDUCE_FORMULA    // force `formula . formula` reduce instead of
                            // shifting

%%
line    : expr ARROW expr '\n'  {print_map(diff_map($1, $3));}
        ;

expr    : expr '+' expr         {$$ = merge_map($1, $3);}
        | INTEGER formula       {   // factor of the compound
                                    for (std::map<std::string, int>::iterator it = $2.begin(); it != $2.end(); it++)
                                        it->second *= $1;
                                    $$ = $2;
                                }
        | formula               {$$ = $1;}
        ;

formula : formula formula %prec REDUCE_FORMULA {
                                $$ = merge_map($1, $2);
                                }
        | '(' formula ')' INTEGER {
                                    size_t i;
                                    for (std::map<std::string, int>::iterator it = $2.begin(); it != $2.end(); it++)
                                        it->second *= $4;
                                    $$ = $2;
                                }
        | '(' formula ')'       {$$ = $2;}
        | ELEM INTEGER          {
                                    std::map<std::string, int> m;
                                    m[$1] += $2;
                                    $$ = m;
                                }
        | ELEM                  {
                                    std::map<std::string, int> m;
                                    m[$1]++;
                                    $$ = m;
                                }
        ;

%%

void yyerror(const char *message) {
    std::cout << "Invalid format" << std::endl;
}

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

std::map<std::string, int> merge_map(std::map<std::string, int> map1,
                                      std::map<std::string, int> map2) {
    for (std::map<std::string, int>::iterator it = map2.begin(); it != map2.end(); it++)
        map1[it->first] += it->second;
    return map1;
}

std::map<std::string, int> diff_map(std::map<std::string, int> map1,
                                     std::map<std::string, int> map2) {
    for (std::map<std::string, int>::iterator it = map2.begin(); it != map2.end(); it++)
        map1[it->first] -= it->second;
    return map1;
}

void print_map(std::map<std::string, int> m) {
    for (std::map<std::string, int>::iterator it = m.begin(); it != m.end(); it++)
        if (it->second != 0)
            std::cout << it->first << " " << it->second << std::endl;
}