From time to time one might need to write simple language parser to implement some domain specific language for his application. As always python ecosystem offers various solutions – overview of python parser generators is available here. In this article I’d like to describe my experiences with parsimonious package. For recent project of mine ( imap_detach – a tool to automatically download attachment from IMAP mailbox) I needed simple expressions to specify what emails and what exact parts should be downloaded.

## Requirements

I needed a parser for simple logical expressions, which use a set of predefined variables ( properties of email), like these:

mime = "image/jpg" & attached & ! seen

Meaning: Email part is jpg image and is added as attachment and have not been seen yet

name ~=".pdf" & ( from ~= "jack" | from ~= "jim" )

Meaning all email part where filename contains .pdf and is from jack or jim

## Grammar

Parsimonious implements PEG grammar which enables to create very compact grammar definitions. Unlike some other parser generators, where grammar in expressed in Python, parsimonious has it’s own syntax, which enables to create short and easy to overview grammar definitions:

GRAMMAR=r""" # Test grammar expr = space or space or = and more_or more_or = ( space "|" space and )* and = term more_and more_and = ( space "&" space term )* term = not / value not = "!" space value value = contains / equals / bracketed / name bracketed = "(" space expr space ")" contains = name space "~=" space literal equals = name space "=" space literal name = ~"[a-z]+" literal = "\"" chars "\"" space = " "* chars = ~"[^\"]*" """

There are couple of things which has to be remembered, when creating grammar:

- PEG grammar should avoid left recursion, so rules like
and = expr space "&" space expr

Don not work and will result in recursion error ( infinite recursion). They have to be rewritten as indirect left recursion, which might be sometime challenging.

- PEG grammar grammar are more deterministic that context free grammars – so there is always one rule that is matched – there is no ambiguity like in CFG. This is assured by deterministic selection / – always first match is selected and by greedy repetition operators * + ? (they always match maximum possible length from input).

Practically this means that rules has to be more carefully designed and they need to be design in particular way to assure required priority of operators. - Only named rules can have some special treatment when walking AST tree ( see below). I think this is special feature of parsimonious, but AST contains nodes for a part of rule – like expressions that are in brackets. This means if I have rule like this:
and = term ( space "&" space term )*

I have no control on evaluating the right part, so I rather split it into two rules.

## Evaluation

Once we have the grammar, we can evaluate expressions by walking the parsed AST. Parsimonious provides nice support for this with visitor pattern . We can create subclass of `parsimonious.NodeVisitor`

with `visit_rulename`

methods for all (relevant) rules from the grammar. visit method receives current node in AST and list of values from its already visited (evaluated ) children.

We will need some supporting code (error class and function to decode binary strings to unicode):

class EvalError(Exception): def __init__(self, text, pos=0): super(EvalError, self).__init__(text+ ' at position %d'%pos) def decode(s): if isinstance(s, six.binary_type): return s.decode('UTF-8') return s

So here is example of `NodeVisitor`

class, that evaluates our simple expressions:

class SimpleEvaluator(parsimonious.NodeVisitor): def __init__(self, ctx, strict=True): self.grammar = parsimonious.Grammar(GRAMMAR) self._ctx = ctx self._strict = strict def visit_name(self, node, chidren): if node.text in self._ctx : val=self._ctx[node.text] if isinstance(val, (six.string_types)+ (six.binary_type,)) : val = decode(val).lower() return val elif self._strict: raise EvalError('Unknown variable %s'%node.text, node.start) else: return '' def visit_literal(self,node, children): return decode(children[1]).lower() def visit_chars(self, node, children): return node.text def binary(fn): # @NoSelf def _inner(self, node, children): if isinstance(children[0], bool): raise EvalError('Variable is boolean, should not be used here %s'% node.text, node.start) return fn(self, node, children) return _inner @binary def visit_contains(self, node, children): return children[0].find(children[-1]) > -1 @binary def visit_equals(self, node, children): return children[0] == children[-1] def visit_expr(self, node, children): return children[1] def visit_or(self, node, children): return children[0] or children[1] def visit_more_or(self,node, children): return any(children) def visit_and(self, node, children): return children[0] and (True if children[1] is None else children[1]) def visit_more_and(self, node, children): return all(children) def visit_not(self, node, children): return not children[-1] def visit_bracketed(self, node, children): return children[2] def generic_visit(self, node, children): if children: return children[-1]

This class evaluates expression within context of defined variable’s values (dictionary). So we can parse and evaluate expression with one method:

context = {"name": "test.pdf", "mime": "application/pdf", "from": "jim@example.com", "to": "myself@example.com", "attached": True, "seen": False } parser=SimpleEvaluator(context) result= parser.parse('name ~=".pdf" & ( from ~= "jack" | from ~= "jim" )')

## Conclusion

Parsimonious is a nice compact package for creating small parsers that are easy to use. For myself I bit struggled with PEG grammar, but that’s probably due to my unfamiliarity with this type of grammars. Once accustomed to it one can create more complex grammars.