Return to the
comp.compilers page.
Search the
comp.compilers archives again.
| Related articles |
|---|
| From: | gah4 <gah4@u.washington.edu> |
| Newsgroups: | comp.compilers |
| Date: | Wed, 23 Mar 2022 19:57:45 -0700 (PDT) |
| Organization: | Compilers Central |
| References: | 22-03-047 22-03-048 |
| Injection-Info: | gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="64200"; mail-complaints-to="abuse@iecc.com" |
| Keywords: | lex, performance |
| Posted-Date: | 24 Mar 2022 13:02:35 EDT |
| In-Reply-To: | 22-03-048 |
On Wednesday, March 23, 2022 at 2:49:30 PM UTC-7, Kaz Kylheku wrote:
> On 2022-03-23, Roger L Costello <cost...@mitre.org> wrote:
(snip)
> > Note that adding rules does not slow down the scanner! The speed of the
> > scanner is independent of the number of rules or (modulo the considerations
> > given at the beginning of this section) how complicated the rules are with
> > regard to operators such as '*' and '|'.
(snip)
> In terms of theoretical computer science, it cannot be true that there
> is no slowdown regardless of the number of rules added. This is because
> the rules are compiled into tables, and tables are indexed by integers.
> Integers have to get wider (more bits) with increasing table size.
Yes, but 32 bit integers will get a huge number of states.
(snip)
> If the lexer is in a test case that does nothing but discard tokens,
> it may be that even though the 1000 rule lexer has a bigger cache
> footprint, it doesn't matter.
Yes, cache is the complication of just about any speed comparison.
And in this case, it depends not only on the scanner, but could be
sensitive to the actual input data.
It would seem that you could do the comparison based on the same
scanner, but using either UTF-8 or UTF-16 coded characters.
That would be closer to an apple vs. apple comparison.
Return to the
comp.compilers page.
Search the
comp.compilers archives again.