COMP 481, Prolog, Ch 7–8
Ch 7: Definite-Clause Grammars
Copyright By PowCoder代写 加微信 powcoder
Ch 8: More Definite-Clause Grammars
University of the Fraser Valley
COMP 481: Functional and Logic Programming
• Chapter 7
• Context-Free Grammars
• CFG Recognition Using Append
• CFG Recognition Using Difference Lists
• Definite Clause Grammars
• Adding Recursive Rules
• A DCG for a Simple Language
• Chapter 8
• Context-Free Grammars with Features
• Building Parse Trees
• Separating Rules and Lexicon
— Chapter 7 —
— Context-Free Grammars —
History of
Development
was one researcher to spearhead
development of Prolog as a programming language.
• Alain actually specialized in natural language processing
• they were among some of the first
computer science researchers in France
• NLP and theorem provers were part of the
traditional approach to artificial intelligence
• they focused on logic, context-free grammars, and semantics
• their researchers realized that going against the pure logical theorem-
prover approaches, they could create a full programming language
The study of formal languages (not natural languages)
lays the foundation of computer science.
• at UFV, the course that studies formal languages is called
Language, Computation, and Machines (COMP 382)
• one of the mid-tier machines is called a push-down automata
equivalent to context-free grammars
• these are still very powerful, and useful for designing compilers
• the main idea is that each token in the grammar
does not change its meaning (context-free)
• part of the design for its machine uses a stack
• tokens can be placed on the stack and “processed“
We will be concerned in this chapter with a special type called
Definite Clause Grammars (DCGs).
Context-Free
First, we briefly review the definition of a
context-free grammar (CFG) by way of example.
The rules define a specific context-free grammar that is
only capable of generating kinds of words (or patterns).
s -> np vp
s -> np vp
np -> det n
vp -> v np
det -> the
n -> woman
v -> shoots
• each row of the above gives a grammar rule
• also called productions
• the variables `s`, `np`, `vp`, `det`, `n`, `v` are
examples of non-terminal symbols
• the values `a`, `the`, `woman`, `man`, `shoots`
are examples of terminal symbols
CFG Details
• can only begin to generate words with the start symbol
• typically called `s`
• no other symbol can be used to begin
• non-terminal symbols are meant to
eventually be replaced with terminal symbols
• we replace each non-terminal with a choice
of possible right-hand-side (of `->`) strings of symbols
• many choices on right-hand side can be listed using Sheffer stroke:
`vp -> v np | v`
Derivations
• we can only replace one non-terminal symbol at a time, in sequence
• we write a replacement using a right arrow with two lines, `=>`
• does not matter which non-terminal symbol we choose to replace first
• the replacement is the whole right side of a rule (between | | strokes),
matching with the non-terminal on its left
• stop when no more non-terminal symbols are in the generated string
• such a process of a finite number of replacements that finishes with
only terminal symbols is called a derivation
• the set of all derivations is called the language of the grammar
Deriving a
For example:
s => np vp
=> det n vp
=> a man vp
=> a man v
=> a man shoots
As you can see, a grammar does not necessarily have to
derive only single words, but can derive whole sentences.
• the textbook will use terminology such as lexical items, or terminals,
or just “words,” which all means the same thing
• the textbook also says that replacement symbols
(on the right of the rule)
are licensed by their non-terminal symbols
(on the left of the rule)
• this wording is inherited from linguistics
What about strings that belong to a grammar’s language?
• if we find a derivation for the string, then it belongs to the language
• if no such derivation exists,
then the string does not belong to the language
Deriving all words in a language is a difficult question to
answer with only a grammar’s rules.
• it is much easier to check with an equivalent pushdown automata
• textbook calls a pushdown automata machine a recognizer program
• fortunately, Prolog is designed very much like a pushdown automata
(that uses a stack)
• another way to visualize whether a string belongs to a language is to
represent a derivation using a parse tree:
Parse Tree
• the root of the tree has the start symbol `s`
• each rule that replaces a non-terminal lists
its replacement symbols each as separate child nodes
• the leaves of the parse tree give the string
• all internal nodes have non-terminal symbols
• (not all strings necessarily have unique parse trees)
• a parse-tree/derivation shows that a string is grammatical
(the string belongs to the grammar’s language)
An example of a string that is not grammatical for this
language would be “woman a woman man a shoots”.
• there is no parse tree (nor derivation)
using the grammar’s rules that generates this string
But, more often we care more about why a string is
grammatical, not just that it is or is not.
• a parse tree shows the structure of why a string is grammatical
• this gives us power within other applications for possibly
interpreting the structure semantically (what the string means)
A parser is a program that builds a parse tree for us.
One final note is to be sure you do not try to program a
parser for an entire natural language.
• it is not possible to have a CFG that would generate every possible
sentence in written/spoken communication
• since we could create new words, or even new sentence structures
• the meaning of words changes and the rules for parsing different
meanings follow different grammatical rules depending on context
• hence, non-context free languages exist
— CFG Recognition Using Append —
and Parsers
So given a CFG, how do we write a recognizer and then a
parser for it?
• Prolog has difference lists to help with creating recognizers
• Prolog has definite clause grammars to help with creating parsers
In our Prolog programs:
• we will represent strings as lists
• where each element is a symbol from the grammar
• we start with a naive (and inefficient) implementation
Starting with `s`, we can speak of the result as an `s` list
• the rule `s -> np vp` implies that
• an `s` list
• consists of an `np` list
• concatenated with a `vp` list
• it should be pretty easy to turn these kinds of rules into Prolog
For the example the grammar we have been using:
s(Z) :- np(X), vp(Y), append(X, Y, Z).
np(Z) :- det(X), n(Y), append(X, Y, Z).
vp(Z) :- v(X), np(Y), append(X, Y, Z).
vp(Z) :- v(Z).
det([the]).
n([woman]).
v([shoots]).
Membership
Derivation
Save it as a file and load it in an interactive swipl session.
We can make queries for recognition in the language:
?- s([a,woman,shoots,a,man]).
We can also use the grammar rules in a knowledge base to
produce grammatical strings.
(see next slide)
Derivations
X = [the, woman, shoots, the, woman] ;
X = [the, woman, shoots, the, man] ;
X = [the, woman, shoots, a, woman] ;
X = [the, woman, shoots, a, man] ;
X = [the, woman, shoots] ;
X = [the, man, shoots, the, woman] ;
X = [the, man, shoots, the, man] ;
X = [the, man, shoots, a, woman] ;
X = [the, man, shoots, a, man] ;
X = [the, man, shoots] ;
X = [a, woman, shoots, the, woman] ;
X = [a, woman, shoots, the, man] ;
X = [a, woman, shoots, a, woman] ;
X = [a, woman, shoots, a, man] ;
X = [a, woman, shoots] ;
X = [a, man, shoots, the, woman] ;
X = [a, man, shoots, the, man] ;
X = [a, man, shoots, a, woman] ;
X = [a, man, shoots, a, man] ;
X = [a, man, shoots].
The textbook rightly says the grammar can generate a
language of 20 strings.
• stay leery of doing a similar query for other grammars, as a set of
rules can easily generate an infinite number of strings
We can also pose queries for specific parts of the language
encoded with the other non-terminals:
X = [the, woman] ;
X = [the, man] ;
X = [a, woman] ;
X = [a, man].
A chart for the common grammatical meanings:
non-terminal meaning
np noun phrase
vp verb phrase
det determiner
Considering how a grammatical string like
“the man shoots”
is recognized with query `s([the, man, shoots])`:
• Prolog will first search through noun phrases and verb phrases to
concatenate until it successfully does so to derive the string
• e.g.: it might try np “the woman” and the vp “shoots the woman”
• these do not concatenate to become the string “the man shoots”
• Prolog would backtrack and try other noun phrase
and verb phrase combinations, until successful
• try a trace!
Inefficient Rule
Implementation
We could try to `append` before searching for noun and
verb phrases:
s(Z) :- append(X, Y, Z), np(X), vp(Y).
np(Z) :- append(X, Y, Z), det(X), n(Y).
vp(Z) :- append(X, Y, Z), v(X), np(Y).
However, the problem is that we are then calling `append`
with two uninstantiated variables `X` and `Y`.
• we saw in the last chapter how inefficient this was
• not a problem for a small grammar,
but very much a problem for a slightly larger one
— CFG Recognition Using Difference Lists —
Difference
We consider a few examples of difference lists without
going into any detail on their theory.
• instead of a regular list, say `[a, woman, shoots, a, man]`,
we would use two lists:
• `[a, woman, shoots, a, man]` and `[]`
• we expect to consume the left list as input
• we expect to ignore any symbols in the right list
• this example then represents the string “a woman shoots a man”
• another example might be
`[woman, shoots, man, bippity, boppity]` and `[bippity, boppity]`
• this would represent the same string “woman shoots man”
• altogether, we are interested in the string that is the difference
between the two lists
Difference
We can make use of difference lists to avoid `append` completely:
s(X, Z) :- np(X, Y), vp(Y, Z).
np(X, Z) :- det(X, Y), n(Y, Z).
vp(X, Z) :- v(X, Y), np(Y, Z).
vp(X, Z) :- v(X, Z).
det([the|W], W).
det([a|W], W).
n([woman|W], W).
n([man|W], W).
v([shoots|W], W).
Description
• query `s([the,man,shoots],[])` trace is much easier to follow
• note that in recognizing the string, the first rule
`vp(X, Z) :- v(X, Y), np(Y, Z)`
checks that the verb `shoots` is followed by a noun phrase
(which it is not)
• and outputs `Fail`
• then checks the rule `vp(X, Z) :- v(X, Z)`, which does hold
• notice each pair of terms in the rules involving multiple symbols:
• have the first term with symbols left which it ignored `Y`
(in many cases empty `[]`)
• will try to consume the symbols `Y` in the second term’s search
• again, `Z` is empty `[]` to start our query
(but may not be in subsequent subgoal searches)
Trace with
Difference
[trace] 13 ?- s([the,man,shoots],[]).
Call: (10) s([the, man, shoots], []) ? creep
Call: (11) np([the, man, shoots], _9104) ? creep
Call: (12) det([the, man, shoots], _9860) ? creep
Exit: (12) det([the, man, shoots], [man, shoots]) ? creep
Call: (12) n([man, shoots], _9104) ? creep
Exit: (12) n([man, shoots], [shoots]) ? creep
Exit: (11) np([the, man, shoots], [shoots]) ? creep
Call: (11) vp([shoots], []) ? creep
Call: (12) v([shoots], _14386) ? creep
Exit: (12) v([shoots], []) ? creep
Call: (12) np([], []) ? creep
Call: (13) det([], _16650) ? creep
Fail: (13) det([], _16650) ? creep
Fail: (12) np([], []) ? creep
Redo: (11) vp([shoots], []) ? creep
Call: (12) v([shoots], []) ? creep
Exit: (12) v([shoots], []) ? creep
Exit: (11) vp([shoots], []) ? creep
Exit: (10) s([the, man, shoots], []) ? creep
Generating
Difference
We can, as before, generate all sentences with the query
`s(X,[]).` and this time it will be much more efficient.
• this recognizer version is difficult to understand how search succeeds
• fortunately, there is a way to have the simplicity of `append`
with the efficiency of difference lists
— Definite Clause Grammars —
Use of DCGs nicely hide the functionality of difference lists.
• we will see with a first simple example:
s –> np, vp.
np –> det, n.
vp –> v, np.
det –> [the].
det –> [a].
n –> [woman].
n –> [man].
v –> [shoots].
Functionality
We also make queries in the exact same way as we did with
our difference list implementation:
?- s([the,man,shoots],[]).
The notation for encoding a grammar with definite clauses
encodes in Prolog exactly the same as using difference lists.
• the documentation is found under the “Operators” section
(at the bottom of the page):
• https://www.swi-prolog.org/pldoc/man?section=opsummary
• if you ask query `listing(s)` you will get back the expanded predicate
?- listing(s).
s(A, B) :-
• this was for the DCG rule `s –> np, vp.`
• similar expansions had been done to the other DCG rules we wrote
https://www.swi-prolog.org/pldoc/man?section=opsummary
Difference
The textbook mentions:
• a variation on the expansion for the rules involving terminal symbols,
• but the newer version of SWI-Prolog does not alter its expansion
from the rules we wrote for the difference list version
• e.g.: `det([the|A], A)`
— Adding Recursive Rules —
The simple grammar we have only derives 20 sentences.
• however, keep in mind it is easy to create grammars that derive an
infinite number of strings
We add more rules in our previous grammar with rules that
involve recursive replacement of non-terminal symbols:
s –> s, conj, s.
conj –> [and].
conj –> [or].
conj –> [but].
First, let us try adding the first extra rule
• before the rule `s –> np, vp.`
• put the `conj` rules just after the rule `s –> np, vp.`,
otherwise, there is a warning message
• and then query `s([a, woman, shoots],[])`
Note that the expansion for the rule `s –> s, conj, s.`
has the form:
s(A, B) :-
conj(C, D),
• notice that the difference lists pass from left to right their ignored
symbols into the next term’s consume list
Now make a query like we had done before:
?- s([the, woman, shoots], []).
ERROR: Stack limit (1.0Gb) exceeded
• Prolog gets into an infinite loop!
The reason is that the recursive rule is applied repeatedly
without ever a chance to apply the rule `s –> np, vp.`
• so, let’s move the recursive rule
`s –> s, conj, s.` after `s –> np, vp.`
We can see it now handles the same query just fine, but if
we press `;` there is another infinite loop:
?- s([the, woman, shoots], []).
ERROR: Stack limit (1.0Gb) exceeded
• this time, it continues to apply the recursive rule
`s –> s, conj, s.`, since `s –> np, vp.` was not satisfied
• we simply cannot rely on DCG notation alone for recursive rules…
We need a new non-terminal symbol `simple_s` to handle
only going into recursion when absolutely necessary:
s –> simple_s.
s –> simple_s, conj, s.
simple_s –> np, vp.
?- s(X, []).
X = [the, woman, shoots, the, woman] ;
X = [the, woman, shoots, the, man] ;
X = [the, woman, shoots, a, woman] ;
X = [the, woman, shoots, a, man] ;
X = [the, woman, shoots] ;
X = [the, man, shoots, the, woman] ;
X = [the, man, shoots, the, man] ;
X = [the, man, shoots, a, woman] ;
X = [the, man, shoots, a, man] ;
…and so on
Make sure you can understand why Prolog will not enter an
infinite loop with the following edit of our grammar:
s –> simple_s.
s –> simple_s, conj, s.
simple_s –> np, vp.
• only get a `np, vp` concatenation through one use of `simple_s`
• `simple_s` is the only way to derive `np, vp`
• any recursion applied once derives `simple_s` so that the next rule
searched by Prolog must be the last rule `simple_s –> np, vp.`
— A DCG for a Simple Language —
A common language when computer science students are
first introduced to CFGs and pushdown automata:
𝐿𝐿 = 𝑎𝑎𝑛𝑛𝑏𝑏𝑛𝑛 | 𝑛𝑛 ∈ 𝑵𝑵 .
• note that in the above, the natural numbers 𝑵𝑵 also contains zero
• the string 𝑎𝑎0𝑏𝑏0 = 𝜀𝜀, which denotes the
“empty string” that contains no symbols
So, we have 𝐿𝐿 = 𝜀𝜀,𝑎𝑎𝑏𝑏,𝑎𝑎𝑎𝑎𝑏𝑏𝑏𝑏,𝑎𝑎𝑎𝑎𝑎𝑎𝑏𝑏𝑏𝑏𝑏𝑏,𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏, … .
The only reason language 𝐿𝐿 is introduced is because it is
the easiest such language to show that it cannot be
generated by a regular expression.
Trivial for
• it shows the limitations of regular expressions and DFAs
• creating a grammar that generates 𝐿𝐿 with DCG is trivial
s –> []; l, s, r.
l –> [a].
r –> [b].
• note that the textbook give the rules as all separate, but you can use
a semicolon to combine right-hand side symbol choices
• the `l` stands for the left symbol we want to generate
(but you could have named it whatever you wanted)
• the `r` obviously stands for the right
Trivial for
Then we can query to check if our grammar generates the
same strings as in our description:
?- s(X, []).
X = [a, b] ;
X = [a, a, b, b] ;
X = [a, a, a, b, b, b] ;
X = [a, a, a, a, b, b, b, b] .
— Chapter 8 —
— Context-Free Grammars with Features —
We build up our main example CFG, but now with more
features in the derived language based on grammar.
• your usage of grammar every day
in natural language is very complex
• our study of it is actually much simpler,
only focusing on the rules in a logical way
• so, CFGs cannot fully describe our actual usage
in natural speaking, writing, etc.
• for this reason, it is a great place to begin writing programs
The grammar we have been using (without recursion):
s –> np, vp.
np –> det, n.
vp –> v, np.
det –> [the].
det –> [a].
n –> [woman].
n –> [man].
v –> [shoots].
What possible things can we add to this language not
already there?
• verb conjugation
• adjectives
• compound phrases
• punctuation
• modify categories, such as rules for converting nouns to verbs, etc.
• different sentence structures (change order of subject, object, etc.)
• interjections
We continue by adding something simple, like pronouns.
• rules for allowing words such as: he, she, him, her; should do
pro –> [he].
pro –> [she].
pro –> [him].
pro –> [her].
• we also know noun phrases can be pronouns
np –> pro.
Grammatical
w.r.t. Our CFG
Now what kinds of strings are grammatical?
?- s([she, shoots, him],[]).
?- s([a, woman, shoots, she],[]).
?- s([her, shoots, a, man],[]).
?- s([her, shoots, she],[]).
It is unlikely we know anyone in real life that communicates
• the rule we naturally know that is broken here is a disagreement of
subject and object usage
• “she” is only used in the position of a subject in a correct sentence
• “her” is only used in the position of an object in a correct sentence
More bizarre incorrect sentences, such as deriving “the she”, break our
understanding that determiners are never used with pronouns.
• well, we need to edit our ruleset…
Naïve Edit
First, a naive attempt by adding yet more rules to replace
the ones that were too liberal:
s –> np_subject, vp.
np_subject –> det, n.
np_object –> det, n.
np_subject —
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com