Path: csiph.com!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end From: gah4 Newsgroups: comp.compilers Subject: Re: Are compiler developers light-years ahead of other software development? Date: Mon, 17 Jan 2022 07:14:48 -0800 (PST) Organization: Compilers Central Lines: 31 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <22-01-064@comp.compilers> References: <22-01-059@comp.compilers> Mime-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="96741"; mail-complaints-to="abuse@iecc.com" Keywords: theory Posted-Date: 17 Jan 2022 22:15:42 EST X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com In-Reply-To: <22-01-059@comp.compilers> Xref: csiph.com comp.compilers:2838 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.