ParserCombinators.py

#!/usr/bin/python3

"""ParserCombinators.py - parser combinators for left-recursive grammers

Copyright 2016  by Eckhart Arnold

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

    http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
implied.  See the License for the specific language governing
permissions and limitations under the License.


Module parser_combinators contains a number of classes that together
make up parser combinators for left-recursive grammers. For each
element of the extended Backus-Naur-Form as well as for a regular
expression token a class is defined. The set of classes can be used to
define a parser for (ambiguous) left-recursive grammers.


References and Acknowledgements:

Dominikus Herzberg: Objekt-orientierte Parser-Kombinatoren in Python,
Blog-Post, September, 18th 2008 on denkspuren. gedanken, ideen,
anregungen und links rund um informatik-themen, URL:
http://denkspuren.blogspot.de/2008/09/objekt-orientierte-parser-kombinatoren.html

Dominikus Herzberg: Eine einfache Grammatik für LaTeX, Blog-Post,
September, 18th 2008 on denkspuren. gedanken, ideen, anregungen und
links rund um informatik-themen, URL:
http://denkspuren.blogspot.de/2008/09/eine-einfache-grammatik-fr-latex.html

Dominikus Herzberg: Uniform Syntax, Blog-Post, February, 27th 2007 on
denkspuren. gedanken, ideen, anregungen und links rund um
informatik-themen, URL:
http://denkspuren.blogspot.de/2007/02/uniform-syntax.html

Richard A. Frost, Rahmatullah Hafiz and Paul Callaghan: Parser
Combinators for Ambiguous Left-Recursive Grammars, in: P. Hudak and
D.S. Warren (Eds.): PADL 2008, LNCS 4902, pp. 167–181, Springer-Verlag
Berlin Heidelberg 2008.

Juancarlo Añez: grako, a PEG parser generator in Python,
https://bitbucket.org/apalala/grako

"""

# TODO: Replace copy.deepcopy() call in GrammarBase class by custom copy()-methods in the Parser classes. Is that really better?


import collections
import copy
import enum
from functools import partial
import hashlib
import keyword
import os
from typing import NamedTuple

# try:
#     import regex as re
# except ImportError:
#     import re
import re       # as of now use `re` - even hough `regex` appears to be better
import sys


__version__ = '0.5.2' + '_dev' + str(os.stat(__file__).st_mtime)


DEBUG = "DEBUG"


def DEBUG_DIR():
    global DEBUG
    dirname = ""
    if DEBUG:
        if os.path.exists(DEBUG):
            dirname = DEBUG if os.path.isdir(DEBUG) else ""
        else:
            os.mkdir(DEBUG)
            dirname = DEBUG
    return dirname


def DEBUG_FILE_NAME(grammar_base):
    name = grammar_base.__class__.__name__
    return name[:-7] if name.endswith('Grammar') else name


########################################################################
#
# Scanner / Preprocessor support
#
########################################################################


RX_SCANNER_TOKEN = re.compile('\w+')
BEGIN_SCANNER_TOKEN = '\x1b'
END_SCANNER_TOKEN = '\x1c'


def make_token(token, argument=''):
    """
    Turns the ``token`` and ``argument`` into a special token that
    will be caught by the `ScannerToken`-parser.

    Args:
        token (str): The token to be wrapped into a scanner token
        argument (str): The optional argument string added to the token

    Returns (str):
        The scanner token, starting with the `BEGIN_SCANNER_TOKEN`-
        character and ending with the `END_SCANNER_TOKEN`-character.
    """
    assert RX_SCANNER_TOKEN.match(token)
    assert argument.find(BEGIN_SCANNER_TOKEN) < 0
    assert argument.find(END_SCANNER_TOKEN) < 0

    return BEGIN_SCANNER_TOKEN + token + argument + END_SCANNER_TOKEN


nil_scanner = lambda text: text



########################################################################
#
# Parser tree
#
########################################################################


def line_col(text, pos):
    """
    Returns the position within a text as (line, column)-tuple.

    Args:
        text (str):  The text for which the line and column of the
                position ``pos`` shall be returned
        pos (int):  The position in the text starting with 0, e.g. 2536
                means the 2537th character. Must be lower than the
                text's length
    Returns (tuple):
        The line and column of the given position
    """
    assert pos < len(text)
    line = text.count("\n", 0, pos) + 1
    column = pos - text.rfind("\n", 0, pos)
    return line, column


class ZombieParser:
    """Serves as a substitute for a Parser instance. Required by
    `Node`-objects, for example. The ZOMBIE_PARSER has a name and can
    be called, but it never matches.
    """
    alive = False
    def __init__(self):
        assert not self.__class__.alive, "There can be only one!"
        assert self.__class__ == ZombieParser, "No derivatives, please!"
        self.name = "ZOMBIE"
        self.__class__.alive = True

    def __str__(self):
        return self.name

    def __call__(self, text):
        """Better call Saul ;-)"""
        return None, text


