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 25b5a4ce for ; Wed, 16 Jan 2019 02:54:30 +0000 (UTC) Received: by minnie.tuhs.org (Postfix, from userid 112) id DA78094FC9; Wed, 16 Jan 2019 12:54:28 +1000 (AEST) Received: from minnie.tuhs.org (localhost [127.0.0.1]) by minnie.tuhs.org (Postfix) with ESMTP id 0999994FBA; Wed, 16 Jan 2019 12:53:49 +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="U9CcPr1N"; dkim-atps=neutral Received: by minnie.tuhs.org (Postfix, from userid 112) id 649FB94FB8; Wed, 16 Jan 2019 12:53:47 +1000 (AEST) Received: from mail-vs1-f50.google.com (mail-vs1-f50.google.com [209.85.217.50]) by minnie.tuhs.org (Postfix) with ESMTPS id 86C2E94FB7 for ; Wed, 16 Jan 2019 12:53:46 +1000 (AEST) Received: by mail-vs1-f50.google.com with SMTP id z3so3009793vsf.7 for ; Tue, 15 Jan 2019 18:53:46 -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=bLqx2tWrFRv2hJ9NggsKmFIEpVoSCYCHtmCMG8ORQN0=; b=U9CcPr1NRFeCnzO8ZoGBsIaLoU5UN0pfIYIv6SJeMftdNuQatmYa0EsnrZJ8bAYJEc JnAEYiNyLiye1c4983NjB+Y8hGDtMnLDjV0/a1VxgaoBSHUf5JklS/umMYwe09OCubq1 I6RbPQPA/Us4iSoTqseWMS5wD+hL9jA96V9jIeu4IxazyhENTZS5+wDnQqXbjqKW5Gj4 cOhT6CzLTyH1VGfEFC9P0HTETS3KBWhwkFv5qztWub3t4941Ebt44mwITwiCKTH4Hfxw 5y1PLLyXoU2J29yTtptf7VAHnky2vFhPwkbyHI6vgWaolDevaKnDdtB6tj1LRCbjl3EP XgyA== 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=bLqx2tWrFRv2hJ9NggsKmFIEpVoSCYCHtmCMG8ORQN0=; b=l4Otfz0I2FSVFu/1ZeN2kFus8QrvX59/B2VbqJa21bBxuxhSpL1zJz4YzMYhaWtQw1 +Ut1hVSeONMQ85O58q0JNZRBsGwgrphm0quj694E1Rx0jSYZFyZOZWPC/YcyjiJYlj7T ZxEEGL/PcmNr7Vy0LCjQSp+iN6tZUBeuxepcBDXvrwtPsk7J5q3V1TujY+5AJMCFhuce IUdfJYFRr6teSTwnQt7J1Q/zktEWW7NWk8Nv2u7zBXkm0h5lvgVOFRESX3R6LFVN4CtC b6HxjoyalO6LSOIGOLVzsIK2mxtaN6mJWzH2/uwCaLkOKODOs2eEOQ424H3XNZx4BblU x3Hg== X-Gm-Message-State: AJcUuke5U72zNvyQuIeB6l60TiRqxD1xyHU1TMHayFdQfSxr303TjLvc j9qZ7WKnwjZiR0RAoX3GxtkTJtOfxo3c0/znEHg= X-Google-Smtp-Source: ALg8bN4vPrx0uUHAZ0RUsD281w9uoDsc8fgEq+tPSyKO9ZNFxWpXNcnSwiF/fbizaCMQQft+tC7FQO6kx0WKP32HS8Y= X-Received: by 2002:a67:f445:: with SMTP id r5mr3036537vsn.164.1547607225450; Tue, 15 Jan 2019 18:53:45 -0800 (PST) MIME-Version: 1.0 References: <20190113044018.B235E156E410@mail.bitblocks.com> In-Reply-To: From: Rob Pike Date: Wed, 16 Jan 2019 13:53:33 +1100 Message-ID: To: Steve Johnson 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" 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 Stanford ab= out that time that influenced me greatly -- it was about pattern matching l= anguages, and proposed separating two ideas: 1. "Here are the patterns tha= t 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 broad= ening the shift/reduce test to trest operator precedence fit right into tha= t pattern. Another thing that I think was unique to Yacc at the time was = introducing symbols that matched the empty string whose reduction caused pr= ogram 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" wrot= e: > > One connection Knuth had to Unix was inventing LALR parsing, the basic > > algorithm used in Yacc. I added some things (notably, the precedence > > mechanism) and had to do a lot of engineering to be able to handle larg= e > > grammars (e.g. F77) on a PDP-11. But the underlying algorithm (taught t= o > > 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. >