Whole file
rocky/python-spark
The author described this change as “Fix bug in dumpGrammar()”. It counts as a record because the check below fails on the code as it stood at 0bf3a5c25 and passes on 93e012447, with nothing else changed between the two runs.
Projectrocky/python-spark
Fix saved2017-01-27
Sharing licenceMIT · LICENSE
Change size+791 −791
What the code was meant to do, written into the code itself as a save note
Fix bug in dumpGrammar()
The change
| 1 | 1 | """ | |
| 2 | - | Copyright (c) 2015-2016 Rocky Bernstein | |
| 3 | - | Copyright (c) 1998-2002 John Aycock | |
| 4 | - | ||
| 5 | - | Permission is hereby granted, free of charge, to any person obtaining | |
| 6 | - | a copy of this software and associated documentation files (the | |
| 7 | - | "Software"), to deal in the Software without restriction, including | |
| 8 | - | without limitation the rights to use, copy, modify, merge, publish, | |
| 9 | - | distribute, sublicense, and/or sell copies of the Software, and to | |
| 10 | - | permit persons to whom the Software is furnished to do so, subject to | |
| 11 | - | the following conditions: | |
| 12 | - | ||
| 13 | - | The above copyright notice and this permission notice shall be | |
| 14 | - | included in all copies or substantial portions of the Software. | |
| 15 | - | ||
| 16 | - | THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, | |
| 17 | - | EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF | |
| 18 | - | MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. | |
| 19 | - | IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY | |
| 20 | - | CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, | |
| 21 | - | TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE | |
| 22 | - | SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. | |
| 23 | - | """ | |
| 24 | - | ||
| 25 | - | import os, re, sys | |
| 26 | - | ||
| 27 | - | if sys.version[0:3] <= '2.3': | |
| 28 | - | from sets import Set as set | |
| 29 | - | ||
| 30 | - | def sorted(iterable): | |
| 31 | - | temp = [x for x in iterable] | |
| 32 | - | temp.sort() | |
| 33 | - | return temp | |
| 34 | - | ||
| 35 | - | def _namelist(instance): | |
| 36 | - | namelist, namedict, classlist = [], {}, [instance.__class__] | |
| 37 | - | for c in classlist: | |
| 38 | - | for b in c.__bases__: | |
| 39 | - | classlist.append(b) | |
| 40 | - | for name in list(c.__dict__.keys()): | |
| 41 | - | if name not in namedict: | |
| 42 | - | namelist.append(name) | |
| 43 | - | namedict[name] = 1 | |
| 44 | - | return namelist | |
| 45 | - | ||
| 46 | - | def rule2str(rule): | |
| 47 | - | return "%s ::= %s" % (rule[0], ' '.join(rule[1])) | |
| 48 | - | ||
| 49 | - | class _State: | |
| 50 | - | ''' | |
| 51 | - | Extracted from GenericParser and made global so that [un]picking works. | |
| 52 | - | ''' | |
| 53 | - | def __init__(self, stateno, items): | |
| 54 | - | self.T, self.complete, self.items = [], [], items | |
| 55 | - | self.stateno = stateno | |
| 56 | - | ||
| 57 | - | # DEFAULT_DEBUG = {'rules': True, 'transition': True, 'reduce' : True, | |
| 58 | - | # 'errorstack': 'full', 'dups': False } | |
| 59 | - | # DEFAULT_DEBUG = {'rules': False, 'transition': False, 'reduce' : True, | |
| 60 | - | # 'errorstack': 'plain', 'dups': False } | |
| 61 | - | DEFAULT_DEBUG = {'rules': False, 'transition': False, 'reduce': False, | |
| 62 | - | 'errorstack': None, 'context': True, 'dups': False} | |
| 63 | - | ||
| 64 | - | class GenericParser(object): | |
| 65 | - | ''' | |
| 66 | - | An Earley parser, as per J. Earley, "An Efficient Context-Free | |
| 67 | - | Parsing Algorithm", CACM 13(2), pp. 94-102. Also J. C. Earley, | |
| 68 | - | "An Efficient Context-Free Parsing Algorithm", Ph.D. thesis, | |
| 69 | - | Carnegie-Mellon University, August 1968. New formulation of | |
| 70 | - | the parser according to J. Aycock, "Practical Earley Parsing | |
| 71 | - | and the SPARK Toolkit", Ph.D. thesis, University of Victoria, | |
| 72 | - | 2001, and J. Aycock and R. N. Horspool, "Practical Earley | |
| 73 | - | Parsing", unpublished paper, 2001. | |
| 74 | - | ''' | |
| 75 | - | ||
| 76 | - | def __init__(self, start, debug=DEFAULT_DEBUG): | |
| 77 | - | self.rules = {} | |
| 78 | - | self.rule2func = {} | |
| 79 | - | self.rule2name = {} | |
| 80 | - | ||
| 81 | - | # When set, shows additional debug output | |
| 82 | - | self.debug = debug | |
| 83 | - | ||
| 84 | - | self.collectRules() | |
| 85 | - | if start not in self.rules: | |
| 86 | - | raise TypeError('Start symbol "%s" is not in LHS of any rule' % start) | |
| 87 | - | self.augment(start) | |
| 88 | - | self.ruleschanged = True | |
| 89 | - | ||
| 90 | - | # The key is an LHS non-terminal string. The value | |
| 91 | - | # should be AST if you want to pass an AST to the routine | |
| 92 | - | # to do the checking. The routine called is | |
| 93 | - | # self.reduce_is_invalid and is passed the rule, | |
| 94 | - | # the list of tokens, the current state item, | |
| 95 | - | # and index of the next last token index and | |
| 96 | - | # the first token index for the reduction. | |
| 97 | - | self.check_reduce = {} | |
| 98 | - | ||
| 99 | - | _NULLABLE = '\e_' | |
| 100 | - | _START = 'START' | |
| 101 | - | _BOF = '|-' | |
| 102 | - | ||
| 103 | - | # | |
| 104 | - | # When pickling, take the time to generate the full state machine; | |
| 105 | - | # some information is then extraneous, too. Unfortunately we | |
| 106 | - | # can't save the rule2func map. | |
| 107 | - | # | |
| 108 | - | def __getstate__(self): | |
| 109 | - | if self.ruleschanged: | |
| 110 | - | # | |
| 111 | - | # XXX - duplicated from parse() | |
| 112 | - | # | |
| 113 | - | self.computeNull() | |
| 114 | - | self.newrules = {} | |
| 115 | - | self.new2old = {} | |
| 116 | - | self.makeNewRules() | |
| 117 | - | self.ruleschanged = False | |
| 118 | - | self.edges, self.cores = {}, {} | |
| 119 | - | self.states = {0: self.makeState0()} | |
| 120 | - | self.makeState(0, self._BOF) | |
| 121 | - | # | |
| 122 | - | # XXX - should find a better way to do this.. | |
| 123 | - | # | |
| 124 | - | changes = 1 | |
| 125 | - | while changes: | |
| 126 | - | changes = 0 | |
| 127 | - | for k, v in list(self.edges.items()): | |
| 128 | - | if v is None: | |
| 129 | - | state, sym = k | |
| 130 | - | if state in self.states: | |
| 131 | - | self.goto(state, sym) | |
| 132 | - | changes = 1 | |
| 133 | - | rv = self.__dict__.copy() | |
| 134 | - | for s in list(self.states.values()): | |
| 135 | - | del s.items | |
| 136 | - | del rv['rule2func'] | |
| 137 | - | del rv['nullable'] | |
| 138 | - | del rv['cores'] | |
| 139 | - | return rv | |
| 140 | - | ||
| 141 | - | def __setstate__(self, D): | |
| 142 | - | self.rules = {} | |
| 143 | - | self.rule2func = {} | |
| 144 | - | self.rule2name = {} | |
| 145 | - | self.collectRules() | |
| 146 | - | start = D['rules'][self._START][0][1][1] # Blech. | |
| 147 | - | self.augment(start) | |
| 148 | - | D['rule2func'] = self.rule2func | |
| 149 | - | D['makeSet'] = self.makeSet_fast | |
| 150 | - | self.__dict__ = D | |
| 151 | - | ||
| 152 | - | # | |
| 153 | - | # A hook for GenericASTBuilder and GenericASTMatcher. Mess | |
| 154 | - | # thee not with this; nor shall thee toucheth the _preprocess | |
| 155 | - | # argument to addRule. | |
| 156 | - | # | |
| 157 | - | def preprocess(self, rule, func): | |
| 158 | - | return rule, func | |
| 159 | - | ||
| 160 | - | def addRule(self, doc, func, _preprocess=True): | |
| 161 | - | """Add a grammar rules to _self.rules_, _self.rule2func_, | |
| 162 | - | and _self.rule2name_ | |
| 163 | - | ||
| 164 | - | Comments, lines starting with # and blank lines are stripped from | |
| 165 | - | doc. We also allow limited form of * and + when there it is of | |
| 166 | - | the RHS has a single item, e.g. | |
| 167 | - | stmts ::= stmt+ | |
| 168 | - | """ | |
| 169 | - | fn = func | |
| 170 | - | ||
| 171 | - | # remove blanks lines and comment lines, e.g. lines starting with "#" | |
| 172 | - | doc = os.linesep.join([s for s in doc.splitlines() if s and not re.match("^\s*#", s)]) | |
| 173 | - | ||
| 174 | - | rules = doc.split() | |
| 175 | - | ||
| 176 | - | index = [] | |
| 177 | - | for i in range(len(rules)): | |
| 178 | - | if rules[i] == '::=': | |
| 179 | - | index.append(i-1) | |
| 180 | - | index.append(len(rules)) | |
| 181 | - | ||
| 182 | - | for i in range(len(index)-1): | |
| 183 | - | lhs = rules[index[i]] | |
| 184 | - | rhs = rules[index[i]+2:index[i+1]] | |
| 185 | - | rule = (lhs, tuple(rhs)) | |
| 186 | - | ||
| 187 | - | if _preprocess: | |
| 188 | - | rule, fn = self.preprocess(rule, func) | |
| 189 | - | ||
| 190 | - | # Handle a stripped-down form of *, +, and ?: | |
| 191 | - | # allow only one nonterminal on the right-hand side | |
| 192 | - | if len(rule[1]) == 1: | |
| 193 | - | ||
| 194 | - | if rule[1][0] == rule[0]: | |
| 195 | - | raise TypeError("Complete recursive rule %s" % rule2str(rule)) | |
| 196 | - | ||
| 197 | - | if rule[1][-1][-1] in ('*', '+', '?'): | |
| 198 | - | repeat = rule[1][-1][-1] | |
| 199 | - | nt = rule[1][-1][:-1] | |
| 200 | - | if repeat == '?': | |
| 201 | - | new_rule_pair = [rule[0], list((nt,))] | |
| 202 | - | else: | |
| 203 | - | new_rule_pair = [rule[0], [rule[0]] + list((nt,))] | |
| 204 | - | new_rule = rule2str(new_rule_pair) | |
| 205 | - | self.addRule(new_rule, func, _preprocess) | |
| 206 | - | if repeat == '+': | |
| 207 | - | second_rule_pair = (lhs, (nt,)) | |
| 208 | - | else: | |
| 209 | - | second_rule_pair = (lhs, tuple()) | |
| 210 | - | new_rule = rule2str(second_rule_pair) | |
| 211 | - | self.addRule(new_rule, func, _preprocess) | |
| 212 | - | continue | |
| 213 | - | ||
| 214 | - | if lhs in self.rules: | |
| 215 | - | if rule in self.rules[lhs]: | |
| 216 | - | if 'dups' in self.debug and self.debug['dups']: | |
| 217 | - | self.duplicate_rule(rule) | |
| 218 | - | continue | |
| 219 | - | self.rules[lhs].append(rule) | |
| 220 | - | else: | |
| 221 | - | self.rules[lhs] = [ rule ] | |
| 222 | - | self.rule2func[rule] = fn | |
| 223 | - | self.rule2name[rule] = func.__name__[2:] | |
| 224 | - | self.ruleschanged = True | |
| 225 | - | pass | |
| 226 | - | return | |
| 227 | - | ||
| 228 | - | def collectRules(self): | |
| 229 | - | for name in _namelist(self): | |
| 230 | - | if name[:2] == 'p_': | |
| 231 | - | func = getattr(self, name) | |
| 232 | - | doc = func.__doc__ | |
| 233 | - | self.addRule(doc, func) | |
| 234 | - | ||
| 235 | - | def augment(self, start): | |
| 236 | - | rule = '%s ::= %s %s' % (self._START, self._BOF, start) | |
| 237 | - | self.addRule(rule, lambda args: args[1], 0) | |
| 238 | - | ||
| 239 | - | def computeNull(self): | |
| 240 | - | self.nullable = {} | |
| 241 | - | tbd = [] | |
| 242 | - | ||
| 243 | - | for rulelist in list(self.rules.values()): | |
| 244 | - | lhs = rulelist[0][0] | |
| 245 | - | self.nullable[lhs] = 0 | |
| 246 | - | for rule in rulelist: | |
| 247 | - | rhs = rule[1] | |
| 248 | - | if len(rhs) == 0: | |
| 249 | - | self.nullable[lhs] = 1 | |
| 250 | - | continue | |
| 251 | - | # | |
| 252 | - | # We only need to consider rules which | |
| 253 | - | # consist entirely of nonterminal symbols. | |
| 254 | - | # This should be a savings on typical | |
| 255 | - | # grammars. | |
| 256 | - | # | |
| 257 | - | for sym in rhs: | |
| 258 | - | if sym not in self.rules: | |
| 259 | - | break | |
| 260 | - | else: | |
| 261 | - | tbd.append(rule) | |
| 262 | - | changes = 1 | |
| 263 | - | while changes: | |
| 264 | - | changes = 0 | |
| 265 | - | for lhs, rhs in tbd: | |
| 266 | - | if self.nullable[lhs]: | |
| 267 | - | continue | |
| 268 | - | for sym in rhs: | |
| 269 | - | if not self.nullable[sym]: | |
| 270 | - | break | |
| 271 | - | else: | |
| 272 | - | self.nullable[lhs] = 1 | |
| 273 | - | changes = 1 | |
| 274 | - | ||
| 275 | - | def makeState0(self): | |
| 276 | - | s0 = _State(0, []) | |
| 277 | - | for rule in self.newrules[self._START]: | |
| 278 | - | s0.items.append((rule, 0)) | |
| 279 | - | return s0 | |
| 280 | - | ||
| 281 | - | def finalState(self, tokens): | |
| 282 | - | # | |
| 283 | - | # Yuck. | |
| 284 | - | # | |
| 285 | - | if len(self.newrules[self._START]) == 2 and len(tokens) == 0: | |
| 286 | - | return 1 | |
| 287 | - | start = self.rules[self._START][0][1][1] | |
| 288 | - | return self.goto(1, start) | |
| 289 | - | ||
| 290 | - | def makeNewRules(self): | |
| 291 | - | worklist = [] | |
| 292 | - | for rulelist in list(self.rules.values()): | |
| 293 | - | for rule in rulelist: | |
| 294 | - | worklist.append((rule, 0, 1, rule)) | |
| 295 | - | ||
| 296 | - | for rule, i, candidate, oldrule in worklist: | |
| 297 | - | lhs, rhs = rule | |
| 298 | - | n = len(rhs) | |
| 299 | - | while i < n: | |
| 300 | - | sym = rhs[i] | |
| 301 | - | if (sym not in self.rules or | |
| 302 | - | not self.nullable[sym]): | |
| 303 | - | candidate = 0 | |
| 304 | - | i = i + 1 | |
| 305 | - | continue | |
| 306 | - | ||
| 307 | - | newrhs = list(rhs) | |
| 308 | - | newrhs[i] = self._NULLABLE+sym | |
| 309 | - | newrule = (lhs, tuple(newrhs)) | |
| 310 | - | worklist.append((newrule, i+1, | |
| 311 | - | candidate, oldrule)) | |
| 312 | - | candidate = 0 | |
| 313 | - | i = i + 1 | |
| 314 | - | else: | |
| 315 | - | if candidate: | |
| 316 | - | lhs = self._NULLABLE+lhs | |
| 317 | - | rule = (lhs, rhs) | |
| 318 | - | if lhs in self.newrules: | |
| 319 | - | self.newrules[lhs].append(rule) | |
| 320 | - | else: | |
| 321 | - | self.newrules[lhs] = [rule] | |
| 322 | - | self.new2old[rule] = oldrule | |
| 323 | - | ||
| 324 | - | def typestring(self, token): | |
| 325 | - | return None | |
| 326 | - | ||
| 327 | - | def duplicate_rule(self, rule): | |
| 328 | - | print("Duplicate rule:\n\t%s" % rule2str(rule)) | |
| 329 | - | ||
| 330 | - | def error(self, tokens, index): | |
| 331 | - | print("Syntax error at or near token %d: `%s'" % (index, tokens[index])) | |
| 332 | - | ||
| 333 | - | if 'context' in self.debug and self.debug['context']: | |
| 334 | - | start = index - 2 if index - 2 >= 0 else 0 | |
| 335 | - | tokens = [str(tokens[i]) for i in range(start, index+1)] | |
| 336 | - | print("Token context:\n\t%s" % ("\n\t".join(tokens))) | |
| 337 | - | raise SystemExit | |
| 338 | - | ||
| 339 | - | def errorstack(self, tokens, i, full=False): | |
| 340 | - | """Show the stacks of completed symbols. | |
| 341 | - | We get this by inspecting the current transitions | |
| 342 | - | possible and from that extracting the set of states | |
| 343 | - | we are in, and from there we look at the set of | |
| 344 | - | symbols before the "dot". If full is True, we | |
| 345 | - | show the entire rule with the dot placement. | |
| 346 | - | Otherwise just the rule up to the dot. | |
| 347 | - | """ | |
| 348 | - | print("\n-- Stacks of completed symbols:") | |
| 349 | - | states = [s for s in self.edges.values() if s] | |
| 350 | - | # States now has the set of states we are in | |
| 351 | - | state_stack = set() | |
| 352 | - | for state in states: | |
| 353 | - | # Find rules which can follow, but keep only | |
| 354 | - | # the part before the dot | |
| 355 | - | for rule, dot in self.states[state].items: | |
| 356 | - | lhs, rhs = rule | |
| 357 | - | if dot > 0: | |
| 358 | - | if full: | |
| 359 | - | state_stack.add(' '.join(rhs[:dot]) + ' . ' + ' '.join(rhs[dot:])) | |
| 360 | - | else: | |
| 361 | - | state_stack.add(' '.join(rhs[:dot])) | |
| 362 | - | pass | |
| 363 | - | pass | |
| 364 | - | pass | |
| 365 | - | for stack in sorted(state_stack): | |
| 366 | - | print(stack) | |
| 367 | - | ||
| 368 | - | def parse(self, tokens, debug=None): | |
| 369 | - | """This is the main entry point from outside. | |
| 370 | - | ||
| 371 | - | Passing in a debug dictionary changes the default debug | |
| 372 | - | setting. | |
| 373 | - | """ | |
| 374 | - | ||
| 375 | - | if debug: | |
| 376 | - | self.debug = debug | |
| 377 | - | ||
| 378 | - | sets = [ [(1, 0), (2, 0)] ] | |
| 379 | - | self.links = {} | |
| 380 | - | ||
| 381 | - | if self.ruleschanged: | |
| 382 | - | self.computeNull() | |
| 383 | - | self.newrules = {} | |
| 384 | - | self.new2old = {} | |
| 385 | - | self.makeNewRules() | |
| 386 | - | self.ruleschanged = False | |
| 387 | - | self.edges, self.cores = {}, {} | |
| 388 | - | self.states = { 0: self.makeState0() } | |
| 389 | - | self.makeState(0, self._BOF) | |
| 390 | - | ||
| 391 | - | for i in range(len(tokens)): | |
| 392 | - | sets.append([]) | |
| 393 | - | ||
| 394 | - | if sets[i] == []: | |
| 395 | - | break | |
| 396 | - | self.makeSet(tokens, sets, i) | |
| 397 | - | else: | |
| 398 | - | sets.append([]) | |
| 399 | - | self.makeSet(None, sets, len(tokens)) | |
| 400 | - | ||
| 1186 further changed lines not shown | |||
The check that tells the two apart
fail→pass·test/test_misc.py::TestMisc::test_basic
Check file test/test_misc.py, taken without changes from the fix and copied onto the older code, so the exact same check runs against both versions.
Origin and history
The code before it0bf3a5c2505a059064daf5e96b40c89900818822
Broken version dated2016-12-08
Modulespark_parser.spark
Units changedGenericParser, rule2str
Fingerprint63e3a740adc994ef
Checked2026-08-18 by goldset/0.1
Every field above is generated by our program. None of it is written by hand.