TatSu 5.22.0

TatSu takes a grammar in a variation of EBNF as input, and outputs a memoizing PEG/Packrat parser in Python.

​

​ ​ ​ ​

竜 TatSu

At least for the people who send me mail about a new language that they’re designing, the general advice is: do it to learn about how to write a compiler. Don’t have any expectations that anyone will use it, unless you hook up with some sort of organization in a position to push it hard. It’s a lottery, and some can buy a lot of the tickets. There are plenty of beautiful languages (more beautiful than C) that didn’t catch on. But someone does win the lottery, and doing a language at least teaches you something.

Dennis Ritchie (1941-2011) Creator of the C programming language and of Unix

竜 TatSu is a tool that takes grammars in extended EBNF as input, and outputs memoizing (Packrat) PEG parsers in Python. The classic variations of EBNF (Tomassetti, EasyExtend, Wirth) and ISO EBNF are supported as input grammar formats.

Sibling Projects!

Take a look at the sibling projects:

• 修TieXiu in Rust

• ⻰OGoPEGo in Go

• ꘩TS’emekwes in TypeScript

They are functionally complete and pass all the 竜 TatSu test suite.

Some features are implemented differently to abide to the semantics and idioms of each language (features being deprecated in 竜 TatSu are missing).

Prepare to be surprised at the performance differences, after thorough optimization, of Python versus Go, Rust, and TypeScript.

The New CLI Tool

Why use a PEG parser generator?

Regular expressions are “memory-less”—they excel at finding flat patterns like email addresses or phone numbers, but they fail once data becomes hierarchical. Regular expressions cannot “count” or balance demarcations (a regex cannot reliably validate whether opening and closing parenthesis are matched in a nested math equation).

Parsing is the essential step up when you need to understand the logic and structure of information rather than just its appearance. Parsing constructs an Abstract Syntax Tree (AST) of the input, a hierarchical map that represents how different parts of a sequence relate to one another.

• Recursive Structures: Whenever a piece of data can contain a version of itself (like a folder inside a folder, or a conditional if statement inside another if), you need a parser to track the depth and scope.

• Translating Formats: When converting one format into another, a parser ensures that the meaning of the original structure is preserved, preventing the “data soup” that occurs when using simple find-and-replace tools.

• Ambiguity Resolution: In complex sequences, the same sub-sequence might mean different things depending on where it sits in the tree. A parser uses the surrounding context to decide how to treat that sequence, whereas a regex treats every match in isolation.

• Domain-Specific Languages (DSL): Parsing allows the creation of specialized “mini-languages” tailored to a specific field, such as hardware description, music notation, or complex business rules.

• Executable Logic: While a regex can tell you if a string looks like a command, a parser turns that string into an object that a computer can actually execute, ensuring the order of operations and dependencies are strictly followed.

竜 TatSu can compile a grammar stored in a string into a Grammar object that can be used to parse any given input (much like the re module does with regular expressions). 竜 TatSu can also generate a Python module that implements the parser.

竜 TatSu supports left-recursive rules in PEG grammars using the algorithm by Laurent and Mens. The generated AST has the expected left associativity.

Compatibility

竜 TatSu expects a maintained version of Python (>=3.13), but currently all tests run in versions of Python down to Python 3.12. 竜 TatSu is also compatible with the current pre-release version of Python 3.15.

For older versions of Python, you may consider TatSu-LTS, a friendly fork of 竜 TatSu aimed at compatibility.

Installation

$ pip install TatSu

Using the Tool

竜 TatSu can be used as a library, much like Python’s re, by embedding grammars as strings and generating grammar models instead of generating Python code.

This compiles the grammar and generates an in-memory parser that can subsequently be used for parsing input with:

parser = tatsu.compile(grammar)

Compiles the grammar and parses the given input producing an AST as result:

ast = tatsu.parse(grammar, input)

The result is equivalent to calling:

parser = compile(grammar)
ast = parser.parse(input)

Compiled grammars are cached for efficiency.

This compiles the grammar to the Python source code that implements the parser:

parser_source = tatsu.to_python_sourcecode(grammar)