ZOMBIE_PARSER = ZombieParser()


class Error(NamedTuple):
    pos: int
    msg: str


class Node:
    """
    Represents a node in the concrete or abstract syntax tree.

    Attributes:
        tag (str):  The name of the node, which is either its parser's
                name or, if that is empty, the parser's class name
        result (str or tuple):  The result of the parser which
                generated this node, which can be either a string or a
                tuple of child nodes.
        children (tuple):  The tuple of child nodes or an empty tuple
                if there are no child nodes. READ ONLY!
        parser (Parser):  The parser which generated this node.
        errors (list):  A list of parser- or compiler-errors:
                tuple(position, string) attached to this node
        len (int):  The full length of the node's string result if the
                node is a leaf node or, otherwise, the concatenated
                string result's of its descendants. The figure always
                represents the length before AST-transformation and
                will never change through AST-transformation.
                READ ONLY!
        pos (int):  the position of the node within the parsed text.

                The value of ``pos`` is zero by default and is will be
                updated if the node or any of its parents is attached
                to a new parent.

                From the point of view of a client, this value should
                be considered READ ONLY. At any rate, it should never
                be reassigned only during parsing stage and never
                during or after AST-transformation.
    """

    def __init__(self, parser, result):
        """
        Initializes the ``Node``-object.

        Args:
            parser (Parser):  The `Parser`-instance which generated
                    this node
            result (Union):  The parsing result, which can either be a
                    string or a tuple of child nodes
        """
        self.result = result
        self.parser = parser or ZOMBIE_PARSER
        self._errors = []
        self.error_flag = any(r.error_flag for r in self.result) if self.children else False
        self._len = len(self.result) if not self.children else \
            sum(child._len for child in self.result)
        self.pos = 0

    def __str__(self):
        if self.children:
            return "".join([str(child) for child in self.result])
        return str(self.result)

    @property
    def tag(self):
        return self.parser.name or self.parser.__class__.__name__

    @property
    def result(self):
        return self._result

    @result.setter
    def result(self, result):
        assert ((isinstance(result, tuple) and all(isinstance(child, Node) for child in result))
                or isinstance(result, Node)
                or isinstance(result, str)), str(result)
        self._result = (result,) if isinstance(result, Node) else result or ''
        self._children = self._result if isinstance(self._result, tuple) else ()

    @property
    def children(self):
        return self._children

    @property
    def len(self):
        return self._len

    @property
    def pos(self):
        return self._pos

    @pos.setter
    def pos(self, pos):
        self._pos = pos
        offset = 0
        for child in self.children:
            child.pos = pos + offset
            offset += child.len

    @property
    def errors(self):
        return [Error(self.pos, err) for err in self._errors]

    def _tree_repr(self, tab, openF, closeF, dataF=lambda s: s):
        """
        Generates a tree representation of this node and its children
        in string from.

        This could be an XML-representation or a lisp-like
        S-expression. Exactly which form the tree representation takes is
        defined by the parameters of the function.

        Args:
            tab (str): The indentation string, e.g. '\t' or '    '
            openF (Node->str):  A function that returns an opening
                    string (e.g. an XML-tag) for a given node
            closeF (Node->str): A function that returns a closeF string
                    (e.g. an XML-tag) for a given node.
            dataF (str->str): A function that filters the data string
                    before printing, e.g. to add quotation marks
        Returns (str):
            A string that contains a (serialized) tree representation of the
            node and its children.
        """
        head = openF(self)
        tail = closeF(self)

        if not self.result:
            return head + tail

        head = head + '\n'        # place the head, tail and content
        tail = '\n' + tail        # of the node on different lines

        if self.children:
            content = []
            for child in self.result:
                subtree = child._tree_repr(tab, openF, closeF, dataF).split('\n')
                content.append('\n'.join((tab + s) for s in subtree))
            return head + '\n'.join(content) + tail

        return head + '\n'.join([tab + dataF(s)
                                 for s in str(self.result).split('\n')]) + tail

    def as_sexpr(self, src=None):
        """
        Returns content as S-expression, i.e. in lisp-like form.

        Args:
            src (str or None):  The source text or `None`. In case the
                    source text is given the position of the element
                    in the text will be reported as line and column.
        """
        def opening(node):
            s = '(' + node.tag
            # s += " '(pos %i)" % node.pos
            if src:
                s += " '(pos %i  %i %i)" % (node.pos, *line_col(src, node.pos))
            if node.errors:
                s += " '(err '(%s))" % ' '.join(str(err).replace('"', r'\"')
                                                for err in node.errors)
            return s
        def pretty(s):
            return '"%s"' % s if s.find('"') < 0 \
                else "'%s'" % s if s.find("'") < 0 \
                else '"%s"' % s.replace('"', r'\"')
        return self._tree_repr('    ', opening, lambda node: ')', pretty)

    def as_xml(self, src=None):
        """
        Returns content as XML-tree.

        Args:
            src (str):  The source text or `None`. In case the source
                    text is given the position will also be reported
                    as line and column.
        """

        def opening(node):
            s = '<' + node.tag
            # s += ' pos="%i"' % node.pos
            if src:
                s += ' line="%i" col="%i"' % line_col(src, node.pos)
            if node.errors:
                s += ' err="%s"' % ''.join(str(err).replace('"', r'\"') for err in node.errors)
            s += ">"
            return s

        def closing(node):
            s = '</' + node.tag + '>'
            return s

        return self._tree_repr('    ', opening, closing)

    def add_error(self, error_str):
        self._errors.append(error_str)
        self.error_flag = True
        return self

    def collect_errors(self, clear_errors=False):
        """
        Returns all errors of this node or any child node in the form
        of a set of tuples (position, error_message), where position
        is always relative to this node.
        """
        if self.error_flag:
            errors = self.errors
            if clear_errors:
                self._errors = []
                self.error_flag = False
            if self.children:
                for child in self.result:
                    errors.extend(child.collect_errors(clear_errors))
            return errors
        return []

    def navigate(self, path):
        """EXPERIMENTAL! NOT YET TESTED!!!
        Returns the first descendant element matched by `path`, e.g.
        'd/s' returns 'l' from (d (s l)(e (r x1) (r x2))
        'e/r' returns 'x2'
        'e'   returns (r x1)(r x2)

        Args:
            path (str): The path of the object, e.g. 'a/b/c'

        Returns:
            The object at the path, either a string or a Node or
            `None`, if the path did not match.
        """
        pl = path.strip('')
        assert pl[0] != '/', 'Path must noch start with "/"!'
        nd = self
        for p in pl:
            if isinstance(nd.result, str):
                return p if (p == nd.result) and (p == pl[-1]) else None
            for child in nd.result:
                if str(child) == p:
                    nd = child
                    break
            else:
                return None
        return child


