path: root/pypy/interpreter/pyparser/metaparser.py

"""
Makes a parser from a grammar source.

Inspired by Guido van Rossum's pgen2.
"""

import StringIO
import tokenize
import token

from pypy.interpreter.pyparser import parser


class PgenError(Exception):

    def __init__(self, msg, location=None):
        Exception.__init__(self, msg)
        self.location = location


class NFA(object):

    def __init__(self):
        self.arcs = []

    def arc(self, to_state, label=None):
        self.arcs.append((label, to_state))

    def find_unlabeled_states(self, into):
        if self in into:
            return
        into.add(self)
        for label, state in self.arcs:
            if label is None:
                state.find_unlabeled_states(into)


class DFA(object):

    def __init__(self, nfa_set, final_state):
        self.nfas = nfa_set
        self.is_final = final_state in nfa_set
        self.arcs = {}

    def arc(self, next, label):
        self.arcs[label] = next

    def unify_state(self, old, new):
        for label, state in self.arcs.iteritems():
            if state is old:
                self.arcs[label] = new

    def __repr__(self):
        return "<DFA arcs=%r>" % self.arcs

    def __eq__(self, other):
        if not isinstance(other, DFA):
            # This shouldn't really happen.
            return NotImplemented
        if other.is_final != self.is_final:
            return False
        if len(self.arcs) != len(other.arcs):
            return False
        for label, state in self.arcs.iteritems():
            try:
                other_state = other.arcs[label]
            except KeyError:
                return False
            else:
                if other_state is not state:
                    return False
        return True


def nfa_to_dfa(start, end):
    """Convert an NFA to a DFA(s)

    Each DFA is initially a set of NFA states without labels.  We start with the
    DFA for the start NFA.  Then we add labeled arcs to it pointing to another
    set of NFAs (the next state).  Finally, we do the same thing to every DFA
    that is found and return the list of states.
    """
    base_nfas = set()
    start.find_unlabeled_states(base_nfas)
    state_stack = [DFA(base_nfas, end)]
    for state in state_stack:
        arcs = {}
        for nfa in state.nfas:
            for label, sub_nfa in nfa.arcs:
                if label is not None:
                    sub_nfa.find_unlabeled_states(arcs.setdefault(label, set()))
        for label, nfa_set in arcs.iteritems():
            for st in state_stack:
                if st.nfas == nfa_set:
                    break
            else:
                st = DFA(nfa_set, end)
                state_stack.append(st)
            state.arc(st, label)
    return state_stack

def simplify_dfa(dfa):
    changed = True
    while changed:
        changed = False
        for i, state in enumerate(dfa):
            for j in xrange(i + 1, len(dfa)):
                other_state = dfa[j]
                if state == other_state:
                    del dfa[j]
                    for sub_state in dfa:
                        sub_state.unify_state(other_state, state)
                    changed = True
                    break


