00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018 #ifndef VCSN_ALGEBRA_IMPLEMENTATION_SERIES_KRAT_EXP_PARSER_HXX
00019 # define VCSN_ALGEBRA_IMPLEMENTATION_SERIES_KRAT_EXP_PARSER_HXX
00020 # include <map>
00021 # include <queue>
00022 # include <set>
00023 # include <vaucanson/algebra/implementation/series/krat_exp_parser.hh>
00024 # include <vaucanson/algebra/implementation/series/krat_exp_proxy.hh>
00025 # include <vaucanson/algebra/concept/monoid_base.hh>
00026
00027
00028 namespace yy
00029 {
00030 struct token_queue;
00031 struct krat_exp_parser
00032 {
00033 krat_exp_parser();
00034 void insert_word(vcsn::algebra::krat_exp_virtual* rexp);
00035 void insert_weight(vcsn::algebra::semiring_virtual* sem);
00036 void insert_one(vcsn::algebra::krat_exp_virtual* rexp);
00037 void insert_zero(vcsn::algebra::krat_exp_virtual* rexp);
00038 void insert_token(int i, std::string* str);
00039 int parse(vcsn::algebra::krat_exp_virtual& rexp, std::string& error);
00040
00041
00042 token_queue* tok_q_;
00043 };
00044 }
00045
00046 namespace vcsn
00047 {
00048 namespace algebra
00049 {
00050 template <class S, class T>
00051 struct Lexer
00052 {
00053 typedef typename Element<S, T>::monoid_elt_t monoid_elt_t;
00054 typedef typename Element<S, T>::semiring_elt_t semiring_elt_t;
00055 Lexer(const std::string& from,
00056 Element<S, T>& e,
00057 yy::krat_exp_parser& parser,
00058 bool lex_trace,
00059 const token_representation_t tok_rep,
00060 std::string& error) :
00061 from_(from),
00062 e_(e),
00063 parser_(parser),
00064 lex_trace_(lex_trace),
00065 close_weight_("}"),
00066 token_tab_(9),
00067 error_(error)
00068 {
00069 token_tab_[0] = tok_rep.open_par;
00070 token_tab_[1] = tok_rep.close_par;
00071 token_tab_[2] = tok_rep.plus;
00072 token_tab_[3] = tok_rep.times;
00073 token_tab_[4] = tok_rep.star;
00074 token_tab_[5] = tok_rep.one;
00075 token_tab_[6] = tok_rep.zero;
00076 token_tab_[7] = tok_rep.open_weight;
00077 close_weight_ = tok_rep.close_weight;
00078 for (unsigned i = 0; i < tok_rep.spaces.size(); i++)
00079 {
00080 token_tab_[8 + i] = tok_rep.spaces[i];
00081 }
00082
00083 std::string::const_iterator sit;
00084 semiring_elt_t ww(e_.structure().semiring());
00085 sit = close_weight_.begin();
00086 if (parse_weight(ww, close_weight_, sit))
00087 error_ += "Warning : the token '" + close_weight_ +
00088 + "' is already defined as a weight.\n";
00089 sit = token_tab_[7].begin();
00090 if (parse_weight(ww, token_tab_[7], sit))
00091 error_ += "Warning : the token '" + token_tab_[7]
00092 + "' is already defined as a weight.\n";
00093 for (unsigned i = 0; i < token_tab_.size(); i++)
00094 {
00095 sit = token_tab_[i].begin();
00096 monoid_elt_t w(e_.structure().monoid());
00097 if (parse_word(w, token_tab_[i], sit, std::set<char>()))
00098 error_ += "Warning : the token '" + token_tab_[i]
00099 + "' is already defined as a word.\n";
00100 }
00101
00102 }
00103
00104 bool
00105 lex()
00106 {
00107 size_t curr = 0;
00108 size_t size = from_.size();
00109 size_t it = curr;
00110 while (it < size)
00111 {
00112 for (size_t i = 0; i < token_tab_.size(); i++)
00113 {
00114 if (!from_.compare(it, token_tab_[i].size(), token_tab_[i]))
00115 {
00116 if (curr != it)
00117 if (!insert_word(curr, it))
00118 return false;
00119 if (i == 7)
00120 {
00121 if (!insert_weight(it))
00122 return false;
00123 }
00124 else
00125 {
00126 if (i < 7)
00127 insert_token(i);
00128 it += token_tab_[i].size();
00129 }
00130 curr = it--;
00131 break;
00132 }
00133 }
00134 it++;
00135 }
00136 if (curr != it)
00137 if (!insert_word(curr, it))
00138 return false;
00139 return true;
00140 }
00141
00142 private:
00143 bool
00144 insert_word(size_t curr, size_t it)
00145 {
00146 monoid_elt_t w(e_.structure().monoid());
00147 std::string s = from_.substr(curr, it - curr);
00148 std::string::const_iterator sit = s.begin();
00149 if (parse_word(w, s, sit, std::set<char>()))
00150 {
00151 Element<S, T> ww = Element<S, T>(e_.structure(), w.value());
00152 krat_exp_proxy<S, T>* rexp = new krat_exp_proxy<S, T>(ww);
00153 parser_.insert_word(rexp);
00154 }
00155 else
00156 {
00157 error_ += "Lexer error : " + s
00158 + " some characters are not part of the alphabet\n";
00159 return false;
00160 }
00161 return true;
00162 }
00163
00164 bool
00165 insert_weight(size_t& it)
00166 {
00167 it += token_tab_[7].size();
00168 size_t bg = it;
00169 size_t size = from_.size();
00170 unsigned cpt = 1;
00171 for (; it < size; it++)
00172 {
00173 if (!from_.compare(it, token_tab_[7].size(), token_tab_[7]))
00174 cpt++;
00175 else
00176 if (!from_.compare(it, close_weight_.size(), close_weight_))
00177 {
00178 if (cpt == 1)
00179 {
00180 semiring_elt_t w(e_.structure().semiring());
00181 std::string s = from_.substr(bg, it - bg);
00182 std::string::const_iterator sit = s.begin();
00183 if (parse_weight(w, s, sit))
00184 {
00185 semiring_proxy<S, T>* sem = new semiring_proxy<S, T>(w);
00186 parser_.insert_weight(sem);
00187 }
00188 else
00189 {
00190 error_ += "Lexer error : " + s + " is not a weight\n";
00191 return false;
00192 }
00193 it += close_weight_.size();
00194 return true;
00195 }
00196 else
00197 cpt--;
00198 }
00199 }
00200 error_ += "Lexer error : Expected " + close_weight_
00201 + "instead of END\n";
00202 return false;
00203 }
00204
00205 void
00206 insert_token(int i)
00207 {
00208 if (i == 5)
00209 {
00210 Element<S, T> w = identity_as<T>::of(e_.structure());
00211 krat_exp_proxy<S, T>* rexp = new krat_exp_proxy<S, T>(w);
00212 parser_.insert_one(rexp);
00213 }
00214 else
00215 if (i == 6)
00216 {
00217 Element<S, T> w = zero_as<T>::of(e_.structure());
00218 krat_exp_proxy<S, T>* rexp = new krat_exp_proxy<S, T>(w);
00219 parser_.insert_zero(rexp);
00220 }
00221 else
00222 {
00223 std::string* str = new std::string(token_tab_[i]);
00224 parser_.insert_token(i, str);
00225 }
00226 }
00227
00228 const std::string& from_;
00229 Element<S, T>& e_;
00230 yy::krat_exp_parser& parser_;
00231 bool lex_trace_;
00232 std::string close_weight_;
00233 std::vector<std::string> token_tab_;
00234 std::string& error_;
00235 };
00236
00237 template <class S, class T>
00238 std::pair<bool, std::string>
00239 parse(const std::string& from,
00240 Element<S, T>& exp,
00241 const token_representation_t tok_rep = token_representation_t(),
00242 bool lex_trace = false,
00243 bool parse_trace = false)
00244 {
00245 parse_trace = parse_trace;
00246 std::string error;
00247 yy::krat_exp_parser parser;
00248 Lexer<S, T> lex(from, exp, parser, lex_trace, tok_rep, error);
00249 if (!lex.lex())
00250 return std::make_pair(true, error);
00251 krat_exp_proxy<S, T> rexp(exp);
00252 if (parser.parse(rexp, error))
00253 return std::make_pair(true, error);
00254 exp = rexp.self;
00255 return std::make_pair(false, error);
00256 }
00257
00258 }
00259
00260 }
00261
00262 #endif // ! VCSN_ALGEBRA_IMPLEMENTATION_SERIES_KRAT_EXP_PARSER_HXX