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 6a11a484 for ; Fri, 18 Jan 2019 21:57:53 +0000 (UTC) Received: by minnie.tuhs.org (Postfix, from userid 112) id 0BA5594FDA; Sat, 19 Jan 2019 07:57:52 +1000 (AEST) Received: from minnie.tuhs.org (localhost [127.0.0.1]) by minnie.tuhs.org (Postfix) with ESMTP id 39B2894FC8; Sat, 19 Jan 2019 07:57:13 +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="CawpkRVZ"; dkim-atps=neutral Received: by minnie.tuhs.org (Postfix, from userid 112) id 66F5094FC8; Sat, 19 Jan 2019 07:57:11 +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 7D35794FC6 for ; Sat, 19 Jan 2019 07:57: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 C4D465C39E2; Fri, 18 Jan 2019 21:57:07 +0000 (UTC) Received: from pdx1-sub0-mail-a56.g.dreamhost.com (unknown [100.96.11.179]) (Authenticated sender: dreamhost) by relay.mailchannels.net (Postfix) with ESMTPA id 44DF75C2CA1; Fri, 18 Jan 2019 21:57:07 +0000 (UTC) X-Sender-Id: dreamhost|x-authsender|scj@yaccman.com Received: from pdx1-sub0-mail-a56.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 21:57:07 +0000 X-MC-Relay: Neutral X-MailChannels-SenderId: dreamhost|x-authsender|scj@yaccman.com X-MailChannels-Auth-Id: dreamhost X-Callous-Abiding: 7c7ea5b03d426fe1_1547848627607_396674064 X-MC-Loop-Signature: 1547848627607:2744921881 X-MC-Ingress-Time: 1547848627607 Received: from pdx1-sub0-mail-a56.g.dreamhost.com (localhost [127.0.0.1]) by pdx1-sub0-mail-a56.g.dreamhost.com (Postfix) with ESMTP id AFBC78017B; Fri, 18 Jan 2019 13:57:06 -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=tT/FWrJaQ93FqVPY9e/FUJ9qbv0=; b=CawpkRVZpGwnx InlTQxNirsH4MFvP/sJNXU93bZALGI3Yuh11802g7hkrwKoxereLgDpx2JVrF+5F w/fVs4dc6cczB5KgWkpyY5Zt//kwAdyvTOSkdoNDcUStoWZtW3HoaZEgoOMJl23A tOdVKcyvykgB3FTb6fg7/cp5VERQKI= 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-a56.g.dreamhost.com (Postfix) with ESMTPSA id 312CF800D1; Fri, 18 Jan 2019 13:57:04 -0800 (PST) Message-Id: <30735aec554140bc4c98c14fe18be5b7ac1fff66@webmail.yaccman.com> X-DH-BACKEND: pdx1-sub0-mail-a56 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: <20190116205043.21C22156E410@mail.bitblocks.com> Date: Fri, 18 Jan 2019 13:57:04 -0800 Content-Type: multipart/alternative; boundary="=_40c2c9ce775184a880f935b6e4641c77" MIME-Version: 1.0 X-VR-OUT-STATUS: OK X-VR-OUT-SCORE: -100 X-VR-OUT-SPAMCAUSE: gggruggvucftvghtrhhoucdtuddrgedtledrhedtgdduheekucetufdoteggodetrfdotffvucfrrhhofhhilhgvmecuggftfghnshhusghstghrihgsvgdpffftgfetoffjqffuvfenuceurghilhhouhhtmecufedttdenucesvcftvggtihhpihgvnhhtshculddquddttddmnecujfgurhepkffhvffoihgjuffftgggsegrtderreertdejnecuhfhrohhmpedfufhtvghvvgculfhohhhnshhonhdfuceoshgtjheshigrtggtmhgrnhdrtghomheqnecukfhppeeiiedrfeefrddvtddtrdegpddutddrfeehrdegvddrvddvudenucfrrghrrghmpehmohguvgepshhmthhppdhhvghloheplhhotggrlhhhohhsthdpihhnvghtpeeiiedrfeefrddvtddtrdegpdhrvghtuhhrnhdqphgrthhhpedfufhtvghvvgculfhohhhnshhonhdfuceoshgtjheshigrtggtmhgrnhdrtghomheqpdhmrghilhhfrhhomhepshgtjheshigrtggtmhgrnhdrtghomhdpnhhrtghpthhtohepthhuhhhssehtuhhhshdrohhrghenucevlhhushhtvghrufhiiigvpedt 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" --=_40c2c9ce775184a880f935b6e4641c77 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable =0AThe paper=C2=A0 was called "The Competence/Performance Dichotomy" by= =0APratt.=C2=A0 He borrowed an idea from Chompsky and distinguished betw= een=0Abeing able to understand something and being able to produce it.= =C2=A0 The=0Aidea I took from it was to recognize grammar rules even if= the parse=0Awas ambiguous and then use other mechanisms (e.g., Shift/Re= duce,=0Aprecedence) to decide what to do.=0A=0AAbout empty productions:= one of the most useful versions of this was=0Ain handling scopes in pro= gramming languages, especially in C where xyz=0Acould be a variable in o= ne scope and a typedef in an inner one, or=0Avice versa.=C2=A0 The empty= production could get called at the right=0Amoment to make the appropria= te symbol table fixes, where otherwise we=0Awould have had a syntax erro= r. =0A=0ASteve=0A=0A----- Original Message -----=0AFrom: "Bakul Shah" =0ATo:"Steve Johnson" =0ACc:, , ,=0A=0ASent:Wed, 16 Jan 2019 12:50:35 -0800=0ASubject:Re: [TUHS] Knuth an= d Unix=0A=0A On Tue, 15 Jan 2019 14:32:16 -0800 "Steve Johnson" =0Awrote:=0A > I remember reading Knuth's paper, and certainly= heard=0A > DeRemer's name, but it didn't affect much of what I did.=0A= > There was a paper out of Stanford about that time that=0A > influence= d me greatly -- it was about pattern matching=0A > languages, and propos= ed separating two ideas: 1. "Here are=0A > the patterns that match this= tree". And 2. "If more than one=0A > pattern matches, here's how to dec= ide which one to use."=0A > Given the constraints of size on the PDP 11,= anything but=0A > LR(1) was infeasable. But using ambiguous grammars an= d=0A > broadening the shift/reduce test to trest operator precedence=0A= > fit right into that pattern. Another thing that I think was=0A > uniq= ue to Yacc at the time was introducing symbols that=0A > matched the emp= ty string whose reduction caused program=0A > actions. Many similar pars= er systems at the time could not=0A > deal with these "empty" symbols.= =0A=0A Good to know all this. The Stanford paper you refer, would=0A tha= t be "fast pattern matching" by Knuth, Morris & Pratt?=0A=0A I remember= struggling with empty strings and I also missed=0A other yacc tricks. I= n my formulation I had two kinds of=0A rules: set rules and sequence rul= es. Set rules avoided=0A unnecessary reductions in rules such as foo: ba= r|...=0A=0A For example:=0A=0A // sets=0A expr =3D relexpr | expr1=0A ex= pr1 =3D addexpr | expr2=0A expr2 =3D mulexpr | expr3=0A ...=0A=0A // seq= uences=0A relexpr: expr1 RELOP expr1=0A addexpr: expr1 ('+'|'-') expr2= =0A mulexpr: expr2 ('*'|'/') expr3=0A ...=0A=0A Basically I completely a= voided empty symbols -- even an empty=0A file has an EOF! [I didn't try= it on anything more complicated=0A than (extended) Pascal so no idea ho= w it would have fared on=0A complexificated lanuages]=0A=0A --=_40c2c9ce775184a880f935b6e4641c77 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
The paper=C2=A0 was called "The Competence/Performance Dich= otomy" by Pratt.=C2=A0 He borrowed an idea from Chompsky and distinguish= ed between being able to understand something and being able to produce= it.=C2=A0 The idea I took from it was to recognize grammar rules even i= f the parse was ambiguous and then use other mechanisms (e.g., Shift/Red= uce, precedence) to decide what to do.

