grako 3.15.1

Table of Contents

Rationale

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

• Many languages allow the use of certain keywords as identifiers, or have different meanings for symbols depending on context (Ruby). A parser needs to be able to control the lexical analysis 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 in this case), 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 that the embedded semantic actions have correct syntax, so errors get reported at awkward moments, and against the generated code, not against the source.

• 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 (Python in this case), but it’s hard for 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 you cannot understand.

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

The Generated Parsers

A Grako generated parser consists of the following classes:

• A parser class derived from Parser which implements the parser using one method for each grammar rule:

  def _myrulename_(self):

• A semantics delegate class with one semantic method per grammar rule. Each method receives as its single parameter the Abstract Syntax Tree (AST) built from the rule invocation:

  def myrulename(self, ast):
      return ast

The methods in the delegate class return the same AST received as parameter, but custom semantic classes can override the methods to have them return anything (for example, a Semantic Graph). The semantics class can be used as a template for the final semantics implementation, which can omit methods for the rules it is not interested in.

If present, a _default() method will be called in the semantics class when no method matched the rule name:

def _default(self, ast):
    ...
    return ast

If present, a _postproc() method will be called in the semantics class after each rule (including the semantics) is processed. This method will receive the current parsing context as parameter:

def _postproc(self, context, ast):
    ...

Using the Tool

Grako can be run from the command line:

$ python -m grako

Or:

$ scripts/grako

Or just:

$ grako

if Grako was installed using easy_install or pip.

The -h and –help parameters provide full usage information:

$ python -m grako -h
usage: grako [--generate-parser | --draw | --object-model | --pretty]
            [--color] [--trace] [--no-left-recursion] [--name NAME]
            [--no-nameguard] [--outfile FILE] [--object-model-outfile FILE]
            [--whitespace CHARACTERS] [--help] [--version]
            GRAMMAR

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

positional arguments:
GRAMMAR               the filename of the Grako grammar to parse

optional arguments:
--generate-parser     generate parser code from the grammar (default)
--draw, -d            generate a diagram of the grammar (requires --outfile)
--object-model, -g    generate object model from the class names given as
                        rule arguments
--pretty, -p          generate a prettified version of the input grammar

parse-time options:
--color, -c           use color in traces (requires the colorama library)
--trace, -t           produce verbose parsing output

generation options:
--no-left-recursion, -l
                        turns left-recusion support off
--name NAME, -m NAME  Name for the grammar (defaults to GRAMMAR base name)
--no-nameguard, -n    allow tokens that are prefixes of others
--outfile FILE, --output FILE, -o FILE
                        output file (default is stdout)
--object-model-outfile FILE, -G FILE
                        generate object model and save to FILE
--whitespace CHARACTERS, -w CHARACTERS
                        characters to skip during parsing (use "" to disable)

common options:
--help, -h            show this help message and exit
--version, -v         provide version information and exit
$

Using the Generated Parser

To use the generated parser, just subclass the base or the abstract parser, create an instance of it, and invoke its parse() method passing the grammar to parse and the starting rule’s name as parameter:

parser = MyParser()
ast = parser.parse('text to parse', rule_name='start')
print(ast)
print(json.dumps(ast, indent=2)) # ASTs are JSON-friendy

This is more or less what happens if you invoke the generated parser directly:

python myparser.py inputfile startrule

The generated parsers’ constructors accept named arguments to specify whitespace characters, the regular expression for comments, case sensitivity, verbosity, and more (see below).

To add semantic actions, just pass a semantic delegate to the parse method:

model = parser.parse(text, rule_name='start', semantics=MySemantics())

If special lexical treatment is required (like in Python’s structure-through-indentation), then a descendant of grako.buffering.Buffer can be passed instead of the text:

class MySpecialBuffer(grako.buffering.Buffer):
    ...

buf = MySpecialBuffer(text)
model = parser.parse(buf, rule_name='start', semantics=MySemantics())

The EBNF Grammar Syntax

Grako uses a variant of the standard EBNF syntax. Syntax definitions for VIM can be found under the etc/vim directory in the source code distribution.

name = <expre> ;

FRAGMENT = /[a-z]+/ ;

number = /[0-9]+/ ;

number = number:/[0-9]+/ ;

addition(Add, op='+')
    =
    addend '+' addend
    ;

addition::Add, '+'
    =
    addend '+' addend
    ;

def addition(self, ast, name, op=None):
    ...

def _default(self, ast, *args, **kwargs):
    ...

base::Param = exp1 ;

