Перевод кода ML на C++

Question

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

Вот заголовок для разбора выражения постфикса (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; 
} 

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

Edit:

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

Answer 1

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

Это означает, что ipts является главой списка ipts' и является оператором постфикс?

Не совсем. оператор сопоставления as фактически связывает менее плотные конструкторы рисунка, такие как ::; добавление собственных скобок, ipts становится полный список с RATOR ... как головы и ipts' (один элемент короткий), как хвост:

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

Почему еще один матч внутри (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') = ... 
   

   , а затем обратитесь к RATOR (text, prec, POSTFIX) всякий раз, когда он обращается к irator и RATOR (text, prec, POSTFIX :: ipts' всякий раз, когда он обращается к ipts. Но это и длиннее, и труднее читать, и требует перестройки значений, которые уже построены в памяти, когда ссылаются на irator и ipts (т. Е. Меньше копирования).

   Вместо вспомогательная функция noparens конструктор значения UNARY, исключение ParseError и т.д., все предназначены для обработки irator 3-кортежа непосредственно для этого удобства.

это удалить ли его из списка или авансов в любом случае? Или ipts остальная часть списка, когда оператор irator удален?

Иногда и почти. ipts' - это остальная часть списка, когда irator был удален, а ipts - это полный список без удаления элементов. В зависимости от того, указаны ли ipts или ipts' в if-then-else s, элемент выскользнул или нет.

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

Не могу сказать прямо сейчас. Но одно можно сказать наверняка: гораздо проще перевести эти функции, если вы будете придерживаться неизменных структур данных. Однако он не будет работать так же быстро.