A language built for language
Lesson 1 told how Prolog was born in Marseille among people who wanted computers to read French. Parsing was not an application added later; it was the reason the language exists. The idea that made it natural is simple: a grammar is a set of rules, and so is a Prolog program. "A sentence is a noun phrase followed by a verb phrase" has exactly the shape of a clause, "S is a sentence if it splits into a noun phrase and a verb phrase".
Prolog gives this idea its own notation, the definite clause grammar or DCG. You write grammar rules almost as a linguist would, and Prolog turns them into ordinary clauses. The result is a parser with backtracking built in: when a rule does not fit, Prolog tries the next, exactly as in lesson 3. Because it is still Prolog, the same grammar can also generate sentences, build parse trees, and run arbitrary checks along the way.
DCGs are not only for natural language. They are one of the most pleasant ways in any language to write parsers for small languages and data formats: configuration files, commands, arithmetic, protocols. This lesson starts with a fragment of English and ends with an arithmetic language and a command language with error reports.
Grammar rules
Definition— Definite clause grammar (DCG)
A set of grammar rules written Head --> Body. The head is a nonterminal, a name with optional arguments. The body is a sequence, separated by commas, of nonterminals, terminals (literal items to match, written as a list such as [the] or, for text, a string such as "+"), Prolog goals in braces { ... }, and alternatives ( A ; B ). The empty sequence is written [].
A DCG describes a sequence, usually a list of words or of character codes. You run it with phrase/2: phrase(sentence, Words) is true if the whole list Words is a sentence. phrase/3, phrase(sentence, Words, Rest), allows a prefix of Words to be the sentence and binds Rest to what is left over.
How does Prolog run a grammar? It translates each rule into a clause with two extra arguments: the list before the phrase, and the list remaining after it. A pair of lists used this way, "the input, and what is left of it", is called a difference list: the phrase consists of the items you must take off the first list to reach the second. The rule
greeting --> [hello], name.becomes, roughly,
greeting(S0, S) :- S0 = [hello|S1], name(S1, S).which reads "a greeting runs from S0 to S if S0 starts with hello and a name runs from what follows to S". Each nonterminal hands the remaining input to the next. Because of the two hidden arguments, a nonterminal written noun(N) becomes a predicate noun/3; documentation writes it as noun//1, with a double slash, to mean "a nonterminal with one argument of its own".
Inside braces, { Goal } is a plain Prolog goal that consumes no input, so a grammar can do arithmetic, consult facts or check conditions as it parses.
From recognising to parsing to generating
A first grammar
Here is a tiny grammar for a fragment of English: noun phrases are a determiner and a noun, or a name; verb phrases are a verb with or without an object.
:- initialization(main, main).
% A tiny grammar for a fragment of English.
sentence --> noun_phrase, verb_phrase.
noun_phrase --> determiner, noun.
noun_phrase --> name.
verb_phrase --> verb, noun_phrase.
verb_phrase --> verb.
determiner --> [the].
determiner --> [a].
noun --> [farmer].
noun --> [poem].
name --> [amina].
name --> [tomas].
verb --> [reads].
verb --> [writes].
% test(Words): say whether Words is a sentence of the grammar.
test(Words) :-
( phrase(sentence, Words)
-> format("yes: ~w~n", [Words])
; format("no: ~w~n", [Words])
).
main :-
test([amina, writes, a, poem]),
test([the, farmer, reads]),
test([poem, the, reads]),
aggregate_all(count, phrase(sentence, _), N),
format("The grammar has ~w sentences. The first five:~n", [N]),
forall(limit(5, phrase(sentence, S)),
( atomic_list_concat(S, ' ', Text),
format(" ~w~n", [Text]) )),
format("Two rules as Prolog sees them:~n"),
forall(member(Rule, [(sentence --> noun_phrase, verb_phrase),
(determiner --> [the])]),
( dcg_translate_rule(Rule, Clause),
portray_clause(Clause) )).yes: [amina,writes,a,poem]
yes: [the,farmer,reads]
no: [poem,the,reads]
The grammar has 84 sentences. The first five:
the farmer reads the farmer
the farmer reads the poem
the farmer reads a farmer
the farmer reads a poem
the farmer reads amina
Two rules as Prolog sees them:
sentence(A, B) :-
noun_phrase(A, C),
verb_phrase(C, B).
determiner(A, B) :-
A=[the|B].Three things happened with one grammar:
- Recognising.
phrase(sentence, Words)with a given list says yes or no. - Generating. With the list left unbound,
phrase(sentence, S)produces sentences on backtracking, in depth-first order.limit(5, Goal)keeps only the first five solutions, andaggregate_all(count, ...)counts them all: 6 noun phrases (4 with a determiner, 2 names) times 14 verb phrases (12 with an object, 2 without) makes 84. A grammar is a description of a language, and Prolog can run a description in either direction. - Translating.
dcg_translate_rule/2shows the clause Prolog actually compiles. Thesentencerule threads the list through its two parts,AtoCtoB, and the terminal[the]becomes the unificationA = [the|B]: the input must start withthe, and the rest is what is left. (portray_clause/1prints a clause with tidy variable names.)
Arguments: agreement and parse trees
Nonterminals can take arguments, and this is where DCGs become more powerful than the grammars of a textbook on formal languages. One argument can carry grammatical number, so that the subject and the verb must agree; another can build the parse tree. Here the words live in an ordinary table of facts, and the grammar consults it inside braces:
:- initialization(main, main).
% word(Word, Category, Number): the lexicon, kept as ordinary facts.
word(the, det, _).
word(a, det, singular).
word(farmer, noun, singular).
word(farmers, noun, plural).
word(poem, noun, singular).
word(poems, noun, plural).
word(reads, verb, singular).
word(read, verb, plural).
word(writes, verb, singular).
word(write, verb, plural).
% sentence(Tree): subject and verb must agree in number.
sentence(s(NP, VP)) -->
noun_phrase(NP, Num),
verb_phrase(VP, Num).
noun_phrase(np(D, N), Num) -->
det(D, Num),
noun(N, Num).
verb_phrase(vp(V, NP), Num) -->
verb(V, Num),
noun_phrase(NP, _).
verb_phrase(vp(V), Num) -->
verb(V, Num).
det(det(W), Num) --> [W], { word(W, det, Num) }.
noun(noun(W), Num) --> [W], { word(W, noun, Num) }.
verb(verb(W), Num) --> [W], { word(W, verb, Num) }.
% parse(Text): split Text into words and print its tree, if it has one.
parse(Text) :-
split_string(Text, " ", "", Strings),
maplist([S, A]>>atom_string(A, S), Strings, Words),
( phrase(sentence(Tree), Words)
-> format("~w~n ~w~n", [Text, Tree])
; format("~w~n no parse~n", [Text])
).
main :-
parse("the farmers write a poem"),
parse("a farmer reads the poems"),
parse("the farmer read a poem"),
parse("a farmers reads"),
phrase(sentence(s(np(det(the), noun(poems)), vp(verb(V)))), Words),
format("Generated from a tree with a hole: ~w~n", [Words]),
format("verb chosen: ~w~n", [V]).the farmers write a poem
s(np(det(the),noun(farmers)),vp(verb(write),np(det(a),noun(poem))))
a farmer reads the poems
s(np(det(a),noun(farmer)),vp(verb(reads),np(det(the),noun(poems))))
the farmer read a poem
no parse
a farmers reads
no parse
Generated from a tree with a hole: [the,poems,read]
verb chosen: readFollow the variable Num. In sentence//1, the noun phrase and the verb phrase share it, so whatever number the subject has, the verb must have too: "the farmer read a poem" fails because farmer is singular and read plural. Inside noun_phrase//2, the determiner and the noun share it as well, so "a farmers" fails. The fact word(the, det, _) leaves the number open, so the goes with either. Agreement costs one shared variable, which is unification doing what it does best. The object's number, by contrast, is free (noun_phrase(NP, _)), because in English the object need not agree with anything.
The first argument of each nonterminal builds a tree as the parse goes, in exactly the way lists were built in clause heads in lesson 4. And the last query runs the grammar backwards from a partial tree: the subject is fixed and the verb is a hole. Prolog fills the hole with a plural verb without an object and produces the words. The grammar knows agreement, not meaning, so "the poems read" is grammatical to it.
Parsing text
Characters, codes and library(dcg/basics)
To parse text rather than lists of words, run the grammar over the text's characters. The usual representation is a list of character codes (integers), which string_codes/2 produces. In SWI-Prolog, a double-quoted literal inside a grammar body, such as "+", stands for its list of codes, so you can write terminals naturally. (Outside grammar bodies, "..." is a string object, as lesson 4 said.)
library(dcg/basics) provides the nonterminals every text parser needs: blank//0 (one whitespace character), blanks//0 (any amount, including none), integer//1, number//1, digits//1, string//1 (any sequence of codes, shortest first) and string_without//2 (codes up to one of a set of stop characters), among others.
An arithmetic parser, and the left-recursion trap
Arithmetic expressions have two classic requirements. Precedence: * binds more tightly than +, so 1 + 2 * 3 is 7. Associativity: 10 - 4 - 3 means (10 - 4) - 3, which is 3, not 10 - (4 - 3), which is 9. A grammar handles precedence with one nonterminal per level (expressions are made of terms, terms of factors). Associativity is where the trap lies. The textbook rule for a left-associative operator is
expr(L - R) --> expr(L), "-", term(R).
expr(T) --> term(T).and in Prolog it never terminates: to parse an expr, the first rule first parses an expr, which first parses an expr, and so on, without consuming a single character. This is the left recursion of lesson 3 in grammar form. The standard cure parses the first term, then loops over the rest with an accumulator that holds the tree built so far, so each new operator applies to everything on its left:
:- initialization(main, main).
:- use_module(library(dcg/basics)).
% expr(E): an expression of terms joined by + and -, grouped to the left.
expr(E) --> term(T), expr_rest(T, E).
expr_rest(Acc, E) --> blanks, "+", term(T), expr_rest(Acc + T, E).
expr_rest(Acc, E) --> blanks, "-", term(T), expr_rest(Acc - T, E).
expr_rest(E, E) --> [].
% term(T): factors joined by * and /.
term(T) --> factor(F), term_rest(F, T).
term_rest(Acc, T) --> blanks, "*", factor(F), term_rest(Acc * F, T).
term_rest(Acc, T) --> blanks, "/", factor(F), term_rest(Acc / F, T).
term_rest(T, T) --> [].
% factor(F): a number or a bracketed expression.
factor(N) --> blanks, number(N).
factor(E) --> blanks, "(", expr(E), blanks, ")".
% calc(Text): parse Text, show the tree, and evaluate it with is/2.
calc(Text) :-
string_codes(Text, Codes),
( phrase((expr(E), blanks), Codes)
-> V is E,
format("~w~t~18|=> ~w~t~36|= ~w~n", [Text, E, V])
; format("~w~t~18|=> syntax error~n", [Text])
).
main :-
calc("1 + 2 * 3"),
calc("(1 + 2) * 3"),
calc("10 - 4 - 3"),
calc("2 * (3 + 4) - 5"),
calc(" 7 / 2 "),
calc("1.5 * 4"),
calc("2 + * 3"),
calc("(1 + 2"),
string_codes("10 - 4 - 3", Codes),
phrase((expr(Tree), blanks), Codes),
format("10 - 4 - 3 in canonical form: ~k~n", [Tree]).1 + 2 * 3 => 1+2*3 = 7
(1 + 2) * 3 => (1+2)*3 = 9
10 - 4 - 3 => 10-4-3 = 3
2 * (3 + 4) - 5 => 2*(3+4)-5 = 9
7 / 2 => 7/2 = 3.5
1.5 * 4 => 1.5*4 = 6.0
2 + * 3 => syntax error
(1 + 2 => syntax error
10 - 4 - 3 in canonical form: -(-(10,4),3)A few things make this short program work:
- The parser builds Prolog's own arithmetic terms,
Acc + Tand so on, as its trees. So evaluating the parsed expression is justV is E, theis/2of lesson 5. In a larger interpreter you would build your own node types, such asadd(L, R), and write an evaluator over them, but the shape of the parser would be the same. ~kprints a term in canonical form, without operators, which makes the grouping visible:-(-(10,4),3)is(10 - 4) - 3. The accumulator inexpr_rest//2made it so.- Whitespace is handled in one place: every token is preceded by
blanks, andcalc/1allows trailing blanks withphrase((expr(E), blanks), Codes). A body can be any DCG body, including a conjunction in brackets. number//1from dcg/basics reads integers and floats, which is why1.5 * 4works. As in lesson 5,7 / 2evaluates to3.5and1.5 * 4to the float6.0.- A syntax error is simply failure:
phrase/2finds no way to read the whole input. That is honest but not very helpful, which is the next program's subject.
A command language, with error positions
Real parsers must say where the input went wrong. phrase/3 makes this possible: it lets the grammar consume as much as it can and hands back the rest. Here a delivery robot reads a route such as north 3, east 12, pause:
:- initialization(main, main).
:- use_module(library(dcg/basics)).
% commands(Cs): one or more commands separated by commas.
commands([C|Cs]) -->
blanks, command(C), blanks,
( ",", commands(Cs)
; { Cs = [] }
).
% command(C): a move with a direction and a distance, or a pause.
command(move(Dir, N)) --> direction(Dir), blank, blanks, integer(N), { N > 0 }.
command(pause) --> "pause".
direction(north) --> "north".
direction(south) --> "south".
direction(east) --> "east".
direction(west) --> "west".
% step(Command, Position0, Position): carry out one command.
step(move(north, N), X-Y0, X-Y) :- Y is Y0 + N.
step(move(south, N), X-Y0, X-Y) :- Y is Y0 - N.
step(move(east, N), X0-Y, X-Y) :- X is X0 + N.
step(move(west, N), X0-Y, X-Y) :- X is X0 - N.
step(pause, P, P).
% run(Text): parse a route, report where parsing stopped if it failed,
% otherwise follow the route from 0-0.
run(Text) :-
string_codes(Text, Codes),
( phrase(commands(Cs), Codes, Rest)
-> true
; Cs = [], Rest = Codes
),
( Rest == []
-> foldl(step, Cs, 0-0, End),
length(Cs, N),
format("~w commands, ending at ~w~n", [N, End])
; length(Codes, Len),
length(Rest, RestLen),
Col is Len - RestLen + 1,
format("stopped at column ~w: ~s~n", [Col, Rest])
).
main :-
run("north 3, east 12, pause, south 1, west 4"),
run(" east 5 ,north 2"),
run("north 3, up 2, east 1"),
run("north 3 east 1"),
run("west 0").5 commands, ending at 8-2
2 commands, ending at 5-2
stopped at column 8: , up 2, east 1
stopped at column 9: east 1
stopped at column 1: west 0How it works:
commands//1tries the comma branch first, so the first solution ofphrase/3is the longest list of commands it can read. If the whole input is consumed,Restis[]and the route runs; otherwise the length ofResttells us the column where reading stopped, and~sprints the unread codes as text.{ N > 0 }checks a condition during the parse, sowest 0is rejected by the grammar itself.- The grammar produces a list of plain terms such as
move(east, 12), and a separate predicate,step/3, gives them meaning, folded over the list withfoldl/4from lesson 4. Keeping parsing and evaluation apart is good design in any language. - The error positions are where the longest valid prefix ends, which is a common and useful convention, though not the only one. In
north 3, up 2, the parser readnorth 3and then could not continue, so it points at the comma beforeup. Production parsers often go further: they remember the furthest point any alternative reached and what it expected there, and raise an exception carrying that position, so the caller can print a message such as "expected a direction at column 10".
For files, phrase_from_file/2 from library(pio) runs a grammar over a file's contents lazily, reading only as much as the parse needs, so even very large files can be parsed with the same rules.
Grammars, then and now
The grammar notation grew up with Prolog. In the early 1970s Alain Colmerauer had already designed rewriting systems for machine translation, and in the mid-1970s he described metamorphosis grammars, grammar rules with arguments that compile into logic. In 1980 Fernando Pereira and David H. D. Warren published "Definite clause grammars for language analysis", which gave DCGs their name and their now-standard form, and compared them favourably with the augmented transition networks then popular in language research. The two then built CHAT-80, a system that answered English questions about world geography, such as which countries border a given sea, by translating them into Prolog queries over a database of facts, and it became one of the best-known demonstrations of Prolog in natural-language processing.
Mainstream natural-language processing has since moved to statistical methods and, today, to neural networks trained on vast amounts of text, which handle the ambiguity and variety of real language far better than hand-written grammars. Grammar-based approaches remain in use where precision and explanation matter, such as controlled languages, grammar checking for specific domains and teaching linguistics. And DCGs remain an excellent tool for what most programmers actually parse: formats, commands and small languages. SWI-Prolog itself uses DCGs throughout its libraries, for instance to parse HTTP headers and to generate HTML with html//1 in its web framework.
Common misconceptions
Misconception
"DCGs are only for natural language." They describe any sequence: text in any format, tokens, or lists of anything at all. Some Prolog programmers use them to describe ordinary lists, because the hidden list arguments save writing them by hand.
Misconception
"A grammar rule can be left-recursive, as in the textbooks." In Prolog, a --> a, b. loops forever, because Prolog parses top-down and left to right. Rewrite left recursion as a first item followed by a loop with an accumulator, as expr_rest//2 does. (Tabling, in lesson 7, can also tame left recursion.)
Misconception
"phrase(g, L) succeeds if L starts with a g." phrase/2 requires the whole list to be consumed. To allow leftovers, use phrase/3 and look at the rest.
Misconception
"noun(N) in a grammar is the predicate noun/1." It is noun/3, with two hidden arguments for the input and the remainder. Call nonterminals through phrase/2,3, not directly, and write them as noun//1 in documentation.
Misconception
"Strings work as terminals everywhere." A double-quoted literal means a list of codes only inside a grammar body. To run a grammar on a string, convert it first with string_codes/2 (or string_chars/2, if your grammar uses one-character atoms).
Exercises
Try each question before opening the hints. Every answer about program output was checked by running the program with SWI-Prolog 10.1.
2. Grammars and parsing
CoreComputationalAdd one rule, noun --> [song]., to the lesson's first grammar. How many sentences does aggregate_all(count, phrase(sentence, _), N) count now?
3. Grammars and parsing
CoreComputationalWith the lesson's agreement grammar (the one with word/3 facts), which of these have a parse? Choose all that apply.
4. Grammars and parsing
CoreComputationalUsing the lesson's arithmetic parser, what value does calc("12 / 2 / 3") print after the =?
5. Grammars and parsing
Warm-upComputationalUsing the lesson's arithmetic parser, what value does calc("2 * 3 + 4 * 5") print after the =?
6. Grammars and parsing
CoreHumanWhy does the rule expr(L - R) --> expr(L), "-", term(R). (placed first) make phrase(expr(E), Codes) run forever?
7. Grammars and parsing
Warm-upComputationalUsing the lesson's robot program, what does run("east 4, north 6, west 1") print?
8. Grammars and parsing
StretchComputationalUsing the lesson's robot program, run("north 2, east 5 pause") reports stopped at column N: pause. What is N?
Further reading and resources
- SWI-Prolog manual, DCG grammar rulesThe notation, phrase/2 and phrase/3, and how rules are translated.
- SWI-Prolog manual, library(dcg/basics)Ready-made nonterminals for blanks, digits, numbers and strings.
- SWI-Prolog manual, library(pio)phrase_from_file/2, for running a grammar over a file without reading it all into memory.
- Definite clause grammar (Wikipedia)The history of DCGs, from Colmerauer's metamorphosis grammars to Pereira and Warren's 1980 paper.
- The Power of Prolog · Markus TriskaHas a chapter on DCGs, including their use for describing lists in general, not only text.