c++ - 将 ML 代码转换为 C++

Question

我找到了一个解析算法here ，但是它在 ML 中，我对它不太熟悉。为了更好地理解该算法，我试图将其翻译成命令式语言，如 C++。现在有一些我不确定或不太了解的事情。

这是一个用于解析后缀表达式的 header (据我所知，这在技术上不是 header ，而是一个匹配项，但我不熟悉功能术语):

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)。

Answer 1

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

This means that ipts is the head of the list ipts' and is a postfix operator?

不完全是。 as 匹配运算符实际上绑定(bind)不如 :: 这样的模式构造器紧密；添加适当的括号后，ipts 将成为完整列表，其中 RATOR ... 作为头部，ipts'(短一个元素)作为尾部:

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

Why is there another match inside (irator as...)?

此处 as 匹配运算符用于两个不同的目的:

1. ipts as (...::ipts') 和 irator as (_, _, POSTFIX) 模式用于保证变量 ipts 和 irator 涵盖特定子结构的内容，因此在函数体中保证 ipts 永远不会为空并且 irator 始终是后缀样式的 rator(否则 parse_postfix 的工作不是处理它)。

2. 作为一个小的性能增强。诺曼也可以写成例如

   parse_postfix(stack, (e, []),
                 RATOR (text, prec, POSTFIX) :: ipts') = ...
   

   然后每当他提到 irator 和 RATOR (text, prec, POSTFIX::ipts' 每当他引用 ipts 时。但这既更长，更难阅读，并且需要重新构造在引用 irator 时已经在内存中构造的值和 ipts(即减少复制)。

   相反，辅助函数noparens、值构造函数UNARY、异常ParseError等都是为了处理irator 为方便起见，直接使用三元组。

Does it remove it from the list or advances anyway? Or is ipts the remainder of the list when the operator irator is removed?

有时，几乎。 ipts' 是删除 irator 后列表的剩余部分，而 ipts 是未删除任何元素的完整列表。根据 ipts 或 ipts' 在 if-then-else 中被引用，一个元素是否被弹出。

I'm hoping that this part is corect with parse prefix but I don't know how about implementing the parse_postfix function.

我现在不能说。但有一件事是肯定的:如果坚持使用不可变数据结构，转换这些函数会简单得多。不过，它不会运行得那么快。