00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #ifndef VCSN_ALGORITHMS_THOMPSON_HXX
00018 # define VCSN_ALGORITHMS_THOMPSON_HXX
00019
00020 # include <vaucanson/algorithms/thompson.hh>
00021
00022 # include <vaucanson/automata/concept/automata_base.hh>
00023 # include <vaucanson/algorithms/normalized.hh>
00024 # include <vaucanson/misc/usual_macros.hh>
00025
00026 namespace vcsn {
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036 template <class Auto_, class Monoid_, class Semiring_>
00037 class ThompsonVisitor :
00038 public rat::ConstNodeVisitor<Monoid_, Semiring_>
00039 {
00040 public :
00041 typedef Auto_ automaton_t;
00042 typedef typename automaton_t::hstate_t hstate_t;
00043 typedef typename automaton_t::set_t automata_set_t;
00044 typedef typename automaton_t::series_set_t series_set_t;
00045 typedef typename automaton_t::series_set_elt_t series_set_elt_t;
00046 typedef typename series_set_elt_t::semiring_elt_t semiring_elt_t;
00047 typedef Monoid_ monoid_elt_value_t;
00048 typedef Semiring_ semiring_elt_value_t;
00049 typedef rat::Node<monoid_elt_value_t, semiring_elt_value_t> node_t;
00050
00051 public :
00052
00053 ThompsonVisitor(const series_set_t& s) : series_(s)
00054 {}
00055
00056 virtual
00057 ~ThompsonVisitor()
00058 {}
00059
00060 virtual void
00061 product(const node_t* lhs, const node_t* rhs)
00062 {
00063 automaton_t *tmp_;
00064 rhs->accept(*this);
00065 tmp_ = auto_;
00066 lhs->accept(*this);
00067 concatenate_of_normalized_here(*auto_, *tmp_);
00068 delete(tmp_);
00069 }
00070
00071 virtual void
00072 sum(const node_t* lhs, const node_t* rhs)
00073 {
00074 automaton_t *tmp_;
00075 lhs->accept(*this);
00076 tmp_ = auto_;
00077 rhs->accept(*this);
00078 union_of_normalized_here(*auto_, *tmp_);
00079 }
00080
00081 virtual void
00082 star(const node_t* node)
00083 {
00084 node->accept(*this);
00085 star_of_normalized_here(*auto_);
00086 }
00087
00088 virtual void
00089 left_weight(const semiring_elt_value_t& w, const node_t* node)
00090 {
00091 node->accept(*this);
00092
00093 AUTOMATON_TYPES(automaton_t);
00094
00095 hstate_t new_i = auto_->add_state();
00096 hstate_t new_f = auto_->add_state();
00097
00098 for_all_const_initial_states(i, *auto_)
00099 {
00100 series_set_elt_t t = auto_->series().zero_;
00101 t.assoc(auto_->series().monoid().identity(SELECT(monoid_elt_value_t)), w);
00102 auto_->add_series_transition(new_i, *i, t);
00103 }
00104 for_all_const_final_states(f, *auto_)
00105 auto_->add_spontaneous(*f, new_f);
00106
00107 auto_->clear_initial();
00108 auto_->clear_final();
00109
00110 auto_->set_initial(new_i);
00111 auto_->set_final(new_f);
00112 }
00113
00114 virtual void
00115 right_weight(const semiring_elt_value_t& w, const node_t* node)
00116 {
00117 node->accept(*this);
00118
00119 AUTOMATON_TYPES(automaton_t);
00120
00121 hstate_t new_i = auto_->add_state();
00122 hstate_t new_f = auto_->add_state();
00123
00124 for_all_const_initial_states(i, *auto_)
00125 auto_->add_spontaneous(new_i, *i);
00126 for_all_const_final_states(f, *auto_)
00127 {
00128 series_set_elt_t t = auto_->series().zero_;
00129 t.assoc(auto_->series().monoid().identity(SELECT(monoid_elt_value_t)), w);
00130 auto_->add_series_transition(*f, new_f, t);
00131 }
00132
00133 auto_->clear_initial();
00134 auto_->clear_final();
00135
00136 auto_->set_initial(new_i);
00137 auto_->set_final(new_f);
00138 }
00139
00140 virtual void
00141 constant(const monoid_elt_value_t& m)
00142 {
00143 auto_ = new automaton_t(automata_set_t(series_));
00144 hstate_t new_i = auto_->add_state();
00145 hstate_t last = new_i;
00146 hstate_t new_f;
00147 for (typename monoid_elt_value_t::const_iterator i = m.begin();
00148 i != m.end(); ++i)
00149 {
00150 new_f = auto_->add_state();
00151 auto_->add_letter_transition(last, new_f, *i);
00152 last = new_f;
00153 }
00154 auto_->set_initial(new_i);
00155 auto_->set_final(new_f);
00156 }
00157
00158 virtual void
00159 zero()
00160 {
00161 auto_ = new automaton_t(automata_set_t(series_));
00162 auto_->set_initial(auto_->add_state());
00163 auto_->set_final(auto_->add_state());
00164 }
00165
00166 virtual void
00167 one()
00168 {
00169 auto_ = new automaton_t(automata_set_t(series_));
00170 hstate_t new_i = auto_->add_state();
00171 hstate_t new_f = auto_->add_state();
00172 auto_->set_initial(new_i);
00173 auto_->set_final(new_f);
00174 auto_->add_spontaneous(new_i, new_f);
00175 }
00176
00177 const automaton_t &get_auto() const
00178 {
00179 return *auto_;
00180 }
00181
00182 private :
00183 automaton_t *auto_;
00184 const series_set_t &series_;
00185 };
00186
00187 template <typename A, typename auto_t,
00188 typename Letter, typename Weight>
00189 void
00190 do_thompson_of(const AutomataBase<A>&,
00191 auto_t& output,
00192 const rat::exp<Letter, Weight>& kexp)
00193 {
00194 ThompsonVisitor<auto_t, Letter, Weight> visitor(output.structure().series());
00195
00196
00197
00198
00199 kexp.accept(visitor);
00200 output = visitor.get_auto();
00201 }
00202
00203 template<typename A, typename T,
00204 typename Letter, typename Weight>
00205 void
00206 thompson_of(Element<A, T>& out,
00207 const rat::exp<Letter, Weight>& kexp)
00208 {
00209 do_thompson_of(out.structure(), out, kexp);
00210 }
00211
00212 template <typename AutoType, typename S, typename K, typename T>
00213 Element<Automata<S, K>, AutoType>
00214 thompson_of(const Element<S, T>& exp)
00215 {
00216 Automata<S, K> automata_set(exp.structure());
00217 Element<Automata<S, K>, AutoType> automata(automata_set);
00218
00219 thompson_of(automata, exp.value());
00220 return automata;
00221 }
00222 }
00223
00224 #endif // ! VCSN_ALGORITHMS_THOMPSON_HXX