def error_messages(text, errors):
    """
    Converts the list of ``errors`` collected from the root node of the
    parse tree of `text` into a human readable (and IDE or editor
    parsable text) with line an column numbers. Error messages are
    separated by an empty line.
    """
    return "\n\n".join("line: %i, column: %i, error: %s" %
                       (*line_col(text, err.pos), err.msg)
                       for err in sorted(list(errors)))
    # return "\n\n".join("line: %i, column: %i, error: %s" %
    #                    (*line_col(text, err[0]), " and ".join(err[1]))
    #                    for err in sorted(list(errors)))


# lambda compact_sexpr s : re.sub('\s(?=\))', '', re.sub('\s+', ' ', s)).strip()



########################################################################
#
# Abstract syntax tree support
#
########################################################################


def DEBUG_DUMP_SYNTAX_TREE(grammar_base, syntax_tree, ext):
    global DEBUG
    if DEBUG:
        st_file_name = DEBUG_FILE_NAME(grammar_base) + ext
        with open(os.path.join(DEBUG_DIR(), st_file_name), "w",  encoding="utf-8") as f:
            f.write(syntax_tree.as_sexpr())


def expand_table(compact_table):
    """Expands a table by separating keywords that are tuples or strings
    containing comma separated words into single keyword entries with
    the same values. Returns the expanded table.
    Example:
    expand_table({"a, b": 1, "b": 1, ('d','e','f'):5, "c":3}) yields
    {'a': 1, 'b': 1, 'c': 3, 'd': 5, 'e': 5, 'f': 5}
    """
    expanded_table = {}
    keys = list(compact_table.keys())
    for key in keys:
        value = compact_table[key]
        if isinstance(key, str):
            parts = (s.strip() for s in key.split(','))
        else:
            assert isinstance(key, collections.abc.Iterable)
            parts = key
        for p in parts:
            expanded_table[p] = value
    return expanded_table


def ASTTransform(node, transtable):
    """Transforms the parse tree starting with the given `node` into an
    abstract syntax tree by calling transformation functions registered in a
    transformation table.

    Args:
        node (Node): The root node of the parse tree (or sub-tree) to be
                transformed into the abstract syntax tree.
        transtable (dict): A dictionary that assigns a transformation
                transformation functions to parser name strings.
    """
    # normalize transformation entries by turning single transformations
    # into lists with a single item
    table = {name: transformation
             if isinstance(transformation, collections.abc.Sequence)
             else [transformation]
             for name, transformation in list(transtable.items())}
    table = expand_table(table)

    def recursive_ASTTransform(node):
        if node.children:
            for child in node.result:
                recursive_ASTTransform(child)
        transformation = table.get(node.parser.name,
                            table.get('~', [])) + table.get('*', [])
        for transform in transformation:
            transform(node)

    recursive_ASTTransform(node)


