From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-0.1 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,HTML_MESSAGE,MAILING_LIST_MULTI,PDS_SHORTFWD_URISHRT_QP, RCVD_IN_DNSWL_NONE,URI_DOTEDU_ENTITY autolearn=ham autolearn_force=no version=3.4.4 Received: (qmail 327 invoked from network); 2 Jul 2021 02:29:07 -0000 Received: from minnie.tuhs.org (45.79.103.53) by inbox.vuxu.org with ESMTPUTF8; 2 Jul 2021 02:29:07 -0000 Received: by minnie.tuhs.org (Postfix, from userid 112) id C6C5C9C87C; Fri, 2 Jul 2021 12:29:06 +1000 (AEST) Received: from minnie.tuhs.org (localhost [127.0.0.1]) by minnie.tuhs.org (Postfix) with ESMTP id 74BF19C861; Fri, 2 Jul 2021 12:28:13 +1000 (AEST) Authentication-Results: minnie.tuhs.org; dkim=pass (1024-bit key; unprotected) header.d=yaccman.com header.i=@yaccman.com header.b="keGlFCNk"; dkim-atps=neutral Received: by minnie.tuhs.org (Postfix, from userid 112) id 64E4D9C861; Fri, 2 Jul 2021 12:28:11 +1000 (AEST) X-Greylist: delayed 903 seconds by postgrey-1.36 at minnie.tuhs.org; Fri, 02 Jul 2021 12:28:10 AEST Received: from donkey.elm.relay.mailchannels.net (donkey.elm.relay.mailchannels.net [23.83.212.49]) by minnie.tuhs.org (Postfix) with ESMTPS id 59A0E9C854 for ; Fri, 2 Jul 2021 12:28:10 +1000 (AEST) X-Sender-Id: dreamhost|x-authsender|scj@yaccman.com Received: from relay.mailchannels.net (localhost [127.0.0.1]) by relay.mailchannels.net (Postfix) with ESMTP id 464ED342BD0; Fri, 2 Jul 2021 02:13:07 +0000 (UTC) Received: from pdx1-sub0-mail-a41.g.dreamhost.com (100-96-11-26.trex.outbound.svc.cluster.local [100.96.11.26]) (Authenticated sender: dreamhost) by relay.mailchannels.net (Postfix) with ESMTPA id 6A876342C77; Fri, 2 Jul 2021 02:13:06 +0000 (UTC) X-Sender-Id: dreamhost|x-authsender|scj@yaccman.com Received: from pdx1-sub0-mail-a41.g.dreamhost.com (pop.dreamhost.com [64.90.62.162]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384) by 100.96.11.26 (trex/6.3.3); Fri, 02 Jul 2021 02:13:07 +0000 X-MC-Relay: Neutral X-MailChannels-SenderId: dreamhost|x-authsender|scj@yaccman.com X-MailChannels-Auth-Id: dreamhost X-Plucky-Stretch: 1d3257dd16bcbf12_1625191987135_3198048552 X-MC-Loop-Signature: 1625191987134:2660727179 X-MC-Ingress-Time: 1625191987134 Received: from pdx1-sub0-mail-a41.g.dreamhost.com (localhost [127.0.0.1]) by pdx1-sub0-mail-a41.g.dreamhost.com (Postfix) with ESMTP id 14E607ECDC; Thu, 1 Jul 2021 19:13:06 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=yaccman.com; h= mime-version:date:from:to:cc:subject:in-reply-to:references :message-id:content-type; s=yaccman.com; bh=kumxmXTe2cjJPjeCCPvf U6Y3+pw=; b=keGlFCNkumbw0CtkGttXYg9mPHEMKbexlW8IFKWYzHljlxI7vGMs xQoOhVIiXm+8z9xS126SHQd9BUokV1CG7D9JpHjf52ufS+tuClkAAatTxzMLoHNs P8KwDcVTK6nRvSBVhT1fub+agJ/rQ6H0AXnhJmn+oM7430wbE/X7m8Y= Received: from webmail.dreamhost.com (ip-66-33-200-4.dreamhost.com [66.33.200.4]) (Authenticated sender: scj@yaccman.com) by pdx1-sub0-mail-a41.g.dreamhost.com (Postfix) with ESMTPA id AD8BF7ECDA; Thu, 1 Jul 2021 19:13:05 -0700 (PDT) MIME-Version: 1.0 Date: Thu, 01 Jul 2021 19:13:05 -0700 X-DH-BACKEND: pdx1-sub0-mail-a41 From: scj@yaccman.com To: Rob Pike In-Reply-To: References: <20210526030341.GD27558@mcvoy.com> <2834EEEA-1C32-461B-900B-7480CCC4399B@iitbombay.org> User-Agent: DreamHost Webmail/1.4.1 Message-ID: X-Sender: scj@yaccman.com Content-Type: multipart/alternative; boundary="=_544f96af4a5ab26c41a752d6690e0582" Subject: Re: [TUHS] [tuhs] Dennis Ritchie's couch X-BeenThere: tuhs@minnie.tuhs.org X-Mailman-Version: 2.1.26 Precedence: list List-Id: The Unix Heritage Society mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Bakul Shah , The Unix Heritage Society mailing list Errors-To: tuhs-bounces@minnie.tuhs.org Sender: "TUHS" --=_544f96af4a5ab26c41a752d6690e0582 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset=US-ASCII; format=flowed 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 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 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 >>>> 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@math.utah.edu - >>>>> - 155 S 1400 E RM 233 beebe@acm.org >>>>> beebe@computer.org - >>>>> - Salt Lake City, UT 84112-0090, USA URL: >>>>> http://www.math.utah.edu/~beebe/ - >>>>> >>>>> ------------------------------------------------------------------------------- >>>>> >>> >>> -- >>> --- >>> Larry McVoy lm at mcvoy.com [1] http://www.mcvoy.com/lm Links: ------ [1] http://mcvoy.com --=_544f96af4a5ab26c41a752d6690e0582 Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset=UTF-8

