Mathematical expression evaluator (C++) Using Flex and Yacc

Question

Based on this question, I thought I should show how to implement an expression evaluator using Flex and Bison.

Updated: Here

Currently it does not handle releasing the expressions (I only spent an hour throwing it together).

Makefile

YACC            ?= bison
LEX             ?= flex
CXX             ?= g++

SRC             = exp.tab.cpp exp.lex.cpp Lexer.cpp Parser.cpp Expression.cpp main.cpp
OBJ             = $(patsubst %.cpp,%.o,$(SRC))

expression: $(OBJ)
    g++ -std=c++17 -o $@ $^

%.tab.cpp: %.y
    $(YACC) -o $@ -d $<

%.lex.cpp: %.l
    $(LEX) -t --c++ --header-file=$*.lex.h $< > $@

%.o:    %.cpp
    $(CXX) -std=c++17 -c $*.cpp

exp.l

%option c++
%option noyywrap
%option yyclass="Lexer"

%{

#undef YY_DECL
#define YY_DECL int Lexer::yylexWithAction()
#define IN_LEXER
#include "exp.tab.hpp"

%}

IdentifierObject    [a-z][A-Za-z0-9_]*
LiteralInteger      ([1-9][0-9]*)|(0)

WhiteSpace          [ \t\r]+
NewLine             \n


%%
\(                  {return '(';}
\)                  {return ')';}
\^                  {return '^';}
\+                  {return '+';}
\-                  {return '-';}
\*                  {return '*';}
\/                  {return '/';}
\=                  {return '=';}


{LiteralInteger}    {return yy::Parser::token::LITERAL_INTEGER;}
{IdentifierObject}  {return yy::Parser::token::IDENTIFIER_OBJECT;}

{WhiteSpace}        {/* Ignore */}
{NewLine}           {return '\n';}
.                   {throw std::runtime_error("Invalid Character");}

%%

exp.y

%skeleton "lalr1.cc"
%require "2.1a"
%defines
%define "parser_class_name" "Parser"

%{

#include "Lexer.h"
#include "Expression.h"

using ThorsAnvil::Anvil::Ice::Lexer;
using ThorsAnvil::Anvil::Ice::Expression;
using ThorsAnvil::Anvil::Ice::PowerExpression;
using ThorsAnvil::Anvil::Ice::AddExpression;
using ThorsAnvil::Anvil::Ice::SubExpression;
using ThorsAnvil::Anvil::Ice::MulExpression;
using ThorsAnvil::Anvil::Ice::DivExpression;
using ThorsAnvil::Anvil::Ice::LiteralIntExpression;
using ThorsAnvil::Anvil::Ice::IdentifierExpression;


//namespace ThorsAnvial::Anvil::Ice {
int yylex(void*, ThorsAnvil::Anvil::Ice::Lexer& lexer);
//}


%}


%parse-param {Lexer&        lexer}
%lex-param   {Lexer&        lexer}

%token                          IDENTIFIER_OBJECT
%token                          LITERAL_INTEGER
%type   <expression>            Expression
%type   <expression>            PowerExpression
%type   <expression>            AddExpression
%type   <expression>            MultExpression
%type   <expression>            PrimaryExpression
%type   <expression>            Literal
%type   <identifier>            Identifier

%union {
    Expression*                 expression;
    IdentifierExpression*       identifier;
};



%%

StatementList:          Statement
                    |   StatementList '\n' Statement

Statement:              Expression                                          {/*Empty*/}
                    |   Identifier '=' Expression                           {IdentifierExpression::addValue($1, $3);}

Expression:             PowerExpression                                     {$$ = $1;std::cerr << "Value: " << $1->evaluate() << "\n";}

PowerExpression:        AddExpression                                       {$$ = $1;}
                    |   PowerExpression '^' AddExpression                   {$$ = new PowerExpression($1, $3);}

AddExpression:          MultExpression                                      {$$ = $1;}
                    |   AddExpression '+' MultExpression                    {$$ = new AddExpression($1, $3);}
                    |   AddExpression '-' MultExpression                    {$$ = new SubExpression($1, $3);}

MultExpression:         PrimaryExpression                                   {$$ = $1;}
                    |   MultExpression '*' PrimaryExpression                {$$ = new MulExpression($1, $3);}
                    |   MultExpression '/' PrimaryExpression                {$$ = new DivExpression($1, $3);}

PrimaryExpression:      Literal                                             {$$ = $1;}
                    |   '(' Expression ')'                                  {$$ = $2;}
                    |   Identifier                                          {$$ = $1;}

Literal:                LITERAL_INTEGER                                     {$$ = new LiteralIntExpression(lexer.lexem());}

Identifier:             IDENTIFIER_OBJECT                                   {$$ = new IdentifierExpression(lexer.lexem());}

%%


int yylex(void*, Lexer& lexer)
{
    return lexer.yylexWithActionGo();
}

