bug-bison
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Implementing "%fallback" like in Lemon parser


From: Domingo Alvarez Duarte
Subject: Implementing "%fallback" like in Lemon parser
Date: Wed, 8 Nov 2023 11:19:08 +0100
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.11.0

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 !




reply via email to

[Prev in Thread] Current Thread [Next in Thread]