Skip to content

Instantly share code, notes, and snippets.

@caiorss

caiorss/formula.cpp Secret

Created November 21, 2022 21:39
Show Gist options
  • Save caiorss/b5c5dc8d940a5927159f9d48d7b43a0c to your computer and use it in GitHub Desktop.
Save caiorss/b5c5dc8d940a5927159f9d48d7b43a0c to your computer and use it in GitHub Desktop.
Download ZIP
Expression parser
Raw
formula.cpp
#include <iostream>
#include <sstream>
#include <string>
#include <cassert>
#include <map>
#include <vector>
#include <memory>
#include <functional>
#include <fstream>
#include <cmath>
#undef EOF
// Token Type
enum class Type
{
INT // Number - integer
, FLT // Number - floating point
, NPC // Number in percent ending with '%' character
, IDEN // Identifier
, BOOL // Boolean
, STR // String
, SYM // Symbol - starts with ':', for instance :asymbol
, NIL // Nil
, ADD // '+' operator
, SUB // '-'
, MUL // '*' multiplication operator
, DIV // '/' division operator
, MOD // '%' modulus operator
, POW // '^' power operator - example 2^3 = 8
, ASN // '=' assignment
, EQ // '==' equal
, NEQ // '!=' not equal
, LT // '<' less than
, GT // '>' greater than
, LTE // '<=' less or equal than
, GTE // '>=' greater or equal than
, NOT // '!' not - invert logical value
, OR // 'or' - or operator keyword
, AND // 'and' - and operator keyword
, FN // 'fn' - keyword for defining functions
, END // 'end' - keyword delimiter
, BEGIN // 'begin' keyword
, FOR // 'for' - keyword
, WHILE // 'while' - keyword
, IF // 'if' - keyword
, ELSE // 'else' - keyword
, THEN // 'then' - keyword
, DO // 'do' - keyword
, TO // 'to' - keyword (used in for-loop)
, BY // 'by' - keyword
, ARROW // '->' - token used short function defintion
// --- Delimiters --- //
, LPAR // Left parenthesis
, RPAR // Right parenthesis
, COM // ',' Comma
, SEM // ';' semicolon
, EOF // End of File
, ERR // Indicates lexer error
, NONE // Indicates an empty token, non initialized token.
};
enum class Oper
{
ADD, SUB, MUL, DIV, MOD, POW, NOT, EQ, NEQ, LT, LTE, GT, GTE, AND, OR, ERR
};
std::string operators[] = { "+", "-", "*", "/", "%", "^", "!" };
std::string operator_names[] = { "ADD", "SUB", "MUL", "DIV", "MOD", "POW", "NOT" };
// Converts token type to operator
Oper type_to_oper(Type t)
{
static auto map = std::map<Type, Oper> {
{Type::ADD, Oper::ADD}, {Type::SUB, Oper::SUB}, {Type::MUL, Oper::MUL}
,{Type::DIV, Oper::DIV}, {Type::MOD, Oper::MOD}, {Type::POW, Oper::POW}
,{Type::NOT, Oper::NOT}, {Type::EQ, Oper::EQ }, {Type::NEQ, Oper::NEQ}
,{Type::LT, Oper::LT }, {Type::LTE, Oper::LTE }, {Type::AND, Oper::AND}
,{Type::GT, Oper::GT}, {Type::GTE, Oper::GTE }, {Type::OR, Oper::OR }
};
return map.at(t);
}
std::string oper_to_name(Oper op)
{
static auto map = std::map<Oper, std::string> {
{Oper::ADD, "ADD"}, {Oper::SUB, "SUB" }, {Oper::MUL, "MUL"}
,{Oper::DIV, "DIV"}, {Oper::MOD, "MOD" }, {Oper::POW, "POW"}
,{Oper::NOT, "NOT"}, {Oper::EQ, "EQ" }, {Oper::NEQ, "NEQ"}
,{Oper::LT, "LT" }, {Oper::LTE, "LTE" }, {Oper::AND, "AND"}
,{Oper::GT, "GT" }, {Oper::GTE, "GTE" }, {Oper::OR, "OR" }
};
return map.at(op);
}
std::string oper_to_str(Oper op)
{
static auto map = std::map<Oper, std::string> {
{Oper::ADD, "+" }, {Oper::SUB, "-" }, {Oper::MUL, "*" }
,{Oper::DIV, "/" }, {Oper::MOD, "%" }, {Oper::POW, "^" }
,{Oper::NOT, "!" }, {Oper::EQ, "==" }, {Oper::NEQ, "!=" }
,{Oper::LT, "<" }, {Oper::LTE, "<=" }, {Oper::AND, "and"}
,{Oper::GT, ">" }, {Oper::GTE, ">=" }, {Oper::OR, "or" }
};
return map.at(op);
}
struct Token
{
Type type;
std::string text;
int begin;
int end;
int lin;
int col;
Token(){
type = Type::NONE;
text = "";
begin = end = lin = col = 0;
}
Token(Type type, std::string const& text, int begin, int end, int lin, int col)
: type(type), text(text), begin(begin), end(end), lin(lin), col(col){ }
bool isEOF(){ return type == Type::EOF; }
};
std::ostream& operator<<(std::ostream& os, Token const& tok)
{
static auto map = std::map<Type, std::string>{
{Type::INT, "INT"}, {Type::FLT, "FLT"}, {Type::IDEN, "IDEN"}, {Type::BOOL, "BOOL" }
,{Type::STR, "STR"}, {Type::NIL, "NIL"}, {Type::ADD, "ADD" }, {Type::SUB, "SUB" }
,{Type::MUL, "MUL"}, {Type::DIV, "DIV"}, {Type::MOD, "MOD" }, {Type::POW, "POW" }
,{Type::ASN, "ASN"}, {Type::EQ, "EQ" }, {Type::NEQ, "NEQ" }, {Type::LT, "LT" }
,{Type::GT, "GT" }, {Type::LTE, "LTE"}, {Type::GTE, "GTE" }, {Type::NOT, "NOT" }
,{Type::OR, "OR" }, {Type::AND, "AND"}, {Type::LPAR, "LPAR"}, {Type::RPAR, "RPAR" }
,{Type::COM, "COM"}, {Type::COM, "COM"}, {Type::SEM, "SEM" }, {Type::RPAR, "RPAR" }
,{Type::EOF, "EOF"}, {Type::ERR, "ERR"}, {Type::NONE, "NONE" }, {Type::FN, "FN" }
,{Type::WHILE, "WHILE"}, {Type::ARROW, "ARROW"}, {Type::END, "END"}, {Type::BEGIN, "BEGIN"}
,{Type::TO, "TO"}, {Type::NPC, "PEC"}
};
os << "Token( " << (int) tok.type << " ; type = " << map[tok.type] << " ; " << tok.text << "; "
<< " ; begin = " << tok.begin << " ; end = " << tok.end << " ) ";
return os;
}
class Tokenizer
{
std::istream& _is; // Input stream
char _chr = '\0'; // Current character
int _pos = 0; // Current position
int _col = 0; // current column
int _lin = 0; // current line
// Keywords database
std::map<std::string, Type> _keywords;
public:
Tokenizer(std::istream& is): _is(is)
{
this->next_chr();
add_keyword("true", Type::BOOL);
add_keyword("false", Type::BOOL);
add_keyword("nil", Type::NIL);
add_keyword("or", Type::OR);
add_keyword("and", Type::AND);
add_keyword("fn", Type::FN);
add_keyword("if", Type::IF);
add_keyword("do", Type::DO);
add_keyword("else", Type::ELSE);
add_keyword("then", Type::THEN);
add_keyword("begin", Type::BEGIN);
add_keyword("end", Type::END);
add_keyword("for", Type::FOR);
add_keyword("to", Type::TO);
add_keyword("by", Type::BY);
add_keyword("while", Type::WHILE);
}
void add_keyword(std::string const& keyword, Type type)
{
_keywords[keyword] = type;
}
// Returns true if at end of file
bool is_eof() const { return _is.eof(); }
char peek() const { return _is.peek(); }
// Advances to next character
char next_chr()
{
_chr = _is.get();
_pos++;
_col++;
// Assumes that characcter for new line
// always will be '\n' and never '\r\n' or '\r'
if(_chr == '\n'){
_col = 0;
_lin++;
}
return _chr;
}
bool match(char x)
{
if( _chr == x){ next_chr(); return true; }
return false;
}
// Generates an error token
Token error(std::string const& message)
{
return Token(Type::ERR, message, _pos, _pos, _lin, _col);
}
// Return all tokens
std::vector<Token> tokens()
{
std::vector<Token> toks;
Token tk;
while( tk.type != Type::EOF ){
tk = this->next_token();
if( tk.type == Type::EOF){ break; }
toks.push_back(tk);
}
return toks;
}
Token next_token()
{
// Ignore blank characters, such as white spaces, tabs and
// new line characters.
while( !is_eof() && std::isspace(_chr) ){
next_chr();
}
// std::fprintf(stderr, " [TRACE] _chr = %c \n", _chr);
if( is_eof() || _chr == '\0' ){ return Token(Type::EOF, "", _pos, _pos, _lin, _col); }
// Sanity checking
assert( !isspace(_chr) );
int begin = _pos - 1;
auto tok = next_delimiter();
if( tok.type != Type::NONE){ return tok; }
// Number => Integer or floating point
if( std::isdigit(_chr) || _chr == '.' ) { return next_number(); }
// Identifier or keyword
if (std::isalpha(_chr) || _chr == '_') { return next_identifier_or_keyword(); }
// Symbol literal
if( match(':') ) { return next_symbol(); }
// String literal
if (_chr == '"') { return next_string(); }
// Discard next character to avoid infinite loop
char ch = _chr;
next_chr();
// Return a tokenizer error value
return Token(Type::ERR, std::string("Edge case - tokenizer cannot match character: ") + ch , _pos, _pos, _lin, _col);
}
private:
Token next_delimiter()
{
int begin = _pos - 1;
if( match('(') ){ return Token(Type::LPAR, "(", begin, _pos - 1, _lin, _col); }
if( match(')') ){ return Token(Type::RPAR, ")", begin, _pos - 1, _lin, _col); }
if( match('+') ){ return Token(Type::ADD, "+", begin, _pos - 1, _lin, _col); }
if( match('-') ){
if( match('>') ){ return Token(Type::ARROW, "->", begin, _pos - 1, _lin, _col); }
return Token(Type::SUB, "-", begin, _pos - 1, _lin, _col);
}
if( match('*') ){ return Token(Type::MUL, "*", begin, _pos - 1, _lin, _col); }
if( match('/') ){
// Ingore comment until new line
if( match('/') )
{
while( !is_eof() && _chr != '\n' ){ next_chr(); }
return next_token();
}
return Token(Type::DIV, "/", begin, _pos - 1, _lin, _col);
}
if( match('^') ){ return Token(Type::POW, "^", begin, _pos - 1, _lin, _col); }
if( match(',') ){ return Token(Type::COM, ",", begin, _pos - 1, _lin, _col); }
if( match(';') ){ return Token(Type::SEM, ";", begin, _pos - 1, _lin, _col); }
if( match('=') ){
if( match('=') ){
return Token(Type::EQ, "==", begin, _pos, _lin, _col);
}
return Token(Type::ASN, "=", begin, _pos, _lin, _col);
}
if( match('>') ){
if( match('=') ){ return Token(Type::GTE, ">=", begin, _pos, _lin, _col); }
return Token(Type::GT, ">", begin, _pos, _lin, _col);
}
if( match('<') ){
if( match('=') ){ return Token(Type::LTE, "<=", begin, _pos, _lin, _col); }
return Token(Type::LT, "<", begin, _pos, _lin, _col);
}
if( match('!') ){
if( match('=') ){ return Token(Type::NEQ, "!=", begin, _pos, _lin, _col); }
return Token(Type::NOT, "!", begin, _pos, _lin, _col);
}
return Token(Type::NONE, "", begin, _pos, _lin, _col);
}
Token next_identifier_or_keyword()
{
std::string lexeme;
int begin = _pos - 1;
while (!is_eof() && (std::isalnum(_chr) || _chr == '_'))
{
lexeme = lexeme + _chr;
next_chr();
}
auto it = _keywords.find(lexeme);
if(it != _keywords.end()){
Type t = it->second;
return Token(t, lexeme, begin, _pos - 1, _lin, _col);
}
return Token(Type::IDEN, lexeme, begin, _pos - 1, _lin, _col);
}
Token next_symbol()
{
std::string lexeme;
// next_chr();
int begin = _pos - 1;
while (!is_eof() && (std::isalnum(_chr) || _chr == '_'))
{
lexeme = lexeme + _chr;
next_chr();
}
return Token(Type::SYM, lexeme, begin, _pos - 1, _lin, _col);
}
// Returns next string literal
Token next_string()
{
assert( _chr == '"');
std::string lexeme;
int begin = _pos - 1;
next_chr();
// std::fprintf(stderr, " [TRACE] Detect string literal\n");
while (!is_eof() && _chr != '"')
{
// Handle escape characters
if( match('\\') ){
if( match('n') ){ lexeme = lexeme + "\n"; continue; }
if( match('t') ){ lexeme = lexeme + "\t"; continue; }
if( match('r') ){ lexeme = lexeme + "\r"; continue; }
if( match('v') ){ lexeme = lexeme + "\v"; continue; }
if( match('"') ){ lexeme = lexeme + "\""; continue; }
if( match('\\') ){ lexeme = lexeme + "\\"; continue; }
return Token(Type::ERR, "Tokenizer error - invalid escape character.", _pos, _pos, _lin, _col);
}
lexeme = lexeme + _chr;
next_chr();
}
assert( _chr == '"' );
next_chr();
// std::fprintf(stderr, " [TRACE] _chr = %c \n", _chr);
return Token(Type::STR, lexeme, begin, _pos - 1, _lin, _col);
}
// Returns next integer
std::string next_int()
{
std::string lexeme = "";
while( std::isdigit(_chr) || _chr == '_' ){
lexeme = lexeme + _chr;
next_chr();
}
// std::fprintf(stderr, " [TRACE] next number = %s \n", lexeme.c_str());
return lexeme;
}
// Returns next number token
Token next_number()
{
std::string lexeme = "";
int begin = _pos - 1;
if(_chr != '.'){
lexeme = next_int();
}
// std::fprintf(stderr, "[TRACE] _chr = %c \n", _chr);
if(_chr != '.' && _chr != 'e' && _chr != 'E' )
{
if( match('%') ) { return Token(Type::NPC, lexeme, begin, _pos - 1, _lin, _col); }
return Token(Type::INT, lexeme, begin, _pos - 1, _lin, _col);
}
if( match('.') )
{
lexeme = lexeme + ".";
lexeme = lexeme + next_int();
}
// std::cout << " [TRACE] chr = " << _chr << std::endl;
// Floating point exponent
if( match('e') || match('E') )
{
// std::fprintf(stderr, "[TRACE] Found exponent \n");
lexeme = lexeme + "e";
// next_chr();
if( _chr != '-' && !std::isdigit(_chr) ){
return Token(Type::ERR, "Invalid floatitng point number: " + lexeme, begin, _pos -1, _lin, _col );
}
if( match('-') ){
lexeme = lexeme + "-";
}
if( !isdigit(_chr) ){
return Token(Type::ERR, "Invalid floatitng point number. Expected digit.", begin, _pos -1, _lin, _col );
}
lexeme = lexeme + next_int();
}
if( match('%') ) { return Token(Type::NPC, lexeme, begin, _pos - 1, _lin, _col); }
return Token(Type::FLT, lexeme, begin, _pos - 1, _lin, _col);
}
}; // ------ End of class Tokenizer ---------
// Forward declaration
struct AstNil;
struct AstInt;
struct AstFlt;
struct AstIden;
struct AstSym;
struct AstBool;
struct AstStr;
struct AstBinop;
struct AstUnop;
struct AstAsn;
struct AstCall;
struct AstDef;
struct AstIf;
struct AstWhile;
struct AstFor;
struct AstProg;
struct AstErr;
struct IAstVisitor{
virtual void visit(AstNil& ast) = 0;
virtual void visit(AstInt& ast) = 0;
virtual void visit(AstFlt& ast) = 0;
virtual void visit(AstIden& ast) = 0;
virtual void visit(AstSym& ast) = 0;
virtual void visit(AstBool& ast) = 0;
virtual void visit(AstStr& ast) = 0;
virtual void visit(AstBinop& ast) = 0;
virtual void visit(AstUnop& ast) = 0;
virtual void visit(AstAsn& ast) = 0;
virtual void visit(AstCall& ast) = 0;
virtual void visit(AstDef& ast) = 0;
virtual void visit(AstWhile& ast) = 0;
virtual void visit(AstIf& ast) = 0;
virtual void visit(AstFor& ast) = 0;
virtual void visit(AstProg& ast) = 0;
virtual void visit(AstErr& ast) = 0;
};
// Represents abstract syntax tree noes
struct Ast
{
int begin = 0;
int end = 0;
virtual ~Ast() = default;
/// Check if AST node is nil (null value)
virtual bool is_nil() const { return false; };
/// Check if AST node is number
virtual bool is_num() const { return false; };
/// Check if AST node is integer
virtual bool is_int() const { return false; };
/// Check if AST node is floating point
virtual bool is_flt() const { return false; };
/// Check if AST node is boolean
virtual bool is_bool() const { return false; };
/// Check if AST node is identifier
virtual bool is_iden() const { return false; };
/// Check if AST node is symbol
virtual bool is_sym() const { return false; };
/// Check if AST node is string
virtual bool is_str() const { return false; };
/// Check if AST node is binary operation
virtual bool is_binop() const { return false; };
/// Check if AST node is unary operation
virtual bool is_unop() const { return false; };
/// Check whether AST node is assignment
virtual bool is_asn() const { return false; };
/// Check whether AST node is an error
virtual bool is_err() const { return false; }
// Check if AST is function call
virtual bool is_call() const { return false; }
// Check if AST is function defintion
virtual bool is_def() const { return false; }
// Check if AST is if statement
virtual bool is_if() const { return false; }
// Check if AST is while statement
virtual bool is_while() const { return false; }
// Chekc if AST is for-loop statement
virtual bool is_for() const { return false; }
// Check if AST is program
virtual bool is_prog() const { return false; }
virtual int to_int() const { return -1; };
virtual double to_flt() const { return -1; };
virtual std::string to_str() const { return ""; };
virtual void accept(IAstVisitor& v) = 0;
};
// Nil AST node
struct AstNil: public Ast
{
bool is_nil() const override { return true; };
void accept(IAstVisitor& v) override { v.visit(*this); }
AstNil(){}
AstNil(int begin, int end)
{
this->begin = begin;
this->end = end;
}
};
// Integer AST node
struct AstInt: public Ast
{
int value;
AstInt(int value): value(value){ }
AstInt(int value, int begin, int end): value(value)
{
this->begin = begin;
this->end = end;
}
bool is_num() const override { return true; };
bool is_int() const override { return true; };
void accept(IAstVisitor& v) override { v.visit(*this); }
virtual int to_int() const override { return value; };
virtual double to_flt() const override { return value; };
};
// Floating point literal
struct AstFlt: public Ast
{
double value;
AstFlt(double value): value(value){ }
AstFlt(double value, int begin, int end): value(value)
{
this->begin = begin;
this->end = end;
}
bool is_num() const override { return true; };
bool is_flt() const override { return true; };
void accept(IAstVisitor& v) override { v.visit(*this); }
int to_int() const override { return value; };
double to_flt() const override { return value; };
};
// Identifier node
struct AstIden: public Ast
{
std::string value;
AstIden(std::string const& value): value(value){ }
AstIden(std::string const& value, int begin, int end): value(value)
{
this->begin = begin;
this->end = end;
}
bool is_iden() const override { return true; };
void accept(IAstVisitor& v) override { v.visit(*this); }
std::string to_str() const override { return value; };
};
// Symbol node - for isntance, :x, :y, :asymbol
struct AstSym: public Ast
{
std::string value;
AstSym(std::string const& value): value(value){ }
AstSym(std::string const& value, int begin, int end): value(value)
{
this->begin = begin;
this->end = end;
}
bool is_sym() const override { return true; };
void accept(IAstVisitor& v) override { v.visit(*this); }
std::string to_str() const override { return ":" + value; };
};
// Boolean literal
struct AstBool: public Ast
{
bool value;
AstBool(bool value): value(value){ }
AstBool(bool value, int begin, int end): value(value)
{
this->begin = begin;
this->end = end;
}
bool is_bool() const override { return true; };
void accept(IAstVisitor& v) override { v.visit(*this); }
};
// String literal AST node
struct AstStr: public Ast
{
std::string value;
AstStr(std::string const& value): value(value){ }
AstStr(std::string const& value, int begin, int end): value(value)
{
this->begin = begin;
this->end = end;
}
bool is_str() const override { return true; };
void accept(IAstVisitor& v) override { v.visit(*this); }
std::string to_str() const override { return value; };
};
// Binary operation such as: <node> + <node>
struct AstBinop: public Ast
{
// Operator
Oper op;
// Left-hand side
std::shared_ptr<Ast> lhs;
// Right-hand side
std::shared_ptr<Ast> rhs;
AstBinop(Oper op, std::shared_ptr<Ast> lhs, std::shared_ptr<Ast> rhs)
: op(op), lhs(lhs), rhs(rhs){ }
bool is_binop() const override { return true; }
void accept(IAstVisitor& v) override { v.visit(*this); }
};
// Unary operation such as: -<node> +<node> -200
struct AstUnop: public Ast
{
// Operator
Oper op;
// Left-hand side
std::shared_ptr<Ast> node;
AstUnop(Oper op, std::shared_ptr<Ast> node)
: op(op), node(node) { }
bool is_unop() const override { return true; }
void accept(IAstVisitor& v) override { v.visit(*this); }
};
// Assignment node ('=') - represents expressions such as
// x = 20; z = call(20, 1.25)
struct AstAsn: public Ast
{
// identifier (left-hand side) L-value
std::string iden;
// right-hand side of assignment R-value
std::shared_ptr<Ast> node;
AstAsn(std::string const& iden, std::shared_ptr<Ast> node)
: iden(iden), node(node) { }
bool is_asn() const override { return true; };
void accept(IAstVisitor& v) override { v.visit(*this); }
};
// Represents a function call
struct AstCall: public Ast
{
// identifier - AST or function name (identidier)
std::shared_ptr<Ast> iden;
// Function arguments
std::vector<std::shared_ptr<Ast>> args;
bool is_call() const override { return true; }
// Get function name
std::string name() const
{
if(iden->is_iden()){ return iden->to_str(); }
return "";
}
AstCall(){}
AstCall(std::shared_ptr<Ast> iden, std::vector<std::shared_ptr<Ast>> const& args)
: iden(iden), args(args) { }
AstCall(std::string const& name, std::vector<std::shared_ptr<Ast>> const& args)
: iden( std::make_shared<AstIden>(name) ), args(args) { }
void accept(IAstVisitor& v) override { v.visit(*this); }
};
// Function defintion
struct AstDef: public Ast
{
// identifier
std::string name;
// Function arguments
std::vector<std::string> args;
// Function body
std::vector<std::shared_ptr<Ast>> body;
bool is_def() const override { return true; }
AstDef(){}
void accept(IAstVisitor& v) override { v.visit(*this); }
};
struct AstIf: public Ast
{
// Condition of an if-else statement
std::shared_ptr<Ast> cond;
// Code block related to then statement
std::shared_ptr<AstProg> then_block;
// Coode block related to else statement
std::shared_ptr<AstProg> else_block;
bool is_if() const override { return true; }
AstIf(){}
void accept(IAstVisitor& v) override { v.visit(*this); }
};
struct AstWhile: public Ast
{
std::shared_ptr<Ast> cond;
// Function arguments
std::vector<std::shared_ptr<Ast>> block;
bool is_while() const override { return true; }
AstWhile(){}
void accept(IAstVisitor& v) override { v.visit(*this); }
};
// Represents a for-loop, for instance:
// for i=0 to 10 do print(i) end
// for i=10 to 0 by -2 do print(i) end
struct AstFor: public Ast
{
// For-loop variable
std::string var;
// For-loop lower limit
std::shared_ptr<Ast> lower = nullptr;
// For-loop upper limit
std::shared_ptr<Ast> upper = nullptr;
// For-loop step
std::shared_ptr<Ast> step = nullptr;
// Code block executed each cycle
// std::vector<std::shared_ptr<AST>> body{};
std::shared_ptr<AstProg> block = {};
bool is_for() const override { return true; }
AstFor(){}
void accept(IAstVisitor& v) override { v.visit(*this); }
};
// Represents a program - zero or more statements
struct AstProg: public Ast
{
// Function arguments
std::vector<std::shared_ptr<Ast>> statements;
AstProg(){}
AstProg(std::vector<std::shared_ptr<Ast>> const& statements)
: statements(statements) { }
bool is_prog() const override { return true; }
void accept(IAstVisitor& v) override { v.visit(*this); }
};
// Node returned by parser when there is an error
struct AstErr: public Ast
{
std::string message;
AstErr(){}
AstErr(std::string message): message(message){ }
bool is_err() const override { return true; }
std::string to_str() const override { return message ; };
void accept(IAstVisitor& v) override { v.visit(*this); }
};
struct Val;
struct ValErr;
/// Type alias for interpreter function
using InterpFunc = std::function<std::shared_ptr<Val> (std::vector<std::shared_ptr<Val>> const& args)>;
enum class ValType{
INT, FLT, SYM, STR, NIL, BOOL, FUN, ERR
};
// Represents all runtime values produced by the interpreter
struct Val
{
virtual ~Val() = default;
virtual ValType type() const = 0;
// Checks whether runtime value is a number
virtual bool is_num() const { return false; }
// Checks whether runtime value is int
virtual bool is_int() const { return false; }
// Checks whether runtime value is floating point number
virtual bool is_flt() const { return false; }
// Checks whether runtime value is string
virtual bool is_str() const { return false; }
// Checks whether runtime value is bool
virtual bool is_bool() const { return false; }
// Checks whether runtime value is symbpl
virtual bool is_sym() const { return false; }
// Checks whether runtime value is nil
virtual bool is_nil() const { return false; }
// Checks whether runtime value is error
virtual bool is_err() const { return false; }
// Checks whether value is a function
virtual bool is_fun() const { return false; }
// Convert runtime value to integer
virtual int to_int() const { return 0; }
// Convert runtime value to floating point
virtual double to_flt() const { return 0; }
// Convert value to string
virtual std::string to_str() const = 0 ;
// Convert value boolean - anything not nil or false (bool) is true
virtual bool to_bool() const = 0;
// It evaluates to true if function value is native (implemented in C++)
// The usage of this function makes no sense if the current value is
// not a function.
virtual bool is_native() const { return false; }
virtual void print(std::ostream& os) = 0;
virtual std::shared_ptr<Val>
call(std::vector<std::shared_ptr<Val>> const& args)
{
return nullptr;
}
friend std::ostream& operator<<(std::ostream& os, Val& val)
{ val.print(os); return os; }
};
struct Env {
std::map<std::string, std::shared_ptr<Val>> store;
std::shared_ptr<Env> outer = nullptr;
Env(){}
Env(std::shared_ptr<Env> outer): outer(outer) { }
std::shared_ptr<Val> get(std::string const& name)
{
auto it = store.find(name);
if(it != store.end()){ return it->second; }
if( outer == nullptr ){ return nullptr; }
auto res = outer->get(name);
return res;
}
void set(std::string const& name, std::shared_ptr<Val> value)
{
store[name] = value;
}
void clear(){ store.clear(); }
};
/// Reprents an integer number
struct ValInt : public Val
{
int value = 0;
ValInt(){}
ValInt(int value): value(value){}
ValType type() const override { return ValType::INT; }
bool is_num() const override { return true; }
bool is_int() const override { return true; }
std::string to_str() const override { return std::to_string(value); }
bool to_bool() const override { return true; }
int to_int() const override { return value; }
double to_flt() const override { return value; }
void print(std::ostream& os) override { os << value; }
};
// Represents a floating point number
struct ValFlt : public Val
{
double value = 0.0;
ValFlt(){}
ValFlt(double value): value(value){}
ValType type() const override { return ValType::FLT; }
bool is_num() const override { return true; }
bool is_flt() const override { return true; }
std::string to_str() const override { return std::to_string(value); }
bool to_bool() const override { return true; }
int to_int() const override { return value; }
double to_flt() const override { return value; }
void print(std::ostream& os) override { os << value; }
};
// Represents a string
struct ValStr: public Val
{
std::string value = "";
ValStr(){}
ValStr(std::string value): value(value){}
ValType type() const override { return ValType::STR; }
std::string to_str() const override { return value; }
bool to_bool() const override { return true; }
bool is_str() const override { return true; }
void print(std::ostream& os) override { os << '"' << value << '"'; }
};
// Represents a symbol
struct ValSym: public Val
{
std::string value = "";
ValSym(){}
ValSym(std::string value)
{
// Remove first character from string
if(value[0] == ':'){ value.erase(0, 1); }
this->value = value;
}
ValType type() const override { return ValType::SYM; }
std::string to_str() const override { return value; }
bool to_bool() const override { return true; }
bool is_sym() const override { return true; }
void print(std::ostream& os) override { os << ':' << value ; }
};
// Represents a boolean
struct ValBool: public Val
{
bool value = false;
ValBool(){}
ValBool(bool value): value(value){}
ValType type() const override { return ValType::BOOL; }
std::string to_str() const override { return value ? "true" : "false"; }
bool to_bool() const override { return value; }
bool is_bool() const override { return true; }
void print(std::ostream& os) override { os << (value ? "true" : "false" ) ;}
};
// Represents a nil
struct ValNil: public Val
{
ValNil(){}
ValType type() const override { return ValType::NIL; }
std::string to_str() const override { return "nil"; }
bool to_bool() const override { return false; }
bool is_nil() const override { return true; }
void print(std::ostream& os) override { os << "nil"; }
};
// Represents a runtime error (interpreter error)
struct ValErr: public Val
{
int code = 0;
std::string message = "";
ValErr(){}
ValErr(std::string message): message(message){ }
ValErr(int code, std::string message): code(code), message(message){ }
ValType type() const override { return ValType::ERR; }
std::string to_str() const override { return message; }
bool to_bool() const override { return false; }
bool is_err() const override { return true; }
void print(std::ostream& os) override { os << "ERROR - " << message ; }
};
// Represents a function at runtime
struct ValFun: public Val
{
// Function name or identifier
std::string name = "";
// Function description metadata
std::string desc = "";
// Function arguments names
std::vector<std::string> args = {};
// If true, this flag indicates that the function is implemented in C++
bool _is_native = false;
// Function body
AstProg body;
// Funcion implementation in C++
InterpFunc func = nullptr;
// Function environment
std::shared_ptr<Env> env = std::make_shared<Env>();
ValFun(){}
ValType type() const override { return ValType::FLT; }
// Convert value to string
std::string to_str() const override { return "<Function " + name + "() >"; } ;
bool is_fun() const override { return true; }
bool is_native() const override { return func != nullptr; }
// Convert value boolean - anything not nil or false (bool) is true
bool to_bool() const override { return true; }
void print(std::ostream& os) override
{
os << "<Function " << name << ">";
}
virtual std::shared_ptr<Val>
call(std::vector<std::shared_ptr<Val>> const& args) override
{
return this->func(args);
}
};
/// Print AST as Lisp-like S-expression
struct PrintSexpVisitor: public IAstVisitor
{
void visit(AstNil& ast) { std::cout << "nil"; }
void visit(AstInt& ast) { std::cout << ast.value; }
void visit(AstFlt& ast) { std::cout << ast.value; }
void visit(AstIden& ast) { std::cout << ast.value; }
void visit(AstSym& ast) { std::cout << ":" << ast.value; }
void visit(AstBool& ast) { std::cout << (ast.value ? "true" : "false"); }
void visit(AstStr& ast) { std::cout << '"' << ast.value << '"'; };
void visit(AstBinop& ast)
{
auto op = oper_to_str(ast.op);
std::cout << "(" << op;
std::cout << " ";
ast.lhs->accept(*this);
std::cout << " ";
ast.rhs->accept(*this);
std::cout << " )";
}
void visit(AstUnop& ast)
{
auto op = oper_to_str(ast.op);
std::cout << "(" << op;
std::cout << " ";
ast.node->accept(*this);
std::cout << ")";
}
void visit(AstAsn& ast)
{
std::cout << "(SET " << ast.iden;
std::cout << " ";
ast.node->accept(*this);
std::cout << ")";
}
void visit(AstCall& ast)
{
std::cout << "(CALL ";
ast.iden->accept(*this);
for(auto const& arg: ast.args)
{
std::cout << " ";
arg->accept(*this);
}
std::cout << ")";
}
void visit(AstDef& ast)
{
std::cout << "(FN " << ast.name << " ( ";
for(auto const& arg: ast.args) { std::cout << arg << " "; }
std::cout << ") ";
for(auto const& s: ast.body)
{
std::cout << " ";
s->accept(*this);
}
std::cout << ")";
}
void visit(AstIf& ast)
{
std::cout << "(IF ";
ast.cond->accept(*this);
ast.then_block->accept(*this);
ast.else_block->accept(*this);
std::cout << ")";
}
void visit(AstWhile& ast)
{
std::cout << "(WHILE ";
ast.cond->accept(*this);
std::cout << " (DO ";
for(auto& st: ast.block) {
st->accept(*this) ;
std::cout << " ";
}
std::cout << "))";
}
void visit(AstFor& ast)
{
std::cout << "(FOR " << ast.var;
std::cout << " ";
ast.lower->accept(*this);
std::cout << " ";
ast.upper->accept(*this);
std::cout << " ";
if( ast.step ){
ast.step->accept(*this);
std::cout << " ";
}
ast.block->accept(*this);
std::cout << ")";
}
void visit(AstProg& ast)
{
std::cout << "(DO ";
for(auto const& stat: ast.statements)
{
std::cout << "\n ";
stat->accept(*this);
}
std::cout << " \n)";
}
void visit(AstErr& ast){ std::cout << "(ERROR " << ast.to_str() << " )"; }
};
// Pretty print AST as infix expressions (no lisp-like S-Expressions)
// This procedure is useful for printing ASTs representing math expressions in math format (infix).
void pprint(const Ast& ast)
{
auto priority = [](Oper op) -> int
{
if(op == Oper::ADD || op == Oper::SUB){ return 3; }
if(op == Oper::MUL || op == Oper::DIV){ return 4; }
if(op == Oper::POW){ return 5; }
throw std::runtime_error( " Not implemented for operator: " + oper_to_str(op));
};
if( ast.is_int() ) { std::cout << ast.to_int(); }
else if( ast.is_flt() ) { std::cout << ast.to_flt(); }
else if( ast.is_iden() ) { std::cout << ast.to_str(); }
else if( ast.is_asn() )
{
auto n = static_cast<const AstAsn&>(ast);
std::cout << n.iden << " = ";
pprint(*n.node);
}
else if( ast.is_call() )
{
//std::fprintf(stderr, " [TRACE] Function call AST node \n");
auto n = static_cast<const AstCall&>(ast);
pprint(*n.iden);
std::cout << "(";
size_t k = n.args.size();
if( k > 0){
pprint(*n.args[0]);
}
for(size_t i = 1; i < n.args.size(); i++)
{
std::cout << ", ";
pprint(*n.args[i]);
}
std::cout << ")";
}
else if( ast.is_unop() )
{
auto n = static_cast<const AstUnop&>(ast);
auto op = n.op;
std::cout << oper_to_str(op);
if( n.node->is_num() || n.node->is_iden() || n.node->is_nil() || n.node->is_bool() )
{
pprint(*n.node);
}
if( n.node->is_binop() )
{
std::cout << "(";
pprint(*n.node);
std::cout << ")";
}
}
else if( ast.is_binop() )
{
auto n = static_cast<const AstBinop&>(ast);
auto op = n.op;
if( n.lhs->is_num() || n.lhs->is_iden() || n.lhs->is_unop() || n.lhs->is_call() )
{
pprint(*n.lhs);
}
if( n.lhs->is_binop())
{
auto lhs = std::static_pointer_cast<AstBinop>(n.lhs);
auto opn = lhs->op;
//if( (op == Oper::MUL || op == Oper::DIV) && (opn == Oper::ADD || opn == Oper::SUB) )
if( priority(op) > priority(opn) )
{
std::cout << "( ";
pprint(*lhs->lhs);
std::cout << " ";
std::cout << oper_to_str(opn);
std::cout << " ";
pprint(*lhs->rhs);
std::cout << " )";
} else {
pprint(*lhs);
}
}
std::cout << " " << oper_to_str(op) << " ";
if( n.rhs->is_num() || n.rhs->is_iden() || n.rhs->is_unop() || n.rhs->is_call() )
{
pprint(*n.rhs);
}
if( n.rhs->is_binop())
{
auto rhs = std::static_pointer_cast<AstBinop>(n.rhs);
auto opn = rhs->op;
//if( (op == Oper::MUL || op == Oper::DIV) && (opn == Oper::ADD || opn == Oper::SUB) )
if( priority(op) > priority(opn) )
{
std::cout << "( ";
pprint(*rhs->lhs);
std::cout << " ";
std::cout << oper_to_str(opn);
std::cout << " ";
pprint(*rhs->rhs);
std::cout << " )";
} else {
pprint(*rhs);
}
}
}
// std::cerr << " [ERROR] Not implemented for this AST node \n";
} // ---- End of pprint() function -----//
class Parser
{
Token _token;
std::vector<Token> _tokens;
int _idx;
public:
Parser()
{
_tokens = {};
_idx = 0;
}
void read(std::istream& is)
{
Tokenizer tok(is);
_tokens = tok.tokens();
_idx = 0;
this->next();
}
// Parse a program
std::shared_ptr<Ast> parse(std::string const& code)
{
std::stringstream ss(code);
read(ss);
return _parse_prog();
}
std::shared_ptr<Ast> parse(std::istream& is)
{
read(is);
return _parse_prog();
}
// Parse a single expression or statement
std::shared_ptr<Ast> parse_expr(std::string const& code)
{
std::stringstream ss(code);
this->read(ss);
return _parse_stat();
}
Token next()
{
// _token = _tokenizer.next_token();
// std::cerr << " [TRACE] token = " << _token << std::endl;
if( _idx == _tokens.size() )
{ _token = Token(Type::EOF, "", 0, 0, 0, 0); }
if( _idx < _tokens.size() ){
_token = _tokens[_idx];
_idx = _idx + 1;
}
return _token;
}
Token peek() const { return _token; }
bool is_eof(){ return _token.type == Type::EOF; }
bool check(Type type)
{ return _token.type == type; }
bool match(Type type)
{
if( _token.type == type ){
this->next();
return true;
}
return false;
}
void expect(Type type, std::string const& message)
{
if( _token.type == type ){
this->next();
return;
}
throw std::runtime_error(message);
}
std::shared_ptr<AstErr>
expect_token(Type type)
{
if( _token.type == type){
this->next();
return nullptr;
}
std::stringstream ss;
ss << "Expected token of type ";
if (type == Type::ASN ){ ss << "'=' (assignemnt)"; }
else if(type == Type::RPAR){ ss << "')' right/closing parenthesis"; }
else { ss << (int) type; }
ss << " but got token " << _token;
return std::make_shared<AstErr>(ss.str());
}
private:
// Replace string
std::string replace( const std::string& text, const std::string& rep, const std::string& subst )
{
std::string out = text;
// Find position of character matching the string
size_t i = out.find(rep);
while(i != std::string::npos){
out.replace(i, rep.size(), subst);
i = out.find(rep, i);
}
return out;
}
/// Parse atom
std::shared_ptr<Ast> _parse_atom()
{
auto tok = peek();
// Parse integer number
if( match(Type::INT) ){ return std::make_shared<AstInt>( std::stoi( replace(tok.text, "_", "") ), tok.begin, tok.end ); }
// Parse floating point number
if( match(Type::FLT) ){ return std::make_shared<AstFlt>( std::stod( replace(tok.text, "_", "") ), tok.begin, tok.end ); }
// Parse floating point number (in percent format)
if( match(Type::NPC) ){ return std::make_shared<AstFlt>( std::stod( replace(tok.text, "_", "") ) / 100.0, tok.begin, tok.end ); }
if( match(Type::NIL) ){ return std::make_shared<AstNil>( tok.begin, tok.end); }
if( match(Type::STR) ){ return std::make_shared<AstStr>( tok.text, tok.begin, tok.end ); }
if( match(Type::IDEN) ){ return std::make_shared<AstIden>( tok.text, tok.begin, tok.end ); }
if( match(Type::SYM) ){ return std::make_shared<AstSym>( tok.text, tok.begin, tok.end ); }
if( match(Type::BOOL) ){ return std::make_shared<AstBool>( tok.text == "true" ? true : false, tok.begin, tok.end ); }
if( _token.type == Type::FN ){ return _parse_def(); }
if( _token.type == Type::IF ){ return _parse_if(); }
int begin = _token.begin;
if( match(Type::LPAR) )
{
auto expr = this->_parse_expr();
//std::cout << " [TRACE] token = " << _token << std::endl;
int end = _token.end;
auto err = expect_token(Type::RPAR);
if(err != nullptr ){ return err; }
// expect(Type::RPAR, "Expected right/closing parenthesis");
expr->begin = begin;
expr->end = end;
return expr;
}
// throw std::runtime_error("Error: - atom() function - not implemented ");
std::stringstream ss;
ss << "ERROR - edge case found - atom() cannot be parserd => token = " << tok;
return std::make_shared<AstErr>(ss.str());
}
// Parse function call, example atan2(y, x)
// call: atom
// | IDEN "(" ( expr ( "," expr )* )? ")"
std::shared_ptr<Ast> _parse_call()
{
auto atom = this->_parse_atom();
if( atom->is_err() ){ return atom; }
if( !match(Type::LPAR) ) { return atom; }
int begin = atom->begin;
// Function arguments
auto args = std::vector<std::shared_ptr<Ast>>{};
// Function with zero arguments
if( match(Type::RPAR) )
{
auto _call = std::make_shared<AstCall>(atom, args);
_call->begin = begin;
_call->end = _token.end;
return _call;
}
auto arg = _parse_expr();
args.push_back(arg);
while( _token.type == Type::COM )
{
next();
arg = _parse_expr();
args.push_back(arg);
}
int end = _token.end;
auto err = expect_token(Type::RPAR);
if( err ){ return err; }
auto _call = std::make_shared<AstCall>(atom, args);
_call->begin = begin;
_call->end = end;
return _call;
}
// Parse power operation such as 2^3
std::shared_ptr<Ast> _parse_power()
{
auto lhs = _parse_call();
if( lhs->is_err() ){ return lhs; }
int begin = lhs->begin;
int end = lhs->end;
while( check(Type::POW) )
{
auto op = type_to_oper(_token.type);
next();
auto rhs = _parse_unary();
if( rhs->is_err() ){ return rhs; }
lhs = std::make_shared<AstBinop>(op, lhs, rhs);
end = lhs->end;
}
lhs->begin = begin;
lhs->end = end;
return lhs;
}
// Parse unary expressions such as: a, -a or +a
std::shared_ptr<Ast> _parse_unary()
{
auto tok = _token;
// std::cerr << " [TRACE] unary => token = " << tok << std::endl;
if( tok.type == Type::SUB || tok.type == Type::ADD || tok.type == Type::NOT)
{
int begin = tok.begin;
// std::fprintf(stdout, " [TRACE] unary =>> begin = %d ; end = %d \n"
// , tok.begin, tok.end);
auto oper = type_to_oper(tok.type);
next();
auto factor = _parse_unary();
if( factor->is_err() ){ return factor; }
int end = factor->end;
auto ast = std::make_shared<AstUnop>(oper, factor);
ast->begin = begin;
ast->end = end;
return ast;
}
return _parse_power();
}
// Parse multiplication and division expressions
// such as 10 * 20 or x / y
std::shared_ptr<Ast> _parse_factor()
{
auto lhs = _parse_unary();
if( lhs->is_err() ){ return lhs; }
while( _token.type == Type::MUL || _token.type == Type::DIV )
{
auto oper = type_to_oper(_token.type);
next();
auto rhs = _parse_unary();
if( rhs->is_err() ){ return rhs; }
int begin = lhs->begin;
lhs = std::make_shared<AstBinop>(oper, lhs, rhs);
lhs->begin = begin;
lhs->end = rhs->end;
}
// lhs->begin = begin;
// lhs->end = end;
return lhs;
}
// Parse arithmetic expressions, such as sum and subtraction expressions such as
// a + 10 ; a - b
std::shared_ptr<Ast> _parse_arithmetic()
{
auto lhs = _parse_factor();
if( lhs->is_err() ){ return lhs; }
while( _token.type == Type::ADD || _token.type == Type::SUB )
{
auto oper = type_to_oper(_token.type);
next();
auto rhs = _parse_factor();
if( rhs->is_err() ){ return rhs; }
int begin = lhs->begin;
lhs = std::make_shared<AstBinop>(oper, lhs, rhs);
lhs->begin = begin;
lhs->end = rhs->end;
}
return lhs;
}
// Parse comparison expressions
// x >= 10 ; x + 20 < 200
std::shared_ptr<Ast> _parse_comparison()
{
auto lhs = _parse_arithmetic();
if( lhs->is_err() ){ return lhs; }
while( _token.type == Type::LT || _token.type == Type::LTE
|| _token.type == Type::GT || _token.type == Type::GTE )
{
auto op = type_to_oper(_token.type);
next();
auto rhs = _parse_arithmetic();
if( rhs->is_err() ){ return rhs; }
int begin = lhs->begin;
lhs = std::make_shared<AstBinop>(op, lhs, rhs);
lhs->begin = begin;
lhs->end = rhs->end;
}
return lhs;
}
// Parse equality and inequality expressions
// a + 200 == 400 ; a > 10 == a > 20
std::shared_ptr<Ast> _parse_equality()
{
// return term1();
auto lhs = _parse_comparison();
if( lhs->is_err() ){ return lhs; }
while( _token.type == Type::EQ || _token.type == Type::NEQ )
{
auto op = type_to_oper(_token.type);
next();
auto rhs = _parse_comparison();
if( rhs->is_err() ){ return rhs; }
int begin = lhs->begin;
lhs = std::make_shared<AstBinop>(op, lhs, rhs);
lhs->begin = begin;
lhs->end = rhs->end;
}
return lhs;
}
// Parse logical expressions such as '10 > x and x > sqrt(y) or false'
std::shared_ptr<Ast> _parse_expr()
{
auto lhs = _parse_equality();
if( lhs->is_err() ){ return lhs; }
while( _token.type == Type::AND || _token.type == Type::OR )
{
auto op = type_to_oper(_token.type);
next();
auto rhs = _parse_equality();
if( rhs->is_err() ){ return rhs; }
int begin = lhs->begin;
lhs = std::make_shared<AstBinop>(op, lhs, rhs);
lhs->begin = begin;
lhs->end = rhs->end;
}
return lhs;
}
// Parse while-do-end statement
// For instance, this function parses this syntax:
//
// while i > 0 do
// print(i);
// i = i - 1;
// end
std::shared_ptr<Ast> _parse_while()
{
auto begin = _token.begin;
if( !match(Type::WHILE) )
{ return std::make_shared<AstErr>("Invalid while statement. Expected keyword 'while'"); }
auto cond = _parse_expr();
if( cond->is_err() ){ return cond; }
auto err = expect_token(Type::DO);
if( err ){ return err; }
auto block = std::vector<std::shared_ptr<Ast>>{};
while ( _token.type != Type::END )
{
auto stat = this->_parse_stat();
if( stat->is_err() ){ return stat; }
block.push_back(stat);
}
auto end = _token.end;
err = expect_token(Type::END);
if( err ){ return err; }
auto ast = std::make_shared<AstWhile>();
ast->begin = begin;
ast->end = end;
ast->cond = cond;
ast->block = block;
return ast;
}
// Parse for-statement
// Syntax example: for i = 0 to 10 by 2 do print(i) end
// Syntax example: for i = 0 to 10 do print(i) end
// Syntax: for <VAR> = <LOWER> to <UPPER> do <BLOCK>... end
// Syntax for <VAR> = <LOWER> to <UPPER> by <STEP> do <BLOCK>... end
std::shared_ptr<Ast> _parse_for()
{
auto begin = _token.begin;
if( !match(Type::FOR) )
{ return std::make_shared<AstErr>("Invalid FOR statement. Expected keyword 'for'"); }
auto atom = _parse_atom();
if(atom->is_err()){ return atom; }
if( !atom->is_iden() )
{ return std::make_shared<AstErr>("Invalid FOR statement. Expected identifier"); }
// For-loop variable
auto var = atom->to_str();
// Equal '=' sign
if( !match(Type::ASN) )
{ return std::make_shared<AstErr>("Invalid FOR statement. Expected '=' sign."); }
auto lower = _parse_expr();
if(lower->is_err()){ return lower; }
if( !match(Type::TO) )
{ return std::make_shared<AstErr>("Invalid FOR statement. Expected 'to' keyword."); }
auto upper = _parse_expr();
if(upper->is_err()){ return upper; }
auto step = std::shared_ptr<Ast>{nullptr};
if( match(Type::BY) ){
step = _parse_expr();
if( step->is_err() ){ return step; }
}
if( !match(Type::DO) )
{ return std::make_shared<AstErr>("Invalid FOR statement. Expected 'do' keyword."); }
auto block = std::vector<std::shared_ptr<Ast>>{};
while ( _token.type != Type::END )
{
auto stat = this->_parse_stat();
if( stat->is_err() ){ return stat; }
block.push_back(stat);
}
auto end = _token.end;
if( !match(Type::END) )
{ return std::make_shared<AstErr>("Invalid FOR statement. Expected 'end' keyword."); }
auto ast = std::make_shared<AstFor>();
ast->begin = begin;
ast->end = end;
ast->var = var;
ast->lower = lower;
ast->upper = upper;
ast->step = step;
ast->block = std::make_shared<AstProg>(block);
return ast;
}
std::shared_ptr<Ast> _parse_block()
{
auto block = std::vector<std::shared_ptr<Ast>>{};
auto begin = _token.begin;
while ( _token.type != Type::END && _token.type != Type::ELSE && _token.type != Type::END )
{
// parse statement
auto stat = this->_parse_stat();
// Abort computation if there is any error
if( stat->is_err() ){ return stat; }
block.push_back(stat);
}
auto end = _token.end;
//auto err = expect_token(Type::END);
//if( err ){ return err; }
auto ast = std::make_shared<AstProg>(block);
ast->begin = begin;
ast->end = end;
return ast;
}
/**
* @brief Parse if-else satements.
*
* Example => Parses statements such as:
*
* if x > 10 then
* print("Greater than 10")
* end
*
* z = if x < 0 then
* print("negative")
* :pos
* else
* print("Positive or zero")
* :neg_or_zero
* end
*
*/
std::shared_ptr<Ast> _parse_if()
{
// std::fprintf(stderr, " [TRACE] Enter _parse_if() \n");
auto begin = _token.begin;
if( !match(Type::IF) ){ return std::make_shared<AstErr>("Invalid if-else statement. Expected IF keyword."); }
auto cond = _parse_expr();
if( cond->is_err() ){ return cond; }
if( !match(Type::THEN) ){ return std::make_shared<AstErr>("Invalid if-else statement. Expected THEN keyword."); }
auto then_block = _parse_block();
if( then_block->is_err() ){ return then_block; }
auto ast = std::make_shared<AstIf>();
ast->begin = begin;
ast->then_block = std::static_pointer_cast<AstProg>(then_block);
ast->cond = cond;
ast->end = _token.end;
ast->else_block = std::make_shared<AstProg>();
if( match(Type::END) ) { return ast; }
if( !match(Type::ELSE) )
{ return std::make_shared<AstErr>("Invalid if-else statement. Expected ELSE keyword."); }
auto else_block = _parse_block();
if( else_block->is_err() ){ return else_block; }
if( !match(Type::END) )
{ return std::make_shared<AstErr>("Invalid if-else statement. Expected END keyword."); }
ast->else_block = std::static_pointer_cast<AstProg>(else_block);
ast->end = _token.end;
return ast;
}
// Parse function defintion
// Example:
// fn myfun (x, y) -> 2 * y + y
// myfun = fn(x, y) -> 2 * y + y
//
// fn myfun(x, y)
// z = x / 10;
// a = z - x;
// a + z // Last value of block is the return value
// end
//
// fn <identifier> "(" arg0, arg1, ..., argN-1 ")"
std::shared_ptr<Ast> _parse_def()
{
auto tok = _token;
if( !match(Type::FN) )
{ return std::make_shared<AstErr>("Invalid function defintion. Expected keyword 'fn'"); }
std::string name = "";
if( _token.type == Type::IDEN )
{
name = _token.text;
next();
// return std::make_shared<ASTErr>("Invalid function defintion. Expected identifier.");
}
if( !match(Type::LPAR) ){
return std::make_shared<AstErr>("Invalid function defintion. Expected left parenthesis '('.");
}
// Function with empty argument, example: fn myfun() -> 10 + random()
if( match(Type::RPAR) ){
auto out = std::make_shared<AstDef>();
out->name = name;
out->args = {};
if( match(Type::ARROW) )
{
auto expr = _parse_expr();
if( expr->is_err()){ return expr; }
out->body = { expr };
out->begin = tok.begin;
out->end = expr->end;
return out;
}
auto block = _parse_block();
if(block->is_err()){ return block; }
assert( block->is_prog() );
if( !match(Type::END) ){ return std::make_shared<AstErr>("Invalid function definition. Expected end keyword."); }
out->body = std::static_pointer_cast<AstProg>(block)->statements;
out->end = block->end;
return out;
}
auto arg0 = _parse_atom();
if( !arg0->is_iden() ){
return std::make_shared<AstErr>("Invalid function defintion. Expected identifier as argument.");
}
auto args = std::vector<std::string>{ arg0->to_str() };
while( _token.type == Type::COM){
next();
auto arg = _parse_atom();
if( !arg0->is_iden() ){
return std::make_shared<AstErr>("Invalid function defintion. Expected identifier as argument.");
}
args.push_back( arg->to_str() );
}
if( !match(Type::RPAR) ){
return std::make_shared<AstErr>("Invalid function defintion. Expected right parenthesis.");
}
auto out = std::make_shared<AstDef>();
out->name = name;
out->args = args;
out->begin = tok.begin;
if( match(Type::ARROW) ){
auto expr = _parse_expr();
if( expr->is_err()){ return expr; }
out->body = { expr };
out->end = expr->end;
return out;
}
// Parse multiple statements until an 'end' keyword is found
auto block = _parse_block();
if(block->is_err()){ return block; }
if( !match(Type::END) ){ return std::make_shared<AstErr>("Invalid function definition. Expected end keyword."); }
assert( block->is_prog() );
out->body = std::static_pointer_cast<AstProg>(block)->statements;
out->end = block->end;
return out;
}
// Parse statement
// stat: expr | IDEN '=' expr
std::shared_ptr<Ast> _parse_stat()
{
if( _token.type == Type::WHILE ){ return _parse_while(); }
if( _token.type == Type::FOR ){ return _parse_for(); }
// std::fprintf(stderr, " [TRACE] Enter stats() function \n");
int saved_idx = _idx;
auto saved_token = _token;
// int begin = atom->begin;
int begin = _token.begin;
auto atom = this->_parse_atom();
if( atom->is_err() || !atom->is_iden() || _token.type != Type::ASN )
{
// Backtrack parser - restoring its state
_idx = saved_idx;
_token = saved_token;
// attempt to parse an expression
auto expr = this->_parse_expr();
// expect(Type::SEM, "Expected semicolon");
// optional semicolon for avoid ambiguity
match(Type::SEM);
return expr;
}
expect(Type::ASN, "Expected assignment");
auto expr = this->_parse_expr();
if( expr->is_err() ){ return expr; }
int end = _token.end;
//expect(Type::SEM, "Expected semicolon");
// optional semicolon for avoid ambiguity
match(Type::SEM);
auto ast = std::make_shared<AstAsn>(atom->to_str(), expr);
ast->begin = begin;
ast->end = end;
return ast;
}
std::shared_ptr<Ast> _parse_prog()
{
auto statements = std::vector<std::shared_ptr<Ast>>{};
int begin = _token.begin;
int end = 0;
while ( _token.type != Type::EOF )
{
auto stat = this->_parse_stat();
if( stat->is_err() ){ return stat; }
end = stat->end;
statements.push_back(stat);
}
auto ast = std::make_shared<AstProg>(statements);
ast->begin = begin;
ast->end = end;
return ast;
}
}; // ----- End of class Parser ----------- //
std::string substring(std::string const& str, int begin, int end)
{
std::string out;
for(int k = begin; k < end; k++){
out = out + str[k];
}
return out;
}
// Interpreter - turns the AST into a runtime value
class Interp
{
std::shared_ptr<Env> _env;
bool verbose = false;
bool in_function = false;
std::string code = "";
public:
Interp()
{
_env = std::make_shared<Env>();
reset();
}
void set_verbose(bool flag) { verbose = flag; }
// Interpreter's RPL - Read-Print-Eval Loop (interactive shell)
void repl()
{
Parser parser;
PrintSexpVisitor printer;
this->set_verbose(false);
bool show_ast = false;
std::string line, command, arg;
auto ast = std::shared_ptr<Ast>{nullptr};
while( std::cin.good() )
{
std::cout << "\n $> ";
std::getline(std::cin, line);
if(line == ""){ continue; }
auto ss = std::stringstream(line);
ss >> command >> arg;
if(command == ":show_ast"){ show_ast = true; continue; }
if(command == ":hide_ast"){ show_ast = false; continue; }
if(command == ":quit" || line == ":q"){ break; }
if(command == ":reset"){ this->reset(); continue; }
// Allows entering a multi-line expression
if(command == ":block")
{
std::cerr << " [INFO] Enter multi-line expression mode. Type (;;) when you are done. \n";
auto text = std::string{};
while( std::cin.good() )
{
std::getline(std::cin, line);
if(line == ";;"){ break; }
text = text + line;
}
line = text;
}
if( command == ":load")
{
std::ifstream ifs(arg);
if( !ifs.good() ){
std::fprintf(stderr, " [ERROR] Unable to open file '%s' \n", arg.c_str());
continue;
}
ast = parser.parse(ifs);
} else {
ast = parser.parse(line);
}
assert( ast != nullptr );
if(show_ast){
// Print AST in SEXP (S-Expression) Lisp-like format
std::cout << " ast = ";
ast->accept(printer);
std::cout << '\n';
// Print AST in math-like infix notation
/// std::cout << " pprint(ast) = "; pprint(*ast); std::cout << '\n';
}
auto result = this->eval(*ast);
// Set answer variable
this->add_var("ans", result);
std::cout << " = " << *result << '\n';
}
}
void add_var(std::string name, double value)
{
auto val = std::make_shared<ValFlt>(value);
_env->set(name, val);
}
void add_var(std::string name, std::string value)
{
auto val = std::make_shared<ValStr>(value);
_env->set(name, val);
}
void add_var(std::string name, std::shared_ptr<Val> value)
{
_env->set(name, value);
}
// Add C++ native function to interpreter
void add_fun(std::string name, std::function<double (double)> fun)
{
auto fn = std::make_shared<ValFun>();
fn->name = name;
fn->args = { "x" };
fn->func = [=](std::vector<std::shared_ptr<Val>> const& args) -> std::shared_ptr<Val>
{
if( args.size() != 1){
return std::make_shared<ValErr>("Function expects 1 argument");
}
if( !args[0]->is_num() ){
return std::make_shared<ValErr>("Type mismatch - function expects number argument");
}
auto x = args[0]->to_flt();
auto y = fun(x);
return std::make_shared<ValFlt>(y);
};
_env->set(name, fn);
}
void add_fun(std::string name, InterpFunc func)
{
auto fn = std::make_shared<ValFun>();
fn->name = name;
fn->func = func;
_env->set(name, fn);
}
// Reset interpreter environment (state)
void reset()
{
_env->clear();
add_fun("inv", [](double x){ return 1.0 / x; } );
add_fun("abs", static_cast<double (*) (double)>(&std::abs) );
add_fun("cos", static_cast<double (*) (double)>(&std::cos) );
add_fun("sin", static_cast<double (*) (double)>(&std::sin) );
add_fun("tan", static_cast<double (*) (double)>(&std::tan) );
add_fun("exp", static_cast<double (*) (double)>(&std::exp) );
add_fun("sqrt", static_cast<double (*) (double)>(&std::sqrt) );
add_fun("log", static_cast<double (*) (double)>(&std::log) );
add_fun("log10", static_cast<double (*) (double)>(&std::log10) );
add_fun("log2", static_cast<double (*) (double)>(&std::log2) );
add_var("PI", 3.1415);
// version constant
add_var("version", "0.1");
// Load script file
add_fun("load", [self = this](std::vector<std::shared_ptr<Val>> const& args) -> std::shared_ptr<Val>
{
if( args.size() != 1 ){
return std::make_shared<ValErr>("Expects 1 argument of type string.");
}
auto file = args[0]->to_str();
std::ifstream ifs(file);
if( !ifs.good() ){
std::string text = " [ERROR] Unable to open file " + file;
return std::make_shared<ValErr>();
}
Parser parser;
auto ast = parser.parse(ifs);
return self->eval(*ast);
});
add_fun("print", [=](std::vector<std::shared_ptr<Val>> const& args) -> std::shared_ptr<Val>
{
for(auto const& a: args){ std::cout << a->to_str(); }
std::cout << '\n';
return std::make_shared<ValNil>();
});
add_fun("type", [=](std::vector<std::shared_ptr<Val>> const& args) -> std::shared_ptr<Val>
{
if( args.size() != 1 ){
return std::make_shared<ValErr>("Function type() expects 1 argument.");
}
if( args[0]->is_bool()){ return std::make_shared<ValSym>("bool"); }
if( args[0]->is_nil()){ return std::make_shared<ValSym>("nil"); }
if( args[0]->is_fun()){ return std::make_shared<ValSym>("fun"); }
if( args[0]->is_int()){ return std::make_shared<ValSym>("int"); }
if( args[0]->is_flt()){ return std::make_shared<ValSym>("flt"); }
if( args[0]->is_str()){ return std::make_shared<ValSym>("str"); }
if( args[0]->is_sym()){ return std::make_shared<ValSym>("sym"); }
return std::make_shared<ValErr>("Edge case - function type() edge case .");
});
add_fun("max", [=](std::vector<std::shared_ptr<Val>> const& args) -> std::shared_ptr<Val>
{
if( args.size() < 1 )
{ return std::make_shared<ValErr>("Function max() expects at least 1 argument."); }
if( !args[0]->is_num() )
{ return std::make_shared<ValErr>("Function max() expects number as argument."); }
auto max = args[0]->to_flt();
float x = max;
for(auto const& a: args){
if( !a->is_num() )
{ return std::make_shared<ValErr>("Function max() expects number as argument."); }
x = a->to_flt();
if(max < x){ max = x;}
}
return std::make_shared<ValFlt>(max);
});
}
std::shared_ptr<Val> eval(std::string const &code)
{
Parser parser;
auto ast = parser.parse(code);
this->code = code;
return eval(*ast, _env);
}
std::shared_ptr<Val> eval(const Ast& ast)
{
return eval(ast, _env);
}
std::shared_ptr<Val> eval(const Ast& ast, std::shared_ptr<Env> env)
{
// Parser error
if (ast.is_err()) { return std::make_shared<ValErr>("Parser error - " + ast.to_str()); }
if (ast.is_nil()) { return std::make_shared<ValNil>(); }
if (ast.is_int()) { return std::make_shared<ValInt>(ast.to_int()); }
if (ast.is_flt()) { return std::make_shared<ValFlt>(ast.to_flt()); }
if (ast.is_bool())
{
//auto it = std::static_pointer_cast<ASTBool>(ast);
auto it = static_cast<AstBool const&>(ast);
return std::make_shared<ValBool>(it.value);
}
if (ast.is_str()) { return std::make_shared<ValStr>(ast.to_str()); }
if (ast.is_sym()) { return std::make_shared<ValSym>(ast.to_str()); }
if (ast.is_binop())
{
// auto it = std::static_pointer_cast<ASTBinop>(ast);
auto it = static_cast<AstBinop const&>(ast);
return eval_binop(it, env);
}
if (ast.is_unop())
{
// auto it = std::static_pointer_cast<ASTUnop>(ast);
// auto it = static_cast<ASTUnop const&>(ast);
auto it = static_cast<AstUnop const&>(ast);
return eval_unop(it, env);
}
if (ast.is_asn())
{
//auto it = std::static_pointer_cast<ASTAsn>(ast);
auto it = static_cast<AstAsn const&>(ast);
return eval_asn(it, env);
}
if (ast.is_iden())
{
auto name = ast.to_str();
auto val = env->get(name);
if (val == nullptr)
{
return std::make_shared<ValErr>("Unbound variable " + name);
}
return val;
}
if (ast.is_prog())
{
//auto it = std::static_pointer_cast<ASTProg>(ast);
auto it = static_cast<AstProg const&>(ast);
return eval_prog(it, env);
}
if (ast.is_call())
{
//auto it = std::static_pointer_cast<ASTCall>(ast);
auto it = static_cast<AstCall const&>(ast);
return eval_call(it, env);
}
if(ast.is_def())
{
//auto it = std::static_pointer_cast<ASTDef>(ast);
auto it = static_cast<AstDef const&>(ast);
return eval_def(it, env);
}
if(ast.is_if())
{
auto it = static_cast<AstIf const&>(ast);
return eval_if(it, env);
}
if(ast.is_while())
{
//auto it = std::static_pointer_cast<ASTWhile>(ast);
auto it = static_cast<AstWhile const&>(ast);
return eval_while(it, env);
}
if(ast.is_for())
{
//auto it = std::static_pointer_cast<ASTFor>(ast);
auto it = static_cast<AstFor const&>(ast);
return eval_for(it, env);
}
return std::make_shared<ValErr>("Interpreter not implemented for this AST type");
} // --- End of eval() ---- //
private:
// Equality operator evaluation
std::shared_ptr<Val> equal(Val const& lhs, Val const& rhs ) const
{
if( lhs.is_num() && rhs.is_num() )
{ return std::make_shared<ValBool>(lhs.to_flt() == rhs.to_flt() ); }
if( lhs.type() != rhs.type() ) { return std::make_shared<ValBool>( false); }
if( lhs.type() == ValType::STR && rhs.type() == ValType::STR )
{ return std::make_shared<ValBool>(lhs.to_str() == rhs.to_str() ); }
if( lhs.type() == ValType::SYM && rhs.type() == ValType::SYM )
{ return std::make_shared<ValBool>(lhs.to_str() == rhs.to_str() ); }
if( lhs.type() == ValType::BOOL && rhs.type() == ValType::BOOL )
{ return std::make_shared<ValBool>(lhs.to_bool() == rhs.to_bool() ); }
if( lhs.type() == ValType::NIL && rhs.type() == ValType::NIL )
{ return std::make_shared<ValBool>(true); }
return std::make_shared<ValErr>("Type mismatch. Invalid use case of operator (==).");
}
// Eval assignment operation
std::shared_ptr<Val> eval_asn(AstAsn const &ast, std::shared_ptr<Env> env)
{
auto value = eval(*ast.node, env);
if (value->is_err()) { return value; }
env->set(ast.iden, value);
return value;
}
// Eval unary operation
std::shared_ptr<Val> eval_unop(AstUnop const &ast, std::shared_ptr<Env> env)
{
auto node = eval(*ast.node, env);
if (node->is_err()) { return node; }
switch (ast.op)
{
case Oper::ADD:
return node;
break;
case Oper::SUB:
if (!node->is_num())
{ return std::make_shared<ValErr>("Negative operation is only valid for numbers"); }
if (node->is_int())
{ return std::make_shared<ValInt>(-node->to_int()); }
if (node->is_flt())
{ return std::make_shared<ValFlt>(-node->to_flt()); }
default:
return std::make_shared<ValErr>("Operation not defined for this operator: " + oper_to_str(ast.op));
}
}
// Eval binary operation
std::shared_ptr<Val> eval_binop(AstBinop const &ast, std::shared_ptr<Env> &env)
{
auto lhs = eval(*ast.lhs, env);
auto rhs = eval(*ast.rhs, env);
if (lhs->is_err()) { return lhs; }
if (rhs->is_err()) { return rhs; }
switch (ast.op)
{
case Oper::ADD:
if (lhs->is_flt() || rhs->is_flt())
{ return std::make_shared<ValFlt>(lhs->to_flt() + rhs->to_flt()); }
if (lhs->is_int() || rhs->is_int())
{ return std::make_shared<ValInt>(lhs->to_int() + rhs->to_int()); }
else if (lhs->is_str() || rhs->is_str())
{ return std::make_shared<ValStr>(lhs->to_str() + rhs->to_str()); }
else { return std::make_shared<ValErr>("Type mismatch (+) operator only valid for numbers or strings"); }
break;
case Oper::SUB:
if (!lhs->is_num() || !rhs->is_num())
{ return std::make_shared<ValErr>("Addition operation is only valid for numbers"); }
else if (lhs->is_flt() || rhs->is_flt())
{ return std::make_shared<ValFlt>(lhs->to_flt() - rhs->to_flt()); }
else
{ return std::make_shared<ValInt>(lhs->to_int() - rhs->to_int()); }
break;
case Oper::MUL:
if (!lhs->is_num() || !rhs->is_num())
{ return std::make_shared<ValErr>("Multiplication operation is only valid for numbers"); }
else if (lhs->is_flt() || rhs->is_flt())
{ return std::make_shared<ValFlt>(lhs->to_flt() * rhs->to_flt()); }
else
{ return std::make_shared<ValInt>(lhs->to_int() * rhs->to_int()); }
break;
case Oper::DIV:
if (!lhs->is_num() || !rhs->is_num())
{ return std::make_shared<ValErr>("Division operation not valid for non numbers"); }
return std::make_shared<ValFlt>(lhs->to_flt() / rhs->to_flt());
break;
// POwer operation a^b
case Oper::POW:
if (!lhs->is_num() || !rhs->is_num())
{ return std::make_shared<ValErr>("Power operation not valid for numbers"); }
return std::make_shared<ValFlt>(std::pow(lhs->to_flt(), rhs->to_flt()));
break;
// Less than => lhs < rhs
case Oper::LT:
if (!lhs->is_num() || !rhs->is_num())
{ return std::make_shared<ValErr>("Type mismatch. Less than (<) operator is only valid for numbers."); }
return std::make_shared<ValBool>(lhs->to_flt() < rhs->to_flt());
break;
// Greater than => lhs > rhs
case Oper::GT:
if (!lhs->is_num() || !rhs->is_num())
{ return std::make_shared<ValErr>("Type mismatch. Greater than (>) operator is only valid for numbers."); }
return std::make_shared<ValBool>(lhs->to_flt() > rhs->to_flt());
break;
// Less or equal than => lhs <= rhs
case Oper::LTE:
{
if (!lhs->is_num() || !rhs->is_num())
{ return std::make_shared<ValErr>("Type mismatch. Operator (<=) is only valid for numbers."); }
auto res = lhs->to_flt() <= rhs->to_flt();
return std::make_shared<ValBool>(res);
break;
}
// Greater or equal than or equal => lhs >= rhs
case Oper::GTE:
{
if (!lhs->is_num() || !rhs->is_num())
{ return std::make_shared<ValErr>("Type mismatch. Operator (>=) is only valid for numbers."); }
auto res = lhs->to_flt() >= rhs->to_flt();
return std::make_shared<ValBool>(res);
break;
}
// Equality operator: lhs == rhs
case Oper::EQ:
return this->equal(*lhs, *rhs);
break;
// Inequality operator: lhs != rhs
case Oper::NEQ: {
auto res = this->equal(*lhs, *rhs);
if( res->is_err() ){ return res; }
auto b = res->to_bool();
return std::make_shared<ValBool>(!b);
break;
}
case Oper::OR: {
if( !lhs->is_bool() || !rhs->is_bool() )
{ return std::make_shared<ValErr>("Or logical operator only valid for booleans."); }
return std::make_shared<ValBool>(lhs->to_bool() || rhs->to_bool() );
break;
}
case Oper::AND:
if( !lhs->is_bool() || !rhs->is_bool() )
{ return std::make_shared<ValErr>("And logical operator only valid for booleans."); }
return std::make_shared<ValBool>(lhs->to_bool() && rhs->to_bool() );
break;
default:
return std::make_shared<ValErr>("Binary operation not defined for this operator: " + oper_to_str(ast.op));
break;
}
} // ---- End of eval_binop() ------ //
std::shared_ptr<Val> eval_if(AstIf const &ast, std::shared_ptr<Env> env)
{
auto cond = eval(*ast.cond, env);
if( cond->is_err() ){ return cond; }
if( cond->to_bool() ){ return eval_prog(*ast.then_block, env); }
return eval_prog(*ast.else_block, env);
}
std::shared_ptr<Val> eval_while(AstWhile const &ast, std::shared_ptr<Env> env)
{
auto cond = eval(*ast.cond, env);
if(cond->is_err()){ return cond; }
while( cond->to_bool() )
{
for(auto& st: ast.block)
{
auto res = eval(*st, env);
if(res->is_err()){ return res; }
}
cond = eval(*ast.cond, env);
if(cond->is_err()){ return cond; }
}
return std::make_shared<ValNil>();
}
std::shared_ptr<Val> eval_for(AstFor const &ast, std::shared_ptr<Env> env)
{
auto lower = eval(*ast.lower, env);
if(lower->is_err()){ return lower; }
auto upper = eval(*ast.upper, env);
if(upper->is_err()){ return upper; }
auto step = std::shared_ptr<Val>{nullptr};
if( ast.step != nullptr ){
step = eval(*ast.step, env);
if(step->is_err()){ return step; }
}
if( !lower->is_num() ){ return std::make_shared<ValErr>("Expected number as for-loop lower limit"); }
if( !upper->is_num() ){ return std::make_shared<ValErr>("Expected number as for-loop upper limit"); }
if( step && !step->is_num() ){ return std::make_shared<ValErr>("Expected number as for-loop step"); }
auto lo = lower->to_int();
auto up = upper->to_int();
auto sp = step != nullptr ? step->to_int() : 1;
if( sp == 0 ) { return std::make_shared<ValErr>("Expected for-loop step to be non zero."); }
// Create temporary environment
auto tenv = std::make_shared<Env>(env);
if( lo <= up){
for(int k = lo; k < up; k = k + sp )
{
tenv->set(ast.var, std::make_shared<ValInt>(k));
eval(*ast.block, tenv);
}
} else {
if( sp > 0 ){ sp = -sp; }
for(int k = lo; k > up; k = k + sp )
{
tenv->set(ast.var, std::make_shared<ValInt>(k));
eval(*ast.block, tenv);
}
}
return std::make_shared<ValNil>();
}
// Eval program
std::shared_ptr<Val> eval_prog(AstProg const &ast, std::shared_ptr<Env> env)
{
std::shared_ptr<Val> res = std::make_shared<ValNil>();
for (auto &n : ast.statements)
{
res = eval(*n, env);
if (res->is_err())
{
return res;
}
if (verbose && !in_function)
{
auto s = substring(this->code, n->begin, n->end);
std::cout << " [*] " << s << " => " << *res << std::endl;
}
}
return res;
}
// Eval function defintion
std::shared_ptr<Val> eval_def(AstDef const &ast, std::shared_ptr<Env> env)
{
auto val = std::make_shared<ValFun>();
// std::fprintf(stderr, " [TRACE] Fundef => name = %s \n", ast.name.c_str());
val->name = ast.name;
val->args = ast.args;
val->_is_native = false;
val->body = ast.body;
val->env->outer = env;
// Only register non anonymous functions (non lambdas)
if( val->name != "" ){ env->set(val->name, val); }
return val;
// return std::make_shared<ValErr>("Not implemented for ASTDef");
}
// Eval function call
std::shared_ptr<Val> eval_call(AstCall const &ast, std::shared_ptr<Env> env)
{
// auto it = env.get(ast.name);
auto it = this->eval(*ast.iden, env);
//if ( it == nullptr )
//{ return std::make_shared<ValErr>("Function " + ast.name + " not defined"); }
if ( !it->is_fun() )
{ return std::make_shared<ValErr>("Object is not a function."); }
auto fun = std::static_pointer_cast<ValFun>(it);
// Vector containing evaluated function arguments
std::vector<std::shared_ptr<Val>> args;
args.reserve(ast.args.size());
// Evalute arguments before function application
for (auto &arg : ast.args)
{
// Evaluate function argument
auto res = this->eval(*arg, env);
// Abort computation if any error is found.
if (res->is_err()) { return res; }
args.push_back(res);
}
// Native function - implemented in C++
if( fun->func != nullptr )
{
auto res = fun->func(args);
return res;
}
// ---- Non native function ---------- //
// Create temporary enviroment.
if (ast.args.size() != fun->args.size())
{ return std::make_shared<ValErr>("Invalid number of arguments passed to function " + fun->name); }
auto tenv = std::make_shared<Env>(fun->env);
for (size_t i = 0; i < fun->args.size(); i++)
{ tenv->set(fun->args[i], args[i]); }
in_function = true;
// Evaluate function body using the temporary environment.
auto res = eval_prog(fun->body, tenv);
in_function = false;
return res;
}
}; // ---- End of class interp -------------- //
int main()
{
#if 1
printf("\n ============= Interpreter =============== \n");
Interp interp;
interp.set_verbose(true);
auto parser = Parser();
auto ast = parser.parse_expr(" z = - ( -20 + 8 * 10 / 25 ) - 3 * random() + 100 / sqrt( 5 * 10 + 3 * (20 - 7 + 8) + 3 ^ (2 * 3) ) * 15");
PrintSexpVisitor printer;
std::cout << " ast = ";
ast->accept(printer);
std::cout << "\n";
std::cout << " PPRINT => ";
pprint(*ast);
interp.repl();
#endif
return 0;
}
Raw
script.txt
print("\t[TRACE] Starting user script ")
print("\t[INFO] REPL Version = " + version)
// Function that computes square
fn sq(x) -> x * x
print("\n ------ Test IF-ELSE -------------")
x = -10
if x > 0 then
print(" => x greater than zero ")
else
print(" => x negative or zero ")
end
z = if x > 0 then
print(" => x greater than zero ")
100
else
print(" => x negative or zero ")
200
end
print(" [TRACE] z = ", z)
fn test_number(x)
if x < 0 then print(" => x = ", x, " => negative ") end
if x == 0 then print(" => x = ", x, " => zero ") end
if x > 0 then print(" => x = ", x, " => positive ") end
end
test_number(-10)
test_number(20)
test_number(0)
print("\n---------- WHILE LOOP ----------- ")
fn do_sum(i)
sum = 0;
// Start loop
while i > 0 do
i = i - 1;
sum = sum + sq(i);
print("\tsq(i) = ", sq(i));
end
print("\tsum = ", sum);
// The return value is the last function value
sum;
end
sum = do_sum(5)
print(" sum = do_sum(5) = ", sum)
print("\n---------- FOR LOOP ----------- ")
for i = 10 to 0 by -2 do
print(" \t i = ", i, " ; i^2 = ", i * i)
end
print("\n ------- CLOSURES ----------------------")
fn make_add(k) -> fn(x) -> k + x
add10 = make_add(10)
add20 = make_add(20)
add30 = make_add(30)
fn test_function(name, fun)
print("\n --- Testing function: ", name)
for k = 10 to 30 by 5 do
print("\t", name, "(", k,")", " = ", fun(k))
end
end
test_function("add10", add10)
test_function("add20", add20)
test_function("add30", add30)
Raw
xmake.lua
add_rules("mode.debug", "mode.release")
add_requires("glm", "glew", "glfw")
target("formula")
set_kind("binary")
add_files("./formula.cpp")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment