--- /dev/null
+# Copyright 2004-2005 Elemental Security, Inc. All Rights Reserved.\r
+# Licensed to PSF under a Contributor Agreement.\r
+\r
+# Pgen imports\r
+from . import grammar, token, tokenize\r
+\r
+class PgenGrammar(grammar.Grammar):\r
+ pass\r
+\r
+class ParserGenerator(object):\r
+\r
+ def __init__(self, filename, stream=None):\r
+ close_stream = None\r
+ if stream is None:\r
+ stream = open(filename)\r
+ close_stream = stream.close\r
+ self.filename = filename\r
+ self.stream = stream\r
+ self.generator = tokenize.generate_tokens(stream.readline)\r
+ self.gettoken() # Initialize lookahead\r
+ self.dfas, self.startsymbol = self.parse()\r
+ if close_stream is not None:\r
+ close_stream()\r
+ self.first = {} # map from symbol name to set of tokens\r
+ self.addfirstsets()\r
+\r
+ def make_grammar(self):\r
+ c = PgenGrammar()\r
+ names = self.dfas.keys()\r
+ names.sort()\r
+ names.remove(self.startsymbol)\r
+ names.insert(0, self.startsymbol)\r
+ for name in names:\r
+ i = 256 + len(c.symbol2number)\r
+ c.symbol2number[name] = i\r
+ c.number2symbol[i] = name\r
+ for name in names:\r
+ dfa = self.dfas[name]\r
+ states = []\r
+ for state in dfa:\r
+ arcs = []\r
+ for label, next in state.arcs.iteritems():\r
+ arcs.append((self.make_label(c, label), dfa.index(next)))\r
+ if state.isfinal:\r
+ arcs.append((0, dfa.index(state)))\r
+ states.append(arcs)\r
+ c.states.append(states)\r
+ c.dfas[c.symbol2number[name]] = (states, self.make_first(c, name))\r
+ c.start = c.symbol2number[self.startsymbol]\r
+ return c\r
+\r
+ def make_first(self, c, name):\r
+ rawfirst = self.first[name]\r
+ first = {}\r
+ for label in rawfirst:\r
+ ilabel = self.make_label(c, label)\r
+ ##assert ilabel not in first # XXX failed on <> ... !=\r
+ first[ilabel] = 1\r
+ return first\r
+\r
+ def make_label(self, c, label):\r
+ # XXX Maybe this should be a method on a subclass of converter?\r
+ ilabel = len(c.labels)\r
+ if label[0].isalpha():\r
+ # Either a symbol name or a named token\r
+ if label in c.symbol2number:\r
+ # A symbol name (a non-terminal)\r
+ if label in c.symbol2label:\r
+ return c.symbol2label[label]\r
+ else:\r
+ c.labels.append((c.symbol2number[label], None))\r
+ c.symbol2label[label] = ilabel\r
+ return ilabel\r
+ else:\r
+ # A named token (NAME, NUMBER, STRING)\r
+ itoken = getattr(token, label, None)\r
+ assert isinstance(itoken, int), label\r
+ assert itoken in token.tok_name, label\r
+ if itoken in c.tokens:\r
+ return c.tokens[itoken]\r
+ else:\r
+ c.labels.append((itoken, None))\r
+ c.tokens[itoken] = ilabel\r
+ return ilabel\r
+ else:\r
+ # Either a keyword or an operator\r
+ assert label[0] in ('"', "'"), label\r
+ value = eval(label)\r
+ if value[0].isalpha():\r
+ # A keyword\r
+ if value in c.keywords:\r
+ return c.keywords[value]\r
+ else:\r
+ c.labels.append((token.NAME, value))\r
+ c.keywords[value] = ilabel\r
+ return ilabel\r
+ else:\r
+ # An operator (any non-numeric token)\r
+ itoken = grammar.opmap[value] # Fails if unknown token\r
+ if itoken in c.tokens:\r
+ return c.tokens[itoken]\r
+ else:\r
+ c.labels.append((itoken, None))\r
+ c.tokens[itoken] = ilabel\r
+ return ilabel\r
+\r
+ def addfirstsets(self):\r
+ names = self.dfas.keys()\r
+ names.sort()\r
+ for name in names:\r
+ if name not in self.first:\r
+ self.calcfirst(name)\r
+ #print name, self.first[name].keys()\r
+\r
+ def calcfirst(self, name):\r
+ dfa = self.dfas[name]\r
+ self.first[name] = None # dummy to detect left recursion\r
+ state = dfa[0]\r
+ totalset = {}\r
+ overlapcheck = {}\r
+ for label, next in state.arcs.iteritems():\r
+ if label in self.dfas:\r
+ if label in self.first:\r
+ fset = self.first[label]\r
+ if fset is None:\r
+ raise ValueError("recursion for rule %r" % name)\r
+ else:\r
+ self.calcfirst(label)\r
+ fset = self.first[label]\r
+ totalset.update(fset)\r
+ overlapcheck[label] = fset\r
+ else:\r
+ totalset[label] = 1\r
+ overlapcheck[label] = {label: 1}\r
+ inverse = {}\r
+ for label, itsfirst in overlapcheck.iteritems():\r
+ for symbol in itsfirst:\r
+ if symbol in inverse:\r
+ raise ValueError("rule %s is ambiguous; %s is in the"\r
+ " first sets of %s as well as %s" %\r
+ (name, symbol, label, inverse[symbol]))\r
+ inverse[symbol] = label\r
+ self.first[name] = totalset\r
+\r
+ def parse(self):\r
+ dfas = {}\r
+ startsymbol = None\r
+ # MSTART: (NEWLINE | RULE)* ENDMARKER\r
+ while self.type != token.ENDMARKER:\r
+ while self.type == token.NEWLINE:\r
+ self.gettoken()\r
+ # RULE: NAME ':' RHS NEWLINE\r
+ name = self.expect(token.NAME)\r
+ self.expect(token.OP, ":")\r
+ a, z = self.parse_rhs()\r
+ self.expect(token.NEWLINE)\r
+ #self.dump_nfa(name, a, z)\r
+ dfa = self.make_dfa(a, z)\r
+ #self.dump_dfa(name, dfa)\r
+ oldlen = len(dfa)\r
+ self.simplify_dfa(dfa)\r
+ newlen = len(dfa)\r
+ dfas[name] = dfa\r
+ #print name, oldlen, newlen\r
+ if startsymbol is None:\r
+ startsymbol = name\r
+ return dfas, startsymbol\r
+\r
+ def make_dfa(self, start, finish):\r
+ # To turn an NFA into a DFA, we define the states of the DFA\r
+ # to correspond to *sets* of states of the NFA. Then do some\r
+ # state reduction. Let's represent sets as dicts with 1 for\r
+ # values.\r
+ assert isinstance(start, NFAState)\r
+ assert isinstance(finish, NFAState)\r
+ def closure(state):\r
+ base = {}\r
+ addclosure(state, base)\r
+ return base\r
+ def addclosure(state, base):\r
+ assert isinstance(state, NFAState)\r
+ if state in base:\r
+ return\r
+ base[state] = 1\r
+ for label, next in state.arcs:\r
+ if label is None:\r
+ addclosure(next, base)\r
+ states = [DFAState(closure(start), finish)]\r
+ for state in states: # NB states grows while we're iterating\r
+ arcs = {}\r
+ for nfastate in state.nfaset:\r
+ for label, next in nfastate.arcs:\r
+ if label is not None:\r
+ addclosure(next, arcs.setdefault(label, {}))\r
+ for label, nfaset in arcs.iteritems():\r
+ for st in states:\r
+ if st.nfaset == nfaset:\r
+ break\r
+ else:\r
+ st = DFAState(nfaset, finish)\r
+ states.append(st)\r
+ state.addarc(st, label)\r
+ return states # List of DFAState instances; first one is start\r
+\r
+ def dump_nfa(self, name, start, finish):\r
+ print "Dump of NFA for", name\r
+ todo = [start]\r
+ for i, state in enumerate(todo):\r
+ print " State", i, state is finish and "(final)" or ""\r
+ for label, next in state.arcs:\r
+ if next in todo:\r
+ j = todo.index(next)\r
+ else:\r
+ j = len(todo)\r
+ todo.append(next)\r
+ if label is None:\r
+ print " -> %d" % j\r
+ else:\r
+ print " %s -> %d" % (label, j)\r
+\r
+ def dump_dfa(self, name, dfa):\r
+ print "Dump of DFA for", name\r
+ for i, state in enumerate(dfa):\r
+ print " State", i, state.isfinal and "(final)" or ""\r
+ for label, next in state.arcs.iteritems():\r
+ print " %s -> %d" % (label, dfa.index(next))\r
+\r
+ def simplify_dfa(self, dfa):\r
+ # This is not theoretically optimal, but works well enough.\r
+ # Algorithm: repeatedly look for two states that have the same\r
+ # set of arcs (same labels pointing to the same nodes) and\r
+ # unify them, until things stop changing.\r
+\r
+ # dfa is a list of DFAState instances\r
+ changes = True\r
+ while changes:\r
+ changes = False\r
+ for i, state_i in enumerate(dfa):\r
+ for j in range(i+1, len(dfa)):\r
+ state_j = dfa[j]\r
+ if state_i == state_j:\r
+ #print " unify", i, j\r
+ del dfa[j]\r
+ for state in dfa:\r
+ state.unifystate(state_j, state_i)\r
+ changes = True\r
+ break\r
+\r
+ def parse_rhs(self):\r
+ # RHS: ALT ('|' ALT)*\r
+ a, z = self.parse_alt()\r
+ if self.value != "|":\r
+ return a, z\r
+ else:\r
+ aa = NFAState()\r
+ zz = NFAState()\r
+ aa.addarc(a)\r
+ z.addarc(zz)\r
+ while self.value == "|":\r
+ self.gettoken()\r
+ a, z = self.parse_alt()\r
+ aa.addarc(a)\r
+ z.addarc(zz)\r
+ return aa, zz\r
+\r
+ def parse_alt(self):\r
+ # ALT: ITEM+\r
+ a, b = self.parse_item()\r
+ while (self.value in ("(", "[") or\r
+ self.type in (token.NAME, token.STRING)):\r
+ c, d = self.parse_item()\r
+ b.addarc(c)\r
+ b = d\r
+ return a, b\r
+\r
+ def parse_item(self):\r
+ # ITEM: '[' RHS ']' | ATOM ['+' | '*']\r
+ if self.value == "[":\r
+ self.gettoken()\r
+ a, z = self.parse_rhs()\r
+ self.expect(token.OP, "]")\r
+ a.addarc(z)\r
+ return a, z\r
+ else:\r
+ a, z = self.parse_atom()\r
+ value = self.value\r
+ if value not in ("+", "*"):\r
+ return a, z\r
+ self.gettoken()\r
+ z.addarc(a)\r
+ if value == "+":\r
+ return a, z\r
+ else:\r
+ return a, a\r
+\r
+ def parse_atom(self):\r
+ # ATOM: '(' RHS ')' | NAME | STRING\r
+ if self.value == "(":\r
+ self.gettoken()\r
+ a, z = self.parse_rhs()\r
+ self.expect(token.OP, ")")\r
+ return a, z\r
+ elif self.type in (token.NAME, token.STRING):\r
+ a = NFAState()\r
+ z = NFAState()\r
+ a.addarc(z, self.value)\r
+ self.gettoken()\r
+ return a, z\r
+ else:\r
+ self.raise_error("expected (...) or NAME or STRING, got %s/%s",\r
+ self.type, self.value)\r
+\r
+ def expect(self, type, value=None):\r
+ if self.type != type or (value is not None and self.value != value):\r
+ self.raise_error("expected %s/%s, got %s/%s",\r
+ type, value, self.type, self.value)\r
+ value = self.value\r
+ self.gettoken()\r
+ return value\r
+\r
+ def gettoken(self):\r
+ tup = self.generator.next()\r
+ while tup[0] in (tokenize.COMMENT, tokenize.NL):\r
+ tup = self.generator.next()\r
+ self.type, self.value, self.begin, self.end, self.line = tup\r
+ #print token.tok_name[self.type], repr(self.value)\r
+\r
+ def raise_error(self, msg, *args):\r
+ if args:\r
+ try:\r
+ msg = msg % args\r
+ except:\r
+ msg = " ".join([msg] + map(str, args))\r
+ raise SyntaxError(msg, (self.filename, self.end[0],\r
+ self.end[1], self.line))\r
+\r
+class NFAState(object):\r
+\r
+ def __init__(self):\r
+ self.arcs = [] # list of (label, NFAState) pairs\r
+\r
+ def addarc(self, next, label=None):\r
+ assert label is None or isinstance(label, str)\r
+ assert isinstance(next, NFAState)\r
+ self.arcs.append((label, next))\r
+\r
+class DFAState(object):\r
+\r
+ def __init__(self, nfaset, final):\r
+ assert isinstance(nfaset, dict)\r
+ assert isinstance(iter(nfaset).next(), NFAState)\r
+ assert isinstance(final, NFAState)\r
+ self.nfaset = nfaset\r
+ self.isfinal = final in nfaset\r
+ self.arcs = {} # map from label to DFAState\r
+\r
+ def addarc(self, next, label):\r
+ assert isinstance(label, str)\r
+ assert label not in self.arcs\r
+ assert isinstance(next, DFAState)\r
+ self.arcs[label] = next\r
+\r
+ def unifystate(self, old, new):\r
+ for label, next in self.arcs.iteritems():\r
+ if next is old:\r
+ self.arcs[label] = new\r
+\r
+ def __eq__(self, other):\r
+ # Equality test -- ignore the nfaset instance variable\r
+ assert isinstance(other, DFAState)\r
+ if self.isfinal != other.isfinal:\r
+ return False\r
+ # Can't just return self.arcs == other.arcs, because that\r
+ # would invoke this method recursively, with cycles...\r
+ if len(self.arcs) != len(other.arcs):\r
+ return False\r
+ for label, next in self.arcs.iteritems():\r
+ if next is not other.arcs.get(label):\r
+ return False\r
+ return True\r
+\r
+ __hash__ = None # For Py3 compatibility.\r
+\r
+def generate_grammar(filename="Grammar.txt"):\r
+ p = ParserGenerator(filename)\r
+ return p.make_grammar()\r
projects / mirror_edk2.git / blobdiff