compiler/nfa_construct.lua

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