Module `hat.peg`

PEG Parser

Implementation of PEG parser as described in paper "Parsing Expression Grammars: A Recognition-Based Syntactic Foundation" (Bryan Ford, 2004). PEG's grammar itself can be defined by PEG grammar::

# Hierarchical syntax
Grammar    <- Spacing Definition+ EndOfFile
Definition <- Identifier LEFTARROW Expression
Expression <- Sequence (SLASH Sequence)*
Sequence   <- Prefix*
Prefix     <- (AND / NOT)? Suffix
Suffix     <- Primary (QUESTION / STAR / PLUS)?
Primary    <- Identifier !LEFTARROW
            / OPEN Expression CLOSE
            / Literal
            / Class
            / DOT

# Lexical syntax
Identifier <- IdentStart IdentCont* Spacing
IdentStart <- [a-zA-Z_]
IdentCont  <- IdentStart / [0-9]
Literal    <- ['] (!['] Char)* ['] Spacing
            / ["] (!["] Char)* ["] Spacing
Class      <- '[' (!']' Range)* ']' Spacing
Range      <- Char '-' Char / Char
Char       <- '\\' [nrt'"\[\]\\]
            / '\\' 'x' Hex Hex
            / '\\' 'u' Hex Hex Hex Hex
            / !'\\' .
Hex        <- [0-9a-fA-F]

LEFTARROW  <- '<-' Spacing
SLASH      <- '/' Spacing
AND        <- '&' Spacing
NOT        <- '!' Spacing
QUESTION   <- '?' Spacing
STAR       <- '*' Spacing
PLUS       <- '+' Spacing
OPEN       <- '(' Spacing
CLOSE      <- ')' Spacing
DOT        <- '.' Spacing

Spacing    <- (Space / Comment)*
Comment    <- '#' (!EndOfLine .)* EndOfLine
Space      <- ' ' / '\t' / EndOfLine
EndOfLine  <- '\r\n' / '\n' / '\r'
EndOfFile  <- !.

Example usage of PEG parser::

import functools
import hat.peg

grammar = hat.peg.Grammar(r'''
    Expr    <- Sum
    Sum     <- Product (('+' / '-') Product)*
    Product <- Value (('*' / '/') Value)*
    Value   <- Spacing ([0-9]+ / '(' Expr ')') Spacing
    Spacing <- ' '*
''', 'Expr')

ast = grammar.parse('1 + 2 * 3 + (4 - 5) * 6 + 7')

result = hat.peg.walk_ast(ast, {
    'Expr': lambda n, c: c[0],
    'Sum': lambda n, c: functools.reduce(
        (lambda acc, x: acc + x[1] if x[0] == '+' else acc - x[1]),
        zip(c[1::2], c[2::2]),
        c[0]),
    'Product': lambda n, c: functools.reduce(
        (lambda acc, x: acc * x[1] if x[0] == '*' else acc / x[1]),
        zip(c[1::2], c[2::2]),
        c[0]),
    'Value': lambda n, c: (c[2] if c[1] == '(' else
                           int(''.join(c[1:-1])))})

assert result == 8

Expand source code

r"""PEG Parser

Implementation of PEG parser as described in paper "Parsing Expression
Grammars: A Recognition-Based Syntactic Foundation" (Bryan Ford, 2004).
PEG's grammar itself can be defined by PEG grammar::

    # Hierarchical syntax
    Grammar    <- Spacing Definition+ EndOfFile
    Definition <- Identifier LEFTARROW Expression
    Expression <- Sequence (SLASH Sequence)*
    Sequence   <- Prefix*
    Prefix     <- (AND / NOT)? Suffix
    Suffix     <- Primary (QUESTION / STAR / PLUS)?
    Primary    <- Identifier !LEFTARROW
                / OPEN Expression CLOSE
                / Literal
                / Class
                / DOT

    # Lexical syntax
    Identifier <- IdentStart IdentCont* Spacing
    IdentStart <- [a-zA-Z_]
    IdentCont  <- IdentStart / [0-9]
    Literal    <- ['] (!['] Char)* ['] Spacing
                / ["] (!["] Char)* ["] Spacing
    Class      <- '[' (!']' Range)* ']' Spacing
    Range      <- Char '-' Char / Char
    Char       <- '\\' [nrt'"\[\]\\]
                / '\\' 'x' Hex Hex
                / '\\' 'u' Hex Hex Hex Hex
                / !'\\' .
    Hex        <- [0-9a-fA-F]

    LEFTARROW  <- '<-' Spacing
    SLASH      <- '/' Spacing
    AND        <- '&' Spacing
    NOT        <- '!' Spacing
    QUESTION   <- '?' Spacing
    STAR       <- '*' Spacing
    PLUS       <- '+' Spacing
    OPEN       <- '(' Spacing
    CLOSE      <- ')' Spacing
    DOT        <- '.' Spacing

    Spacing    <- (Space / Comment)*
    Comment    <- '#' (!EndOfLine .)* EndOfLine
    Space      <- ' ' / '\t' / EndOfLine
    EndOfLine  <- '\r\n' / '\n' / '\r'
    EndOfFile  <- !.

Example usage of PEG parser::

    import functools
    import hat.peg

    grammar = hat.peg.Grammar(r'''
        Expr    <- Sum
        Sum     <- Product (('+' / '-') Product)*
        Product <- Value (('*' / '/') Value)*
        Value   <- Spacing ([0-9]+ / '(' Expr ')') Spacing
        Spacing <- ' '*
    ''', 'Expr')

    ast = grammar.parse('1 + 2 * 3 + (4 - 5) * 6 + 7')

    result = hat.peg.walk_ast(ast, {
        'Expr': lambda n, c: c[0],
        'Sum': lambda n, c: functools.reduce(
            (lambda acc, x: acc + x[1] if x[0] == '+' else acc - x[1]),
            zip(c[1::2], c[2::2]),
            c[0]),
        'Product': lambda n, c: functools.reduce(
            (lambda acc, x: acc * x[1] if x[0] == '*' else acc / x[1]),
            zip(c[1::2], c[2::2]),
            c[0]),
        'Value': lambda n, c: (c[2] if c[1] == '(' else
                               int(''.join(c[1:-1])))})

    assert result == 8

"""

import typing

from hat import util


class Node(typing.NamedTuple):
    """Abstract syntax tree node.

    Node names are identifiers of parser's definitions and values
    are other nodes or string values representing matched `Literal`, `Class`
    or `Dot` leafs.

    """
    name: str
    value: typing.List[typing.Union['Node', str]]


Action = typing.Callable[[Node, typing.List], typing.Any]
"""Action"""
util.register_type_alias('Action')


def walk_ast(node: Node,
             actions: typing.Dict[str, Action],
             default_action: typing.Optional[Action] = None
             ) -> typing.Any:
    """Simple depth-first abstract syntax tree parser.

    Actions are key value pairs where keys represent node names and values
    are callables that should be called for appropriate node. Each callable
    receives matched node and list of results from recursively applying
    this function on child nodes. For nodes which name doesn't match any
    action, default action is used. If default action is not defined and node
    name doesn't match action, result is None and recursion is stopped.

    """
    action = actions.get(node.name, default_action)
    if not action:
        return
    children = [walk_ast(i, actions, default_action)
                if isinstance(i, Node) else i
                for i in node.value]
    return action(node, children)


class Sequence(typing.NamedTuple):
    expressions: typing.List['Expression']


class Choice(typing.NamedTuple):
    expressions: typing.List['Expression']


class Not(typing.NamedTuple):
    expression: 'Expression'


class And(typing.NamedTuple):
    expression: 'Expression'


class OneOrMore(typing.NamedTuple):
    expression: 'Expression'


class ZeroOrMore(typing.NamedTuple):
    expression: 'Expression'


class Optional(typing.NamedTuple):
    expression: 'Expression'


class Identifier(typing.NamedTuple):
    value: str


class Literal(typing.NamedTuple):
    value: str


class Class(typing.NamedTuple):
    values: typing.List[typing.Union[str, typing.Tuple[str, str]]]


class Dot(typing.NamedTuple):
    pass


Expression = typing.Union[Sequence, Choice, Not, And, OneOrMore, ZeroOrMore,
                          Optional, Identifier, Literal, Class, Dot]
"""Expression"""
util.register_type_alias('Expression')


class MatchResult(typing.NamedTuple):
    """Match result

    Args:
        node: matched node or ``None`` if match failed
        rest: remaining input data

    """
    node: typing.Optional[Node]
    rest: str


class MatchCallFrame(typing.NamedTuple):
    """Match call frame

    Args:
        name: definition name
        data: input data

    """
    name: str
    data: str


MatchCallStack = typing.Iterable[MatchCallFrame]
"""Match call stack"""
util.register_type_alias('MatchCallStack')


DebugCb = typing.Callable[[MatchResult, MatchCallStack], None]
"""Debug callback"""
util.register_type_alias('DebugCb')


class Grammar:
    """PEG Grammar.

    Args:
        definitions: grammar definitions
        starting: starting definition name

    """

    def __init__(self,
                 definitions: typing.Union[str,
                                           typing.Dict[str, Expression]],
                 starting: str):
        if isinstance(definitions, str):
            ast = _peg_grammar.parse(definitions)
            definitions = walk_ast(ast, _peg_actions)
            definitions = {k: _reduce_expression(v)
                           for k, v in definitions.items()}
        self._definitions = definitions
        self._starting = starting

    @property
    def definitions(self) -> typing.Dict[str, Expression]:
        """Definitions"""
        return self._definitions

    @property
    def starting(self) -> str:
        """Starting definition name"""
        return self._starting

    def parse(self,
              data: str,
              debug_cb: typing.Optional[DebugCb] = None
              ) -> Node:
        """Parse input data.

        `debug_cb` is optional function which can be used for monitoring and
        debugging parse steps. It is called each time named definition
        is successfully or unsuccessfully matched. This function receives
        match result and match call stack.

        """
        state = _State(grammar=self,
                       data=data,
                       call_stack=_MatchCallStack(None, None),
                       debug_cb=debug_cb)
        result = _match(state, self._starting)
        if result.node is None:
            raise Exception("could not match starting definition")
        x = _reduce_node(result.node)
        return x


def console_debug_cb(result: MatchResult, call_stack: MatchCallStack):
    """Simple console debugger."""
    success = '+++' if result.node else '---'
    stack = ', '.join(frame.name for frame in call_stack)
    consumed = util.first(call_stack).data[:-len(result.rest)]
    print(success, stack)
    print('<<<', consumed)
    print('>>>', result.rest, flush=True)


class _MatchCallStack(typing.NamedTuple):
    frame: typing.Optional[MatchCallFrame]
    previous: typing.Optional['_MatchCallStack']

    def __iter__(self):
        current = self
        while current and current.frame:
            yield current.frame
            current = current.previous


class _State(typing.NamedTuple):
    grammar: Grammar
    data: str
    call_stack: _MatchCallStack
    debug_cb: DebugCb


def _match(state, name):
    call_frame = MatchCallFrame(name, state.data)
    if call_frame in state.call_stack:
        raise Exception('Infinite matching recursion detected')
    state = state._replace(
        call_stack=_MatchCallStack(call_frame, state.call_stack))
    result = _match_expression(state, state.grammar.definitions[name])
    if result.node:
        result = result._replace(
            node=result.node._replace(name=name))
    if state.debug_cb:
        debug_result = MatchResult(
            node=(_reduce_node(result.node) if result.node else None),
            rest=result.rest)
        state.debug_cb(debug_result, state.call_stack)
    return result


def _match_expression(state, expression):
    t = type(expression)
    if t == Choice:
        return _match_choice(state, expression)
    if t == Sequence:
        return _match_sequence(state, expression)
    if t == Not:
        return _match_not(state, expression)
    if t == And:
        return _match_and(state, expression)
    if t == OneOrMore:
        return _match_oneormore(state, expression)
    if t == ZeroOrMore:
        return _match_zeroormore(state, expression)
    if t == Optional:
        return _match_optional(state, expression)
    if t == Identifier:
        return _match_identifier(state, expression)
    if t == Literal:
        return _match_literal(state, expression)
    if t == Class:
        return _match_class(state, expression)
    if t == Dot:
        return _match_dot(state, expression)
    raise ValueError('unsupported expression type')


def _match_choice(state, expression):
    for i in expression.expressions:
        result = _match_expression(state, i)
        if result.node:
            return result
    return MatchResult(None, state.data)


def _match_sequence(state, expression):
    nodes = []
    for i in expression.expressions:
        result = _match_expression(state, i)
        if not result.node:
            return MatchResult(None, state.data)
        nodes.append(result.node)
        state = state._replace(data=result.rest)
    return MatchResult(Node(None, nodes), state.data)


def _match_not(state, expression):
    result = _match_expression(state, expression.expression)
    return (MatchResult(None, state.data) if result.node
            else MatchResult(Node(None, []), state.data))


def _match_and(state, expression):
    node = _match_expression(state, expression.expression).node
    return MatchResult(Node(None, []) if node else None, state.data)


def _match_oneormore(state, expression):
    return _match_expression(state, Sequence([
        expression.expression,
        ZeroOrMore(expression.expression)]))


def _match_zeroormore(state, expression):
    nodes = []
    while True:
        result = _match_expression(state, expression.expression)
        if not result.node:
            return MatchResult(Node(None, nodes), state.data)
        nodes.append(result.node)
        state = state._replace(data=result.rest)


def _match_optional(state, expression):
    result = _match_expression(state, expression.expression)
    if result.node:
        return result
    return MatchResult(Node(None, []), state.data)


def _match_identifier(state, expression):
    result = _match(state, expression.value)
    if result.node:
        result = result._replace(node=Node(None, [result.node]))
    return result


def _match_literal(state, expression):
    data = state.data[:len(expression.value)]
    if data != expression.value:
        return MatchResult(None, state.data)
    rest = state.data[len(expression.value):]
    return MatchResult(Node(None, [data]), rest)


def _match_class(state, expression):
    if state.data:
        for i in expression.values:
            if isinstance(i, str):
                matched = state.data[0] == i
            else:
                matched = i[0] <= state.data[0] <= i[1]
            if matched:
                return MatchResult(Node(None, [state.data[:1]]),
                                   state.data[1:])
    return MatchResult(None, state.data)


def _match_dot(state, expression):
    if not state.data:
        return MatchResult(None, state.data)
    return MatchResult(Node(None, [state.data[:1]]), state.data[1:])


def _reduce_expression(expr):
    if hasattr(expr, 'expressions'):
        if len(expr.expressions) == 1:
            return _reduce_expression(expr.expressions[0])
        return expr._replace(expressions=[_reduce_expression(i)
                                          for i in expr.expressions])
    if hasattr(expr, 'expression'):
        return expr._replace(expression=_reduce_expression(expr.expression))
    return expr


def _reduce_node(node):
    return node._replace(value=list(_reduce_node_list(node.value)))


def _reduce_node_list(nodes):
    for node in nodes:
        if not isinstance(node, Node):
            yield node
        elif node.name is None:
            yield from _reduce_node_list(node.value)
        else:
            yield _reduce_node(node)


_peg_grammar = Grammar({
    'Grammar': Sequence([
        Identifier('Spacing'),
        OneOrMore(Identifier('Definition')),
        Identifier('EndOfFile')]),
    'Definition': Sequence([
        Identifier('Identifier'),
        Identifier('LEFTARROW'),
        Identifier('Expression')]),
    'Expression': Sequence([
        Identifier('Sequence'),
        ZeroOrMore(Sequence([
            Identifier('SLASH'),
            Identifier('Sequence')]))]),
    'Sequence': ZeroOrMore(Identifier('Prefix')),
    'Prefix': Sequence([
        Optional(Choice([
            Identifier('AND'),
            Identifier('NOT')])),
        Identifier('Suffix')]),
    'Suffix': Sequence([
        Identifier('Primary'),
        Optional(Choice([
            Identifier('QUESTION'),
            Identifier('STAR'),
            Identifier('PLUS')]))]),
    'Primary': Choice([
        Sequence([
            Identifier('Identifier'),
            Not(Identifier('LEFTARROW'))]),
        Sequence([
            Identifier('OPEN'),
            Identifier('Expression'),
            Identifier('CLOSE')]),
        Identifier('Literal'),
        Identifier('Class'),
        Identifier('DOT')]),
    'Identifier': Sequence([
        Identifier('IdentStart'),
        ZeroOrMore(Identifier('IdentCont')),
        Identifier('Spacing')]),
    'IdentStart': Class([('a', 'z'),
                         ('A', 'Z'),
                         '_']),
    'IdentCont': Choice([
        Identifier('IdentStart'),
        Class([('0', '9')])]),
    'Literal': Choice([
        Sequence([
            Class(["'"]),
            ZeroOrMore(Sequence([
                Not(Class(["'"])),
                Identifier('Char')])),
            Class(["'"]),
            Identifier('Spacing')]),
        Sequence([
            Class(['"']),
            ZeroOrMore(Sequence([
                Not(Class(['"'])),
                Identifier('Char')])),
            Class(['"']),
            Identifier('Spacing')])]),
    'Class': Sequence([
        Literal('['),
        ZeroOrMore(Sequence([
            Not(Literal(']')),
            Identifier('Range')])),
        Literal(']'),
        Identifier('Spacing')]),
    'Range': Choice([
        Sequence([
            Identifier('Char'),
            Literal('-'),
            Identifier('Char')]),
        Identifier('Char')]),
    'Char': Choice([
        Sequence([
            Literal('\\'),
            Class(['n', 'r', 't', "'", '"', '[', ']', '\\'])]),
        Sequence([
            Literal('\\'),
            Literal('x'),
            Identifier('Hex'),
            Identifier('Hex')]),
        Sequence([
            Literal('\\'),
            Literal('u'),
            Identifier('Hex'),
            Identifier('Hex'),
            Identifier('Hex'),
            Identifier('Hex')]),
        Sequence([
            Not(Literal('\\')),
            Dot()])]),
    'Hex': Class([('0', '9'),
                  ('a', 'f'),
                  ('A', 'F')]),
    'LEFTARROW': Sequence([
        Literal('<-'),
        Identifier('Spacing')]),
    'SLASH': Sequence([
        Literal('/'),
        Identifier('Spacing')]),
    'AND': Sequence([
        Literal('&'),
        Identifier('Spacing')]),
    'NOT': Sequence([
        Literal('!'),
        Identifier('Spacing')]),
    'QUESTION': Sequence([
        Literal('?'),
        Identifier('Spacing')]),
    'STAR': Sequence([
        Literal('*'),
        Identifier('Spacing')]),
    'PLUS': Sequence([
        Literal('+'),
        Identifier('Spacing')]),
    'OPEN': Sequence([
        Literal('('),
        Identifier('Spacing')]),
    'CLOSE': Sequence([
        Literal(')'),
        Identifier('Spacing')]),
    'DOT': Sequence([
        Literal('.'),
        Identifier('Spacing')]),
    'Spacing': ZeroOrMore(Choice([
        Identifier('Space'),
        Identifier('Comment')])),
    'Comment': Sequence([
        Literal('#'),
        ZeroOrMore(Sequence([
            Not(Identifier('EndOfLine')),
            Dot()])),
        Identifier('EndOfLine')]),
    'Space': Choice([
        Literal(' '),
        Literal('\t'),
        Identifier('EndOfLine')]),
    'EndOfLine': Choice([
        Literal('\r\n'),
        Literal('\n'),
        Literal('\r')]),
    'EndOfFile': Not(Dot())
}, 'Grammar')


_peg_actions = {
    'Grammar': lambda n, c: {k: v for k, v in filter(bool, c)},
    'Definition': lambda n, c: (c[0].value, c[2]),
    'Expression': lambda n, c: Choice(list(c[::2])),
    'Sequence': lambda n, c: Sequence(c),
    'Prefix': lambda n, c: (c[0] if len(c) == 1 else
                            c[0](c[1])),
    'Suffix': lambda n, c: (c[0] if len(c) == 1 else
                            c[1](c[0])),
    'Primary': lambda n, c: (c[1] if c[0] is None else
                             c[0]),
    'Identifier': lambda n, c: Identifier(''.join(c[:-1])),
    'IdentStart': lambda n, c: c[0],
    'IdentCont': lambda n, c: c[0],
    'Literal': lambda n, c: Literal(''.join(c[1:-2])),
    'Class': lambda n, c: Class(c[1:-2]),
    'Range': lambda n, c: (c[0] if len(c) == 1 else
                           (c[0], c[2])),
    'Char': lambda n, c: (c[0] if c[0] != '\\' else
                          '\n' if c[1] == 'n' else
                          '\r' if c[1] == 'r' else
                          '\t' if c[1] == 't' else
                          "'" if c[1] == "'" else
                          '"' if c[1] == '"' else
                          '[' if c[1] == '[' else
                          ']' if c[1] == ']' else
                          '\\' if c[1] == '\\' else
                          chr(int(c[2:], 16))),
    'Hex': lambda n, c: c[0],
    'AND': lambda n, c: And,
    'NOT': lambda n, c: Not,
    'QUESTION': lambda n, c: Optional,
    'STAR': lambda n, c: ZeroOrMore,
    'PLUS': lambda n, c: OneOrMore,
    'DOT': lambda n, c: Dot()
}

Global variables

var Action : typing.Type[typing.Callable[[Node, typing.List], typing.Any]]: Action
var DebugCb : typing.Type[typing.Callable[[MatchResult, ~MatchCallStack], NoneType]]: Debug callback
var Expression : typing.Type[typing.Union[Sequence, Choice, Not, And, OneOrMore, ZeroOrMore, Optional, Identifier, Literal, Class, Dot]]: Expression
var MatchCallStack : typing.Type[typing.Iterable[MatchCallFrame]]: Match call stack

Functions

def console_debug_cb(result: MatchResult, call_stack: ~MatchCallStack)

Simple console debugger.

Expand source code

def console_debug_cb(result: MatchResult, call_stack: MatchCallStack):
    """Simple console debugger."""
    success = '+++' if result.node else '---'
    stack = ', '.join(frame.name for frame in call_stack)
    consumed = util.first(call_stack).data[:-len(result.rest)]
    print(success, stack)
    print('<<<', consumed)
    print('>>>', result.rest, flush=True)

def walk_ast(node: Node, actions: typing.Dict[str, ~Action], default_action: typing.Optional[~Action] = None) ‑> typing.Any

Simple depth-first abstract syntax tree parser.

Actions are key value pairs where keys represent node names and values are callables that should be called for appropriate node. Each callable receives matched node and list of results from recursively applying this function on child nodes. For nodes which name doesn't match any action, default action is used. If default action is not defined and node name doesn't match action, result is None and recursion is stopped.

Expand source code

def walk_ast(node: Node,
             actions: typing.Dict[str, Action],
             default_action: typing.Optional[Action] = None
             ) -> typing.Any:
    """Simple depth-first abstract syntax tree parser.

    Actions are key value pairs where keys represent node names and values
    are callables that should be called for appropriate node. Each callable
    receives matched node and list of results from recursively applying
    this function on child nodes. For nodes which name doesn't match any
    action, default action is used. If default action is not defined and node
    name doesn't match action, result is None and recursion is stopped.

    """
    action = actions.get(node.name, default_action)
    if not action:
        return
    children = [walk_ast(i, actions, default_action)
                if isinstance(i, Node) else i
                for i in node.value]
    return action(node, children)

Classes

class And (expression: ForwardRef('Expression'))

And(expression,)

Expand source code

class And(typing.NamedTuple):
    expression: 'Expression'

Ancestors

builtins.tuple

Instance variables

var expression : ~Expression: Alias for field number 0

class Choice (expressions: typing.List[ForwardRef('Expression')])

Choice(expressions,)

Expand source code

class Choice(typing.NamedTuple):
    expressions: typing.List['Expression']

Ancestors

builtins.tuple

Instance variables

var expressions : typing.List[~Expression]: Alias for field number 0

class Class (values: typing.List[typing.Union[typing.Tuple[str, str], str]])

Class(values,)

Expand source code

class Class(typing.NamedTuple):
    values: typing.List[typing.Union[str, typing.Tuple[str, str]]]

Ancestors

builtins.tuple

Instance variables

var values : typing.List[typing.Union[typing.Tuple[str, str], str]]: Alias for field number 0

class Dot

Dot()

Expand source code

class Dot(typing.NamedTuple):
    pass

Ancestors

builtins.tuple

class Grammar (definitions: typing.Union[str, typing.Dict[str, ~Expression]], starting: str)

PEG Grammar.

Args

definitions: grammar definitions
starting: starting definition name

Expand source code

class Grammar:
    """PEG Grammar.

    Args:
        definitions: grammar definitions
        starting: starting definition name

    """

    def __init__(self,
                 definitions: typing.Union[str,
                                           typing.Dict[str, Expression]],
                 starting: str):
        if isinstance(definitions, str):
            ast = _peg_grammar.parse(definitions)
            definitions = walk_ast(ast, _peg_actions)
            definitions = {k: _reduce_expression(v)
                           for k, v in definitions.items()}
        self._definitions = definitions
        self._starting = starting

    @property
    def definitions(self) -> typing.Dict[str, Expression]:
        """Definitions"""
        return self._definitions

    @property
    def starting(self) -> str:
        """Starting definition name"""
        return self._starting

    def parse(self,
              data: str,
              debug_cb: typing.Optional[DebugCb] = None
              ) -> Node:
        """Parse input data.

        `debug_cb` is optional function which can be used for monitoring and
        debugging parse steps. It is called each time named definition
        is successfully or unsuccessfully matched. This function receives
        match result and match call stack.

        """
        state = _State(grammar=self,
                       data=data,
                       call_stack=_MatchCallStack(None, None),
                       debug_cb=debug_cb)
        result = _match(state, self._starting)
        if result.node is None:
            raise Exception("could not match starting definition")
        x = _reduce_node(result.node)
        return x

Instance variables

var definitions : typing.Dict[str, ~Expression]

Definitions

Expand source code

@property
def definitions(self) -> typing.Dict[str, Expression]:
    """Definitions"""
    return self._definitions

var starting : str

Starting definition name

Expand source code

@property
def starting(self) -> str:
    """Starting definition name"""
    return self._starting

Methods

def parse(self, data: str, debug_cb: typing.Optional[~DebugCb] = None) ‑> Node

Parse input data.

debug_cb is optional function which can be used for monitoring and debugging parse steps. It is called each time named definition is successfully or unsuccessfully matched. This function receives match result and match call stack.

Expand source code

def parse(self,
          data: str,
          debug_cb: typing.Optional[DebugCb] = None
          ) -> Node:
    """Parse input data.

    `debug_cb` is optional function which can be used for monitoring and
    debugging parse steps. It is called each time named definition
    is successfully or unsuccessfully matched. This function receives
    match result and match call stack.

    """
    state = _State(grammar=self,
                   data=data,
                   call_stack=_MatchCallStack(None, None),
                   debug_cb=debug_cb)
    result = _match(state, self._starting)
    if result.node is None:
        raise Exception("could not match starting definition")
    x = _reduce_node(result.node)
    return x

class Identifier (value: str)

Identifier(value,)

Expand source code

class Identifier(typing.NamedTuple):
    value: str

Ancestors

builtins.tuple

Instance variables

var value : str: Alias for field number 0

class Literal (value: str)

Literal(value,)

Expand source code

class Literal(typing.NamedTuple):
    value: str

Ancestors

builtins.tuple

Instance variables

var value : str: Alias for field number 0

class MatchCallFrame (name: str, data: str)

Match call frame

Args

name: definition name
data: input data

Expand source code

class MatchCallFrame(typing.NamedTuple):
    """Match call frame

    Args:
        name: definition name
        data: input data

    """
    name: str
    data: str

Ancestors

builtins.tuple

Instance variables

var data : str: Alias for field number 1
var name : str: Alias for field number 0

class MatchResult (node: typing.Optional[Node], rest: str)

Match result

Args

node: matched node or None if match failed
rest: remaining input data

Expand source code

class MatchResult(typing.NamedTuple):
    """Match result

    Args:
        node: matched node or ``None`` if match failed
        rest: remaining input data

    """
    node: typing.Optional[Node]
    rest: str

Ancestors

builtins.tuple

Instance variables

var node : typing.Optional[Node]: Alias for field number 0
var rest : str: Alias for field number 1

class Node (name: str, value: typing.List[typing.Union[ForwardRef('Node'), str]])

Abstract syntax tree node.

Node names are identifiers of parser's definitions and values are other nodes or string values representing matched Literal, Class or Dot leafs.

Expand source code

class Node(typing.NamedTuple):
    """Abstract syntax tree node.

    Node names are identifiers of parser's definitions and values
    are other nodes or string values representing matched `Literal`, `Class`
    or `Dot` leafs.

    """
    name: str
    value: typing.List[typing.Union['Node', str]]

Ancestors

builtins.tuple

Instance variables

var name : str: Alias for field number 0
var value : typing.List[typing.Union[Node, str]]: Alias for field number 1

class Not (expression: ForwardRef('Expression'))

Not(expression,)

Expand source code

class Not(typing.NamedTuple):
    expression: 'Expression'

Ancestors

builtins.tuple

Instance variables

var expression : ~Expression: Alias for field number 0

class OneOrMore (expression: ForwardRef('Expression'))

OneOrMore(expression,)

Expand source code

class OneOrMore(typing.NamedTuple):
    expression: 'Expression'

Ancestors

builtins.tuple

Instance variables

var expression : ~Expression: Alias for field number 0

class Optional (expression: ForwardRef('Expression'))

Optional(expression,)

Expand source code

class Optional(typing.NamedTuple):
    expression: 'Expression'

Ancestors

builtins.tuple

Instance variables

var expression : ~Expression: Alias for field number 0

class Sequence (expressions: typing.List[ForwardRef('Expression')])

Sequence(expressions,)

Expand source code

class Sequence(typing.NamedTuple):
    expressions: typing.List['Expression']

Ancestors

builtins.tuple

Instance variables

var expressions : typing.List[~Expression]: Alias for field number 0

class ZeroOrMore (expression: ForwardRef('Expression'))

ZeroOrMore(expression,)

Expand source code

class ZeroOrMore(typing.NamedTuple):
    expression: 'Expression'

Ancestors

builtins.tuple

Instance variables

var expression : ~Expression: Alias for field number 0