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

3, but that doesn't matter in the context of this program and is easily

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 <bakul(a)iitbombay.org> 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 beebe(a)math.utah.edu> ------------------------------------------------------------------------------- ------------------------------------------------------------------------------- http://www.mcvoy.com/lm