shreducer
Simple compilers in Python for fun and profit.
Example Grammars Included in This Project
If you want to reuse the examples code, feel free to copy the code into your projects, but do not introduce dependencies on examples as the examples may be changed or removed without notice. Build your own grammar and related classes by extending classes provided in the shreducer package only.
- Python 3.6+ type hints string representation
- Filter expressions for web APIs. Allows parsing of expressions like this:
https://your.api?filter=(status eq open and type eq store) or (status eq closed and type not in office, garage)
- With a compiler of Elasticsearch queries included (not tested since 2016)
- A couple of primitive grammars for basic arithmetic expressions as examples
Components
- Tokenizers (no need to implement your own, we rely on
shlex
from Python Standard Library) - Grammars
- Parsers (no need to implement your own, we use a shift-reduce parser, hence the name of the project)
- Generators
Tokenizer splits input string into lexical units of the grammar (we call them tokens here).
Grammar describes the syntax rules of a language that we want to parse.
Parser parses sequence of tokens and generates a parse tree.
For example ('+', 2, ('-', 10, 3))
could be a parse tree.
Generator takes a parse tree and evaluates it. For example, an arithmetic generator could take
a parse tree ('+', 2, ('-', 10, 3))
as an input and produce 9
as an output.
All these components together make a compiler.
Expressing a New Grammar
See examples under shreducer_examples/
:
DictG
- simplest of all grammars, the most suitable to understand the basic idea, parser produces parsed dictionaryListG
- another simple grammar, but unlike dictionary grammar, parser for this one produces parse treePlusMinusArithmeticsG
- simple arithmetic expression parser, parser produces parse treeBetterArithmeticsG
- arithmetic expression parser that respects operator precedence, parser produces parse treeFilterExpressionsG
- comparison operators and logical operators, parser produces parse treeBetterFiltersG
- comparatively rich filter expression language, unlike other grammars this one uses look-ahead, parser produces parse treeTypeHintsG
- parsing Python 3.6+ type hints string representation
There is some magic (a meta class) going on in t
class to allow
declaring a string constant without writing its value twice:
class MyGrammar(Grammar):
class t:
IDENT = None
PLUS_MINUS = '+-'
EXPR = ()
After the class MyGrammar
is created, the value of MyGrammar.t.IDENT
will be "IDENT"
.
Similarly, MyGrammar.t.PLUS_MINUS
will be "PLUS_MINUS"
, and MyGrammar.t.EXPR
will be "EXPR"
.
Member of class t
with value None
is treated as the default token type.
Members of class t
with value ()
are treated as names of tokens of higher order -- expressions.
Testing Your New Grammar
If you implement just a grammar, you can try parsing input strings with Grammar.simple_parse
(which is a class
method).
For example, to try TypeHintsG
(grammar for parsing type hints string representation in Python 3.6+),
you can do:
print(TypeHintsG.simple_parse('typing.Union[typing.List[str], typing.Dict[str, int]]'))
This will produce the following parse tree:
{
"name": "typing.Union",
"args": [
{
"name": "typing.List",
"args": [
{"name": "str", "args": None},
],
},
{
"name": "typing.Dict",
"args": [
{"name": "str", "args": None},
{"name": "int", "args": None},
],
},
],
}