Another more powerful form of grammars is the class of context sensitive grammars. They contain rules that have strings on both the left-hand-side and the right-hand-side, as opposed to context-free rules which require a single symbol on the left-hand-side. A constraint on context sensitive rules is that the length of the string of the left-hand side is at least one, and is less than or equal to the length of the string on the right-hand side. (Without this constraint, one gets full Turing computability and the recognition problem is undecidable.) As a simple example, consider the following context sensitive grammar:
1. S --> aSBC
2. S --> aBC
3. CB --> BC
4. aB --> ab
5. bB --> bb
6. bC --> bc
7. cC --> cc
This grammar generates all strings consisting of a nonempty sequence
of a's followed by the same number of b's followed by the same number
of c's. Consider the following derivation:
S
aSBC rule 1
aaBCBC rule 2
aaBBCC rule 3
aabBCC rule 4
aabbCC rule 5
aabbcC rule 6
aabbcc rule 7
Even though in this simple example the rules fire in order, it's not
difficult to see that rule 3 will have to fire enough times to move
all the C's to the right over the B's, and then rules 4-7 will fire
enough times to turn all the nonterminals into terminals.
The question now is how to represent this in XSB. We can think of the
XSB DCG rules as running on a graph that starts as a linear chain
representing the input string. Then each DCG context-free rule tells
how we can add edges to that linear graph. For example, a DCG rule
a --> b,c. tells us that if there is an arc from node X to node
Y labeled by b and also an arc from node Y to node Z labeled by c,
then we should add an arc from node X to node Z labeled by a. So the
DCG rule in Prolog, a(S0,S) :- b(S0,S1),c(S1,S)., read
right-to-left, says explicitly and directly that if there is an arc
from S0 to S1 labeled b and an arc from S1 to S labeled c, then there
is an arc from S0 to S labeled by a. We can think of DCG rules as
rules that add labeled arcs to graphs. This is exactly the way that
chart-parsing is understood.
Now we can extend this way of understanding logic grammars to
context-sensitive rules. A context-sensitive rule, with say two
symbols on the left-hand-side, can be seen also as a graph-generating
rule, but in this case it must introduce a new node as well as new
arcs. So for example, a rule such as AB --> CD, when it sees
two adjacent edges labeled C and D, should introduce a new node and
connect it with the first node of the C-arc labeling it A, and also
connect it to the final node of the D-arc, labeling that new arc with
B. So we add two new XSB rules for a context sensitive rule such as
AB --> CD, as follows:
a(S0,p1(S0)) :- c(S0,S1), d(S1,S).
b(p1(S0),S) :- c(S0,S1), d(S1,S).
which explicitly add the arcs and nodes. We have to introduce a new
name for the new node. We choose to identify the new nodes by using a
functor symbol that uniquely determines the rule and left-hand
internal position, and pairing it with the name of the initial node in
the base arc. So in this case, p1 uniquely identifies the (only)
internal position in the left-hand-side of this rule. Other rules,
and positions, would have different functors to identify them
uniquely.
Now we can represent the context sensitive grammar above using the following XSB rules:
:- auto_table.
s(S0,S) :- word(S0,a,S1),s(S1,S2),b(S2,S3),c(S3,S).
s(S0,S) :- word(S0,a,S1),b(S1,S2),c(S2,S).
c(S0,p0(S0)) :- b(S0,S1),c(S1,_S).
b(p0(S0),S) :- b(S0,S1),c(S1,S).
word(S0,a,p1(S0)) :- word(S0,a,S1),word(S1,b,_S).
b(p1(S0),S) :- word(S0,a,S1),word(S1,b,S).
word(S0,b,p2(S0)) :- word(S0,b,S1),word(S1,b,_S).
b(p2(S0),S) :- word(S0,b,S1),word(S1,b,S).
word(S0,b,p3(S0)) :- word(S0,b,S1),word(S1,c,_S).
c(p3(S0),S) :- word(S0,b,S1),word(S1,c,S).
word(S0,c,p4(S0)) :- word(S0,c,S1),word(S1,c,_S).
c(p4(S0),S) :- word(S0,c,S1),word(S1,c,S).
% define word/3 using base word (separation necessary)
word(X,Y,Z) :- base_word(X,Y,Z).
% parse a string... assert words first, then call sentence symbol
parse(String) :-
abolish_all_tables,
retractall(base_word(_,_,_)),
assertWordList(String,0,Len),
s(0,Len).
% assert the list of words.
assertWordList([],N,N).
assertWordList([Sym|Syms],N,M) :-
N1 is N+1,
assert(base_word(N,Sym,N1)),
assertWordList(Syms,N1,M).
We can run this grammar to parse input strings as follows:
warren% xsb XSB Version 1.7.2 (7/10/97) [Sun, optimal mode] | ?- [csgram]. [csgram loaded] yes | ?- parse([a,a,b,b,c,c]). ++Warning: Removing incomplete tables... yes | ?- parse([a,a,a,b,b,c,c,c]). no | ?- parse([a,a,a,a,b,b,b,b,c,c,c,c]). ++Warning: Removing incomplete tables... yes | ?-
So now we have generalized DCG's to include processing of context-sensitive grammars and languages. The builtin DCG notation doesn't support context sensitive languages, but we can write the necessary rules directly as XSB rules, as we did above. It is interesting to note that the XSB rules we generate for a single context-sensitive rule all have the same body, and that the logical implications
p <- r & s.
q <- r & s.
are logically equivalent to the single implication:
p & q <- r & s.
So it would be very natural to extend the Prolog notation to support
``multi-headed'' rules, which would be compiled to a set of
``single-headed'', i.e., regular Prolog, rules. Were we to do this, we
could write the context-sensitive rule:
AB --> CD
as the single (multi-headed) XSB rule:
a(S0,p1(S0)), b(p1(S0),S) :- c(S0,S1), d(S1,S).
which looks very much like the original context sensitive rule. This
suggests how we might want to extend the DCG notation to support
context-sensitive rules through the support of multi-headed rules.