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, prioritized)
  56   local new_nfa = nfas[1]:new_graph()
  57   local priority_class = {}
  58
  59   for i=1,#nfas do
  60     local properties
  61     if prioritized then
  62       properties = {
  63         priority_class = priority_class,
  64         priority = #nfas - i + 1  -- priorities count down from #nfas to 0
  65       }
  66     end
  67
  68     new_nfa.start:add_transition(fa.e, nfas[i].start, properties)
  69     nfas[i].final:add_transition(fa.e, new_nfa.final)
  70   end
  71
  72   return new_nfa
  73 end
  74
  75 -- alt2(nfa1, nfa2): a convenience wrapper for alternation of 2 NFAs.
  76 function alt2(nfa1, nfa2, prioritized)
  77   return alt({nfa1, nfa2}, prioritized)
  78 end
  79
  80 function get_repeating_properties(favor_repeating)
  81   local repeat_properties
  82   local finish_properties
  83
  84   if favor_repeating ~= nil then
  85     local priority_class = {}  -- just a unique value
  86     repeat_properties = {priority_class=priority_class}
  87     finish_properties = {priority_class=priority_class}
  88     if favor_repeating then
  89       repeat_properties.priority = 2
  90       finish_properties.priority = 1
  91     else
  92       repeat_properties.priority = 1
  93       finish_properties.priority = 2
  94     end
  95   end
  96
  97   return repeat_properties, finish_properties
  98 end
  99
 100 --[[--------------------------------------------------------------------
 101
 102   rep(nfa): Returns the given NFA repeated one or more times.
 103   eg. for the NFA A:
 104
 105
 106      A                      e      A      e
 107   o ---> *  ...becomes:  o ---> o ---> o ---> *
 108                                 ^      |
 109                                 +------+
 110                                    e
 111
 112   Note: This construction isn't strictly necessary: we could always
 113   rewrite A+ as AA*, therefore using the kleene star to construct
 114   all repetition.  However, this makes for less understandable NFAs.
 115   The difference would disappear in the minimization state, but it's
 116   nice to keep the FAs as understandable as possible at every stage.
 117
 118 --------------------------------------------------------------------]]--
 119
 120 function rep(nfa, favor_repeat)
 121   local new_nfa = nfa:new_graph()
 122   local repeat_properties, finish_properties = get_repeating_properties(favor_repeating)
 123   new_nfa.start:add_transition(fa.e, nfa.start)
 124   nfa.final:add_transition(fa.e, nfa.start, repeat_properties)
 125   nfa.final:add_transition(fa.e, new_nfa.final, finish_properties)
 126   return new_nfa
 127 end
 128
 129
 130 --[[--------------------------------------------------------------------
 131
 132   kleene(nfa): Returns the given NFA repeated zero or more times.
 133   eg. for the regular expression A*  :
 134
 135                                       e
 136                             +--------------------+
 137                             |                    |
 138         A                   |  e      A      e   v
 139      o ---> *  ...becomes:  o ---> o ---> o ---> *
 140                                    ^      |
 141                                    +------+
 142                                       e
 143
 144 --------------------------------------------------------------------]]--
 145
 146 function kleene(nfa, favor_repeat)
 147   local new_nfa = rep(nfa)
 148   local repeat_properties, finish_properties = get_repeating_properties(favor_repeat)
 149   new_nfa.start:add_transition(fa.e, nfa.start)
 150   new_nfa.start:add_transition(fa.e, new_nfa.final, finish_properties)
 151   nfa.final:add_transition(fa.e, nfa.start, repeat_properties)
 152   nfa.final:add_transition(fa.e, new_nfa.final, finish_properties)
 153   return new_nfa
 154 end
 155
 156 -- vim:et:sts=2:sw=2