This is an example of how to use 竜 TatSu as a library:

GRAMMAR = '''
    start:  expression $

    expression:
        | expression '+' term
        | expression '-' term
        | term

    term:
        | term '*' factor
        | term '/' factor
        | factor

    factor:
        | '(' expression ')'
        | number

    number: /\d+/
'''


if __name__ == '__main__':
    import json
    from tatsu import parse
    from tatsu.util import asjson

    ast = parse(GRAMMAR, '3 + 5 * ( 10 - 20 )')
    print(ast.asjsons())

竜 TatSu will use the first rule defined in the grammar as the start rule.

This is the output:

[
  "3",
  "+",
  [
    "5",
    "*",
    [
      "10",
      "-",
      "20"
    ]
  ]
]

Documentation

For a detailed explanation of what 竜 TatSu is capable of, please see the documentation.

Questions?

Please use the [tatsu] tag on StackOverflow for general Q&A, and limit GitHub issues to bugs, enhancement proposals, and feature requests.

Changes

See the RELEASES for details.

License

You may use 竜 TatSu under the terms of the BSD-style license described in the enclosed LICENSE file. If your project requires different licensing please email.

For Fun

This is a diagram of the grammar for 竜 TatSu’s own grammar language:

start ●─grammar─■

grammar[Grammar] ●─ [title](`TATSU`)──┬→───────────────────────────────────┬── [`rules`]+(rule)──┬→───────────────────────────────┬──⇥＄
                                      ├→──┬─ [`directives`]+(directive)─┬──┤                     ├→──┬─ [`rules`]+(rule)───────┬──┤
                                      │   └─ [`keywords`]+(keyword)─────┘  │                     │   └─ [`keywords`]+(keyword)─┘  │
                                      └───────────────────────────────────<┘                     └───────────────────────────────<┘

directive ●─'@@'─ !['keyword'] ✂ ───┬─ [name](──┬─'comments'─────┬─) ✂ ─'::' ✂ ─ [value](regex)────────────┬─ ✂ ──■
                                    │           └─'eol_comments'─┘                                         │
                                    ├─ [name]('whitespace') ✂ ─'::' ✂ ─ [value](──┬─regex───┬─)────────────┤
                                    │                                             ├─string──┤              │
                                    │                                             ├─'None'──┤              │
                                    │                                             ├─'False'─┤              │
                                    │                                             └─`None`──┘              │
                                    ├─ [name](──┬─'nameguard'──────┬─) ✂ ───┬─'::' ✂ ─ [value](boolean)─┬──┤
                                    │           ├─'ignorecase'─────┤        └─ [value](`True`)──────────┘  │
                                    │           ├─'left_recursion'─┤                                       │
                                    │           ├─'parseinfo'──────┤                                       │
                                    │           └─'memoization'────┘                                       │
                                    ├─ [name]('grammar') ✂ ─'::' ✂ ─ [value](word)─────────────────────────┤
                                    └─ [name]('namechars') ✂ ─'::' ✂ ─ [value](string)─────────────────────┘

keywords ●───┬─keywords─┬───■
             └─────────<┘

keyword ●─'@@keyword' ✂ ─'::' ✂ ───┬→──────────────────────────────────┬───■
                                   ├→ @+(──┬─word───┬─)─ ![──┬─':'─┬─]─┤
                                   │       └─string─┘        └─'='─┘   │
                                   └──────────────────────────────────<┘

the_params_at_last ●───┬─ [kwparams](kwparams)─────────────────────────┬──■
                       ├─ [params](params)',' ✂ ─ [kwparams](kwparams)─┤
                       └─ [params](params)─────────────────────────────┘

paramdef ●───┬─'[' ✂ ─ >(the_params_at_last) ']'─┬──■
             ├─'(' ✂ ─ >(the_params_at_last) ')'─┤
             └─'::' ✂ ─ [params](params)─────────┘

rule[Rule] ●─ [decorators](──┬→──────────┬──) [name](name) ✂ ───┬─→ >(paramdef) ─┬───┬─→'<' ✂ ─ [base](known_name)─┬───┬─'='──┬─ ✂ ─ [exp](expre)ENDRULE ✂ ──■
                             ├→decorator─┤                      └─→──────────────┘   └─→───────────────────────────┘   ├─':='─┤
                             └──────────<┘                                                                             └─':'──┘

