orphan:

Calc Mini Tutorial

竜 TatSu users have suggested that a simple calculator, like the one in the documentation for PLY would be useful, so here it goes.

The initial grammar

This is the original PLY grammar for arithmetic expressions:

expression : expression + term
           | expression - term
           | term

term       : term * factor
           | term / factor
           | factor

factor     : NUMBER
           | ( expression )

And this is the input expression for testing:

3 + 5 * ( 10 - 20 )

The TatSu grammar

The first step is to convert the grammar to 竜 TatSu syntax and style, with rules for lexical elements (number in this case). Then add a start rule that checks for end of input, and a directive to name the generated parser:

@@grammar::CALC


start
    =
    expression $
    ;


expression
    =
    | expression '+' term
    | expression '-' term
    | term
    ;


term
    =
    | term '*' factor
    | term '/' factor
    | factor
    ;


factor
    =
    | '(' expression ')'
    | number
    ;


number
    =
    /\d+/
    ;

Add cut expressions

Cut expressions make a parser commit to a particular option after certain tokens have been seen. They make parsing more efficient, because other options are not tried. They also make error messages more precise, because errors will be reported closest to the point of failure in the input.

@@grammar::CALC


start
    =
    expression $
    ;


expression
    =
    | expression '+' ~ term
    | expression '-' ~ term
    | term
    ;


term
    =
    | term '*' ~ factor
    | term '/' ~ factor
    | factor
    ;


factor
    =
    | '(' ~ expression ')'
    | number
    ;


number
    =
    /\d+/
    ;

Save the grammar as calc_cut.tatsu, and compile the grammar to test the parser:

import json
from pprint import pprint

import tatsu


def simple_parse():
    with open('calc_cut.tatsu') as f:
        grammar = f.read()

    parser = tatsu.compile(grammar)
    ast = parser.parse('3 + 5 * ( 10 - 20 )')

    print('# SIMPLE PARSE')
    print('# AST')
    pprint(ast, width=20, indent=4)

    print()

    print('# JSON')
    print(json.dumps(ast, indent=4))


if __name__ == '__main__':
    simple_parse()

Save the program as calc.py. This is the output:

$ python calc.py

# SIMPLE PARSE
# AST
[   '3',
    '+',
    [   '5',
        '*',
        [   '(',
            [   '10',
                '-',
                '20'],
            ')']]]

# JSON
[
    "3",
    "+",
    [
        "5",
        "*",
        [
            "(",
            [
                "10",
                "-",
                "20"
            ],
            ")"
        ]
    ]
]

Annotating the grammar

Dealing with ASTs that are lists of lists leads to code that is difficult to read, and error-prone. 竜 TatSu allows naming the elements in a rule to produce more humanly-readable ASTs and to allow for clearer semantics code. This is an annotated version of the grammar:

@@grammar::CALC


start
    =
    expression $
    ;


expression
    =
    | left:expression op:'+' ~ right:term
    | left:expression op:'-' ~ right:term
    | term
    ;


term
    =
    | left:term op:'*' ~ right:factor
    | left:term '/' ~ right:factor
    | factor
    ;


factor
    =
    | '(' ~ @:expression ')'
    | number
    ;


number
    =
    /\d+/
    ;

Save the annotated grammar in calc_annotated.tatsu, change the grammar filename in calc.py and re-execute it to get the resulting AST:

# ANNOTATED AST
{   'left': '3',
    'op': '+',
    'right': {   'left': '5',
                'op': '*',
                'right': {   'left': '10',
                            'op': '-',
                            'right': '20'}}}

Semantics

Semantic actions for 竜 TatSu parsers are not specified in the grammar, but in a separate semantics class.

from pprint import pprint

import tatsu
from tatsu.ast import AST