# def preserve_errors(transformation):
#     """Wrapper that moves errors of child nodes that have been removed
#     after the application of function ``transformation()`` to the root
#     node. As an optimization, ``transformation()`` will only be called
#     if its ``node``-argument (i.e. the root-node) has children at all.
#     """
#     # requires nd.collect_errors() to return a set
#     @functools.wraps(transformation)
#     def preserve_errors_wrapper(*args, **kwds):
#         nd = kwds['node'] if 'node' in kwds else args[0]
#         if nd.children:
#             errors = nd.collect_errors()
#             transformation(*args, **kwds)
#             for err in errors - nd.collect_errors():
#                 nd.add_error(err[1], err[0])
#     return preserve_errors_wrapper


def no_transformation(node):
    pass


# ------------------------------------------------
#
# rearranging transformations:
#     - tree may be rearranged (flattened)
#     - order is preserved
#     - all leaves are kept
#
# ------------------------------------------------


def replace_by_single_child(node):
    """Remove single branch node, replacing it by its immediate descendant.
    (In case the descendant's name is empty (i.e. anonymous) the
    name of this node's parser is kept.)
    """
    if node.children and len(node.result) == 1:
        if not node.result[0].parser.name:
            node.result[0].parser.name = node.parser.name
        node.parser = node.result[0].parser
        node._errors.extend(node.result[0].errors)
        node.result = node.result[0].result


def reduce_single_child(node):
    """Reduce a single branch node, by transferring the result of its
    immediate descendant to this node, but keeping this node's parser entry.
    """
    if node.children and len(node.result) == 1:
        node._errors.extend(node.result[0].errors)
        node.result = node.result[0].result


# ------------------------------------------------
#
# destructive transformations:
#     - tree may be rearranged (flattened),
#     - order is preserved
#     - but (irrelevant) leaves may be dropped
#     - errors of dropped leaves will be lost
#
# ------------------------------------------------


def is_whitespace(node):
    return not node.result or (isinstance(node.result, str) and not node.result.strip())


def is_comment(node):
    return node.parser.name == WHITESPACE_KEYWORD


def is_scanner_token(node):
    return isinstance(node.parser, ScannerToken)


def is_expendable(node):
    return is_whitespace(node) or is_comment(node) or is_scanner_token(node)


def remove_children_if(node, condition):
    """Removes all nodes from the result field if the function `condition` evaluates
    to `True`."""
    if node.children:
        node.result = tuple(r for r in node.result if not condition(r))


remove_whitespace = partial(remove_children_if, condition=is_whitespace)
remove_comments = partial(remove_children_if, condition=is_comment)
remove_scanner_tokens = partial(remove_children_if, condition=is_scanner_token)
remove_expendables = partial(remove_children_if, condition=is_expendable)


def flatten(node):
    """Recursively flattens all unnamed sub-nodes, in case there is more
    than one sub-node present. Flattening means that
    wherever a node has child nodes, the child nodes are inserted in place
    of the node. In other words, all leaves of this node and its child nodes
    are collected in-order as direct children of this node.
    This is meant to achieve the following structural transformation:
    X (+ Y + Z)  ->   X + Y + Z
    """
    if node.children:
        new_result = []
        for child in node.children:
            if not child.parser.name and child.children:
                assert child.children, node.as_sexpr()
                flatten(child)
                new_result.extend(child.result)
            else:
                new_result.append(child)
        node.result = tuple(new_result)


def remove_tokens(node, tokens=set()):
    """Reomoves any among a particular set of tokens from the immediate
    descendants of a node. If ``tokens`` is the empty set, all tokens
    are removed.
    """
    if node.children:
        if tokens:
            node.result = tuple(child for child in node.children
                                if child.parser.name != TOKEN_KEYWORD or
                                child.result not in tokens)
        else:
            node.result = tuple(child for child in node.children
                                if child.parser.name != TOKEN_KEYWORD)


def remove_enclosing_delimiters(node):
    """Removes the enclosing delimiters from a structure (e.g. quotation marks
    from a literal or braces from a group).
    """
    if len(node.children) >= 3:
        assert isinstance(node.children[0].result, str) and \
               isinstance(node.children[-1].result, str), node.as_sexpr()
        node.result = node.result[1:-1]


AST_SYMBOLS = {'replace_by_single_child', 'reduce_single_child',
               'no_transformation', 'remove_children_if', 'is_whitespace',
               'is_comment', 'is_scanner_token', 'is_expendable',
               'remove_whitespace', 'remove_comments',
               'remove_scanner_tokens', 'remove_expendables', 'flatten',
               'remove_tokens', 'remove_enclosing_delimiters',
               'TOKEN_KEYWORD', 'WHITESPACE_KEYWORD', 'partial'}



########################################################################
#
# Parser base classes
#
########################################################################


LEFT_RECURSION_DEPTH = 10   # because of pythons recursion depth limit, this
                            # value ought not to be set too high
