#include <algorithm> #include <iostream> #include <iterator> #include <map> #include <set> #include <boost/noncopyable.hpp> namespace xxx { class set_algorithm { public: static std::set<int> _union(const std::set<int> &_x, const std::set<int> &_y) { std::set<int> _result; std::set_union(_x.begin(), _x.end(), _y.begin(), _y.end(), std::inserter(_result, _result.begin())); return _result; } }; class node:boost::noncopyable { public: virtual ~node() {} virtual bool nullable() const=0; virtual const std::set<int> firstpos() const=0; virtual const std::set<int> lastpos() const=0; virtual void follow(std::map<int, std::set<int> > &) const=0; virtual char element_of_position(int) const=0; }; class leaf:public node { public: leaf(char _c, int _n):_char_m(_c), _num_m(_n) {} bool nullable() const {return false;} const std::set<int> firstpos() const {return _generic_self();} const std::set<int> lastpos() const {return _generic_self();} void follow(std::map<int, std::set<int> > &) const {} char element_of_position(int _num) const { if(_num_m==_num) return _char_m; else return 0; } private: const std::set<int> _generic_self() const {return std::set<int>(&_num_m, &_num_m+1);} char _char_m; int _num_m; }; class unary_node:public node { public: unary_node(const node *_next):_next_m(_next) {} protected: const node *_next_m; }; class star:public unary_node { public: star(const node *_next):unary_node(_next) {} bool nullable() const {return true;} const std::set<int> firstpos() const {return _next_m->firstpos();} const std::set<int> lastpos() const {return _next_m->lastpos();} void follow(std::map<int, std::set<int> > &_t) const { const std::set<int> _s(lastpos()); for(std::set<int>::const_iterator _i=_s.begin(); _i!=_s.end(); ++_i) _t[*_i]=set_algorithm::_union(_t[*_i], firstpos()); } char element_of_position(int _num) const {return _next_m->element_of_position(_num);} }; class binary_node:public node { public: binary_node(const node *_lchild, const node *_rchild):_lchild_m(_lchild), _rchild_m(_rchild) {} char element_of_position(int _num) const { const char _lchild_result=_lchild_m->element_of_position(_num); if(!_lchild_result) return _rchild_m->element_of_position(_num); return _lchild_result; } protected: void down_follow(std::map<int, std::set<int> > &_t) const { _lchild_m->follow(_t); _rchild_m->follow(_t); } const node *_lchild_m, *_rchild_m; }; class _or:public binary_node { public: _or(const node *_lchild, const node *_rchild):binary_node(_lchild, _rchild) {} bool nullable() const {return _lchild_m->nullable()||_rchild_m->nullable();} const std::set<int> firstpos() const {return set_algorithm::_union(_lchild_m->firstpos(), _rchild_m->firstpos());} const std::set<int> lastpos() const {return set_algorithm::_union(_lchild_m->lastpos(), _rchild_m->lastpos());} void follow(std::map<int, std::set<int> > &_t) const {down_follow(_t);} }; class cat:public binary_node { public: cat(const node *_lchild, const node *_rchild):binary_node(_lchild, _rchild) {} bool nullable() const {return _lchild_m->nullable()&&_rchild_m->nullable();} const std::set<int> firstpos() const { if(_lchild_m->nullable()) return set_algorithm::_union(_lchild_m->firstpos(), _rchild_m->firstpos()); else return _lchild_m->firstpos(); } const std::set<int> lastpos() const { if(_rchild_m->nullable()) return set_algorithm::_union(_lchild_m->lastpos(), _rchild_m->lastpos()); else return _rchild_m->lastpos(); } void follow(std::map<int, std::set<int> > &_t) const { down_follow(_t); const std::set<int> _s(_lchild_m->lastpos()); for(std::set<int>::const_iterator _i=_s.begin(); _i!=_s.end(); ++_i) _t[*_i]=set_algorithm::_union(_t[*_i], _rchild_m->firstpos()); } }; class node_wrapper { public: node_wrapper(node *_grammar_tree):_grammar_tree_m(_grammar_tree) {} const std::set<int> firstpos() const {return _grammar_tree_m->firstpos();} const std::set<int> lastpos() const {return _grammar_tree_m->lastpos();} const std::map<int, std::set<int> > follow() const { std::map<int, std::set<int> > _result; _grammar_tree_m->follow(_result); return _result; } char element_of_position(int _num) const {return _grammar_tree_m->element_of_position(_num);} private: node *_grammar_tree_m; }; class alpha_extractor { public: static std::set<char> get(const std::string &_expr) { std::set<char> _result; for(std::string::const_iterator _i=_expr.begin(); _i!=_expr.end(); ++_i) if(isalpha(*_i)) _result.insert(*_i); return _result; } }; class dfa_generator { public: static std::map<std::set<int>, std::map<char, std::set<int> > > generic(const node_wrapper &_grammar_tree) { std::map<std::set<int>, bool> _state; _state.insert(std::pair<std::set<int>, bool>(_grammar_tree.firstpos(), false)); } }; }