I found Dennis's compiler to be a thing of beauty when compiling stateme= nts, but hell on wheels when doing expressions.  One of the motivation= s for writing Yacc was that I wanted to add the exclusive or into the expre= ssion syntax and we had agreed on the character (^) and the precedence.&nbs= p; Practically the whole expression grammar needed to be rewritten, and sma= ll typos created un-debuggable chaos.  The state of the art at the tim= e was to write multi-layered grammars for each precedence level.  A pa= per was published on how to shrink the resulting parsing tables by eliminat= ing 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 academ= ic community to programming with ambiguous grammars was somewhere between s= keptical and horrified -- as if I had shown porn to a Victorian.  So A= l 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 s= hould never have been born.  Remember, though, that the dominant langu= age at the time was FORTRAN, and it had all sorts of strange implementation= issues in their hand-written compilers.  Things like subscript indice= s had to be single variables in some places, and in others could have a con= stant added to the index.  One of Yacc's best features was that it mad= e consistency of usage the path of least resistance when designing the lang= uage, and the grammar was often easier to understand than the programming m= anual.  At Bell Labs, Barbara Ryder wrote a program that would read FO= RTRAN 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 s= ame 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, e= specially since the real language problems of today are how to program very= large numbers of processor-like objects on a single chip.  We need ne= w ways to think, and I doubt that we'll get there by making C++ require a 2= 000-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, yac= c 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 Bak= ul Shah <bakul= @iitbombay.org> wrote:
Many existing programming = languages do have a simple enough
syntax to make it easy to write a re= cursive descent parser for them
but not alll.

Handwritten r= ecursive descent parsers are often LL(1) with may be
a separate opera= tor-precedence parsing for expressions.

If you are defining a ne= w language syntax you can make sure parsing
is easy but not all langua= ges 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 gener= al grammars are bound to get more
complicated.

Even *we* un= derstand parsing, writing a parser for some existing
languages  w= hich grew "organically" can become tedious, or
complicated or adhoc. O= ften such languages have no well specified
grammar (the code is the sp= ecification!). A yacc grammar would help.

Often one writes a yac= c grammar while a new language & its syntax
is evolving. Changing = a yacc file is more localized & easier than fixing
up a handwritte= n parser. Even Go has such a grammar initially.

-- Bakul
> On May 25, 2021, at 8:03 PM, Larry McVoy <lm@mcvoy.com> wrote:
>
&= gt; 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 so= me 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 get= ting past that is cool but it doesn't make his work less.
>
&= gt; 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, Ma= y 26, 2021 at 10:20 AM Nelson H. F. Beebe <beebe@math.utah.edu>
>> w= rote:
>>
>>> The last article of the latest issue= of the Communications of the ACM
>>> that appeared electroni= cally earlier today is a brief interview with
>>> this year's= ACM Turing Award winners, Al Aho and Jeff Ullman.
>>>
= >>> The article is
>>>
>>>  &nbs= p;     Last byte: Shaping the foundations of programming language= s
>>>        https://doi= =2Eorg/10.1145/3460442
>>>        Com= m. ACM 64(6), 120, 119, June 2021.
>>>
>>> and= it includes a picture of the two winners sitting on Dennis
>>&g= t; Ritchie's couch.
>>>
>>> I liked this snipp= et from Jeff Ullman, praising fellow list member
>>> Steve Jo= hnson's landmark program, yacc:
>>>
>>>>>= ; ...
>>>>> At the time of the first Fortran compiler, = it took several
>>>>> person-years to write a parser.&n= bsp; By the time yacc came around,
>>>>> you could do i= t in an afternoon.
>>>>> ...
>>>
&g= t;>>
>>> ---------------------------------------------= ----------------------------------
>>> - Nelson H. F. Beebe&n= bsp;                   Tel: +1= 801 581 5254
>>>    -
>>> - Universi= ty of Utah                  &n= bsp; FAX: +1 801 581 4148
>>>    -
>>>= ; - Department of Mathematics, 110 LCB    Internet e-mail:
&= gt;>> beebe= @math.utah.edu  -
>>> - 155 S 1400 E RM 233  &n= bsp;                    <= a href=3D"mailto:beebe@acm.org" rel=3D"noreferrer">beebe@acm.org
&= gt;>> beebe@= computer.org -
>>> - Salt Lake City, UT 84112-0090, USA&n= bsp;   URL:
>>> http://www.math.utah.edu= /~beebe/ -
>>>
>>> -----------------------= --------------------------------------------------------
>>> =
>
> --
> ---
> Larry McVoy    =                     lm at= mcvoy.com             http:/= /www.mcvoy.com/lm

--=_544f96af4a5ab26c41a752d6690e0582--