MAX_DROPOUTS = 25   # stop trying to recover parsing after so many errors

WHITESPACE_KEYWORD = 'wsp__'
TOKEN_KEYWORD = 'token__'


class HistoryRecord:
    __slots__ = ('call_stack', 'node', 'remaining')

    MATCH = "MATCH"
    ERROR = "ERROR"
    FAIL = "FAIL"

    def __init__(self, call_stack, node, remaining):
        self.call_stack = call_stack
        self.node = node
        self.remaining = remaining

    @property
    def stack(self):
        return "->".join(str(parser) for parser in self.call_stack)

    @property
    def status(self):
        return self.FAIL if self.node is None else self.ERROR if self.node._errors else self.MATCH

    @property
    def extent(self):
        return ((-self.remaining - self.node.len, -self.remaining) if self.node
                else (-self.remaining, None))


def DEBUG_DUMP_PARSING_HISTORY(grammar_base, document):
    def prepare_line(record):
        excerpt = document.__getitem__(slice(*record.extent))[:25].replace('\n','\\n')
        excerpt = "'%s'" % excerpt if len(excerpt) < 25 else "'%s...'" % excerpt
        return (record.stack, record.status, excerpt)

    def write_log(history, log_name):
        path = os.path.join(DEBUG_DIR(), DEBUG_FILE_NAME(grammar_base) + log_name + "_parser.log")
        if history:
            with open(path, "w", encoding="utf-8") as f:
                f.write("\n".join(history))
        elif os.path.exists(path):
            os.remove(path)

    global DEBUG
    if DEBUG:
        full_history, match_history, errors_only = [], [], []
        for record in grammar_base.history:
            line = ";  ".join(prepare_line(record))
            full_history.append(line)
            if record.node and record.node.parser.name != WHITESPACE_KEYWORD:
                match_history.append(line)
                if record.node.errors:
                    errors_only.append(line)
        write_log(full_history, '_full')
        write_log(match_history, '_match')
        write_log(errors_only, '_errors')
        # hist = [";  ".join(prepare_line(r)) for r in grammar_base.history]
        # lines = [prepare_line(r) for r in grammar_base.history]
        # n = max(len(line[0]) for line in lines)
        # hist = ["    ".join((l[0] + ' ' * (n - len(l[0])), l[1], l[2])) for l in lines]


def add_parser_guard(parser_func):
    def guarded_call(parser, text):
        try:
            location = len(text)
            # if location has already been visited by the current parser,
            # return saved result
            if location in parser.visited:
                return parser.visited[location]
            # break left recursion at the maximum allowed depth
            if parser.recursion_counter.setdefault(location, 0) > LEFT_RECURSION_DEPTH:
                return None, text

            parser.recursion_counter[location] += 1
            grammar = parser.grammar

            if grammar.track_history:
                grammar.call_stack.append(parser)
                grammar.moving_forward = True

            # run original __call__ method
            node, rest = parser_func(parser, text)

            if grammar.track_history:
                if grammar.moving_forward:  # and result[0] == None
                    grammar.moving_forward = False
                    record = HistoryRecord(grammar.call_stack.copy(), node, len(rest))
                    grammar.history.append(record)
                grammar.call_stack.pop()

            if node is not None:
                # in case of a recursive call saves the result of the first
                # (or left-most) call that matches
                parser.visited[location] = (node, rest)
                grammar.last_node = node
            elif location in parser.visited:
                # if parser did non match but a saved result exits, assume
                # left recursion and use the saved result
                node, rest = parser.visited[location]

            parser.recursion_counter[location] -= 1

        except RecursionError:
            node = Node(None, text[:min(10, max(1, text.find("\n")))] + " ...")
            node.add_error("maximum recursion depth of parser reached; "
                           "potentially due to too many errors!")
            node.error_flag = True
            rest = ''

        return node, rest

    return guarded_call


class ParserMetaClass(type):
    def __init__(cls, name, bases, attrs):
        # The following condition is necessary for classes that don't override
        # the __call__() method, because in these cases the non-overridden
        # __call__()-method would be substituted a second time!
        guarded_parser_call = add_parser_guard(cls.__call__)
        if cls.__call__.__code__ != guarded_parser_call.__code__:
            cls.__call__ = guarded_parser_call
        super(ParserMetaClass, cls).__init__(name, bases, attrs)


def sane_parser_name(name):
    """Checks whether given name is an acceptable parser name. Parser names
    must not be preceeded or succeeded by a double underscore '__'!
    """
    return name and name[:2] != '__' and name[-2:] != '__'


