How to find unambiguous grammar for palindromes

I am trying to figure out how to make an unambiguous grammar for palindromes over the alphabet {a, b}. I have the following, but it is ambiguous and causes conflicts in yacc.

S -> a S a 
   | b S b 
   | a 
   | b 
   | ε

Is there a way to convert this to an unambiguous grammar? Or is there another solution?

First, I believe you are looking for a different word than 'unambiguous'. A grammar is ambiguous if some string in its language has two or more derivations; I'm sure that a palindromic string must have only one derivation in this grammar.

I suspect the word you really mean is 'deterministic'. YACC must declare that this grammar has 'shift-reduce' conflicts - e.g if the next letter is 'a' one cannot decide if the first, third, or fourth rule is to be applied. This is an inherent problem with palindromic languages; the core problem is that there is no way to know, during a left-to-right scan of the input string, exactly where the midpoint of the string is.

If you are permitted to change the language, you could add a new letter 'c' and use it to always (and ONLY) mark the center of each string.

StackExchange Computer Science Q#70047, answer score: 8