I am writing a handwritten recursive descent parser as a self exercise. I'd like to see if an iterative approach is possible. Generally speaking, I'd like to know what mindset I should have in order to transform interdependent recursive functions into an iterative solution.
In my current minimal example, I have a list of Tokens (which is simply a type with a lexeme) and they are consumed via recursive descent to build an abstract syntax tree represented by a unique_ptr to an expression:
#include <string>
#include <memory>
#include <vector>
enum Type { Num, Add, Mul, LParen, RParen };
struct Token {
Type type;
std::string lexeme;
};
struct Expr {
Token token;
};
using AST = std::unique_ptr<Expr>;
struct Literal : public Expr {
double value;
};
struct Grouping : public Expr {
AST inner;
};
struct Binary : public Expr {
AST lhs, rhs;
};
using CIT = std::vector<Token>::const_iterator;
auto expression(CIT& it, CIT end) -> AST;
auto literal(CIT &it, CIT end) -> AST {
if (it != end and it->type == Type::Num) {
auto value = std::stod(it->lexeme);
auto token = *it++;
return std::make_unique<Literal>(Literal{ token, value });
}
else if (it != end and it->type == Type::LParen) {
auto token = *it++;
auto ast = std::make_unique<Grouping>(Grouping{ token, expression(it, end) });;
if (it != end and it->type == Type::RParen)
return ast;
else
throw "Mismatched parenthesis";
}
throw "Unable to parse literal";
}
auto multiplication(CIT &it, CIT end) -> AST {
auto ast = literal(it, end);
while (it != end and it->type == Type::Mul) {
auto token = *it++;
ast = std::make_unique<Binary>(Binary{ token, std::move(ast), literal(it, end) });
}
return ast;
}
auto addition(CIT &it, CIT end) -> AST {
auto ast = multiplication(it, end);
while (it != end and it->type == Type::Add) {
auto token = *it++;
ast = std::make_unique<Binary>(Binary{ token, std::move(ast), multiplication(it, end) });
}
return ast;
}
auto expression(CIT &it, CIT end) -> AST {
return addition(it, end);
}
int main() {
std::vector<Token> tokens = {
{ Type::Num, "5"},
{ Type::Add, "+"},
{ Type::LParen, "("},
{ Type::Num, "4"},
{ Type::Mul, "*"},
{ Type::Num, "3"},
{ Type::RParen, ")"},
};
auto it = tokens.begin();
auto ast = expression(it, tokens.end());
}
Here there is a circular dependency of recursive calls: addition depends on multiplication, multiplication depends on literal, and literal 'depends on' addition.
I'd like to see if there is a way to flatten these calls into a singular iterative call. My first thoughts were to loop through the tokens and do a switch case between the precedence of operators; however, I am unsure where to go come there.
Non-complete attempt:
auto parse(const std::vector<Token>& tokens) -> AST {
AST current;
enum class Precedent {
Addition, Multiplication, Literal
};
for (const auto& token : tokens) {
switch (precedent) {
case Precedent::Addition: {
???
} break;
case Precedent::Multiplication: {
???
} break;
case Precedent::Literal: {
???
} break;
}
}
return current;
}
I feel that I am missing some kind of stack as a lot of iterative solutions from recursive solutions appear to maintain a manual call-like stack.
Any hints would be appreciated.
Edit: I've reviewed the post referring to the duplicate, though I believe my question is different that the one linked. I am not trying to make a single recursive function into an iterative one, I am trying to make multiple recursive functions into a single iterative function. I hope that explains why I asked this question.
