GoLR is a modern tool for generating parsers based on LR(1) grammars. It combines the expressive power of full LR(1) parsing with the compact tables of IELR(1) by Joel E. Denny and Brian A. Malloy. The tables accept the same language and produce the same parses as canonical LR(1), but states are split only where merging them would change the parser's behavior. For an LALR(1) grammar the result is the LALR(1) table.
GoLR also includes a scanner generator for regular expressions. The parser generator and the scanner generator are each split into a frontend which reads the input, a core which builds the parser or scanner, and a backend which writes it out. The supported frontends, cores and backends are listed in the parser generator and scanner generator sections below.
Generated parsers build a parse tree which users can then walk.
See correctness for how the IELR(1) core is verified.
Download a prebuilt binary from the Releases section and make it available in your shell.
Or run it as container without installing anything locally:
docker run --rm backbone81/golr:latest --helpOr install the binary with your Go toolchain:
go install github.com/backbone81/golr/cmd/golr@latestThis example assumes a context free grammar in a GNU Bison grammar file grammar.y. Run GoLR to generate a Go parser
from it:
golr parser \
--frontend bison \
--frontend-file-path grammar.y \
--backend-file-path parser/parser.goThe same command works through Docker by mounting the current directory into the container, so both the grammar file and the generated output are visible on the host:
docker run --rm -v "$(pwd):/work" -w /work backbone81/golr:latest parser \
--frontend bison \
--frontend-file-path grammar.y \
--backend-file-path parser/parser.goThis generates a parser/parser.go file in the default parser package.
You then need to provide a scanner that produces tokens for the parser. The generated ParserScanner interface documents what the parser expects from the scanner. You can use the GoLR scanner generator to generate a scanner for you. Note that the scanner tokens need to be defined in the same package as the parser. Otherwise, the parser will reference tokens which do not exist.
Once you have a scanner, parsing works like this:
scanner := parser.NewScanner() // your scanner implementation
p := parser.NewParser()
rootNode, err := p.Parse(scanner)
if err != nil {
log.Fatal(err)
}You can then walk the parse tree from the root node.
See the Calculator Example for a simple and complete example about how to use GoLR.
See the examples directory for parsers generated with GoLR.
The IntelliJ Plugin and the
Visual Studio Code Extension provide syntax
highlighting, navigation, rename, code completion and formatting for .golr grammar files.
See the ide/ folder for the source code of those IDE plugins.
The GoLR CLI supports several command line parameters. Use --help for a help screen.
The main top level sub-commands are parser to generate an LR(1) parser and scanner to generate an DFA scanner:
GoLR is a parser generator for LR(1) grammars.
Usage:
golr [command]
Available Commands:
completion Generate the autocompletion script for the specified shell
convert Converts grammar files between different formats.
fmt Pretty prints GoLR grammar files.
help Help about any command
parser Generates a LR(1) parser.
scanner Generates a DFA scanner.
selftest Fuzz tests the IELR(1) parser core against a canonical LR(1) oracle.
Flags:
-h, --help help for golr
Use "golr [command] --help" for more information about a command.
The parser sub-command allows selecting frontend, core and backend for the parser:
Generates a LR(1) parser.
Usage:
golr parser [flags]
Flags:
--backend string The backend to use for writing the parser. One of: c, cpp, csharp, dot, go, java, javascript, json, kotlin, null, python, rust, typescript, yaml. (default "go")
--backend-c-prefix string The prefix to put in front of every name the generated C code declares. Has to be the one the scanner was generated with. (default "parser")
--backend-c-scanner-include string The header the generated C parser includes the token type from. (default "scanner.h")
--backend-cpp-namespace string The C++ namespace to use for the generated C++ code. Has to be the one the scanner was generated into. (default "parser")
--backend-cpp-scanner-include string The header the generated C++ parser includes the token type from. (default "scanner.hpp")
--backend-csharp-namespace string The C# namespace to use for the generated C# code. Has to be the one the scanner was generated into. (default "Parser")
--backend-file-path string The file path to write the parser to. Can be '-' to write to stdout.
--backend-go-package-name string The Go package name to use for the generated Go code. (default "parser")
--backend-java-package-name string The Java package name to use for the generated Java code. Has to be the one the scanner was generated into. (default "parser")
--backend-javascript-scanner-module string The module specifier the generated JavaScript parser imports the token constants from. (default "./scanner.js")
--backend-kotlin-package-name string The Kotlin package name to use for the generated Kotlin code. Has to be the one the scanner was generated into. (default "parser")
--backend-python-scanner-module string The module the generated Python parser imports the token constants from. (default "scanner")
--backend-rust-scanner-module string The module path the generated Rust parser takes the token type from. (default "super::scanner")
--backend-typescript-scanner-module string The module specifier the generated TypeScript parser imports the token constants from. (default "./scanner.js")
--core string The core to use for generating the parser from the context free grammar. One of: ielr1, ielr1-golr, ielr1-bison, lalr1, lalr1-golr, lalr1-bison, lr1, lr1-golr, lr1-bison. (default "ielr1")
--counterexample-time-limit duration The time after which the search for a counterexample which proves the grammar ambiguous gives up on a conflict, and shows a counterexample up to the conflict instead. (default 5s)
--counterexample-total-time-limit duration The time after which the search for counterexamples which prove the grammar ambiguous gives up on all remaining conflicts. (default 2m0s)
--fail-on-conflicts Fail if a shift/reduce or reduce/reduce conflict is not resolved by precedence or associativity.
--fail-on-rr-conflicts Fail if a reduce/reduce conflict is not resolved by precedence or associativity.
--fail-on-sr-conflicts Fail if a shift/reduce conflict is not resolved by precedence or associativity.
--fail-on-warnings Fail if there are warnings.
--frontend string The frontend to use for reading the context free grammar. One of: bison, golr, json, yaml. (default "golr")
--frontend-file-path string The file path to read the context free grammar from. Can be '-' to read from stdin.
-h, --help help for parser
-v, --verbose List every conflict the parser generator resolved on its own.
--with-counterexamples Add counterexamples to every listed conflict, which show where the conflict comes from. Implies --verbose.
--with-state-number Output the state number with every conflicted state.
The scanner sub-command allows for selecting frontend, core and backend for the scanner:
Generates a DFA scanner.
Usage:
golr scanner [flags]
Flags:
--backend string The backend to use for writing the scanner. One of: c, cpp, csharp, dot, go, java, javascript, json, kotlin, null, python, rust, typescript, yaml. (default "go")
--backend-c-prefix string The prefix to put in front of every name the generated C code declares. (default "parser")
--backend-cpp-namespace string The C++ namespace to use for the generated C++ code. (default "parser")
--backend-csharp-namespace string The C# namespace to use for the generated C# code. (default "Parser")
--backend-file-path string The file path to write the scanner to. Can be '-' to write to stdout.
--backend-go-package-name string The Go package name to use for the generated Go code. (default "parser")
--backend-java-package-name string The Java package name to use for the generated Java code. (default "parser")
--backend-kotlin-package-name string The Kotlin package name to use for the generated Kotlin code. (default "parser")
--core string The core to use for generating the scanner from the regular expressions. One of: subset. (default "subset")
--frontend string The frontend to use for reading the regular expressions. One of: golr, json, yaml. (default "golr")
--frontend-file-path string The file path to read the regular expressions from. Can be '-' to read from stdin.
-h, --help help for scanner
The fmt sub-command allows to pretty print GoLR grammar files:
Pretty prints GoLR grammar files.
Usage:
golr fmt [file...] [flags]
Flags:
-h, --help help for fmt
The convert sub-command converts GNU Bison grammar files to GoLR grammar files:
Converts grammar files between different formats.
Usage:
golr convert [flags]
Flags:
-h, --help help for convert
--input-file-path string The GNU Bison grammar file to convert. Can be '-' to read from stdin.
--output-file-path string The GoLR grammar file to write. Can be '-' to write to stdout. (default "-")
Note that the conversion is incomplete most of the time. GNU Bison grammar files do not describe regular expressions of tokens, for example. But the conversion can be a starting point to have a GoLR grammar quickly with only a few manual corrections needed.
The selftest sub-command checks the IELR(1) parser core against a canonical LR(1) oracle:
Fuzz tests the IELR(1) parser core against a canonical LR(1) oracle.
Usage:
golr selftest [flags]
Flags:
--duration duration The duration to check random grammars. Supports Go durations with 30s or 10m. Use 0 for unlimited.
--fail-on-conflicts Check the cores under the policy which fails if a shift/reduce or reduce/reduce conflict is not resolved by precedence or associativity.
--fail-on-rr-conflicts Check the cores under the policy which fails if a reduce/reduce conflict is not resolved by precedence or associativity.
--fail-on-sr-conflicts Check the cores under the policy which fails if a shift/reduce conflict is not resolved by precedence or associativity.
--failure-dir string The directory to dump a failing grammar and its action traces into. (default ".")
--grammar-count int The number of random grammars to check in total. Use 0 for unlimited.
-h, --help help for selftest
--max-nonterminal-count int The largest number of nonterminals a random grammar may have. (default 8)
--max-production-count-per-nonterminal int The largest number of productions a generated nonterminal may have. (default 6)
--max-rhs-symbol-count int The largest number of symbols on the right hand side of a generated production. (default 4)
--max-terminal-count int The largest number of terminals a random grammar may have. (default 5)
--memory-limit int The megabytes of heap to fill before collecting garbage. Higher values check more grammars per second at the cost of memory. Use 0 to leave the Go garbage collector at its defaults. (default 512)
--sentences-per-grammar int The number of random sentences each grammar is checked with. (default 16)
--stop-on-failure Exit the application on the first failing grammar instead of continuing.
--workers int The number of random grammars to check concurrently. Defaults to the number of CPU cores.
This is a soak test for GoLR itself, not a step of generating a parser. Random grammars are turned into an IELR(1) and a canonical LR(1) parser table, and both tables are driven through the same generated sentences. They have to take the identical sequence of LR actions every time, because that is what IELR(1) guarantees: the same language and the same parses as canonical LR(1), only with fewer states. Any disagreement is a bug in the IELR(1) core.
A run saturates every core it is given and keeps going until the grammar count or the duration is reached, so a run with neither only ends on Ctrl-C. Interrupting it is fine at any point, the summary still covers everything checked so far:
golr selftest --duration 8h --failure-dir ./selftest-failures | tee selftest.logThe --fail-on-... flags build both tables under the same policy as the flags of golr parser, which covers the paths
an unresolved conflict takes through the IELR(1) core.
See the documentation about correctness for where this fits into the overall verification of the IELR(1) implementation.
The parser generator constructs an LR(1) parser from a context free grammar. Please be aware of the known limitations.
See conflicts for how conflicts are decided, how they are reported, and how to make a build fail on them. See grammar checks for the errors and warnings about nonterminals which cannot be used.
These frontends are currently supported:
Are you missing a frontend for your use case? Use the JSON frontend of GoLR to input the grammar as JSON and implement your own frontend by loading whatever format you need and output the JSON. You do not need to do that in Go. Any programming language which is able to load your format and can output JSON can be used for such a custom frontend. And with outputting JSON to stdout, the output of your own frontend application can be piped into GoLR for maximum flexibility.
These cores are currently supported:
See parser generator backends for the backends which are currently supported, for what the generated parsers have in common, and for how to write a backend of your own.
The scanner generator constructs a DFA scanner from regular expressions.
These frontends are currently supported:
Are you missing a frontend for your use case? Use the JSON frontend of GoLR to input the regular expressions as JSON and implement your own frontend by loading whatever format you need and output the JSON. You do not need to do that in Go. Any programming language which is able to load your format and can output JSON can be used for such a custom frontend. And with outputting JSON to stdout, the output of your own frontend application can be piped into GoLR for maximum flexibility.
These cores are currently supported:
See scanner generator backends for the backends which are currently supported, for what the generated scanners have in common, and for how to write a backend of your own.
A parser generator fails quietly. A reduction lookahead set which is one terminal too large turns a perfectly good grammar into one with a conflict, and one which is one terminal too small produces a parser that builds, runs and then rejects a sentence the grammar clearly derives. Nothing crashes, and the damage surfaces only in whoever uses the generated parser. IELR(1) makes this worse: it is a five phase algorithm whose output is deliberately not comparable to any table you could write down by hand, so "diff it against the expected result" is not available as a test strategy.
What IELR(1) does guarantee is behavioral — an IELR(1) parser accepts the same language and produces the same parses as a canonical LR(1) parser under the same conflict resolution policy, only with fewer states. GoLR builds its verification on that guarantee, in overlapping layers:
- The grammars from the IELR(1) paper. Parser tables, follow kernel items, annotations and item lookahead sets are pinned against the definitions of the paper for the small grammars its figures were constructed from.
- Real-world grammars cross-checked against GNU Bison. The grammars of GNU Bison, GCC's C, Objective-C, C++ and Java, Go, PHP and PostgreSQL are each built with the GoLR LALR(1) and IELR(1) cores and with GNU Bison itself — the reference implementation whose authors wrote the paper. Where a grammar is LALR(1), all four tables must agree on the state count. Where it is not, both implementations must split, and GoLR must land within 2% of Bison's state count.
- Differential testing against canonical LR(1). Random grammars, generated from scenarios deliberately biased
toward the shapes where LALR(1) and canonical LR(1) diverge, are turned into an IELR(1) and a canonical LR(1) table.
Both tables are then driven through sentences derived from the grammar itself and have to take the identical sequence
of LR actions, step for step. Every run additionally asserts the size invariant
|LALR(1)| <= |IELR(1)| <= |canonical LR(1)|, and the corpus measures itself so it cannot pass vacuously on grammars which never exercise the splitting. - The
golr selftestsoak test. The same comparison, running across every CPU core for hours instead of seconds. Corpora of millions of grammars are routine, and a single seed reproduces any failure it finds. - Mutation testing of the test suite itself. Around 50 deliberate bugs, each derived from a specific definition in the paper, were injected one at a time to confirm the self-test actually notices. Every mutation which changes a parse was detected, most within a few dozen grammars.
The correctness documentation describes each layer in detail, including what these checks deliberately do not cover.
GoLR is licensed under the Apache License, Version 2.0.
The parsers and scanners GoLR generates for you are exempt from that license. The GoLR Output Exception gives you unlimited permission to use, modify and distribute the generated files under terms of your choosing. You do not need to place them under the Apache License, ship a copy of the license with them, or attribute GoLR in them.
The exception covers the generated output only. GoLR itself, including its code-generation templates, stays under the Apache License.