Re: RFC: Requiring the ending `;'

[Hans Aberg]

At 16:31 +0100 2002/03/03, Akim Demaille wrote:
>You may know that the Bison grammar (that of the grammar files) is not
>LALR(1) because it's LR(2).  This is due to the optionality of the
>ending `;': the parser has to read the `:' after each identifier to
>learn whether the latter is an additional symbol of the current rule,
>or the LHS of the next rule.

One might make it 1-lookahead by letting say only the end actions using
"{}" (mid-rule actions using say "[]"), giving the default action a special
name. Perhaps the empty string should have a name as well.

>Since I'm willing to have a more flexible grammar parser (many new
>interesting features require additional Bison directives), I am highly
>tempted by making the `;' mandatory.

You might make a rule terminator mandatory; but in the literature, '.' is
the standard. So you might allow either ';' (for Yacc compatibility), or
'.' (making it possible to plug in grammars from books).

Also common substitutes for the ':' are "->" (books on parsing) and "::="
(BNF grammar style).

Admitting these alternatives would not make the grammar more complicated.

>  As far as I could see, no
>significant grammar exhibits lacks of `;'.

Yes, mine. :-)

And the grammar in the C++ standard.

>All the presentations I know of Yacc do use this terminator, including
>Johnson's paper.

What's this? Is it available on an URL?

>  Nevertheless, he acknowledges the problem of the non
>LR(1) grammar of Yacc, explains why, and hints at the implementation
>of a workaround, which is a form of not condemning such grammars.
>
>This workaround is yet ported to Bison grammar (in a word: instead of
>returning ID COLON, recognize this sequence, and return ID_COLON in
>addition to ID and to COLON).  But this is quite awkward, and, unless
>you really fight with Lex, won't work for
>
>my_lhs /* some comment. */ :
>
>Again, I can workaround this, but puke.

(As you probably know, "id" is the primitive undifferentiated part of the
psychic apparatus that reacts blindly on the pleasure-pain level, and was
the downfall of the Krell people in the movie "Forbidden Planet".)

You might try making Flex 2-lookahead as follows:

%%
  if identifer_name recorded, clear it and return it.
  if ":" recorded, clear it and return it.
  if "%%" recorded, clear it and return it.

[[:space:]]+     { /* Skip white-space. */ }

{identifier}                { return identifier_name }
{identifier}[[:space:]]*":" { If rule reading
                              then { record identifer_name and ":",
                                     return rule-terminator-key. }
                              else { record ":", return identifer_name. } }
{identifier}[[:space:]]*"%%" { If rule reading
                              then { record identifer_name and "%%",
                                     return rule-terminator-key. }
                              else { record "%%", return identifer_name. } }
":"   { return ":". }
"%%"  { return "%%". }
";"   { return rule_terminator-key. }
...

Here, "rule reading" means that scanning for the rules has started.

Then the .y grammar will look as though it always has a rule terminator.

  Hans Aberg