extended < base = exp2 ;

extended::Param = exp1 exp2 ;

start = ab $;

ab = 'xyz' ;

@override
ab = @:'a' {@:'b'} ;

Abstract Syntax Trees (ASTs)

By default, and AST is either a list (for closures and rules without named elements), or dict-derived object that contains one item for every named element in the grammar rule. Items can be accessed through the standard dict syntax (ast['key']), or as attributes (ast.key).

AST entries are single values if only one item was associated with a name, or lists if more than one item was matched. There’s a provision in the grammar syntax (the +: operator) to force an AST entry to be a list even if only one element was matched. The value for named elements that were not found during the parse (perhaps because they are optional) is None.

When the parseinfo=True keyword argument has been passed to the Parser constructor, a parseinfo element is added to AST nodes that are dict-like. The element contains a collections.namedtuple with the parse information for the node:

ParseInfo = namedtuple(
    'ParseInfo',
    [
        'buffer',
        'rule',
        'pos',
        'endpos',
        'line',
        'endline',
    ]
)

With the help of the Buffer.line_info() method, it is possible to recover the line, column, and original text parsed for the node. Note that when ParseInfo is generated, the Buffer used during parsing is kept in memory for the lifetime of the AST.

Generation of parseinfo can also be controlled using the @@parseinfo :: True grammar directive.

Grammar Name

The prefix to be used in classes generated by Grako can be passed to the command-line tool using the -m option:

grako -m My mygrammar.ebnf

will generate:

class MyParser(Parser):

The name can also be specified within the grammar using the @@grammar directive:

@@grammar :: My

Whitespace

By default, Grako generated parsers skip the usual whitespace characters with the regular expression r'\s+' using the re.UNICODE flag (or with the Pattern_White_Space property if the regex module is available), but you can change that behavior by passing a whitespace parameter to your parser.

For example, the following will skip over tab (\t) and space characters, but not so with other typical whitespace characters such as newline (\n):

parser = MyParser(text, whitespace='\t ')

The character string is converted into a regular expression character set before starting to parse.

You can also provide a regular expression directly instead of a string. The following is equivalent to the above example:

parser = MyParser(text, whitespace=re.compile(r'[\t ]+'))

Note that the regular expression must be pre-compiled to let Grako distinguish it from plain string.

If you do not define any whitespace characters, then you will have to handle whitespace in your grammar rules (as it’s often done in PEG parsers):

parser = MyParser(text, whitespace='')

Whitespace may also be specified within the grammar using the @@whitespace directive, although any of the above methods will overwrite the grammar directive:

@@whitespace :: /[\t ]+/

Case Sensitivity

If the source language is case insensitive, you can tell your parser by using the ignorecase parameter:

parser = MyParser(text, ignorecase=True)

You may also specify case insensitivity within the grammar using the @@ignorecase directive:

@@ignorecase :: True

The change will affect both token and pattern matching.

Comments

Parsers will skip over comments specified as a regular expression using the comments_re parameter:

parser = MyParser(text, comments_re="\(\*.*?\*\)")

For more complex comment handling, you can override the Buffer.eat_comments() method.

For flexibility, it is possible to specify a pattern for end-of-line comments separately:

parser = MyParser(
    text,
    comments_re="\(\*.*?\*\)",
    eol_comments_re="#.*?$"
)

Both patterns may also be specified within a grammar using the @@comments and @@eol_comments directives:

@@comments :: /\(\*.*?\*\)/
@@eol_comments :: /#.*?$/

Reserved Words and Keywords

Some languages must reserve the use of certain tokens as valid identifiers because the tokens are used to mark particular constructs in the language. Those reserved tokens are known as Reserved Words or Keywords

Grako provides support for preventing the use of keywords as identifiers though the @@ keyword directive,and the @ name decorator.

A grammar may specify reserved tokens providing a list of them in one or more @@ keyword directives:

@@keyword :: if endif
@@keyword :: else elseif

The @ name decorator checks that the result of a grammar rule does not match a token defined as a keyword:

@name
identifier = /(?!\d)\w+/ ;

There are situations in which a token is reserved only in a very specific context. In those cases, a negative lookahead will prevent the use of the token:

statements = {!'END' statement}+ ;

Left Recursion

Grako provides support for left recursion in PEG grammars.

Sometimes, while debugging a grammar, it is useful to turn left-recursion support off:

parser = MyParser(
    text,
    left_recursion=False,
)

Left recursion can also be turned off from within the grammar using the @@left_recursion directive:

