grako 3.99.9

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

---

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

Grako

NOTE: DEVELOPMENT OF GRAKO HAS STOPPED

If you’re interested in the technology, or in future developments such as proper support for left recursion, then please follow the Tatsu project.

---

Grako (for grammar compiler) is a tool that takes grammars in a variation of EBNF as input, and outputs memoizing (Packrat) PEG parsers in Python.

Grako can also 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.

Grako is different from other PEG parser generators:

• Generated parsers use Python’s very efficient exception-handling system to backtrack. Grako generated parsers simply assert what must be parsed. There are no complicated if-then-else sequences for decision making or backtracking. Memoization allows going over the same input sequence several times in linear time.

• Positive and negative lookaheads, and the cut element (with its cleaning of the memoization cache) allow for additional, hand-crafted optimizations at the grammar level.

• Delegation to Python’s re module for lexemes allows for (Perl-like) powerful and efficient lexical analysis.

• The use of Python’s context managers considerably reduces the size of the generated parsers for code clarity, and enhanced CPU-cache hits.

• Include files, rule inheritance, and rule inclusion give Grako grammars considerable expressive power.

• Automatic generation of Abstract Syntax Trees and Object Models, along with Model Walkers and Code Generators make analysis and translation approachable

The parser generator, the run-time support, and the generated parsers have measurably low Cyclomatic complexity. At around 5 KLOC of Python, it is possible to study all its source code in a single session.

The only dependencies are on the Python standard library, yet the regex library will be used if installed, and colorama will be used on trace output if available. pygraphviz is required for generating diagrams.

Grako is feature-complete and currently being used with complex grammars to parse, analyze, and translate hundreds of thousands of lines of input text, including source code in several programming languages.

Rationale

Grako was created to address some recurring problems encountered over decades of working with parser generation tools:

• Some programming languages allow the use of keywords as identifiers, or have different meanings for symbols depending on context (Ruby). A parser needs control of lexical analysis to be able to handle those languages.

• LL and LR grammars become contaminated with myriads of lookahead statements to deal with ambiguous constructs in the source language. PEG parsers address ambiguity from the onset.

• Separating the grammar from the code that implements the semantics, and using a variation of a well-known grammar syntax (EBNF) allows for full declarative power in language descriptions. General-purpose programming languages are not up to the task.

• Semantic actions do not belong in a grammar. They create yet another programming language to deal with when doing parsing and translation: the source language, the grammar language, the semantics language, the generated parser’s language, and the translation’s target language. Most grammar parsers do not check the syntax of embedded semantic actions, so errors get reported at awkward moments, and against the generated code, not against the grammar.

• Preprocessing (like dealing with includes, fixed column formats, or structure-through-indentation) belongs in well-designed program code; not in the grammar.

• It is easy to recruit help with knowledge about a mainstream programming language like Python, but help is hard to find for working with complex grammar-description languages. Grako grammars are in the spirit of a Translators and Interpreters 101 course (if something is hard to explain to a college student, it’s probably too complicated, or not well understood).

• Generated parsers should be easy to read and debug by humans. Looking at the generated source code is sometimes the only way to find problems in a grammar, the semantic actions, or in the parser generator itself. It’s inconvenient to trust generated code that one cannot understand.

• Python is a great language for working with language parsing and translation.

Documentation

The complete documentation is available at Grako’s home page.

License

Copyright (C) 2017      by Juancarlo Añez
Copyright (C) 2012-2016 by Juancarlo Añez and Thomas Bragg

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

Changes

See the CHANGELOG for details.