Vcsn  2.3
Be Rational
thompson.hh
Go to the documentation of this file.
1 #pragma once
2 
5 #include <vcsn/ctx/fwd.hh>
6 #include <vcsn/ctx/traits.hh>
7 #include <vcsn/dyn/automaton.hh>
8 #include <vcsn/dyn/value.hh>
9 #include <vcsn/labelset/labelset.hh> // make_nullableset_context
10 #include <vcsn/misc/raise.hh>
11 
12 namespace vcsn
13 {
14  namespace rat
15  {
20  template <Automaton Aut,
21  typename ExpSet>
23  : public ExpSet::const_visitor
24  {
25  public:
26  using automaton_t = Aut;
27  using expressionset_t = ExpSet;
28  using expression_t = typename expressionset_t::value_t;
33 
34  using super_t = typename expressionset_t::const_visitor;
35 
36  static_assert(labelset_t_of<Aut>::has_one(),
37  "thompson: requires nullable labels");
38 
40  constexpr static const char* me() { return "thompson"; }
41 
44  : rs_(rs)
46  {}
47 
49  : thompson_visitor(rs.context(), rs)
50  {}
51 
54  {
55  try
56  {
57  v->accept(*this);
58  res_->set_initial(initial_);
59  res_->set_final(final_);
60  return std::move(res_);
61  }
62  catch (const std::runtime_error& e)
63  {
64  raise(e,
65  " while computing thompson automaton of: ",
66  to_string(rs_, v));
67  }
68  }
69 
70  private:
78  using tuple_t = typename super_t::tuple_t;
79  void visit(const tuple_t&, std::true_type) override
80  {
81  raise(me(), ": tuple is not supported");
82  }
83 
85  {
86  initial_ = res_->new_state();
87  final_ = res_->new_state();
88  }
89 
91  {
92  initial_ = res_->new_state();
93  final_ = res_->new_state();
94  res_->new_transition(initial_, final_, epsilon_);
95  }
96 
98  {
99  initial_ = res_->new_state();
100  final_ = res_->new_state();
101  // The automaton and the expression might have different
102  // labelsets.
103  res_->new_transition(initial_, final_,
104  res_->labelset()->conv(*rs_.labelset(),
105  e.value()));
106  }
107 
109  {
110  state_t initial = res_->new_state();
111  state_t final = res_->new_state();
112  for (const auto& c: e)
113  {
114  c->accept(*this);
115  res_->new_transition(initial, initial_, epsilon_);
116  res_->new_transition(final_, final, epsilon_);
117  }
118  initial_ = initial;
119  final_ = final;
120  }
121 
123  {
124  e.head()->accept(*this);
125  state_t initial = initial_;
126 
127  // Then the remainder.
128  for (const auto& c: e.tail())
129  {
130  state_t final = final_;
131  c->accept(*this);
132  res_->new_transition(final, initial_, epsilon_);
133  }
134  initial_ = initial;
135  }
136 
138  {
139  e.sub()->accept(*this);
140  state_t initial = res_->new_state();
141  state_t final = res_->new_state();
142  res_->new_transition(initial, initial_, epsilon_);
143  res_->new_transition(final_, final, epsilon_);
144  res_->new_transition(final_, initial_, epsilon_);
145  res_->new_transition(initial, final, epsilon_);
146  initial_ = initial;
147  final_ = final;
148  }
149 
151  {
152  e.sub()->accept(*this);
153 
154  const weight_t& w = e.weight();
155  for (auto t: out(res_, initial_))
156  res_->set_weight(t, ws_.mul(w, res_->weight_of(t)));
157  }
158 
160  {
161  e.sub()->accept(*this);
162 
163  const weight_t& w = e.weight();
164  for (auto t: in(res_, final_))
165  res_->set_weight(t, ws_.mul(res_->weight_of(t), w));
166  }
167 
168  private:
170  const weightset_t& ws_ = *rs_.weightset();
173  const label_t epsilon_ = res_->labelset()->one();
174  state_t initial_ = automaton_t::element_type::null_state();
175  state_t final_ = automaton_t::element_type::null_state();
176  };
177  } // rat::
178 
183  template <Automaton Aut, typename ExpSet>
184  Aut
186  const ExpSet& rs, const typename ExpSet::value_t& r)
187  {
188  auto thm = rat::thompson_visitor<Aut, ExpSet>{ctx, rs};
189  return thm(r);
190  }
191 
196  template <Automaton Aut, typename ExpSet>
197  Aut
198  thompson(const ExpSet& rs, const typename ExpSet::value_t& r)
199  {
200  auto thm = rat::thompson_visitor<Aut, ExpSet>{rs};
201  return thm(r);
202  }
203 
204  namespace dyn
205  {
206  namespace detail
207  {
208  /*---------------------.
209  | dyn::thompson(exp). |
210  `---------------------*/
211 
213  template <typename ExpSet>
214  automaton
215  thompson(const expression& exp)
216  {
217  // FIXME: So far, there is a single implementation of expressions,
218  // but we should actually be parameterized by its type too.
219  using expressionset_t = ExpSet;
220  const auto& e = exp->as<expressionset_t>();
221  auto ctx
222  = vcsn::detail::make_nullableset_context(e.valueset().context());
223  using ctx_t = decltype(ctx);
224  using automaton_t = mutable_automaton<ctx_t>;
225  return ::vcsn::thompson<automaton_t>(ctx, e.valueset(), e.value());
226  }
227  }
228  }
229 
230 } // vcsn::
void visit(const tuple_t &, std::true_type) override
Definition: thompson.hh:79
return v
Definition: multiply.hh:361
automaton thompson(const expression &exp)
Bridge.
Definition: thompson.hh:215
typename detail::weight_t_of_impl< base_t< ValueSet >>::type weight_t_of
Definition: traits.hh:66
SharedPtr make_shared_ptr(Args &&...args)
Same as std::make_shared, but parameterized by the shared_ptr type, not the (pointed to) element_type...
Definition: memory.hh:13
#define Automaton
Definition: automaton.hh:23
STL namespace.
std::shared_ptr< detail::mutable_automaton_impl< Context >> mutable_automaton
Definition: fwd.hh:25
const expressionset_t & rs_
Definition: thompson.hh:169
state_t_of< automaton_t > state_t
Definition: thompson.hh:32
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:63
auto in(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions arriving to state s.
Definition: automaton.hh:113
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
Definition: traits.hh:61
auto out(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions leaving state s.
Definition: automaton.hh:64
An inner node implementing a weight.
Definition: expression.hh:264
context_t_of< automaton_t > context_t
Definition: thompson.hh:29
const weightset_t & ws_
Definition: thompson.hh:170
thompson_visitor(const expressionset_t &rs)
Definition: thompson.hh:48
typename super_t::tuple_t tuple_t
Definition: thompson.hh:78
automaton_t operator()(const expression_t &v)
The Thompson automaton of v.
Definition: thompson.hh:53
Aut thompson(const context_t_of< Aut > &ctx, const ExpSet &rs, const typename ExpSet::value_t &r)
Build a Thompson automaton from an expression.
Definition: thompson.hh:185
static constexpr const char * me()
Name of this algorithm, for error messages.
Definition: thompson.hh:40
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64
auto rs
Definition: lift.hh:152
Definition: a-star.hh:8
typename detail::label_t_of_impl< base_t< ValueSet >>::type label_t_of
Definition: traits.hh:62
label_t_of< automaton_t > label_t
Definition: thompson.hh:172
Build a Thompson automaton from an expression.
Definition: thompson.hh:22
thompson_visitor(const context_t &ctx, const expressionset_t &rs)
Build an automaton of context ctx.
Definition: thompson.hh:43
nullableset_context_t< context< LabelSet, WeightSet > > make_nullableset_context(const context< LabelSet, WeightSet > &ctx)
The nullableset context of a context.
Definition: labelset.hh:163
std::string to_string(identities i)
Wrapper around operator<<.
Definition: identities.cc:41
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:67
auto & as()
Extract wrapped typed automaton.
Definition: automaton.hh:37
An inner node with multiple children.
Definition: expression.hh:118
#define VCSN_RAT_UNSUPPORTED(Type)
Definition: visitor.hh:75
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
weightset_t_of< expressionset_t > weightset_t
Definition: thompson.hh:30
value_impl< detail::expression_tag > expression
Definition: fwd.hh:25
typename expressionset_t::value_t expression_t
Definition: thompson.hh:28
weight_t_of< expressionset_t > weight_t
Definition: thompson.hh:31
typename expressionset_t::const_visitor super_t
Definition: thompson.hh:34
static dyn::context ctx(const driver &d)
Get the context of the driver.
Definition: parse.cc:82