blib2to3/pgen2/conv.py

   1 # Copyright 2004-2005 Elemental Security, Inc. All Rights Reserved.
   2 # Licensed to PSF under a Contributor Agreement.
   3
   4 """Convert graminit.[ch] spit out by pgen to Python code.
   5
   6 Pgen is the Python parser generator.  It is useful to quickly create a
   7 parser from a grammar file in Python's grammar notation.  But I don't
   8 want my parsers to be written in C (yet), so I'm translating the
   9 parsing tables to Python data structures and writing a Python parse
  10 engine.
  11
  12 Note that the token numbers are constants determined by the standard
  13 Python tokenizer.  The standard token module defines these numbers and
  14 their names (the names are not used much).  The token numbers are
  15 hardcoded into the Python tokenizer and into pgen.  A Python
  16 implementation of the Python tokenizer is also available, in the
  17 standard tokenize module.
  18
  19 On the other hand, symbol numbers (representing the grammar's
  20 non-terminals) are assigned by pgen based on the actual grammar
  21 input.
  22
  23 Note: this module is pretty much obsolete; the pgen module generates
  24 equivalent grammar tables directly from the Grammar.txt input file
  25 without having to invoke the Python pgen C program.
  26
  27 """
  28
  29 # Python imports
  30 import re
  31
  32 # Local imports
  33 from pgen2 import grammar, token
  34
  35
  36 class Converter(grammar.Grammar):
  37     """Grammar subclass that reads classic pgen output files.
  38
  39     The run() method reads the tables as produced by the pgen parser
  40     generator, typically contained in two C files, graminit.h and
  41     graminit.c.  The other methods are for internal use only.
  42
  43     See the base class for more documentation.
  44
  45     """
  46
  47     def run(self, graminit_h, graminit_c):
  48         """Load the grammar tables from the text files written by pgen."""
  49         self.parse_graminit_h(graminit_h)
  50         self.parse_graminit_c(graminit_c)
  51         self.finish_off()
  52
  53     def parse_graminit_h(self, filename):
  54         """Parse the .h file written by pgen.  (Internal)
  55
  56         This file is a sequence of #define statements defining the
  57         nonterminals of the grammar as numbers.  We build two tables
  58         mapping the numbers to names and back.
  59
  60         """
  61         try:
  62             f = open(filename)
  63         except OSError as err:
  64             print("Can't open %s: %s" % (filename, err))
  65             return False
  66         self.symbol2number = {}
  67         self.number2symbol = {}
  68         lineno = 0
  69         for line in f:
  70             lineno += 1
  71             mo = re.match(r"^#define\s+(\w+)\s+(\d+)$", line)
  72             if not mo and line.strip():
  73                 print("%s(%s): can't parse %s" % (filename, lineno,
  74                                                   line.strip()))
  75             else:
  76                 symbol, number = mo.groups()
  77                 number = int(number)
  78                 assert symbol not in self.symbol2number
  79                 assert number not in self.number2symbol
  80                 self.symbol2number[symbol] = number
  81                 self.number2symbol[number] = symbol
  82         return True
  83
  84     def parse_graminit_c(self, filename):
  85         """Parse the .c file written by pgen.  (Internal)
  86
  87         The file looks as follows.  The first two lines are always this:
  88
  89         #include "pgenheaders.h"
  90         #include "grammar.h"
  91
  92         After that come four blocks:
  93
  94         1) one or more state definitions
  95         2) a table defining dfas
  96         3) a table defining labels
  97         4) a struct defining the grammar
  98
  99         A state definition has the following form:
 100         - one or more arc arrays, each of the form:
 101           static arc arcs_<n>_<m>[<k>] = {
 102                   {<i>, <j>},
 103                   ...
 104           };
 105         - followed by a state array, of the form:
 106           static state states_<s>[<t>] = {
 107                   {<k>, arcs_<n>_<m>},
 108                   ...
 109           };
 110
 111         """
 112         try:
 113             f = open(filename)
 114         except OSError as err:
 115             print("Can't open %s: %s" % (filename, err))
 116             return False
 117         # The code below essentially uses f's iterator-ness!
 118         lineno = 0
 119
 120         # Expect the two #include lines
 121         lineno, line = lineno+1, next(f)
 122         assert line == '#include "pgenheaders.h"\n', (lineno, line)
 123         lineno, line = lineno+1, next(f)
 124         assert line == '#include "grammar.h"\n', (lineno, line)
 125
 126         # Parse the state definitions
 127         lineno, line = lineno+1, next(f)
 128         allarcs = {}
 129         states = []
 130         while line.startswith("static arc "):
 131             while line.startswith("static arc "):
 132                 mo = re.match(r"static arc arcs_(\d+)_(\d+)\[(\d+)\] = {$",
 133                               line)
 134                 assert mo, (lineno, line)
 135                 n, m, k = list(map(int, mo.groups()))
 136                 arcs = []
 137                 for _ in range(k):
 138                     lineno, line = lineno+1, next(f)
 139                     mo = re.match(r"\s+{(\d+), (\d+)},$", line)
 140                     assert mo, (lineno, line)
 141                     i, j = list(map(int, mo.groups()))
 142                     arcs.append((i, j))
 143                 lineno, line = lineno+1, next(f)
 144                 assert line == "};\n", (lineno, line)
 145                 allarcs[(n, m)] = arcs
 146                 lineno, line = lineno+1, next(f)
 147             mo = re.match(r"static state states_(\d+)\[(\d+)\] = {$", line)
 148             assert mo, (lineno, line)
 149             s, t = list(map(int, mo.groups()))
 150             assert s == len(states), (lineno, line)
 151             state = []
 152             for _ in range(t):
 153                 lineno, line = lineno+1, next(f)
 154                 mo = re.match(r"\s+{(\d+), arcs_(\d+)_(\d+)},$", line)
 155                 assert mo, (lineno, line)
 156                 k, n, m = list(map(int, mo.groups()))
 157                 arcs = allarcs[n, m]
 158                 assert k == len(arcs), (lineno, line)
 159                 state.append(arcs)
 160             states.append(state)
 161             lineno, line = lineno+1, next(f)
 162             assert line == "};\n", (lineno, line)
 163             lineno, line = lineno+1, next(f)
 164         self.states = states
 165
 166         # Parse the dfas
 167         dfas = {}
 168         mo = re.match(r"static dfa dfas\[(\d+)\] = {$", line)
 169         assert mo, (lineno, line)
 170         ndfas = int(mo.group(1))
 171         for i in range(ndfas):
 172             lineno, line = lineno+1, next(f)
 173             mo = re.match(r'\s+{(\d+), "(\w+)", (\d+), (\d+), states_(\d+),$',
 174                           line)
 175             assert mo, (lineno, line)
 176             symbol = mo.group(2)
 177             number, x, y, z = list(map(int, mo.group(1, 3, 4, 5)))
 178             assert self.symbol2number[symbol] == number, (lineno, line)
 179             assert self.number2symbol[number] == symbol, (lineno, line)
 180             assert x == 0, (lineno, line)
 181             state = states[z]
 182             assert y == len(state), (lineno, line)
 183             lineno, line = lineno+1, next(f)
 184             mo = re.match(r'\s+("(?:\\\d\d\d)*")},$', line)
 185             assert mo, (lineno, line)
 186             first = {}
 187             rawbitset = eval(mo.group(1))
 188             for i, c in enumerate(rawbitset):
 189                 byte = ord(c)
 190                 for j in range(8):
 191                     if byte & (1<<j):
 192                         first[i*8 + j] = 1
 193             dfas[number] = (state, first)
 194         lineno, line = lineno+1, next(f)
 195         assert line == "};\n", (lineno, line)
 196         self.dfas = dfas
 197
 198         # Parse the labels
 199         labels = []
 200         lineno, line = lineno+1, next(f)
 201         mo = re.match(r"static label labels\[(\d+)\] = {$", line)
 202         assert mo, (lineno, line)
 203         nlabels = int(mo.group(1))
 204         for i in range(nlabels):
 205             lineno, line = lineno+1, next(f)
 206             mo = re.match(r'\s+{(\d+), (0|"\w+")},$', line)
 207             assert mo, (lineno, line)
 208             x, y = mo.groups()
 209             x = int(x)
 210             if y == "0":
 211                 y = None
 212             else:
 213                 y = eval(y)
 214             labels.append((x, y))
 215         lineno, line = lineno+1, next(f)
 216         assert line == "};\n", (lineno, line)
 217         self.labels = labels
 218
 219         # Parse the grammar struct
 220         lineno, line = lineno+1, next(f)
 221         assert line == "grammar _PyParser_Grammar = {\n", (lineno, line)
 222         lineno, line = lineno+1, next(f)
 223         mo = re.match(r"\s+(\d+),$", line)
 224         assert mo, (lineno, line)
 225         ndfas = int(mo.group(1))
 226         assert ndfas == len(self.dfas)
 227         lineno, line = lineno+1, next(f)
 228         assert line == "\tdfas,\n", (lineno, line)
 229         lineno, line = lineno+1, next(f)
 230         mo = re.match(r"\s+{(\d+), labels},$", line)
 231         assert mo, (lineno, line)
 232         nlabels = int(mo.group(1))
 233         assert nlabels == len(self.labels), (lineno, line)
 234         lineno, line = lineno+1, next(f)
 235         mo = re.match(r"\s+(\d+)$", line)
 236         assert mo, (lineno, line)
 237         start = int(mo.group(1))
 238         assert start in self.number2symbol, (lineno, line)
 239         self.start = start
 240         lineno, line = lineno+1, next(f)
 241         assert line == "};\n", (lineno, line)
 242         try:
 243             lineno, line = lineno+1, next(f)
 244         except StopIteration:
 245             pass
 246         else:
 247             assert 0, (lineno, line)
 248
 249     def finish_off(self):
 250         """Create additional useful structures.  (Internal)."""
 251         self.keywords = {} # map from keyword strings to arc labels
 252         self.tokens = {}   # map from numeric token values to arc labels
 253         for ilabel, (type, value) in enumerate(self.labels):
 254             if type == token.NAME and value is not None:
 255                 self.keywords[value] = ilabel
 256             elif value is None:
 257                 self.tokens[type] = ilabel