Manual: chartparser

A parser engine

Puzzles and problems related to parsing occur naturally at computer and human interaction. Often the hard parsing problems lead to searching for alternatives that eventually turn out to be just as problematic as the original challenge.

This parsing module is an implementation of the marpa parsing algorithm. It is distinctively easy to use.

This module can be used to interpret a sequence or a string according to a context free grammar. Alternative uses include generating strings or detecting ambiguity in generated output.

This is one of the libraries that made Lever feasible to implement by a single person.

01. Short example of use

from chartparser import Rule, Nonterminal, Terminal, preprocess

expr   = Nonterminal("expr")
number = Nonterminal("number")
digit = Terminal("digit")
plus  = Terminal("plus")

grammar = [
    Rule(expr, [expr, plus, number], "math_op"),
    Rule(expr, [number],             "pass_number"),
    Rule(number, [digit],            "new_number"),
    Rule(number, [number, digit],    "add_digit")
]
new_parser = preprocess(grammar, expr)
parser = new_parser()
for ch in "123 + 456"
    if ch.is_space()
        continue
    elif ch.is_digit()
        parser.step(digit, ch)
    elif ch == "+"
        parser.step(plus, ch)
    else
        print("parsing failed")
        print(parser.expect...)
        exit(1)
print("accept?", parser.accepted)
if parser.accepted
    result = parser.traverse((rule, tree, start, stop):
        name = rule.annotation
        if name == "new_number"
            num = parse_int(tree[0])
            return num
        elif name == "add_digit"
            return tree[0] * 10 + parse_int(tree[1])
        elif name == "pass_number"
            print("a number", tree[0])
            return tree[0]
        elif name == "math_op"
            print("adding two numbers", tree[0], tree[2])
            return tree[0] + tree[2]
        else
            assert false
                "Not implemented: " ++ name)
    print(result)

The output:

accept? true
a number 123
adding two numbers 123 456
579

The writing of grammar rules may be tedious, so there is a separate language for writing rules and annotations into them.

02. Core interface

03. Implementation details