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.to_a do t.delete
 364                         for t in s.outs.to_a 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                 assert_valid
 377
 378                 trim
 379
 380                 # Graph of known distinct states.
 381                 var distincts = new HashMap[State, Set[State]]
 382                 for s in states do
 383                         distincts[s] = new HashSet[State]
 384                 end
 385
 386                 # split accept states.
 387                 # An accept state is distinct with a non accept state.
 388                 for s1 in states do
 389                         for s2 in states do
 390                                 if distincts[s1].has(s2) then continue
 391                                 if not accept.has(s1) then continue
 392                                 if not accept.has(s2) then
 393                                         distincts[s1].add(s2)
 394                                         distincts[s2].add(s1)
 395                                         continue
 396                                 end
 397                                 if tags.get_or_null(s1) != tags.get_or_null(s2) then
 398                                         distincts[s1].add(s2)
 399                                         distincts[s2].add(s1)
 400                                         continue
 401                                 end
 402                         end
 403                 end
 404
 405                 # Fixed point algorithm.
 406                 # * Get 2 states s1 and s2 not yet distinguished.
 407                 # * Get a symbol w.
 408                 # * If s1.trans(w) and s2.trans(w) are distinguished, then
 409                 #   distinguish s1 and s2.
 410                 var changed = true
 411                 var ints = new Array[Int] # List of symbols to check
 412                 while changed do
 413                         changed = false
 414                         for s1 in states do for s2 in states do
 415                                 if distincts[s1].has(s2) then continue
 416
 417                                 # The transitions use intervals. Therefore, for the states s1 and s2,
 418                                 # we need to check only the meaningful symbols. They are the `first`
 419                                 # symbol of each interval and the first one after the interval (`last+1`).
 420                                 ints.clear
 421                                 # Check only `s1`; `s2` will be checked later when s1 and s2 are switched.
 422                                 for t in s1.outs do
 423                                         var sym = t.symbol
 424                                         assert sym != null
 425                                         ints.add sym.first
 426                                         var l = sym.last
 427                                         if l != null then ints.add l + 1
 428                                 end
 429
 430                                 # Check each symbol
 431                                 for i in ints do
 432                                         var ds1 = s1.trans(i)
 433                                         var ds2 = s2.trans(i)
 434                                         if ds1 == ds2 then continue
 435                                         if ds1 != null and ds2 != null and not distincts[ds1].has(ds2) then continue
 436                                         distincts[s1].add(s2)
 437                                         distincts[s2].add(s1)
 438                                         changed = true
 439                                         break
 440                                 end
 441                         end
 442                 end
 443
 444                 # We need to unify not-distinguished states.
 445                 # Just add an epsilon-transition and DFAize the automaton.
 446                 for s1 in states do for s2 in states do
 447                         if distincts[s1].has(s2) then continue
 448                         s1.add_trans(s2, null)
 449                 end
 450
 451                 return to_dfa
 452         end
 453
 454         # Assert that `self` is a valid automaton or abort
 455         fun assert_valid
 456         do
 457                 assert states.has(start)
 458                 assert states.has_all(accept)
 459                 for s in states do
 460                         for t in s.outs do assert states.has(t.to)
 461                         for t in s.ins do assert states.has(t.from)
 462                 end
 463                 assert states.has_all(tags.keys)
 464                 for t, ss in retrotags do
 465                         assert states.has_all(ss)
 466                 end
 467         end
 468
 469         # Produce a graphvis file for the automaton
 470         fun to_dot(filepath: String)
 471         do
 472                 var names = new HashMap[State, String]
 473                 var ni = 0
 474                 for s in states do
 475                         names[s] = ni.to_s
 476                         ni += 1
 477                 end
 478
 479                 var f = new FileWriter.open(filepath)
 480                 f.write("digraph g \{\n")
 481
 482                 for s in states do
 483                         f.write("s{names[s]}[shape=oval")
 484                         #f.write("label=\"\",")
 485                         if accept.has(s) then
 486                                 f.write(",color=blue")
 487                         end
 488                         if tags.has_key(s) then
 489                                 f.write(",label=\"")
 490                                 for token in tags[s] do
 491                                         f.write("{token.name.escape_to_c}\\n")
 492                                 end
 493                                 f.write("\"")
 494                         else
 495                                 f.write(",label=\"\"")
 496                         end
 497                         f.write("];\n")
 498                         var outs = new HashMap[State, Array[nullable TSymbol]]
 499                         for t in s.outs do
 500                                 var a
 501                                 var s2 = t.to
 502                                 var c = t.symbol
 503                                 if outs.has_key(s2) then
 504                                         a = outs[s2]
 505                                 else
 506                                         a = new Array[nullable TSymbol]
 507                                         outs[s2] = a
 508                                 end
 509                                 a.add(c)
 510                         end
 511                         for s2, a in outs do
 512                                 var labe = ""
 513                                 for c in a do
 514                                         if not labe.is_empty then labe += "\n"
 515                                         if c == null then
 516                                                 labe += "''"
 517                                         else
 518                                                 labe += c.to_s
 519                                         end
 520                                 end
 521                                 f.write("s{names[s]}->s{names[s2]} [label=\"{labe.escape_to_c}\"];\n")
 522                         end
 523                 end
 524                 f.write("empty->s{names[start]}; empty[label=\"\",shape=none];\n")
 525
 526                 f.write("\}\n")
 527                 f.close
 528         end
 529
 530         # Transform a NFA to a DFA.
 531         # note: the DFA is not minimized.
 532         fun to_dfa: Automaton
 533         do
 534                 assert_valid
 535
 536                 trim
 537
 538                 var dfa = new Automaton.empty
 539                 var n2d = new ArrayMap[Set[State], State]
 540                 var seen = new ArraySet[Set[State]]
 541                 var alphabet = new HashSet[Int]
 542                 var st = eclosure([start])
 543                 var todo = [st]
 544                 n2d[st] = dfa.start
 545                 seen.add(st)
 546                 while not todo.is_empty do
 547                         var nfa_states = todo.pop
 548                         #print "* work on {nfa_states.inspect}={nfa_states} (remains {todo.length}/{seen.length})"
 549                         var dfa_state = n2d[nfa_states]
 550                         alphabet.clear
 551                         for s in nfa_states do
 552                                 # Collect important values to build the alphabet
 553                                 for t in s.outs do
 554                                         var sym = t.symbol
 555                                         if sym == null then continue
 556                                         alphabet.add(sym.first)
 557                                         var l = sym.last
 558                                         if l != null then alphabet.add(l)
 559                                 end
 560
 561                                 # Mark accept and tags
 562                                 if accept.has(s) then
 563                                         if tags.has_key(s) then
 564                                                 for t in tags[s] do
 565                                                         dfa.add_tag(dfa_state, t)
 566                                                 end
 567                                         end
 568                                         dfa.accept.add(dfa_state)
 569                                 end
 570                         end
 571
 572                         # From the important values, build a sequence of TSymbols
 573                         var a = alphabet.to_a
 574                         default_comparator.sort(a)
 575                         var tsyms = new Array[TSymbol]
 576                         var last = 0
 577                         for i in a do
 578                                 if last > 0 and last <= i-1 then
 579                                         tsyms.add(new TSymbol(last,i-1))
 580                                 end
 581                                 tsyms.add(new TSymbol(i,i))
 582                                 last = i+1
 583                         end
 584                         if last > 0 then
 585                                 tsyms.add(new TSymbol(last,null))
 586                         end
 587                         #print "Alphabet: {tsyms.join(", ")}"
 588
 589                         var lastst: nullable Transition = null
 590                         for sym in tsyms do
 591                                 var nfa_dest = eclosure(trans(nfa_states, sym.first))
 592                                 if nfa_dest.is_empty then
 593                                         lastst = null
 594                                         continue
 595                                 end
 596                                 #print "{nfa_states} -> {sym} -> {nfa_dest}"
 597                                 var dfa_dest
 598                                 if seen.has(nfa_dest) then
 599                                         #print "* reuse {nfa_dest.inspect}={nfa_dest}"
 600                                         dfa_dest = n2d[nfa_dest]
 601                                 else
 602                                         #print "* new {nfa_dest.inspect}={nfa_dest}"
 603                                         dfa_dest = new State
 604                                         dfa.states.add(dfa_dest)
 605                                         n2d[nfa_dest] = dfa_dest
 606                                         todo.add(nfa_dest)
 607                                         seen.add(nfa_dest)
 608                                 end
 609                                 if lastst != null and lastst.to == dfa_dest then
 610                                         lastst.symbol.last = sym.last
 611                                 else
 612                                         lastst = dfa_state.add_trans(dfa_dest, sym)
 613                                 end
 614                         end
 615                 end
 616                 return dfa
 617         end
 618
 619         # Epsilon-closure on a state of states.
 620         # Used by `to_dfa`.
 621         private fun eclosure(states: Collection[State]): Set[State]
 622         do
 623                 var res = new ArraySet[State]
 624                 res.add_all(states)
 625                 var todo = states.to_a
 626                 while not todo.is_empty do
 627                         var s = todo.pop
 628                         for t in s.outs do
 629                                 if t.symbol != null then continue
 630                                 var to = t.to
 631                                 if res.has(to) then continue
 632                                 res.add(to)
 633                                 todo.add(to)
 634                         end
 635                 end
 636                 return res
 637         end
 638
 639         # Trans on a set of states.
 640         # Used by `to_dfa`.
 641         fun trans(states: Collection[State], symbol: Int): Set[State]
 642         do
 643                 var res = new ArraySet[State]
 644                 for s in states do
 645                         for t in s.outs do
 646                                 var sym = t.symbol
 647                                 if sym == null then continue
 648                                 if sym.first > symbol then continue
 649                                 var l = sym.last
 650                                 if l != null and l < symbol then continue
 651                                 var to = t.to
 652                                 if res.has(to) then continue
 653                                 res.add(to)
 654                         end
 655                 end
 656                 return res
 657         end
 658
 659         # Generate the Nit source code of the lexer.
 660         # `filepath` is the name of the output file.
 661         # `parser` is the name of the parser module (used to import the token classes).
 662         fun gen_to_nit(filepath: String, name: String, parser: nullable String)
 663         do
 664                 var gen = new DFAGenerator(filepath, name, self, parser)
 665                 gen.gen_to_nit
 666         end
 667 end
 668
 669 # Generate the Nit source code of the lexer
 670 private class DFAGenerator
 671         var filepath: String
 672         var name: String
 673         var automaton: Automaton
 674         var parser: nullable String
 675
 676         var out: Writer is noinit
 677
 678         init do
 679                 self.out = new FileWriter.open(filepath)
 680         end
 681
 682         fun add(s: String) do out.write(s)
 683
 684         fun gen_to_nit
 685         do
 686                 var names = new HashMap[State, String]
 687                 var i = 0
 688                 for s in automaton.states do
 689                         names[s] = i.to_s
 690                         i += 1
 691                 end
 692
 693                 add "# Lexer generated by nitcc for the grammar {name}\n"
 694                 add "module {name}_lexer is generated, no_warning \"missing-doc\"\n"
 695                 add("import nitcc_runtime\n")
 696
 697                 var p = parser
 698                 if p != null then add("import {p}\n")
 699
 700                 add("class Lexer_{name}\n")
 701                 add("\tsuper Lexer\n")
 702                 add("\tredef fun start_state do return dfastate_{names[automaton.start]}\n")
 703                 add("end\n")
 704
 705                 for s in automaton.states do
 706                         var n = names[s]
 707                         add("private fun dfastate_{n}: DFAState{n} do return once new DFAState{n}\n")
 708                 end
 709
 710                 add("class MyNToken\n")
 711                 add("\tsuper NToken\n")
 712                 add("end\n")
 713
 714                 for s in automaton.states do
 715                         var  n = names[s]
 716                         add("private class DFAState{n}\n")
 717                         add("\tsuper DFAState\n")
 718                         if automaton.accept.has(s) then
 719                                 var token
 720                                 if automaton.tags.has_key(s) then
 721                                         token = automaton.tags[s].first
 722                                 else
 723                                         token = null
 724                                 end
 725                                 add("\tredef fun is_accept do return true\n")
 726                                 var is_ignored = false
 727                                 if token != null and token.name == "Ignored" then
 728                                         is_ignored = true
 729                                         add("\tredef fun is_ignored do return true\n")
 730                                 end
 731                                 add("\tredef fun make_token(position, source) do\n")
 732                                 if is_ignored then
 733                                         add("\t\treturn null\n")
 734                                 else
 735                                         if token == null then
 736                                                 add("\t\tvar t = new MyNToken\n")
 737                                                 add("\t\tt.text = position.extract(source)\n")
 738                                         else
 739                                                 add("\t\tvar t = new {token.cname}\n")
 740                                                 var ttext = token.text
 741                                                 if ttext == null then
 742                                                         add("\t\tt.text = position.extract(source)\n")
 743                                                 else
 744                                                         add("\t\tt.text = \"{ttext.escape_to_nit}\"\n")
 745                                                 end
 746                                         end
 747                                         add("\t\tt.position = position\n")
 748                                         add("\t\treturn t\n")
 749                                 end
 750                                 add("\tend\n")
 751                         end
 752                         var trans = new ArrayMap[TSymbol, State]
 753                         for t in s.outs do
 754                                 var sym = t.symbol
 755                                 assert sym != null
 756                                 trans[sym] = t.to
 757                         end
 758                         if trans.is_empty then
 759                                 # Do nothing, inherit the trans
 760                         else
 761                                 add("\tredef fun trans(char) do\n")
 762
 763                                 # Collect the sequence of tests in the dispatch sequence
 764                                 # The point here is that for each transition, there is a first and a last
 765                                 # So holes have to be identified
 766                                 var dispatch = new HashMap[Int, nullable State]
 767                                 var haslast: nullable State = null
 768
 769                                 var last = -1
 770                                 for sym, next in trans do
 771                                         assert haslast == null
 772                                         assert sym.first > last
 773                                         if sym.first > last + 1 then
 774                                                 dispatch[sym.first-1] = null
 775                                         end
 776                                         var l = sym.last
 777                                         if l == null then
 778                                                 haslast = next
 779                                         else
 780                                                 dispatch[l] = next
 781                                                 last = l
 782                                         end
 783                                 end
 784
 785                                 if dispatch.is_empty and haslast != null then
 786                                         # Only one transition that accepts everything (quite rare)
 787                                 else
 788                                         # We need to check
 789                                         add("\t\tvar c = char.code_point\n")
 790                                 end
 791
 792                                 # Generate a sequence of `if` for the dispatch
 793                                 if haslast != null and last >= 0 then
 794                                         # Special case: handle up-bound first if not an error
 795                                         add("\t\tif c > {last} then return dfastate_{names[haslast]}\n")
 796                                         # previous become the new last case
 797                                         haslast = dispatch[last]
 798                                         dispatch.keys.remove(last)
 799                                 end
 800                                 for c, next in dispatch do
 801                                         if next == null then
 802                                                 add("\t\tif c <= {c} then return null\n")
 803                                         else
 804                                                 add("\t\tif c <= {c} then return dfastate_{names[next]}\n")
 805                                         end
 806                                 end
 807                                 if haslast == null then
 808                                         add("\t\treturn null\n")
 809                                 else
 810                                         add("\t\treturn dfastate_{names[haslast]}\n")
 811                                 end
 812
 813                                 add("\tend\n")
 814                         end
 815                         add("end\n")
 816                 end
 817
 818                 self.out.close
 819         end
 820 end
 821
 822 redef class Token
 823         # The associated text (if any, ie defined in the parser part)
 824         var text: nullable String is noautoinit, writable
 825 end
 826
 827 # A state in a finite automaton
 828 class State
 829         # Outgoing transitions
 830         var outs = new Array[Transition]
 831
 832         # Ingoing transitions
 833         var ins = new Array[Transition]
 834
 835         # Add a transitions to `to` on `symbol` (null means epsilon)
 836         fun add_trans(to: State, symbol: nullable TSymbol): Transition
 837         do
 838                 var t = new Transition(self, to, symbol)
 839                 outs.add(t)
 840                 to.ins.add(t)
 841                 return t
 842         end
 843
 844         # Get the first state following the transition `i`.
 845         # Null if no transition for `i`.
 846         fun trans(i: Int): nullable State
 847         do
 848                 for t in outs do
 849                         var sym = t.symbol
 850                         assert sym != null
 851                         var f = sym.first
 852                         var l = sym.last
 853                         if i < f then continue
 854                         if l != null and i > l then continue
 855                         return t.to
 856                 end
 857                 return null
 858         end
 859 end
 860
 861 # A range of symbols on a transition
 862 class TSymbol
 863         # The first symbol in the range
 864         var first: Int
 865
 866         # The last symbol if any.
 867         #
 868         # `null` means infinity.
 869         var last: nullable Int
 870
 871         redef fun to_s
 872         do
 873                 var res
 874                 var f = first
 875                 if f <= 32 then
 876                         res = "#{f}"
 877                 else
 878                         res = f.code_point.to_s
 879                 end
 880                 var l = last
 881                 if f == l then return res
 882                 res += " .. "
 883                 if l == null then return res
 884                 if l <= 32 or l >= 127 then return res + "#{l}"
 885                 return res + l.code_point.to_s
 886         end
 887 end
 888
 889 # A transition in a finite automaton
 890 class Transition
 891         # The source state
 892         var from: State
 893         # The destination state
 894         var to: State
 895         # The symbol on the transition (null means epsilon)
 896         var symbol: nullable TSymbol
 897
 898         # Remove the transition from the automaton.
 899         # Detach from `from` and `to`.
 900         fun delete
 901         do
 902                 from.outs.remove(self)
 903                 to.ins.remove(self)
 904         end
 905 end