#include #include #include #include "parser.hpp" #include "runtime.hpp" #include "stack.hpp" #include "token.hpp" #include "value.hpp" namespace LambdaCalc { Parser::Exception::Exception(const Token& token, const std::string& message) { std::ostringstream osmsg; osmsg << "At " << token << ": " << message; msg = osmsg.str(); } Parser::Exception::~Exception() throw() {}; const char* Parser::Exception::what() const throw() { return msg.c_str(); } Parser::Parser(Lex& lex, SymbolTable& symtab) : lex(lex), symtab(symtab), tokenConsumed(true) { } FunctionPtr Parser::getFunction() throw(Exception) { getToken(); if (!lex.valid()) { return FunctionPtr(nullptr); } bindings.clear(); FunctionPtr f = parseExpression(); lex.markFinished(); return f; } void Parser::nextToken() { if (tokenConsumed) { token = lex.getToken(); } else { tokenConsumed = true; } } Token Parser::getToken() { if (tokenConsumed) { token = lex.getToken(); tokenConsumed = false; } return token; } /* All functions have exactly one parameter. Hence, the function call stack consists of one value per call. For lexical scoped variables, the parser has to compute the relative offset of a variable. Examples where we always look for the variable "x": Expression | bindings | offset | count ------------------------------------+----------+--------+------- (lambda x x) | x | 0 | 1 (lambda x (lambda y x)) | y, x | 1 | 2 (lambda x (lambda y (lambda z x))) | z, y, x | 2 | 3 (lambda x (lambda y (lambda x x))) | x, y, x | 0 | 1 ------------------------------------+----------+--------+------- findBinding returns the count which is 0 when varname is not found within bindings; in the latter case varname is then to be looked up in the global symbol table which is used for defines */ unsigned int Parser::findBinding(const std::string& varname) { unsigned int count = 0; for (auto& binding: bindings) { ++count; if (binding == varname) return count; } return 0; } FunctionPtr Parser::parseExpression() throw(Exception) { // expr --> identifier if (getToken().symbol == Token::IDENT) { std::string varname = getToken().identifier; nextToken(); unsigned int index = findBinding(varname); if (index) { return std::make_shared([=] (StackPtr sp) -> ValuePtr { return (*sp)[index-1]; }); } return std::make_shared([this,varname] (StackPtr sp) -> ValuePtr { ValuePtr value = symtab.get(varname); if (value) return value; throw RuntimeException("undefined variable: '" + varname + "'"); }); } // expr --> integer if (getToken().symbol == Token::INTEGER) { int integer = getToken().integer; nextToken(); return std::make_shared([=] (StackPtr sp) { return std::make_shared(integer); }); } // all other variants start with '(' if (getToken().symbol != Token::LPAREN) { throw Exception(getToken(), "identifier, integer or '(' expected"); } nextToken(); // expr --> '(' lambda identifier expr ')' if (getToken().symbol == Token::LAMBDA) { nextToken(); if (getToken().symbol != Token::IDENT) { throw Exception(getToken(), "variable expected"); } // open local scope with the variable and parse function body bindings.push_front(getToken().identifier); nextToken(); FunctionPtr value = parseExpression(); bindings.pop_front(); if (getToken().symbol != Token::RPAREN) { throw Exception(getToken(), "')' expected"); } nextToken(); FunctionPtr f = std::make_shared([=] (StackPtr sp) { return (*value)(sp); }); return std::make_shared([=] (StackPtr sp) { return std::make_shared(f, sp); }); } // expr --> '(' define identifier expr ')' if (getToken().symbol == Token::DEFINE) { nextToken(); if (getToken().symbol != Token::IDENT) { throw Exception(getToken(), "identifier expected"); } std::string name = getToken().identifier; nextToken(); FunctionPtr expr = parseExpression(); if (getToken().symbol != Token::RPAREN) { throw Exception(getToken(), "')' expected"); } nextToken(); return std::make_shared([=] (StackPtr sp) -> ValuePtr { ValuePtr value = (*expr)(sp); symtab.define(name, value); return value; }); } // expr --> '(' if expr expr expr')' if (getToken().symbol == Token::IF) { nextToken(); FunctionPtr condition = parseExpression(); FunctionPtr then_part = parseExpression(); FunctionPtr else_part = parseExpression(); if (getToken().symbol != Token::RPAREN) { throw Exception(getToken(), "')' expected"); } nextToken(); return std::make_shared([=] (StackPtr sp) -> ValuePtr { ValuePtr cond = (*condition)(sp); if (cond->get_type() != Value::INTEGER || cond->get_integer()) { return (*then_part)(sp); } else { return (*else_part)(sp); } }); } // expr --> '(' expr expr ')' FunctionPtr funexpr = parseExpression(); FunctionPtr paramexpr = parseExpression(); if (getToken().symbol != Token::RPAREN) { throw Exception(getToken(), "')' expected"); } nextToken(); return std::make_shared([=] (StackPtr sp) -> ValuePtr { ValuePtr f = (*funexpr)(sp); ValuePtr param = (*paramexpr)(sp); assert(param); if (f->get_type() != Value::FUNCTION) { throw RuntimeException("bad function call"); } FunctionPtr function = f->get_function(); StackPtr closure = f->get_closure(); StackPtr nested = std::make_shared(closure, param); return (*function)(nested); }); } } // namespace LambdaCalc