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

On Thursday, March 24, 2022 at 12:19:52 PM UTC-7, Jan Ziak wrote:


(snip)


> 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.


This distinction comes up more often for sorting algorithms,
but I suppose it applies here, too.


If one wants to sort a gigabyte of bytes, that is elements of length
one (8 bit) byte, it is faster to count them, and then generate an output
file with the appropriate number of each byte.


Depending on how you do the measurement, that violates some rule
on sorting algorithms.


> 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.


Some years ago, I was working on using DFA for DNA sequence comparison.


I did, at least, do some tests with millions of states, maybe tens of
millions. (The alphabet size is four, so you can fit a lot of states in memory.)


But yes, I didn't try to enter the states using a keyboard, mouse,
or other human interface device.


Reminds me, though, of some years ago, close to the time I was working
on that one, it was said that much of the DNA sequences in GenBank were
obtained by OCR scanning the pages of journal articles. The fraction that
were obtained that way kept decreasing, but the number was increasing.
(Like Moore's law, the size of the GenBank increases exponentially,
last I knew at 1%/week.)

Return to the comp.compilers page.
Search the comp.compilers archives again.