Go backward to Interpreters
Go up to Top
Go forward to Generate and Test

Natural Language Analysis

  • Grammar rules
  • Context-free grammar rules
  • A simple context-free grammar
  • Context-free grammar rules expressed in Prolog
  • Difference lists
  • Definite-clause grammar rules
  • The language anbncn
  • Recall first the language anbn
  • anbncn
  • Nondeterminism
  • example: finite state automata
  • example
  • Prolog interpreter (section 17.1 from The Art of Prolog)
  • DFA example
  • NFA example

    • Logic programming languages such as Prolog have a special connection to natural language analysis. Early researchers in the logic programming field were motivated by the desire to process natural language. Logic programming languages such as Prolog allow grammars for natural language to be expressed in a very simple and natural way while the underlying inference engine allows us to use the grammar for both parsing and generation. Viewed declaratively a grammar for some language L is a static characterization of membership in L. Viewed procedurally, a grammar for some language L is a program for either parsing or generating strings in L.

    Grammar rules

    Languages and the grammars which characterize them can be classified according to their expressive power. The Chomsky hierarchy consists of four classes of languages/grammars in a subset relationship.
    type 0
    Unrestricted
    type 1
    Context-sensitive
    ?
    Mildly context-sensitive

    The following grammar formalisms have the same weak generative capacity:

    type 2
    Context-free
    type 3
    Regular/finite state
    Although it has been argued that context-free grammars are not powerful enough to describe natural languages, we will start our exploration of natural language analysis with context-free grammar rules.

    Context-free grammar rules

    The general format for context-free grammar rules is,
    alpha -> beta1 ...betan
    alpha is a non-terminal, and the betai's are either terminals or non-terminals. Such a rule is translated into Prolog as,
    alpha(P0,Pn) :- beta(P0,P1),
    .
    .
    .
    beta(Pn-1,Pn).

    A simple context-free grammar

    Consider the sentence
    1. The cat chased the rat.
    Suppose we are told that the following is a plausible analysis of this sentence. 
    
                              s
                             / \
                           /     \
                         /         \
                       np           vp
                      /  \         /  \
                     d    n       v    np
                     |    |       |   /  \
                    the  cat chased  d    n
                                     |    |
                                    the  rat
    We can write a grammar to accept the string of words "the cat chased the rat" with the given analysis as follows: 
    s --> np vp
np --> d n
vp --> v np
d --> the
n --> cat
n --> rat
v --> chased

    Context-free grammar rules expressed in Prolog

    Most (if not all) Prolog systems "understand" a particular syntax for expressing grammar rules. For example, the above grammar can be expressed as follows in Prolog. 
    s --> np, vp.
np --> d, n.
vp --> v, np.
d --> [the].
n --> [cat].
n --> [rat].
v --> [chased].
    These grammar clauses are translated into Prolog clauses automatically. How this is done is explained in the following subsections.

    Difference lists

    First we need to talk about difference lists. Up until now we have been representing lists using the standard Prolog notation [Head|Tail]. We might, however, think of a list as the difference of any one of a number of pairs of lists. For example, the list in (2) can be represented as a difference of lists as in (a) - (e). The form shown in (e) is the most general.

    Why are difference lists useful? Consider append/3: 

    append([],Ys,Ys).
append([X|Xs],Ys,[X|Zs]) :- append(Xs,Ys,Zs).
    append/3 takes time linear in the size of its first argument to append two lists. With difference lists we can write a version of append which appends two difference lists in constant time. 
    append_dl(Xs-Ys,Ys-Zs,Xs-Zs).
    How can this work? Let's first convince ourselves that it does, in fact, work. Here's a query posed to Prolog: 
    | ?- append_dl([1,2,3|As]-As,[4,5,6|Bs]-Bs,Result).

As = [4,5,6|Bs],
Result = [1,2,3,4,5,6|Bs]-Bs ? ;

