Palindrome in yacc

1
votes

I have write a grammar for number palindrome in yacc. But it didn't accept the input string. Here is my grammar :

T: PAL '\n' {printf("Accepted\n");return 0;};
PAL: "1" PAL "1"|
     "2" PAL "2"|
     "3" PAL "3"|
     "4" PAL "4"|
     "5" PAL "5"|
     "6" PAL "6"|
     "7" PAL "7"|
     "8" PAL "8"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9"|"0"|;

When I input the number it will show the error message.

Here is my yacc file contents

pal.y

%{
#include<stdio.h>
%}

%%

T: PAL '\n' {printf("Accepted\n");return 0;};

PAL: "1" PAL "1"|
     "2" PAL "2"|
     "3" PAL "3"|
     "4" PAL "4"|
     "5" PAL "5"|
     "6" PAL "6"|
     "7" PAL "7"|
     "8" PAL "8"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9"|"0"|;

%%

int yywrap()
{
return 1;
}
main()
{
yyparse();
}

int yyerror(char *S)
{
printf("Not Accepted\n");
}

And here is the lex file

pal.l

%{
#include "y.tab.h"
%}

%%

\n {return *yytext;}

 . {return *yytext;}

 %%

please help me.

2
compiler-constructionyaccpalindrome
The error message that I given in the yacc file. – Sooraj K S
LR is unable to parse palindromes, no? Which is not to say your grammar is a palindrome. Except that is what you said. :-) What was your input? (preferably with a hex dump of said input) Also, since your grammar believes it will only see numerals and '\n', it would aid provability if your lexer objected to other characters, instead of just passing all illegal tokens up to the parser. Or alternatively change yyerror to reveal what was "Not Accepted". But most likely, the problem is not understanding that palindromes lie outside the ability of LR parsing... Consider input "11". – Ron Burk
A problem you have that is not central to the real problem: "1" does NOT match an input of 1 -- you need to use '1' in the .y file to match single character tokens. Using double-quotes (") in the .y file does something very non-intuitive and useless in most cases. – Chris Dodd
@ChrisDodd, Thank you for the very important remark. I have always avoid "..." tokens in bison because I don't know any good way to return them from the lexer: I believe that it is important that you post your comment as an answer to somehow clarify this tricky trap ☺ – JJoao
@RonBurk, I see the point of most of your observations. If you have the time, please check if my answer makes sense. – JJoao

2 Answers

2
votes

@Ron is correct. yacc can only parse Look-Ahead-Left-Right (LALR) grammars and a palindrome is not an LALR grammar. This is because to determine if it is a palindrome requires more than a single look-ahead. yacc parses LALR(1) languages, a subclass of context free languages (CFL) designed to be parsed in linear time. To parse a palindrome the parser must be able to decide when it has reached the middle of the palindrome. With a look ahead of just 1 (or any fixed number) this is not possible.

See this link for more details.

0
votes

One of the most popular yacc (in linux, and many others) is Bison, the gnu version of yacc has some extra features. Besides LALR(1), it can also generates LR(1), GLR.

The GLR algorithm can be used in this problem.

When a GLR parser encounters a conflict, it splits into a several parsers, one for each possible shift or reduction. These parsers then proceed as usual, consuming tokens in lock-step. Some of the stacks may encounter other conflicts and split further, with the result that instead of a sequence of states, a Bison GLR parsing stack is what is in effect a tree of states.

In the following you'll find an example using:

  • %glr-parse to select GLR-parser algorithm
  • error pseudo non-terminal (do deal with "invalid")
  • changed "1" and similar to '1'

Flex:

%option noyywrap
%%
[0-9\n]    {return yytext[0]; }
.          {fprintf(stderr, "Error\n"); exit(1);}
%%

Bison:

%{
#include <stdio.h>
int i=0;
%}

%glr-parser

%%

S  : pal   '\n'   {i=1; return 1 ;}
   | error '\n'   {i=0; return 1 ;}

pal: '0' pal '0' 
   | '1' pal '1' 
   ...
   | '0'       
   | '1'     
   |        
   ;
%%

#include "lex.yy.c"

int main() {
    yyparse();
    if(i==1) printf("Valid\n");
    else     printf("inValid\n");
    return 0;
}

int yyerror(char* s) { return 0; }

Please compare the results obtained with the original and this version for example with 1 11 111 101101 and also some invalid expressions.