Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #2956

Re: How can the speed of a scanner be independent of the number of rules?

Show all headers | View raw

On Thursday, March 24, 2022 at 6:39:31 PM UTC+1, Roger L Costello wrote:
> Kaz Kylheku wrote:
>
> > suppose we have some existing scanner with 10 rules,
> > which correctly tokenizes an input. Then suppose we
> > add 990 rules to it. None of these rules take precedence
> > over the 10 rules, and so the the input is handled by the
> > same rules.
>
> Ouch!!!
>
> Such a letdown. So the statement "adding rules does not slow down the scanner"
> really isn't remarkable or awesome. Add 990 more irrelevant rules, and the
> scanner operates just as fast. Big deal.

That is, in my opinion, an invalid way of looking at scanning, because it
isn't computer science. A better way (I am not saying "the only right way") is
for example to compare the size of integers, the size of a memory address,
that a typical year-2022 CPU can process/access/read/write/lookup using in a
single CPU instruction. The fact is that the size of those integers and
addresses (such as: 32 bits, 64 bits) is extremely large compared to the
number of rules and complexity of any grammar that a human is able to directly
(by hand, by means of keyboard/mouse/touchscreen) enter into a computer. And,
creating a program just to generate or download an extremely large complex
grammar, containing quantities exceeding the capabilities of a single CPU
instruction and exceeding the size of memory installed in a typical year-2022
computer, is pointless.

-atom

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

How can the speed of a scanner be independent of the number of rules? Roger L Costello <costello@mitre.org> - 2022-03-23 18:49 +0000
  Re: How can the speed of a scanner be independent of the number of rules? Kaz Kylheku <480-992-1380@kylheku.com> - 2022-03-23 21:27 +0000
    Re: How can the speed of a scanner be independent of the number of rules? gah4 <gah4@u.washington.edu> - 2022-03-23 19:57 -0700
    Re: How can the speed of a scanner be independent of the number of rules? Christopher F Clark <christopher.f.clark@compiler-resources.com> - 2022-03-24 13:12 +0200
    Re: How can the speed of a scanner be independent of the number of rules? Roger L Costello <costello@mitre.org> - 2022-03-24 11:53 +0000
      Re: How can the speed of a scanner be independent of the number of rules? Jan Ziak <0xe2.0x9a.0x9b@gmail.com> - 2022-03-24 11:56 -0700
        Re: How can the speed of a scanner be independent of the number of rules? gah4 <gah4@u.washington.edu> - 2022-03-24 13:08 -0700
  Re: How can the speed of a scanner be independent of the number of rules? Jan Ziak <0xe2.0x9a.0x9b@gmail.com> - 2022-03-24 02:01 -0700
    Re: Parallel scanning, was How can the speed of a scanner be independent of the number of rules? Jan Ziak <0xe2.0x9a.0x9b@gmail.com> - 2022-03-24 11:18 -0700
      Parallel lexers by chunking the input Christopher F Clark <christopher.f.clark@compiler-resources.com> - 2022-03-24 22:32 +0200
        Re: Parallel lexers by chunking the input anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2022-03-25 08:04 +0000
          Re: Parallel lexers by chunking the input gah4 <gah4@u.washington.edu> - 2022-03-25 07:58 -0700
          Re: Parallel lexers by chunking the input anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2022-03-25 17:47 +0000
            Parallel lexers by chunking the input. Christopher F Clark <christopher.f.clark@compiler-resources.com> - 2022-03-26 00:36 +0200
            Parallel lexers by chunking the input Christopher F Clark <christopher.f.clark@compiler-resources.com> - 2022-03-26 01:00 +0200
            Re: Parallel lexers by chunking the input anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2022-03-26 09:27 +0000

csiph-web