3
구문 분석 알고리즘 here을 찾았습니다. 그러나 ML에 있으며 너무 익숙하지 않습니다. 알고리즘을 더 잘 이해하기 위해 저는 이것을 C++과 같은 명령형 언어로 변환하려고합니다. 이제 너는 내가 잘 모르거나 이해하지 못하는 몇 가지 것들이있다. 여기 ML 코드를 C++로 번역
는 후위 식을 구문 분석에 대한 헤더입니다 (AFAIK이 기술적으로하지 헤더, 그러나 일치하지만 기능적인 용어에 익숙하지 않은 오전) : 는parse_postfix(stack, (e, []),
ipts as RATOR (irator as (_, _, POSTFIX)) :: ipts') =
이 ipts이의 머리는 것을 의미 목록 ipts'은 후위 연산자입니까? 내부에 다른 일치 항목이있는 이유는 무엇입니까 (irator as...)? 그것은 목록에서 제거하거나 어쨌든 발전합니까? 또는 irator 연산자가 제거 된 경우 목록의 나머지는 ipts입니까?
번역에 어려움이 있습니다. 나는이 부분은 해석 접두어 corect 것을 바라고 있어요
#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).
이 알고리즘은이 문서에서 자세히 설명합니다. – molbdnilo
@molbdnilo 네,하지만 예제 구현은보기에 좋을 것입니다. –