Re: Yacc poll

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
--

Return to the comp.compilers page.
Search the comp.compilers archives again.