-
-
Save caiorss/b5c5dc8d940a5927159f9d48d7b43a0c to your computer and use it in GitHub Desktop.
Expression parser
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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) | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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