Logo Search packages:      
Sourcecode: gadfly version File versions  Download package

def gadfly::kjParseBuild::Ruleset::compFirst (   self  ) 

method to compute prefixes and First sets for nonterminals

Definition at line 164 of file kjParseBuild.py.

00164                        :
        ''' method to compute prefixes and First sets for nonterminals
        '''
        # uses the special null production token NULLTOKEN
        # snarfed directly from Aho+Ullman (terminals glossed)
        First = kjSet.NewDG([])
        # repeat the while loop until no change is made to First
        done = 0
        while not done:
            # assume we're done until a change is made to First
            done = 1

            # iterate through all rules looking for a new arc to add
            # indicating Terminal > possible first token derivation
            #
            for R in self.Rules:
                GoalNonterm = R.Nonterm
                Bodylength = len(R.Body)
                # look through the body of the rule up to the token with
                # no epsilon production (yet seen)
                Bodyindex = 0
                Processindex = 1
                while Processindex:
                    # unless otherwise indicated below, don't go to next token
                    Processindex = 0

                    # if index is past end of body then record
                    # an epsilon production for this nonterminal
                    if Bodyindex >= Bodylength:
                        if not kjSet.HasArc(First, GoalNonterm, NULLTOKEN ):
                            kjSet.AddArc( First, GoalNonterm, NULLTOKEN )
                            done = 0 # change made to First
                    else:
                        # otherwise try to add firsts of this token
                        # to firsts of the Head of the rule.
                        Token = R.Body[Bodyindex]
                        (type, name) = Token
                        if type in (KEYFLAG,TERMFLAG):
                            # try to add this terminal to First for GoalNonterm
                            if not kjSet.HasArc(First, GoalNonterm, Token):
                                kjSet.AddArc( First, GoalNonterm, Token)
                                done = 0
                        elif type == NONTERMFLAG:
                            # try to add each First entry for nonterminal
                            # to First entry for GoalNonterm
                            for FToken in kjSet.Neighbors( First, Token ):
                                if not kjSet.HasArc(First, GoalNonterm, FToken):
                                    kjSet.AddArc( First, GoalNonterm, FToken)
                                    done = 0
                            # does this nonterminal have a known e production?
                            if kjSet.HasArc( First, Token, NULLTOKEN ):
                                # if so, process next token in rule
                                Processindex = 1
                        else:
                            raise TokenError, "unknown token type in rule body"
                    #endif
                    Bodyindex = Bodyindex + 1
                #endwhile Processindex
            #endfor R in self.Rules
        #endwhile not done
        self.First = First

    def compFollow(self):


Generated by  Doxygen 1.6.0   Back to index