Awali
Another Weighted Automata library
exp_parser.hh
Go to the documentation of this file.
1 // This file is part of Awali.
2 // Copyright 2016-2021 Sylvain Lombardy, Victor Marsault, Jacques Sakarovitch
3 //
4 // Awali is a free software: you can redistribute it and/or modify
5 // it under the terms of the GNU General Public License as published by
6 // the Free Software Foundation, either version 3 of the License, or
7 // (at your option) any later version.
8 //
9 // This program is distributed in the hope that it will be useful,
10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 // GNU General Public License for more details.
13 //
14 // You should have received a copy of the GNU General Public License
15 // along with this program. If not, see <http://www.gnu.org/licenses/>.
16 
17 #ifndef AWALI_EXP_PARSER_HH
18 #define AWALI_EXP_PARSER_HH
19 namespace awali {
20  namespace sttc {
21  namespace internal {
22 
23  template<typename RatExpSet>
24  struct exp_parser;
25  }
26  }
27 }
32 #include <awali/common/parse_exception.cc>
33 #include<string>
34 #include<list>
35 
36  /*
37 
38  E -> P | E+P
39  P -> S | PS | P.S
40  S -> L | S* | S{exp} | S?
41  L -> R | <weight>R
42  R -> A | A<weight>
43  A -> label | (E) | [labelinterval]
44 
45  */
46 
47 namespace awali { namespace sttc {
48 
49  namespace internal {
50 
51  template<typename RatExpSet>
52  struct exp_parser {
53  using ratexpset_t = RatExpSet;
56  using ratexp_t = typename ratexpset_t::value_t;
58 
59  exp_parser(const ratexpset_t& rs, const std::string& s, bool strict_alphabet)
60  : p_(s.length()), rs_(rs), s_(s), strict_(strict_alphabet)
61  {}
62 
63  exp_parser(const ratexpset_t& rs, const std::string& s, size_t& p, bool strict_alphabet)
64  : rs_(rs), s_(s), p_(p), strict_(strict_alphabet)
65  {}
66 
68  ignore();
69  ratexp_t e2=parseP();
70  if(p_ == 0)
71  return e2;
72  if(s_[p_-1]=='+') {
73  --p_;
74  ignore();
75  if(p_==0)
76  throw parse_exception("Parsing expression");
77  ratexp_t e1=parseE();
78  return ratexp_t(rs_.add(e1,e2));
79  }
80  return e2;
81  }
82 
84  ratexp_t e2=parseS();
85  if(p_==0)
86  return e2;
87  if(s_[p_-1]=='.') {
88  --p_;
89  ignore();
90  if(p_==0)
91  throw parse_exception("Parsing product");
92  ratexp_t e1=parseP();
93  return ratexp_t(rs_.mul(e1,e2));
94  }
95  if(s_[p_-1]!='(' && s_[p_-1]!='+') {
96  ratexp_t e1=parseP();
97  return ratexp_t(rs_.mul(e1,e2));
98  }
99  return e2;
100  }
101 
103  if(s_[p_-1]=='*'){
104  --p_;
105  ignore();
106  if(p_==0)
107  throw parse_exception("Parsing star");
108  ratexp_t e=parseS();
109  return ratexp_t(rs_.star(e));
110  }
111  if(s_[p_-1]=='?'){
112  --p_;
113  ignore();
114  if(p_==0)
115  throw parse_exception("Parsing ?");
116  ratexp_t e=parseS();
117  return ratexp_t(rs_.add(e,rs_.one()));
118  }
119  if(s_[p_-1]=='}'){
120  --p_;
121  ignore();
122  if(p_==0)
123  throw parse_exception("Parsing exponent");
124  int a,b,h;
125  if(s_[p_-1]==',')
126  b=-1;
127  else {
128  b=0; h=1;
129  while(s_[p_-1]>='0' && s_[p_-1]<='9') {
130  b+=h*(s_[p_-1]-'0'); h*=10;
131  --p_;
132  ignore();
133  if(p_==0)
134  throw parse_exception("Parsing exponent");
135  }
136  }
137  a=b;
138  if(s_[p_-1]!='{') {
139  if(s_[p_-1]!=',' || p_==1)
140  throw parse_exception(p_-1,"Parsing exponent");
141  --p_;
142  ignore();
143  a=0; h=1;
144  while(s_[p_-1]>='0' && s_[p_-1]<='9') {
145  a+=h*(s_[p_-1]-'0'); h*=10;
146  --p_;
147  ignore();
148  if(p_==0)
149  throw parse_exception("Parsing exponent");
150  }
151  if(s_[p_-1]!='{')
152  throw parse_exception(p_-1,"Parsing exponent");
153  }
154  --p_;
155  ignore();
156  if(p_==0)
157  throw parse_exception("Parsing");
158  ratexp_t e=parseS();
159  ratexp_t p(rs_.one());
160  for(int i=0; i<a; ++i)
161  p=ratexp_t(rs_.mul(p,e));
162  if(b==-1)
163  return ratexp_t(rs_.mul(p,rs_.star(e)));
164  ratexp_t pp(rs_.one());
165  ratexp_t qq(rs_.one());
166  for(int i=a; i<b; ++i) {
167  pp=ratexp_t(rs_.mul(pp,e));
168  qq=ratexp_t(rs_.add(qq,pp));
169  }
170  return ratexp_t(rs_.mul(p,qq));
171  }
172  return parseL();
173  }
174 
176  ratexp_t e=parseR();
177  if(p_==0)
178  return e;
179  if(s_[p_-1]=='>') {
180  --p_;
181  ignore();
182  auto w = ws_.parse(s_,p_);
183  ignore();
184  if(p_==0 || s_[p_-1]!='<')
185  throw parse_exception(p_-1,"Parsing weight");
186  --p_;
187  ignore();
188  return ratexp_t(rs_.lmul(w, e));
189  }
190  return e;
191  }
192 
194  if(p_==0)
195  throw parse_exception("Parsing right weight");
196  if(s_[p_-1]=='>') {
197  --p_;
198  ignore();
199  auto w = ws_.parse(s_,p_);
200  ignore();
201  if(p_==0 || s_[p_-1]!='<')
202  throw parse_exception(p_-1,"Parsing right weight");
203  --p_;
204  ignore();
205  ratexp_t e=parseA();
206  return ratexp_t(rs_.rmul(e, w));
207  }
208  return parseA();
209  }
210 
212  if(p_>1 && s_[p_-1]=='e' && s_[p_-2]=='\\') {
213  p_-=2;
214  ignore();
215  return ratexp_t(rs_.one());
216  }
217  if(p_>1 && s_[p_-1]=='z' && s_[p_-2]=='\\') {
218  p_-=2;
219  ignore();
220  return ratexp_t(rs_.zero());
221  }
222  if(p_==0)
223  throw parse_exception("Parsing atom");
224  if(s_[p_-1]==')'){
225  --p_;
226  ignore();
227  ratexp_t res= parseE();
228  if(p_==0)
229  throw parse_exception("Parsing atom");
230  if(s_[p_-1]=='(') {
231  --p_;
232  ignore();
233  return res;
234  }
235  }
236  if(s_[p_-1]==']')
237  return parseSqrBrkt(ls_);
238  auto l = ls_.parse(s_,p_, strict_);
239  ignore();
240  return ratexp_t(rs_.atom(l));
241  }
242 
243  template<typename T>
244  ratexp_t parseSqrBrkt(const T&) {
245  --p_;
246  //ignore(); // to capture space at the end of list
247  std::set<typename labelset_t::value_t> letter_list;
248  while (p_>0 && s_[p_-1]!='[') {
249  if(strict_ && p_>1 && s_[p_-1]=='^' && s_[p_-2]=='['){
250  std::set<typename labelset_t::value_t> tmp;
251  auto const& alpha=ls_.genset();
252  auto it=alpha.begin();
253  auto ite=alpha.end();
254  for( auto l : letter_list) {
255  while(!(*it == l)) {
256  tmp.emplace(*it);
257  ++it;
258  }
259  ++it;
260  }
261  for(; it!=ite; ++it)
262  tmp.emplace(*it);
263  letter_list=tmp;
264  p_--;
265  break;
266  }
267  auto l = ls_.parse(s_,p_, strict_);
268  ignore();
269  if(s_[p_-1]=='-') {
270  --p_;
271  ignore();
272  auto k = ls_.parse(s_,p_, strict_);
273  ignore();
274  for(auto i=l; i>=k; --i) {
275  std::ostringstream os;
276  ls_.print(i,os);
277  const std::string& s=os.str();
278  size_t q=s.length();
279  ls_.parse(s,q, strict_);
280  letter_list.emplace(i);
281  }
282  }
283  else
284  letter_list.emplace(l);
285  }
286  if(p_==0)
287  throw parse_exception("Parsing interval");
288  --p_;
289  ignore();
290  bool first=true;
291  ratexp_t res;
292  for(auto l : letter_list) {
293  if(first) {
294  res = ratexp_t(rs_.atom(l));
295  first=false;
296  }
297  else
298  res = rs_.add(res,ratexp_t(rs_.atom(l)));
299  }
300  return res;
301  }
302 
303  template<typename... T>
305  auto l = ls_.parse(s_,p_, strict_);
306  ignore();
307  return ratexp_t(rs_.atom(l));
308  }
309 
310  template<typename F, typename S>
312  auto l = ls_.parse(s_,p_, strict_);
313  ignore();
314  return ratexp_t(rs_.atom(l));
315  }
316 
317  template<typename T>
319  auto l = ls_.parse(s_,p_, strict_);
320  ignore();
321  return ratexp_t(rs_.atom(l));
322  }
323 
324  void ignore() {
325  while(p_>0 && s_[p_-1]==' ')
326  --p_;
327  }
328 
329  size_t getPos() {
330  return p_;
331  }
332 
333  size_t p_;
334  private:
335  const ratexpset_t& rs_;
336  const std::string& s_;
337  const bool strict_;
338  weightset_t ws_ = *rs_.weightset();
339  labelset_t ls_ = *rs_.labelset();
340 
341  };
342  }
343 
422  template <typename RatExpSet>
423  inline
424  typename RatExpSet::ratexp_t
425  parse_exp(const RatExpSet& ratexpset,
426  const std::string& s, bool check_complete=true, bool strict_alphabet=true)
427  {
428  internal::exp_parser<RatExpSet> parser{ratexpset,s,strict_alphabet};
429  auto exp=parser.parseE();
430  if(check_complete && parser.getPos()>0)
431  throw parse_exception(parser.getPos(), "Parsing of a proper suffix");
432  return exp;
433  }
434 
435 }}//end of ns awali::stcs
436 
437 
438 #endif
The Boolean semring.
Definition: b.hh:38
Implementation of labels are letters.
Definition: letterset.hh:43
helper for manipulations of pair letters
Definition: pair.hh:35
The semiring of rational numbers.
Definition: q.hh:42
objets that represent the alphabets of letters as char
Definition: setalpha.hh:44
A ValueSet which is a Cartesian product of ValueSets.
Definition: tupleset.hh:80
Implementation of labels are words.
Definition: wordset.hh:35
variadic_mul_mixin< rat::ratexpset_impl< Context > > ratexpset
Definition: fwd.hh:182
RatExpSet::ratexp_t parse_exp(const RatExpSet &ratexpset, const std::string &s, bool check_complete=true, bool strict_alphabet=true)
parser of rational expressions
Definition: exp_parser.hh:425
typename internal::context_t_of_impl< internal::base_t< ValueSet > >::type context_t_of
Helper to retrieve the type of the context of a value set.
Definition: traits.hh:66
typename internal::labelset_t_of_impl< internal::base_t< ValueSet > >::type labelset_t_of
Helper to retrieve the type of the labelset of a value set.
Definition: traits.hh:76
typename internal::weightset_t_of_impl< internal::base_t< ValueSet > >::type weightset_t_of
Helper to retrieve the type of the weightset of a value set.
Definition: traits.hh:86
Main namespace of Awali.
Definition: ato.hh:22
Exceptions thrown during parsing.
Definition: parse_exception.hh:26
Definition: exp_parser.hh:52
size_t getPos()
Definition: exp_parser.hh:329
ratexp_t parseA()
Definition: exp_parser.hh:211
ratexp_t parseSqrBrkt(const tupleset< T... > &)
Definition: exp_parser.hh:304
context_t_of< ratexpset_t > context_t
Definition: exp_parser.hh:54
ratexp_t parseP()
Definition: exp_parser.hh:83
exp_parser(const ratexpset_t &rs, const std::string &s, size_t &p, bool strict_alphabet)
Definition: exp_parser.hh:63
exp_parser(const ratexpset_t &rs, const std::string &s, bool strict_alphabet)
Definition: exp_parser.hh:59
ratexp_t parseSqrBrkt(const T &)
Definition: exp_parser.hh:244
typename ratexpset_t::value_t ratexp_t
Definition: exp_parser.hh:56
ratexp_t parseE()
Definition: exp_parser.hh:67
RatExpSet ratexpset_t
Definition: exp_parser.hh:53
void ignore()
Definition: exp_parser.hh:324
ratexp_t parseS()
Definition: exp_parser.hh:102
ratexp_t parseL()
Definition: exp_parser.hh:175
size_t p_
Definition: exp_parser.hh:333
ratexp_t parseSqrBrkt(const letterset< set_alphabet< pair_letters< F, S >>> &)
Definition: exp_parser.hh:311
ratexp_t parseSqrBrkt(const wordset< T > &)
Definition: exp_parser.hh:318
weightset_t_of< ratexpset_t > weightset_t
Definition: exp_parser.hh:57
labelset_t_of< context_t > labelset_t
Definition: exp_parser.hh:55
ratexp_t parseR()
Definition: exp_parser.hh:193
Provide a variadic mul on top of a binary mul(), and one().
Definition: weightset.hh:38