Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watmath!clyde!ima!johnl
From: johnl@ima.UUCP
Newsgroups: comp.compilers
Subject: Re: Yacc poll
Message-ID: <283@keilir.UUCP>
Date: Fri, 14-Aug-87 13:02:03 EDT
Article-I.D.: keilir.283
Posted: Fri Aug 14 13:02:03 1987
Date-Received: Sun, 16-Aug-87 09:44:55 EDT
References: <634@ima.ISC.COM>
Sender: johnl@ima.ISC.COM
Reply-To: malcolm@keilir.UUCP (Malcolm Cohen)
Organization: University of Iceland (RHI)
Lines: 52
Approved: compilers@ima.UUCP

In article <634@ima.ISC.COM> harvard!ames!ausmelb!ejp writes:
>I am presently involved in a discussion about compiler implementation,
>specifically the pros and cons of Yacc,
>and I would like opinions from other experienced compiler-writers.

Well, the Toolpack/1 parser was generated using Yacc (the output was munged
into Fortran though).  Recursive-descent parsing was considered (1) probably
insufficiently powerful to parse Fortran's somewhat grubby syntax, and (2 -
more importantly) impossible since ANSI Fortran does not provide recursion.
"ad hoc" was *NEVER EVER* considered suitable for parsing Fortran - it was hard
enough to get the bugs out of the Yacc input code (~1500 lines).

My own experience with writing recursive-descent parsers is that it is easy
to provide error recovery far superior to the normal Yacc stuff (and which one
often sees in C compilers).  Unfortunately this also depends on the syntax of
the language in question - if there is not much variety of input 'terminator'
symbols (e.g. ';', 'end' in Pascal) error recovery is hobbled anyway.

The only place where I would use ad-hoc methods by choice is in lexical
analysis, as this is probably simple enough to hand-craft decently.  In lexing
Fortran one has either to hand-craft an ad-hoc lexer or use something more
powerful than regular expressions (vis. lex) - or sadistically leave it to the
parser-writer to tokenise 'DO' statements etc...  Toolpack/1 used a
table-driven pushdown automaton with backtracking - ugh.

Thus Toolpack/1 took a similar approach to that of Stu Feldman with his f77
compiler - FORTLEX for the lexer, and YACC for the parser.  I recommend that
anyone who is considering the use or not of Yacc to read his paper describing
his implementation experience (in the proceeding of some ancient SIGPLAN
conference  - I think 1978).  He recommends its use.

>There seem to be some standard objections to Yacc in particular, e.g.
>	c. the incomprehensibility of the C output
Perfectly comprehensible - even when translated into Fortran!
>	f. debugging difficulties
Certainly easier than with an ad hoc parser (except for very small languages).

>and some more general objections, e.g.
>	g. generic objections to LR parsing
Well, if recursive descent (LL) is powerful enough without kludging the
grammar, I find it can provide a more convenient framework for the semantics
and error recovery - but only for a suitable target language (not COBOL).
In this case LR has no advantages over LL, and may even lose because of its
excessive power.
-- 
Malcolm Cohen			       mcvax!keilir!malcolm
Utgardar, Computer Centre, University of Iceland, Reykjavik
--
Send compilers articles to ima!compilers or, in a pinch, to Levine@YALE.ARPA
Plausible paths are { ihnp4 | decvax | cbosgd | harvard | yale | cca}!ima
Please send responses to the originator of the message -- I cannot forward
mail accidentally sent back to compilers.  Meta-mail to ima!compilers-request