no
    The value of Result is the list [1,2,3,4,5,6] expressed as a general difference list. This is clearly the right answer. How was this answer computed? To answer this question, we have to get our hands dirty and do some unification!

    Stack Substitution (Z) Comment

    append_dl([1,2,3|As]-As,[4,5,6|Bs]-Bs,Result) =

    		{} Inital state.
    append_dl(Xs-Ys,Ys-Zs,Xs-Zs)
    [1,2,3|As]-As = Xs-Ys, [4,5,6|Bs]-Bs = Ys-Zs, {} Pop equation from stack.
    Result = Xs-Zs Add 3 equations to stack.
    [1,2,3|As]=Xs, As=Ys, {} Pop [1,2,3|As]-As = Xs-Ys from stack.
    [4,5,6|Bs]-Bs = Ys-Zs, Result = Xs-Zs Same functor "-" and arity, 2.
    Add two equations to stack.
    As=Ys, [4,5,6|Bs]-Bs = Ys-Zs, { Xs=[1,2,3|As] } Pop [1,2,3|As]=Xs from stack.
    Result = [1,2,3|As]-Zs Replace all occurances of Xs by [1,2,3|As] in the stack
    Add Xs=[1,2,3|As] to Z.
    [4,5,6|Bs]-Bs = Ys-Zs, {Xs=[1,2,3|As], Pop As=Ys from stack.
    Result = [1,2,3|Ys]-Zs. As=Ys} Replace all occurances of As by Ys in the stack.
    Add As=Xs to Z.
    [4,5,6|Bs] = Ys, Bs = Zs, {Xs=[1,2,3|As], Pop [4,5,6|Bs]-Bs = Ys-Zs from stack.
    Result = [1,2,3|Ys]-Zs As=Ys} Same functor "-" and arity, 2.
    Add two equations to stack.
    Bs = Zs, Result = [1,2,3|[4,5,6|Bs]]-Zs {Xs=[1,2,3|As], Pop [4,5,6|Bs] = Ys from stack.
    As=Ys, Replace all occurances of Ys by [4,5,6|Bs] in the stack.
    Ys=[4,5,6|Bs]} Add Ys=[4,5,6|Bs] to Z.
    Result = [1,2,3|[4,5,6|Zs]]-Zs {Xs=[1,2,3|As], Pop Bs = Zs from stack.
    As=Ys, Replace all occurances of Bs by Zs in the stack.
    Ys=[4,5,6|Bs], Add Bs=Zs to Z.
    Bs=Zs}
    (empty) {Xs=[1,2,3|As], Pop Result = [1,2,3|[4,5,6|Zs]]-Zs from stack.
    As=Ys, Replace all occurances of Result by [1,2,3|[4,5,6|Zs]]-Zs in the stack.
    Ys=[4,5,6|Bs], Add Result=[1,2,3|[4,5,6|Zs]]-Zs to Z.
    Bs=Zs,
    Result=[1,2,3|[4,5,6|Zs]]-Zs}

    We're done! The most general unifier is {Xs=[1,2,3|As], As=Ys, Ys=[4,5,6|Bs], Bs=Zs, Result=[1,2,3|[4,5,6|Zs]]-Zs}.

    To find the common instance, apply mgu to either term:

    Definite-clause grammar rules

    On the assignment you are asked to extend a given grammar in a variety of ways. In order to do this, you need to add arguments to your grammar rules. When you do this, you increase the expressive power of the grammar formalism, and we call the resulting rules definite clause grammar (DCG) rules.

    The general format for DCG rules is,

    alpha(args) -> beta1(args) ...betan(args)
    alpha is a non-terminal, and the betai's are either terminals or non-terminals. Such a rule is translated into Prolog as,
    alpha(Arg1,...,Argm,P0,Pn) :- beta1(Argi1,1,...,Argi1,k1,P0,P1),
    .
    .
    .
    betan(Argin,1,...,Argin,kn,Pn-1,Pn).

    DCG rules can be extended by adding Prolog goals to them in braces '{' and '}'.

    The language anbncn

    Recall first the language anbn

    Context free grammar which generates anbn. 
    ab --> [a,b].
ab --> [a], ab, [b].

    Here's another grammar (non-context free) which generates this language as well. 

    s --> a(N), b(N).

