Re: Are compiler developers light-years ahead of other software development?

On Sunday, January 16, 2022 at 9:26:38 AM UTC-8, Roger L Costello wrote:
> Hello Compiler Experts!


> I am learning the algorithms and theory underlying parsing. Wow! I am
> discovering that parsing has such a rich theoretical foundation: grammars, LL,
> LR, first() function, following() function, parsing tables, etc.


(snip)


> I can't think of any other branch of computer science where there is such a
> rich foundation upon which to develop software.


Thinking about D.E.Knuth's "The Art of Computer Programming", there is a whole
book (volume 3), "Sorting and Searching". A large fraction of important
algorithms rely on the foundation of search algorithms. (And if you sort, you can
use binary search to find thinks.)


Now, some of the book is based on the now lost art of sorting data on
magnetic tape, where one has only sequential access to most of the data.


Others will tell you that Quicksort is all you need to know, and forget
the rest of the book.


In any case, I vote for sorting and searching algorithms as the rich theoretical
foundation of much of CS. Hash tables are in important part
of many compilers. Dynamic programming algorithms are used in
many optimization problems, and fundamental to many algorithms.


The dynamic programming algorithm used by the Unix diff command,
to find an optimal set of differences between two files, originated
from biologists comparing protein sequences.

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