class Parser(metaclass=ParserMetaClass):
    def __init__(self, name=None):
        assert name is None or isinstance(name, str), str(name)
        self.name = name or ''
        self.grammar = None          # center for global variables etc.
        self.reset()

    def reset(self):
        self.visited = dict()
        self.recursion_counter = dict()
        self.cycle_detection = set()

    def __call__(self, text):
        return None, text               # default behaviour: don't match

    def __str__(self):
        return self.name or self.__class__.__name__

    @property
    def grammar(self):
        return self._grammar

    @grammar.setter
    def grammar(self, grammar_base):
        self._grammar = grammar_base
        self._grammar_assigned_notifier()

    def _grammar_assigned_notifier(self):
        pass

    def apply(self, func):
        """Applies function `func(parser)` recursively to this parser and all
        descendendants of the tree of parsers. The same function can never
        be applied twice between calls of the ``reset()``-method!
        """
        if func in self.cycle_detection:
            return False
        else:
            self.cycle_detection.add(func)
            func(self)
            return True


class GrammarBase:
    root__ = None   # should be overwritten by grammar subclass

    @classmethod
    def _assign_parser_names(cls):
        """Initializes the `parser.name` fields of those
        Parser objects that are directly assigned to a class field with
        the field's name, e.g.
            class Grammar(GrammarBase):
                ...
                symbol = RE('(?!\\d)\\w+')
        After the call of this method symbol.name == "symbol"
        holds. Names assigned via the `name`-parameter of the
        constructor will not be overwritten.
        """
        if cls.parser_initialization__ == "done":
            return
        cdict = cls.__dict__
        for entry, parser in cdict.items():
            if isinstance(parser, Parser):
                if not parser.name or parser.name == TOKEN_KEYWORD:
                    parser.name = entry
                if (isinstance(parser, Forward) and (not parser.parser.name
                    or parser.parser.name == TOKEN_KEYWORD)):
                    parser.parser.name = entry
        cls.parser_initialization__ = "done"

    def __init__(self):
        self.all_parsers = set()
        self.dirty_flag = False
        self.track_history = DEBUG
        self._reset()
        self._assign_parser_names()
        self.root__ = copy.deepcopy(self.__class__.root__)
        if self.wspL__:
            self.wsp_left_parser__ = RegExp(self.wspL__, WHITESPACE_KEYWORD)
            self.wsp_left_parser__.grammar = self
        else:
            self.wsp_left_parser__ = ZOMBIE_PARSER
        if self.wspR__:
            self.wsp_right_parser__ = RegExp(self.wspR__, WHITESPACE_KEYWORD)
            self.wsp_right_parser__.grammar = self
        else:
            self.wsp_right_parser__ = ZOMBIE_PARSER
        self.root__.apply(self._add_parser)

    def _reset(self):
        self.variables = dict()                 # support for Pop and Retrieve operators
        self.last_node = None
        self.call_stack = []                    # support for call stack tracing
        self.history = []                       # snapshots of call stacks
        self.moving_forward = True              # also needed for call stack tracing

    def _add_parser(self, parser):
        """Adds the copy of the classes parser object to this
        particular instance of GrammarBase.
        """
        setattr(self, parser.name, parser)
        self.all_parsers.add(parser)
        parser.grammar = self

    def parse(self, document):
        """Parses a document with with parser-combinators.

        Args:
            document (str): The source text to be parsed.
        Returns:
            Node: The root node ot the parse tree.
        """
        if self.root__ is None:
            raise NotImplementedError()
        if self.dirty_flag:
            self._reset()
            for parser in self.all_parsers:
                parser.reset()
        else:
            self.dirty_flag = True
        parser = self.root__
        result = ""
        stitches = []
        rest = document
        while rest and len(stitches) < MAX_DROPOUTS:
            result, rest = parser(rest)
            if rest:
                fwd = rest.find("\n") + 1 or len(rest)
                skip, rest = rest[:fwd], rest[fwd:]
                if result is None:
                    error_msg = "Parser did not match! Invalid source file?"
                else:
                    stitches.append(result)
                    error_msg = "Parser stopped before end" + \
                                ("! trying to recover..."
                                 if len(stitches) < MAX_DROPOUTS
                                 else " too often! Terminating parser.")
                stitches.append(Node(None, skip))
                stitches[-1].add_error(error_msg)
        if stitches:
            if result and stitches[-1] != result:
                stitches.append(result)
            if rest:
                stitches.append(Node(None, rest))
        return result if not stitches else Node(None, tuple(stitches))



########################################################################
#
# Token and Regular Expression parser classes (i.e. leaf classes)
#
########################################################################


