Gecko: a fast GLR parser with automatic syntax error recovery

# Gecko: a fast GLR parser with automatic syntax error recovery Source: [https://vnmakarov.github.io/parsing/compilers/c/open-source/2026/04/22/gecko-glr.html](https://vnmakarov.github.io/parsing/compilers/c/open-source/2026/04/22/gecko-glr.html) ## Gecko: A Fast, Standalone GLR Parser Library in C Parsing is the backbone of every programming language implementation, and the choice of parser technology has far\-reaching consequences for the language designer\.[LALR\(1\)](https://en.wikipedia.org/wiki/LALR_parser)parsers like[YACC](https://invisible-island.net/byacc)and[Bison](https://www.gnu.org/software/bison/)have dominated for decades, but they force grammar authors into contortions to avoid conflicts\. Generalized parsers – those that handle the full class of[context\-free grammars](https://en.wikipedia.org/wiki/Context-free_grammar), including[ambiguous](https://en.wikipedia.org/wiki/Ambiguous_grammar)ones – have traditionally been considered too slow for production use\. Gecko is a new[GLR](https://en.wikipedia.org/wiki/GLR_parser)parser library that challenges that assumption\. It handles**any**context\-free grammar, provides**automatic syntax error recovery**with no grammar modifications, and still runs at speeds competitive with YACC on unambiguous grammars\. In this post I’ll walk through Gecko’s design goals, its key features, how to use it in your own projects, and the benchmarks that demonstrate its performance\. ## Why another parser? The world of parser generators is crowded\. YACC and Bison have been around since the 1970s\. More recently,[PEG](https://en.wikipedia.org/wiki/Parsing_expression_grammar)parsers,[parser combinators](https://en.wikipedia.org/wiki/Parser_combinator), and various[Earley](https://en.wikipedia.org/wiki/Earley_parser)\-based tools have appeared\. So why build yet another parser? During my career I wrote several compiler\-compilers\. The first one was an LALR\(1\) parser written in 1985 in Pascal \(you can try to find its description in the Russian journal “Programming” for 1985\)\. The next one was[MSTA](https://github.com/cocom-org/msta), written in the nineties\. It was an LALR\(k\)/[LR\(k\)](https://en.wikipedia.org/wiki/LR_parser)parser with many additional optimizations that made it faster than YACC/Bison\. Using it I found that speed is not the most important feature of a parser, especially with faster modern CPUs, and that LR\(k\) is not enough for real language grammars\. Therefore, about ten years ago I wrote[YAEP](https://github.com/vnmakarov/yaep): an Earley parser that can work with any context\-free grammar\. I spent a lot of time making it fast, and it is actually the fastest implementation of an Earley parser that I know of\. Still, I was not satisfied with its speed and memory consumption for unambiguous and moderately ambiguous grammars\. Unfortunately, it is difficult to solve these problems because of inherent features of the Earley algorithm\. Therefore, recently I turned my attention to GLR parsers – and Gecko is my implementation of one\. **I don’t know tools that offer the combination of features that Gecko provides**: 1. **Full CFG support**– no restrictions on grammar structure, including ambiguous grammars 2. **Library form**– embeddable in any C program, with no external code generation step 3. **Operator[precedence](https://en.wikipedia.org/wiki/Order_of_operations)/[associativity](https://en.wikipedia.org/wiki/Operator_associativity)**–the same mechanism that YACC users have relied on for decades 4. **Automatic error recovery**–no`error`tokens, no grammar modifications, just correct parse trees with minimal token skipping 5. **Competitive speed**–within 5–10% of YACC on unambiguous grammars, and dramatically faster than other GLR parsers on ambiguous ones Let’s look at each of these in detail\. ## Feature overview ### Small and simple Gecko core code is roughly 2800 lines of C \([SLOC](https://en.wikipedia.org/wiki/Source_lines_of_code)\)\. It uses 6 header\-only utility libraries \(custom allocators, bitmaps, hashing, hash tables, variable\-length objects, and object stacks\) which is about 900 lines\. So Gecko’s entire implementation is roughly**3,700 lines of C**\(SLOC\)\. The compiled x86\-64 code weighs in at about**90KB**\. There are no external dependencies beyond the C standard library\. This makes Gecko trivial to embed in any project –just drop in the source files and compile\. ### Full context\-free grammar support YACC and Bison are limited to LALR\(1\) grammars\. Bison claims GLR support, but I was unable to make it work with ambiguous grammars\. Using`%glr\-parser`with an ambiguous C grammar \(the same one used by Gecko and[ElkHound](https://github.com/WeiDUorg/elkhound)for benchmarking\) reports a syntax error on the third line\. With the simplest ambiguous grammar`E : E '\+' E \| 'a'`it reports a syntax error on the 23rd token\. Gecko, by contrast, can parse inputs described by**any context\-free grammar**, including ambiguous ones\. This is particularly useful for languages like C, where the infamous “typedef problem” \(is`T \* x;`a pointer declaration or a multiplication?\) creates genuine ambiguity if typenames are not distinguished from identifiers at the lexer level\. With Gecko, you can use a single token type for all identifiers – including typenames –and let the parser explore both interpretations simultaneously\. The ambiguity is resolved structurally in the resulting parse tree, rather than requiring feedback hacks between scanner and parser\. ### Simple syntax\-directed translation Gecko doesn’t use semantic actions the way YACC does\. Instead, it generates[**abstract syntax trees \(ASTs\)**](https://en.wikipedia.org/wiki/Abstract_syntax_tree)as output using a concise notation in the grammar rules\. Each rule’s right\-hand side can specify which children contribute to the AST node: ``` E : T # 0 | E '+' T # plus (0 2) ; T : F # 0 | T '*' F # mult (0 2) ; F : 'a' # 0 | '(' E ')' # 1 ; ``` The`\#`notation after each alternative specifies the translation: - `\# 0`means “the translation of this rule is the translation of RHS symbol at index 0” \(i\.e\., pass through\) - `\# plus \(0 2\)`means “create an abstract node named`plus`whose children are the translations of RHS symbols at positions 0 and 2” - `\# 1`means “the translation is the translation of the RHS symbol at index 1” \(skipping the left parenthesis\) This approach is simpler than YACC\-style actions for many use cases: you get a clean AST without writing any C code in the grammar\. The resulting parse tree consists of`GP\_TERM`nodes \(for terminals\),`GP\_ANODE`nodes \(for abstract nodes with named children\),`GP\_NIL`nodes \(for empty translations\),`GP\_ALT`nodes \(for ambiguous alternatives\), and`GP\_OPT`nodes \(for context\-dependent alternatives\)\. For the grammar above and input`a\+a\*\(a\*a\+a\)`, Gecko will generate the following tree:  In the tree,`ANODE`and`TERM`represent parse tree node types \(`GP\_ANODE`and`GP\_TERM`\),`plus`and`mult`are the`name`field of the abstract node, and`a`represents the attribute of the corresponding input token\. ### Operator grammars Many practical grammars include expression syntax with dozens of precedence levels\. Writing these out as a cascade of nonterminals \(one per precedence level\) is tedious and error\-prone\. Gecko supports**operator priority and associativity declarations**using the same syntax as YACC/Bison: ``` LEFT '+'; LEFT '*'; E : 'a' # 0 | '(' E ')' # 1 | E '+' E # plus (0 2) | E '*' E # mult (0 2) ; ``` Here,`LEFT '\+'`and`LEFT '\*'`declare left\-associative operators with`\*`having higher precedence than`\+`\(later declarations have higher precedence\)\. This lets you write ambiguous\-looking rules like`E '\+' E`and have Gecko resolve the conflicts the same way YACC would\. The full power of GLR parsing is still behind it in case other parts of your grammar are genuinely ambiguous\. The supported associativity declarations are`LEFT`,`RIGHT`, and`NONASSOC`, and multiple tokens can appear on the same line to share a precedence level\. As with YACC, writing grammars that use operator precedence/associativity declarations and left\-recursive rules results in faster parsing and lower memory consumption\. ### Library architecture Gecko is a**library**, not a standalone tool\. This is a fundamental design decision\. Where YACC and Bison generate C source files that you compile and link, Gecko is simply linked into your program\. The grammar can be provided either through function calls \(`gp\_read\_grammar`\) or as a YACC\-like description string \(`gp\_parse\_grammar`\)\. This means: - **No code generation step**in your build process - **Multiple grammars**can coexist in the same program - **Grammars can be changed at runtime**–read from configuration files, constructed dynamically, or switched between parsing passes - **Very fast startup**after reading a grammar from a file or string The core API is deliberately minimal: ``` struct grammar *g = gp_create_grammar(); gp_parse_grammar(g, true, description); gp_parse(g, read_token, &root, &ambiguity, NULL); gp_fin(g); ``` Four function calls to go from grammar description to parse tree\. This is perhaps Gecko’s most distinctive feature\. People who have used YACC/Bison or other widely used compiler\-compiler tools know how difficult it is to implement good syntactic error recovery\. In my experience, more time is spent on this task –and on dealing with syntax errors in the semantic checker –than on writing the original grammar\. Therefore, a strong emphasis in the Gecko project was placed on simplifying this task\. Syntax error recovery in Gecko is automated as much as possible\. Gecko always generates parse trees corresponding to some correct input, which is obtained from the original erroneous input by removing as few tokens as possible\. Traditional parser generators require you to manually add`error`tokens to your grammar to enable any kind of error recovery\. Getting this right is notoriously difficult –place the`error`token in the wrong production and the parser either gives up too early, or swallows too many tokens and produces confusing follow\-on errors\. Gecko’s error recovery is**fully automatic**\. It requires**no grammar modifications whatsoever**\. This is made possible by Gecko’s GLR architecture, which naturally maintains multiple parsing stacks simultaneously\. ### How it works When a syntax error is detected \(a token that no current stack can shift or reduce on\), Gecko’s recovery algorithm kicks in: 1. **Reject and pop\.**For each failed stack, Gecko rejects the current stack token and creates a new stack derived from the failed stack by popping the top elements until the new stack has an action on the current token of the original stack\. 2. **Find minimal\-cost success\.**Recovery succeeds when a candidate stack with minimal cost successfully consumes a configurable number of consecutive tokens \(default: 5, can be changed via`gp\_set\_recovery\_match`\) without encountering another error, or when a candidate reaches EOF\. 3. **Resume normal parsing\.**All stacks that matched at least one token become the new starting point for continued parsing\. ### The key guarantee Gecko’s error recovery guarantees that**the parser always produces parse trees corresponding to syntactically correct inputs**\. The way it achieves this is conceptually simple: some tokens before and/or after the error point are ignored, and the remaining token stream is syntactically valid according to the grammar\. The parser reports which tokens were involved in the error through a user\-configurable error callback\. Consider a simple expression grammar \(see section “simple syntax\-directed translation” above\) and the input`a\+a\*\(a\*\+a\)`–note the extra`\*`before`\+a\)`\. Gecko will detect the error at the`\+`token \(after`a\*`\), determine that skipping the second`\*`operator yields a valid continuation, and produce a parse tree as if the input had been`a\+a\*\(a\+a\)`\. The error callback reports the problematic tokens, and parsing continues\. This approach works well in practice because: - It is**grammar\-agnostic**–any grammar gets error recovery for free - It finds the**minimal\-cost**repair, not just any repair - It handles**multiple errors**in the same input, recovering from each one independently - The parse tree output is always**structurally valid** Note that minimal\-cost error recovery here means minimal within a local search space\. I am not aware of any parser that searches for a globally minimal\-cost error recovery\. For example, YAEP performs a global search only in a limited sense: it minimizes the number of tokens covered by the special grammar terminal`error`\. ## The grammar description language Gecko accepts grammars in a YACC\-like textual format via`gp\_parse\_grammar`\. The format supports: ### Terminal declarations Named terminals with explicit codes are described as follows: ``` TERM IDENTIFIER = 300 CONSTANT = 338 STRING_LITERAL = 340; ``` Multiple terminals can be declared in a single`TERM`statement, each with an optional`= code`assignment\. Single\-character literals \(`'a'`,`'\+'`, etc\.\) are terminals with codes equal to their ASCII values and should not be described in TERM declarations\. ### Operator precedence ``` LEFT '+' '-'; LEFT '*' '/' '%'; RIGHT ELSE; NONASSOC '<' '>'; ``` Operators listed on the same line share a precedence level\. Lines appearing later have higher precedence\. This is identical to YACC/Bison semantics\. ### Rules ``` lhs : rhs_symbol_1 rhs_symbol_2 ... # translation | alternative_rhs ... # translation ; ``` Terminals can be single\-character literals \(`'a'`,`'\+'`\) or named tokens \(`IDENTIFIER`\)\. Nonterminals are any names not previously declared as terminals\. Gecko requires the grammar axiom \(start symbol\) to have exactly one rule\. Therefore, when using`gp\_read\_grammar`, you typically add an explicit start rule such as`$S : E`that has a single alternative \(see programmatic grammar construction\)\. When using`gp\_parse\_grammar`, Gecko adds such a rule automatically\. ### Translation specifications After`\#`: - A single number`N`means the translation is the translation of the Nth RHS symbol \(0\-indexed\) - `name \(i j k\)`creates an abstract node with the given name whose children are the translations of RHS symbols at positions i, j, k - Omitting the`\#`gives a nil translation An optional**guard**can follow the translation:`? N`assigns guard number`N`to the rule alternative \(see Rule Guards in Configuration\)\. C\-style`/\* \.\.\. \*/`comments are supported in grammar descriptions\. ## Programmatic grammar construction For maximum flexibility, Gecko also supports building grammars programmatically via the`gp\_read\_grammar`function\. You provide two callback functions: **`read\_terminal`**–called repeatedly to provide terminal definitions: ``` const char *read_terminal(int *code, int *priority, enum gp_assoc *assoc) { // Return terminal name, set code, priority, and associativity. // Return NULL when done. } ``` **`read\_rule`**–called repeatedly to provide grammar rules: ``` const char *read_rule(const char ***rhs, const char **abs_node, int **transl, int *guard_num) { // Return LHS name, set RHS array, abstract node name, translation, // and guard number. Return NULL when done. } ``` Assume we have a simple expression grammar: ``` LEFT '+'; E : 'a' # 1 | E '+' E # plus (0 2) | '(' E ')' # 1 ; ``` A complete example of programmatic grammar construction for the grammar would be ``` static int nterm = 0; const char *read_terminal(int *code, int *priority, enum gp_assoc *assoc) { nterm++; *priority = -1; *assoc = GP_NON_ASSOC; switch (nterm) { case 1: *code = 'a'; return "a"; case 2: *assoc = GP_LEFT_ASSOC; *code = '+'; return "+"; case 3: *code = '('; return "("; case 4: *code = ')'; return ")"; default: return 0; } } static int nrule = 0; const char *read_rule(const char ***rhs, const char **anode, int **transl, int *guard_num) { typedef const char *str; nrule++; *guard_num = -1; *anode = 0; switch (nrule) { case 1: *rhs = (str[]){"E", 0}; *transl = (int[]){0, -1}; return "$S"; case 2: *rhs = (str[]){"a", 0}; *transl = (int[]){0, -1}; return "E"; case 3: *anode = "plus"; *rhs = (str[]){"E", "+", "E", 0}; *transl = (int[]){0, 2, -1}; return "E"; case 4: *rhs = (str[]){"(", "E", ")", 0}; *transl = (int[]){1, -1}; return "E"; default: return 0; } } ``` This programmatic interface is useful when grammars need to be constructed dynamically or when integrating Gecko with a system that already has its own grammar representation\. ## A complete usage example Here is a small but complete example showing how to use Gecko to parse arithmetic expressions: ``` #include <stdio.h> #include <stdlib.h> #include <stddef.h> #include "gecko.h" #define NUMBER 300 static const char *description = "\n" "TERM NUMBER = 300;\n" "LEFT '+';\n" "LEFT '*';\n" "E : E '+' E # plus (0 2)\n" " | E '*' E # mult (0 2)\n" " | '(' E ')' # 1\n" " | NUMBER # 0\n" " ;\n" ; static struct { int code; int val; } input[] = { /* Input: 10 + 2 * (5 + 11) */ {NUMBER, 10}, {'+', 0}, {NUMBER, 2}, {'*', 0}, {'(', 0}, {NUMBER, 5}, {'+', 0}, {NUMBER, 11}, {')', 0} }; static int input_pos = 0; static int read_token_func(void **attr) { if (input_pos >= (int)(sizeof(input) / sizeof(input[0]))) return -1; *attr = (void *)(ptrdiff_t)input[input_pos].val; return input[input_pos++].code; } int main(void) { struct grammar *g; struct gp_tree_node *root; int ambiguity; if ((g = gp_create_grammar()) == NULL) { fprintf(stderr, "gp_create_grammar: No memory\n"); exit(1); } if (gp_parse_grammar(g, true, description) != 0) { fprintf(stderr, "%s\n", gp_error_message(g)); exit(1); } gp_set_debug_level(g, 2); if (gp_parse(g, read_token_func, &root, &ambiguity, NULL)) fprintf(stderr, "gp_parse: %s\n", gp_error_message(g)); gp_fin(g); return 0; } ``` Build the example with ``` gcc -O2 -I/usr/local/include example.c /usr/local/lib/libgecko.a ``` A few things to note: 1. **`gp\_create\_grammar\(\)`**allocates and initializes the grammar object\. 2. **`gp\_parse\_grammar\(g, true, description\)`**parses the textual grammar description\. The`true`argument enables strict grammar checking \(detecting unreachable nonterminals, nonterminals that can’t derive terminal strings, loops, etc\.\)\. 3. **`gp\_set\_debug\_level\(g, 2\)`**enables printing of the result translation \(AST\) to stderr, which is useful for verifying the parse tree structure\. 4. **`gp\_parse\(g, read\_token\_func, &root, &ambiguity, NULL\)`**runs the parser\.`read\_token\_func`is a user\-provided function that returns the next token’s code and attribute\. It returns a negative value at end of input\. On success,`root`points to the parse tree and`ambiguity`indicates the ambiguity level\. 0 means no ambiguity\. 1 means the grammar is found to be ambiguous on the input\. 2 means the final stack was produced by merging stacks where terminal attributes or abstract nodes differed, which would result in context\-dependent alternative \(`GP\_OPT`\) nodes in the parse tree if a custom merge function is provided\. The last argument is passed to the rule guard function \(see below\)\. 5. **`gp\_fin\(g\)`**frees all resources associated with the grammar\. 6. `/usr/local`is the default directory where Gecko is installed by`make install`\. ## Configuration and customization Gecko provides several configuration functions to customize parser behavior: ### Memory management ``` gp_set_parse_alloc(g, my_alloc); // Custom allocator for parse tree nodes gp_set_parse_free(g, my_free); // Custom deallocator (NULL = no freeing) ``` By default Gecko uses`malloc`and`free`\. You can provide custom allocators, for instance to use arena allocation for the parse tree\. Note that it is not safe to change these functions after`gp\_parse`and before`gp\_fin`, as some data allocated by`parse\_alloc`in`gp\_parse`can be freed in`gp\_fin`and when reading a new grammar\. ### Syntax error reporting ``` gp_set_syntax_error(g, my_error_func); ``` The error function receives the representation of a nonterminal related to the error position and a boolean`after\_p`flag indicating whether the error occurred after that nonterminal \(print “error after …”\) or within it \(print “error in …”\)\. It also receives the representation and attribute of the error token, plus the representation and attribute of the token where recovery stopped\. The default function prints the error nonterminal and token representations\. In a real compiler, you would set this to print file names, line numbers, and column numbers extracted from the token attributes\. You would also translate nonterminal names into more readable form \(e\.g\., nonterminal`stmt`used in grammar into`statement`\)\. ### Error recovery tuning ``` gp_set_recovery_match(g, 7); // Require 7 matched tokens for recovery ``` The default is 5\. Higher values produce more conservative recovery \(fewer false recoveries, but potentially more tokens skipped\)\. The optimal value depends on your grammar and expected input\. ### Debug output ``` gp_set_debug_level(g, 3); ``` Debug levels range from 0 \(silent\) to 6 \(extremely verbose\): - **Level 1:**Statistics \(number of[SLR](https://en.wikipedia.org/wiki/SLR_grammar)sets, parse tree nodes, etc\.\) - **Level 2:**Additionally print the result translation \(AST\) - **Level 3:**Print read tokens, SLR set actions and conflicts, and high\-level error recovery information - **Level 4:**Print grammar rules, FIRST/FOLLOW sets, and all generated SLR sets - **Level 5:**Print stack operations during parsing and stack merging - **Level 6:**Even more detailed stack processing information ### Rule guards ``` gp_set_rule_guard(g, my_guard); ``` Rule guards allow you to reject specific rule reductions during parsing, enabling context\-sensitive parsing constraints\. Each rule alternative can have a guard number assigned in the grammar description \(using`? N`after the translation\) or via`read\_rule`\. When a rule with a guard number is about to be reduced, the guard function is called with that number and the`arg`passed to`gp\_parse`\. If the guard function returns`false`, the reduction is rejected\. The guard function can also prepare data for subsequent guard calls\. For example, using this mechanism you could distinguish typenames from identifiers in a C grammar, eliminating the need for ambiguous parsing and generation of alternative nodes\. ### Stack merging for ambiguous grammars ElkHound uses a mechanism to merge different translations of merged stacks\. Gecko uses an analogous mechanism, but with a more explicit interface\. ``` gp_set_node_merge_func(g, my_merge); ``` When the parser merges stacks \(because two parsing paths have reached the same state\), it needs to combine the parse tree nodes from both paths\. The default merge function simply returns the first node, effectively choosing one arbitrary parse\. If you want to preserve all alternatives \(e\.g\., for later semantic disambiguation\), you can use`gp\_get\_alt\_node`and`gp\_get\_opt\_node`: ``` void *my_merge(struct grammar *g, struct gp_tree_node *node1, struct gp_tree_node *node2, size_t context_num) { return context_num == 0 ? gp_get_alt_node(g, node1, node2) : gp_get_opt_node(g, node1, node2, context_num); } ``` This creates`GP\_ALT`or`GP\_OPT`nodes in the parse tree that represent all possible interpretations\. The`context\_num`argument defines the merge context\. A zero value indicates a context\-independent alternative\. A positive value indicates correlated alternatives –in such cases,`GP\_OPT`\(context\-dependent alternative\) nodes should be used instead of`GP\_ALT`to preserve the correct pairing of alternatives \(see the parse tree section below for details\)\. ## The parse tree Gecko’s parse tree is a tree of`struct gp\_tree\_node`values\. Each node has a`type`field and a`num`field \(a unique node number\), plus a C union containing the type\-specific data: - **`GP\_NIL`**–an empty node, used for empty translations - **`GP\_TERM`**–a terminal node, containing the terminal`code`and user\-provided`attr` - **`GP\_ANODE`**–an abstract node, containing a`name`string and an array of`children`\(each a pointer to another`gp\_tree\_node`\) - **`GP\_ALT`**–an alternative node \(for ambiguous grammars\), containing`first`and`second`pointers to two alternative parse trees - **`GP\_OPT`**–a context\-dependent alternative \(option\) node, containing a`context\_num`,`first`, and`second`\. Unlike`GP\_ALT`, option nodes indicate that the alternatives are correlated with other option nodes having the same`context\_num`\. For example, when merging stacks`\.\.\.a\.\.\.b\.\.\.`and`\.\.\.c\.\.\.d\.\.\.`, using`GP\_ALT`nodes would produce`\.\.\.alt\(a,c\)\.\.\.alt\(b,d\)\.\.\.`, which incorrectly implies four combinations \(`ac`,`ad`,`bc`,`bd`\) instead of the two correct ones \(`ac`,`bd`\)\.`GP\_OPT`nodes preserve this correlation:`\.\.\.opt\(n,a,c\)\.\.\.opt\(n,b,d\)\.\.\.`, where`n`is some context number\.  Fortunately, this is a rare case for programming language grammars; for example, the C grammar does not exhibit this behavior\. To correctly traverse the parse tree, you should always choose the same alternative \(`first`or`second`\) for option nodes with the same`context\_num`\. By doing so, it is possible to eliminate option nodes and transform the parse tree to contain only context\-independent alternative nodes, but this is a non\-trivial task\. If your grammar requires this, consider using[YAEP](https://github.com/vnmakarov/yaep), which handles this automatically\. The parse tree can be very unbalanced, so using recursive functions for traversal may cause stack overflow\. Gecko provides`gp\_traverse\_tree`, which uses an explicit stack instead of recursion\. It calls user\-provided`preorder`and`postorder`functions before and after processing each node’s children\. If the`preorder`function returns`false`, the node’s children are skipped\. Both callbacks receive the current node, its parent, and a user\-provided argument\. You can free the parse tree explicitly with: Or, if you provided a custom`parse\_free`function, all parse tree memory will be freed through that\. Setting`parse\_free`to`NULL`disables automatic freeing entirely, which is useful if you’re using arena allocation and plan to free everything at once\. ## Comparison with other parser technologies Here is a summary of how Gecko compares with the major alternatives: YACCBisonElkHoundYAEPGeckoLibraryNoNoNoYesYesCFG grammarLALR\(1\)LALR\(1\)AmbiguousAmbiguousAmbiguousOperator grammar \(priority/associativity\)YesYesYesNoYesSpeed independent of grammar sizeYesYesYesNoYesSyntax error recoveryYesYesNoYesYesAutomatic error recoveryNoNo–NoYesActionsYesYesYesNoYes\*Simple syntax\-directed translationNoNoNoYesYesGeneration of all translations––YesYesYesGeneration of minimal cost translation––NoYesNoReentrant \(thread\-safe\)Yes\*\*Yes\*\*YesNoYes\(\*\) See rule guard functions\. \(\*\*\) Needs non\-POSIX extensions`%pure\-parser`or`%define api\.pure`\. Key differentiators: - **Gecko and YAEP are the only libraries**–everything else requires a separate code generation step - **Gecko is the only parser with automatic error recovery**–all others require manual grammar modifications - **YAEP is the only parser without operator grammar support** - **YAEP can generate minimal\-cost translations**for ambiguous grammars, which Gecko doesn’t support\. YAEP is also faster when generating all possible translations for highly ambiguous grammars ## Benchmark results Performance claims are meaningless without data\. Gecko includes a comprehensive benchmark suite \(`make bench`\) that compares it against[YACC](https://invisible-island.net/byacc),[ElkHound](https://github.com/WeiDUorg/elkhound)\(a well\-known GLR parser\), and[YAEP](https://github.com/vnmakarov/yaep)\(a fast Earley parser\)\. ### Test setup The benchmarks use an**ANSI C grammar**as the test grammar\. For Gecko, ElkHound, and YAEP, the grammar is slightly ambiguous because typenames use the same token type as identifiers\. For YACC, typenames are a separate token type \(since YACC can’t handle the ambiguity\)\. Two test files are used: 1. **1\.5 million lines**of C code \(100,000 sieve functions\) 2. **500,000 lines**of C code \(an old version of GCC, all files combined\) Parsing time includes scanning time, but I found that even for the fastest parsers scanning takes at most 30% of the overall parsing time\. The benchmarks were run on four different architectures: - AMD Ryzen 9900X \(Fedora 43\) - Apple M4 \(Fedora 41\) - Intel 285 \(Fedora 42\) - IBM Power10 \(RHEL 10\) ### C grammar results: 1\.5M lines \(100K sieve functions\)  On this test, YAEP has unusually good results because it uses dynamic programming that speeds up parsing of files with repeating patterns\. The second test \(whole old GCC code as one file\) is more representative of real\-world parsing\. ### C grammar results: ~500K lines \(whole old GCC\)  This is the more interesting benchmark\. On realistic C code: - **Gecko is only 5–12% slower than YACC**across all architectures, while handling a grammar that YACC cannot even accept \(the ambiguous version\) - **Gecko is 2–2\.5x faster than ElkHound**and uses comparable memory - **Gecko is 2–3x faster than YAEP**and uses 3–4x less memory - Gecko can parse roughly**2 million lines of C per second**on an AMD 9900X To put this in perspective: Gecko parses the entire old GCC source tree in**0\.29 seconds**on modern hardware\. The numbers for`gcc \-fsyntax\-only`and`clang \-fsyntax\-only`, which only do fast hand\-written recursive descent parsing and basic semantic analysis, show that parsing is not the bottleneck of the compilers\. A 10% Gecko parser slowdown will not be critical\. ### Highly ambiguous grammar For the truly ambiguous grammar`E = E \+ E \| a`with input`a\(\+a\)\{200\}`\(200 plus operators\), Gecko’s GLR engine shows its strength:  Gecko is approximately**13x faster than ElkHound**and**7\.5x faster than YAEP**on this test\. This demonstrates that Gecko’s stack merging technique works extremely well even under heavy ambiguity \(see the next section\)\. Note: YAEP and Gecko generate AST for the test while ElkHound generates nothing and works only as a recognizer\. ## How Gecko works inside Understanding Gecko’s internal architecture helps explain its performance characteristics\. ### Grammar analysis When you call`gp\_parse\_grammar`or`gp\_read\_grammar`, Gecko performs several analysis passes: 1. **Symbol classification**–determine which symbols are terminals and which are nonterminals 2. **Empty detection**–identify nonterminals that can derive the empty string 3. **Accessibility analysis**–verify all nonterminals are reachable from the start symbol 4. **Terminal derivation**–verify all nonterminals can eventually derive terminal strings 5. **Loop detection**–detect nonterminals involved in cycles \(A =\>\* A\) 6. **FIRST/FOLLOW set computation**–via fixed\-point iteration, used for SLR set construction In strict mode \(`strict\_p = true`\), Gecko will report errors for unreachable nonterminals, nonterminals that can’t derive terminals, and grammar loops\. ### SLR set construction After analyzing grammar, Gecko constructs**SLR\(1\) sets**\(also known as LR\(0\) item sets with SLR lookaheads\)\. Each set contains a collection of LR items \(a rule plus a position within that rule\)\. LR items are**memoized**–each unique \(rule, position\) pair exists as exactly one object in memory\. Each SLR set has: - A**goto map**: for each nonterminal, which set to transition to - An**action map**: for each terminal, what actions to take \(shift, reduce, or both\) Conflicts in the action map \(shift\-reduce or reduce\-reduce\) are resolved using operator precedence and associativity declarations, exactly as in YACC\. Conflicts that cannot be resolved this way are left as multiple actions\. This is where GLR parsing takes over\. Setting the debug level to more than 2 before calling`gp\_parse\_grammar`or`gp\_read\_grammar`prints SLR sets, actions, and goto maps\. Conflicts in the output are marked with`\!`\. This debug information is useful for identifying where ambiguity can occur and for modifying the grammar as needed\. I initially tried building SLR sets on demand during parsing, but I found that for the C grammar, parsing even small files \(e\.g\., the sieve test\) results in building practically all possible SLR sets\. So I switched to building all SLR sets at once, which makes sense since building all SLR sets for the C grammar takes less than 1ms on an AMD 9900X\. ### The parsing algorithm Gecko’s GLR parser uses a two\-tier architecture that is key to its performance: **Single\-stack fast path\.**When there is exactly one parsing stack and exactly one possible action for the current token, Gecko runs a tight inner loop with no extra allocations\. This is the common case for unambiguous grammars and makes Gecko nearly as fast as a hand\-coded LALR\(1\) parser\. This is why Gecko achieves speeds within 5–10% of YACC on unambiguous grammars –for most tokens, it’s doing essentially the same work\. **Multi\-stack path\.**When ambiguity or unresolved conflicts create multiple possible actions, Gecko forks the stack and maintains multiple parsing paths simultaneously\. Each stack independently processes shifts and reduces\. Stacks that reach a dead end \(no valid action\) are discarded\. **Stack merging\.**When two stacks have identical state sequences \(i\.e\., they represent different parse trees but have arrived at the same parsing configuration\), they are merged\. The parse tree nodes from both stacks are combined using the user\-configurable merge function\. This prevents the exponential blowup that would otherwise occur with ambiguous grammars\. ### Garbage collection During parsing, Gecko periodically performs**garbage collection**of unreachable parse tree nodes\. This uses a mark\-sweep algorithm with a bitmap for marking\. The GC threshold is adaptive –it runs more frequently when many nodes are being created and less frequently when parsing is proceeding smoothly\. This is important for keeping memory consumption bounded during the parsing of long inputs, especially with ambiguous grammars where many intermediate nodes are created and then become unreachable as stacks are merged or discarded\. ## Building and installing Getting started with Gecko is straightforward: ``` cd gecko make # Build (requires GCC, YACC, AR) make test # Run tests (requires Flex, GCC with ASAN/UBSAN) make bench # Run benchmarks (requires YACC/Bison, GCC, Clang) make install # Install to /usr/local make PREFIX=/usr install # Or install to a custom prefix ``` After installation,`gecko\.h`goes to`$PREFIX/include`and`libgecko\.a`to`$PREFIX/lib`\. Link your program with`\-lgecko`\. To run the ElkHound benchmarks, pass the ElkHound build directory: ``` make bench ELKHOUND_DIR=/path/to/elkhound ``` ## Design philosophy Gecko reflects several deliberate design choices\. I preferred simplicity over generality\. Gecko doesn’t try to be a framework for arbitrary semantic analysis\. It produces ASTs and gets out of the way\. If you need more complex semantic processing, do it in a separate pass over the AST\. Performance comes through specialization\. The single\-stack fast path means that for the common case \(unambiguous input with an unambiguous grammar region\), Gecko does no more work than YACC\. The GLR machinery only kicks in when it’s actually needed\. Error recovery should be a fundamental parser feature, not an afterthought that grammar authors have to implement manually\. That is why Gecko’s recovery is fully automatic\. By being a library rather than a code generator, Gecko avoids the build complexity, debugging difficulty, and inflexibility that come with generated parsers\. ## When to use Gecko Gecko is a good fit when: - You need to parse a**context\-free grammar**that may have ambiguities - You want**good error recovery**without spending days adding`error`rules to your grammar - You need a**fast**parser but don’t want to write one by hand - You want to**embed a parser**in a larger C application - You need**operator precedence**handling without writing precedence cascades - Your grammar might**change at runtime**or you need multiple grammars Gecko might not be the best choice when: - You need sophisticated**semantic actions**during parsing \(Gecko uses primitive rule guards instead\) - You need**minimal\-cost translations**for highly ambiguous grammars or you need a guarantee that parsing complexity is no more than quadratic in input length \(consider YAEP\) - You need a parser in a language other than C \(Gecko is C\-only\) ## Getting the code Gecko is open source under the**MIT license**\. The source code, tests, and benchmarks are available on GitHub: [https://github\.com/vnmakarov/gecko](https://github.com/vnmakarov/gecko) --- ## Conclusion Gecko demonstrates that generalized parsing doesn’t have to mean slow parsing\. By combining a GLR algorithm with a single\-stack fast path, and adaptive garbage collection, Gecko achieves speeds within 5–10% of YACC on unambiguous grammars while handling the full class of context\-free grammars\. Its automatic error recovery eliminates one of the most painful aspects of working with traditional parser generators\. At 3,700 lines of C and 90KB of compiled code, Gecko is small enough to understand and fast enough for production use\. The final result is quite satisfactory, though I expect to continue improving it as new use cases and requirements arise\.