void yy::Parser::error(yy::location const& /*location*/, std::string const& msg)
{
    throw std::runtime_error(msg);
}

Lexer.h

#ifndef THORSANVIL_ANVIL_ICE_LEXER_H
#define THORSANVIL_ANVIL_ICE_LEXER_H

#ifndef IN_LEXER
#include <FlexLexer.h>
#endif

#include <string_view>

namespace ThorsAnvil::Anvil::Ice
{

class Lexer: public yyFlexLexer
{
    bool started;
    public:
        Lexer(std::istream& input = std::cin, std::ostream& output = std::cerr);
        std::string_view lexem() const;
        virtual int yylex() override {throw std::runtime_error("Wrong Lex Called");}
        virtual int yylexWithAction();
        int yylexWithActionGo() { started = true; return yylexWithAction(); }
};

}

#endif

Lexer.cpp

#include "Lexer.h"

using namespace ThorsAnvil::Anvil::Ice;

Lexer::Lexer(std::istream& input, std::ostream& output)
    : yyFlexLexer(&input, &output)
    , started(false)
{}

std::string_view Lexer::lexem() const
{
    int length = started ? YYLeng() : 0;
    std::string_view    tokenView(YYText(), length);
    while (tokenView.size() > 0 && tokenView[tokenView.size() - 1] == '\0')
    {
        tokenView.remove_suffix(1);
    }
    return tokenView;
}

Parser.h

#ifndef THORSANVIL_ANVIL_ICE_PARSER_H
#define THORSANVIL_ANVIL_ICE_PARSER_H

#include "exp.tab.hpp"
#include "Expression.h"

namespace ThorsAnvil::Anvil::Ice
{

class Lexer;
class Parser
{
    public:
        Parser(Lexer& lexer);
        bool parse();
    private:
        Lexer&          lexer;
        ::yy::Parser    parser;
};

}

#endif

Parser.cpp

#include "Parser.h"

using namespace ThorsAnvil::Anvil::Ice;

Parser::Parser(Lexer& lexer)
    : lexer(lexer)
    , parser(lexer)
    , result(result)
{}

bool Parser::parse()
{
    return parser.parse() == 0;
}

Expression.h

#ifndef THORSANVIL_ANVIL_ICE_EXPRESSION_H
#define THORSANVIL_ANVIL_ICE_EXPRESSION_H

#include <map>
#include <cmath>
#include <string>
#include <charconv>

namespace ThorsAnvil::Anvil::Ice
{

class Expression
{
    public:
        virtual ~Expression(){}
        virtual int evaluate() const = 0;
};
class BinaryExpression: public Expression
{
    Expression* lhs;
    Expression* rhs;
    public:
        BinaryExpression(Expression* lhs, Expression* rhs)
            : lhs(lhs)
            , rhs(rhs)
        {}
        int le() const {return lhs->evaluate();}
        int re() const {return rhs->evaluate();}
};

class PowerExpression: public BinaryExpression
{
    public:
        using BinaryExpression::BinaryExpression;
        virtual int evaluate() const { return std::pow(le(), re());}
};
class AddExpression: public BinaryExpression
{
    public:
        using BinaryExpression::BinaryExpression;
        virtual int evaluate() const {return le() + re();}
};
class SubExpression: public BinaryExpression
{
    public:
        using BinaryExpression::BinaryExpression;
        virtual int evaluate() const {return le() - re();}
};
class MulExpression: public BinaryExpression
{
    public:
        using BinaryExpression::BinaryExpression;
        virtual int evaluate() const {return le() * re();}
};
class DivExpression: public BinaryExpression
{
    public:
        using BinaryExpression::BinaryExpression;
        virtual int evaluate() const {return le() / re();}
};
class LiteralIntExpression: public Expression
{
    int value;
    public:
        LiteralIntExpression(std::string_view view)
            : value(0)
        {
            std::from_chars(std::begin(view), std::end(view), value);
        }
        virtual int evaluate() const {return value;}
};
class IdentifierExpression: public Expression
{
    static std::map<std::string, int>   valueMap;

    std::string identifier;
    public:
        IdentifierExpression(std::string_view view)
            : identifier(view)
        {}
        virtual int evaluate() const {return valueMap[identifier];}

        static void addValue(IdentifierExpression* exp, Expression* value)
        {
            valueMap[exp->identifier] = value->evaluate();
        }
};

}

#endif

Expression.cpp

#include "Expression.h"

std::map<std::string, int>   ThorsAnvil::Anvil::Ice::IdentifierExpression::valueMap;

main.cpp

#include "Lexer.h"
#include "Parser.h"
#include "Expression.h"

int main()
{
    using ThorsAnvil::Anvil::Ice::Lexer;
    using ThorsAnvil::Anvil::Ice::Parser;
    using ThorsAnvil::Anvil::Ice::Expression;

    Lexer       lexer(std::cin, std::cout);
    Parser      parser(lexer);

    try {
        parser.parse();
    }
    catch(std::exception const& e) {
        std::cerr << "Exception: " << e.what() << "\n";
    }
}

