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