compiler.cpp
compiler/src/compiler.cpp · 57 line(s) · c
#include "sleela/compiler.hpp"
#include <fstream>
#include <limits>
#include <memory>
#include <sstream>
#include <stdexcept>
#include <unordered_map>
#include <utility>
namespace sleela::compiler { namespace {
enum class K{end,number,id,let_,print_,return_,plus,minus,mul,div,eq,semi,lp,rp,bad};
struct Tok{K k{K::end};std::string s;std::int64_t n{0};std::size_t l{1},c{1};};
class Lex{std::string_view s;std::size_t p=0,l=1,c=1;char at(std::size_t n=0)const{return p+n<s.size()?s[p+n]:'\0';}void step(){if(p<s.size()){++p;++c;}}static bool d(char x){return x>='0'&&x<='9';}static bool a(char x){return(x>='a'&&x<='z')||(x>='A'&&x<='Z');}
public:explicit Lex(std::string_view x):s(x){}std::vector<Tok> scan(std::vector<Diagnostic>&e){std::vector<Tok>v;while(p<s.size()){char x=at();if(x==' '||x=='\t'||x=='\r'){step();continue;}if(x=='\n'){step();++l;c=1;continue;}if(x=='/'&&at(1)=='/'){while(p<s.size()&&at()!='\n')step();continue;}auto ln=l,co=c;if(d(x)){std::string t;while(d(at())){t+=at();step();}try{std::size_t z=0;auto n=std::stoll(t,&z);if(z!=t.size())throw std::out_of_range("n");v.push_back({K::number,t,n,ln,co});}catch(...){e.push_back({ln,co,"integer literal out of range"});}continue;}if(a(x)||x=='_'){std::string t;while(a(at())||d(at())||at()=='_'){t+=at();step();}K k=t=="let"?K::let_:t=="print"?K::print_:t=="return"?K::return_:K::id;v.push_back({k,t,0,ln,co});continue;}K k=K::bad;switch(x){case '+':k=K::plus;break;case '-':k=K::minus;break;case '*':k=K::mul;break;case '/':k=K::div;break;case '=':k=K::eq;break;case ';':k=K::semi;break;case '(':k=K::lp;break;case ')':k=K::rp;break;default:break;}step();if(k==K::bad)e.push_back({ln,co,std::string("unexpected character '")+x+"'"});else v.push_back({k,std::string(1,x),0,ln,co});}v.push_back({K::end,"",0,l,c});return v;}};
struct E{enum class T{num,var,unary,binary}t{T::num};std::int64_t n=0;std::string name;K op{K::end};std::size_t l=1,c=1;std::unique_ptr<E>a,b;};
struct S{enum class T{decl,print,ret}t{T::print};std::string name;std::unique_ptr<E>e;std::size_t l=1,c=1;};
class Parse{std::vector<Tok>v;std::vector<Diagnostic>&d;std::size_t p=0;const Tok&peek()const{return v[p];}const Tok&prev()const{return v[p-1];}bool is(K k)const{return peek().k==k;}const Tok&step(){if(!is(K::end))++p;return prev();}bool take(K k){if(!is(k))return false;step();return true;}void err(const Tok&t,std::string m){d.push_back({t.l,t.c,std::move(m)});}bool need(K k,const char*m){if(take(k))return true;err(peek(),m);return false;}void sync(){while(!is(K::end)){if(prev().k==K::semi)return;if(is(K::let_)||is(K::print_)||is(K::return_))return;step();}}
std::unique_ptr<E> expr(){return add();}std::unique_ptr<E> add(){auto e=mul();while(take(K::plus)||take(K::minus)){auto o=prev();auto n=std::make_unique<E>();n->t=E::T::binary;n->op=o.k;n->l=o.l;n->c=o.c;n->a=std::move(e);n->b=mul();e=std::move(n);}return e;}std::unique_ptr<E> mul(){auto e=unary();while(take(K::mul)||take(K::div)){auto o=prev();auto n=std::make_unique<E>();n->t=E::T::binary;n->op=o.k;n->l=o.l;n->c=o.c;n->a=std::move(e);n->b=unary();e=std::move(n);}return e;}std::unique_ptr<E> unary(){if(take(K::minus)){auto o=prev();auto n=std::make_unique<E>();n->t=E::T::unary;n->op=o.k;n->l=o.l;n->c=o.c;n->a=unary();return n;}return primary();}std::unique_ptr<E> primary(){if(take(K::number)){auto n=std::make_unique<E>();n->t=E::T::num;n->n=prev().n;n->l=prev().l;n->c=prev().c;return n;}if(take(K::id)){auto n=std::make_unique<E>();n->t=E::T::var;n->name=prev().s;n->l=prev().l;n->c=prev().c;return n;}if(take(K::lp)){auto e=expr();need(K::rp,"expected ')'");return e;}err(peek(),"expected integer, variable, or parenthesized expression");auto n=std::make_unique<E>();n->l=peek().l;n->c=peek().c;if(!is(K::end))step();return n;}
public:Parse(std::vector<Tok>x,std::vector<Diagnostic>&z):v(std::move(x)),d(z){}std::vector<S> all(){std::vector<S>r;while(!is(K::end)){auto old=p;if(take(K::let_)){auto t=prev();S s;s.t=S::T::decl;s.l=t.l;s.c=t.c;if(!is(K::id)){err(peek(),"expected name after let");sync();continue;}s.name=step().s;need(K::eq,"expected '='");s.e=expr();need(K::semi,"expected ';'");r.push_back(std::move(s));}else if(take(K::print_)||take(K::return_)){auto t=prev();S s;s.t=t.k==K::print_?S::T::print:S::T::ret;s.l=t.l;s.c=t.c;s.e=expr();need(K::semi,"expected ';'");bool ret=s.t==S::T::ret;r.push_back(std::move(s));if(ret&&!is(K::end))err(peek(),"return must be final statement");}else{err(peek(),"expected let, print, or return");sync();}if(old==p&&!is(K::end))step();}return r;}};
class Lower{CompileResult&r;std::unordered_map<std::string,std::int64_t>vars;bool returned=false;void emit(OpCode o,std::int64_t n=0){r.code.push_back({o,n});}void ex(const E&e){switch(e.t){case E::T::num:emit(OpCode::push_integer,e.n);break;case E::T::var:{auto i=vars.find(e.name);if(i==vars.end()){r.diagnostics.push_back({e.l,e.c,"unknown variable '"+e.name+"'"});emit(OpCode::push_integer,0);}else emit(OpCode::load_local,i->second);break;}case E::T::unary:ex(*e.a);emit(OpCode::negate);break;case E::T::binary:ex(*e.a);ex(*e.b);switch(e.op){case K::plus:emit(OpCode::add);break;case K::minus:emit(OpCode::subtract);break;case K::mul:emit(OpCode::multiply);break;case K::div:emit(OpCode::divide);break;default:break;}}}
public:explicit Lower(CompileResult&x):r(x){}void all(const std::vector<S>&ss){for(const auto&s:ss){if(s.t==S::T::decl){if(vars.contains(s.name)){r.diagnostics.push_back({s.l,s.c,"duplicate variable '"+s.name+"'"});continue;}if(r.local_names.size()>=65536){r.diagnostics.push_back({s.l,s.c,"local variable limit exceeded (65536)"});continue;}ex(*s.e);auto slot=static_cast<std::int64_t>(r.local_names.size());r.local_names.push_back(s.name);vars[s.name]=slot;emit(OpCode::store_local,slot);}else if(s.t==S::T::print){ex(*s.e);emit(OpCode::print);}else{ex(*s.e);emit(OpCode::return_value);returned=true;}if(returned)break;}emit(OpCode::halt);}};
}
CompileResult compile(std::string_view src){CompileResult r;Lex l(src);auto ts=l.scan(r.diagnostics);if(!r.ok())return r;Parse p(std::move(ts),r.diagnostics);auto ss=p.all();if(!r.ok())return r;Lower lower(r);lower.all(ss);if(!r.ok()){r.code.clear();r.local_names.clear();}return r;}
RunResult run(const CompileResult&p){RunResult r;if(!p.ok()){r.error="cannot execute failed compilation";return r;}std::vector<std::int64_t>s,locals(p.local_names.size());auto push=[&](std::int64_t value){if(s.size()>=65536)throw std::runtime_error("stack overflow");s.push_back(value);};auto pop=[&](){if(s.empty())throw std::runtime_error("stack underflow");auto x=s.back();s.pop_back();return x;};try{for(const auto&i:p.code)switch(i.opcode){case OpCode::push_integer:push(i.operand);break;case OpCode::load_local:if(i.operand<0||static_cast<std::size_t>(i.operand)>=locals.size())throw std::runtime_error("invalid local slot");push(locals[static_cast<std::size_t>(i.operand)]);break;case OpCode::store_local:if(i.operand<0||static_cast<std::size_t>(i.operand)>=locals.size())throw std::runtime_error("invalid local slot");locals[static_cast<std::size_t>(i.operand)]=pop();break;case OpCode::add:{auto b=pop(),a=pop();if((b>0&&a>std::numeric_limits<std::int64_t>::max()-b)||(b<0&&a<std::numeric_limits<std::int64_t>::min()-b))throw std::runtime_error("addition overflow");push(a+b);break;}case OpCode::subtract:{auto b=pop(),a=pop();if((b<0&&a>std::numeric_limits<std::int64_t>::max()+b)||(b>0&&a<std::numeric_limits<std::int64_t>::min()+b))throw std::runtime_error("subtraction overflow");push(a-b);break;}case OpCode::multiply:{auto b=pop(),a=pop();if(a!=0&&b!=0){if((a==-1&&b==std::numeric_limits<std::int64_t>::min())||(b==-1&&a==std::numeric_limits<std::int64_t>::min()))throw std::runtime_error("multiplication overflow");if(a>0?(b>0?a>std::numeric_limits<std::int64_t>::max()/b:b<std::numeric_limits<std::int64_t>::min()/a):(b>0?a<std::numeric_limits<std::int64_t>::min()/b:(a!=0&&b<std::numeric_limits<std::int64_t>::max()/a)))throw std::runtime_error("multiplication overflow");}push(a*b);break;}case OpCode::divide:{auto b=pop(),a=pop();if(!b)throw std::runtime_error("division by zero");if(a==std::numeric_limits<std::int64_t>::min()&&b==-1)throw std::runtime_error("division overflow");push(a/b);break;}case OpCode::negate:{auto a=pop();if(a==std::numeric_limits<std::int64_t>::min())throw std::runtime_error("negation overflow");s.push_back(-a);break;}case OpCode::print:r.printed_values.push_back(pop());break;case OpCode::return_value:r.return_value=pop();return r;case OpCode::halt:return r;default:throw std::runtime_error("invalid opcode");}}catch(const std::exception&e){r.error=e.what();}return r;}
std::string disassemble(const CompileResult&p){std::ostringstream o;for(std::size_t n=0;n<p.code.size();++n){const auto&i=p.code[n];o<<n<<": ";switch(i.opcode){case OpCode::push_integer:o<<"PUSH_INT "<<i.operand;break;case OpCode::load_local:o<<"LOAD_LOCAL "<<i.operand;break;case OpCode::store_local:o<<"STORE_LOCAL "<<i.operand;break;case OpCode::add:o<<"ADD";break;case OpCode::subtract:o<<"SUB";break;case OpCode::multiply:o<<"MUL";break;case OpCode::divide:o<<"DIV";break;case OpCode::negate:o<<"NEG";break;case OpCode::print:o<<"PRINT";break;case OpCode::return_value:o<<"RETURN";break;case OpCode::halt:o<<"HALT";break;}o<<'\n';}return o.str();}
bool write_bytecode(const CompileResult&p,const std::filesystem::path&path,std::string&e){if(!p.ok()){e="refusing to emit failed compilation";return false;}if(p.code.size()>std::numeric_limits<std::uint32_t>::max()||p.local_names.size()>std::numeric_limits<std::uint32_t>::max()){e="bytecode exceeds SLBC container limits";return false;}std::ofstream f(path,std::ios::binary);if(!f){e="cannot open output: "+path.string();return false;}f.write("SLBC",4);std::uint16_t ver=1;f.write(reinterpret_cast<const char*>(&ver),sizeof ver);auto count=static_cast<std::uint32_t>(p.code.size()),locals=static_cast<std::uint32_t>(p.local_names.size());f.write(reinterpret_cast<const char*>(&count),sizeof count);f.write(reinterpret_cast<const char*>(&locals),sizeof locals);for(const auto&i:p.code){auto op=static_cast<std::uint8_t>(i.opcode);f.write(reinterpret_cast<const char*>(&op),sizeof op);f.write(reinterpret_cast<const char*>(&i.operand),sizeof i.operand);}if(!f){e="bytecode write failed";return false;}return true;}
bool write_native_source(const CompileResult&p,const std::filesystem::path&path,bool cpp,std::string&e){
if(!p.ok()){e="refusing native emission from failed compilation";return false;}
std::ofstream f(path,std::ios::binary);if(!f){e="cannot open native output: "+path.string();return false;}
f << "/* Generated by SLeeLa Native Compiler " << version << ". Experimental subset backend. */\n"
<< "#include <stdint.h>\n#include <stdio.h>\n#include <limits.h>\n#include <stddef.h>\n"
<< "typedef struct { unsigned char op; int64_t arg; } sl_insn;\n"
<< "static const sl_insn program[] = {\n";
for(const auto&i:p.code){const std::string operand=i.operand==std::numeric_limits<std::int64_t>::min()?"INT64_MIN":std::to_string(i.operand)+"LL";f << "{" << static_cast<unsigned>(i.opcode) << "," << operand << "},\n";}
f << "};\n#define SL_LOCAL_COUNT " << (p.local_names.empty()?1:p.local_names.size()) << "\n"
<< "static int sl_add(int64_t a,int64_t b,int64_t*r){if((b>0&&a>INT64_MAX-b)||(b<0&&a<INT64_MIN-b))return 0;*r=a+b;return 1;}\n"
<< "static int sl_sub(int64_t a,int64_t b,int64_t*r){if((b<0&&a>INT64_MAX+b)||(b>0&&a<INT64_MIN+b))return 0;*r=a-b;return 1;}\n"
<< "static int sl_mul(int64_t a,int64_t b,int64_t*r){if(a==0||b==0){*r=0;return 1;}if((a==-1&&b==INT64_MIN)||(b==-1&&a==INT64_MIN))return 0;if(a>0){if((b>0&&a>INT64_MAX/b)||(b<0&&b<INT64_MIN/a))return 0;}else{if((b>0&&a<INT64_MIN/b)||(b<0&&b<INT64_MAX/a))return 0;}*r=a*b;return 1;}\n"
<< "#define SL_PROGRAM_COUNT (sizeof(program)/sizeof(program[0]))\n"
<< "int main(void){static int64_t stack[65536],locals[SL_LOCAL_COUNT],ret;size_t sp=0,pc=0;for(;;){if(pc>=SL_PROGRAM_COUNT){fputs(\"program counter out of range\\n\",stderr);return 2;}sl_insn i=program[pc++];int64_t a,b,v;switch(i.op){"
<< "case 1:if(sp>=65536){fputs(\"stack overflow\\n\",stderr);return 2;}stack[sp++]=i.arg;break;"
<< "case 2:if(i.arg<0||(uint64_t)i.arg>=SL_LOCAL_COUNT){fputs(\"invalid local slot\\n\",stderr);return 2;}if(sp>=65536){fputs(\"stack overflow\\n\",stderr);return 2;}stack[sp++]=locals[i.arg];break;"
<< "case 3:if(i.arg<0||(uint64_t)i.arg>=SL_LOCAL_COUNT){fputs(\"invalid local slot\\n\",stderr);return 2;}if(sp==0){fputs(\"stack underflow\\n\",stderr);return 2;}locals[i.arg]=stack[--sp];break;"
<< "case 4:case 5:case 6:case 7:if(sp<2){fputs(\"stack underflow\\n\",stderr);return 2;}b=stack[--sp];a=stack[--sp];"
<< "if(i.op==4){if(!sl_add(a,b,&v)){fputs(\"integer overflow\\n\",stderr);return 2;}}"
<< "else if(i.op==5){if(!sl_sub(a,b,&v)){fputs(\"integer overflow\\n\",stderr);return 2;}}"
<< "else if(i.op==6){if(!sl_mul(a,b,&v)){fputs(\"integer overflow\\n\",stderr);return 2;}}"
<< "else{if(b==0){fputs(\"division by zero\\n\",stderr);return 2;}if(a==INT64_MIN&&b==-1){fputs(\"integer overflow\\n\",stderr);return 2;}v=a/b;}stack[sp++]=v;break;"
<< "case 8:if(sp==0){fputs(\"stack underflow\\n\",stderr);return 2;}if(stack[sp-1]==INT64_MIN){fputs(\"integer overflow\\n\",stderr);return 2;}stack[sp-1]=-stack[sp-1];break;"
<< "case 9:if(sp==0){fputs(\"stack underflow\\n\",stderr);return 2;}printf(\"%lld\\n\",(long long)stack[--sp]);break;"
<< "case 10:if(sp==0){fputs(\"stack underflow\\n\",stderr);return 2;}ret=stack[--sp];return (int)((uint64_t)ret&255u);"
<< "case 255:return (int)((uint64_t)ret&255u);default:fputs(\"invalid opcode\\n\",stderr);return 2;}}}\n";
f.flush();if(!f){e="native source write failed: "+path.string();return false;}
(void)cpp;return true;
}
std::string read_text_file(const std::filesystem::path&p,std::string&e){std::ifstream f(p,std::ios::binary);if(!f){e="cannot open source: "+p.string();return {};}std::ostringstream o;o<<f.rdbuf();if(f.bad()){e="source read failed: "+p.string();return {};}return o.str();}
}