a yacc grammar for palindromes?

SHORT VERSION:


      Q: is it possible to write a yacc grammar to recognize palindromes?




LONG VERSION:


If I recall language theory class correctly, a ND-PDA (non-deterministic
pushdown automata) is more powerful than a D-PDA (a deterministic PDA).
In particular, a ND-PDA can handle the language of palindromes, whereas
a D-PDA can't.


But a D-PDA can *simulate* a ND-PDA by basically trying all the possible
combinations. This would take exponential time (i.e., each time we added
one token to the input, it would double the time it takes to parse the
input).


I tried this with yacc, with a simple grammar for palindromes for the
input characters 0 and 1. yacc reported the warning:


                        conflicts: 6 shift/reduce


but it wasn't a fatal error. However, it refused to recognize any
palindromes:




                  hprcl171(ted) 668>cat test1
                  10101
                  hprcl171(ted) 668>p < test1
                  S -> ONE
                  syntax error
                  hprcl171(ted) 669>




Q: is it impossible for a D-PDA to recognize palindromes, or did I
      just screw up my yacc grammar?


The complete program is very short, and is appended below with a
compile script.


Thanks!


-Ted


--------cut here---------


# This is a shell archive. Remove anything before this line,
# then unpack it by saving it in a file and typing "sh file".
#
# Wrapped by Ted Johnson <ted@hprcl171> on Thu Mar 30 22:47:29 1995
#
# This archive contains:
# makeit p.l p.y test1
#


LANG=""; export LANG
PATH=/bin:/usr/bin:$PATH; export PATH


echo x - makeit
cat >makeit <<'@EOF'
#!/bin/ksh
set -xv


CFLAGS="-g -Ae +e"


yacc -vd p.y
lex p.l
cc -c $CFLAGS lex.yy.c
cc -c $CFLAGS y.tab.c
cc -Aa -o p lex.yy.o y.tab.o -ll -ly
@EOF


chmod 755 makeit


echo x - p.l
sed 's/^@//' >p.l <<'@EOF'
%{
#include "y.tab.h"
%}


%%


[ \t] { ; /*ignore whitespace*/}
[0] { return(ZERO);printf("got a 0\n"); }
[1] { return(ONE);;printf("got a 1\n"); }


@. { fprintf(stderr, "Bad input char -->%c<-- on line %d\n",
                                            yytext[0], yylineno);}
%%
@EOF


chmod 644 p.l


echo x - p.y
cat >p.y <<'@EOF'
%{
%}


%token ZERO ONE


%%


start : { printf("S -> nada\n"); }
          | ZERO { printf("S -> ZERO\n"); }
          | ONE { printf("S -> ONE\n"); }
          | ZERO start ZERO { printf("S -> ZERO S ZERO\n"); }
          | ONE start ONE { printf("S -> ONE S ONE\n"); }
          ;


%%


main()
{
      yyparse();
}
@EOF


chmod 644 p.y


echo x - test1
cat >test1 <<'@EOF'
10101
@EOF


chmod 644 test1


exit 0
--

Return to the comp.compilers page.
Search the comp.compilers archives again.