Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!ucsd!swrinde!cs.utexas.edu!husc6!spdcc!ima!esegue!compilers-sender
From: corbett@ernie.Berkeley.EDU (Robert Corbett)
Newsgroups: comp.compilers
Subject: PD Yacc slows down
Message-ID: <1989Nov15.010400.11488@esegue.segue.boston.ma.us>
Date: 15 Nov 89 01:04:00 GMT
Sender: compilers-sender@esegue.segue.boston.ma.us
Reply-To: corbett@ernie.Berkeley.EDU (Robert Corbett)
Distribution: usa
Organization: University of California, Berkeley
Lines: 20
Approved: compilers@esegue.segue.boston.ma.us

I have nearly completed the next version of Berkeley Yacc.  Some of the
changes were to make error recovery more effective (though Yacc error recovery
is never very effective).  If a state contains a reduction where the lookahead
is the error token, no default reduction is used in that state.  For one of my
test grammars, this change has doubled the table size and the time required to
generate the tables.  The bulk of the time (45%) was spent in fprintf.

I made this change in response to the footnote on page 71 of the book
Introduction to Compiler Construction with UNIX by Schreiner and Friedman.
I am beginning doubt if the resulting improvement is worth the cost.
I have devised a way of achieving the same effect without increasing the
size of the tables.  However, my alternative will make parsing slower.

						Yours truly,
						Robert Paul Corbett
[From corbett@ernie.Berkeley.EDU (Robert Corbett)]
-- 
Send compilers articles to compilers@esegue.segue.boston.ma.us
{spdcc | ima | lotus}!esegue.  Meta-mail to compilers-request@esegue.
Please send responses to the author of the message, not the poster.