16 Jan
2019
16 Jan
'19
8:53 a.m.
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 <scj(a)yaccman.com> 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 about that time
that influenced me greatly -- it was about pattern matching 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 broadening 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 caused program
actions. Many similar parser systems at the time could not deal with these
"empty" symbols.
Steve
----- Original Message -----
From: "Bakul Shah" <bakul(a)bitblocks.com>
To:"Steve Johnson" <scj(a)yaccman.com>
Cc:<arnold@skeeve.com>, <ecashin(a)noserose.net>, <dave(a)horsfall.org>,
<tuhs(a)tuhs.org>
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" <scj(a)yaccman.com>
wrote:
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 large
grammars (e.g. F77) on a PDP-11. But the underlying algorithm (taught 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.