@@left_recursion :: False

Semantic Actions

There are no constructs for semantic actions in Grako grammars. This is on purpose, because semantic actions obscure the declarative nature of grammars and provide for poor modularization from the parser-execution perspective.

Semantic actions are defined in a class, and applied by passing an object of the class to the parse() method of the parser as the semantics= parameter. Grako will invoke the method that matches the name of the grammar rule every time the rule parses. The argument to the method will be the AST constructed from the right-hand-side of the rule:

class MySemantics(object):
    def some_rule_name(self, ast):
        return ''.join(ast)

    def _default(self, ast):
        pass

If there’s no method matching the rule’s name, Grako will try to invoke a _default() method if it’s defined:

def _default(self, ast):

Nothing will happen if neither the per-rule method nor _default() are defined.

The per-rule methods in classes implementing the semantics provide enough opportunity to do rule post-processing operations, like verifications (for inadequate use of keywords as identifiers), or AST transformation:

class MyLanguageSemantics(object):
    def identifier(self, ast):
        if my_lange_module.is_keyword(ast):
            raise FailedSemantics('"%s" is a keyword' % str(ast))
        return ast

For finer-grained control it is enough to declare more rules, as the impact on the parsing times will be minimal.

If preprocessing is required at some point, it is enough to place invocations of empty rules where appropriate:

myrule = first_part preproc {second_part} ;

preproc = () ;

The abstract parser will honor as a semantic action a method declared as:

def preproc(self, ast):

Include Directive

Grako grammars support file inclusion through the include directive:

#include :: "filename"

The resolution of the filename is relative to the directory/folder of the source. Absolute paths and ../ navigations are honored.

The functionality required for implementing includes is available to all Grako-generated parsers through the Buffer class; see the GrakoBuffer class in the grako.parser module for an example.

Building Models

Naming elements in grammar rules makes the parser discard uninteresting parts of the input, like punctuation, to produce an Abstract Syntax Tree (AST) that reflects the semantic structure of what was parsed. But an AST doesn’t carry information about the rule that generated it, so navigating the trees may be difficult.

Grako defines the grako.model.ModelBuilderSemantics semantics class which helps construct object models from abtract syntax trees:

from grako.model import ModelBuilderSemantics

parser = MyParser(semantics=ModelBuilderSemantics())

Then you add the desired node type as first parameter to each grammar rule:

addition::AddOperator = left:mulexpre '+' right:addition ;

ModelBuilderSemantics will synthesize an AddOperator(Node) class and use it to construct the node. The synthesized class will have one attribute with the same name as the named elements in the rule.

You can also use Python’s built-in types as node types, and ModelBuilderSemantics will do the right thing:

integer::int = /[0-9]+/ ;

ModelBuilderSemantics acts as any other semantics class, so its default behavior can be overidden by defining a method to handle the result of any particular grammar rule.

from grako.model import NodeWalker

class MyNodeWalker(NodeWalker):

    def walk_AddOperator(self, node):
        left = self.walk(node.left)
        right = self.walk(node.right)

        print('ADDED', left, right)

model = MyParser(semantics=ModelBuilderSemantics()).parse(input)

walker = MyNodeWalker()
walker.walk(model)

from mymodel import AddOperator, MulOperator

semantics=ModelBuilderSemantics(types=[AddOperator, MulOperator])

Templates and Translation

Grako doesn’t impose a way to create translators with it, but it exposes the facilities it uses to generate the Python source code for parsers.

Translation in Grako is template-based, but instead of defining or using a complex templating engine (yet another language), it relies on the simple but powerful string.Formatter of the Python standard library. The templates are simple strings that, in Grako’s style, are inlined with the code.

To generate a parser, Grako constructs an object model of the parsed grammar. A grako.codegen.CodeGenerator instance matches model objects to classes that descend from grako.codegen.ModelRenderer and implement the translation and rendering using string templates. Templates are left-trimmed on whitespace, like Python doc-comments are. This is an example taken from Grako’s source code:

class Lookahead(ModelRenderer):
    template = '''\
                with self._if():
                {exp:1::}\
                '''

Every attribute of the object that doesn’t start with an underscore (_) may be used as a template field, and fields can be added or modified by overriding the render_fields(fields) method. Fields themselves are lazily rendered before being expanded by the template, so a field may be an instance of a ModelRenderer descendant.

The rendering module defines a Formatter enhanced to support the rendering of items in an iterable one by one. The syntax to achieve that is:

{fieldname:ind:sep:fmt}

