Witam, pisząc własny parser napotkałem się z pierwszymi sporymi dla mnie do pokonania problemami. Początkowo uczyłem się z tego: http://informatyka.wroc.pl/node/391
Usuwanie tam drzewa w razie wystąpienia błędu w wyrażeniu prezentuje się tam tak: http://informatyka.wroc.pl/node/431?page=0,3
Ja nie tak dawno poznałem inteligentne wskaźniki i zacząłem się zastanawiać czy ich nie można wykorzystać, tak wyglądają przykładowo u mnie definicje klas reprezentujących drzewo:
#ifndef EXP_H_
#define EXP_H_
#include <string>
#include <stdexcept>
#include <map>
#include <memory>
///--------------------------------------------------------------------
using Memory = std::map<std::string, double>;
//////////////////////////// EXPRESSION //////////////////////////////////////////
class AST_Exp {
public:
virtual double Solve(Memory& vars) = 0;
};
///--------------------------------------------------------------------
class Constant : public AST_Exp {
private:
const double m_constant;
public:
Constant(double constant) : m_constant(constant) {}
virtual double Solve(Memory& vars);
};
///--------------------------------------------------------------------
class BinaryOperator : public AST_Exp {
private:
char m_operator;
std::unique_ptr<AST_Exp> m_left;
std::unique_ptr<AST_Exp> m_right;
public:
BinaryOperator(char operat, AST_Exp* left, AST_Exp* right)
: m_operator(operat), m_left(left), m_right(right) {}
virtual double Solve(Memory& vars);
};
///--------------------------------------------------------------------
class Variable : public AST_Exp {
private:
std::string m_name;
public:
Variable(const std::string& variable) : m_name(variable) {}
virtual double Solve(Memory& vars);
};
//////////////////////////// PROGRAM /////////////////////////////////////////////
#endif
Jak widać użyłem tu szablonu klasy std::unique_ptr.
To jednak nie koniec problemów, mamy też klasę parsera:
#ifndef PARSER_H_
#define PARSER_H_
#include "program.h"
#include <string>
///--------------------------------------------------------------------
class Parser {
private:
const char EOS = 0;
std::string m_expression;
unsigned pointer;
private:
void skip_whitespace();
char look_ahead();
public:
Parser(std::string input);
AST_Exp* parse_expression(); //start
AST_Exp* parse_logic(); //1 - parsuj zbiór porównań jakim jest wyrażenie
AST_Exp* parse_sum(); //2 - parsuj sume ( z sum składają się porównania )
AST_Exp* parse_mult(); //3 - parsuj skladnik ( ze składników składają się sumy )
AST_Exp* parse_term(); //4 - parsuj czynnik ( z czynników składają się składniki )
AST_Exp* parse_constant();
AST_Exp* parse_variable();
AST_Exp* parse_paren();
};
///--------------------------------------------------------------------
#endif
i definicje jej metod:
#include <string>
#include <cctype>
#include <stdexcept>
#include <sstream>
#include "program.h"
#include "Parser.h"
///--------------------------------------------------------------------
Parser::Parser(std::string input)
: pointer(0), m_expression(input) {
m_expression.push_back(EOS);
}
///--------------------------------------------------------------------
void Parser::skip_whitespace() {
while (isspace(m_expression[pointer]))
++pointer;
}
///--------------------------------------------------------------------
char Parser::look_ahead() {
skip_whitespace();
return m_expression[pointer];
}
///--------------------------------------------------------------------
AST_Exp* Parser::parse_expression() {
AST_Exp* res = parse_logic();
if (look_ahead() == EOS)
return res;
else
throw std::logic_error("bad code structure");
}
///--------------------------------------------------------------------
AST_Exp* Parser::parse_logic() {
AST_Exp* res = parse_sum();
char c = look_ahead();
while (c == '=' || c == '>' || c == '<' || c == '!') {
++pointer;
res = new BinaryOperator(c, res, parse_sum());
c = look_ahead();
}
return res;
}
///--------------------------------------------------------------------
AST_Exp* Parser::parse_sum() {
AST_Exp* res = parse_mult();
char c = look_ahead();
while (c == '+' || c == '-') {
++pointer;
res = new BinaryOperator(c, res, parse_mult());
c = look_ahead();
}
return res;
}
///--------------------------------------------------------------------
AST_Exp* Parser::parse_mult() {
AST_Exp* res = parse_term();
char c = look_ahead();
while (c == '*' || c == '/' || c == '%' || c == '^') {
++pointer;
res = new BinaryOperator(c, res, parse_term());
c = look_ahead();
}
return res;
}
///--------------------------------------------------------------------
AST_Exp* Parser::parse_term() {
char c = look_ahead();
if (std::isdigit(c))
return parse_constant();
else if (std::isalpha(c))
return parse_variable();
else if (c == '(')
return parse_paren();
else
throw std::logic_error("undefined character");
}
///--------------------------------------------------------------------
AST_Exp* Parser::parse_constant() {
std::string num;
while (std::isdigit(m_expression[pointer]) || m_expression[pointer] == '.') {
num.push_back(m_expression[pointer]);
++pointer;
}
double temp = 0.0;
std::stringstream ss;
ss << num;
ss >> temp;
return new Constant(temp);
}
///--------------------------------------------------------------------
AST_Exp* Parser::parse_variable() {
std::string temp;
while (isalnum(m_expression[pointer])) {
temp.push_back(m_expression[pointer]);
++pointer;
}
return new Variable(temp);
}
///--------------------------------------------------------------------
AST_Exp* Parser::parse_paren() {
++pointer;
AST_Exp* res = parse_logic();
if (look_ahead() == ')') {
++pointer;
return res;
}
else
throw std::logic_error("odd number of brackets");
}
///--------------------------------------------------------------------
Kompletnie nie mam pomysłu jak takie drzewo "zacząć usuwać" z poziomu parsera przy użyciu inteligentnych wskaźników. W których w ogóle miejscach powinien występować zwykły a w których inteligentny wskaźnik... Myślę też sobie czy takie drzewo warto robić na szablonach inteligentnych wskaźników, czy to jeszcze bardziej nie komplikuje sprawy...
Będę wam bardzo wdzięczny za pomoc :)
