compiler/nfa_construct.lua

   1 --[[--------------------------------------------------------------------
   2
   3   nfa_construct.lua
   4
   5   Construct NFAs based on primitives of concatenation, alternation,
   6   and repetition/kleene-star.  The construction is as given in
   7   "Programming Language Pragmatics," by Michael L. Scott (see
   8   BIBLIOGRAPHY for more info).
   9
  10   Copyright (c) 2007 Joshua Haberman.  See LICENSE for details.
  11
  12 --------------------------------------------------------------------]]--
  13
  14 require "fa"
  15
  16 module("nfa_construct", package.seeall)
  17
  18 --[[--------------------------------------------------------------------
  19
  20   concat(nfa1, nfa2): Returns a concatenations of two NFAs.
  21   eg. for the NFAs A and B:
  22
  23      A
  24   o ---> *
  25                              A      e      B
  26      B       ...becomes:  o ---> o ---> o ---> *
  27   o ---> *
  28
  29 --------------------------------------------------------------------]]--
  30
  31 function concat(nfa1, nfa2)
  32   nfa1.final:add_transition(fa.e, nfa2.start)
  33   return nfa1:new_graph{start = nfa1.start, final = nfa2.final}
  34 end
  35
  36
  37 --[[--------------------------------------------------------------------
  38
  39    alt([nfa1, nfa2, ...]): Returns an alternation of the given NFAs.
  40    eg. for the NFAs A, B, and C:
  41
  42         A                      e      A      e
  43      o ---> *               ,----> o ---> o -----,
  44                             |                    |
  45         B                   |  e      B      e   v
  46      o ---> *  ...becomes:  o ---> o ---> o ---> *
  47                             |                    ^
  48         C                   |  e      C      e   |
  49      o ---> *               +----> o ---> o -----'
  50
  51 --------------------------------------------------------------------]]--
  52
  53 function alt(nfas)
  54   local new_nfa = nfas[1]:new_graph()
  55
  56   for i=1,#nfas do
  57     new_nfa.start:add_transition(fa.e, nfas[i].start)
  58     nfas[i].final:add_transition(fa.e, new_nfa.final)
  59   end
  60
  61   return new_nfa
  62 end
  63
  64 -- alt2(nfa1, nfa2): a convenience wrapper for alternation of 2 NFAs.
  65 function alt2(nfa1, nfa2)
  66   return alt({nfa1, nfa2})
  67 end
  68
  69
  70 --[[--------------------------------------------------------------------
  71
  72   rep(nfa): Returns the given NFA repeated one or more times.
  73   eg. for the NFA A:
  74
  75
  76      A                      e      A      e
  77   o ---> *  ...becomes:  o ---> o ---> o ---> *
  78                                 ^      |
  79                                 +------+
  80                                    e
  81
  82   Note: This construction isn't strictly necessary: we could always
  83   rewrite A+ as AA*, therefore using the kleene star to construct
  84   all repetition.  However, this makes for less understandable NFAs.
  85   The difference would disappear in the minimization state, but it's
  86   nice to keep the FAs as understandable as possible at every stage.
  87
  88 --------------------------------------------------------------------]]--
  89
  90 function rep(nfa)
  91   local new_nfa = nfa:new_graph()
  92   new_nfa.start:add_transition(fa.e, nfa.start)
  93   nfa.final:add_transition(fa.e, nfa.start)
  94   nfa.final:add_transition(fa.e, new_nfa.final)
  95   return new_nfa
  96 end
  97
  98
  99 --[[--------------------------------------------------------------------
 100
 101   kleene(nfa): Returns the given NFA repeated zero or more times.
 102   eg. for the regular expression A*  :
 103
 104                                       e
 105                             +--------------------+
 106                             |                    |
 107         A                   |  e      A      e   v
 108      o ---> *  ...becomes:  o ---> o ---> o ---> *
 109                                    ^      |
 110                                    +------+
 111                                       e
 112
 113 --------------------------------------------------------------------]]--
 114
 115 function kleene(nfa)
 116   local new_nfa = rep(nfa)
 117   new_nfa.start:add_transition(fa.e, nfa.start)
 118   new_nfa.start:add_transition(fa.e, new_nfa.final)
 119   nfa.final:add_transition(fa.e, nfa.start)
 120   nfa.final:add_transition(fa.e, new_nfa.final)
 121   return new_nfa
 122 end
 123