Palindromes are words or sentences which are the unchanged by reversing the letters. Usually we ignore capitalisation, spaces and punctuation, so “Anna”, “Bob”, “Eve”, “Hannah” and “Otto” are palindromes, as are “Cigar? Toss it in a can. It is so tragic.” and “ΝΙΨΟΝ ΑΝΟΜΗΜΑΤΑ ΜΗ ΜΟΝΑΝ ΟΨΙΝ”.
A grammar for palindromes is
palindrome : | non_empty_p
non_empty_p : "a" non_empty_p "a" | "b" non_empty_p "b"
| ... | "z" non_empty_p "z" | "a" "a"
| "b" "b" | ... | "z" "z" | "a" | "b" | ... | "z"This assumes that the lexical analyser strips out everything which isn’t a letter of the English alphabet and changes every upper case letter to the corresponding lower case letter. The “…” isn’t really part of our language for specifying grammars. I just used it to prevent the specification from being too long.
It’s important to realise that the following would not be a grammar for the language of palindromes.
palindrome : | non_empty_p
non_empty_p : letter non_empty_p letter | letter letter | letter
letter : "a" | "b" | ... | "z"The problem with this grammar is that in the expansions
letter non_empty_p letter and letter letter
the two different occurrences of letter could expand to
different letters, so we wouldn’t have a palindrome.