Re: [TUHS] [tuhs] Dennis Ritchie's couch

<resending with the program as an attachment, as 100K is considered big here? moderator, you can kill the prior message> To show you what I mean, here is a parser I wrote recently for a simple Go expression evaluator, in Go. It has all Go's precedence levels and operators. The one odd detail is that >= etc. can be combined, as in 1 >= 2 avoided with a few more lines in cmpList. I'm using a screen grab because GMail refuses to leave my indentation alone. I left factor off. It's got all the usual details but it's the leaf of the grammar and of no interest here. Note that this could easily have been made a table instead of a bunch of one-line functions. Parsers are easy to write. It took us a generation (or more) to understand that, but it's remarkable nonetheless. The first big step might have been realizing that recursion was a good idea, even if you weren't writing LISP, if the data structure is itself recursive. -rob On Fri, Jul 2, 2021 at 1:30 PM Rob Pike &lt;robpike(a)gmail.com&gt; wrote: > To show you what I mean, here is a parser I wrote recently for a simple Go > expression evaluator, in Go. It has all Go's precedence levels and > operators. The one odd detail is that >= etc. can be combined, as in 1 >= 2 > > avoided with a few more lines in cmpList. > > I'm using a screen grab because GMail refuses to leave my indentation > alone. I left factor off. It's got all the usual details but it's the leaf > of the grammar and of no interest here. > > Note that this could easily have been made a table instead of a bunch of > one-line functions. > > Parsers are easy to write. It took us a generation (or more) to understand > that, but it's remarkable nonetheless. The first big step might have been > realizing that recursion was a good idea, even if you weren't writing LISP, > if the data structure is itself recursive. > > -rob > > > [image: image.png] > > > On Fri, Jul 2, 2021 at 12:13 PM &lt;scj(a)yaccman.com&gt; wrote: > >> I found Dennis's compiler to be a thing of beauty when compiling >> statements, but hell on wheels when doing expressions. One of the >> motivations for writing Yacc was that I wanted to add the exclusive or into >> the expression syntax and we had agreed on the character (^) and the >> precedence. Practically the whole expression grammar needed to be >> rewritten, and small typos created un-debuggable chaos. The state of the >> art at the time was to write multi-layered grammars for each precedence >> level. A paper was published on how to shrink the resulting parsing tables >> by eliminating redundant states. I realized that the same results could >> be obtained by writing an ambiguous expression grammar and using a >> precedence table to resolve the ambiguities. The initial response in the >> academic community to programming with ambiguous grammars was somewhere >> between skeptical and horrified -- as if I had shown porn to a Victorian. >> So Al and I worked out a proof that we would get the same optimized parser >> in a much more intuitive way. >> >> I do agree with Rob that some of the languages that Yacc gave birth to >> should never have been born. Remember, though, that the dominant language >> at the time was FORTRAN, and it had all sorts of strange implementation >> issues in their hand-written compilers. Things like subscript indices had >> to be single variables in some places, and in others could have a constant >> added to the index. One of Yacc's best features was that it made >> consistency of usage the path of least resistance when designing the >> language, and the grammar was often easier to understand than the >> programming manual. At Bell Labs, Barbara Ryder wrote a program that would >> read FORTRAN and detect things that would not work on one or more of the >> six major FORTRAN's at the time. It was an inspiration for me, later, do >> the same thing with Lint. >> >> I do suggest that having languages like C++ that have bloated up to over >> 1000 pages in the programmer reference doesn't feel like a real advance, >> especially since the real language problems of today are how to program >> very large numbers of processor-like objects on a single chip. We need new >> ways to think, and I doubt that we'll get there by making C++ require a >> 2000-page manual. >> --- >> >> >> >> On 2021-05-25 23:52, Rob Pike wrote: >> >> I enjoy writing recursive descent parsers, and I enjoy the grammars that >> result from such parsers when cleanly done. >> >> I do agree though that if you grammar is being invented as you go, yacc >> can be a boon. But in a sense, that's also it's biggest failing: it makes >> it too easy to write bad grammars. >> >> -rob >> >> >> On Wed, May 26, 2021 at 4:22 PM Bakul Shah &lt;bakul(a)iitbombay.org&gt; wrote: >> >> Many existing programming languages do have a simple enough >> syntax to make it easy to write a recursive descent parser for them >> but not alll. >> >> Handwritten recursive descent parsers are often LL(1) with may be >> a separate operator-precedence parsing for expressions. >> >> If you are defining a new language syntax you can make sure parsing >> is easy but not all languages are LL(1) (which is a subset of LALR(1), >> which is a subset of LR(1), which is a subset of GLR). Handwritten >> parsers for these more general grammars are bound to get more >> complicated. >> >> Even *we* understand parsing, writing a parser for some existing >> languages which grew "organically" can become tedious, or >> complicated or adhoc. Often such languages have no well specified >> grammar (the code is the specification!). A yacc grammar would help. >> >> Often one writes a yacc grammar while a new language & its syntax >> is evolving. Changing a yacc file is more localized & easier than fixing >> up a handwritten parser. Even Go has such a grammar initially. >> >> -- Bakul >> >> > On May 25, 2021, at 8:03 PM, Larry McVoy &lt;lm(a)mcvoy.com&gt; wrote: >> > >> > You do, I don't. I'm not alone in my lack of understanding. >> > >> > I think that all the things that yacc solved, Steve gets some kudos. >> > I've used it a bunch and I did not need to be as smart as you or >> > Steve to get the job done. >> > >> > You getting past that is cool but it doesn't make his work less. >> > >> > On Wed, May 26, 2021 at 10:37:45AM +1000, Rob Pike wrote: >> >> And today, we understand parsing so well we don't need yacc. >> >> >> >> -rob >> >> >> >> >> >> On Wed, May 26, 2021 at 10:20 AM Nelson H. F. Beebe < >> beebe(a)math.utah.edu&gt; >> >> wrote: >> >> >> >>> The last article of the latest issue of the Communications of the ACM >> >>> that appeared electronically earlier today is a brief interview with >> >>> this year's ACM Turing Award winners, Al Aho and Jeff Ullman. >> >>> >> >>> The article is >> >>> >> >>> Last byte: Shaping the foundations of programming languages >> >>> https://doi.org/10.1145/3460442 >> >>> Comm. ACM 64(6), 120, 119, June 2021. >> >>> >> >>> and it includes a picture of the two winners sitting on Dennis >> >>> Ritchie's couch. >> >>> >> >>> I liked this snippet from Jeff Ullman, praising fellow list member >> >>> Steve Johnson's landmark program, yacc: >> >>> >> >>>>> ... >> >>>>> At the time of the first Fortran compiler, it took several >> >>>>> person-years to write a parser. By the time yacc came around, >> >>>>> you could do it in an afternoon. >> >>>>> ... >> >>> >> >>> >> >>> >> ------------------------------------------------------------------------------- >> >>> - Nelson H. F. Beebe Tel: +1 801 581 5254 >> >>> - >> >>> - University of Utah FAX: +1 801 581 4148 >> >>> - >> >>> - Department of Mathematics, 110 LCB Internet e-mail: >> >>> beebe(a)math.utah.edu - >> >>> - 155 S 1400 E RM 233 beebe(a)acm.org >> >>> beebe(a)computer.org - >> >>> - Salt Lake City, UT 84112-0090, USA URL: >> >>> http://www.math.utah.edu/~beebe/ - >> >>> >> >>> >> ------------------------------------------------------------------------------- >> >>> >> > >> > -- >> > --- >> > Larry McVoy lm at mcvoy.com >> http://www.mcvoy.com/lm >> >>