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_ADSP_CUSTOM_MED, DKIM_INVALID,DKIM_SIGNED,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,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 cbcbf417 for ; Wed, 16 Jan 2019 20:11:48 +0000 (UTC) Received: by minnie.tuhs.org (Postfix, from userid 112) id A1ECF94FC6; Thu, 17 Jan 2019 06:11:47 +1000 (AEST) Received: from minnie.tuhs.org (localhost [127.0.0.1]) by minnie.tuhs.org (Postfix) with ESMTP id 7532294FB8; Thu, 17 Jan 2019 06:11:14 +1000 (AEST) Authentication-Results: minnie.tuhs.org; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=gmail.com header.i=@gmail.com header.b="uXSIh7iy"; dkim-atps=neutral Received: by minnie.tuhs.org (Postfix, from userid 112) id 9C2E494FB9; Thu, 17 Jan 2019 06:11:11 +1000 (AEST) Received: from mail-vk1-f169.google.com (mail-vk1-f169.google.com [209.85.221.169]) by minnie.tuhs.org (Postfix) with ESMTPS id D637694FB8 for ; Thu, 17 Jan 2019 06:11:10 +1000 (AEST) Received: by mail-vk1-f169.google.com with SMTP id y14so1723784vky.9 for ; Wed, 16 Jan 2019 12:11:10 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc:content-transfer-encoding; bh=TfSiyr9Yi9cy6ArMJwCgku3Dj3ckG322o9KeLOnzLSQ=; b=uXSIh7iyzz6hBS9KVTiG9XhTV8TCF8R6gSqIh2mVvVyvXKIL0GsJGy8UBD0vddIHP3 QFsJpwqrpknVcAmnCWJoEtGVdlDKDoSfKnDjz3+uVZjogXy4p962gFyUlTUgaJw/qnOY wr7o1RML0atqYCPChtCaXL6+WzMIn/KxE4ZTz+ZdeRpGtgFscHRx+hOz4cbMy2v+YVlW cKBTBp0YuvUnsX1HMPK2eciR6QB10a/vjOhL2HZTkBKELeJ529tYgHhf7JuzEgCNe0lh jel+EyhoUumHUwZXtDEaGFt/LHosC/H747DsVooDs25IwT62usrUL9CbwB/LHvSjaksp BYxA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc:content-transfer-encoding; bh=TfSiyr9Yi9cy6ArMJwCgku3Dj3ckG322o9KeLOnzLSQ=; b=IKuT+F0equ74x8qstVsaeUS8nTLDcNdKm9+FsFnL0lv8fuxRFGDubEUNgrpBSaP7Rj qx3O95nMdU7OH74K5/IDpIL4IHNdwsJo9IoJBlRnVFrbey+CgvyKjn5LjRWQp+HXW3EW Mkg8NR8Nsz3UrT52RX0+V9xXQYpirKg32vIWo3/m8FDiw22ON3lcrxe8lucFT8TtPdfQ T18C+RgvdOndqeme0BwBL4/Z45pSJmKAIOznrkwGDNTrI5STzJ2dCmPbjibvmAkV6YYG g6cAvNiM7hIoS4kPsrGcxnRSjWOVXBGyZLQcMd58uUf9mccZdr6JDaZgUWS/Zd77+4Ly 9Ffw== X-Gm-Message-State: AJcUukeR7EJ/DObmB4xSJ8o8OjT+vL7wobPBWpCAfQaUXFxy9diGITVO MXB2+pXstTXEVB42P7dS4gq/r8DMoFDT4YJgjjiN8g== X-Google-Smtp-Source: ALg8bN7qrWZvkxGoKMptqVf/gAVsZnmys94701h+/GIHGL6r9mNjsZv6jW5wGaBNQqx/FuuEkTUk+hhSEvbhRvus02g= X-Received: by 2002:a1f:298e:: with SMTP id p136mr4408692vkp.40.1547669469865; Wed, 16 Jan 2019 12:11:09 -0800 (PST) MIME-Version: 1.0 References: <20190113044018.B235E156E410@mail.bitblocks.com> <201901161822.x0GIMmQW026812@freefriends.org> In-Reply-To: <201901161822.x0GIMmQW026812@freefriends.org> From: Rob Pike Date: Thu, 17 Jan 2019 07:10:58 +1100 Message-ID: To: arnold@skeeve.com Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable 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" I was speaking in jest... But the (official) awk grammar has been an eye-opener for years. -rob On Thu, Jan 17, 2019 at 5:22 AM wrote: > > You can't lay the blame for that on Steve. > > The GNU Awk grammar has only 36 shift-reduce conflicts and no > reduce-reduce conflicts. > > The mawk 1.3.4 grammar has an amazing count of only *four* shift-reduce > conflicts. (But then, Mike Brennan is an amazing programmer.) > > I have no idea what happens if you run the POSIX awk grammar through > yacc / bison, but it'd be an interesting experiment. > > Arnold > > Rob Pike wrote: > > > So you're the reason (Plan 9) awk has 83 reduce-reduce conflicts (and > > 42 shift-reduce). > > > > -rob > > > > On Wed, Jan 16, 2019 at 9:39 AM Steve Johnson wrote: > > > > > > I remember reading Knuth's paper, and certainly heard DeRemer's name,= but it didn't affect much of what I did. There was a paper out of Stanfor= d about that time that influenced me greatly -- it was about pattern matchi= ng languages, and proposed separating 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 use." Given the constraints of size on the PDP= 11, anything but LR(1) was infeasable. But using ambiguous grammars and b= roadening the shift/reduce test to trest operator precedence fit right into= that pattern. Another thing that I think was unique to Yacc at the time = was introducing symbols that matched the empty string whose reduction cause= d program actions. Many similar parser systems at the time could not deal = with these "empty" symbols. > > > > > > Steve > > > > > > > > > > > > ----- Original Message ----- > > > From: "Bakul Shah" > > > To:"Steve Johnson" > > > Cc:, , , = > > > Sent:Sat, 12 Jan 2019 20:40:11 -0800 > > > Subject:Re: [TUHS] Knuth and Unix > > > > > > > > > On Sat, 12 Jan 2019 19:41:26 -0800 "Steve Johnson" = wrote: > > > > One connection Knuth had to Unix was inventing LALR parsing, the ba= sic > > > > algorithm used in Yacc. I added some things (notably, the precedenc= e > > > > mechanism) and had to do a lot of engineering to be able to handle = large > > > > grammars (e.g. F77) on a PDP-11. But the underlying algorithm (taug= ht to > > > > my be Al Aho) was all Knuth. > > > > > > Knuth invented LR parsing but IIRC it was DeRemer who came up > > > with LALR parsing. In 78-79 I was implementing a LALR(1) > > > parser generator in Pascal on strength of which I got my first > > > real job. At that job I used DeRemer and Pennello's 1979 > > > paper to reimplement the parser generator. > > >