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 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.first.ascii)
  54                 return a
  55         end
  56 end
  57
  58 redef class NProd
  59         redef fun make_rfa: Automaton
  60         do
  61                 assert children.length == 1 else print "no make_rfa for {self}"
  62                 return children.first.make_rfa
  63         end
  64 end
  65
  66 redef class Nre_alter
  67         redef fun make_rfa
  68         do
  69                 var a = children[0].make_rfa
  70                 var b = children[2].make_rfa
  71                 a.alternate(b)
  72                 return a
  73         end
  74 end
  75
  76 redef class Nre_minus
  77         redef fun make_rfa
  78         do
  79                 var a = children[0].make_rfa
  80                 var b = children[2].make_rfa.to_dfa
  81                 for t in b.start.outs do
  82                         if not t.to.outs.is_empty then
  83                                 print "Not Yet Implemented Error: '-' only works on single char"
  84                                 exit(1)
  85                         end
  86                         a.minus_sym(t.symbol.as(not null))
  87                 end
  88                 return a
  89         end
  90 end
  91
  92 redef class Nre_and
  93         redef fun make_rfa
  94         do
  95                 var a = children[0].make_rfa
  96                 var ta = new Token("1")
  97                 a.tag_accept(ta)
  98                 var b = children[2].make_rfa
  99                 var tb = new Token("2")
 100                 b.tag_accept(tb)
 101
 102                 var c = new Automaton.empty
 103                 c.absorb(a)
 104                 c.absorb(b)
 105                 c = c.to_dfa
 106                 c.accept.clear
 107                 for s in c.retrotags[ta] do
 108                         if c.tags[s].has(tb) then
 109                                 c.accept.add(s)
 110                         end
 111                 end
 112                 c.clear_tag(ta)
 113                 c.clear_tag(tb)
 114                 return c
 115         end
 116 end
 117
 118 redef class Nre_except
 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 not 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_shortest
 145         redef fun make_rfa
 146         do
 147                 var a = children[2].make_rfa
 148                 a = a.to_dfa
 149                 for s in a.accept do
 150                         for t in s.outs.to_a do t.delete
 151                 end
 152                 return a
 153         end
 154 end
 155
 156 redef class Nre_longest
 157         redef fun make_rfa
 158         do
 159                 var a = children[2].make_rfa
 160                 a = a.to_dfa
 161                 for s in a.accept.to_a do
 162                         if not s.outs.is_empty then a.accept.remove(s)
 163                 end
 164                 return a
 165         end
 166 end
 167
 168 redef class Nre_conc
 169         redef fun make_rfa
 170         do
 171                 var a = children[0].make_rfa
 172                 var b = children[1].make_rfa
 173                 a.concat(b)
 174                 return a
 175         end
 176 end
 177
 178 redef class Nre_star
 179         redef fun make_rfa
 180         do
 181                 var a = children[0].make_rfa
 182                 a.close
 183                 return a
 184         end
 185 end
 186
 187 redef class Nre_ques
 188         redef fun make_rfa
 189         do
 190                 var a = children[0].make_rfa
 191                 a.optionnal
 192                 return a
 193         end
 194 end
 195
 196 redef class Nre_plus
 197         redef fun make_rfa
 198         do
 199                 var a = children[0].make_rfa
 200                 a.plus
 201                 return a
 202         end
 203 end
 204
 205 redef class Nre_par
 206         redef fun make_rfa
 207         do
 208                 return children[1].make_rfa
 209         end
 210 end
 211
 212 redef class Nre_class
 213         redef fun make_rfa: Automaton
 214         do
 215                 var c1 = children[0].children[0].value
 216                 var c2 = children[3].children[0].value
 217                 if c1.length != 1 or c2.length != 1 then
 218                         print "Classes only works on single char"
 219                         exit(1)
 220                         abort
 221                 end
 222                 var a = new Automaton.cla(c1.first.ascii, c2.first.ascii)
 223                 return a
 224         end
 225 end
 226
 227 redef class Nre_any
 228         redef fun make_rfa: Automaton
 229         do
 230                 var a = new Automaton.cla(0, null)
 231                 return a
 232         end
 233 end