class CalcBasicSemantics:
    def number(self, ast):
        return int(ast)

    def term(self, ast):
        if not isinstance(ast, AST):
            return ast
        elif ast.op == '*':
            return ast.left * ast.right
        elif ast.op == '/':
            return ast.left / ast.right
        else:
            raise Exception('Unknown operator', ast.op)

    def expression(self, ast):
        if not isinstance(ast, AST):
            return ast
        elif ast.op == '+':
            return ast.left + ast.right
        elif ast.op == '-':
            return ast.left - ast.right
        else:
            raise Exception('Unknown operator', ast.op)


def parse_with_basic_semantics():
    with open('calc_annotated.tatsu') as f:
        grammar = f.read()

    parser = tatsu.compile(grammar)
    ast = parser.parse(
        '3 + 5 * ( 10 - 20 )',
        semantics=CalcBasicSemantics()
    )

    print('# BASIC SEMANTICS RESULT')
    pprint(ast, width=20, indent=4)


if __name__ == '__main__':
    parse_with_basic_semantics()

Save the program as calc_semantics.py and execute it with python calc_semantics.py. The result is:

# BASIC SEMANTICS RESULT
-47

One rule per expression type

Having semantic actions determine what was parsed with isinstance() or querying the AST for operators is not too pythonic, nor object oriented. It leads to code more difficult to maintain. It’s preferable to have one rule per expression kind (something necessary if we want to build object models and use walkers or code generation).

@@grammar::CALC


start
    =
    expression $
    ;


expression
    =
    | addition
    | subtraction
    | term
    ;


addition
    =
    left:expression op:'+' ~ right:term
    ;

subtraction
    =
    left:expression op:'-' ~ right:term
    ;


term
    =
    | multiplication
    | division
    | factor
    ;


multiplication
    =
    left:term op:'*' ~ right:factor
    ;


division
    =
    left:term op:'/' ~ right:factor
    ;


factor
    =
    | '(' ~ @:expression ')'
    | number
    ;


number
    =
    /\d+/
    ;

Save the grammar in calc_refactored.tatsu.

from pprint import pprint

import tatsu


class CalcSemantics:
    def number(self, ast):
        return int(ast)

    def addition(self, ast):
        return ast.left + ast.right

    def subtraction(self, ast):
        return ast.left - ast.right

    def multiplication(self, ast):
        return ast.left * ast.right

    def division(self, ast):
        return ast.left / ast.right


def parse_refactored():
    with open('calc_refactored.tatsu') as f:
        grammar = f.read()

    parser = tatsu.compile(grammar)
    ast = parser.parse(
        '3 + 5 * ( 10 - 20 )',
        semantics=CalcSemantics()
    )

    print('# REFACTORED SEMANTICS RESULT')
    pprint(ast, width=20, indent=4)
    print()


if __name__ == '__main__':
    parse_refactored()

The semantics implementation is simpler, and the results are the same:

# REFACTORED SEMANTICS RESULT
-47

Object models

Binding semantics to grammar rules is powerful and versatile, but this approach risks tying the semantics to the parsing process, rather than to the parsed objects.

That is not a problem for simple languages, like the arithmetic expression language in this tutorial. But as the complexity of the parsed language increases, the number of grammar rules becomes larger than the types of objects parsed.

竜 TatSu can create typed object models directly from the parsing process which can be navigated (walked) and transformed (with code generation) in later passes.

The first step to create an object model is to annotate the rule names with the desired class names:

@@grammar::Calc


start: expression $

expression:
    | addition
    | subtraction
    | term

addition[Add]:
    left:term op:'+' ~ right:expression

subtraction[Subtract]:
    left:term op:'-' ~ right:expression

term:
    | multiplication
    | division
    | factor

multiplication[Multiply]:
    left:factor op:'*' ~ right:term

division[Divide]:
    left:factor op:'/' ~ right:term

factor:
    | subexpression
    | number

subexpression:
    '(' ~ @:expression ')'

number[int]:
    /\d+/

Save the grammar in a file name calc_model.tatsu.

The tatsu.objectmodel.Node descendants are synthetized at runtime using tatsu.semantics .ModelBuilderSemantics.

