1 --[[--------------------------------------------------------------------
3 Gazelle: a system for building fast, reusable parsers
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).
12 Copyright (c) 2007 Joshua Haberman. See LICENSE for details.
14 --------------------------------------------------------------------]]--
18 module("nfa_construct", package
.seeall
)
20 --[[--------------------------------------------------------------------
22 concat(nfa1, nfa2): Returns a concatenations of two NFAs.
23 eg. for the NFAs A and B:
28 B ...becomes: o ---> o ---> o ---> *
31 --------------------------------------------------------------------]]--
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
}
39 --[[--------------------------------------------------------------------
41 alt([nfa1, nfa2, ...]): Returns an alternation of the given NFAs.
42 eg. for the NFAs A, B, and C:
45 o ---> * ,----> o ---> o -----,
48 o ---> * ...becomes: o ---> o ---> o ---> *
51 o ---> * +----> o ---> o -----'
53 --------------------------------------------------------------------]]--
56 local new_nfa
= nfas
[1]:new_graph()
59 new_nfa
.start
:add_transition(fa
.e
, nfas
[i
].start
)
60 nfas
[i
].final
:add_transition(fa
.e
, new_nfa
.final
)
66 -- alt2(nfa1, nfa2): a convenience wrapper for alternation of 2 NFAs.
67 function alt2(nfa1
, nfa2
)
68 return alt({nfa1
, nfa2
})
72 --[[--------------------------------------------------------------------
74 rep(nfa): Returns the given NFA repeated one or more times.
79 o ---> * ...becomes: o ---> o ---> o ---> *
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.
90 --------------------------------------------------------------------]]--
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
)
101 --[[--------------------------------------------------------------------
103 kleene(nfa): Returns the given NFA repeated zero or more times.
104 eg. for the regular expression A* :
107 +--------------------+
110 o ---> * ...becomes: o ---> o ---> o ---> *
115 --------------------------------------------------------------------]]--
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
)