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

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

this function completes the computation of an SLR DFA
   by adding reduction states for each DFA state S containing
   item   H > B.
   which reduces rule H > B
   for each token T in Follow of H.
   if S already has a transition for T then there is a conflict!

   assumes DFA and SLRNFA and Follow have been computed.

Definition at line 510 of file kjParseBuild.py.

00510                        :
        '''this function completes the computation of an SLR DFA
           by adding reduction states for each DFA state S containing
           item   H > B.
           which reduces rule H > B
           for each token T in Follow of H.
           if S already has a transition for T then there is a conflict!

           assumes DFA and SLRNFA and Follow have been computed.
        '''
        DFA = self.DFA
        NFA = self.SLRNFA
        # look through the states (except 0=success) of the DFA
        # initially don't add any new states, just record
        # actions to be done
        #   uses convention that 0 is successful final state

        # ToDo is a dictionary which maps
        #     (State, Token) to a item to reduce
        ToDo = {}
        Error = None
        for State in range(1, len(DFA.States) ):
            # look for a final item for a rule in this state
            fromNFAindices = kjSet.get_elts(DFA.States[State][1])
            for NFAindex in fromNFAindices:
                item = NFA.States[NFAindex][1]
                # if the item is final remember to do the reductions...
                if self.SLRItemIsFinal(item):
                    (ruleindex, position) = item
                    Rule = self.Rules[ruleindex]
                    Head = Rule.Nonterm
                    Following = kjSet.Neighbors( self.Follow, Head )
                    for Token in Following:
                        key = (State, Token)
                        if not ToDo.has_key(key):
                            ToDo[ key ] = item
                        else:
                            # it might be okay if the items are identical?
                            item2 = ToDo[key]
                            if item != item2:
                                print "reduce/reduce conflict on ",key
                                self.ItemDump(item)
                                self.ItemDump(item2)
                            Error = " apparent reduce/reduce conflict"
                        #endif
                    #endfor
                #endif
            #endfor NFAindex
        #endfor State

        # for each (State,Token) pair which indicates a reduction
        # record the reduction UNLESS the map is already set for the pair
        for key in ToDo.keys():
            (State,Token) = key
            item = ToDo[key]
            (rulenum, dotpos) = item
            ExistingMap = DFA.map( State, Token )
            if ExistingMap[0] == NOMATCHFLAG:
                DFA.SetReduction( State, Token, rulenum )
            else:
                print "apparent shift/reduce conflict"
                print "reduction: ", key, ": "
                self.ItemDump(item)
                print "existing map ", ExistingMap
                Error = " apparent shift/reduce conflict"
        #endfor
        if Error and ABORTONERROR:
            raise NotSLRError, Error
    #enddef SLRfixDFA()

    def DoSLRGeneration(self):


Generated by  Doxygen 1.6.0   Back to index