4
$\begingroup$

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?

$\endgroup$
8
$\begingroup$

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.

$\endgroup$

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.