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

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

compute an SLR NFA for the ruleset with states for each SLR "item"
   and transitions, eg:
       X > .AB
     on A maps to X > A.B
     on epsilon maps to A > .ZC
            and A > .WK
   an item is a pair (rulenumber, bodyposition)
   where body position 0 is interpreted to point before the
   beginning of the body.

   SLR = "simple LR" in Aho+Ullman terminology

Definition at line 373 of file kjParseBuild.py.

00373                         :
        '''compute an SLR NFA for the ruleset with states for each SLR "item"
           and transitions, eg:
               X > .AB
             on A maps to X > A.B
             on epsilon maps to A > .ZC
                            and A > .WK
           an item is a pair (rulenumber, bodyposition)
           where body position 0 is interpreted to point before the
           beginning of the body.

           SLR = "simple LR" in Aho+Ullman terminology
        '''
        NFA = CFSMachine(self.StartNonterm)
        Nrules = len(self.Rules)
        itemStateMap = {}
        for Ruleindex in range(0,Nrules):
            Rule = self.Rules[Ruleindex]
            # make an item for each "dot" position in the body
            for DotPos in range(0, len(Rule.Body) + 1):
                item = (Ruleindex, DotPos)
                itemState = NFA.NewState(TRANSFLAG, [item])
                itemStateMap[item] = itemState
            #endfor DotPos
        #endfor Ruleindex

        # now that the states are initialized
        # compute transitions except for the last item of a rule
        # (which has none)
        for Ruleindex in range(0,Nrules):
            Rule = self.Rules[Ruleindex]
            for DotPos in range(0, len(Rule.Body)):
                item = (Ruleindex, DotPos)
                CurrentToken = Rule.Body[DotPos]
                ThisState = itemStateMap[item]
                NextState = itemStateMap[ (Ruleindex, DotPos + 1) ]
                NFA.SetMap( ThisState, CurrentToken, NextState  )
                # if the current token is a nonterminal
                # ad epsilon transitions to first item for any
                # rule that derives this nonterminal
                (CTtype, CTname) = CurrentToken
                if CTtype == NONTERMFLAG:
                    for Rule2index in range(0,Nrules):
                        Rule2 = self.Rules[Rule2index]
                        Head = Rule2.Nonterm
                        if Head == CurrentToken:
                            NextState = itemStateMap[( Rule2index, 0 )]
                            NFA.SetMap( ThisState, NULLTOKEN, NextState )
                    #endfor Rule2index
                #endif CTtype == NONTERMFLAG
            #endfor DotPos
        #endfor Ruleindex

        # must handle the initial state properly here!
        # Make a dummy state with e-transitions to all first items
        # for rules that derive the initial nonterminal
        ThisState = NFA.initial_state
        GoodStartingPlace = None
        for Ruleindex in range(0,Nrules):
            Rule = self.Rules[Ruleindex]
            Head = Rule.Nonterm
            if Head == self.StartNonterm:
                GoodStartingPlace= (Ruleindex, 0)
                NextState = itemStateMap[ GoodStartingPlace ]
                NFA.SetMap( ThisState, NULLTOKEN, NextState )
        # fix the NFA.States entry
        if GoodStartingPlace == None:
            raise NotSLRError, "No derivation for root nonterminal."
        NFA.States[ NFA.initial_state ] = \
             [ 'transient', GoodStartingPlace ]

        self.SLRNFA = NFA
    #enddef compSLRNFA

    def ItemDump(self, item):


Generated by  Doxygen 1.6.0   Back to index