lark parsing library

Lark is a modern parsing library for Python capable of parsing any context-free grammar. Key features include:

• Advanced grammar language: Based on EBNF.
• Multiple parsing algorithms: Choose from Earley, LALR(1), and CYK.
• Automatic tree construction: Trees are automatically inferred from your grammar.
• Fast unicode lexer: Includes regexp support and automatic line-counting.

Lark provides two main parsing algorithms that allow you to trade off power and speed:

• Earley: A powerful parser that can handle all context-free grammars, including highly ambiguous ones.
• LALR(1): A fast and lightweight parser suitable for deterministic grammars. It can also be used to generate a stand-alone parser.

Lark provides different parser implementations depending on your grammar complexity and performance requirements:

• Earley parser: Capable of parsing any context-free grammar. It implements SPPF (Shared Packed Parse Forest) for efficient parsing and storing of ambiguous grammars.
• LALR(1) parser: Highly efficient in space and performance (O(n)). It uses a parse-aware lexer that offers more expressive power than traditional LALR implementations like ply.
• CYK parser: An additional parser implementation available in Lark.

Lark provides a tool to convert grammars from Nearley (a Javascript Earley library) into Python modules. This process uses Js2Py to convert and execute Javascript postprocessing code segments.

Requirements

1. Install Lark with the nearley component:

pip install lark[nearley]

2. Acquire a copy of the Nearley codebase via git.

Usage

Run the converter using the following command structure: python -m lark.tools.nearley <grammar.ne> <start_rule> <path_to_nearley_repo>

Limitations

• Lark cannot import templates from Nearley.
• Lark cannot export grammars to Nearley.

git clone https://github.com/Hardmath123/nearley
python -m lark.tools.nearley nearley/examples/calculator/arithmetic.ne main ./nearley > ncalc.py

When using the Earley parser, you can obtain the Shared Packed Parse Forest (SPPF) instead of a standard tree by passing the ambiguity='forest' option to the parser. This is useful for efficiently storing highly ambiguous parses and handling infinite ambiguities, though it is more complex than working with a standard tree.

Note on Grammar Features in SPPF:

• Rules starting with _ are not inlined.
• Rules starting with ? are never inlined.
• All tokens will appear in the SPPF.

By default, Lark filters out certain terminals (like unnamed literals or terminals starting with _) to reduce tree noise. To force a rule to retain all its terminals (including literals) as nodes in the tree, prefix the rule name with an exclamation mark !.

!expr: "(" expr ")"
     | NAME+
NAME: /\w+/
%ignore " "

When using the LALR(1) parser, you can avoid the overhead of building a full parse tree by passing a Transformer directly to the Lark constructor via the transformer argument.

When a transformer is provided this way, the .parse() method returns the transformed data directly instead of a tree structure. This is more memory-efficient and faster for large datasets. It is recommended to use this approach only once your transformer logic is already verified and working.

When building a parser with Lark, follow this iterative workflow:

1. Collect Samples: Gather input samples that demonstrate the key features and behaviors of your target language.
2. Write a Grammar: Create a grammar that is intuitive and imitates how you would explain the language naturally.
3. Test against Samples: Run your grammar against your input samples and verify that the resulting parse-trees are correct.
4. Shape the Tree: Use Lark's grammar features (like inlining rules or using aliases) to refine the tree structure and remove superfluous nodes.
5. Create a Transformer: Implement a transformer to evaluate the parse-tree into a usable data structure, such as an Abstract Syntax Tree (AST) or a custom set of Python classes.

To build the HTML documentation, navigate to the docs/ directory, install the necessary requirements, and use make.

cd docs/
pip install -r requirements.txt
make html

You can run the full suite of unit tests from the project root using several different methods depending on your environment and preference.

# Using the standard python module
python -m tests

# Using pypy
pypy -m tests

# Using pytest
pytest tests

# Using setup.py
python setup.py test

By default, Lark builds a parse-tree. Trees are preferred over state-machines because they allow you to visualize the state, maintain awareness of previous/future states, and process the parse in incremental steps.

If you are using the LALR(1) algorithm and need to improve performance, you can skip tree construction by providing a transformer instead.