contrib/nitcc/src/re2nfa.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Licensed under the Apache License, Version 2.0 (the "License");
   4 # you may not use this file except in compliance with the License.
   5 # You may obtain a copy of the License at
   6 #
   7 #     http://www.apache.org/licenses/LICENSE-2.0
   8 #
   9 # Unless required by applicable law or agreed to in writing, software
  10 # distributed under the License is distributed on an "AS IS" BASIS,
  11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 # See the License for the specific language governing permissions and
  13 # limitations under the License.
  14
  15 # Transformation of regular expression to NFA
  16 module re2nfa
  17
  18 import nitcc_lexer
  19 import autom
  20
  21 redef class Node
  22         # Build the NFA of the regular expression
  23         fun make_rfa: Automaton do
  24                 print inspect
  25                 abort
  26         end
  27
  28         # The real value of the string
  29         fun value: String do
  30                 print inspect
  31                 abort
  32         end
  33 end
  34
  35 redef class Nstr
  36         redef fun value: String do return text.substring(1, text.length-2).unescape_nit
  37         redef fun make_rfa: Automaton
  38         do
  39                 var a = new Automaton.epsilon
  40                 var val
  41                 for c in self.value.chars do
  42                         var b = new Automaton.atom(c.ascii)
  43                         a.concat(b)
  44                 end
  45                 return a
  46         end
  47 end
  48
  49 redef class Nch_dec
  50         redef fun value: String do return text.substring_from(1).to_i.ascii.to_s
  51         redef fun make_rfa: Automaton
  52         do
  53                 var a = new Automaton.atom(self.value.chars.first.ascii)
  54                 return a
  55         end
  56 end
  57
  58 redef class Nch_hex
  59         redef fun value: String do return text.substring_from(2).to_hex.ascii.to_s
  60         redef fun make_rfa: Automaton
  61         do
  62                 var a = new Automaton.atom(self.value.chars.first.ascii)
  63                 return a
  64         end
  65 end
  66
  67 redef class NProd
  68         redef fun make_rfa: Automaton
  69         do
  70                 assert children.length == 1 else print "no make_rfa for {self}"
  71                 return children.first.make_rfa
  72         end
  73 end
  74
  75 redef class Nre_alter
  76         redef fun make_rfa
  77         do
  78                 var a = children[0].make_rfa
  79                 var b = children[2].make_rfa
  80                 a.alternate(b)
  81                 return a
  82         end
  83 end
  84
  85 redef class Nre_minus
  86         redef fun make_rfa
  87         do
  88                 var a = children[0].make_rfa
  89                 var b = children[2].make_rfa.to_dfa
  90                 for t in b.start.outs do
  91                         if not t.to.outs.is_empty then
  92                                 # `b` is not a single char, so just use except
  93                                 # "a - b == a Except (Any* b Any*)"
  94                                 var any1 = new Automaton.cla(0, null)
  95                                 any1.close
  96                                 var any2 = new Automaton.cla(0, null)
  97                                 any2.close
  98                                 var b2 = any1
  99                                 b2.concat(b)
 100                                 b2.concat(any2)
 101                                 var c = a.except(b2)
 102                                 return c
 103                         end
 104                         a.minus_sym(t.symbol.as(not null))
 105                 end
 106                 return a
 107         end
 108 end
 109
 110 redef class Nre_end
 111         redef fun make_rfa
 112         do
 113                 print "{children.first.position.to_s}: NOT YET IMPLEMENTED: token `End`; replaced with an empty string"
 114                 return new Automaton.epsilon
 115         end
 116 end
 117
 118 redef class Nre_and
 119         redef fun make_rfa
 120         do
 121                 var a = children[0].make_rfa
 122                 var ta = new Token("1")
 123                 a.tag_accept(ta)
 124                 var b = children[2].make_rfa
 125                 var tb = new Token("2")
 126                 b.tag_accept(tb)
 127
 128                 var c = new Automaton.empty
 129                 c.absorb(a)
 130                 c.absorb(b)
 131                 c = c.to_dfa
 132                 c.accept.clear
 133                 for s in c.retrotags[ta] do
 134                         if c.tags[s].has(tb) then
 135                                 c.accept.add(s)
 136                         end
 137                 end
 138                 c.clear_tag(ta)
 139                 c.clear_tag(tb)
 140                 return c
 141         end
 142 end
 143
 144 redef class Nre_except
 145         redef fun make_rfa
 146         do
 147                 var a = children[0].make_rfa
 148                 var b = children[2].make_rfa
 149                 return a.except(b)
 150         end
 151 end
 152
 153 redef class Nre_shortest
 154         redef fun make_rfa
 155         do
 156                 var a = children[2].make_rfa
 157                 a = a.to_dfa
 158                 for s in a.accept do
 159                         for t in s.outs.to_a do t.delete
 160                 end
 161                 return a
 162         end
 163 end
 164
 165 redef class Nre_longest
 166         redef fun make_rfa
 167         do
 168                 var a = children[2].make_rfa
 169                 a = a.to_dfa
 170                 for s in a.accept.to_a do
 171                         if not s.outs.is_empty then a.accept.remove(s)
 172                 end
 173                 return a
 174         end
 175 end
 176
 177 redef class Nre_conc
 178         redef fun make_rfa
 179         do
 180                 var a = children[0].make_rfa
 181                 var b = children[1].make_rfa
 182                 a.concat(b)
 183                 return a
 184         end
 185 end
 186
 187 redef class Nre_star
 188         redef fun make_rfa
 189         do
 190                 var a = children[0].make_rfa
 191                 a.close
 192                 return a
 193         end
 194 end
 195
 196 redef class Nre_ques
 197         redef fun make_rfa
 198         do
 199                 var a = children[0].make_rfa
 200                 a.optionnal
 201                 return a
 202         end
 203 end
 204
 205 redef class Nre_plus
 206         redef fun make_rfa
 207         do
 208                 var a = children[0].make_rfa
 209                 a.plus
 210                 return a
 211         end
 212 end
 213
 214 redef class Nre_par
 215         redef fun make_rfa
 216         do
 217                 return children[1].make_rfa
 218         end
 219 end
 220
 221 redef class Nre_class
 222         redef fun make_rfa: Automaton
 223         do
 224                 var c1 = children[0].children[0].value
 225                 var c2 = children[3].children[0].value
 226                 if c1.length != 1 or c2.length != 1 then
 227                         print "Classes only works on single char"
 228                         exit(1)
 229                         abort
 230                 end
 231                 var a = new Automaton.cla(c1.chars.first.ascii, c2.chars.first.ascii)
 232                 return a
 233         end
 234 end
 235
 236 redef class Nre_any
 237         redef fun make_rfa: Automaton
 238         do
 239                 var a = new Automaton.cla(0, null)
 240                 return a
 241         end
 242 end