class ScannerToken(Parser):
    def __init__(self, scanner_token):
        assert isinstance(scanner_token, str) and scanner_token and \
               scanner_token.isupper()
        assert RX_SCANNER_TOKEN.match(scanner_token)
        super(ScannerToken, self).__init__(scanner_token)

    def __call__(self, text):
        if text[0:1] == BEGIN_SCANNER_TOKEN:
            end = text.find(END_SCANNER_TOKEN, 1)
            if end < 0:
                node = Node(self, '').add_error(
                    'END_SCANNER_TOKEN delimiter missing from scanner token. '
                    '(Most likely due to a scanner bug!)')
                return node, text[1:]
            elif end == 0:
                node = Node(self, '').add_error(
                    'Scanner token cannot have zero length. '
                    '(Most likely due to a scanner bug!)')
                return node, text[2:]
            elif text.find(BEGIN_SCANNER_TOKEN, 1, end) >= 0:
                node = Node(self, text[len(self.name) + 1:end])
                node.add_error(
                    'Scanner tokens must not be nested or contain '
                    'BEGIN_SCANNER_TOKEN delimiter as part of their argument. '
                    '(Most likely due to a scanner bug!)')
                return node, text[end:]
            if text[1:len(self.name) + 1] == self.name:
                return Node(self, text[len(self.name) + 1:end]), \
                       text[end + 1:]
        return None, text


class RegExp(Parser):
    def __init__(self, regexp, name=None):
        super(RegExp, self).__init__(name)
        self.regexp = re.compile(regexp) if isinstance(regexp, str) else regexp

    def __deepcopy__(self, memo):
        # this method is obsolete with the new `regex` module!
        try:
            regexp = copy.deepcopy(self.regexp)
        except TypeError:
            regexp = self.regexp.pattern
        duplicate = RegExp(self.name, regexp)
        duplicate.name = self.name  # this ist needed!!!!
        duplicate.regexp = self.regexp
        duplicate.grammar = self.grammar
        duplicate.visited = copy.deepcopy(self.visited, memo)
        duplicate.recursion_counter = copy.deepcopy(self.recursion_counter,
                                                    memo)
        return duplicate

    def __call__(self, text):
        match = text[0:1] != BEGIN_SCANNER_TOKEN and self.regexp.match(text)  # ESC starts a scanner token.
        if match:
            end = match.end()
            return Node(self, text[:end]), text[end:]
        return None, text


class RE(Parser):
    """Regular Expressions with optional leading or trailing whitespace.
    """
    def __init__(self, regexp, wL=None, wR=None, name=None):
        super(RE, self).__init__(name)
        # assert wR or regexp == '.' or isinstance(self, Token)
        self.wL = wL
        self.wR = wR
        self.wspLeft = RegExp(wL, WHITESPACE_KEYWORD) if wL else ZOMBIE_PARSER
        self.wspRight = RegExp(wR, WHITESPACE_KEYWORD) if wR else ZOMBIE_PARSER
        self.main = RegExp(regexp)

    def __call__(self, text):
        # assert self.main.regexp.pattern != "@"
        t = text
        wL, t = self.wspLeft(t)
        main, t = self.main(t)
        if main:
            wR, t = self.wspRight(t)
            result = tuple(nd for nd in (wL, main, wR)
                           if nd and nd.result != '')
            return Node(self, result), t
        return None, text

    def __str__(self):
        if self.name == TOKEN_KEYWORD:
            return 'Token "%s"' % self.main.regexp.pattern.replace('\\', '')
        return self.name or ('RE ' + ('~' if self.wL else '')
                             + '/%s/' % self.main.regexp.pattern + ('~' if self.wR else ''))

    def _grammar_assigned_notifier(self):
        if self.grammar:
            if self.wL is None:
                self.wspLeft = self.grammar.wsp_left_parser__
            if self.wR is None:
                self.wspRight = self.grammar.wsp_right_parser__

    def apply(self, func):
        if super(RE, self).apply(func):
            if self.wL:
                self.wspLeft.apply(func)
            if self.wR:
                self.wspRight.apply(func)
            self.main.apply(func)


def escape_re(s):
    """Returns `s` with all regular expression special characters escaped.
    """
    assert isinstance(s, str)
    re_chars = r"\.^$*+?{}[]()#<>=|!"
    for esc_ch in re_chars:
        s = s.replace(esc_ch, '\\' + esc_ch)
    return s

#
# class Token(RE):
#     def __init__(self, token, wL=None, wR=None, name=None):
#         super(Token, self).__init__(escape_re(token), wL, wR, name or TOKEN_KEYWORD)
#
#     def __str__(self):
#         return self.name or 'Token "%s"' % self.main.regexp.pattern.replace('\\', '')

def Token(token, wL=None, wR=None, name=None):
    return RE(escape_re(token), wL, wR, name or TOKEN_KEYWORD)


def mixin_comment(whitespace, comment):
    """Mixes comment-regexp into whitespace regexp.
    """
    wspc = '(?:' + whitespace + '(?:' + comment + whitespace + ')*)'
    return wspc



########################################################################
#
# Combinator parser classes (i.e. trunk classes of the parser tree)
#
########################################################################


class UnaryOperator(Parser):
    def __init__(self, parser, name=None):
        super(UnaryOperator, self).__init__(name)
        assert isinstance(parser, Parser)
        self.parser = parser

    def apply(self, func):
        if super(UnaryOperator, self).apply(func):
            self.parser.apply(func)


