1
$\begingroup$

I have written a yacc program for generating palindromic strings consisting of 0s and 1s. Here is the rules section of the yacc program below:

%%
program: expr NL { printf("Valid string.\n"); exit(0); }
;
expr: ZERO expr ZERO
| ONE expr ONE 
| ZERO 
| ONE
|
;
%%

Here ZERO is the token representing 0, ONE is the token representing 1, and NL represents \n. Using yacc on the above grammar, I'm given the following warnings.

yacc -dt --verbose 7b.y
7b.y: warning: 4 shift/reduce conflicts [-Wconflicts-sr]
7b.y: warning: 2 reduce/reduce conflicts [-Wconflicts-rr]

To the best of my knowledge, the grammar above seems to be unambiguous. My questions are:

  1. Why is yacc giving me this error?
  2. What should I change to resolve this?

Here are the complete lex and yacc programs if they should help:

Lex:

%{
#include <stdlib.h>
void yyerror(char *);
#include "y.tab.h"
%}
%%
[0] { yylval = 0; return ZERO; }
[1] { yylval = 1; return ONE; }
\n { return NL; }
. yyerror("invalid character");
%%
int yywrap(void) {
return 1;
}

Yacc:

%{
#include <stdio.h>
#include <stdlib.h>
int yylex(void);
void yyerror(char *);
%}
%token ZERO ONE NL
%%
program: expr NL { printf("Valid string.\n"); exit(0); }
;
expr: ZERO expr ZERO
| ONE expr ONE 
| ZERO 
| ONE
|
;
%%
void yyerror(char *s) {
fprintf(stderr, "Invalid string.\n");
}
int main(void) {
yyparse();
return 0;
}

Thanks for your help in advance.

$\endgroup$
3
  • $\begingroup$ (Consider giving more to look-ahead to.) $\endgroup$
    – greybeard
    Sep 29 at 5:39
  • $\begingroup$ @greybeard sorry I'm new to stackexchange. What does "look-ahead to" mean? $\endgroup$ Sep 29 at 5:55
  • $\begingroup$ (That has been a lame pun on the method "YACC parsers" use to resolve conflicts.) Have another look at your last rule: Can you imagine any rule not having a conflict with this one? How can you fix this? $\endgroup$
    – greybeard
    Sep 29 at 6:10
2
$\begingroup$

The grammar is, as you say, unambiguous. But it is not deterministic. LR parsers with bounded lookahead can only recognise deterministic languages; since not all unambiguous context-free languages are deterministic, LR parsers cannot recognise all unambiguous context-free languages.

Intuitively, palindromes are non-deterministic because the parser must switch states precisely at the middle of the input, but there is no way to tell where the middle of a sentence is until you know where the end is, which is obviously not possible with bounded lookahead.

Proving that the language of palindromes is not deterministic is a bit of work. You probably won't find the proof in a textbook oriented towards writing compilers, such as the Dragon Book, but if you are studying formal language theory you might be working with a more theory-oriented textbook (such as Hopcroft and Ullman.) There is a proof that the language of even-length palindromes is non-deterministic here, and extending the proof to the language of all palindromes is not that difficult.

$\endgroup$
1
  • $\begingroup$ Congrats on the recent 10k @rici :) $\endgroup$
    – nir shahar
    Sep 29 at 8:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.