contrib/re_parser/src/re_parser.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 module re_parser
  16
  17 import nitcc::autom
  18 import re_parser_lexer
  19 import re_parser_parser
  20
  21 # Parse regular expression into NFA
  22 #
  23 # ~~~
  24 # # Parse the regular expression
  25 # var re = "(a|b)*"
  26 # var re_parser = new REParser
  27 # var node = re_parser.parse_re(re)
  28 #
  29 # # Check syntax errors
  30 # assert node != null else
  31 #       print re_parser.last_error.as(not null)
  32 # end
  33 #
  34 # # Build nfa and dfa
  35 # var nfa = re_parser.make_nfa(node)
  36 # print nfa.to_dot
  37 # print nfa.to_dfa.to_dot
  38 # ~~~
  39 class REParser
  40
  41         # Parse the regular expression `re` and return the root production node.
  42         #
  43         # Returns `null` in case of syntax error. See `last_error`.
  44         #
  45         # ~~~
  46         # var re_parser = new REParser
  47         #
  48         # # Valid regular expression
  49         # assert re_parser.parse_re("(a|b)*") != null
  50         # assert re_parser.last_error == null
  51         #
  52         # # Invalid regular expression
  53         # assert re_parser.parse_re("a|b)*") == null
  54         # assert re_parser.last_error != null
  55         # ~~~
  56         fun parse_re(re: String): nullable NProd do
  57                 var l = new Lexer_re_parser(re)
  58                 var ts = l.lex
  59
  60                 var p = new Parser_re_parser
  61                 p.tokens.add_all ts
  62
  63                 var node = p.parse
  64
  65                 if not node isa NProd then
  66                         if node isa NError then
  67                                 last_error = "{node.position.as(not null).to_s} Syntax Error: {node.message}"
  68                         else
  69                                 last_error = "Parsing Error: expected `NProd` got `{node.class_name}`"
  70                         end
  71                         return null
  72                 end
  73                 last_error = null
  74                 return node
  75         end
  76
  77         # Contains the error from the last call to `parse_re` or null if no error
  78         #
  79         # ~~~
  80         # var re_parser = new REParser
  81         #
  82         # # Invalid regular expression
  83         # assert re_parser.parse_re("a|b)*") == null
  84         # assert re_parser.last_error != null
  85         # ~~~
  86         var last_error: nullable String
  87
  88         # Build the NFA for `node`
  89         #
  90         # Use `parse_re` to transform a re string into a NProd.
  91         fun make_nfa(node: NProd): Automaton do
  92                 var v = new REVisitor
  93                 v.start(node)
  94                 return v.nfa
  95         end
  96 end
  97
  98 class REVisitor
  99         super Visitor
 100
 101         var nfa = new Automaton
 102
 103         fun start(n: Node) do
 104                 enter_visit(n)
 105         end
 106
 107         redef fun visit(n) do n.accept_revisitor(self)
 108 end
 109
 110 redef class Node
 111         fun accept_revisitor(v: REVisitor) do visit_children(v)
 112
 113         # Build the NFA of the regular expression
 114         fun make_nfa: Automaton do
 115                 print inspect
 116                 abort
 117         end
 118 end
 119
 120 redef class Nre
 121         redef fun accept_revisitor(v) do
 122                 v.nfa = make_nfa
 123         end
 124
 125         redef fun make_nfa do
 126                 var a = new Automaton
 127                 for child in children do
 128                         if child == null then continue
 129                         a.concat(child.make_nfa)
 130                 end
 131                 return a
 132         end
 133 end
 134
 135 redef class Nre_char
 136         redef fun make_nfa do
 137                 return new Automaton.atom(n_char.text.chars.first.code_point)
 138         end
 139 end
 140
 141 redef class Nre_alter
 142         redef fun make_nfa
 143         do
 144                 var a = n_re.make_nfa
 145                 var b = n_re2.make_nfa
 146                 a.alternate(b)
 147                 return a
 148         end
 149 end
 150
 151 redef class Nre_conc
 152         redef fun make_nfa
 153         do
 154                 var a = n_re.make_nfa
 155                 var b = n_re2.make_nfa
 156                 a.concat(b)
 157                 return a
 158         end
 159 end
 160
 161 redef class Nre_star
 162         redef fun make_nfa
 163         do
 164                 var a = n_re.make_nfa
 165                 a.close
 166                 return a
 167         end
 168 end
 169
 170 redef class Nre_ques
 171         redef fun make_nfa
 172         do
 173                 var a = n_re.make_nfa
 174                 a.optionnal
 175                 return a
 176         end
 177 end
 178
 179 redef class Nre_plus
 180         redef fun make_nfa
 181         do
 182                 var a = n_re.make_nfa
 183                 a.plus
 184                 return a
 185         end
 186 end
 187
 188 redef class Nre_par
 189         redef fun make_nfa
 190         do
 191                 return n_re.make_nfa
 192         end
 193 end
 194
 195 # Parse arguments
 196 if args.is_empty then
 197         print "usage: re_parser <re>"
 198         exit 1
 199 end
 200 var re = args.first
 201
 202 # Parse re
 203 var re_parser = new REParser
 204 var node = re_parser.parse_re(re)
 205
 206 if node == null then
 207         print re_parser.last_error.as(not null)
 208         exit 1
 209         abort
 210 end
 211
 212 # Build nfa and dfa
 213 var nfa = re_parser.make_nfa(node)
 214 nfa.to_dot(false).write_to_file("nfa.dot")
 215 nfa.to_dfa.to_dot(false).write_to_file("dfa.dot")
 216 print "Produced files `nfa.dot` and `dfa.dot`"