Implementing "%fallback" like in Lemon parser
Domingo Alvarez Duarte <[email protected]> Wed, 8 Nov 2023 11:19:08 +0100
| Newsgroups | gmane.comp.parsers.bison.bugs |
|---|---|
| Message-ID | <[email protected]> |
I've been adding grammars to https://mingodad.github.io/parsertl-playground/playground/ an "Yacc/Lex" compatible wasm/online editor/tester and for grammars with big number of soft keywords like PostgreSQL, Vitess, ... the resources usage in terms of memory/time/size for the parser grows exponentially proportional to the number of such tokens. The Lemon parser generator has an option "%fallback" (see https://sqlite.org/src/doc/trunk/doc/lemon.html#pfallback ) that reduce the resources usage and also has less probabilities of generating conflicts. I've implemented it on https://mingodad.github.io/parsertl-playground/playground/ and I've got good performance gains: Statistics of Vitess SQL parser (be patient)(partially working): ==== build master parser -> Time taken : 87ms parse user grammar -> Time taken : 5ms start build user grammar -> Time taken : 2ms build user parser -> Time taken : 1481ms dump input parser tree -> Time taken : 10ms ==== Statistics of Vitess SQL parser with fallback (partially working): ==== build master parser -> Time taken : 34ms parse user grammar -> Time taken : 3ms start build user grammar -> Time taken : 0ms build user parser -> Time taken : 446ms dump input parser tree -> Time taken : 5ms ==== Would be nice to have the same implemented in bison. What is the opinion of people on this list ? Cheers !