Subject: Re: parsing using difference lists

From: "Richard A. O'Keefe" <[email-masked]>
Date: Wed, 22 Nov 2000 14:22:21 +1300 (NZDT)

How exactly do you do parsing using difference lists.

You Read The Fine Textbook.

To start with, there is no such animal as a difference list.
There isn't a special kind of list called a difference list.
What we _do_ have is a special kind of difference called a 
list difference, that is, L1 \ L2 where L1 and L2 are both
lists and L2 is a tail of L1.

More precisely,

    L1, L2 are the components of a list difference
    if and only if they are (or will be) lists and
    there is (or will be) a list L3 such that
    append(L3, L2, L1).  In this case, L3 is the
    difference of the lists L1 and L2.

Read where your textbook describes Definite Clause Grammars.
A non-terminal is construed as a relation between the components
of a list difference, describing the structure of the difference
between those components.

	How would you parse this
	BNF grammar in prolog using difference lists:
	
You don't parse *grammars*, you parse *sentences* according to a grammar.
I suspect that what you mean is "how would you express this grammar in
Prolog" or "how would you write a parser for this grammar in Prolog."
Sloppy use of words leads to sloppy thinking which leads to sloppy
programs which leads to misery for other people.

If you have a predicate which mentions successive positions in a list,
it is conventional (the Pereira convention) to call them L0, L1, L2, ... L
where L0 is the initial position, L the final position, and positions are
numbered according to their spatial order.  Similarly, a succession of
states would be S0, S1, S2, ... S.  The convention applies to the numeric
suffixes; the alphabetic prefix should be whatever makes the most sense.
For grammars, the usual alphabetic prefix is S.

	<expn> ::= <name> | 
	       ::= the <reln> of <expn> | 
	       ::= <expn> poss <reln> 
	<reln> ::= mother | father | sister | brother | son | daughter
	
This is badly punctuated; one should never have the ::= following a |.

expn(S0, S) :- name(S0, S).
expn(S0, S) :- word(the, S0, S1), reln(S1, S2), word(of, S2, S3), expn(S3, S).
expn(S0, S) :- expn(S0, S1), word(poss, S1, S2), reln(S2, S).

reln(S0, S) :- word(mother, S0, S).
reln(S0, S) :- word(father, S0, S).
reln(S0, S) :- word(sister, S0, S).
reln(S0, S) :- word(brother, S0, S).
reln(S0, S) :- word(son, S0, S).
reln(S0, S) :- word(daughter, S0, S).

word(W, [W|S], S).

This won't quite work, because name/2 is already a built-in predicate which
means something quite different, so let's use a Latin word instead:

expn(S0, S) :- nomen(S0, S).
...

Prolog has a special notation for predicates of this form.
One would write, for example,

expn  --> nomen | [the], reln, [of], expn | expn, [poss], expn.
reln  --> [mother] | [father] | [sister] | [brother] | [son] | [daughter].
nomen --> [jack] | [jill].

However, there is a reason why you might not want to use either of these
formulations.  That is that the grammar is LEFT RECURSIVE.  A grammar is
left recursive if there is a sequence of rules such that
	A0 --> A1, ...
	A1 --> A2, ...
	...
	An --> A0, ...
Here there is a left recursion involving expn//0.
Suppose we try parsing
	expn([my,brother,poss,daughter], []).
The first rule for expn//0 does not match, because 'my' is not a name.
The second rule for expn//0 does not match, because 'my' is not 'the'.
So the third clause will be tried, and it will call expn//0 again with
the initial position in the list unchanged, which will soon lead to
just such another call, and it will not fail.

What we have to do is to introduce a DEPTH BOUND so that left recursion
won't get us into too much trouble.  So instead of passing two arguments,
saying where the parser is to start (S0) and where it ended up (S), we'll
also pass a depth bound pair (D0, D). The depth bound will not be a
number, it will be the list to be parsed.  In this case it's easy,
because each rule consumes at least one terminal symbol.  Each clause
will decrease the depth bound by the number of terminal symbols it
wants.  (There is a better way to do this, but this will serve here.)

expn(S) :-
    expn(S, _, S, []).

expn(D0, D, S0, S) :-
    nomen(D0, D, S0, S).
expn([_,_|D0], D, [the|S0], S) :-
    reln(D0, D1, S0, [of|S1]),
    expn(D1, D, S1, S).
expn([_|D0], D, S0, S) :-
    expn(D0, D1, S0, [poss|S1]),
    expn(D1, D, S1, S).

reln([_|D], D, [W|S], S) :-
    ( W = mother ; W = sister  ; W = daughter
    ; W = father ; W = brother ; W = son
    ).

nomen([_|D], D, [W|S], S) :-
    ( W = jack ; W = jill ).

I've tested this last version of the code.  It can do fun things like

?- length(L, 12), expn(L).
L = [the,mother,of,the,mother,of,the,mother,of,jack,poss,jack]

Of course, this now points up that it's a rather strange grammar in the
first place, but that's not Prolog's fault.