Re: [REQUEST] Infinite recursion warning

[David M. Warme]

The problem isn't exactly infinite recursion, at least not as far
as Bison is concerned.  The error/warning messages are indeed
suboptimal.  Bison reports a constellation of symbols/rules as
being "useless."

When most people (myself included) see this message, they usually
assume that this means that the symbol is "unreachable from the
start symbol."  This is indeed one of the root causes for the
"useless symbol/rule" messages.  But there is, in fact, a second
possible root cause for seeing the "useless" message --
namely grammar symbols/rules that cannot be reduced to a string
consisting entirely of tokens.  This is in fact the root cause
for the "infinite recursion" issue that started this thread.

Note that any interesting LALR(1) grammar winds up being
infinitely recursive -- it can be used to derive strings of
arbitrary length (infinite length in the limiting case).
What is different here is the *inability* to derive a string
containing only tokens (once the offending symbol is ever
derived).  If the rule/symbol cannot derive a string consisting
entirely of tokens (using the grammar as a generative process),
then it is impossible to run this generative process in reverse
-- taking the sequence of (only) tokens and producing its
derivation in terms of the grammar rules -- i.e., parsing.

I have a batch of Bison enhancements that I have been meaning
to donate, but have not gotten around to doing so.  The main
feature is a grammar annotation:

   %begin-library "foo"

      /* grammar rules */

   %end-library

This declaration causes Bison to assume that all rules defined
in this section (and the non-terminal symbols appearing on their
left-hand-sides) are part of a cohesive "library" (e.g., a
grammar header file).  Bison will not warn that any of these
symbols are useless -- unless ALL of them are useless (i.e.,
the grammar header file was included unnecessarily).  Furthermore,
Bison simply reports that library "foo" is useless, instead of
puking out a separate "useless" message for every symbol and rule
contained in the library.

Note that we use GNU M4 to perform "include" processing on our
grammar files, and this include mechanism automatically adds
the %begin-library ... %end-library declarations.

Another reason this is useful is because although most grammar
header files define a single "root" grammar symbol that clients
refer to, it is occasionally convenient to have several "closely
related" root grammar symbols in a header file, e.g.:

   foobar_phrase_with_baz_blivets : ... ;

   foobar_phrase_without_baz_blivets : ... ;

Few high-level grammars will refer to both/all of these
alternate root symbols -- leaving a few of them that get flagged
as being "useless".  In our context, these warning messages are
annoying artifacts of our software architecture, and not anything
to be concerned about.  The %begin-library ... %end-library
declaration is a convenient mechanism to suppress these otherwise
annoying warning messages (unless the entire library is "useless").

As part of these changes, I revamped the "useless" grammar
symbol reporting to indicate (for each useless grammar symbol or
rule) the reason for it being useless.  This reason can be either:

   1. Symbol is unreachable from the %start symbol,
   2. Symbol cannot be reduced to a string consisting
      entirely of tokens, or
   3. Both.

If I recall correctly, it annotates the messages with tags
like [1], [2], or [1,2].  After all of the "useless" messages are
displayed, it outputs a "secret decoder ring" indicating what [1]
and [2] mean as I have shown above.  So the error reporting winds
up being rather concise, but also quite precise and certainly much
more informative than Bison's present "useless" warning messages.

David Warme


Le 15 déc. 2013 à 01:31, Arthur Schwarz <address@hidden> a écrit :

> > exp:NIL
> >    | NIL list
> >
> > list:NIL list
> >
> > I won't address the issue of messaging (unqualified and this is an 
issue best addressed by the development team) but I will explore the 
grammar.

Valentin is well aware of the fact that the grammar is broken.
He actually contributed not trivial code to the Bison base
code.  His point is not to have help on his grammar, but to
report that the diagnostics are suboptimal.
_______________________________________________
address@hidden https://lists.gnu.org/mailman/listinfo/help-bison