Grammars with DCGs
Parse and generate language with Definite Clause Grammars.
Prolog was born for natural-language processing, and it has built-in syntax for it: Definite Clause Grammars. A grammar rule uses --> instead of :-:
greeting --> [hello], name.Read it as "a greeting is the word hello followed by a name". Terminals, actual words, go in square brackets; non-terminals are other rules.
greeting --> [hello], name.
name --> [world].
name --> [prolog].Run a grammar with \phrase(Rule, List)\: does the list match the rule?
?- phrase(greeting, [hello, world])?- phrase(greeting, [hello, there])Like everything in Prolog it runs backwards too, leave the list open and Prolog generates sentences:
?- phrase(greeting, Words)?- phrase(greeting, [hello, Who])What --> really is
A DCG rule is syntactic sugar. Each non-terminal gets two extra arguments, a list of words before and after, and each rule describes how it consumes words from the front of the list. listing shows the translation:
?- listing(greeting/2), listing(name/2)Because of the two hidden arguments you can even call the rule directly: greeting([hello, world], []) means "greeting consumes [hello, world], leaving nothing".
A bigger grammar
sentence --> noun_phrase, verb_phrase.
noun_phrase --> determiner, noun.
verb_phrase --> verb, noun_phrase.
determiner --> [the] ; [a].
noun --> [cat] ; [dog] ; [robot].
verb --> [sees] ; [chases].?- phrase(sentence, [the, cat, chases, a, robot])?- phrase(sentence, [cat, the, chases, a, robot])?- aggregate_all(count, phrase(sentence, _), N)That grammar accepts exactly 72 sentences (2 determiners × 3 nouns × 2 verbs × 2 × 3).
Building a parse tree: extra arguments
Non-terminals can carry arguments, so a parser can return structure:
s(s(NP, VP)) --> np(NP), vp(VP).
np(np(D, N)) --> det(D), n(N).
vp(vp(V, NP)) --> v(V), np(NP).
det(det(the)) --> [the].
det(det(a)) --> [a].
n(n(cat)) --> [cat].
n(n(dog)) --> [dog].
v(v(sees)) --> [sees].
v(v(chases)) --> [chases].?- phrase(s(Tree), [the, cat, sees, a, dog])Curly braces: ordinary Prolog inside a rule
{ Goal } runs plain Prolog without consuming input. That's how you do arithmetic or type checks, here, reading numbers out of text. Text is a list of character codes; backquotes make such a list: \123\``.
digits([D|T]) --> digit(D), digits(T).
digits([D]) --> digit(D).
digit(D) --> [D], { code_type(D, digit) }.
number(N) --> digits(Ds), { number_codes(N, Ds) }.?- phrase(number(N), `1234`)?- atom_codes('2024', Codes), phrase(number(N), Codes)A calculator in 15 lines
Put it together: a grammar for +, -, *, and parentheses that also evaluates as it parses. Note the structure, * binds tighter than + because it lives lower in the grammar, and the use of loops (..._rest) rather than left recursion, which would never terminate.
expr(V) --> term(T), expr_rest(T, V).
expr_rest(Acc, V) --> "+", term(T), { Acc1 is Acc + T }, expr_rest(Acc1, V).
expr_rest(Acc, V) --> "-", term(T), { Acc1 is Acc - T }, expr_rest(Acc1, V).
expr_rest(V, V) --> [].
term(V) --> factor(F), term_rest(F, V).
term_rest(Acc, V) --> "*", factor(F), { Acc1 is Acc * F }, term_rest(Acc1, V).
term_rest(V, V) --> [].
factor(V) --> number(V).
factor(V) --> "(", expr(V), ")".
calc(Text, Value) :- string_codes(Text, Codes), phrase(expr(Value), Codes).?- calc("2+3*4", V)?- calc("(2+3)*4", V)?- calc("10-4-3", V)?- calc("2+", V)Exercise: The language aⁿbⁿ
Write a grammar rule anbn that accepts lists made of some number of as followed by the same number of bs: [], [a,b], [a,a,b,b], … but not [a,b,b] or [b,a].