From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-0.8 required=5.0 tests=DKIM_INVALID,DKIM_SIGNED, HEADER_FROM_DIFFERENT_DOMAINS,HTML_MESSAGE,MAILING_LIST_MULTI, RCVD_IN_DNSWL_NONE autolearn=ham autolearn_force=no version=3.4.2 Received: from minnie.tuhs.org (minnie.tuhs.org [45.79.103.53]) by inbox.vuxu.org (OpenSMTPD) with ESMTP id 281e8ae9 for ; Fri, 18 Jan 2019 00:56:32 +0000 (UTC) Received: by minnie.tuhs.org (Postfix, from userid 112) id 58AA494FD6; Fri, 18 Jan 2019 10:56:31 +1000 (AEST) Received: from minnie.tuhs.org (localhost [127.0.0.1]) by minnie.tuhs.org (Postfix) with ESMTP id 8396994FC9; Fri, 18 Jan 2019 10:55:49 +1000 (AEST) Authentication-Results: minnie.tuhs.org; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=yaccman.com header.i=@yaccman.com header.b="lwurXmFW"; dkim-atps=neutral Received: by minnie.tuhs.org (Postfix, from userid 112) id D698794FC8; Fri, 18 Jan 2019 10:55:46 +1000 (AEST) Received: from bird.maple.relay.mailchannels.net (bird.maple.relay.mailchannels.net [23.83.214.17]) by minnie.tuhs.org (Postfix) with ESMTPS id B8C7994FC6 for ; Fri, 18 Jan 2019 10:55:45 +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 D8B445C4C3C; Fri, 18 Jan 2019 00:55:44 +0000 (UTC) Received: from pdx1-sub0-mail-a68.g.dreamhost.com (unknown [100.96.35.77]) (Authenticated sender: dreamhost) by relay.mailchannels.net (Postfix) with ESMTPA id 795AA5C4C5B; Fri, 18 Jan 2019 00:55:44 +0000 (UTC) X-Sender-Id: dreamhost|x-authsender|scj@yaccman.com Received: from pdx1-sub0-mail-a68.g.dreamhost.com (pop.dreamhost.com [64.90.62.162]) (using TLSv1.2 with cipher DHE-RSA-AES256-GCM-SHA384) by 0.0.0.0:2500 (trex/5.16.2); Fri, 18 Jan 2019 00:55:44 +0000 X-MC-Relay: Neutral X-MailChannels-SenderId: dreamhost|x-authsender|scj@yaccman.com X-MailChannels-Auth-Id: dreamhost X-Cold-Blushing: 189740e877397b7c_1547772944706_1045744976 X-MC-Loop-Signature: 1547772944705:3139026420 X-MC-Ingress-Time: 1547772944705 Received: from pdx1-sub0-mail-a68.g.dreamhost.com (localhost [127.0.0.1]) by pdx1-sub0-mail-a68.g.dreamhost.com (Postfix) with ESMTP id 2527F7FC52; Thu, 17 Jan 2019 16:55:44 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=yaccman.com; h=message-id :from:to:cc:in-reply-to:subject:date:content-type:mime-version; s=yaccman.com; bh=nQWyauZi0PR+SDT4BRzPhoiRVPI=; b=lwurXmFW4zeEn ytSdqcENhm0hONqhGgwwqu5fWPbQAm0//u8HH2cXQQxm+JBgU8TFOfbSVFvsG0oc VoT4noWYEPAai2bbSScGkLep8S4ee+ry7VpHeqLIEL75uFhbSb+77yE5DCLK2xTh h5hkuAsiWbY+3rv2uPhmN+vf/YmAlc= Received: from localhost (ip-66-33-200-4.dreamhost.com [66.33.200.4]) (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) (Authenticated sender: scj@yaccman.com) by pdx1-sub0-mail-a68.g.dreamhost.com (Postfix) with ESMTPSA id 1F5207FC3D; Thu, 17 Jan 2019 16:55:43 -0800 (PST) Message-Id: <3afa277677b7d3d9f90382bec46541fbf17aed83@webmail.yaccman.com> X-DH-BACKEND: pdx1-sub0-mail-a68 From: "Steve Johnson" To: "Rob Pike" , arnold@skeeve.com X-Mailer: Atmail 7.8.0.2 X-Originating-IP: 10.35.42.221 in-reply-to: Date: Thu, 17 Jan 2019 16:55:43 -0800 Content-Type: multipart/alternative; boundary="=_b1355723e5b53a1e9fd6ded77fae3360" MIME-Version: 1.0 X-VR-OUT-STATUS: OK X-VR-OUT-SCORE: -100 X-VR-OUT-SPAMCAUSE: gggruggvucftvghtrhhoucdtuddrgedtledrgeelgddviecutefuodetggdotefrodftvfcurfhrohhfihhlvgemucggtfgfnhhsuhgsshgtrhhisggvpdfftffgtefojffquffvnecuuegrihhlohhuthemuceftddtnecusecvtfgvtghiphhivghnthhsucdlqddutddtmdenucfjughrpefkhffvofhijgfuffgtggesrgdtreerredtjeenucfhrhhomhepfdfuthgvvhgvucflohhhnhhsohhnfdcuoehstghjseihrggttghmrghnrdgtohhmqeenucfkphepieeirdeffedrvddttddrgedpuddtrdefhedrgedvrddvvddunecurfgrrhgrmhepmhhouggvpehsmhhtphdphhgvlhhopehlohgtrghlhhhoshhtpdhinhgvthepieeirdeffedrvddttddrgedprhgvthhurhhnqdhprghthhepfdfuthgvvhgvucflohhhnhhsohhnfdcuoehstghjseihrggttghmrghnrdgtohhmqedpmhgrihhlfhhrohhmpehstghjseihrggttghmrghnrdgtohhmpdhnrhgtphhtthhopehtuhhhshesthhuhhhsrdhorhhgnecuvehluhhsthgvrhfuihiivgeptd Subject: Re: [TUHS] Knuth and Unix 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: tuhs@tuhs.org Errors-To: tuhs-bounces@minnie.tuhs.org Sender: "TUHS" --=_b1355723e5b53a1e9fd6ded77fae3360 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable =0AAs I remember, the original EQN grammar had >300 S/R conflicts and 50= =0Aor so RR conflicts.=C2=A0 But it mostly did what you wanted.=C2=A0 I= think Al=0AAho got faint when he looked it it, though...=C2=A0 (It got= better when=0Aprecedence was added...)=0A=0ASteve=0A=0A----- Original M= essage -----=0AFrom: "Rob Pike" =0ATo:=0ACc:, =0ASent:Thu, 17 Jan 2019 07:= 10:58 +1100=0ASubject:Re: [TUHS] Knuth and Unix=0A=0A I was speaking in= jest... But the (official) awk grammar has been an=0A eye-opener for ye= ars.=0A=0A -rob=0A=0A On Thu, Jan 17, 2019 at 5:22 AM wrote:=0A >=0A > You can't lay the blame for that on Steve.=0A >=0A >= The GNU Awk grammar has only 36 shift-reduce conflicts and no=0A > redu= ce-reduce conflicts.=0A >=0A > The mawk 1.3.4 grammar has an amazing cou= nt of only *four*=0Ashift-reduce=0A > conflicts. (But then, Mike Brennan= is an amazing programmer.)=0A >=0A > I have no idea what happens if you= run the POSIX awk grammar=0Athrough=0A > yacc / bison, but it'd be an i= nteresting experiment.=0A >=0A > Arnold=0A >=0A > Rob Pike wrote:=0A >=0A > > So you're the reason (Plan 9) awk has 83 reduc= e-reduce conflicts=0A(and=0A > > 42 shift-reduce).=0A > >=0A > > -rob=0A= > >=0A > > On Wed, Jan 16, 2019 at 9:39 AM Steve Johnson =0Awrote:=0A > > >=0A > > > I remember reading Knuth's paper, and cer= tainly heard DeRemer's=0Aname, but it didn't affect much of what I did.= There was a paper out=0Aof Stanford about that time that influenced me= greatly -- it was about=0Apattern matching languages, and proposed sepa= rating two ideas: 1.=0A"Here are the patterns that match this tree". And= 2. "If more than one=0Apattern matches, here's how to decide which one= to use." Given the=0Aconstraints of size on the PDP 11, anything but LR= (1) was infeasable.=0ABut using ambiguous grammars and broadening the sh= ift/reduce test to=0Atrest operator precedence fit right into that patte= rn. Another thing=0Athat I think was unique to Yacc at the time was intr= oducing symbols=0Athat matched the empty string whose reduction caused p= rogram actions.=0AMany similar parser systems at the time could not deal= with these=0A"empty" symbols.=0A > > >=0A > > > Steve=0A > > >=0A > > >= =0A > > >=0A > > > ----- Original Message -----=0A > > > From: "Bakul Sh= ah" =0A > > > To:"Steve Johnson" = =0A > > > Cc:, ,=0A, =0A > > > Sent:Sat, 12 Jan 2019 20:40:11 -0800= =0A > > > Subject:Re: [TUHS] Knuth and Unix=0A > > >=0A > > >=0A > > > O= n Sat, 12 Jan 2019 19:41:26 -0800 "Steve Johnson"=0A wr= ote:=0A > > > > One connection Knuth had to Unix was inventing LALR pars= ing,=0Athe basic=0A > > > > algorithm used in Yacc. I added some things= (notably, the=0Aprecedence=0A > > > > mechanism) and had to do a lot of= engineering to be able to=0Ahandle large=0A > > > > grammars (e.g. F77)= on a PDP-11. But the underlying algorithm=0A(taught to=0A > > > > my be= Al Aho) was all Knuth.=0A > > >=0A > > > Knuth invented LR parsing but= IIRC it was DeRemer who came up=0A > > > with LALR parsing. In 78-79 I= was implementing a LALR(1)=0A > > > parser generator in Pascal on stren= gth of which I got my first=0A > > > real job. At that job I used DeReme= r and Pennello's 1979=0A > > > paper to reimplement the parser generator= .=0A > > >=0A=0A --=_b1355723e5b53a1e9fd6ded77fae3360 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
As I remember, the original EQN grammar had >300 S/R con= flicts and 50 or so RR conflicts.=C2=A0 But it mostly did what you wante= d.=C2=A0 I think Al Aho got faint when he looked it it, though...=C2=A0= (It got better when precedence was added...)