Wouldn't it handle releasing memory pretty much automatically if you changed the raw pointers to std::unique_ptr? — Daniel Schepler
– Daniel Schepler, Commented Sep 30, 2022 at 14:55
@DanielSchepler The trouble is that flex/yacc are not designed for advanced C++. They do not incorporate the move semantics required for unique_ptrs. — Loki Astari
– Loki Astari, Commented Sep 30, 2022 at 15:29
OK - in a situation like that, personally, I'd probably treat the Bison/Yacc infrastructure like a C (or legacy C++) API, and try to push uniqueptr.release() and capture(rawptr) as close to the boundary with that API as possible. Where template<typename T> std::unique_ptr<T> capture(T* rawptr) { return { rawptr }; } is a common template I like to use to signal where my code is taking ownership of a pointer from the C API. (Though at this point, I might be dangerously close to something that should be put in an answer instead of a comment...) — Daniel Schepler
– Daniel Schepler, Commented Sep 30, 2022 at 16:26
@DanielSchepler I have an update that handles the pointers: codereview.stackexchange.com/questions/280095/… — Loki Astari
– Loki Astari, Commented Sep 30, 2022 at 18:11

G. Sliepen · Accepted Answer · 2022-09-29 22:24:31Z

The Makefile can be improved a bit

The Makefile looks very reasonable, but there are a few things that can be improved:

Use $(CXX) instead of g++ for expression, just like you did for %.o.
It's great that you don't hardcode which binaries to use, but it's also common to use $(CXXFLAGS) and $(LDFLAGS) when compiling, and if $(CXXFLAGS) is not defined, set it to something like -O2 -Wall -g.
patsubst is a GNU make extension, you can avoid that by removing SRC and just defining: OBJ = exp.tab.o exp.lex.o Lexer.o ...
Add a clean rule and a corresponding .PHONY: clean.

Incorrect precedence for powers

From your grammer it seems that the power operator has a lower precedence than addition and subtraction, which is wrong.

Consider creating custom exceptions

Just like the in the code in the question you linked to, create custom exception classes that derive from std::runtime_error. This conveys extra information to the caller, and allows them to programmatically make a distinction between different parser errors without having to parse the what() text.

Check the return value of `std::from_chars()`

You are ignoring the return value of std::from_chars(). While LiteralIntExpressions is only called with a string that matches the LiteralInteger lexer rule, it is still possible that the provided number is out of the range of an int.

Check that identifiers exist when evaluating an expression

In IdentifierExpression::evaluate(), you don't check if a given identifier exists in valueMap first. You probably want to do that first and throw an exception if it doesn't exist, otherwise the program will continue but will return unexpected results.

Output never goes to `output`

While the constructor of Lexer takes a std::ostream reference that is supposed to be where the output is written to, you hardcoded the output to std::cerr in exp.y.

I also find it strange that you use std::cerr as the default output stream, it should just be std::cout.

Tie it all together

The code looks very clean, but in your example main() function you have to write a lot of lines just to parse the input. It would be nice if you can create a single function or class that takes care of setting up the Lexer and Parser objects. Ideally, just:

#include "ExpressionParser.h"

int main() {
    ThorsAnvil::Anvil::Ice::ExpressionParser::parse(std::cin, std::cout);
}

otherwise the program will continue but will return unexpected results: It will continue with using the value 0. But point taken. — Loki Astari
– Loki Astari, Commented Sep 29, 2022 at 23:27
All good points. Thanks. It just re-enforces one of my rules I broke. Unit test your results. Should have noticed that I got the pow precedence wrong. — Loki Astari
– Loki Astari, Commented Sep 29, 2022 at 23:29

Stack Exchange Network

Mathematical expression evaluator (C++) Using Flex and Yacc

Makefile

exp.l

exp.y

Lexer.h

Lexer.cpp

Parser.h

Parser.cpp

Expression.h

Expression.cpp

main.cpp

1 Answer 1

The Makefile can be improved a bit

Incorrect precedence for powers

Consider creating custom exceptions

Check the return value of `std::from_chars()`

Check that identifiers exist when evaluating an expression

Output never goes to `output`

Tie it all together

You must log in to answer this question.

Linked

Hot Network Questions

Mathematical expression evaluator (C++) Using Flex and Yacc

Makefile

exp.l

exp.y

Lexer.h

Lexer.cpp

Parser.h

Parser.cpp

Expression.h

Expression.cpp

main.cpp

1 Answer 1

The Makefile can be improved a bit

Incorrect precedence for powers

Consider creating custom exceptions

Check the return value of std::from_chars()

Check that identifiers exist when evaluating an expression

Output never goes to output

Tie it all together

You must log in to answer this question.

Linked

Related

Hot Network Questions

Check the return value of `std::from_chars()`

Output never goes to `output`