All of ind, sep, and fmt are optional, but the three colons are not. A field specified that way will be rendered using:

indent(sep.join(fmt % render(v) for v in value), ind)

The extended format can also be used with non-iterables, in which case the rendering will be:

indent(fmt % render(value), ind)

The default multiplier for ind is 4, but that can be overridden using n*m (for example 3*1) in the format.

Note

Using a newline (\\n) as separator will interfere with left trimming and indentation of templates. To use newline as separator, specify it as \\n, and the renderer will understand the intention.

Examples

Other Open-source Examples

• Christian Ledermann wrote parsewkt a parser for Well-known text (WTK) using Grako.

• Marcus Brinkmann (lambdafu) wrote smc.mw, a parser for a MediaWiki-style language.

• Marcus Brinkmann (lambdafu) is working on a C++ code generator for Grako called Grako++. Help in the form of testing, test cases, and pull requests is welcome.

License

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

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

Contact and Updates

For general Q&A, please use the [grako] tag on StackOverflow.

To discuss Grako and to receive notifications about new releases, please join the low-volume Grako Forum at Google Groups.

You can also follow the latest Grako developments with @GrakoPEG on Twitter.

Credits

The following must be mentioned as contributors of thoughts, ideas, code, and funding to the Grako project:

• Niklaus Wirth was the chief designer of the programming languages Euler, Algol W, Pascal, Modula, Modula-2, Oberon, and Oberon-2. In the last chapter of his 1976 book Algorithms + Data Structures = Programs, Wirth creates a top-down, descent parser with recovery for the Pascal-like, LL(1) programming language PL/0. The structure of the program is that of a PEG parser, though the concept of PEG wasn’t formalized until 2004.

• Bryan Ford introduced PEG (parsing expression grammars) in 2004.

• Other parser generators like PEG.js by David Majda inspired the work in Grako.

• William Thompson inspired the use of context managers with his blog post that I knew about through the invaluable Python Weekly newsletter, curated by Rahul Chaudhary

• Jeff Knupp explains why Grako’s use of exceptions is sound, so I don’t have to.

• Terence Parr created ANTLR, probably the most solid and professional parser generator out there. Ter, ANTLR, and the folks on the ANLTR forums helped me shape my ideas about Grako.

• JavaCC (originally Jack) looks like an abandoned project. It was the first parser generator I used while teaching.

• Grako is very fast. But dealing with millions of lines of legacy source code in a matter of minutes would be impossible without PyPy, the work of Armin Rigo and the PyPy team.

• Guido van Rossum created and has lead the development of the Python programming environment for over a decade. A tool like Grako, at under six thousand lines of code, would not have been possible without Python.

• Kota Mizushima welcomed me to the CSAIL at MIT PEG and Packrat parsing mailing list, and immediately offered ideas and pointed me to documentation about the implementation of cut in modern parsers. The optimization of memoization information in Grako is thanks to one of his papers.

• My students at UCAB inspired me to think about how grammar-based parser generation could be made more approachable.

• Gustavo Lau was my professor of Language Theory at USB, and he was kind enough to be my tutor in a thesis project on programming languages that was more than I could chew. My peers, and then teaching advisers Alberto Torres, and Enzo Chiariotti formed a team with Gustavo to challenge us with programming languages like LATORTA and term exams that went well into the eight hours. And, of course, there was also the pirate patch that should be worn on the left or right eye depending on the LL or LR challenge.

• Manuel Rey led me through another, unfinished, thesis project that taught me about what languages (spoken languages in general, and programming languages in particular) are about. I learned why languages use declensions, and why, although the underlying words are in English, the structure of the programs we write is more like Japanese.

• Marcus Brinkmann has kindly submitted patches that have resolved obscure bugs in Grako’s implementation, and that have made the tool more user-friendly, specially for newcomers to parsing and translation.

• Robert Speer cleaned up the nonsense in trying to have Unicode handling be compatible with 2.7.x and 3.x, and figured out the canonical way of honoring escape sequences in grammar tokens without throwing off the encoding.

• Basel Shishani has been an incredibly throrough peer-reviewer of Grako.

• Paul Sargent implemented Warth et al’s algorithm for supporting direct and indirect left recursion in PEG parsers.

• Kathryn Long proposed better support for UNICODE in the treatment of whitespace and regular expressions (patterns) in general. Her other contributions have made Grako more congruent, and more user-friendly.

• David Röthlisberger provided the definitive patch that allows the use of Python keywords as rule names.

Changes

See the CHANGELOG for details.