blib2to3/pgen2/pgen.py

   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 = list(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 sorted(state.arcs.items()):
  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 sorted(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 = list(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.items():
 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.items():
 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 sorted(arcs.items()):
 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 sorted(state.arcs.items()):
 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 = next(self.generator)
 323         while tup[0] in (tokenize.COMMENT, tokenize.NL):
 324             tup = next(self.generator)
 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] + list(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(next(iter(nfaset)), 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.items():
 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.items():
 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()