Metadata-Version: 2.4
Name: larkita
Version: 0.5.0
Summary: A light-weight canonical LR(1) parser generator that returns abstract syntax trees as nested tuples
Author: Karl Stroetmann
Author-email: "Erez Shinan (Lark)" <erezshin@gmail.com>
License-Expression: MIT
Project-URL: Homepage, https://github.com/karlstroetmann/Larkita
Project-URL: Documentation, https://github.com/karlstroetmann/Larkita/blob/master/tutorial/larkita-tutorial.pdf
Keywords: LR(1),parser,parsing,ast
Classifier: Development Status :: 3 - Alpha
Classifier: Intended Audience :: Developers
Classifier: Intended Audience :: Education
Classifier: Programming Language :: Python :: 3
Classifier: Topic :: Software Development :: Libraries :: Python Modules
Classifier: Topic :: Text Processing :: General
Requires-Python: >=3.12
Description-Content-Type: text/markdown
License-File: LICENSE
Provides-Extra: regex
Requires-Dist: regex; extra == "regex"
Provides-Extra: interegular
Requires-Dist: interegular<0.4.0,>=0.3.1; extra == "interegular"
Provides-Extra: pygments
Requires-Dist: pygments; extra == "pygments"
Dynamic: license-file

# Larkita

Larkita is a light-weight version of the Python parser generator
[Lark](https://github.com/lark-parser/lark).  It differs from Lark in three ways:

* It generates a **canonical LR(1) parser** (not Earley or CYK).  On request, it
  merges states with the same core; for an LALR(1) grammar and the basic lexer,
  the result is the LALR(1) parser.
* The parser returns the **abstract syntax tree as a nested tuple**, not as a tree
  of objects.  How the tuple is built follows from the grammar itself; you never
  have to write tree-building code.
* Every time a parser is generated, Larkita writes an **output file** with all
  the LR(1) states, every item annotated with its lookahead tokens.  This makes
  conflicts easy to debug.

Grammars are written in Lark's EBNF notation, with a few additions for building
the abstract syntax tree.

## Installation

Larkita needs Python 3.12 or newer and has no dependencies.  Install it with

    pip install larkita

The source code is on GitHub at <https://github.com/karlstroetmann/Larkita>.  To
install the latest version from there, run

    pip install git+https://github.com/karlstroetmann/Larkita.git

If the optional package `interegular` is installed, Larkita checks whether the
regular expressions of different terminals can match the same text.  It reports
such collisions via `larkita.logger`, which is silent by default; call
`larkita.logger.setLevel(logging.WARNING)` to see them.

## Quick start

```python
from larkita import Larkita

grammar = r'''
stmnt: IDENTIFIER ":=" expr ";"
     | expr ";"

expr: expr "+" product
    | expr "-" product
    | product

product: product "*" factor
       | product "/" factor
       | factor

factor: "(" expr ")"    %ignore "(", ")"
      | NUMBER
      | IDENTIFIER

%import common.CNAME -> IDENTIFIER
%import common.NUMBER
%import common.WS
%ignore WS
'''

parser = Larkita(grammar)
print(parser.parse('x := (a + 3) * b;'))
```

prints

```python
((':=', ';'), ('IDENTIFIER', 'x'), ('*', ('+', ('IDENTIFIER', 'a'), ('NUMBER', '3')), ('IDENTIFIER', 'b')))
```

and writes the description of the automaton to `grammar.out`.  To read the
grammar from a file, use

```python
parser = Larkita.open('new-syntax/expr.g')     # writes new-syntax/expr.out
```

The start symbol is the first rule of the grammar (here `stmnt`).

## Tutorial

The tutorial
[`tutorial/larkita-tutorial.pdf`](https://github.com/karlstroetmann/Larkita/blob/master/tutorial/larkita-tutorial.pdf)
explains how to write grammars for Larkita, how the abstract syntax trees are
built, how to process them with `match`, and how to deal with syntax errors and
conflicts.  Its grammars and programs are in the directory `tutorial/examples` of
the repository; running `make` in the directory `tutorial` runs them and rebuilds
the PDF.

## How the abstract syntax tree is built

Consider an alternative `a: X1 X2 ... Xn`.  The literal tokens written in double
quotes form the **head** of the tuple; all other symbols become its **children**:

    (head, ast(child_1), ..., ast(child_k))

| Grammar | Abstract syntax tree |
|---|---|
| `expr: expr "+" product` | `("+", ast(expr), ast(product))` |
| `stmnt: expr ";"` | `(";", ast(expr))` |
| `stmnt: IDENTIFIER ":=" expr ";"` | `((":=", ";"), ("IDENTIFIER", name), ast(expr))` |
| `atom: IDENTIFIER` | `("IDENTIFIER", name)` |
| `expr: product` | `ast(product)` |
| `factor: "(" expr ")"  %ignore "(", ")"` | `ast(expr)` |
| `atom: IDENTIFIER "(" args ")" -> "call"` | `("call", ("IDENTIFIER", name), ast(args))` |
| `args: expr ("," expr)*` | `(",", ast(expr_1), ..., ast(expr_n))` |
| `set: "{" expr ("," expr)* "}"` | `(("{", ",", "}"), ast(expr_1), ..., ast(expr_n))` |
| `program: statement*` | `("program", ast(statement_1), ..., ast(statement_n))` |
| `stmnt: "return" [expr] ";"` | `(("return", ";"),)` or `(("return", ";"), ast(expr))` |
| `expr: expr ("+" \| "-") product` | `("+", ast(expr), ast(product))` or `("-", ast(expr), ast(product))` |
| `expr: product (("+" \| "-") product)*` | `("expr", ast(product_1), "-", ast(product_2), ...)` |

In detail:

* **Head.**  The head consists of all literals of the alternative that are not
  ignored, in the order in which they are written, one entry per occurrence.  If
  there is exactly one literal, the head is that string; otherwise it is a tuple
  of strings.  The head is fixed by the grammar, not by the input: `f(a)` with the
  rule for `args` above yields `(",", ast(a))`, even though no comma was read.
  Literals inside repetitions, optional parts and groups belong to the head, too,
  except for the literals of inner alternatives inside repetitions and optional parts.
* **Inner alternatives** like `("+" | "-")` abbreviate several alternatives:
  `expr: expr ("+" | "-") product` means `expr: expr "+" product | expr "-" product`,
  so the literal that has been read is the head.  Inside a repetition or an optional
  part, and in an alternative with an alias, the head cannot depend on the input.
  There, the literal that has been read becomes a child of the tuple, as a plain
  string: `1 - 2 + 3` yields `("expr", ast(1), "-", ast(2), "+", ast(3))` with the
  rule `expr: product (("+" | "-") product)*`.
* **Named tokens** become `(NAME, text)`, e.g. `("NUMBER", "42")`.  The text is
  not converted.  Inline regular expressions `/.../` are treated like named tokens.
* **Pass-through.**  If an alternative has no head and consists of exactly one
  symbol (with no `*`, `+`, `?`, `[...]` or `|`), it returns the abstract syntax
  tree of that symbol unchanged.  Inner alternatives are expanded first, so
  `a: (b | "-" b)` passes the abstract syntax tree of `b` through.
* **Rule name as head.**  If an alternative has no head and is not a pass-through,
  the name of the rule is used as head, e.g. `("program", ...)`.  An empty
  alternative yields `("rule_name",)`.
* **Repetitions and groups are flattened** into the tuple of the alternative.
* **Missing optional parts are left out**; there is no `None` placeholder.
* **Aliases** replace the whole head: `-> "call"` and `-> call` are equivalent.

### Ignoring literals

`%ignore` has three forms:

```
%ignore WS                      // the lexer skips the terminal WS
%ignore WS, COMMENT             // the lexer skips the terminals WS and COMMENT
factor: "(" expr ")"  %ignore "(", ")"
                                // "(" and ")" are left out of the head of this alternative
%ignore: "(", ")", "{", "}"     // these literals are left out of the heads of all rules
```

With `%ignore: "(", ")"`, the rule
`statement: "while" "(" expr ")" statement` yields
`("while", ast(expr), ast(statement))`.

## Grammar syntax

Larkita reads Lark grammars:

* Rules have lowercase names, terminals have uppercase names.
* `|` separates alternatives, `( ... )` groups, `[ ... ]` and `?` mark optional
  parts, `*` and `+` repeat, and `~ n` or `~ n..m` repeat a fixed number of times.
* String literals are written as `"..."` (append `i` for case-insensitive
  matching), regular expressions as `/.../flags`.
* Terminals are defined with `NAME: ...`; `NAME.p: ...` gives a terminal the
  priority `p`, and `rule.p: ...` gives a rule the priority `p` (used to resolve
  reduce/reduce conflicts).
* `%import common.NUMBER` imports terminals from Lark's standard library
  (`larkita/grammars/common.lark`), and `%import .file.rule` imports from a
  grammar file next to the current one.  `-> NAME` renames an import.  Several
  imports are separated by commas: `%import common.CNAME -> ID, common.INT, common.WS`.
* `%declare`, `%extend` and `%override` work as in Lark.
* `//` starts a comment.

Not supported (compared with Lark): the rule modifiers `?rule` and `!rule`,
templates, post-lexers (such as Lark's `Indenter`), lexer callbacks, and
transformers.  Rules and terminals whose names start with `_` are not inlined
or filtered.

## The output file

If the grammar is read from a file, the output file has the same name with the
extension `.out` (`expr.g` produces `expr.out`).  Otherwise it is `grammar.out` in
the current directory.  The parameter `out_file` sets another path.

The file contains

1. the rules after the EBNF operators have been expanded, each followed by the
   abstract syntax tree that a reduction produces, e.g.
   `(3) expr → expr "+" product  ⇒ ("+", ast(expr), ast(product))`;
2. a list of all conflicts and how they were resolved;
3. all states.  Each state lists its items with their lookahead tokens (closure
   items are marked with `+`), followed by its actions and gotos:

```
State 2

    (1)   stmnt → IDENTIFIER • ":=" expr ";"  { $END }
    (11)  factor → IDENTIFIER •               { "*", "+", "-", "/", ";" }

    ":="  shift and go to state 8
    "*"   reduce using rule (11) factor → IDENTIFIER
    "+"   reduce using rule (11) factor → IDENTIFIER
    "-"   reduce using rule (11) factor → IDENTIFIER
    "/"   reduce using rule (11) factor → IDENTIFIER
    ";"   reduce using rule (11) factor → IDENTIFIER
```

## Conflicts

* **Shift/reduce conflicts** are resolved in favour of shift (so the dangling
  `else` belongs to the innermost `if`).  Larkita issues a `ConflictWarning`.
* **Reduce/reduce conflicts** are resolved in favour of the rule with the highest
  priority.  If no rule has a higher priority than the others, `Larkita` raises a
  `GrammarError`; the output file is written anyway.

## Merging states

Canonical LR(1) automata can be large.  With `merge_states=True`, Larkita merges
states with the same core (i.e. the same items without lookaheads), as long as
this is safe:

* Merging must not introduce a new conflict, neither in the merged states nor in
  their successors.
* With the contextual lexer, merging must not change how the input is split into
  tokens.  For example, if a keyword like `"else"` is only acceptable in one of
  two states, merging them could make the lexer read `else` as a keyword where
  the other state reads an identifier.

The resulting parser accepts the same strings, builds the same abstract syntax
trees, and detects syntax errors at the same tokens as the canonical parser,
although it may perform a few more reductions before it reports an error.  With
`lexer='basic'`, the lexer does not depend on the state of the parser, so for an
LALR(1) grammar the result is the LALR(1) automaton.  The output file then
describes the merged states and explains why the remaining states with the same
core have been kept apart.

## API

```python
Larkita(grammar, *, start=None, lexer='contextual', import_paths=(),
        source_path=None, out_file=None, regex=False, g_regex_flags=0,
        merge_states=False)
```

* `grammar`: the grammar as a string or an open file.
* `start`: the start symbol; defaults to the first rule.
* `lexer`: `'contextual'` (only matches the terminals that the parser can accept
  in its current state) or `'basic'`.
* `import_paths`: additional directories to search for imported grammars.
* `source_path`: the file name of the grammar, used for relative imports and to
  name the output file.
* `out_file`: the path of the output file.
* `regex`: use the `regex` module instead of `re`.
* `g_regex_flags`: flags applied to all terminals.
* `merge_states`: merge states with the same core, as long as this is safe
  (see above).

`Larkita.open(filename, rel_to=None, **options)` reads the grammar from a file.

`parser.parse(text)` returns the abstract syntax tree.  It raises
`UnexpectedCharacters` if the lexer cannot match the input, and `UnexpectedToken`
if the parser receives a token it cannot accept (at the end of the input, the
token has the type `$END`).  All exceptions derive from `LarkitaError`.

`parser.lex(text)` runs only the scanner and returns an iterator over the tokens.
Every token `t` provides `t.type`, `t.value`, `t.line`, and `t.column`; ignored
tokens are skipped.

After construction, `parser.conflicts`, `parser.rules`, `parser.terminals`,
`parser.parse_table` and `parser.out_file` describe the generated parser.

### Highlighting grammars

Larkita registers two lexers for [Pygments](https://pygments.org): `larkita` for
grammars and `python-larkita` for Python code whose raw strings `r"""..."""` are
grammars.  They need Pygments, e.g. `pip install larkita[pygments]`:

```
pygmentize -l larkita grammar.g
```

In Jupyter, `IPython.display.Code(text, language='larkita')` displays a grammar
with syntax highlighting.

## Examples and tests

The directory `new-syntax` of the repository contains two example grammars:
`expr.g` (arithmetic expressions) and `interpreter.g` (a small imperative language
with sets).

In a clone of the repository, run the tests with

    python3 -m tests

## License

MIT.  Larkita is derived from [Lark](https://github.com/lark-parser/lark) by
Erez Shinan; see `LICENSE`.
