From: neitzel@ips.cs.tu-bs.de (Martin Neitzel)
Newsgroups: comp.compilers
Subject: Re: error productions in YACC/Bison
Keywords: yacc, debug
Date: 27 Aug 92 15:33:31 GMT
Reply-To: neitzel@ips.cs.tu-bs.de (Martin Neitzel)
Organization: Inst. f. Informatik, TU Braunschweig, FRG

I've found it worth while to expose all my students dealing with yacc to
an illustrated version of byacc.  (Authors: byacc: Bob Corbett,
illustrations: Jim Roskind.)

Mr Roskind's small changes to the byacc driver template will replace the
standard "yydebug messages" indicating current state and action of the
parser with a much more comprehensible graphical output.  I've appended a
real life example of an Modula2 parse below.  We were pretty in the dark
about the effects of interspersed error symbols until we made small
experiments with this enhanced yacc.  The students can see the difference
between discarding states and symbols, the reduction of the error symbol,
the exact timing of events in a rule like "foo: bar {A;} error {B;} ';'",
and more.

You will find Jim Roskind's enhanced driver skeleton for byacc
packaged with his C++-grammar.

						Martin Neitzel

So here is the promised example.  It's a bit lengthy (90 lines), but it
should "give you the picture".  There's a rule "IdentList: error" in the
grammar, see what happens during the faulty input "*+-":

input:	MODULE a; VAR foo, bar, *+- : INTEGER; BEGIN END a.

parse trace:

           .... look ahead at MODULE   `MODULE'
MODULE <-- `MODULE'
|            .... look ahead at IDENTIFIER   `a'
|  IDENTIFIER <-- `a'
|  ident
|  |            .... look ahead at SEMI   `;'
|  |  opt.priority
|  |  |  SEMI <-- `;'
|  |  |  |  ImportList
|  |  |  |  |            .... look ahead at VAR   `VAR'
|  |  |  |  |  DeclarationList
|  |  |  |  |  |  VAR <-- `VAR'
|  |  |  |  |  |  |  VarDeclList
|  |  |  |  |  |  |  |            .... look ahead at IDENTIFIER   `foo'
|  |  |  |  |  |  |  |  IDENTIFIER <-- `foo'
|  |  |  |  |  |  |  |  ident
|  |  |  |  |  |  |  |  IdentList
|  |  |  |  |  |  |  |  |            .... look ahead at COMMA   `,'
|  |  |  |  |  |  |  |  |  COMMA <-- `,'
|  |  |  |  |  |  |  |  |  |            .... look ahead at IDENTIFIER   `bar'
|  |  |  |  |  |  |  |  |  |  IDENTIFIER <-- `bar'
|  |  |  |  |  |  |  |  |  |  ident
|  |  |  |  |  |  |  |  +--+--+
|  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  IdentList
|  |  |  |  |  |  |  |  |            .... look ahead at COMMA   `,'
|  |  |  |  |  |  |  |  |  COMMA <-- `,'
|  |  |  |  |  |  |  |  |  |            .... look ahead at MULT   `*'

syntax error before "*".
|  |  |  |  |  |  |  |  +--+  discarding state
|  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  +--+  discarding state
|  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  error
|  |  |  |  |  |  |  |  IdentList
|  |  |  |  |  |  |  |  |  discarding token MULT
|  |  |  |  |  |  |  |  |            .... look ahead at PLUS   `+'
|  |  |  |  |  |  |  |  |  discarding token PLUS
|  |  |  |  |  |  |  |  |            .... look ahead at MINUS   `-'
|  |  |  |  |  |  |  |  |  discarding token MINUS
|  |  |  |  |  |  |  |  |            .... look ahead at COLON   `:'
|  |  |  |  |  |  |  |  |  COLON <-- `:'
|  |  |  |  |  |  |  |  |  |            .... look ahead at IDENTIFIER   `INTEGER'
|  |  |  |  |  |  |  |  |  |  IDENTIFIER <-- `INTEGER'
|  |  |  |  |  |  |  |  |  |  ident
|  |  |  |  |  |  |  |  |  |  QualIdent
|  |  |  |  |  |  |  |  |  |  |            .... look ahead at SEMI   `;'
|  |  |  |  |  |  |  |  |  |  QualTypeIdent
|  |  |  |  |  |  |  |  |  |  type
|  |  |  |  |  |  |  |  +--+--+
|  |  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |  VariableDeclaration
|  |  |  |  |  |  |  |  |  SEMI <-- `;'
|  |  |  |  |  |  |  +--+--+
|  |  |  |  |  |  |  |
|  |  |  |  |  |  |  VarDeclList
|  |  |  |  |  |  |  |            .... look ahead at START   `BEGIN'
|  |  |  |  |  |  +--+
|  |  |  |  |  |  |
|  |  |  |  |  |  declaration
|  |  |  |  |  +--+
|  |  |  |  |  |
|  |  |  |  |  DeclarationList
|  |  |  |  |  |  START <-- `BEGIN'
|  |  |  |  |  |  |            .... look ahead at END   `END'
|  |  |  |  |  |  |  statement
|  |  |  |  |  |  |  StatementSequence
|  |  |  |  |  |  |  |  END <-- `END'
|  |  |  |  |  +--+--+--+
|  |  |  |  |  |
|  |  |  |  |  block
|  |  |  |  |  |            .... look ahead at IDENTIFIER   `a'
|  |  |  |  |  |  IDENTIFIER <-- `a'
|  |  |  |  |  |  ident
|  |  |  |  |  |  |            .... look ahead at PERIOD   `.'
|  |  |  |  |  |  |  PERIOD <-- `.'
+--+--+--+--+--+--+--+
|
ProgramModule
CompilationUnit
TopLevelProductions
|            .... look ahead at end-of-file   `'
done.
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.