About em= pty productions: one of the most useful versions of this was in handling= scopes in programming languages, especially in C where xyz could be a v= ariable in one scope and a typedef in an inner one, or vice versa.=C2=A0= The empty production could get called at the right moment to make the a= ppropriate symbol table fixes, where otherwise we would have had a synta= x error.

Steve



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

To:"Steve Johnson" <scj@yaccman.com>
Cc:
<arnold= @skeeve.com>, <ecashin@noserose.net>, <dave@horsfall.org>= , <tuhs@tuhs.org>
Sent:
Wed, 16 Jan 2019 12:50:35 -0800
Subject:Re: [TUHS] Knuth and Unix


=0AOn Tue, 15 Jan 2019 14:32:16= -0800 "Steve Johnson" <scj@yaccman.com> wrote:
=0A> I remem= ber reading Knuth's paper, and certainly heard
=0A> DeRemer's name= , but it didn't affect much of what I did.
=0A> There was a paper= out of Stanford about that time that
=0A> influenced me greatly -= - it was about pattern matching
=0A> languages, and proposed separ= ating two ideas: 1. "Here are
=0A> the patterns that match this t= ree". And 2. "If more than one
=0A> pattern matches, here's how= to decide which one to use."
=0A> Given the constraints of size o= n the PDP 11, anything but
=0A> LR(1) was infeasable. But using a= mbiguous grammars and
=0A> broadening the shift/reduce test to tre= st operator precedence
=0A> fit right into that pattern. Another= thing that I think was
=0A> unique to Yacc at the time was introd= ucing symbols that
=0A> matched the empty string whose reduction c= aused program
=0A> actions. Many similar parser systems at the ti= me could not
=0A> deal with these "empty" symbols.

=0AGood= to know all this. The Stanford paper you refer, would
=0Athat be "fa= st pattern matching" by Knuth, Morris & Pratt?

=0AI remember= struggling with empty strings and I also missed
=0Aother yacc tricks= . In my formulation I had two kinds of
=0Arules: set rules and seque= nce rules. Set rules avoided
=0Aunnecessary reductions in rules such= as foo: bar|...

=0AFor example:

=0A// sets
=0Aexpr =3D= relexpr | expr1
=0Aexpr1 =3D addexpr | expr2
=0Aexpr2 =3D mulexp= r | expr3
=0A...

=0A// sequences
=0Arelexpr: expr1 RELOP e= xpr1
=0Aaddexpr: expr1 ('+'|'-') expr2
=0Amulexpr: expr2 ('*'|'/')= expr3
=0A...

=0ABasically I completely avoided empty symbols= -- even an empty
=0Afile has an EOF! [I didn't try it on anything mo= re complicated
=0Athan (extended) Pascal so no idea how it would have= fared on
=0Acomplexificated lanuages]

--=_40c2c9ce775184a880f935b6e4641c77--