Palindrome Example [ISO]

Grammar rules are also included in the Jekejeke Prolog programming language. The given example allows detecting and generating palindromes. A palindrome is a string that reads the same in the reverse. We can again invoke a graphical intuition based on a sieve to explain our algorithm. In a first step we list the characters of the word, here “racecar”:


The algorithm works outside in by crossing out uncrossed characters. A left outer character and a right outer character can be crossed out when they are the same. If all characters have been crossed out or only one character is left, we have detected a palindrome.

Prolog grammar rules by default work on lists of terminals. Our terminals here are the characters. We define one non-terminal palin that should be able to detect palindromes. The corresponding grammar rules are:

palin --> [_].
palin --> [Middle, Middle].
palin --> [Border], palin, [Border].

The first rule is one of our stopping conditions. We stop when no more characters are left. The second rule expresses that we stop when a single character is left, whereby we don’t care which character it is. The last rule expresses our crossing out step and the continuation of the palindrome check. Grammar rules can be invoked via the phrase/2 predicate:

?- phrase(palin, "racecar").
Yes
?- phrase(palin, "anna").
Yes
?- phrase(palin, "bert").
No

Grammar rules might also return attributes. We simply have to extend the non-terminal palin by further arguments. Our plan is to return the middle element, if it exists and the border elements whereby we do not duplicate them. The corresponding grammar rules are:

palin([], [Middle]) --> [Middle].
palin([Middle], []) --> [Middle, Middle].
palin([Border | List], Middle) --> [Border], palin(List, Middle), [Border].

In the first rule we encode the nonexistence of a middle element by an empty list. In the second rule we encode the middle element by a singleton list. The last rule collects the border elements. The grammar rules are again invoked via the phrase/2 predicate:

?- phrase(palin(X1, Y1), "racecar"), atom_codes(X2,X1), atom_codes(Y2,Y1).
X1 = [114, 97, 99],
Y1 = [101],
X2 = rac,
Y2 = e
?- phrase(palin(X1, Y1), "anna"), atom_codes(X2,X1), atom_codes(Y2,Y1).
X1 = [97, 110],
Y1 = [],
X2 = an,
Y2 = ''
?- phrase(palin(X1, Y1), "bert"), atom_codes(X2,X1), atom_codes(Y2,Y1).
No

But grammar rules can not only be used to detect strings or to extract information from strings. It is also possible to use grammar rules to generate strings. In many cases we it is enough to simply use the grammar attributes as input and the strings as output.

?- phrase(palin("ra", "d"), X1), atom_codes(X2,X1).
X1 = [114, 97, 100, 97, 114],
X2 = radar

The presented examples should work across a great range of Prolog systems. Although there is not yet a definite DCG standard most of the Prolog systems support DCGs.

Kommentare