Re: avoiding infinite loops

[Sylvain Schmitz]

Hans Aberg wrote:
> You should have gotten an ambiguous grammar. Then Bison still produces a 
> runnable parser by choosing: in the case of reduce/reduce conflicts, 
> shift over reduce, and in the case of reduce/reduce conflicts, the first 
> occurring reduce in the .y grammar.

Since we are talking about conflicts and looping parsers, there is a 
possibility for an infinite loop with bison's conflict resolution in 
LALR(1).  See attached file loop.y.  (And there is a different looping 
possibility in GLR; the kind of grammars that can trigger it is a bit 
similar---see 
<http://lists.gnu.org/archive/html/bison-patches/2006-03/msg00030.html>.)

--
Regards,

  Sylvain

/* loop.y
 *
 * Looping grammar found in _Looping_LR_Parsers_, Eljas
 * Soisalon-Soininen and Jorma Tarhio, Information Processing Letters
 * 26:251--253, 1988.
 *
 * Run the executable with "ab" as command-line argument.
 */

%{
  #include <stdio.h>
  char *yystring;

  int yylex (void);
  void yyerror (const char *);
%}

%left 'b'
%left 'a'

%%

s:
    a 'b'
  ;

a:
    b
  ;

b:
    'a'
  | a %prec 'a' /* make bison prefer this reduction over a shift of 'b' */
  ;

%%

int
yylex (void)
{
  return *yystring++;
}

void
yyerror (const char *msg)
{
  fprintf (stderr, "%s\n", msg);
}

int
main (int argc, char *argv[])
{
  int ret;
  yystring = argv[1];
  ret = yyparse ();
  return ret;
}