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";
}
}