Lichen

pyparser/pylexer.py

662:b8733c35d308
2017-03-06 Paul Boddie Incorporated __WITHIN within __HASATTR.
     1 # Used by genpytokenize.py to generate the parser in pytokenize.py     2 from pyparser.automata import DFA, DEFAULT     3      4 class EMPTY: pass     5      6 def newArcPair (states, transitionLabel):     7     s1Index = len(states)     8     s2Index = s1Index + 1     9     states.append([(transitionLabel, s2Index)])    10     states.append([])    11     return s1Index, s2Index    12     13 # ______________________________________________________________________    14     15 def chain (states, *stateIndexPairs):    16     if len(stateIndexPairs) > 1:    17         start, lastFinish = stateIndexPairs[0]    18         for nStart, nFinish in stateIndexPairs[1:]:    19             states[lastFinish].append((EMPTY, nStart))    20             lastFinish = nFinish    21         return start, nFinish    22     else:    23         return stateIndexPairs[0]    24     25     26 # ______________________________________________________________________    27     28 def chainStr (states, str):    29     return chain(states, *map(lambda x : newArcPair(states, x), str))    30     31 # ______________________________________________________________________    32     33 def notChainStr (states, str):    34     """XXX I'm not sure this is how it should be done, but I'm going to    35     try it anyway.  Note that for this case, I require only single character    36     arcs, since I would have to basically invert all accepting states and    37     non-accepting states of any sub-NFA's.    38     """    39     assert len(str) > 0    40     arcs = map(lambda x : newArcPair(states, x), str)    41     finish = len(states)    42     states.append([])    43     start, lastFinish = arcs[0]    44     states[start].append((EMPTY, finish))    45     for crntStart, crntFinish in arcs[1:]:    46         states[lastFinish].append((EMPTY, crntStart))    47         states[crntStart].append((EMPTY, finish))    48     return start, finish    49     50 # ______________________________________________________________________    51     52 def group (states, *stateIndexPairs):    53     if len(stateIndexPairs) > 1:    54         start = len(states)    55         finish = start + 1    56         startList = []    57         states.append(startList)    58         states.append([])    59         for eStart, eFinish in stateIndexPairs:    60             startList.append((EMPTY, eStart))    61             states[eFinish].append((EMPTY, finish))    62         return start, finish    63     else:    64         return stateIndexPairs[0]    65     66 # ______________________________________________________________________    67     68 def groupStr (states, str):    69     return group(states, *map(lambda x : newArcPair(states, x), str))    70     71 # ______________________________________________________________________    72     73 def notGroup (states, *stateIndexPairs):    74     """Like group, but will add a DEFAULT transition to a new end state,    75     causing anything in the group to not match by going to a dead state.    76     XXX I think this is right...    77     """    78     start, dead = group(states, *stateIndexPairs)    79     finish = len(states)    80     states.append([])    81     states[start].append((DEFAULT, finish))    82     return start, finish    83     84 # ______________________________________________________________________    85     86 def notGroupStr (states, str):    87     return notGroup(states, *map(lambda x : newArcPair(states, x), str))    88 # ______________________________________________________________________    89     90 def any (states, *stateIndexPairs):    91     start, finish = group(states, *stateIndexPairs)    92     states[finish].append((EMPTY, start))    93     return start, start    94     95 # ______________________________________________________________________    96     97 def maybe (states, *stateIndexPairs):    98     start, finish = group(states, *stateIndexPairs)    99     states[start].append((EMPTY, finish))   100     return start, finish   101    102 # ______________________________________________________________________   103    104 def atleastonce (states, *stateIndexPairs):   105     start, finish = group(states, *stateIndexPairs)   106     states[finish].append((EMPTY, start))   107     return start, finish   108    109 # ______________________________________________________________________   110    111 def closure (states, start, result = 0L):   112     if None == result:   113         result = 0L   114     if 0 == (result & (1L << start)):   115         result |= (1L << start)   116         for label, arrow in states[start]:   117             if label == EMPTY:   118                 result |= closure(states, arrow, result)   119     return result   120    121 # ______________________________________________________________________   122    123 def nfaToDfa (states, start, finish):   124     tempStates = []   125     startClosure = closure(states, start)   126     crntTempState = [startClosure, [], 0 != (startClosure & (1L << finish))]   127     tempStates.append(crntTempState)   128     index = 0   129     while index < len(tempStates):   130         crntTempState = tempStates[index]   131         crntClosure, crntArcs, crntAccept = crntTempState   132         for index2 in range(0, len(states)):   133             if 0 != (crntClosure & (1L << index2)):   134                 for label, nfaArrow in states[index2]:   135                     if label == EMPTY:   136                         continue   137                     foundTempArc = False   138                     for tempArc in crntArcs:   139                         if tempArc[0] == label:   140                             foundTempArc = True   141                             break   142                     if not foundTempArc:   143                         tempArc = [label, -1, 0L]   144                         crntArcs.append(tempArc)   145                     tempArc[2] = closure(states, nfaArrow, tempArc[2])   146         for arcIndex in range(0, len(crntArcs)):   147             label, arrow, targetStates = crntArcs[arcIndex]   148             targetFound = False   149             arrow = 0   150             for destTempState in tempStates:   151                 if destTempState[0] == targetStates:   152                     targetFound = True   153                     break   154                 arrow += 1   155             if not targetFound:   156                 assert arrow == len(tempStates)   157                 newState = [targetStates, [], 0 != (targetStates &   158                                                     (1L << finish))]   159                 tempStates.append(newState)   160             crntArcs[arcIndex][1] = arrow   161         index += 1   162     tempStates = simplifyTempDfa(tempStates)   163     states = finalizeTempDfa(tempStates)   164     return states   165    166 # ______________________________________________________________________   167    168 def sameState (s1, s2):   169     """sameState(s1, s2)   170     Note:   171     state := [ nfaclosure : Long, [ arc ], accept : Boolean ]   172     arc := [ label, arrow : Int, nfaClosure : Long ]   173     """   174     if (len(s1[1]) != len(s2[1])) or (s1[2] != s2[2]):   175         return False   176     for arcIndex in range(0, len(s1[1])):   177         arc1 = s1[1][arcIndex]   178         arc2 = s2[1][arcIndex]   179         if arc1[:-1] != arc2[:-1]:   180             return False   181     return True   182    183 # ______________________________________________________________________   184    185 def simplifyTempDfa (tempStates):   186     """simplifyTempDfa (tempStates)   187     """   188     changes = True   189     deletedStates = []   190     while changes:   191         changes = False   192         for i in range(1, len(tempStates)):   193             if i in deletedStates:   194                 continue   195             for j in range(0, i):   196                 if j in deletedStates:   197                     continue   198                 if sameState(tempStates[i], tempStates[j]):   199                     deletedStates.append(i)   200                     for k in range(0, len(tempStates)):   201                         if k in deletedStates:   202                             continue   203                         for arc in tempStates[k][1]:   204                             if arc[1] == i:   205                                 arc[1] = j   206                     changes = True   207                     break   208     for stateIndex in deletedStates:   209         tempStates[stateIndex] = None   210     return tempStates   211 # ______________________________________________________________________   212    213 def finalizeTempDfa (tempStates):   214     """finalizeTempDfa (tempStates)   215        216     Input domain:   217     tempState := [ nfaClosure : Long, [ tempArc ], accept : Boolean ]   218     tempArc := [ label, arrow, nfaClosure ]   219    220     Output domain:   221     state := [ arcMap, accept : Boolean ]   222     """   223     states = []   224     accepts = []   225     stateMap = {}   226     tempIndex = 0   227     for tempIndex in range(0, len(tempStates)):   228         tempState = tempStates[tempIndex]   229         if None != tempState:   230             stateMap[tempIndex] = len(states)   231             states.append({})   232             accepts.append(tempState[2])   233     for tempIndex in stateMap.keys():   234         stateBitset, tempArcs, accepting = tempStates[tempIndex]   235         newIndex = stateMap[tempIndex]   236         arcMap = states[newIndex]   237         for tempArc in tempArcs:   238             arcMap[tempArc[0]] = stateMap[tempArc[1]]   239     return states, accepts   240