gecko

KO | EN

gitlite — search

#codex #awesome #cpp #vue #macos #javascript #chatbot #nextjs #markdown #kubernetes

(★ 31)

Gecko: a fast GLR parser with automatic syntax error recovery

File Explorer

ZIP Download

- ambig.c
- ansic.h
- ansic.l
- ansic.y
- bench-arena.c
- common.h
- compare.sh
- elkh-ambig.gr
- elkh-c.gr
- eof_hang.c
- eof_hang.out
- eof_hang2.c
- eof_hang2.out
- gcc.i
- gcc_for_clang.i
- gcc_for_gcc.i
- lex.yy.c
- sieve.c
- small_test.i
- test.i
- test.sh
- test01.c
- test02.c
- test03.c
- test03.out
- test04.c
- test04.out
- test05.c
- test05.out
- test06.c
- test06.out
- test07.c
- test07.out
- test08.c
- test08.out
- test09.c
- test09.out
- test1.i
- test10.c
- test10.out
- test11.c
- test11.out
- test12.c
- test12.out
- test13.c
- test13.out
- test14.c
- test14.out
- test15.c
- test15.out
- test16.c
- test16.out
- test17.c
- test17.out
- test18.c
- test18.out
- test19.c
- test19.out
- test20.c
- test20.out
- test21.c
- test21.out
- test22.c
- test22.out
- test23.c
- test23.out
- test24.c
- test24.out
- test25.c
- test25.out
- test26.c
- test26.out
- test27.c
- test27.out
- test28.c
- test28.out
- test29.c
- test29.out
- test30.c
- test30.out
- test31.c
- test31.out
- test32.c
- test32.out
- test33.c
- test33.out
- test34.c
- test34.out
- test35.c
- test35.out
- test36.c
- test36.out
- test37.c
- test37.out
- test38.c
- test38.out
- test39.c
- test39.out
- test40.c
- test41.c
- test41.out
- test42.c
- test42.out
- test43.c
- test43.out
- test44.c
- test44.out
- test_ambig_elkh.cc
- test_common.c
- test_elkh.cc
- test_gecko.c
- test_yyparse.c
- ticker.h
.clang-format
allocate.h
bitmap.h
GECKO-API.md
gecko.c
gecko.h
gecko.png
GNUmakefile
hash.h
hashtab.h
objstack.h
README.md
sgramm.y
vlobject.h

# Use via CDN

jsDelivr

jsDelivr serves any public GitHub repository as a CDN with zero setup. Pick a version and a file to get a ready-to-paste link and snippet.

Version

File

Link

Example

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