class ParserGenerator(object):
    """NOT_RPYTHON"""

    def __init__(self, grammar_source):
        self.start_symbol = None
        self.dfas = {}
        stream = StringIO.StringIO(grammar_source)
        self.token_stream = tokenize.generate_tokens(stream.readline)
        self.parse()
        self.first = {}
        self.add_first_sets()

    def build_grammar(self, grammar_cls):
        gram = grammar_cls()
        gram.start = self.start_symbol
        names = self.dfas.keys()
        names.sort()
        names.remove(self.start_symbol)
        names.insert(0, self.start_symbol)
        # First, build symbol and id mappings.
        for name in names:
            i = 256 + len(gram.symbol_ids)
            gram.symbol_ids[name] = i
            gram.symbol_names[i] = name
        # Then, iterate through again and finalize labels.
        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(gram, label), dfa.index(next)))
                states.append((arcs, state.is_final))
            gram.dfas.append((states, self.make_first(gram, name)))
            assert len(gram.dfas) - 1 == gram.symbol_ids[name] - 256
        gram.start = gram.symbol_ids[self.start_symbol]
        return gram

    def make_label(self, gram, label):
        label_index = len(gram.labels)
        if label[0].isalpha():
            # Either a symbol or a token.
            if label in gram.symbol_ids:
                if label in gram.symbol_to_label:
                    return gram.symbol_to_label[label]
                else:
                    gram.labels.append(gram.symbol_ids[label])
                    gram.symbol_to_label[label] = label_index
                    return label_index
            elif label.isupper():
                token_index = gram.TOKENS[label]
                if token_index in gram.token_ids:
                    return gram.token_ids[token_index]
                else:
                    gram.labels.append(token_index)
                    gram.token_ids[token_index] = label_index
                    return label_index
            else:
                # Probably a rule without a definition.
                raise PgenError("no such rule: %r" % (label,))
        else:
            # A keyword or operator.
            value = label.strip("\"'")
            if value[0].isalpha():
                if value in gram.keyword_ids:
                    return gram.keyword_ids[value]
                else:
                    gram.labels.append(gram.KEYWORD_TOKEN)
                    gram.keyword_ids[value] = label_index
                    return label_index
            else:
                try:
                    token_index = gram.OPERATOR_MAP[value]
                except KeyError:
                    raise PgenError("no such operator: %r" % (value,))
                if token_index in gram.token_ids:
                    return gram.token_ids[token_index]
                else:
                    gram.labels.append(token_index)
                    gram.token_ids[token_index] = label_index
                    return label_index

    def make_first(self, gram, name):
        original_firsts = self.first[name]
        firsts = dict()
        for label in original_firsts:
            firsts[self.make_label(gram, label)] = None
        return firsts

    def add_first_sets(self):
        for name, dfa in self.dfas.iteritems():
            if name not in self.first:
                self.get_first(name, dfa)

    def get_first(self, name, dfa):
        self.first[name] = None
        state = dfa[0]
        all_labels = set()
        overlap_check = {}
        for label, sub_state in state.arcs.iteritems():
            if label in self.dfas:
                if label in self.first:
                    new_labels = self.first[label]
                    if new_labels is None:
                        raise PgenError("recursion in rule: %r" % (name,))
                else:
                    new_labels = self.get_first(label, self.dfas[label])
                all_labels.update(new_labels)
                overlap_check[label] = new_labels
            else:
                all_labels.add(label)
                overlap_check[label] = set((label,))
        inverse = {}
        for label, their_first in overlap_check.iteritems():
            for sub_label in their_first:
                if sub_label in inverse:
                    raise PgenError("ambiguous symbol with label %s"
                                    % (label,))
                inverse[sub_label] = label
        self.first[name] = all_labels
        return all_labels

    def expect(self, token_type, value=None):
        if token_type != self.type:
            expected = token.tok_name[token_type]
            got = token.tok_name[self.type]
            raise PgenError("expected token %s but got %s" % (expected, got),
                            self.location)
        current_value = self.value
        if value is not None:
            if value != current_value:
                msg = "expected %r but got %r" % (value, current_value)
                raise PgenError(msg,self.location)
        self.advance_token()
        return current_value

    def test_token(self, token_type, value):
        if self.type == token_type and self.value == value:
            return True
        return False

    def advance_token(self):
        data = self.token_stream.next()
        # Ignore comments and non-logical newlines.
        while data[0] in (tokenize.NL, tokenize.COMMENT):
            data = self.token_stream.next()
        self.type, self.value = data[:2]
        self.location = data[2:]

    def parse(self):
        self.advance_token()
        while self.type != token.ENDMARKER:
            # Skip over whitespace.
            while self.type == token.NEWLINE:
                self.advance_token()
            name, start_state, end_state = self.parse_rule()
            dfa = nfa_to_dfa(start_state, end_state)
            simplify_dfa(dfa)
            self.dfas[name] = dfa
            if self.start_symbol is None:
                self.start_symbol = name

    def parse_rule(self):
        # RULE: NAME ':' ALTERNATIVES
        name = self.expect(token.NAME)
        self.expect(token.OP, ":")
        start_state, end_state = self.parse_alternatives()
        self.expect(token.NEWLINE)
        return name, start_state, end_state

    def parse_alternatives(self):
        # ALTERNATIVES: ITEMS ('|' ITEMS)*
        first_state, end_state = self.parse_items()
        if self.test_token(token.OP, "|"):
            # Link all alternatives into a enclosing set of states.
            enclosing_start_state = NFA()
            enclosing_end_state = NFA()
            enclosing_start_state.arc(first_state)
            end_state.arc(enclosing_end_state)
            while self.test_token(token.OP, "|"):
                self.advance_token()
                sub_start_state, sub_end_state = self.parse_items()
                enclosing_start_state.arc(sub_start_state)
                sub_end_state.arc(enclosing_end_state)
            first_state = enclosing_start_state
            end_state = enclosing_end_state
        return first_state, end_state

    def parse_items(self):
        # ITEMS: ITEM+
        first_state, end_state = self.parse_item()
        while self.type in (token.STRING, token.NAME) or \
                           self.test_token(token.OP, "(") or \
                           self.test_token(token.OP, "["):
            sub_first_state, new_end_state = self.parse_item()
            end_state.arc(sub_first_state)
            end_state = new_end_state
        return first_state, end_state

    def parse_item(self):
        # ITEM: '[' ALTERNATIVES ']' | ATOM ['+' | '*']
        if self.test_token(token.OP, "["):
            self.advance_token()
            start_state, end_state = self.parse_alternatives()
            self.expect(token.OP, "]")
            # Bypass the rule if this is optional.
            start_state.arc(end_state)
            return start_state, end_state
        else:
            atom_state, next_state = self.parse_atom()
            # Check for a repeater.
            if self.type == token.OP and self.value in ("+", "*"):
                next_state.arc(atom_state)
                repeat = self.value
                self.advance_token()
                if repeat == "*":
                    # Optionally repeated
                    return atom_state, atom_state
                else:
                    # Required
                    return atom_state, next_state
            else:
                return atom_state, next_state

    def parse_atom(self):
        # ATOM: '(' ALTERNATIVES ')' | NAME | STRING
        if self.test_token(token.OP, "("):
            self.advance_token()
            rule = self.parse_alternatives()
            self.expect(token.OP, ")")
            return rule
        elif self.type in (token.NAME, token.STRING):
            atom_state = NFA()
            next_state = NFA()
            atom_state.arc(next_state, self.value)
            self.advance_token()
            return atom_state, next_state
        else:
            invalid = token.tok_name[self.type]
            raise PgenError("unexpected token: %s" % (invalid,),
                            self.location)