[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: can i rewrite yyparse() based on ACTION and GOTO tables extracted fr
From: |
Christian Schoenebeck |
Subject: |
Re: can i rewrite yyparse() based on ACTION and GOTO tables extracted from XML output? |
Date: |
Sat, 06 Nov 2021 14:13:49 +0100 |
On Samstag, 6. November 2021 09:44:55 CET Akim Demaille wrote:
> Hi Levin,
>
> > Le 28 oct. 2021 à 08:24, elite liu <eligere.liu@gmail.com> a écrit :
> >
> > Dear Akim,
> >
> > I am writing a utility that convert a table-driven dfa into
> >
> > condition/if-else form, for example:
> > [...]
>
> I have always wondered if code won't be more efficient than tables.
> Since compiler and cpu have learned a lot of tricks to make code
> faster, I wouldn't be surprised to have some speedup.
>
> > If above codes are writen in tabled-driven implementation, it should be
> > more concise.
>
> Sure. And compactness is also cache friendliness. So I agree
> it is very much unclear which approach will beat the other one.
> On today's machines.
>
> Cheers.
The intended approach would still be a character by character procedure which
is much slower than allowing a lexer to perform string comparisons as much as
possible:
https://lemire.me/blog/2020/04/30/for-case-insensitive-string-comparisons-avoid-char-by-char-functions/
Keep in mind that most of the CPU time is usually spent on lexer side. So it
would make sense to optimize that first. However that's one of the issues
where you quickly realize that a split parser/lexer design is in the way. If
they were tied together, you could make much more aggressive optimizations by
having knowledge of both grammar and RegEx patterns.
For instance right now, whenever you have some input, the lexer must always
assume that any of the patterns may match. Whereas a tied grammar/lexer would
have the knowledge that for a certain parser state, only a small set of
patterns may match, which in turn would allow much more compact and faster
lexer branches for those states to be generated.
Best regards,
Christian Schoenebeck