Home | History | Annotate | Download | only in pgen2
      1 # Copyright 2004-2005 Elemental Security, Inc. All Rights Reserved.
      2 # Licensed to PSF under a Contributor Agreement.
      3 
      4 # Pgen imports
      5 from . import grammar, token, tokenize
      6 
      7 class PgenGrammar(grammar.Grammar):
      8     pass
      9 
     10 class ParserGenerator(object):
     11 
     12     def __init__(self, filename, stream=None):
     13         close_stream = None
     14         if stream is None:
     15             stream = open(filename)
     16             close_stream = stream.close
     17         self.filename = filename
     18         self.stream = stream
     19         self.generator = tokenize.generate_tokens(stream.readline)
     20         self.gettoken() # Initialize lookahead
     21         self.dfas, self.startsymbol = self.parse()
     22         if close_stream is not None:
     23             close_stream()
     24         self.first = {} # map from symbol name to set of tokens
     25         self.addfirstsets()
     26 
     27     def make_grammar(self):
     28         c = PgenGrammar()
     29         names = self.dfas.keys()
     30         names.sort()
     31         names.remove(self.startsymbol)
     32         names.insert(0, self.startsymbol)
     33         for name in names:
     34             i = 256 + len(c.symbol2number)
     35             c.symbol2number[name] = i
     36             c.number2symbol[i] = name
     37         for name in names:
     38             dfa = self.dfas[name]
     39             states = []
     40             for state in dfa:
     41                 arcs = []
     42                 for label, next in state.arcs.iteritems():
     43                     arcs.append((self.make_label(c, label), dfa.index(next)))
     44                 if state.isfinal:
     45                     arcs.append((0, dfa.index(state)))
     46                 states.append(arcs)
     47             c.states.append(states)
     48             c.dfas[c.symbol2number[name]] = (states, self.make_first(c, name))
     49         c.start = c.symbol2number[self.startsymbol]
     50         return c
     51 
     52     def make_first(self, c, name):
     53         rawfirst = self.first[name]
     54         first = {}
     55         for label in rawfirst:
     56             ilabel = self.make_label(c, label)
     57             ##assert ilabel not in first # XXX failed on <> ... !=
     58             first[ilabel] = 1
     59         return first
     60 
     61     def make_label(self, c, label):
     62         # XXX Maybe this should be a method on a subclass of converter?
     63         ilabel = len(c.labels)
     64         if label[0].isalpha():
     65             # Either a symbol name or a named token
     66             if label in c.symbol2number:
     67                 # A symbol name (a non-terminal)
     68                 if label in c.symbol2label:
     69                     return c.symbol2label[label]
     70                 else:
     71                     c.labels.append((c.symbol2number[label], None))
     72                     c.symbol2label[label] = ilabel
     73                     return ilabel
     74             else:
     75                 # A named token (NAME, NUMBER, STRING)
     76                 itoken = getattr(token, label, None)
     77                 assert isinstance(itoken, int), label
     78                 assert itoken in token.tok_name, label
     79                 if itoken in c.tokens:
     80                     return c.tokens[itoken]
     81                 else:
     82                     c.labels.append((itoken, None))
     83                     c.tokens[itoken] = ilabel
     84                     return ilabel
     85         else:
     86             # Either a keyword or an operator
     87             assert label[0] in ('"', "'"), label
     88             value = eval(label)
     89             if value[0].isalpha():
     90                 # A keyword
     91                 if value in c.keywords:
     92                     return c.keywords[value]
     93                 else:
     94                     c.labels.append((token.NAME, value))
     95                     c.keywords[value] = ilabel
     96                     return ilabel
     97             else:
     98                 # An operator (any non-numeric token)
     99                 itoken = grammar.opmap[value] # Fails if unknown token
    100                 if itoken in c.tokens:
    101                     return c.tokens[itoken]
    102                 else:
    103                     c.labels.append((itoken, None))
    104                     c.tokens[itoken] = ilabel
    105                     return ilabel
    106 
    107     def addfirstsets(self):
    108         names = self.dfas.keys()
    109         names.sort()
    110         for name in names:
    111             if name not in self.first:
    112                 self.calcfirst(name)
    113             #print name, self.first[name].keys()
    114 
    115     def calcfirst(self, name):
    116         dfa = self.dfas[name]
    117         self.first[name] = None # dummy to detect left recursion
    118         state = dfa[0]
    119         totalset = {}
    120         overlapcheck = {}
    121         for label, next in state.arcs.iteritems():
    122             if label in self.dfas:
    123                 if label in self.first:
    124                     fset = self.first[label]
    125                     if fset is None:
    126                         raise ValueError("recursion for rule %r" % name)
    127                 else:
    128                     self.calcfirst(label)
    129                     fset = self.first[label]
    130                 totalset.update(fset)
    131                 overlapcheck[label] = fset
    132             else:
    133                 totalset[label] = 1
    134                 overlapcheck[label] = {label: 1}
    135         inverse = {}
    136         for label, itsfirst in overlapcheck.iteritems():
    137             for symbol in itsfirst:
    138                 if symbol in inverse:
    139                     raise ValueError("rule %s is ambiguous; %s is in the"
    140                                      " first sets of %s as well as %s" %
    141                                      (name, symbol, label, inverse[symbol]))
    142                 inverse[symbol] = label
    143         self.first[name] = totalset
    144 
    145     def parse(self):
    146         dfas = {}
    147         startsymbol = None
    148         # MSTART: (NEWLINE | RULE)* ENDMARKER
    149         while self.type != token.ENDMARKER:
    150             while self.type == token.NEWLINE:
    151                 self.gettoken()
    152             # RULE: NAME ':' RHS NEWLINE
    153             name = self.expect(token.NAME)
    154             self.expect(token.OP, ":")
    155             a, z = self.parse_rhs()
    156             self.expect(token.NEWLINE)
    157             #self.dump_nfa(name, a, z)
    158             dfa = self.make_dfa(a, z)
    159             #self.dump_dfa(name, dfa)
    160             oldlen = len(dfa)
    161             self.simplify_dfa(dfa)
    162             newlen = len(dfa)
    163             dfas[name] = dfa
    164             #print name, oldlen, newlen
    165             if startsymbol is None:
    166                 startsymbol = name
    167         return dfas, startsymbol
    168 
    169     def make_dfa(self, start, finish):
    170         # To turn an NFA into a DFA, we define the states of the DFA
    171         # to correspond to *sets* of states of the NFA.  Then do some
    172         # state reduction.  Let's represent sets as dicts with 1 for
    173         # values.
    174         assert isinstance(start, NFAState)
    175         assert isinstance(finish, NFAState)
    176         def closure(state):
    177             base = {}
    178             addclosure(state, base)
    179             return base
    180         def addclosure(state, base):
    181             assert isinstance(state, NFAState)
    182             if state in base:
    183                 return
    184             base[state] = 1
    185             for label, next in state.arcs:
    186                 if label is None:
    187                     addclosure(next, base)
    188         states = [DFAState(closure(start), finish)]
    189         for state in states: # NB states grows while we're iterating
    190             arcs = {}
    191             for nfastate in state.nfaset:
    192                 for label, next in nfastate.arcs:
    193                     if label is not None:
    194                         addclosure(next, arcs.setdefault(label, {}))
    195             for label, nfaset in arcs.iteritems():
    196                 for st in states:
    197                     if st.nfaset == nfaset:
    198                         break
    199                 else:
    200                     st = DFAState(nfaset, finish)
    201                     states.append(st)
    202                 state.addarc(st, label)
    203         return states # List of DFAState instances; first one is start
    204 
    205     def dump_nfa(self, name, start, finish):
    206         print "Dump of NFA for", name
    207         todo = [start]
    208         for i, state in enumerate(todo):
    209             print "  State", i, state is finish and "(final)" or ""
    210             for label, next in state.arcs:
    211                 if next in todo:
    212                     j = todo.index(next)
    213                 else:
    214                     j = len(todo)
    215                     todo.append(next)
    216                 if label is None:
    217                     print "    -> %d" % j
    218                 else:
    219                     print "    %s -> %d" % (label, j)
    220 
    221     def dump_dfa(self, name, dfa):
    222         print "Dump of DFA for", name
    223         for i, state in enumerate(dfa):
    224             print "  State", i, state.isfinal and "(final)" or ""
    225             for label, next in state.arcs.iteritems():
    226                 print "    %s -> %d" % (label, dfa.index(next))
    227 
    228     def simplify_dfa(self, dfa):
    229         # This is not theoretically optimal, but works well enough.
    230         # Algorithm: repeatedly look for two states that have the same
    231         # set of arcs (same labels pointing to the same nodes) and
    232         # unify them, until things stop changing.
    233 
    234         # dfa is a list of DFAState instances
    235         changes = True
    236         while changes:
    237             changes = False
    238             for i, state_i in enumerate(dfa):
    239                 for j in range(i+1, len(dfa)):
    240                     state_j = dfa[j]
    241                     if state_i == state_j:
    242                         #print "  unify", i, j
    243                         del dfa[j]
    244                         for state in dfa:
    245                             state.unifystate(state_j, state_i)
    246                         changes = True
    247                         break
    248 
    249     def parse_rhs(self):
    250         # RHS: ALT ('|' ALT)*
    251         a, z = self.parse_alt()
    252         if self.value != "|":
    253             return a, z
    254         else:
    255             aa = NFAState()
    256             zz = NFAState()
    257             aa.addarc(a)
    258             z.addarc(zz)
    259             while self.value == "|":
    260                 self.gettoken()
    261                 a, z = self.parse_alt()
    262                 aa.addarc(a)
    263                 z.addarc(zz)
    264             return aa, zz
    265 
    266     def parse_alt(self):
    267         # ALT: ITEM+
    268         a, b = self.parse_item()
    269         while (self.value in ("(", "[") or
    270                self.type in (token.NAME, token.STRING)):
    271             c, d = self.parse_item()
    272             b.addarc(c)
    273             b = d
    274         return a, b
    275 
    276     def parse_item(self):
    277         # ITEM: '[' RHS ']' | ATOM ['+' | '*']
    278         if self.value == "[":
    279             self.gettoken()
    280             a, z = self.parse_rhs()
    281             self.expect(token.OP, "]")
    282             a.addarc(z)
    283             return a, z
    284         else:
    285             a, z = self.parse_atom()
    286             value = self.value
    287             if value not in ("+", "*"):
    288                 return a, z
    289             self.gettoken()
    290             z.addarc(a)
    291             if value == "+":
    292                 return a, z
    293             else:
    294                 return a, a
    295 
    296     def parse_atom(self):
    297         # ATOM: '(' RHS ')' | NAME | STRING
    298         if self.value == "(":
    299             self.gettoken()
    300             a, z = self.parse_rhs()
    301             self.expect(token.OP, ")")
    302             return a, z
    303         elif self.type in (token.NAME, token.STRING):
    304             a = NFAState()
    305             z = NFAState()
    306             a.addarc(z, self.value)
    307             self.gettoken()
    308             return a, z
    309         else:
    310             self.raise_error("expected (...) or NAME or STRING, got %s/%s",
    311                              self.type, self.value)
    312 
    313     def expect(self, type, value=None):
    314         if self.type != type or (value is not None and self.value != value):
    315             self.raise_error("expected %s/%s, got %s/%s",
    316                              type, value, self.type, self.value)
    317         value = self.value
    318         self.gettoken()
    319         return value
    320 
    321     def gettoken(self):
    322         tup = self.generator.next()
    323         while tup[0] in (tokenize.COMMENT, tokenize.NL):
    324             tup = self.generator.next()
    325         self.type, self.value, self.begin, self.end, self.line = tup
    326         #print token.tok_name[self.type], repr(self.value)
    327 
    328     def raise_error(self, msg, *args):
    329         if args:
    330             try:
    331                 msg = msg % args
    332             except:
    333                 msg = " ".join([msg] + map(str, args))
    334         raise SyntaxError(msg, (self.filename, self.end[0],
    335                                 self.end[1], self.line))
    336 
    337 class NFAState(object):
    338 
    339     def __init__(self):
    340         self.arcs = [] # list of (label, NFAState) pairs
    341 
    342     def addarc(self, next, label=None):
    343         assert label is None or isinstance(label, str)
    344         assert isinstance(next, NFAState)
    345         self.arcs.append((label, next))
    346 
    347 class DFAState(object):
    348 
    349     def __init__(self, nfaset, final):
    350         assert isinstance(nfaset, dict)
    351         assert isinstance(iter(nfaset).next(), NFAState)
    352         assert isinstance(final, NFAState)
    353         self.nfaset = nfaset
    354         self.isfinal = final in nfaset
    355         self.arcs = {} # map from label to DFAState
    356 
    357     def addarc(self, next, label):
    358         assert isinstance(label, str)
    359         assert label not in self.arcs
    360         assert isinstance(next, DFAState)
    361         self.arcs[label] = next
    362 
    363     def unifystate(self, old, new):
    364         for label, next in self.arcs.iteritems():
    365             if next is old:
    366                 self.arcs[label] = new
    367 
    368     def __eq__(self, other):
    369         # Equality test -- ignore the nfaset instance variable
    370         assert isinstance(other, DFAState)
    371         if self.isfinal != other.isfinal:
    372             return False
    373         # Can't just return self.arcs == other.arcs, because that
    374         # would invoke this method recursively, with cycles...
    375         if len(self.arcs) != len(other.arcs):
    376             return False
    377         for label, next in self.arcs.iteritems():
    378             if next is not other.arcs.get(label):
    379                 return False
    380         return True
    381 
    382     __hash__ = None # For Py3 compatibility.
    383 
    384 def generate_grammar(filename="Grammar.txt"):
    385     p = ParserGenerator(filename)
    386     return p.make_grammar()
    387