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
