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 d4c8b876 for ; Tue, 15 Jan 2019 22:39:13 +0000 (UTC) Received: by minnie.tuhs.org (Postfix, from userid 112) id 203EE94FBB; Wed, 16 Jan 2019 08:39:12 +1000 (AEST) Received: from minnie.tuhs.org (localhost [127.0.0.1]) by minnie.tuhs.org (Postfix) with ESMTP id 0679F94FB8; Wed, 16 Jan 2019 08:38:32 +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="sbxjAehf"; dkim-atps=neutral Received: by minnie.tuhs.org (Postfix, from userid 112) id 4536494FB8; Wed, 16 Jan 2019 08:38:31 +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 9E57494FB7 for ; Wed, 16 Jan 2019 08:38:29 +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 BA3925C5142; Tue, 15 Jan 2019 22:32:23 +0000 (UTC) Received: from pdx1-sub0-mail-a24.g.dreamhost.com (unknown [100.96.11.179]) (Authenticated sender: dreamhost) by relay.mailchannels.net (Postfix) with ESMTPA id 4513C5C4D08; Tue, 15 Jan 2019 22:32:23 +0000 (UTC) X-Sender-Id: dreamhost|x-authsender|scj@yaccman.com Received: from pdx1-sub0-mail-a24.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); Tue, 15 Jan 2019 22:32:23 +0000 X-MC-Relay: Neutral X-MailChannels-SenderId: dreamhost|x-authsender|scj@yaccman.com X-MailChannels-Auth-Id: dreamhost X-Reaction-Chief: 7d7c537a14845261_1547591543564_2075585313 X-MC-Loop-Signature: 1547591543564:1656944191 X-MC-Ingress-Time: 1547591543564 Received: from pdx1-sub0-mail-a24.g.dreamhost.com (localhost [127.0.0.1]) by pdx1-sub0-mail-a24.g.dreamhost.com (Postfix) with ESMTP id C09497F7D6; Tue, 15 Jan 2019 14:32:21 -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=P0grvyWviV7fWITEed26DPgeeqo=; b=sbxjAehf79p+/ UFo7A05JaODPNQGm1ZfqM3PHl84y8bU7eawAi8lgdmFxCvE1V87vcd9sbCXQv1qr mrMUikT2be7d2xcQ+O2P0LGlM9pf8ckIQtHcIYaggW7xhtzGiatfdSCfqLw4V4iR cPmiBEtfin1tSi7jB8mXsZNRcjdtnw= 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-a24.g.dreamhost.com (Postfix) with ESMTPSA id A7D517F7CB; Tue, 15 Jan 2019 14:32:17 -0800 (PST) Message-Id: X-DH-BACKEND: pdx1-sub0-mail-a24 From: "Steve Johnson" To: "Bakul Shah" , "Steve Johnson" X-Mailer: Atmail 7.8.0.2 X-Originating-IP: 10.35.42.221 in-reply-to: <20190113044018.B235E156E410@mail.bitblocks.com> Date: Tue, 15 Jan 2019 14:32:16 -0800 Content-Type: multipart/alternative; boundary="=_8aadd53284f257dfa0c7571ec120c0a6" MIME-Version: 1.0 X-VR-OUT-STATUS: OK X-VR-OUT-SCORE: -100 X-VR-OUT-SPAMCAUSE: gggruggvucftvghtrhhoucdtuddrgedtledrgeefgdduheelucetufdoteggodetrfdotffvucfrrhhofhhilhgvmecuggftfghnshhusghstghrihgsvgdpffftgfetoffjqffuvfenuceurghilhhouhhtmecufedttdenucesvcftvggtihhpihgvnhhtshculddquddttddmnecujfgurhepkffhvffoihgjuffftgggsegrtderreertdejnecuhfhrohhmpedfufhtvghvvgculfhohhhnshhonhdfuceoshgtjheshigrtggtmhgrnhdrtghomheqnecukfhppeeiiedrfeefrddvtddtrdegpddutddrfeehrdegvddrvddvudenucfrrghrrghmpehmohguvgepshhmthhppdhhvghloheplhhotggrlhhhohhsthdpihhnvghtpeeiiedrfeefrddvtddtrdegpdhrvghtuhhrnhdqphgrthhhpedfufhtvghvvgculfhohhhnshhonhdfuceoshgtjheshigrtggtmhgrnhdrtghomheqpdhmrghilhhfrhhomhepshgtjheshigrtggtmhgrnhdrtghomhdpnhhrtghpthhtohepthhuhhhssehtuhhhshdrohhrghenucevlhhushhtvghrufhiiigvpedt 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" --=_8aadd53284f257dfa0c7571ec120c0a6 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable =0AI remember reading Knuth's paper, and certainly heard DeRemer's name,= =0Abut it didn't affect much of what I did.=C2=A0 There was a paper out= of=0AStanford about that time that influenced me greatly -- it was abou= t=0Apattern matching languages, and proposed separating two ideas: 1.=C2= =A0=0A"Here are the patterns that match this tree".=C2=A0 And 2.=C2=A0 "= If more than=0Aone pattern matches, here's how to decide which one to us= e."=C2=A0=C2=A0 Given=0Athe constraints of size on the PDP 11, anything= but LR(1) was=0Ainfeasable.=C2=A0 But using ambiguous grammars and broa= dening the=0Ashift/reduce test to trest operator precedence fit right in= to that=0Apattern.=C2=A0=C2=A0 Another thing that I think was unique to= Yacc at the time=0Awas introducing symbols that matched the empty strin= g whose reduction=0Acaused program actions.=C2=A0 Many similar parser sy= stems at the time=0Acould not deal with these "empty" symbols.=0A=0AStev= e=0A=0A----- Original Message -----=0AFrom: "Bakul Shah" =0ATo:"Steve Johnson" =0ACc:,= , ,=0A=0ASent:S= at, 12 Jan 2019 20:40:11 -0800=0ASubject:Re: [TUHS] Knuth and Unix=0A=0A= On Sat, 12 Jan 2019 19:41:26 -0800 "Steve Johnson" =0A= wrote:=0A > One connection Knuth had to Unix was inventing LALR parsing,= the=0Abasic=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 handle=0Alarge=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 wit= h 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 real job. At that job= I used DeRemer and Pennello's 1979=0A paper to reimplement the parser g= enerator.=0A=0A --=_8aadd53284f257dfa0c7571ec120c0a6 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
I remember reading Knuth's paper, and certainly heard DeRem= er's name, but it didn't affect much of what I did.=C2=A0 There was a pa= per out of Stanford about that time that influenced me greatly -- it was= about pattern matching languages, and proposed separating two ideas: 1.= =C2=A0 "Here are the patterns that match this tree".=C2=A0 And 2.=C2=A0= "If more than one pattern matches, here's how to decide which one to us= e."=C2=A0=C2=A0 Given the constraints of size on the PDP 11, anything bu= t LR(1) was infeasable.=C2=A0 But using ambiguous grammars and broadenin= g the shift/reduce test to trest operator precedence fit right into that= pattern.=C2=A0=C2=A0 Another thing that I think was unique to Yacc at t= he time was introducing symbols that matched the empty string whose redu= ction caused program actions.=C2=A0 Many similar parser systems at the t= ime could not deal with these "empty" symbols.

= Steve



----- Origi= nal Message -----
From:
"Bakul Shah" <bakul@bitblocks= .com>

To:
"Steve Johnson" <scj@yaccman.com>= ;
Cc:
<arnold@skeeve.com>, <ecashin@noserose.n= et>, <dave@horsfall.org>, <tuhs@tuhs.org>
Sent:
Sat, 12 Jan 2019 20:40:= 11 -0800
Subject:
Re: [TUHS] Knuth and Unix

<= br>=0AOn Sat, 12 Jan 2019 19:41:26 -0800 "Steve Johnson" <scj@yaccman= .com> wrote:
=0A> One connection Knuth had to Unix was inventin= g LALR parsing, the basic
=0A> algorithm used in Yacc. I added so= me things (notably, the precedence
=0A> mechanism) and had 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> m= y be Al Aho) was all Knuth.

=0AKnuth invented LR parsing but IIRC= it was DeRemer who came up
=0Awith LALR parsing. In 78-79 I was impl= ementing a LALR(1)
=0Aparser generator in Pascal on strength of which= I got my first
=0Areal job. At that job I used DeRemer and Pennello= 's 1979
=0Apaper to reimplement the parser generator.

--=_8aadd53284f257dfa0c7571ec120c0a6--