This is how the model looks like when generated with the tatsu.to_python_model() function or from the command line with tatsu --object-model calc_model.tatsu -G calc_semantics_model.py:

from tatsu.objectmodel import Node
from tatsu.semantics import ModelBuilderSemantics


class ModelBase(Node):
    pass


class CalcModelBuilderSemantics(ModelBuilderSemantics):
    def __init__(self, context=None, types=None):
        types = [
            t for t in globals().values()
            if type(t) is type and issubclass(t, ModelBase)
        ] + (types or [])
        super(CalcModelBuilderSemantics, self).__init__(context=context, types=types)


class Add(ModelBase):
    left = None
    op = None
    right = None


class Subtract(ModelBase):
    left = None
    op = None
    right = None


class Multiply(ModelBase):
    left = None
    op = None
    right = None


class Divide(ModelBase):
    left = None
    right = None

The model that results from a parse can be printed, and walked:

import tatsu
from tatsu.walkers import NodeWalker


class CalcWalker(NodeWalker):
    def walk_object(self, node):
        return node

    def walk__add(self, node):
        return self.walk(node.left) + self.walk(node.right)

    def walk__subtract(self, node):
        return self.walk(node.left) - self.walk(node.right)

    def walk__multiply(self, node):
        return self.walk(node.left) * self.walk(node.right)

    def walk__divide(self, node):
        return self.walk(node.left) / self.walk(node.right)


def parse_and_walk_model():
    with open('calc_model.tatsu') as f:
        grammar = f.read()

    parser = tatsu.compile(grammar, asmodel=True)
    model = parser.parse('3 + 5 * ( 10 - 20 )')

    print('# WALKER RESULT IS:')
    print(CalcWalker().walk(model))
    print()


if __name__ == '__main__':
    parse_and_walk_model()

Save the program in calc_model.py and execute it to get this result:

# WALKER RESULT IS:
-47

Code Generation

Translation is one of the most common tasks in language processing. Analysis builds a compact representation of the parsed input. In translation, the output can often be as verbose as the input, so a systematic approach that avoids bookkeeping as much as possible is convenient.

竜 TatSu provides support for template-based code generation (translation) in the tatsu.codegen module. Code generation works by defining a translation class for each class in the model specified by the grammar.

Nowadays the preferred code generation strategy is to walk down the AST and print() the desired output, with the help of the NodWalker class, and the IndentPrintMixin mixin. That’s the strategy used by pegen, the precursor to the new PEG parser in Python.

The following code generator translates input expressions to the postfix instructions of a stack-based processor:

import sys

from tatsu.model import Node
from tatsu.walkers import NodeWalker
from tatsu.mixins.indent import IndentPrintMixin

THIS_MODULE = sys.modules[__name__]


class PostfixCodeGenerator(NodeWalker, IndentPrintMixin):

    def walk_Add(self, node: Node, *args, **kwargs):
        with self.indent():
            self.walk(node.left)  # type: ignore
            self.walk(node.right)  # type: ignore
            self.print('ADD')

    def walk_Subtract(self, node: Node, *args, **kwargs):
        with self.indent():
            self.walk(node.left)  # type: ignore
            self.walk(node.right)  # type: ignore
            self.print('SUB')

    def walk_Multiply(self, node: Node, *args, **kwargs):
        with self.indent():
            self.walk(node.left)  # type: ignore
            self.walk(node.right)  # type: ignore
            self.print('MUL')

    def walk_Divide(self, node: Node, *args, **kwargs):
        with self.indent():
            self.walk(node.left)  # type: ignore
            self.walk(node.right)  # type: ignore
            self.print('DIV')

    def walk_int(self, node: Node, *args, **kwargs):
        self.print('PUSH', node)

Save the previous program in calc_translate.py and execute it to get this result:

# TRANSLATED TO POSTFIX
    PUSH 3
        PUSH 5
            PUSH 10
            PUSH 20
            SUB
        MUL
    ADD