Here is Jeff Ullman's contribution on a way to build your ENFA from the tree that you get from the parser. An ENFA is a graph, and apparently in 106 you only learn to use Eric Roberts' graph package. I wish they had taught you the real implementation, if not there, then in CS109, but the following will do for the particular graphs that are ENFA's.

First, we should use a recursive algorithm to generate the ENFA from the tree. Suppose we are at a concatenation node. You call yourself on the left child and get back a (pointer to) an ENFA. You call yourself on the right child and get another ENFA. You then splice them together as in Fig. 3.16(b) of the reader, and return what you get. You should figure out the similar recursions for the *, union, ? and super-+ operators. And of course you need a basis that doesn't make recursive calls when you reach a leaf node.

How do you represent an ENFA? There are two arrays; make them as long as the maximum size of RE you are willing to handle. Warning: I'm sure the lecturer staff would cringe at the old-fashioned style of programming I'm teaching you, but it works.

One array has elements that represent states. Each state is a struct with three components. Two of those components are states, i.e., indexes into the array, or pointers to elements in the array. The third is used to represent an operand of the RE: either a single character, or character class coded as the parser does. (Note: I strongly advise you to treat the dot and character classes as single symbols at this stage, rather than splitting them into the union of many characters.) You also ned here a special code to say ``there are only epsilon-arcs out of this state.''

It may not be obvious, but if you study the construction in the reader, you see that each state has at most two arcs out. Moreover, if the arcs are not labeled epsilon, then there is only one arc out. Thus, it is easy to represent the transitions out of a state in this structure.

You also need a pointer or integer that indicates the first place in your array that is not yet used as a state. That allows you to get a new state when you need it; don't forget to bump the cursor up by one when you get a new state, and you'd better check for overflow.

The other array represents ENFA's themselves. Its elements are structs with two components: pointers (or better--- integer indexes) to the initial state and the one accepting state of the ENFA. Note that these two states are all you need to know to carry out the constructions in Fig. 3.16 or their analogs for the ? and super-+ operators. Again, you need a cursor to find the first unallocated element; you can reuse them during combination.

Another suggestion: Recall from the class discussion of the ENFA-NFA construction that it is sufficient to compute transitions from only the important states, which are the start state and those states that have a non-epsilon transition in. It might be useful to mark the states that have a non-epsilon transition in, by introducing another field into your struct for states.