ENDRULE ●───┬── &[UNINDENTED]──────┬──■
            ├─EMPTYLINE──┬─→';'─┬──┤
            │            └─→────┘  │
            ├─⇥＄                  │
            └─';'──────────────────┘

UNINDENTED ●─/(?=\s*(?:\r?\n|\r)[^\s])/──■

EMPTYLINE ●─/(?:\s*(?:\r?\n|\r)){2,}/──■

decorator ●─'@'─ !['@'] ✂ ─ @(──┬─'override'─┬─)─■
                                ├─'name'─────┤
                                └─'nomemo'───┘

params ●─ @+(first_param)──┬→────────────────────────────┬───■
                           ├→',' @+(literal)─ !['='] ✂ ──┤
                           └────────────────────────────<┘

first_param ●───┬─path────┬──■
                └─literal─┘

kwparams ●───┬→────────────┬───■
             ├→',' ✂ ─pair─┤
             └────────────<┘

pair ●─ @+(word)'=' ✂ ─ @+(literal)─■

expre ●───┬─choice───┬──■
          └─sequence─┘

choice[Choice] ●───┬─→'|' ✂ ──┬─ @+(option)──┬─'|' ✂ ─ @+(option)─┬───■
                   └─→────────┘              └───────────────────<┘

option[Option] ●─ @(sequence)─■

sequence[Sequence] ●───┬── &[element',']──┬→───────────────┬───┬──■
                       │                  ├→',' ✂ ─element─┤   │
                       │                  └───────────────<┘   │
                       └───┬── ![ENDRULE]element─┬─────────────┘
                           └────────────────────<┘

element ●───┬─rule_include─┬──■
            ├─named────────┤
            ├─override─────┤
            └─term─────────┘

rule_include[RuleInclude] ●─'>' ✂ ─ @(known_name)─■

named ●───┬─named_list───┬──■
          └─named_single─┘

named_list[NamedList] ●─ [name](name)'+:' ✂ ─ [exp](term)─■

named_single[Named] ●─ [name](name)':' ✂ ─ [exp](term)─■

override ●───┬─override_list──────────────┬──■
             ├─override_single────────────┤
             └─override_single_deprecated─┘

override_list[OverrideList] ●─'@+:' ✂ ─ @(term)─■

override_single[Override] ●─'@:' ✂ ─ @(term)─■

override_single_deprecated[Override] ●─'@' ✂ ─ @(term)─■

term ●───┬─void───────────────┬──■
         ├─gather─────────────┤
         ├─join───────────────┤
         ├─left_join──────────┤
         ├─right_join─────────┤
         ├─empty_closure──────┤
         ├─positive_closure───┤
         ├─closure────────────┤
         ├─optional───────────┤
         ├─skip_to────────────┤
         ├─lookahead──────────┤
         ├─negative_lookahead─┤
         ├─cut────────────────┤
         ├─cut_deprecated─────┤
         └─atom───────────────┘

group[Group] ●─'(' ✂ ─ @(expre)')' ✂ ──■

gather ●── &[atom'.{'] ✂ ───┬─positive_gather─┬──■
                            └─normal_gather───┘

positive_gather[PositiveGather] ●─ [sep](atom)'.{' [exp](expre)'}'──┬─'+'─┬─ ✂ ──■
                                                                    └─'-'─┘

normal_gather[Gather] ●─ [sep](atom)'.{' ✂ ─ [exp](expre)'}'──┬─→'*' ✂ ──┬─ ✂ ──■
                                                              └─→────────┘

join ●── &[atom'%{'] ✂ ───┬─positive_join─┬──■
                          └─normal_join───┘

positive_join[PositiveJoin] ●─ [sep](atom)'%{' [exp](expre)'}'──┬─'+'─┬─ ✂ ──■
                                                                └─'-'─┘

normal_join[Join] ●─ [sep](atom)'%{' ✂ ─ [exp](expre)'}'──┬─→'*' ✂ ──┬─ ✂ ──■
                                                          └─→────────┘

