contrib/nitcc/src/autom.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 # Finite automaton (NFA & DFA)
  16 module autom
  17
  18 # For the class Token
  19 import grammar
  20
  21 # A finite automaton
  22 class Automaton
  23         # The start state
  24         var start: State is noinit
  25
  26         # State that are accept states
  27         var accept = new Array[State]
  28
  29         # All states
  30         var states = new Array[State]
  31
  32         # Tokens associated on accept states.
  33         # Use `add_tag` to update
  34         var tags = new HashMap[State, Set[Token]]
  35
  36         # Accept states associated on tokens.
  37         # Use `add_tag` to update
  38         var retrotags = new HashMap[Token, Set[State]]
  39
  40         # Tag all accept states
  41         fun tag_accept(t: Token)
  42         do
  43                 for s in accept do add_tag(s, t)
  44         end
  45
  46         # Add a token to a state
  47         fun add_tag(s: State, t: Token)
  48         do
  49                 if not tags.has_key(s) then
  50                         var set = new ArraySet[Token]
  51                         tags[s] = set
  52                         set.add t
  53                 else
  54                         tags[s].add t
  55                 end
  56
  57                 if not retrotags.has_key(t) then
  58                         var set = new ArraySet[State]
  59                         retrotags[t] = set
  60                         set.add s
  61                 else
  62                         retrotags[t].add s
  63                 end
  64
  65                 assert tags[s].has(t)
  66                 assert retrotags[t].has(s)
  67         end
  68
  69         # Remove all occurrences of a tag in an automaton
  70         fun clear_tag(t: Token)
  71         do
  72                 if not retrotags.has_key(t) then return
  73                 for s in retrotags[t] do
  74                         if not tags.has_key(s) then continue
  75                         tags[s].remove(t)
  76                         if tags[s].is_empty then tags.keys.remove(s)
  77                 end
  78                 retrotags.keys.remove(t)
  79         end
  80
  81         # Remove tokens from conflicting state according the inclusion of language.
  82         # REQUIRE: self isa DFA automaton
  83         fun solve_token_inclusion
  84         do
  85                 for s, ts in tags do
  86                         if ts.length <= 1 then continue
  87                         var losers = new Array[Token]
  88                         for t1 in ts do
  89                                 for t2 in ts do
  90                                         if t1 == t2 then continue
  91                                         if retrotags[t1].length > retrotags[t2].length and retrotags[t1].has_all(retrotags[t2]) then
  92                                                 losers.add(t1)
  93                                                 break
  94                                         end
  95                                 end
  96                         end
  97                         for t in losers do
  98                                 ts.remove(t)
  99                                 retrotags[t].remove s
 100                         end
 101                 end
 102         end
 103
 104         # Initialize a new automaton for the empty language.
 105         # One state, no accept, no transition.
 106         init empty
 107         do
 108                 var state = new State
 109                 start = state
 110                 states.add state
 111         end
 112
 113         # Initialize a new automaton for the empty-string language.
 114         # One state, is accept, no transition.
 115         init epsilon
 116         do
 117                 var state = new State
 118                 start = state
 119                 accept.add state
 120                 states.add state
 121         end
 122
 123         # Initialize a new automation for the language that accepts only a single symbol.
 124         # Two state, the second is accept, one transition on `symbol`.
 125         init atom(symbol: Int)
 126         do
 127                 var s = new State
 128                 var a = new State
 129                 var sym = new TSymbol(symbol, symbol)
 130                 s.add_trans(a, sym)
 131                 start = s
 132                 accept.add a
 133                 states.add s
 134                 states.add a
 135         end
 136
 137         # Initialize a new automation for the language that accepts only a range of symbols
 138         # Two state, the second is accept, one transition for `from` to `to`
 139         init cla(first: Int, last: nullable Int)
 140         do
 141                 var s = new State
 142                 var a = new State
 143                 var sym = new TSymbol(first, last)
 144                 s.add_trans(a, sym)
 145                 start = s
 146                 accept.add a
 147                 states.add s
 148                 states.add a
 149         end
 150
 151         # Concatenate `other` to `self`.
 152         # Other is modified and invalidated.
 153         fun concat(other: Automaton)
 154         do
 155                 var s2 = other.start
 156                 for a1 in accept do
 157                         a1.add_trans(s2, null)
 158                 end
 159                 accept = other.accept
 160                 states.add_all other.states
 161         end
 162
 163         # `self` become the alternation of `self` and `other`.
 164         # `other` is modified and invalidated.
 165         fun alternate(other: Automaton)
 166         do
 167                 var s = new State
 168                 var a = new State
 169                 s.add_trans(start, null)
 170                 for a1 in accept do
 171                         a1.add_trans(a, null)
 172                 end
 173                 s.add_trans(other.start, null)
 174                 for a2 in other.accept do
 175                         a2.add_trans(a, null)
 176                         accept.add(a2)
 177                 end
 178
 179                 start = s
 180                 accept = [a]
 181
 182                 states.add s
 183                 states.add a
 184                 states.add_all other.states
 185         end
 186
 187         # Return a new automaton that recognize `self` but not `other`.
 188         # For a theoretical POV, this is the subtraction of languages.
 189         # Note: the implementation use `to_dfa` internally, so the theoretical complexity is not cheap.
 190         fun except(other: Automaton): Automaton
 191         do
 192                 var ta = new Token("1")
 193                 self.tag_accept(ta)
 194                 var tb = new Token("2")
 195                 other.tag_accept(tb)
 196
 197                 var c = new Automaton.empty
 198                 c.absorb(self)
 199                 c.absorb(other)
 200                 c = c.to_dfa
 201                 c.accept.clear
 202                 for s in c.retrotags[ta] do
 203                         if not c.tags[s].has(tb) then
 204                                 c.accept.add(s)
 205                         end
 206                 end
 207                 c.clear_tag(ta)
 208                 c.clear_tag(tb)
 209                 return c
 210         end
 211
 212         # `self` absorbs all states, transitions, tags, and acceptations of `other`.
 213         # An epsilon transition is added between `self.start` and `other.start`.
 214         fun absorb(other: Automaton)
 215         do
 216                 states.add_all other.states
 217                 start.add_trans(other.start, null)
 218                 for s, ts in other.tags do for t in ts do add_tag(s, t)
 219                 accept.add_all other.accept
 220         end
 221
 222         # Do the Kleene closure (*) on self
 223         fun close
 224         do
 225                 for a1 in accept do
 226                         a1.add_trans(start, null)
 227                         start.add_trans(a1, null)
 228                 end
 229         end
 230
 231         # Do the + on self
 232         fun plus
 233         do
 234                 for a1 in accept do
 235                         a1.add_trans(start, null)
 236                 end
 237         end
 238
 239         # Do the ? on self
 240         fun optionnal
 241         do
 242                 alternate(new Automaton.epsilon)
 243         end
 244
 245         # Remove all transitions on a given symbol
 246         fun minus_sym(symbol: TSymbol)
 247         do
 248                 var f = symbol.first
 249                 var l = symbol.last
 250                 for s in states do
 251                         for t in s.outs.to_a do
 252                                 if t.symbol == null then continue
 253
 254                                 # Check overlaps
 255                                 var tf = t.symbol.first
 256                                 var tl = t.symbol.last
 257                                 if l != null and tf > l then continue
 258                                 if tl != null and f > tl then continue
 259
 260                                 t.delete
 261
 262                                 # Add left and right part if non empty
 263                                 if tf < f then
 264                                         var sym = new TSymbol(tf,f-1)
 265                                         s.add_trans(t.to, sym)
 266                                 end
 267                                 if l != null then
 268                                         if tl == null then
 269                                                 var sym = new TSymbol(l+1, null)
 270                                                 s.add_trans(t.to, sym)
 271                                         else if tl > l then
 272                                                 var sym = new TSymbol(l+1, tl)
 273                                                 s.add_trans(t.to, sym)
 274                                         end
 275                                 end
 276                         end
 277                 end
 278         end
 279
 280         # Fully duplicate an automaton
 281         fun dup: Automaton
 282         do
 283                 var res = new Automaton.empty
 284                 var map = new HashMap[State, State]
 285                 map[start] = res.start
 286                 for s in states do
 287                         if s == start then continue
 288                         var s2 = new State
 289                         map[s] = s2
 290                         res.states.add(s2)
 291                 end
 292                 for s in accept do
 293                         res.accept.add map[s]
 294                 end
 295                 for s, ts in tags do for t in ts do
 296                         res.add_tag(map[s], t)
 297                 end
 298                 for s in states do
 299                         for t in s.outs do
 300                                 map[s].add_trans(map[t.to], t.symbol)
 301                         end
 302                 end
 303                 return res
 304         end
 305
 306         # Reverse an automaton in place
 307         fun reverse
 308         do
 309                 for s in states do
 310                         var tmp = s.ins
 311                         s.ins = s.outs
 312                         s.outs = tmp
 313                         for t in s.outs do
 314                                 var tmp2 = t.from
 315                                 t.from = t.to
 316                                 t.to = tmp2
 317                         end
 318                 end
 319                 var st = start
 320                 if accept.length == 1 then
 321                         start = accept.first
 322                 else
 323                         var st2 = new State
 324                         start = st2
 325                         states.add(st2)
 326
 327                         for s in accept do
 328                                 st2.add_trans(s, null)
 329                         end
 330                 end
 331                 accept.clear
 332                 accept.add(st)
 333         end
 334
 335         # Remove states (and transitions) that does not reach an accept state
 336         fun trim
 337         do
 338                 # Good states are those we want to keep
 339                 var goods = new HashSet[State]
 340                 goods.add_all(accept)
 341
 342                 var todo = accept.to_a
 343
 344                 # Propagate goodness
 345                 while not todo.is_empty do
 346                         var s = todo.pop
 347                         for t in s.ins do
 348                                 var s2 = t.from
 349                                 if goods.has(s2) then continue
 350                                 goods.add(s2)
 351                                 todo.add(s2)
 352                         end
 353                 end
 354
 355                 # What are the bad state then?
 356                 var bads = new Array[State]
 357                 for s in states do
 358                         if not goods.has(s) then bads.add(s)
 359                 end
 360
 361                 # Remove their transitions
 362                 for s in bads do
 363                         for t in s.ins do t.delete
 364                         for t in s.outs do t.delete
 365                 end
 366
 367                 # Keep only the good stuff
 368                 states.clear
 369                 states.add_all(goods)
 370         end
 371
 372         # Generate a minimal DFA
 373         # REQUIRE: self is a DFA
 374         fun to_minimal_dfa: Automaton
 375         do
 376                 trim
 377
 378                 # Graph of known distinct states.
 379                 var distincts = new HashMap[State, Set[State]]
 380                 for s in states do
 381                         distincts[s] = new HashSet[State]
 382                 end
 383
 384                 # split accept states.
 385                 # An accept state is distinct with a non accept state.
 386                 for s1 in states do
 387                         for s2 in states do
 388                                 if distincts[s1].has(s2) then continue
 389                                 if not accept.has(s1) then continue
 390                                 if not accept.has(s2) then
 391                                         distincts[s1].add(s2)
 392                                         distincts[s2].add(s1)
 393                                         continue
 394                                 end
 395                                 if tags.get_or_null(s1) != tags.get_or_null(s2) then
 396                                         distincts[s1].add(s2)
 397                                         distincts[s2].add(s1)
 398                                         continue
 399                                 end
 400                         end
 401                 end
 402
 403                 # Fixed point algorithm.
 404                 # * Get 2 states s1 and s2 not yet distinguished.
 405                 # * Get a symbol w.
 406                 # * If s1.trans(w) and s2.trans(w) are distinguished, then
 407                 #   distinguish s1 and s2.
 408                 var changed = true
 409                 var ints = new Array[Int] # List of symbols to check
 410                 while changed do
 411                         changed = false
 412                         for s1 in states do for s2 in states do
 413                                 if distincts[s1].has(s2) then continue
 414
 415                                 # The transitions use intervals. Therefore, for the states s1 and s2,
 416                                 # we need to check only the meaningful symbols. They are the `first`
 417                                 # symbol of each interval and the first one after the interval (`last+1`).
 418                                 ints.clear
 419                                 # Check only `s1`; `s2` will be checked later when s1 and s2 are switched.
 420                                 for t in s1.outs do
 421                                         var sym = t.symbol
 422                                         assert sym != null
 423                                         ints.add sym.first
 424                                         var l = sym.last
 425                                         if l != null then ints.add l + 1
 426                                 end
 427
 428                                 # Check each symbol
 429                                 for i in ints do
 430                                         var ds1 = s1.trans(i)
 431                                         var ds2 = s2.trans(i)
 432                                         if ds1 == ds2 then continue
 433                                         if ds1 != null and ds2 != null and not distincts[ds1].has(ds2) then continue
 434                                         distincts[s1].add(s2)
 435                                         distincts[s2].add(s1)
 436                                         changed = true
 437                                         break
 438                                 end
 439                         end
 440                 end
 441
 442                 # We need to unify not-distinguished states.
 443                 # Just add an epsilon-transition and DFAize the automaton.
 444                 for s1 in states do for s2 in states do
 445                         if distincts[s1].has(s2) then continue
 446                         s1.add_trans(s2, null)
 447                 end
 448
 449                 return to_dfa
 450         end
 451
 452         # Produce a graphvis file for the automaton
 453         fun to_dot(filepath: String)
 454         do
 455                 var names = new HashMap[State, String]
 456                 var ni = 0
 457                 for s in states do
 458                         names[s] = ni.to_s
 459                         ni += 1
 460                 end
 461
 462                 var f = new FileWriter.open(filepath)
 463                 f.write("digraph g \{\n")
 464
 465                 for s in states do
 466                         f.write("s{names[s]}[shape=oval")
 467                         #f.write("label=\"\",")
 468                         if accept.has(s) then
 469                                 f.write(",color=blue")
 470                         end
 471                         if tags.has_key(s) then
 472                                 f.write(",label=\"")
 473                                 for token in tags[s] do
 474                                         f.write("{token.name.escape_to_c}\\n")
 475                                 end
 476                                 f.write("\"")
 477                         else
 478                                 f.write(",label=\"\"")
 479                         end
 480                         f.write("];\n")
 481                         var outs = new HashMap[State, Array[nullable TSymbol]]
 482                         for t in s.outs do
 483                                 var a
 484                                 var s2 = t.to
 485                                 var c = t.symbol
 486                                 if outs.has_key(s2) then
 487                                         a = outs[s2]
 488                                 else
 489                                         a = new Array[nullable TSymbol]
 490                                         outs[s2] = a
 491                                 end
 492                                 a.add(c)
 493                         end
 494                         for s2, a in outs do
 495                                 var labe = ""
 496                                 for c in a do
 497                                         if not labe.is_empty then labe += "\n"
 498                                         if c == null then
 499                                                 labe += "''"
 500                                         else
 501                                                 labe += c.to_s
 502                                         end
 503                                 end
 504                                 f.write("s{names[s]}->s{names[s2]} [label=\"{labe.escape_to_c}\"];\n")
 505                         end
 506                 end
 507                 f.write("empty->s{names[start]}; empty[label=\"\",shape=none];\n")
 508
 509                 f.write("\}\n")
 510                 f.close
 511         end
 512
 513         # Transform a NFA to a DFA.
 514         # note: the DFA is not minimized.
 515         fun to_dfa: Automaton
 516         do
 517                 trim
 518
 519                 var dfa = new Automaton.empty
 520                 var n2d = new ArrayMap[Set[State], State]
 521                 var seen = new ArraySet[Set[State]]
 522                 var alphabet = new HashSet[Int]
 523                 var st = eclosure([start])
 524                 var todo = [st]
 525                 n2d[st] = dfa.start
 526                 seen.add(st)
 527                 while not todo.is_empty do
 528                         var nfa_states = todo.pop
 529                         #print "* work on {nfa_states.inspect}={nfa_states} (remains {todo.length}/{seen.length})"
 530                         var dfa_state = n2d[nfa_states]
 531                         alphabet.clear
 532                         for s in nfa_states do
 533                                 # Collect important values to build the alphabet
 534                                 for t in s.outs do
 535                                         var sym = t.symbol
 536                                         if sym == null then continue
 537                                         alphabet.add(sym.first)
 538                                         var l = sym.last
 539                                         if l != null then alphabet.add(l)
 540                                 end
 541
 542                                 # Mark accept and tags
 543                                 if accept.has(s) then
 544                                         if tags.has_key(s) then
 545                                                 for t in tags[s] do
 546                                                         dfa.add_tag(dfa_state, t)
 547                                                 end
 548                                         end
 549                                         dfa.accept.add(dfa_state)
 550                                 end
 551                         end
 552
 553                         # From the important values, build a sequence of TSymbols
 554                         var a = alphabet.to_a
 555                         default_comparator.sort(a)
 556                         var tsyms = new Array[TSymbol]
 557                         var last = 0
 558                         for i in a do
 559                                 if last > 0 and last <= i-1 then
 560                                         tsyms.add(new TSymbol(last,i-1))
 561                                 end
 562                                 tsyms.add(new TSymbol(i,i))
 563                                 last = i+1
 564                         end
 565                         if last > 0 then
 566                                 tsyms.add(new TSymbol(last,null))
 567                         end
 568                         #print "Alphabet: {tsyms.join(", ")}"
 569
 570                         var lastst: nullable Transition = null
 571                         for sym in tsyms do
 572                                 var nfa_dest = eclosure(trans(nfa_states, sym.first))
 573                                 if nfa_dest.is_empty then
 574                                         lastst = null
 575                                         continue
 576                                 end
 577                                 #print "{nfa_states} -> {sym} -> {nfa_dest}"
 578                                 var dfa_dest
 579                                 if seen.has(nfa_dest) then
 580                                         #print "* reuse {nfa_dest.inspect}={nfa_dest}"
 581                                         dfa_dest = n2d[nfa_dest]
 582                                 else
 583                                         #print "* new {nfa_dest.inspect}={nfa_dest}"
 584                                         dfa_dest = new State
 585                                         dfa.states.add(dfa_dest)
 586                                         n2d[nfa_dest] = dfa_dest
 587                                         todo.add(nfa_dest)
 588                                         seen.add(nfa_dest)
 589                                 end
 590                                 if lastst != null and lastst.to == dfa_dest then
 591                                         lastst.symbol.last = sym.last
 592                                 else
 593                                         lastst = dfa_state.add_trans(dfa_dest, sym)
 594                                 end
 595                         end
 596                 end
 597                 return dfa
 598         end
 599
 600         # Epsilon-closure on a state of states.
 601         # Used by `to_dfa`.
 602         private fun eclosure(states: Collection[State]): Set[State]
 603         do
 604                 var res = new ArraySet[State]
 605                 res.add_all(states)
 606                 var todo = states.to_a
 607                 while not todo.is_empty do
 608                         var s = todo.pop
 609                         for t in s.outs do
 610                                 if t.symbol != null then continue
 611                                 var to = t.to
 612                                 if res.has(to) then continue
 613                                 res.add(to)
 614                                 todo.add(to)
 615                         end
 616                 end
 617                 return res
 618         end
 619
 620         # Trans on a set of states.
 621         # Used by `to_dfa`.
 622         fun trans(states: Collection[State], symbol: Int): Set[State]
 623         do
 624                 var res = new ArraySet[State]
 625                 for s in states do
 626                         for t in s.outs do
 627                                 var sym = t.symbol
 628                                 if sym == null then continue
 629                                 if sym.first > symbol then continue
 630                                 var l = sym.last
 631                                 if l != null and l < symbol then continue
 632                                 var to = t.to
 633                                 if res.has(to) then continue
 634                                 res.add(to)
 635                         end
 636                 end
 637                 return res
 638         end
 639
 640         # Generate the Nit source code of the lexer.
 641         # `filepath` is the name of the output file.
 642         # `parser` is the name of the parser module (used to import the token classes).
 643         fun gen_to_nit(filepath: String, name: String, parser: nullable String)
 644         do
 645                 var gen = new DFAGenerator(filepath, name, self, parser)
 646                 gen.gen_to_nit
 647         end
 648 end
 649
 650 # Generate the Nit source code of the lexer
 651 private class DFAGenerator
 652         var filepath: String
 653         var name: String
 654         var automaton: Automaton
 655         var parser: nullable String
 656
 657         var out: Writer is noinit
 658
 659         init do
 660                 self.out = new FileWriter.open(filepath)
 661         end
 662
 663         fun add(s: String) do out.write(s)
 664
 665         fun gen_to_nit
 666         do
 667                 var names = new HashMap[State, String]
 668                 var i = 0
 669                 for s in automaton.states do
 670                         names[s] = i.to_s
 671                         i += 1
 672                 end
 673
 674                 add "# Lexer generated by nitcc for the grammar {name}\n"
 675                 add "module {name}_lexer is no_warning \"missing-doc\"\n"
 676                 add("import nitcc_runtime\n")
 677
 678                 var p = parser
 679                 if p != null then add("import {p}\n")
 680
 681                 add("class Lexer_{name}\n")
 682                 add("\tsuper Lexer\n")
 683                 add("\tredef fun start_state do return dfastate_{names[automaton.start]}\n")
 684                 add("end\n")
 685
 686                 for s in automaton.states do
 687                         var n = names[s]
 688                         add("private fun dfastate_{n}: DFAState{n} do return once new DFAState{n}\n")
 689                 end
 690
 691                 add("class MyNToken\n")
 692                 add("\tsuper NToken\n")
 693                 add("end\n")
 694
 695                 for s in automaton.states do
 696                         var  n = names[s]
 697                         add("private class DFAState{n}\n")
 698                         add("\tsuper DFAState\n")
 699                         if automaton.accept.has(s) then
 700                                 var token
 701                                 if automaton.tags.has_key(s) then
 702                                         token = automaton.tags[s].first
 703                                 else
 704                                         token = null
 705                                 end
 706                                 add("\tredef fun is_accept do return true\n")
 707                                 var is_ignored = false
 708                                 if token != null and token.name == "Ignored" then
 709                                         is_ignored = true
 710                                         add("\tredef fun is_ignored do return true\n")
 711                                 end
 712                                 add("\tredef fun make_token(position, source) do\n")
 713                                 if is_ignored then
 714                                         add("\t\treturn null\n")
 715                                 else
 716                                         if token == null then
 717                                                 add("\t\tvar t = new MyNToken\n")
 718                                                 add("\t\tt.text = position.extract(source)\n")
 719                                         else
 720                                                 add("\t\tvar t = new {token.cname}\n")
 721                                                 var ttext = token.text
 722                                                 if ttext == null then
 723                                                         add("\t\tt.text = position.extract(source)\n")
 724                                                 else
 725                                                         add("\t\tt.text = \"{ttext.escape_to_nit}\"\n")
 726                                                 end
 727                                         end
 728                                         add("\t\tt.position = position\n")
 729                                         add("\t\treturn t\n")
 730                                 end
 731                                 add("\tend\n")
 732                         end
 733                         var trans = new ArrayMap[TSymbol, State]
 734                         for t in s.outs do
 735                                 var sym = t.symbol
 736                                 assert sym != null
 737                                 trans[sym] = t.to
 738                         end
 739                         if trans.is_empty then
 740                                 # Do nothing, inherit the trans
 741                         else
 742                                 add("\tredef fun trans(char) do\n")
 743
 744                                 # Collect the sequence of tests in the dispatch sequence
 745                                 # The point here is that for each transition, there is a first and a last
 746                                 # So holes have to be identified
 747                                 var dispatch = new HashMap[Int, nullable State]
 748                                 var haslast: nullable State = null
 749
 750                                 var last = -1
 751                                 for sym, next in trans do
 752                                         assert haslast == null
 753                                         assert sym.first > last
 754                                         if sym.first > last + 1 then
 755                                                 dispatch[sym.first-1] = null
 756                                         end
 757                                         var l = sym.last
 758                                         if l == null then
 759                                                 haslast = next
 760                                         else
 761                                                 dispatch[l] = next
 762                                                 last = l
 763                                         end
 764                                 end
 765
 766                                 if dispatch.is_empty and haslast != null then
 767                                         # Only one transition that accepts everything (quite rare)
 768                                 else
 769                                         # We need to check
 770                                         add("\t\tvar c = char.code_point\n")
 771                                 end
 772
 773                                 # Generate a sequence of `if` for the dispatch
 774                                 if haslast != null and last >= 0 then
 775                                         # Special case: handle up-bound first if not an error
 776                                         add("\t\tif c > {last} then return dfastate_{names[haslast]}\n")
 777                                         # previous become the new last case
 778                                         haslast = dispatch[last]
 779                                         dispatch.keys.remove(last)
 780                                 end
 781                                 for c, next in dispatch do
 782                                         if next == null then
 783                                                 add("\t\tif c <= {c} then return null\n")
 784                                         else
 785                                                 add("\t\tif c <= {c} then return dfastate_{names[next]}\n")
 786                                         end
 787                                 end
 788                                 if haslast == null then
 789                                         add("\t\treturn null\n")
 790                                 else
 791                                         add("\t\treturn dfastate_{names[haslast]}\n")
 792                                 end
 793
 794                                 add("\tend\n")
 795                         end
 796                         add("end\n")
 797                 end
 798
 799                 self.out.close
 800         end
 801 end
 802
 803 redef class Token
 804         # The associated text (if any, ie defined in the parser part)
 805         var text: nullable String is noautoinit, writable
 806 end
 807
 808 # A state in a finite automaton
 809 class State
 810         # Outgoing transitions
 811         var outs = new Array[Transition]
 812
 813         # Ingoing transitions
 814         var ins = new Array[Transition]
 815
 816         # Add a transitions to `to` on `symbol` (null means epsilon)
 817         fun add_trans(to: State, symbol: nullable TSymbol): Transition
 818         do
 819                 var t = new Transition(self, to, symbol)
 820                 outs.add(t)
 821                 to.ins.add(t)
 822                 return t
 823         end
 824
 825         # Get the first state following the transition `i`.
 826         # Null if no transition for `i`.
 827         fun trans(i: Int): nullable State
 828         do
 829                 for t in outs do
 830                         var sym = t.symbol
 831                         assert sym != null
 832                         var f = sym.first
 833                         var l = sym.last
 834                         if i < f then continue
 835                         if l != null and i > l then continue
 836                         return t.to
 837                 end
 838                 return null
 839         end
 840 end
 841
 842 # A range of symbols on a transition
 843 class TSymbol
 844         # The first symbol in the range
 845         var first: Int
 846
 847         # The last symbol if any.
 848         #
 849         # `null` means infinity.
 850         var last: nullable Int
 851
 852         redef fun to_s
 853         do
 854                 var res
 855                 var f = first
 856                 if f <= 32 then
 857                         res = "#{f}"
 858                 else
 859                         res = f.code_point.to_s
 860                 end
 861                 var l = last
 862                 if f == l then return res
 863                 res += " .. "
 864                 if l == null then return res
 865                 if l <= 32 or l >= 127 then return res + "#{l}"
 866                 return res + l.code_point.to_s
 867         end
 868 end
 869
 870 # A transition in a finite automaton
 871 class Transition
 872         # The source state
 873         var from: State
 874         # The destination state
 875         var to: State
 876         # The symbol on the transition (null means epsilon)
 877         var symbol: nullable TSymbol
 878
 879         # Remove the transition from the automaton.
 880         # Detach from `from` and `to`.
 881         fun delete
 882         do
 883                 from.outs.remove(self)
 884                 to.ins.remove(self)
 885         end
 886 end