![Gecko](https://raw.githubusercontent.com/vnmakarov/gecko/master/gecko.png)

* Gecko is licensed under the MIT license
  * More details about Gecko can be found in [blogpost](https://vnmakarov.github.io/parsing/compilers/c/open-source/2026/04/22/gecko-glr.html)
  
## Features

* Parse inputs described by **unambiguous and ambiguous grammars**
* Small and simple
  * x86-64 code size is only 90KB
  * 3.8K C SLOC
* Strong emphasis on good automatic syntax error recovery and error reporting, as this is a complicated feature in other compiler-compilers
  * Requires no grammar modifications
  * Simple interface for custom support of syntax error reporting
* Fast
  * Close to YACC/Bison speed on unambiguous grammars (about 5-10% slower)
  * Processes 2M C lines per second on AMD9900X
  * 2 times faster than [YAEP](https://github.com/vnmakarov/yaep) (the fastest Earley parser I know)
    on unambiguous and moderately ambiguous grammars
  * 2.5 times faster than [ElkHound](https://github.com/WeiDUorg/elkhound) (a famous GLR parser)
    on unambiguous and moderately ambiguous grammars
  * about 8-13 times faster than YAEP and ElkHound on highly ambiguous grammars
* Operator grammar support
  * Descriptions of operator priority and associativity analogous to YACC/Bison
* Simple syntax-directed translation
  * Generates **abstract syntax tree** as output
* Library
  * Can be embedded into other programs
  * A grammar for Gecko can be constructed through function calls or using
    a YACC-like description syntax
  * Very **fast startup** after reading a grammar from a file or string

## Comparison of major features of compiler-compilers

|                                         | YACC    | Bison   | ElkHound | YAEP     | Gecko    |
|-----------------------------------------|---------|---------|----------|----------|----------|
|Library                                  | No      | No      | No       | Yes      | Yes      |
|CFG grammar                              | LALR(1) | LALR(1)*| ambiguous| ambiguous| ambiguous|
|Operator grammar (priority/associativity)| Yes     | Yes     | Yes      | No       | Yes      |
|Speed independent of grammar size        | Yes     | Yes     | Yes      | No       | Yes      |
|Syntax error recovery                    | Yes     | Yes     | No       | Yes      | Yes      |
|Automatic error recovery                 | No      | No      | -        | No       | Yes      |
|Actions                                  | Yes     | Yes     | Yes      | No       | Yes**    |
|Simple syntax-directed translation       | No      | No      | No       | Yes      | Yes      |
|Generation of all translations           | -       | -       | Yes      | Yes***   | Yes***   |
|Generation of minimal cost translation   | -       | -       | No       | Yes      | No       |
|Reentrant (thread-safe)                  | Yes**** | Yes**** | Yes      | No       | Yes      |

\* Bison is claimed to be a GLR parser but I did not manage to use **ambiguous** C grammar (see speed comparison) for it

\** See rule guard functions.

\*** All alternatives can be generated through the corresponding ElkHound/Gecko merge functions.
   But to generate abstract node trees for alternatives analogous to YAEP, additional non-trivial work needs to be done.

\**** Needs non-POSIX extensions `%pure-parser` or `%define api.pure`.

* Additional differences between Gecko and YAEP:
  * Gecko is faster on unambiguous and moderately ambiguous grammars
  * Gecko requires less memory for parsing
  * Gecko memory consumption does not depend on input length (or depends slightly for ambiguous grammars)
  * Gecko permits shorter grammars by supporting operator grammars (operator associativity
    and precedence) analogously to YACC/Bison
  * YAEP is faster on highly ambiguous grammars when all possible translations or minimal cost translation
    are required.  It also generates a much smaller parse tree (DAG) for all possible translations of highly ambiguous grammars

# Gecko usage example:

* The following is a small example of how to use Gecko to parse expressions.  We have omitted the functions
  `read_token`, `syntax_error_func`, `parse_alloc_func`, and `parse_free_func` which are needed to provide tokens,
  print syntax error messages, and allocate memory for the parser.

```
static const char *description =
"\n"
"TERM NUMBER;\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 void parse (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);
  }
  if (gp_parse (g, read_token_func, &root, &ambiguity, NULL))
    fprintf (stderr, "gp_parse: %s\n", gp_error_message (g));
  gp_fin (g);
}
```

## Installing
  * ``cd <srcdir>``
  * ``make``
    * requires GCC, YACC, AR
  * ``make test`` (optional)
    * requires Flex and GCC with ASAN and UBSAN support
  * ``make bench`` (optional)
    * requires YACC/BISON, GCC, Clang, installed YAEP and built Elkhound (use `make bench ELKHOUND_DIR=<path>` to run Elkhound benchmarks)
  * ``make install``
    * `gecko.h` and `libgecko.a` will be installed in `/usr/local/include` and `/usr/local/lib`
    * You can change installation path `/usr/local` by using makefile arg `PREFIX`, e.g. `make PREFIX=/usr install`
    
## Speed comparison with YACC, ElkHound, YAEP, and GCC/Clang parsers

* Test machines:
  * AMD Ryzen 9900X with 64GB memory under Fedora Core 43.
  * Apple M4 with 8GB memory under Fedora Core 41.
  * Intel 285 with 32GB memory under Fedora Core 42.
  * IBM Power10 with 2TB memory under RHEL10.
* Tested parsers:
  * Berkeley YACC 1.9
  * GCC-15.2.1 for AMD9900X and Intel 285, GCC-14.2.1 for Apple M4, and GCC-11.5.0 for Power10
  * Clang-21.1.8 for AMD9900X, Clang-20.0.8 for Intel 285, Clang-19.1.5 for Apple M4, Clang-20.1.8 for Power10
  * YAEP as of Oct. 2015.
  * [ElkHound](https://github.com/WeiDUorg/elkhound) as of 2019-02-17 (a GLR parser)
* Bison is claimed to be a GLR parser but I did not manage to use **ambiguous**
  C grammar (see below) for it.  Therefore, and because its results on **unambiguous**
  C grammar are close to YACC's, I excluded it from the tests.
* Grammar:
  * The base test grammar is the **ANSI C** grammar which is mostly
    a left-recursive grammar.
  * For YAEP, ElkHound, and Gecko, the grammar is slightly **ambiguous** as typenames
    are represented with the same kind of token as identifiers.
  * For the YACC description, typename is a separate token type distinct from
    other identifiers.  The YACC description does not contain any actions except
    for a small number needed to give feedback to the scanner on how to treat
    the next identifier (as a typename or regular identifier).
* Scanning test files:
  * For YACC, at the scanning stage we do not yet distinguish identifiers and typenames.
  * Parsing time includes scanning time, but even for the fastest parsers scanning takes at most 30% of
    the overall parsing time.
* Tests:
  * The first test is 100K sieve functions, so the resulting file size was 1.5M C lines.
  * The second test is a pre-release version of gcc-4.0 for i686 with all the source
    code combined into one file
    ([source](http://people.csail.mit.edu/smcc/projects/single-file-programs/)).
    The file size was 635K C lines.
  * The C pre-processor was applied to the files.
  * Additional preparations were made for YACC, YAEP, and Gecko:
    * GCC extensions (mostly attributes and asm) were removed from the
      pre-processed files.  The removed code is a tiny and insignificant
      fraction of the entire code.
    * A very small number of identifiers were renamed for the 2nd file to avoid confusing
      the simple YACC actions to distinguish typenames and identifiers.  So the resulting code
      is not correct as C code but it is correct from the syntactic point of view.
* Measurements:
  * The result times are elapsed (wall) times.
  * Memory is peak allocated memory for AMD9900X, the results are close to those on other 64-bit targets
  * For GCC and Clang, memory was instead measured as max resident memory reported by ``/usr/bin/time``.
* How to reproduce: please use `make bench`.

## Benchmark Results

* C grammar
  * First file (**1500K** lines) consisting of 100K sieve functions:

|                      | AMD9900X(sec) | Apple M4(sec)  | Intel 285(sec)  | Power10(sec) | Max Memory MB  |
|----------------------|--------------:|---------------:|----------------:|-------------:|---------------:|
|gcc -fsyntax-only     |   2.93        |   2.73         |  2.58           |  7.07        |   1144         |
|gcc -O0               |  43.66        |  49.48         | 45.66           |112.73        |   6200         |
|clang -fsyntax-only   |   1.95        |   3.37         |  2.96           | 15.22        |    529         |
|clang -O0             |   6.45        |  17.52         |  9.13           | 39.07        |   2176         |
|YACC                  |   0.68        |   0.56         |  0.58           |  1.24        |    339         |
|ElkHound              |   1.27        |   1.45         |  1.14           |  2.75        |    127         |
|YAEP                  |   0.62        |   0.77         |  0.92           |  1.90        |   1152         |
|Gecko                 |   0.71        |   0.69         |  0.74           |  1.77        |    340         |

* YAEP has very good results as it uses dynamic programming to speed up Earley's parser
    and therefore it works very fast on files consisting of repeating parts.
  * The file below is more realistic for speed comparison.
      
  * Second file (~**500K** lines) -- a whole old gcc:

|                      |  AMD9900X(sec) |  Apple M4(sec) | Intel 285 (sec)| Power10(sec)| Max Memory MB  |
|----------------------|---------------:|---------------:|---------------:|------------:|---------------:|
|gcc -fsyntax-only     |   0.73         |   0.97         |   0.78         |   1.81      |    283         |
|gcc -O0               |   8.52         |   8.98         |   8.44         |  19.06      |    881         |
|clang -fsyntax-only   |   0.69         |   1.03         |   0.94         |   4.14      |    223         |
|clang -O0             |   2.08         |   4.07         |   2.78         |  10.49      |    470         |
|YACC                  |   0.26         |   0.29         |   0.26         |   0.59      |    123         |
|ElkHound              |   0.73         |   0.84         |   0.71         |   1.73      |    127         |
|YAEP                  |   0.66         |   1.03         |   0.71         |   1.33      |    471         |
|Gecko                 |   0.29         |   0.30         |   0.31         |   0.68      |    124         |

* GCC and Clang have a slightly different test as other parsers cannot take
    C extensions in the original test.

* Highly ambiguous grammar (E=E+E|a) with abstract tree generation
  * Input is `a(+a){200}`.  In other words, 200 operators `+` are used:
  
|                      | AMD9900X(sec) | Apple M4(sec) | Intel 285 (sec) | Power10(sec) |Memory (parse only) MB|
|----------------------|--------------:|--------------:|----------------:|-------------:|---------------------:|
|ElkHound              |  9.50         |  15.65        |  10.82          |  13.82       |  9.6                 |
|YAEP                  |  5.53         |   7.67        |   5.77          |  13.40       |  154                 |
|Gecko                 |  0.73         |   0.80        |   0.84          |   1.59       |   74                 |

* Note: YAEP and Gecko generate AST for the test while ElkHound generates nothing and works only as a recognizer.

## Gecko internals overview

* Gecko uses custom allocators, hash tables, variable-length objects, and object stacks from accompanying header-only libraries
* Grammar analysis computes symbol properties (empty, accessible, derives terminals), detects loops, and builds FIRST/FOLLOW
  sets via fixed-point iteration
* After analyzing grammar, Gecko constructs SLR(1) sets of the grammar
  * LR items (situations) are memoized -- each unique (rule, position) pair exists once
  * Each SLR set has a goto map (nonterminal → set) and action map (terminal → shift/reduce actions)
  * Priority/associativity conflict resolution is applied the same way for the action map as in YACC
* Parsing
  * **Single-stack fast path**: when one stack has exactly one action, a tight inner loop
    runs without extra allocations -- this makes unambiguous grammars nearly as fast as YACC
  * **Multi-stack path**: multiple stacks are maintained when ambiguity or conflicts arise;
    each stack independently processes shifts and reduces
  * **Stack merging**: stacks with identical state sequences are merged, combining parse tree
    nodes via a user callback `gp_node_merge_func_t(grammar, node1, node2, context_num)`.
    A negative `context_num` indicates a context-independent alternative; a non-negative value
    indicates correlated alternatives where `GP_OPT` nodes should be used instead of `GP_ALT`
    to preserve the correct pairing. This prevents exponential blowup on ambiguous grammars
  * Parse tree nodes are **hash-consed** (structurally identical nodes are shared)
  * **Garbage collection** of unreachable parse tree nodes runs periodically during parsing (mark-sweep using a bitmap,
    with adaptive threshold)

## Syntax error recovery

* Gecko implements automatic **minimal-cost error recovery** that requires
  no grammar modifications — unlike YACC/Bison/YAEP, you don't need to add
  `error` rules to your grammar

* As Gecko can deal with numerous parsing stacks, this permits implementing a high-quality syntax recovery algorithm

* The syntax error recovery guarantees that Gecko always produces parse trees corresponding to
  syntactically correct inputs -- simply, some tokens before and after the error token are ignored

* Error recovery algorithm in brief:
  * For each failed stack, we reject the current stack token and add 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
  * We stop error recovery when we have a minimal cost stack that successfully consumed a given number (defined by
    `gp_set_recovery_match`) of tokens without a gap or when we have a final stack that consumed `EOF`
  * All stacks that matched at least one token become the start stacks after the recovery

gecko

Owner Repos

File Explorer

# Use via CDN

Was this content helpful?

Recent Feedback

gecko

Owner Repos

File Explorer

# Use via CDN

Was this content helpful?

Recent Feedback

Download README