left_join[LeftJoin] ●─ [sep](atom)'<{' ✂ ─ [exp](expre)'}'──┬─'+'─┬─ ✂ ──■
                                                            └─'-'─┘

right_join[RightJoin] ●─ [sep](atom)'>{' ✂ ─ [exp](expre)'}'──┬─'+'─┬─ ✂ ──■
                                                              └─'-'─┘

positive_closure[PositiveClosure] ●───┬─'{' @(expre)'}'──┬─'-'─┬─ ✂ ──┬──■
                                      │                  └─'+'─┘      │
                                      └─ @(atom)'+' ✂ ────────────────┘

closure[Closure] ●───┬─'{' @(expre)'}'──┬─→'*'─┬─ ✂ ──┬──■
                     │                  └─→────┘      │
                     └─ @(atom)'*' ✂ ─────────────────┘

empty_closure[EmptyClosure] ●─'{}' ✂ ─ @( ∅ )─■

optional[Optional] ●───┬─'[' ✂ ─ @(expre)']' ✂ ──────────┬──■
                       └─ @(atom)─ ![──┬─'?"'─┬─]'?' ✂ ──┘
                                       ├─"?'"─┤
                                       └─'?/'─┘

lookahead[Lookahead] ●─'&' ✂ ─ @(term)─■

negative_lookahead[NegativeLookahead] ●─'!' ✂ ─ @(term)─■

skip_to[SkipTo] ●─'->' ✂ ─ @(term)─■

atom ●───┬─group────┬──■
         ├─token────┤
         ├─alert────┤
         ├─constant─┤
         ├─call─────┤
         ├─pattern──┤
         ├─dot──────┤
         └─eof──────┘

call[Call] ●─word─■

void[Void] ●─'()' ✂ ──■

fail[Fail] ●─'!()' ✂ ──■

cut[Cut] ●─'~' ✂ ──■

cut_deprecated[Cut] ●─'>>' ✂ ──■

known_name ●─name ✂ ──■

name ●─word─■

constant[Constant] ●── &['`']──┬─/(?ms)```((?:.|\n)*?)```/──┬──■
                               ├─'`' @(literal)'`'──────────┤
                               └─/`(.*?)`/──────────────────┘

alert[Alert] ●─ [level](/\^+/─) [message](constant)─■

token[Token] ●───┬─string─────┬──■
                 └─raw_string─┘

literal ●───┬─string─────┬──■
            ├─raw_string─┤
            ├─boolean────┤
            ├─word───────┤
            ├─hex────────┤
            ├─float──────┤
            ├─int────────┤
            └─null───────┘

string ●─STRING─■

raw_string ●─//─ @(STRING)─■

STRING ●───┬─ @(/"((?:[^"\n]|\\"|\\\\)*?)"/─) ✂ ─────┬──■
           └─ @(/r"'((?:[^'\n]|\\'|\\\\)*?)'"/─) ✂ ──┘

hex ●─/0[xX](?:\d|[a-fA-F])+/──■

float ●─/[-+]?(?:\d+\.\d*|\d*\.\d+)(?:[Ee][-+]?\d+)?/──■

int ●─/[-+]?\d+/──■

path ●─/(?!\d)\w+(?:::(?!\d)\w+)+/──■

word ●─/(?!\d)\w+/──■

dot[Dot] ●─'/./'─■

pattern[Pattern] ●─regexes─■

regexes ●───┬→─────────────┬───■
            ├→'+' ✂ ─regex─┤
            └─────────────<┘

regex ●───┬─'/' ✂ ─ @(/(?:[^/\\]|\\/|\\.)*/─)'/' ✂ ──┬──■
          ├─'?' @(STRING)────────────────────────────┤
          └─deprecated_regex─────────────────────────┘

deprecated_regex ●─'?/' ✂ ─ @(/(?:.|\n)*?(?=/\?)/─)//\?+/─ ✂ ──■

boolean ●───┬─'True'──┬──■
            └─'False'─┘

null ●─'None'─■

eof[EOF] ●─'$' ✂ ──■