Der Formalismus BNF ist ein universeller Formalismus zur Beschreibung von Sprachen, also nicht nur zur Beschreibung arithmetischer Ausdrücke geeignet. Als weiteres Beispiel einer mit BNF beschriebenen Sprache betrachten wir die Spache der Palindrome.
Ein Palindrom ist ein Wort, das von vorne und von hinten gelesen gleich ist. Beispiele sind otto, rentner, oder (wenn wir Satz- und Leerzeichen sowie Groß- und Kleinschreibung vernachlässigen) O Genie, der Herr ehre Dein Ego. Die folgende BNF beschreibt formal die Sprache der Palindrome über dem Alphabet {a,...,z}.
Pali ::= 'a' Pali 'a' | ... | 'z' Pali 'z' | 'a' | ... | 'z' | ''
Die drei Punkte gehören hierbei nicht zum Formalismus einer Syntaxbeschreibung in BNF. Sie symbolisieren ausgelassene Regeln, die wir streng genommen alle notieren müssten. Die letzte Regel erlaubt es, das Nichtterminalsymbol Pali zum leeren Wort, also dem Wort, das keine Zeichen enthält, abzuleiten. Dadurch wird es möglich, auch Palindrome mit gerader Anzahl Buchstaben abzuleiten.
Als Beispiel leiten wir das Wort otto aus dem Nichtterminalsymbol Pali ab: