sml — перевод кода ML в переполнение стека

Я нашел алгоритм разбора Вот, однако это в ML, и я не слишком знаком с этим. Для лучшего понимания алгоритма я пытаюсь перевести его на императивный язык, такой как C ++. Теперь есть несколько вещей, в которых я не уверен или не совсем понимаю.

Вот заголовок для разбора выражения postfix (AFAIK это технически не заголовок, а совпадение, но я не знаком с функциональными терминами):

parse_postfix(stack, (e, []),
ipts as RATOR (irator as (_, _, POSTFIX)) :: ipts') =

Это означает, что ipts является главой списка ipts' и это постфиксный оператор? Почему внутри другая спичка (irator as...)? Удаляет ли он его из списка или в любом случае? Или ipts Остальная часть списка, когда оператор irator устранен?

Мне трудно переводить это. Вот что я кодировал до сих пор:

#include <iostream>
#include <map>
#include <stack>
#include <string>
#include <vector>

enum Assoc { Left, Right, Noassoc };
enum Fixity { Prefix, Infix, Postfix };

struct Oper {
std::string Symbol;
int Precedence;
Fixity Fix;     // We can't represent bound types that way (INFIX <assoc>)
Assoc Asc;      // so we just make it have the operator anyway

Oper(std::string const& s, int p, Fixity f, Assoc a)
: Symbol(s), Precedence(p), Fix(f), Asc(a) { }
};

// A regular AST representation
struct Expr { };
struct ConstExpr : public Expr {
int Value;

ConstExpr(int i) : Value(i) { }
};
struct UryExpr : public Expr {
const Expr *Sub;
Oper *OP;

UryExpr(const Expr *s, Oper *o)
: Sub(s), OP(o) { }
};
struct BinExpr : public Expr {
const Expr *LHS, *RHS;
Oper *OP;

BinExpr(const Expr *l, const Expr *r, Oper *o)
: LHS(l), RHS(r), OP(o) { }
};

bool noparens(Oper *inner, Oper *outer, Assoc side) {
int pi = inner->Precedence, po = outer->Precedence;
Fixity fi = inner->Fix, fo = outer->Fix;
Assoc ai = inner->Asc, ao = outer->Asc;
if (pi > po) return true;
if (side == Left && fi == Postfix) return true;
if (side == Left && fi == Infix && ai == Left) return (fo == Infix && ao == Left);
if (side == Right && fi == Postfix) return true;
if (side == Right && fi == Infix && ai == Right) return (fo == Infix && ao == Right);
if (side == Noassoc) {
if (fi == Infix && fo == Infix) return ai == ao;
return fi == fo;
}
return false;
}

struct StackElem {
Oper *infixop;
const Expr *exp;
std::vector<Oper*> prefixes;

StackElem(Oper* i, const Expr* e, std::vector<Oper*> pref)
: infixop(i), exp(e), prefixes(pref) {}
};
std::map<std::string, Oper*> OperatorMap;
Oper *juxtarator = new Oper(" <juxtarator> ", 100, Infix, Left);
Oper *minrator = new Oper(" <minimal precedence operator> ", -1, Infix, Noassoc);
Oper *srator(std::stack<StackElem> const& st) { return (st.empty() ? minrator : st.top().infixop); }

Oper* get_op(std::string s) {
auto it = OperatorMap.find(s);
if (it == OperatorMap.end()) return nullptr;
return it->second;
}

Expr* parse_postfix(const std::stack<StackElem> stack, const Expr* e, const std::vector<Oper*> prefixes, const std::vector<std::string> ipts);

Expr* parse_prefix(const std::stack<StackElem> stack, const std::vector<Oper*> prefixes, const std::vector<std::string> ipts) {
if (!ipts.empty()) {
std::string head = ipts[0];
std::vector<std::string> tail(ipts.begin() + 1, ipts.end());

Oper* op = get_op(head);
if (!op) return parse_postfix(stack, new ConstExpr(std::atoi(head.c_str())), prefixes, tail);
if (op->Fix == Prefix) {
std::vector<Oper*> newprefix = prefixes;
newprefix.push_back(op);
return parse_prefix(stack, prefixes, tail);
}
else throw std::string("Lookahead is not a prefix operator");
}
else throw std::string("Premature EOF");
}

Expr* parse_postfix(const std::stack<StackElem> stack, const Expr* e, const std::vector<Oper*> prefixes, const std::vector<std::string> ipts)
{
if (prefixes.empty() && !ipts.empty()) {
std::string head = ipts[0];
std::vector<std::string> tail(ipts.begin() + 1, ipts.end());

Oper* irator = get_op(head);
if (irator) {
if (irator->Fix == Postfix) {
if (noparens(srator(stack), irator, Left)) {
if (!stack.empty()) {
StackElem el = stack.top();
std::stack<StackElem> stack_tail = stack;
stack_tail.pop();
return parse_postfix(stack_tail, new BinExpr(el.exp, e, el.infixop), el.prefixes, ipts);
}
else throw std::string("Impossible");
}
else if (noparens(irator, srator(stack), Right)) {
return parse_postfix(stack, new UryExpr(e, irator), std::vector<Oper*>(), tail);
}
else throw std::string("Non-associative");
}
else if (irator->Fix == Infix) {
if (noparens(srator(stack), irator, Left)) {
if (!stack.empty()) {
StackElem el = stack.top();
std::stack<StackElem> stack_tail = stack;
stack_tail.pop();
return parse_postfix(stack_tail, new BinExpr(el.exp, e, el.infixop), el.prefixes, ipts);
}
else throw std::string("Impossible");
}
else if (noparens(irator, srator(stack), Right)) {
std::stack<StackElem> newstack = stack;
newstack.push(StackElem(irator, e, std::vector<Oper*>()));
return parse_prefix(newstack, std::vector<Oper*>(), tail);
}
else throw std::string("Non-associative");
}
}
}
else if (!prefixes.empty() && !ipts.empty()) {
std::string head = ipts[0];
std::vector<std::string> tail(ipts.begin() + 1, ipts.end());
Oper* op = prefixes[0];
std::vector<Oper*> newprefixes(prefixes.begin() + 1, prefixes.end());

Oper* irator = get_op(head);
if (irator) {
if (irator->Fix == Postfix) {
if (noparens(op, irator, Noassoc)) {
return parse_postfix(stack, new UryExpr(e, op), newprefixes, ipts);
}
else if (noparens(irator, op, Noassoc)) {
return parse_postfix(stack, new UryExpr(e, irator), prefixes, tail);
}
else throw std::string("Equal precedence!");
}
else if (irator->Fix == Infix) {
if (noparens(op, irator, Noassoc)) {
parse_postfix(stack, new UryExpr(e, op), newprefixes, ipts);
}
else if (noparens(irator, op, Noassoc)) {
std::stack<StackElem> newstack = stack;
newstack.push(StackElem(irator, e, prefixes));
return parse_prefix(newstack, std::vector<Oper*>(), tail);
}
else throw std::string("Equal precedence!");
}
}
}

std::vector<std::string> nnip = ipts;
nnip.insert(nnip.begin(), juxtarator->Symbol);
return parse_postfix(stack, e, prefixes, nnip);
}

Expr* parse(std::vector<std::string> input) {
return parse_prefix(std::stack<StackElem>(), std::vector<Oper*>(), input);
}

int main(void)
{
OperatorMap.insert(std::make_pair(minrator->Symbol, minrator));
OperatorMap.insert(std::make_pair(juxtarator->Symbol, juxtarator));
OperatorMap.insert(std::make_pair("+", new Oper("+", 3, Infix, Left)));
std::vector<std::string> tokens = { "2", "+", "3" };
try {
Expr* e = parse(tokens);
}
catch (std::string err) {
std::cout << "Error: " << err << std::endl;
}

system("PAUSE");
return 0;
}

Я надеюсь, что эта часть является основной с префиксом разбора, но я не знаю, как насчет реализации parse_postfix функция.

Редактировать:

Теперь это попытка быть полной программой тестирования, но по какой-то причине она терпит неудачу, поскольку для входа «2» «+» «3» (или даже просто одного числа) вызывается исключение (преждевременный EOF).