private Subre parse ( int stopper , int type , State initState , State finalState ) throws RegexException { State left ; /* scaffolding for branch */ State right ; Subre branches ; /* top level */ Subre branch ; /* current branch */ Subre t ; /* temporary */ int firstbranch ; /* is this the first branch? */ assert stopper == ' ' || stopper == EOS ; branches = new Subre ( ' ' , Subre . LONGER , initState , finalState ) ; branch = branches ; firstbranch = 1 ; do { /* a branch */ if ( 0 == firstbranch ) { /* need a place to hang it */ branch . right = new Subre ( ' ' , Subre . LONGER , initState , finalState ) ; branch = branch . right ; } firstbranch = 0 ; left = nfa . newstate ( ) ; right = nfa . newstate ( ) ; nfa . emptyarc ( initState , left ) ; nfa . emptyarc ( right , finalState ) ; branch . left = parsebranch ( stopper , type , left , right , false ) ; branch . flags |= up ( branch . flags | branch . left . flags ) ; if ( ( branch . flags & ~ branches . flags ) != 0 ) /* new flags */ { for ( t = branches ; t != branch ; t = t . right ) { t . flags |= branch . flags ; } } } while ( eat ( ' ' ) ) ; assert see ( stopper ) || see ( EOS ) ; if ( ! see ( stopper ) ) { assert stopper == ' ' && see ( EOS ) ; //ERR(REG_EPAREN); throw new RegexException ( "Unbalanced parentheses." ) ; } /* optimize out simple cases */ if ( branch == branches ) { /* only one branch */ assert branch . right == null ; t = branch . left ; branch . left = null ; branches = t ; } else if ( ! messy ( branches . flags ) ) { /* no interesting innards */ branches . left = null ; branches . right = null ; branches . op = ' ' ; } return branches ; }
parse - parse an RE This is actually just the top level which parses a bunch of branches tied together with | . They appear in the tree as the left children of a chain of | subres .