Steve



----- Or= iginal Message -----
From:
"Rob Pike" <robpike@gmail.= com>

To:
<arnold@skeeve.com>
C= c:
<scj@yaccman.com>, <tuhs@tuhs.org>
Sent:
Thu, 17 Jan 2019 07:10:58 += 1100
Subject:
Re: [TUHS] Knuth and Unix


= =0AI was speaking in jest... But the (official) awk grammar has been an<= br>=0Aeye-opener for years.

=0A-rob

=0AOn Thu, Jan 17, 201= 9 at 5:22 AM <arnold@skeeve.com> wrote:
=0A>
=0A> You= can't lay the blame for that on Steve.
=0A>
=0A> The GNU Aw= k grammar has only 36 shift-reduce conflicts and no
=0A> reduce-re= duce conflicts.
=0A>
=0A> The mawk 1.3.4 grammar has an amaz= ing count of only *four* shift-reduce
=0A> conflicts. (But then,= Mike Brennan is an amazing programmer.)
=0A>
=0A> I have no= idea what happens if you run the POSIX awk grammar through
=0A> y= acc / bison, but it'd be an interesting experiment.
=0A>
=0A>= ; Arnold
=0A>
=0A> Rob Pike <robpike@gmail.com> wrote:=
=0A>
=0A> > So you're the reason (Plan 9) awk has 83 red= uce-reduce conflicts (and
=0A> > 42 shift-reduce).
=0A> &= gt;
=0A> > -rob
=0A> >
=0A> > On Wed, Jan 16,= 2019 at 9:39 AM Steve Johnson <scj@yaccman.com> wrote:
=0A>= > >
=0A> > > I remember reading Knuth's paper, and ce= rtainly heard DeRemer's name, but it didn't affect much of what I did. = There was a paper out of Stanford about that time that influenced me gr= eatly -- it was about pattern matching languages, and proposed separatin= g two ideas: 1. "Here are the patterns that match this tree". And 2. = "If more than one pattern matches, here's how to decide which one to us= e." Given the constraints of size on the PDP 11, anything but LR(1) wa= s infeasable. But using ambiguous grammars and broadening the shift/red= uce test to trest operator precedence fit right into that pattern. Ano= ther thing that I think was unique to Yacc at the time was introducing s= ymbols that matched the empty string whose reduction caused program acti= ons. Many similar parser systems at the time could not deal with these= "empty" symbols.
=0A> > >
=0A> > > Steve
=0A= > > >
=0A> > >
=0A> > >
=0A> >= > ----- Original Message -----
=0A> > > From: "Bakul Sha= h" <bakul@bitblocks.com>
=0A> > > To:"Steve Johnson" &= lt;scj@yaccman.com>
=0A> > > Cc:<arnold@skeeve.com>= , <ecashin@noserose.net>, <dave@horsfall.org>, <tuhs@tuhs= .org>
=0A> > > Sent:Sat, 12 Jan 2019 20:40:11 -0800
= =0A> > > Subject:Re: [TUHS] Knuth and Unix
=0A> > >=
=0A> > >
=0A> > > On Sat, 12 Jan 2019 19:41:26= -0800 "Steve Johnson" <scj@yaccman.com> wrote:
=0A> > &g= t; > One connection Knuth had to Unix was inventing LALR parsing, the= basic
=0A> > > > algorithm used in Yacc. I added some th= ings (notably, the precedence
=0A> > > > mechanism) and h= ad to do a lot of engineering to be able to handle large
=0A> >= > > grammars (e.g. F77) on a PDP-11. But the underlying algorithm= (taught to
=0A> > > > my be Al Aho) was all Knuth.
= =0A> > >
=0A> > > Knuth invented LR parsing but IIR= C it was DeRemer who came up
=0A> > > with LALR parsing. In= 78-79 I was implementing a LALR(1)
=0A> > > parser generato= r in Pascal on strength of which I got my first
=0A> > > rea= l job. At that job I used DeRemer and Pennello's 1979
=0A> > &g= t; paper to reimplement the parser generator.
=0A> > >
--=_b1355723e5b53a1e9fd6ded77fae3360--