next up previous contents
Next: Automata Theory in XSB Up: Grammars Previous: Linear Parsing of LL(k)

Parsing of Context Sensitive Grammars

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.
next up previous contents
Next: Automata Theory in XSB Up: Grammars Previous: Linear Parsing of LL(k)
David S. Warren
1999-07-31