class NaryOperator(Parser):
    def __init__(self, *parsers, name=None):
        super(NaryOperator, self).__init__(name)
        assert all([isinstance(parser, Parser) for parser in parsers]), str(parsers)
        self.parsers = parsers

    def apply(self, func):
        if super(NaryOperator, self).apply(func):
            for parser in self.parsers:
                parser.apply(func)


class Optional(UnaryOperator):
    def __init__(self, parser, name=None):
        super(Optional, self).__init__(parser, name)
        assert isinstance(parser, Parser)
        assert not isinstance(parser, Optional), \
            "Nesting options would be redundant: %s(%s)" % \
            (str(name), str(parser.name))
        assert not isinstance(parser, Required), \
            "Nestion options with required elements is contradictory: " \
            "%s(%s)" % (str(name), str(parser.name))

    def __call__(self, text):
        node, text = self.parser(text)
        if node:
            return Node(self, node), text
        return Node(self, ()), text


class ZeroOrMore(Optional):
    def __call__(self, text):
        results = ()
        while text:
            node, text = self.parser(text)
            if not node:
                break
            results += (node,)
        return Node(self, results), text


class OneOrMore(UnaryOperator):
    def __init__(self, parser, name=None):
        super(OneOrMore, self).__init__(parser, name)
        assert not isinstance(parser, Optional), \
            "Use ZeroOrMore instead of nesting OneOrMore and Optional: " \
            "%s(%s)" % (str(name), str(parser.name))

    def __call__(self, text):
        results = ()
        text_ = text
        while text_:
            node, text_ = self.parser(text_)
            if not node:
                break
            results += (node,)
        if results == ():
            return None, text
        return Node(self, results), text_


class Sequence(NaryOperator):
    def __init__(self, *parsers, name=None):
        super(Sequence, self).__init__(*parsers, name=name)
        assert len(self.parsers) >= 1
        # commented, because sequences can be empty:
        # assert not all(isinstance(p, Optional) for p in self.parsers)

    def __call__(self, text):
        results = ()
        text_ = text
        for parser in self.parsers:
            node, text_ = parser(text_)
            if not node:
                return node, text
            if node.result:  # Nodes with zero-length result are silently omitted
                results += (node,)
            if node.error_flag:
                break
        assert len(results) <= len(self.parsers)
        return Node(self, results), text_


class Alternative(NaryOperator):
    def __init__(self, *parsers, name=None):
        super(Alternative, self).__init__(*parsers, name=name)
        assert len(self.parsers) >= 1
        assert all(not isinstance(p, Optional) for p in self.parsers)

    def __call__(self, text):
        for parser in self.parsers:
            node, text_ = parser(text)
            if node:
                return Node(self, node), text_
        return None, text


########################################################################
#
# Flow control operators
#
########################################################################


class FlowOperator(UnaryOperator):
    def __init__(self, parser, name=None):
        super(FlowOperator, self).__init__(parser, name)


class Required(FlowOperator):
    # TODO: Add constructor that checks for logical errors, like `Required(Optional(...))` constructs
    def __call__(self, text):
        node, text_ = self.parser(text)
        if not node:
            m = re.search(r'\s(\S)', text)
            i = max(1, m.regs[1][0]) if m else 1
            node = Node(self, text[:i])
            text_ = text[i:]
            # assert False, "*"+text[:i]+"*"
            node.add_error('%s expected; "%s..." found!' %
                           (str(self.parser), text[:10]))
        return node, text_


class Lookahead(FlowOperator):
    def __init__(self, parser, name=None):
        super(Lookahead, self).__init__(parser, name)

    def __call__(self, text):
        node, text_ = self.parser(text)
        if self.sign(node is not None):
            return Node(self, ''), text
        else:
            return None, text

    def sign(self, bool_value):
        return bool_value


class NegativeLookahead(Lookahead):
    def sign(self, bool_value):
        return not bool_value


def iter_right_branch(node):
    """Iterates over the right branch of `node` starting with node itself.
    Iteration is stopped if either there are no child nodes any more or
    if the parser of a node is a Lookahead parser. (Reason is: Since
    lookahead nodes do not advance the parser, it does not make sense
    to look back to them.)
    """
    while node and not isinstance(node.parser, Lookahead):  # the second condition should not be necessary
        yield node                                          # for well-formed EBNF code
        node = node.children[-1] if node.children else None


class Lookbehind(FlowOperator):
    def __init__(self, parser, name=None):
        super(Lookbehind, self).__init__(parser, name)
        print("WARNING: Lookbehind Operator is experimental!")

    def __call__(self, text):
        if isinstance(self.grammar.last_node, Lookahead):
            return Node(self, '').add_error('Lookbehind right after Lookahead '
                                            'does not make sense!'), text
        if self.sign(self.condition()):
            return Node(self, ''), text
        else:
            return None, text