## File: README.md
# Lark - a parsing toolkit for Python
Lark is a parsing toolkit for Python, built with a focus on ergonomics, performance and modularity.
Lark can parse all context-free languages. To put it simply, it means that it is capable of parsing almost any programming language out there, and to some degree most natural languages too.
**Who is it for?**
- **Beginners**: Lark is very friendly for experimentation. It can parse any grammar you throw at it, no matter how complicated or ambiguous, and do so efficiently. It also constructs an annotated parse-tree for you, using only the grammar and an input, and it gives you convenient and flexible tools to process that parse-tree.
- **Experts**: Lark implements both Earley(SPPF) and LALR(1), and several different lexers, so you can trade-off power and speed, according to your requirements. It also provides a variety of sophisticated features and utilities.
**What can it do?**
- Parse all context-free grammars, and handle any ambiguity gracefully
- Build an annotated parse-tree automagically, no construction code required.
- Provide first-rate performance in terms of both Big-O complexity and measured run-time (considering that this is Python ;)
- Run on every Python interpreter (it's pure-python)
- Generate a stand-alone parser (for LALR(1) grammars)
And many more features. Read ahead and find out!
Most importantly, Lark will save you time and prevent you from getting parsing headaches.
### Quick links
- [Documentation @readthedocs](https://lark-parser.readthedocs.io/)
- [Cheatsheet (PDF)](/docs/_static/lark_cheatsheet.pdf)
- [Online IDE](https://lark-parser.org/ide)
- [Tutorial](/docs/json_tutorial.md) for writing a JSON parser.
- Blog post: [How to write a DSL with Lark](https://eshsoft.com/blog/write-dsl-in-python-with-lark)
- [Gitter chat](https://gitter.im/lark-parser/Lobby)
### Install Lark
$ pip install lark --upgrade
Lark has no dependencies.
[](https://github.com/lark-parser/lark/actions/workflows/tests.yml)
### Syntax Highlighting
Lark provides syntax highlighting for its grammar files (\*.lark):
- [Sublime Text & TextMate](https://github.com/lark-parser/lark_syntax)
- [vscode](https://github.com/lark-parser/vscode-lark)
- [Intellij & PyCharm](https://github.com/lark-parser/intellij-syntax-highlighting)
- [Vim](https://github.com/lark-parser/vim-lark-syntax)
- [Atom](https://github.com/Alhadis/language-grammars)
### Clones
These are implementations of Lark in other languages. They accept Lark grammars, and provide similar utilities.
- [Lerche (Julia)](https://github.com/jamesrhester/Lerche.jl) - an unofficial clone, written entirely in Julia.
- [Lark.js (Javascript)](https://github.com/lark-parser/lark.js) - a port of the stand-alone LALR(1) parser generator to Javascsript.
### Hello World
Here is a little program to parse "Hello, World!" (Or any other similar phrase):
```python
from lark import Lark
l = Lark('''start: WORD "," WORD "!"
%import common.WORD // imports from terminal library
%ignore " " // Disregard spaces in text
''')
print( l.parse("Hello, World!") )
```
And the output is:
```python
Tree(start, [Token(WORD, 'Hello'), Token(WORD, 'World')])
```
Notice punctuation doesn't appear in the resulting tree. It's automatically filtered away by Lark.
### Fruit flies like bananas
Lark is great at handling ambiguity. Here is the result of parsing the phrase "fruit flies like bananas":
[Read the code here](https://github.com/lark-parser/lark/tree/master/examples/fruitflies.py), and see [more examples here](https://lark-parser.readthedocs.io/en/latest/examples/index.html).
## List of main features
- Builds a parse-tree (AST) automagically, based on the structure of the grammar
- **Earley** parser
- Can parse all context-free grammars
- Full support for ambiguous grammars
- **LALR(1)** parser
- Fast and light, competitive with PLY
- Can generate a stand-alone parser ([read more](docs/tools.md#stand-alone-parser))
- **EBNF** grammar
- **Unicode** fully supported
- Automatic line & column tracking
- Interactive parser for advanced parsing flows and debugging
- Grammar composition - Import terminals and rules from other grammars
- Standard library of terminals (strings, numbers, names, etc.)
- Import grammars from Nearley.js ([read more](/docs/tools.md#importing-grammars-from-nearleyjs))
- Extensive test suite [](https://codecov.io/gh/lark-parser/lark)
- Type annotations (MyPy support)
- And much more!
See the full list of [features here](https://lark-parser.readthedocs.io/en/latest/features.html)
### Comparison to other libraries
#### Performance comparison
Lark is fast and light (lower is better)
Check out the [JSON tutorial](/docs/json_tutorial.md#conclusion) for more details on how the comparison was made.
For thorough 3rd-party benchmarks, checkout the [Python Parsing Benchmarks](https://github.com/goodmami/python-parsing-benchmarks) repo.
#### Feature comparison
| Library | Algorithm | Grammar | Builds tree? | Supports ambiguity? | Can handle every CFG? | Line/Column tracking | Generates Stand-alone
|:--------|:----------|:----|:--------|:------------|:------------|:----------|:----------
| **Lark** | Earley/LALR(1) | EBNF | Yes! | Yes! | Yes! | Yes! | Yes! (LALR only) |
| [PLY](http://www.dabeaz.com/ply/) | LALR(1) | BNF | No | No | No | No | No |
| [PyParsing](https://github.com/pyparsing/pyparsing) | PEG | Combinators | No | No | No\* | No | No |
| [Parsley](https://pypi.python.org/pypi/Parsley) | PEG | EBNF | No | No | No\* | No | No |
| [Parsimonious](https://github.com/erikrose/parsimonious) | PEG | EBNF | Yes | No | No\* | No | No |
| [ANTLR](https://github.com/antlr/antlr4) | LL(*) | EBNF | Yes | No | Yes? | Yes | No |
(\* *PEGs cannot handle non-deterministic grammars. Also, according to Wikipedia, it remains unanswered whether PEGs can really parse all deterministic CFGs*)
### Projects using Lark
- [Poetry](https://github.com/python-poetry/poetry-core) - A utility for dependency management and packaging
- [Vyper](https://github.com/vyperlang/vyper) - Pythonic Smart Contract Language for the EVM
- [PyQuil](https://github.com/rigetti/pyquil) - Python library for quantum programming using Quil
- [Preql](https://github.com/erezsh/preql) - An interpreted relational query language that compiles to SQL
- [Hypothesis](https://github.com/HypothesisWorks/hypothesis) - Library for property-based testing
- [mappyfile](https://github.com/geographika/mappyfile) - a MapFile parser for working with MapServer configuration
- [tartiflette](https://github.com/dailymotion/tartiflette) - GraphQL server by Dailymotion
- [synapse](https://github.com/vertexproject/synapse) - an intelligence analysis platform
- [Datacube-core](https://github.com/opendatacube/datacube-core) - Open Data Cube analyses continental scale Earth Observation data through time
- [SPFlow](https://github.com/SPFlow/SPFlow) - Library for Sum-Product Networks
- [Torchani](https://github.com/aiqm/torchani) - Accurate Neural Network Potential on PyTorch
- [Command-Block-Assembly](https://github.com/simon816/Command-Block-Assembly) - An assembly language, and C compiler, for Minecraft commands
- [EQL](https://github.com/endgameinc/eql) - Event Query Language
- [Fabric-SDK-Py](https://github.com/hyperledger/fabric-sdk-py) - Hyperledger fabric SDK with Python 3.x
- [required](https://github.com/shezadkhan137/required) - multi-field validation using docstrings
- [miniwdl](https://github.com/chanzuckerberg/miniwdl) - A static analysis toolkit for the Workflow Description Language
- [pytreeview](https://gitlab.com/parmenti/pytreeview) - a lightweight tree-based grammar explorer
- [harmalysis](https://github.com/napulen/harmalysis) - A language for harmonic analysis and music theory
- [gersemi](https://github.com/BlankSpruce/gersemi) - A CMake code formatter
- [MistQL](https://github.com/evinism/mistql) - A query language for JSON-like structures
- [Outlines](https://github.com/outlines-dev/outlines) - Structured generation with Large Language Models
[Full list](https://github.com/lark-parser/lark/network/dependents?package_id=UGFja2FnZS01MjI1OTE0NQ%3D%3D)
## License
Lark uses the [MIT license](LICENSE).
(The standalone tool is under MPL2)
## Contributors
Lark accepts pull-requests. See [How to develop Lark](/docs/how_to_develop.md)
Big thanks to everyone who contributed so far:
## Sponsor
If you like Lark, and want to see us grow, please consider [sponsoring us!](https://github.com/sponsors/lark-parser)
## Contact the author
Questions about code are best asked on [gitter](https://gitter.im/lark-parser/Lobby) or in the issues.
For anything else, I can be reached by email at erezshin at gmail com.
-- [Erez](https://github.com/erezsh)
---
## File: docs/classes.rst
API Reference
=============
Lark
----
.. autoclass:: lark.Lark
:members: open, parse, parse_interactive, scan, lex, save, load, get_terminal, open_from_package
Using Unicode character classes with ``regex``
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Python's builtin ``re`` module has a few persistent known bugs and also won't parse
advanced regex features such as character classes.
With ``pip install lark[regex]``, the ``regex`` module will be
installed alongside lark and can act as a drop-in replacement to ``re``.
Any instance of Lark instantiated with ``regex=True`` will use the ``regex`` module instead of ``re``.
For example, we can use character classes to match PEP-3131 compliant Python identifiers:
::
from lark import Lark
>>> g = Lark(r"""
?start: NAME
NAME: ID_START ID_CONTINUE*
ID_START: /[\p{Lu}\p{Ll}\p{Lt}\p{Lm}\p{Lo}\p{Nl}_]+/
ID_CONTINUE: ID_START | /[\p{Mn}\p{Mc}\p{Nd}\p{Pc}·]+/
""", regex=True)
>>> g.parse('வணக்கம்')
'வணக்கம்'
Tree
----
.. autoclass:: lark.Tree
:members: pretty, find_pred, find_data, iter_subtrees, scan_values,
iter_subtrees_topdown, __rich__
Token
-----
.. autoclass:: lark.Token
Transformer, Visitor & Interpreter
----------------------------------
See :doc:`visitors`.
ForestVisitor, ForestTransformer, & TreeForestTransformer
-----------------------------------------------------------
See :doc:`forest`.
UnexpectedInput
---------------
.. autoclass:: lark.exceptions.UnexpectedInput
:members: get_context, match_examples
.. autoclass:: lark.exceptions.UnexpectedToken
.. autoclass:: lark.exceptions.UnexpectedCharacters
.. autoclass:: lark.exceptions.UnexpectedEOF
InteractiveParser
-----------------
.. autoclass:: lark.parsers.lalr_interactive_parser.InteractiveParser
:members: choices, feed_token, copy, pretty, resume_parse, exhaust_lexer, accepts, as_immutable
.. autoclass:: lark.parsers.lalr_interactive_parser.ImmutableInteractiveParser
:members: choices, feed_token, copy, pretty, resume_parse, exhaust_lexer, accepts, as_mutable
ast_utils
---------
For an example of using ``ast_utils``, see `/examples/advanced/create_ast.py`_
.. autoclass:: lark.ast_utils.Ast
.. autoclass:: lark.ast_utils.AsList
.. autofunction:: lark.ast_utils.create_transformer
.. _/examples/advanced/create_ast.py: examples/advanced/create_ast.html
Indenter
--------
.. autoclass:: lark.indenter.Indenter
:members: NL_type, OPEN_PAREN_types, CLOSE_PAREN_types, INDENT_type, DEDENT_type, tab_len
.. autoclass:: lark.indenter.PythonIndenter
TextSlice
---------
.. autoclass:: lark.utils.TextSlice
ScanMatch
---------
A single match yielded by :meth:`Lark.scan`.
.. autoclass:: lark.ScanMatch
---
## File: docs/features.md
# Features
## Main Features
- Earley parser, capable of parsing any context-free grammar
- Implements SPPF, for efficient parsing and storing of ambiguous grammars.
- LALR(1) parser, limited in power of expression, but very efficient in space and performance (O(n)).
- Implements a parse-aware lexer that provides a better power of expression than traditional LALR implementations (such as ply).
- EBNF-inspired grammar, with extra features (See: [Grammar Reference](grammar.md))
- Builds a parse-tree (AST) automagically based on the grammar
- Stand-alone parser generator - create a small independent parser to embed in your project. ([read more](tools.html#stand-alone-parser))
- Flexible error handling by using an interactive parser interface (LALR only)
- Automatic line & column tracking (for both tokens and matched rules)
- Automatic terminal collision resolution
- Warns on regex collisions using the optional `interegular` library. ([read more](how_to_use.html#regex-collisions))
- Grammar composition - Import terminals and rules from other grammars (see [example](https://github.com/lark-parser/lark/tree/master/examples/composition)).
- Standard library of terminals (strings, numbers, names, etc.)
- Unicode fully supported
- Extensive test suite
- Type annotations (MyPy support)
- Pure-Python implementation
[Read more about the parsers](parsers.md)
## Extra features
- `Lark.scan()` for finding non-overlapping grammar matches embedded in arbitrary text (LALR only — see [recipes](recipes.html#extract-grammar-matches-from-arbitrary-text-with-lark-scan))
- Support for external regex module ([see here](classes.html#using-unicode-character-classes-with-regex))
- Import grammars from Nearley.js ([read more](tools.html#importing-grammars-from-nearleyjs))
- CYK parser
- Visualize your parse trees as dot or png files ([see_example](https://github.com/lark-parser/lark/blob/master/examples/fruitflies.py))
- Automatic reconstruction of input from parse-tree (see [example](https://github.com/lark-parser/lark/blob/master/examples/advanced/reconstruct_json.py) and [another example](https://github.com/lark-parser/lark/blob/master/examples/advanced/reconstruct_python.py))
- Use Lark grammars in [Julia](https://github.com/jamesrhester/Lerche.jl) and [Javascript](https://github.com/lark-parser/Lark.js).
---
## File: docs/forest.rst
Working with the SPPF
=====================
When parsing with Earley, Lark provides the ``ambiguity='forest'`` option
to obtain the shared packed parse forest (SPPF) produced by the parser as
an alternative to it being automatically converted to a tree.
Lark provides a few tools to facilitate working with the SPPF. Here are some
things to consider when deciding whether or not to use the SPPF.
**Pros**
- Efficient storage of highly ambiguous parses
- Precise handling of ambiguities
- Custom rule prioritizers
- Ability to handle infinite ambiguities
- Directly transform forest -> object instead of forest -> tree -> object
**Cons**
- More complex than working with a tree
- SPPF may contain nodes corresponding to rules generated internally
- Loss of Lark grammar features:
- Rules starting with '_' are not inlined in the SPPF
- Rules starting with '?' are never inlined in the SPPF
- All tokens will appear in the SPPF
SymbolNode
----------
.. autoclass:: lark.parsers.earley_forest.SymbolNode
:members: is_ambiguous, children
PackedNode
----------
.. autoclass:: lark.parsers.earley_forest.PackedNode
:members: children
ForestVisitor
-------------
.. autoclass:: lark.parsers.earley_forest.ForestVisitor
:members: visit, visit_symbol_node_in, visit_symbol_node_out,
visit_packed_node_in, visit_packed_node_out,
visit_token_node, on_cycle, get_cycle_in_path
ForestTransformer
-----------------
.. autoclass:: lark.parsers.earley_forest.ForestTransformer
:members: transform, transform_symbol_node, transform_intermediate_node,
transform_packed_node, transform_token_node
TreeForestTransformer
---------------------
.. autoclass:: lark.parsers.earley_forest.TreeForestTransformer
:members: __default__, __default_token__, __default_ambig__
handles_ambiguity
-----------------
.. autofunction:: lark.parsers.earley_forest.handles_ambiguity
---
## File: docs/grammar.md
# Grammar Reference
## Definitions
A **grammar** is a list of rules and terminals, that together define a language.
Terminals define the alphabet of the language, while rules define its structure.
In Lark, a terminal may be a string, a regular expression, or a concatenation of these and other terminals.
Each rule is a list of terminals and rules, whose location and nesting define the structure of the resulting parse-tree.
A **parsing algorithm** is an algorithm that takes a grammar definition and a sequence of symbols (members of the alphabet), and matches the entirety of the sequence by searching for a structure that is allowed by the grammar.
### General Syntax and notes
Grammars in Lark are based on [EBNF](https://en.wikipedia.org/wiki/Extended_Backus–Naur_form) syntax, with several enhancements.
EBNF is basically a short-hand for common BNF patterns.
Optionals are expanded:
```ruby
a b? c -> (a c | a b c)
```
Repetition is extracted into a recursion:
```ruby
a: b* -> a: _b_tag
_b_tag: (_b_tag b)?
```
And so on.
Lark grammars are composed of a list of definitions and directives, each on its own line. A definition is either a named rule, or a named terminal, with the following syntax, respectively:
```html
rule:
| etc.
TERM: // Rules aren't allowed
```
**Comments** start with
either `//` (C++ style) or `#` (Python style, since version 1.1.6)
and last to the end of the line.
Lark begins the parse with the rule 'start', unless specified otherwise in the options.
Names of rules are always in lowercase, while names of terminals are always in uppercase. This distinction has practical effects, for the shape of the generated parse-tree, and the automatic construction of the lexer (aka tokenizer, or scanner).
## Terminals
Terminals are used to match text into symbols. They can be defined as a combination of literals and other terminals.
**Syntax:**
```html
[. ] :
```
Terminal names must be uppercase.
Literals can be one of:
* `"string"`
* `/regular expression+/`
* `"case-insensitive string"i`
* `/re with flags/imulx`
* Literal range: `"a".."z"`, `"1".."9"`, etc.
Terminals also support grammar operators, such as `|`, `+`, `*` and `?`.
Terminals are a linear construct, and therefore may not contain themselves (recursion isn't allowed).
### Templates
Templates are expanded when preprocessing the grammar.
Definition syntax:
```javascript
my_template{param1, param2, ...}:
```
Use syntax:
```javascript
some_rule: my_template{arg1, arg2, ...}
```
Example:
```javascript
_separated{x, sep}: x (sep x)* // Define a sequence of 'x sep x sep x ...'
num_list: "[" _separated{NUMBER, ","} "]" // Will match "[1, 2, 3]" etc.
```
### Priority
Terminals can be assigned a priority to influence lexing. Terminal priorities
are signed integers with a default value of 0.
When using a lexer, the highest priority terminals are always matched first.
When using Earley's dynamic lexing, terminal priorities are used to prefer
certain lexings and resolve ambiguity.
### Regexp Flags
You can use flags on regexps and strings. For example:
```perl
SELECT: "select"i //# Will ignore case, and match SELECT or Select, etc.
MULTILINE_TEXT: /.+/s
SIGNED_INTEGER: /
[+-]? # the sign
(0|[1-9][0-9]*) # the digits
/x
```
Supported flags are one of: `imslux`. See Python's regex documentation for more details on each one.
Regexps/strings of different flags can only be concatenated in Python 3.6+
#### Notes for when using a lexer:
When using a lexer (basic or contextual), it is the grammar-author's responsibility to make sure the literals don't collide, or that if they do, they are matched in the desired order. Literals are matched according to the following precedence:
1. Highest priority first (priority is specified as: TERM.number: ...)
2. Length of match (for regexps, the longest theoretical match is used)
3. Length of literal / pattern definition
4. Name
**Examples:**
```perl
IF: "if"
INTEGER : /[0-9]+/
INTEGER2 : ("0".."9")+ //# Same as INTEGER
DECIMAL.2: INTEGER? "." INTEGER //# Will be matched before INTEGER
WHITESPACE: (" " | /\t/ )+
SQL_SELECT: "select"i
```
### Regular expressions & Ambiguity
Each terminal is eventually compiled to a regular expression. All the operators and references inside it are mapped to their respective expressions.
For example, in the following grammar, `A1` and `A2`, are equivalent:
```perl
A1: "a" | "b"
A2: /a|b/
```
This means that inside terminals, Lark cannot detect or resolve ambiguity, even when using Earley.
For example, for this grammar:
```perl
start : (A | B)+
A : "a" | "ab"
B : "b"
```
We get only one possible derivation, instead of two:
```bash
>>> p = Lark(g, ambiguity="explicit")
>>> p.parse("ab")
Tree('start', [Token('A', 'ab')])
```
This is happening because Python's regex engine always returns the best matching option. There is no way to access the alternatives.
If you find yourself in this situation, the recommended solution is to either use the "dynamic_complete" lexer, or use rules instead.
Example using rules:
```python
>>> p = Lark("""start: (a | b)+
... !a: "a" | "ab"
... !b: "b"
... """, ambiguity="explicit")
>>> print(p.parse("ab").pretty())
_ambig
start
a ab
start
a a
b b
```
Example using dynamic-complete:
```python
>>> g = """
... start: (A | B)+
... A : "a" | "ab"
... B : "b"
... """
>>> p = Lark(g, ambiguity="explicit", lexer="dynamic_complete")
>>> rich.print(p.parse("ab"))
_ambig
├── start
│ └── ab
└── start
├── a
└── b
```
(note: the dynamic-complete lexer can significantly affect the performance of the parser)
## Rules
**Syntax:**
```html
: [-> ]
| ...
```
Names of rules and aliases are always in lowercase.
Rule definitions can be extended to the next line by using the OR operator (signified by a pipe: `|` ).
An alias is a name for the specific rule alternative. It affects tree construction.
Each item is one of:
* `rule`
* `TERMINAL`
* `"string literal"` or `/regexp literal/`
* `(item item ..)` - Group items
* `[item item ..]` - Maybe. Same as `(item item ..)?`, but when `maybe_placeholders=True`, generates `None` if there is no match.
* `item?` - Zero or one instances of item ("maybe")
* `item*` - Zero or more instances of item
* `item+` - One or more instances of item
* `item ~ n` - Exactly *n* instances of item
* `item ~ n..m` - Between *n* to *m* instances of item (not recommended for wide ranges, due to performance issues)
Note that all operators, including `~ n`, apply directly to the item on their left.
For instance `a ~ 2 b ~ 3` is parsed as `(a ~ 2) (b ~ 3)`.
**Examples:**
```perl
hello_world: "hello" "world"
mul: (mul "*")? number //# Left-recursion is allowed and encouraged!
expr: expr operator expr
| value //# Multi-line, belongs to expr
four_words: word ~ 4
```
### Priority
Like terminals, rules can be assigned a priority. Rule priorities are signed
integers with a default value of 0.
When using LALR, the highest priority rules are used to resolve collision errors.
When using Earley, rule priorities are used to resolve ambiguity.
## Directives
### %ignore
All occurrences of the terminal will be ignored, and won't be part of the parse.
Using the `%ignore` directive results in a cleaner grammar.
It's especially important for the LALR(1) algorithm, because adding whitespace (or comments, or other extraneous elements) explicitly in the grammar, harms its predictive abilities, which are based on a lookahead of 1.
**Syntax:**
```html
%ignore
```
**Examples:**
```perl
%ignore " "
COMMENT: "#" /[^\n]/*
%ignore COMMENT
```
### %import
Allows one to import terminals and rules from lark grammars.
When importing rules, all their dependencies will be imported into a namespace, to avoid collisions. To override any of their dependencies (e.g. like you would override methods when inheriting a class), use the ``%override`` directive.
**Syntax:**
```html
%import .
%import .
%import . ->
%import . ->
%import (, , , )
```
If the module path is absolute, Lark will attempt to load it from the built-in directory (which currently contains `common.lark`, `lark.lark`, `python.lark`, and `unicode.lark`).
If the module path is relative, such as `.path.to.file`, Lark will attempt to load it from the current working directory. Grammars must have the `.lark` extension.
The rule or terminal can be imported under another name (an alias) with the `->` syntax.
**Example:**
```perl
%import common.NUMBER
%import .terminals_file (A, B, C)
%import .rules_file.rule_a -> rule_b
```
Note that `%ignore` directives cannot be imported. Imported rules will abide by the `%ignore` directives declared in the main grammar.
### %declare
Declare a terminal without defining it. Useful for plugins.
### %override
Override a rule or terminals, affecting all references to it, even in imported grammars.
Useful for implementing an inheritance pattern when importing grammars.
**Example:**
```perl
%import my_grammar (start, number, NUMBER)
// Add hex support to my_grammar
%override number: NUMBER | /0x\w+/
```
### %extend
Extend the definition of a rule or terminal, e.g. add a new option on what it can match, like when separated with `|`.
Useful for splitting up a definition of a complex rule with many different options over multiple files.
Can also be used to implement a plugin system where a core grammar is extended by others.
**Example:**
```perl
%import my_grammar (start, NUMBER)
// Add hex support to my_grammar
%extend NUMBER: /0x\w+/
```
For both `%extend` and `%override`, there is not requirement for a rule/terminal to come from another file, but that is probably the most common use-case.
---
## File: docs/how_to_develop.md
# How to develop Lark - Guide
There are many ways you can help the project:
* Help solve issues
* Improve the documentation
* Write new grammars for Lark's library
* Write a blog post introducing Lark to your audience
* Port Lark to another language
* Help with code development
If you're interested in taking one of these on, contact us on [Gitter](https://gitter.im/lark-parser/Lobby) or [Github Discussion](https://github.com/lark-parser/lark/discussions), and we will provide more details and assist you in the process.
## Code Style
Lark does not follow a predefined code style.
We accept any code style that makes sense, as long as it's Pythonic and easy to read.
## Unit Tests
Lark comes with an extensive set of tests. Many of the tests will run several times, once for each parser configuration.
To run the tests, just go to the lark project root, and run the command:
```bash
python -m tests
```
or
```bash
pypy -m tests
```
For a list of supported interpreters, you can consult the `tox.ini` file.
You can also run a single unittest using its class and method name, for example:
```bash
## test_package test_class_name.test_function_name
python -m tests TestLalrBasic.test_keep_all_tokens
```
### tox
To run all Unit Tests with tox,
install tox and Python 2.7 up to the latest python interpreter supported (consult the file tox.ini).
Then,
run the command `tox` on the root of this project (where the main setup.py file is on).
And, for example,
if you would like to only run the Unit Tests for Python version 2.7,
you can run the command `tox -e py27`
### pytest
You can also run the tests using pytest:
```bash
pytest tests
```
### Using setup.py
Another way to run the tests is using setup.py:
```bash
python setup.py test
```
## Building the Documentation
To build the documentation:
```sh
cd docs/
pip install -r requirements.txt
make html
```
To review the result, open the built HTML files under `_build/html/` in your browser.
---
## File: docs/how_to_use.md
# How To Use Lark - Guide
## Work process
This is the recommended process for working with Lark:
1. Collect or create input samples, that demonstrate key features or behaviors in the language you're trying to parse.
2. Write a grammar. Try to aim for a structure that is intuitive, and in a way that imitates how you would explain your language to a fellow human.
3. Try your grammar in Lark against each input sample. Make sure the resulting parse-trees make sense.
4. Use Lark's grammar features to [shape the tree](tree_construction.md): Get rid of superfluous rules by inlining them, and use aliases when specific cases need clarification.
You can perform steps 1-4 repeatedly, gradually growing your grammar to include more sentences.
5. Create a transformer to evaluate the parse-tree into a structure you'll be comfortable to work with. This may include evaluating literals, merging branches, or even converting the entire tree into your own set of AST classes.
Of course, some specific use-cases may deviate from this process. Feel free to suggest these cases, and I'll add them to this page.
## Getting started
Browse the [Examples](https://github.com/lark-parser/lark/tree/master/examples) to find a template that suits your purposes.
Read the tutorials to get a better understanding of how everything works. (links in the [main page](/index))
Use the [Cheatsheet (PDF)](https://lark-parser.readthedocs.io/en/latest/_static/lark_cheatsheet.pdf) for quick reference.
Use the reference pages for more in-depth explanations. (links in the [main page](/index))
## Debug
Grammars may contain non-obvious bugs, usually caused by rules or terminals interfering with each other in subtle ways.
When trying to debug a misbehaving grammar, the following methodology is recommended:
1. Create a copy of the grammar, so you can change the parser/grammar without any worries
2. Find the minimal input that creates the error
3. Slowly remove rules from the grammar, while making sure the error still occurs.
Usually, by the time you get to a minimal grammar, the problem becomes clear.
But if it doesn't, feel free to ask us on gitter, or even open an issue. Post a reproducing code, with the minimal grammar and input, and we'll do our best to help.
### Regex collisions
A likely source of bugs occurs when two regexes in a grammar can match the same input. If both terminals have the same priority, most lexers would arbitrarily choose the first one that matches, which isn't always the desired one. (a notable exception is the `dynamic_complete` lexer, which always tries all variations. But its users pay for that with performance.)
These collisions can be hard to notice, and their effects can be difficult to debug, as they are subtle and sometimes hard to reproduce.
To help with these situations, Lark can utilize a new external library called `interegular`. If it is installed, Lark uses it to check for collisions, and warn about any conflicts that it can find:
```
import logging
from lark import Lark, logger
logger.setLevel(logging.WARN)
collision_grammar = '''
start: A | B
A: /a+/
B: /[ab]+/
'''
p = Lark(collision_grammar, parser='lalr')
# Output:
# Collision between Terminals B and A. The lexer will choose between them arbitrarily
# Example Collision: a
```
You can install interegular for Lark using `pip install 'lark[interegular]'`.
Note 1: Interegular currently only runs when the lexer is `basic` or `contextual`.
Note 2: Some advanced regex features, such as lookahead and lookbehind, may prevent interegular from detecting existing collisions.
### Shift/Reduce collisions
By default Lark automatically resolves Shift/Reduce conflicts as Shift. It produces notifications as debug messages.
when users pass `debug=True`, those notifications are written as warnings.
Either way, to get the messages printed you have to configure the `logger` beforehand. For example:
```python
import logging
from lark import Lark, logger
logger.setLevel(logging.DEBUG)
collision_grammar = '''
start: as as
as: a*
a: "a"
'''
p = Lark(collision_grammar, parser='lalr', debug=True)
# Shift/Reduce conflict for terminal A: (resolving as shift)
# *
# Shift/Reduce conflict for terminal A: (resolving as shift)
# *
```
### Strict-Mode
Lark, by default, accepts grammars with unresolved Shift/Reduce collisions (which it always resolves to shift), and regex collisions.
Strict-mode allows users to validate that their grammars don't contain these collisions.
When Lark is initialized with `strict=True`, it raises an exception on any Shift/Reduce or regex collision.
If `interegular` isn't installed, an exception is thrown.
When using strict-mode, users will be expected to resolve their collisions manually:
- To resolve Shift/Reduce collisions, adjust the priority weights of the rules involved, until there are no more collisions.
- To resolve regex collisions, change the involved regexes so that they can no longer both match the same input (Lark provides an example).
Strict-mode only applies to LALR for now.
```python
from lark import Lark
collision_grammar = '''
start: as as
as: a*
a: "a"
'''
p = Lark(collision_grammar, parser='lalr', strict=True)
# Traceback (most recent call last):
# ...
# lark.exceptions.GrammarError: Shift/Reduce conflict for terminal A. [strict-mode]
```
## Tools
### Stand-alone parser
Lark can generate a stand-alone LALR(1) parser from a grammar.
The resulting module provides the same interface as Lark, but with a fixed grammar, and reduced functionality.
Run using:
```bash
python -m lark.tools.standalone
```
For a play-by-play, read the [tutorial](http://blog.erezsh.com/create-a-stand-alone-lalr1-parser-in-python/)
### Import Nearley.js grammars
It is possible to import Nearley grammars into Lark. The Javascript code is translated using Js2Py.
See the [tools page](tools.md) for more information.
---
## File: docs/index.rst
.. Lark documentation master file, created by
sphinx-quickstart on Sun Aug 16 13:09:41 2020.
You can adapt this file completely to your liking, but it should at least
contain the root `toctree` directive.
Welcome to Lark's documentation!
================================
.. toctree::
:maxdepth: 2
:caption: Overview
:hidden:
philosophy
features
parsers
.. toctree::
:maxdepth: 2
:caption: Tutorials & Guides
:hidden:
json_tutorial
how_to_use
how_to_develop
recipes
examples/index
.. toctree::
:maxdepth: 2
:caption: Reference
:hidden:
grammar
tree_construction
classes
visitors
forest
tools
Lark is a modern parsing library for Python. Lark can parse any context-free grammar.
Lark provides:
- Advanced grammar language, based on EBNF
- Three parsing algorithms to choose from: Earley, LALR(1) and CYK
- Automatic tree construction, inferred from your grammar
- Fast unicode lexer with regexp support, and automatic line-counting
Install Lark
--------------
.. code:: bash
$ pip install lark
Syntax Highlighting
-------------------
- `Sublime Text & TextMate`_
- `Visual Studio Code`_ (Or install through the vscode plugin system)
- `Intellij & PyCharm`_
- `Vim`_
- `Atom`_
.. _Sublime Text & TextMate: https://github.com/lark-parser/lark_syntax
.. _Visual Studio Code: https://github.com/lark-parser/vscode-lark
.. _Intellij & PyCharm: https://github.com/lark-parser/intellij-syntax-highlighting
.. _Vim: https://github.com/lark-parser/vim-lark-syntax
.. _Atom: https://github.com/Alhadis/language-grammars
Resources
---------
- :doc:`philosophy`
- :doc:`features`
- `Examples`_
- `Third-party examples`_
- `Online IDE`_
- Tutorials
- `How to write a DSL`_ - Implements a toy LOGO-like language with
an interpreter
- :doc:`json_tutorial` - Teaches you how to use Lark
- Unofficial
- `Program Synthesis is Possible`_ - Creates a DSL for Z3
- `Using Lark to Parse Text - Robin Reynolds-Haertle (PyCascades 2023) `_ (video presentation)
- Guides
- :doc:`how_to_use`
- :doc:`how_to_develop`
- Reference
- :doc:`grammar`
- :doc:`tree_construction`
- :doc:`visitors`
- :doc:`forest`
- :doc:`classes`
- :doc:`tools`
- `Cheatsheet (PDF)`_
- Discussion
- `Gitter`_
- `Forum (Google Groups)`_
.. _Examples: https://github.com/lark-parser/lark/tree/master/examples
.. _Third-party examples: https://github.com/ligurio/lark-grammars
.. _Online IDE: https://lark-parser.org/ide
.. _How to write a DSL: https://eshsoft.com/blog/write-dsl-in-python-with-lark
.. _Program Synthesis is Possible: https://www.cs.cornell.edu/~asampson/blog/minisynth.html
.. _Cheatsheet (PDF): _static/lark_cheatsheet.pdf
.. _Gitter: https://gitter.im/lark-parser/Lobby
.. _Forum (Google Groups): https://groups.google.com/forum/#!forum/lark-parser
---
## File: docs/json_tutorial.md
# JSON parser - Tutorial
Lark is a parser - a program that accepts a grammar and text, and produces a structured tree that represents that text.
In this tutorial we will write a JSON parser in Lark, and explore Lark's various features in the process.
It has 5 parts.
1. Writing the grammar
2. Creating the parser
3. Shaping the tree
4. Evaluating the tree
5. Optimizing
Knowledge assumed:
- Using Python
- A basic understanding of how to use regular expressions
## Part 1 - The Grammar
Lark accepts its grammars in a format called [EBNF](https://www.wikiwand.com/en/Extended_Backus%E2%80%93Naur_form). It basically looks like this:
rule_name : list of rules and TERMINALS to match
| another possible list of items
| etc.
TERMINAL: "some text to match"
(*a terminal is a string or a regular expression*)
The parser will try to match each rule (left-part) by matching its items (right-part) sequentially, trying each alternative (In practice, the parser is predictive so we don't have to try every alternative).
How to structure those rules is beyond the scope of this tutorial, but often it's enough to follow one's intuition.
In the case of JSON, the structure is simple: A json document is either a list, or a dictionary, or a string/number/etc.
The dictionaries and lists are recursive, and contain other json documents (or "values").
Let's write this structure in EBNF form:
```lark
value: dict
| list
| STRING
| NUMBER
| "true" | "false" | "null"
list : "[" [value ("," value)*] "]"
dict : "{" [pair ("," pair)*] "}"
pair : STRING ":" value
```
A quick explanation of the syntax:
- Parenthesis let us group rules together.
- rule\* means *any amount*. That means, zero or more instances of that rule.
- [rule] means *optional*. That means zero or one instance of that rule.
Lark also supports the rule+ operator, meaning one or more instances. It also supports the rule? operator which is another way to say *optional*.
Of course, we still haven't defined "STRING" and "NUMBER". Luckily, both these literals are already defined in Lark's common library:
```lark
%import common.ESCAPED_STRING -> STRING
%import common.SIGNED_NUMBER -> NUMBER
```
The arrow (->) renames the terminals. But that only adds obscurity in this case, so going forward we'll just use their original names.
We'll also take care of the white-space, which is part of the text, by simply matching and then throwing it away.
```lark
%import common.WS
%ignore WS
```
We tell our parser to ignore whitespace. Otherwise, we'd have to fill our grammar with WS terminals.
By the way, if you're curious what these terminals signify, they are roughly equivalent to this:
```lark
NUMBER : /-?\d+(\.\d+)?([eE][+-]?\d+)?/
STRING : /".*?(?>> text = '{"key": ["item0", "item1", 3.14]}'
>>> json_parser.parse(text)
Tree(value, [Tree(dict, [Tree(pair, [Token(STRING, "key"), Tree(value, [Tree(list, [Tree(value, [Token(STRING, "item0")]), Tree(value, [Token(STRING, "item1")]), Tree(value, [Token(NUMBER, 3.14)])])])])])])
>>> print( _.pretty() )
value
dict
pair
"key"
value
list
value "item0"
value "item1"
value 3.14
```
As promised, Lark automagically creates a tree that represents the parsed text.
But something is suspiciously missing from the tree. Where are the curly braces, the commas and all the other punctuation literals?
Lark automatically filters out literals from the tree, based on the following criteria:
- Filter out string literals without a name, or with a name that starts with an underscore.
- Keep regexps, even unnamed ones, unless their name starts with an underscore.
Unfortunately, this means that it will also filter out literals like "true" and "false", and we will lose that information. The next section, "Shaping the tree" deals with this issue, and others.
## Part 3 - Shaping the Tree
We now have a parser that can create a parse tree (or: AST), but the tree has some issues:
1. "true", "false" and "null" are filtered out (test it out yourself!)
2. Is has useless branches, like *value*, that clutter-up our view.
I'll present the solution, and then explain it:
```lark
?value: dict
| list
| string
| SIGNED_NUMBER -> number
| "true" -> true
| "false" -> false
| "null" -> null
...
string : ESCAPED_STRING
```
1. Those little arrows signify *aliases*. An alias is a name for a specific part of the rule. In this case, we will name the *true/false/null* matches, and this way we won't lose the information. We also alias *SIGNED_NUMBER* to mark it for later processing.
2. The question-mark prefixing *value* ("?value") tells the tree-builder to inline this branch if it has only one member. In this case, *value* will always have only one member, and will always be inlined.
3. We turned the *ESCAPED_STRING* terminal into a rule. This way it will appear in the tree as a branch. This is equivalent to aliasing (like we did for the number), but now *string* can also be used elsewhere in the grammar (namely, in the *pair* rule).
Here is the new grammar:
```python
from lark import Lark
json_parser = Lark(r"""
?value: dict
| list
| string
| SIGNED_NUMBER -> number
| "true" -> true
| "false" -> false
| "null" -> null
list : "[" [value ("," value)*] "]"
dict : "{" [pair ("," pair)*] "}"
pair : string ":" value
string : ESCAPED_STRING
%import common.ESCAPED_STRING
%import common.SIGNED_NUMBER
%import common.WS
%ignore WS
""", start='value')
```
And let's test it out:
```python
>>> text = '{"key": ["item0", "item1", 3.14, true]}'
>>> print( json_parser.parse(text).pretty() )
dict
pair
string "key"
list
string "item0"
string "item1"
number 3.14
true
```
Ah! That is much much nicer.
## Part 4 - Evaluating the tree
It's nice to have a tree, but what we really want is a JSON object.
The way to do it is to evaluate the tree, using a Transformer.
A transformer is a class with methods corresponding to branch names. For each branch, the appropriate method will be called with the children of the branch as its argument, and its return value will replace the branch in the tree.
So let's write a partial transformer, that handles lists and dictionaries:
```python
from lark import Transformer
class MyTransformer(Transformer):
def list(self, items):
return list(items)
def pair(self, key_value):
k, v = key_value
return k, v
def dict(self, items):
return dict(items)
```
And when we run it, we get this:
```python
>>> tree = json_parser.parse(text)
>>> MyTransformer().transform(tree)
{Tree(string, [Token(ANONRE_1, "key")]): [Tree(string, [Token(ANONRE_1, "item0")]), Tree(string, [Token(ANONRE_1, "item1")]), Tree(number, [Token(ANONRE_0, 3.14)]), Tree(true, [])]}
```
This is pretty close. Let's write a full transformer that can handle the terminals too.
Also, our definitions of list and dict are a bit verbose. We can do better:
```python
from lark import Transformer
class TreeToJson(Transformer):
def string(self, s):
(s,) = s
return s[1:-1]
def number(self, n):
(n,) = n
return float(n)
list = list
pair = tuple
dict = dict
null = lambda self, _: None
true = lambda self, _: True
false = lambda self, _: False
```
And when we run it:
```python
>>> tree = json_parser.parse(text)
>>> TreeToJson().transform(tree)
{u'key': [u'item0', u'item1', 3.14, True]}
```
Magic!
## Part 5 - Optimizing
### Step 1 - Benchmark
By now, we have a fully working JSON parser, that can accept a string of JSON, and return its Pythonic representation.
But how fast is it?
Now, of course there are JSON libraries for Python written in C, and we can never compete with them. But since this is applicable to any parser you would write in Lark, let's see how far we can take this.
The first step for optimizing is to have a benchmark. For this benchmark I'm going to take data from [json-generator.com/](http://www.json-generator.com/). I took their default suggestion and changed it to 5000 objects. The result is a 6.6MB sparse JSON file.
Our first program is going to be just a concatenation of everything we've done so far:
```python
import sys
from lark import Lark, Transformer
json_grammar = r"""
?value: dict
| list
| string
| SIGNED_NUMBER -> number
| "true" -> true
| "false" -> false
| "null" -> null
list : "[" [value ("," value)*] "]"
dict : "{" [pair ("," pair)*] "}"
pair : string ":" value
string : ESCAPED_STRING
%import common.ESCAPED_STRING
%import common.SIGNED_NUMBER
%import common.WS
%ignore WS
"""
class TreeToJson(Transformer):
def string(self, s):
(s,) = s
return s[1:-1]
def number(self, n):
(n,) = n
return float(n)
list = list
pair = tuple
dict = dict
null = lambda self, _: None
true = lambda self, _: True
false = lambda self, _: False
json_parser = Lark(json_grammar, start='value', lexer='basic')
if __name__ == '__main__':
with open(sys.argv[1]) as f:
tree = json_parser.parse(f.read())
print(TreeToJson().transform(tree))
```
We run it and get this:
$ time python tutorial_json.py json_data > /dev/null
real 0m36.257s
user 0m34.735s
sys 0m1.361s
That's unsatisfactory time for a 6MB file. Maybe if we were parsing configuration or a small DSL, but we're trying to handle large amount of data here.
Well, turns out there's quite a bit we can do about it!
### Step 2 - LALR(1)
So far we've been using the Earley algorithm, which is the default in Lark. Earley is powerful but slow. But it just so happens that our grammar is LR-compatible, and specifically LALR(1) compatible.
So let's switch to LALR(1) and see what happens:
```python
json_parser = Lark(json_grammar, start='value', parser='lalr')
```
$ time python tutorial_json.py json_data > /dev/null
real 0m7.554s
user 0m7.352s
sys 0m0.148s
Ah, that's much better. The resulting JSON is of course exactly the same. You can run it for yourself and see.
It's important to note that not all grammars are LR-compatible, and so you can't always switch to LALR(1). But there's no harm in trying! If Lark lets you build the grammar, it means you're good to go.
### Step 3 - Tree-less LALR(1)
So far, we've built a full parse tree for our JSON, and then transformed it. It's a convenient method, but it's not the most efficient in terms of speed and memory. Luckily, Lark lets us avoid building the tree when parsing with LALR(1).
Here's the way to do it:
```python
json_parser = Lark(json_grammar, start='value', parser='lalr', transformer=TreeToJson())
if __name__ == '__main__':
with open(sys.argv[1]) as f:
print( json_parser.parse(f.read()) )
```
We've used the transformer we've already written, but this time we plug it straight into the parser. Now it can avoid building the parse tree, and just send the data straight into our transformer. The *parse()* method now returns the transformed JSON, instead of a tree.
Let's benchmark it:
real 0m4.866s
user 0m4.722s
sys 0m0.121s
That's a measurable improvement! Also, this way is more memory efficient. Check out the benchmark table at the end to see just how much.
As a general practice, it's recommended to work with parse trees, and only skip the tree-builder when your transformer is already working.
### Step 4 - PyPy
PyPy is a JIT engine for running Python, and it's designed to be a drop-in replacement.
Lark is written purely in Python, which makes it very suitable for PyPy.
Let's get some free performance:
$ time pypy tutorial_json.py json_data > /dev/null
real 0m1.397s
user 0m1.296s
sys 0m0.083s
PyPy is awesome!
### Conclusion
We've brought the run-time down from 36 seconds to 1.1 seconds, in a series of small and simple steps.
Now let's compare the benchmarks in a nicely organized table.
I measured memory consumption using a little script called [memusg](https://gist.github.com/netj/526585)
| Code | CPython Time | PyPy Time | CPython Mem | PyPy Mem
|:-----|:-------------|:------------|:----------|:---------
| Lark - Earley *(with lexer)* | 42s | 4s | 1167M | 608M |
| Lark - LALR(1) | 8s | 1.53s | 453M | 266M |
| Lark - LALR(1) tree-less | 4.76s | 1.23s | 70M | 134M |
| PyParsing ([Parser](https://github.com/pyparsing/pyparsing/blob/master/examples/jsonParser.py)) | 32s | 3.53s | 443M | 225M |
| funcparserlib ([Parser](https://github.com/vlasovskikh/funcparserlib/blob/master/tests/json.py)) | 8.5s | 1.3s | 483M | 293M |
| Parsimonious ([Parser](https://gist.github.com/reclosedev/5222560)) | ? | 5.7s | ? | 1545M |
I added a few other parsers for comparison. PyParsing and funcparselib fair pretty well in their memory usage (they don't build a tree), but they can't compete with the run-time speed of LALR(1).
These benchmarks are for Lark's alpha version. I already have several optimizations planned that will significantly improve run-time speed.
Once again, shout-out to PyPy for being so effective.
## Afterword
This is the end of the tutorial. I hoped you liked it and learned a little about Lark.
To see what else you can do with Lark, check out the [examples](/examples).
Read the documentation here: https://lark-parser.readthedocs.io/en/latest/
---
## File: docs/parsers.md
# Parsers
Lark implements the following parsing algorithms: Earley, LALR(1), and CYK
## Earley
An [Earley Parser](https://www.wikiwand.com/en/Earley_parser) is a chart parser capable of parsing any context-free grammar at O(n^3), and O(n^2) when the grammar is unambiguous. It can parse most LR grammars at O(n). Most programming languages are LR, and can be parsed at a linear time.
Lark's Earley implementation runs on top of a skipping chart parser, which allows it to use regular expressions, instead of matching characters one-by-one. This is a huge improvement to Earley that is unique to Lark. This feature is used by default, but can also be requested explicitly using `lexer='dynamic'`.
It's possible to bypass the dynamic lexing, and use the regular Earley parser with a basic lexer, that tokenizes as an independent first step. Doing so will provide a speed benefit, but will tokenize without using Earley's ambiguity-resolution ability. So choose this only if you know why! Activate with `lexer='basic'`
**SPPF & Ambiguity resolution**
Lark implements the Shared Packed Parse Forest data-structure for the Earley parser, in order to reduce the space and computation required to handle ambiguous grammars.
You can read more about SPPF [here](https://web.archive.org/web/20191229100607/www.bramvandersanden.com/post/2014/06/shared-packed-parse-forest)
As a result, Lark can efficiently parse and store every ambiguity in the grammar, when using Earley.
Lark provides the following options to combat ambiguity:
1) Lark will choose the best derivation for you (default). Users can choose between different disambiguation strategies, and can prioritize (or demote) individual rules over others, using the rule-priority syntax.
2) Users may choose to receive the set of all possible parse-trees (using ambiguity='explicit'), and choose the best derivation themselves. While simple and flexible, it comes at the cost of space and performance, and so it isn't recommended for highly ambiguous grammars, or very long inputs.
3) As an advanced feature, users may use specialized visitors to iterate the SPPF themselves. There is also [a 3rd party utility for iterating over the SPPF](https://github.com/chanicpanic/lark-ambig-tools).
**lexer="dynamic_complete"**
Earley's "dynamic" lexer uses regular expressions in order to tokenize the text. It tries every possible combination of terminals, but it matches each terminal exactly once, returning the longest possible match.
That means, for example, that when `lexer="dynamic"` (which is the default), the terminal `/a+/`, when given the text `"aa"`, will return one result, `aa`, even though `a` would also be correct.
This behavior was chosen because it is much faster, and it is usually what you would expect.
Setting `lexer="dynamic_complete"` instructs the lexer to consider every possible regexp match. This ensures that the parser will consider and resolve every ambiguity, even inside the terminals themselves. This lexer provides the same capabilities as scannerless Earley, but with different performance tradeoffs.
Warning: This lexer can be much slower, especially for open-ended terminals such as `/.*/`
## LALR(1)
[LALR(1)](https://www.wikiwand.com/en/LALR_parser) is a very efficient, true-and-tested parsing algorithm. It's incredibly fast and requires very little memory. It can parse most programming languages (For example: Python and Java).
LALR(1) stands for:
- Left-to-right parsing order
- Rightmost derivation, bottom-up
- Lookahead of 1 token
Lark comes with an efficient implementation that outperforms every other parsing library for Python (including PLY)
Lark extends the traditional YACC-based architecture with a *contextual lexer*, which processes feedback from the parser, making the LALR(1) algorithm stronger than ever.
The contextual lexer communicates with the parser, and uses the parser's lookahead prediction to narrow its choice of terminals. So at each point, the lexer only matches the subgroup of terminals that are legal at that parser state, instead of all of the terminals. It’s surprisingly effective at resolving common terminal collisions, and allows one to parse languages that LALR(1) was previously incapable of parsing.
(If you're familiar with YACC, you can think of it as automatic lexer-states)
This is an improvement to LALR(1) that is unique to Lark.
### Grammar constraints in LALR(1)
Due to having only a lookahead of one token, LALR is limited in its ability to choose between rules, when they both match the input.
Tips for writing a conforming grammar:
- Try to avoid writing different rules that can match the same sequence of characters.
- For the best performance, prefer left-recursion over right-recursion.
- Consider setting terminal priority only as a last resort.
For a better understanding of these constraints, it's recommended to learn how a SLR parser works. SLR is very similar to LALR but much simpler.
## CYK Parser
A [CYK parser](https://www.wikiwand.com/en/CYK_algorithm) can parse any context-free grammar at O(n^3*|G|).
Its too slow to be practical for simple grammars, but it offers good performance for highly ambiguous grammars.