# jsparagus parser generator

This directory contains an LALR parser generator called "jsparagus",
written in Python.

This is used to build parts of the jsparagus JS parser in
[crates/generated_parser](https://github.com/mozilla-spidermonkey/jsparagus/blob/master/crates/generated_parser/).

jsparagus generates parsers only; it's "bring your own lexer".

Parser generators are complicated. Here's how this works.

1.  **Input.** jsparagus can load **grammar files** that describe languages.
    It's designed, in particular, to handle
    [this `.esgrammar` file that describes JavaScript](https://github.com/jorendorff/jsparagus/blob/master/js_parser/es-simplified.esgrammar),
    but it can handle a variety of languages.
    (For example, the code we use to parse the `esgrammar` file itself
    is generated by jsparagus.)

    To understand what a grammar is, see the comments in
    [grammar.py](https://github.com/jorendorff/jsparagus/blob/master/jsparagus/grammar.py).

2.  **LALR.** jsparagus runs the
    [LALR](https://en.wikipedia.org/wiki/LALR_parser) parser generator
    algorithm to generate parser tables. See
    [gen.py](https://github.com/jorendorff/jsparagus/blob/master/jsparagus/gen.py).
    This code also rejects invalid or ambiguous grammars and so on.

    There are a few comments in gen.py, but they assume a pretty solid
    background understanding of parser theory. If you're starting from
    scratch, check out:

    *   [Crafting
        Interpreters](http://craftinginterpreters.com/contents.html); or

    *   [Stanford’s CS1 Compilers](https://lagunita.stanford.edu/courses/Engineering/Compilers/Fall2014/about),
        an excellent, challenging, free course with exercises.

    *   [The Dragon
        Book](https://en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools)
        by Aho et al. Often hard to follow, but it contains a
        complete description of LR and LALR.

    jsparagus has a few special features geared toward being able to parse
    JavaScript, which [has an idiosyncratic syntax](https://github.com/mozilla-spidermonkey/jsparagus/blob/master/js-quirks.md#js-syntactic-quirks).
    See [js_parser/README.md](https://github.com/mozilla-spidermonkey/jsparagus/tree/master/js_parser)
    for more.

3.  **Output.** The `emit` directory contains code for dumping the parser tables as
    code in [Rust](https://github.com/jorendorff/jsparagus/blob/master/jsparagus/emit/rust.py)
    or [Python](https://github.com/jorendorff/jsparagus/blob/master/jsparagus/emit/python.py).

4.  **Run time support.** Since the output is mostly just tables, there
    has to be some code to actually look at tokens and the parser tables
    and decide what to do.

    For Python, that's in
    [runtime.py](https://github.com/jorendorff/jsparagus/blob/master/jsparagus/runtime.py).
    
    For Rust, it's in
    [crates/parser/src/parser.rs](https://github.com/jorendorff/jsparagus/blob/master/crates/parser/src/parser.rs).
    Because this code is currently tightly coupled to the JS lexer,
    jsparagus is not a fully general Rust parser generator yet.
    The Python code is more flexible.