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 IOError, 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 IOError, 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, f.next() 122 assert line == '#include "pgenheaders.h"\n', (lineno, line) 123 lineno, line = lineno+1, f.next() 124 assert line == '#include "grammar.h"\n', (lineno, line) 125 126 # Parse the state definitions 127 lineno, line = lineno+1, f.next() 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 = map(int, mo.groups()) 136 arcs = [] 137 for _ in range(k): 138 lineno, line = lineno+1, f.next() 139 mo = re.match(r"\s+{(\d+), (\d+)},$", line) 140 assert mo, (lineno, line) 141 i, j = map(int, mo.groups()) 142 arcs.append((i, j)) 143 lineno, line = lineno+1, f.next() 144 assert line == "};\n", (lineno, line) 145 allarcs[(n, m)] = arcs 146 lineno, line = lineno+1, f.next() 147 mo = re.match(r"static state states_(\d+)\[(\d+)\] = {$", line) 148 assert mo, (lineno, line) 149 s, t = map(int, mo.groups()) 150 assert s == len(states), (lineno, line) 151 state = [] 152 for _ in range(t): 153 lineno, line = lineno+1, f.next() 154 mo = re.match(r"\s+{(\d+), arcs_(\d+)_(\d+)},$", line) 155 assert mo, (lineno, line) 156 k, n, m = 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, f.next() 162 assert line == "};\n", (lineno, line) 163 lineno, line = lineno+1, f.next() 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, f.next() 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 = 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, f.next() 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, f.next() 195 assert line == "};\n", (lineno, line) 196 self.dfas = dfas 197 198 # Parse the labels 199 labels = [] 200 lineno, line = lineno+1, f.next() 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, f.next() 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, f.next() 216 assert line == "};\n", (lineno, line) 217 self.labels = labels 218 219 # Parse the grammar struct 220 lineno, line = lineno+1, f.next() 221 assert line == "grammar _PyParser_Grammar = {\n", (lineno, line) 222 lineno, line = lineno+1, f.next() 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, f.next() 228 assert line == "\tdfas,\n", (lineno, line) 229 lineno, line = lineno+1, f.next() 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, f.next() 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, f.next() 241 assert line == "};\n", (lineno, line) 242 try: 243 lineno, line = lineno+1, f.next() 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 258
