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