a(1) --> [a].
a(N) --> [a], a(M), {N is M+1}.

b(1) --> [b].
b(N) --> {N>1, M is N-1}, [b], b(M).

    anbncn

    The language anbncn is not a context-free language. It belongs to the class on context-senstive languages. Here's one grammar which generates this language. 
    abc --> [a], abc, [b], c1.
abc --> [].
c1, [b] --> [b], c1.          % not a context free rule!
c1 --> [c].

    Here's a grammar in the style of the second grammar for anbn which generates anbncn. 

    s --> a(N), b(N), c(N).

a(1) --> [a].
a(N) --> [a], a(M), {N is M+1}.

b(1) --> [b].
b(N) --> {N>1, M is N-1}, [b], b(M).

c(1) --> [c].
c(N) --> {N>1, M is N-1}, [c], c(M).

    Nondeterminism

    We saw an example of nondeterminism when we looked at the abstract interpreter for logic programs. One unspecified choice of the interpreter was which goal from the resolvent to consider next. Another was which rule from the definition of the appropriate predicate to use in the reduction of a goal. In the examples we looked at we always made the "correct" choice. In a deterministic computation there is never more than one choice. In a nondeterministic computation there can be many possible choices. The computation succeeds if there is at least one computation set of choices which yields a solution.

    Prolog simulates nondeterminism through depth-first search with backtracking.

    The generate-and-test approach to problem solving is really just an example of nondeterministic thinking. The logic program for the n-queens problem specifies a nondeterministic computation. Prolog simulates nondeterminism by searching for a solution, backtracking where necessary. Prolog doesn't know which computation path will lead to a solution, so it tries all of them until it finds one which works.

    If the choice made at a choice point is irrelevant, then it is called don't care nondeterminism. Otherwise, it is called don't know nondeterminism.

    Don't care nondeterminism: min/3 with non-mutually exclusive clauses. This is redundancy, and is to be avoided is possible.

    example: finite state automata

    The smallest class of languages in the Chomsky hierarchy is the class of regular languages. Regular languages (sometimes called regular sets) can be characterized in a number of different ways,

    example

    DFA1 = ({q0,q1,q2}, {a,b}, {delta(q0,a)=q2, delta(q0,b)=q1, delta(q2,b)=q0}, q0, {q1}). Language accepted is (ab)*b = {b,abb,ababb,abababb,...}.

    Prolog interpreter (section 17.1 from The Art of Prolog)

    accept(Xs) :- initial(Q), accept(Xs,Q).
accept([],Q) :- final(Q).
accept([X|Xs],Q) :- delta(Q,X,NewQ), accept(Xs,NewQ).

    DFA example

    initial(q0).
final(q1).

delta(q0,b,q1).
delta(q0,a,q2).
delta(q2,b,q0).

    Here's how it works ...

    | ?- accept(Xs).

Xs = [b] ? ;

Xs = [a,b,b] ? ;

Xs = [a,b,a,b,b] ? ;

Xs = [a,b,a,b,a,b,b] ?

yes
| ?- accept([a,b,a,b,a,b,b]).

yes
| ?- accept([a,b,a,b,a,b]).

no

    NFA example

    NFA1 = ({q0,q1,q2}, {a,b}, {delta(q0,a)=q2, delta(q0,b)=q1, delta(q2,b)=q0, delta(q2,b)=q1}, q0, {q1}). Language accepted is (ab)*(ab  | b) = {b,ab,abb,abab,ababb,ababab,abababb,...}. 
    initial(q0).
final(q1).

delta(q0,b,q1).
delta(q0,a,q2).
delta(q2,b,q0).
delta(q2,b,q1).

    Nondeterminism: the NFA will accept a string if there is a path which accepts the string. Prolog simulates this nondeterminism using depth-first search and backtracking.

    Here's how it works ...

    | ?- accept([a,b,a,b,a,b,b]).

yes
| ?- accept([a,b,a,b,a,b]).

yes
| ?- accept([a,b,a]).

no
    horsch@cs.ubc.ca

    Go backward to Interpreters
    Go up to Top
    Go forward to Generate and Test