Search code examples
c++parsingyacc

FLEX/YACC carry variables between operations


I am building a calculator using YACC/FLEX as part of an assignment and am a little stuck. I would like to know how to carry previously solved variables from one equation to the next.

i.e., input would be summarized as follows :

11 x = 44 ;
y = (2 + 4*x);
y abc = 18;
4 z123 = (9*x -4*abc);
x _Inconnue = 12;

where the left side is a resolved term (nothing, or a number, or a previously solved variable) followed by an unsolved variable equals a properly formatted arithmetic expression that can contain only resolved terms and operators.

result should be

4
18
1
8
3

So far, my lex file looks like this :

%{
#include <iostream>
#include "y.tab.h"
extern "C" int yylex();
%}

%option yylineno

%%


[1-9]+                                                  { return NOMBRE;   }
[a-zA-Z_]([a-zA-Z0-9])*                                 { return INCONNUE; }
";"                                                     { return ';'; }
"="                                                     { return '='; }
"+"                                                     { return '+'; }
"*"                                                     { return '*'; }
"/"                                                     { return '/'; }
"-"                                                     { return '-'; }
"("                                                     { return '('; }
")"                                                     { return ')'; }
\n                                                      { ; }
[\t ]+                                                  { ; }
.                                                       { std::cout << "Caractere inconnu !" << std::endl;      }

%%

My yacc file so far looks like this :

%token NOMBRE INCONNUE ';' '=' '+' '*' '/' '-' '(' ')'

%left '+' '-'
%left '*' '/' '%'
%left '(' ')'

%start sys_eq

%{
#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstdint>
using namespace std;

/* Type des $$, $1, $2 etc. : */
#define YYSTYPE uint64_t

extern FILE *yyin;
extern char yytext[];
extern "C" int yylex();
int yyparse();
extern int yyerror(string);
extern int yylineno;

%}

%%

        sys_eq          : terme rest sys_eq    //a system of equations is a resolved term followed by the rest of the equations; there can be many systems within one system/file. 
                        |
                        ;

        rest            : eqn nl rest       //rest of the equations is a list of equations or nothing
                        |
                        ;

        eqn             : terme INCONNUE '=' expr_paren {if($1==0) {cout << atoi(yytext);} else cout << atoi(yytext)/$1;}
                        |
                        ;       //an equation is a resolved term followed by a variable, followed by '=' and an arithmetic expression

        expr_paren      : terme                         { $$ = $1; }   //standard def for expr arith
                        | expr_paren '+' expr_paren     { $$ = $1 + $3; }
                        | expr_paren '-' expr_paren     { $$ = $1 - $3; }
                        | expr_paren '*' expr_paren     { $$ = $1 * $3; }
                        | expr_paren '/' expr_paren     { $$ = $1 / $3; }
                        | '(' expr_paren ')'            { $$ = $2; }
                        ;

        nl              : ';'                           {cout << endl;}
                        ;

        terme           : NOMBRE INCONNUE '=' NOMBRE {if($1 == 0){$$ = atoi(yytext);} else $$ = atoi(yytext)/$1;} nl
                        | NOMBRE {$$ = atoi(yytext);} nl     //a resolved term is a number or a number divided by another number (to solve the axiome equation that looks like 2 x = 4;)
                        |
                        ;


%%

int main(int argc,char **argv)
{
        ++argv, --argc;
        if(argc) yyin=fopen(argv[0], "r"); else yyin=stdin;

        yyparse(); // Analyse syntaxique

        return 0;
} // main()

int yyerror(string msg)
{
        cout << msg << " sur la ligne #"  << yylineno << endl; return 0;
} // yyerror()

Notes :

  1. I know i haven't added anything to output the results yet, but as long as i can calculate them correctly, i can handle printing them to the screen later. Don't need any help for that one.
  2. I know it is not accepted to use yytext in my yacc actions. Please ignore that, as using yytext in the yacc action is required for this problem. I know it's terrible.
  3. Yes, I am new to YACC/FLEX. I have read a lot about YACC to get to the code I have here, but I am struggling. It is very difficult to explain what I have tried after hours of ignorant trial and error. That is why i have tried to comment what each instruction SHOULD be doing in hopes that it will make the path i went down a little clearer.

The questions: Currently the code is clearly garbage but I can't see the issue.

  1. I am getting 2 shift/reduce conflicts and I don't really understand why. I know what the error means, but don't see why i'm guilty. why?
  2. A memory overrun error is returned on line 2 of the input file. what sort of infinite loop have i managed to create here?
  3. The real question I am struggling with is how to pass the answer from one line into an expression in the next line. If I could understand that, I think I would be able to solve the whole problem.

Solution

  • If you need to persist values with names, you basically need a map which associates names with values. Neither bison nor flex will help you with that, since it has nothing to do with parsing. But C++ is of great help, since its standard library includes both ordered and unordered map implementations. (I'd use unordered_map since there's no need to keep variable names in alphabetical order in your problem description. But either will work fine.)

    You will, of course, have to pass the variable name from the lexer to the parser and you won't be able to do that with your current rules unless you accept that you really can't use yytext in a parser action. (INCONNUE is not the last token read in either of those rules.)

    This is the same issue you have in the action for the first production for terme, which attempts to use the semantic values of the first NOMBREs as $1. That attempt will fail since your scanner did not fill in yylval before returning NOMBRE. And the yytext corresponding to the first NOMBRE is ancient history by the time that action executes. (Whether or not using yytext works for the second NOMBRE depends on the rest of the grammar.)

    There is a way to deal with this and if your professor insists on you using it, they really should have clearly explained it. ("Unit production" is what we'd say in English.) But frankly I think you should just do it the normal way, in your scanner, and explain to your prof that that's how it's done. Up to you.


    You're getting conflicts because you have

    eqn     : terme INCONNUE '=' expr_paren
            |
    

    And

    terme   : NOMBRE INCONNUE '=' NOMBRE { action; } nl
            | NOMBRE {$$ = atoi(yytext);} nl
            |
    

    With input starting NOMBRE INCONNUE it's impossible to know if the first production of terme will apply, in which case INCONNUE is part of terme and must be shifted, or the second production, in which case the INCONNUE is part of eqn and terme needs to be reduced now.

    Another conflict is produced right at the beginning of the input because terme can be empty.