Chart Parser with a Manual Magic Set

The new forward chainer is a real gas. It is not yet that efficient, some indexing is still missing. But it is quite handy in exploring ideas. The screenshot shows an arithmetic grammar and its parsing via a chart parser. The chart parser is based on a modified version of the original grammar rules. Magic set predicates have been added and injected into the grammar rules. The result are less irrelevant chart elements.

We have conducted our experiment with the following grammar:

expr(C,N,M) :- expr(A,N,H), word(+,H,J), term(B,J,M), C is A+B.
expr(C,N,M) :- expr(A,N,H), word( - ,H,J), term(B,J,M), C is A - B.
expr(A,N,M) :- term(A,N,M).

term(C,N,M) :- term(A,N,H), word( * ,H,J), factor(B,J,M), C is A * B.
term(C,N,M) :- term(A,N,H), word(/,H,J), factor(B,J,M), C is A/B.
term(A,N,M) :- factor(A,N,M).

factor(A,N,M) :- word(A,N,M), integer(A).

Magic set predicates are also forward chaining rules but they model some backward chaining behaviour. Forward chaining can be viewed as "if-changed" rules whereas backward chaining can be viewed as "if-needed" rules. The magic set predicates model the "if-needed" of grammar predicates. We have defined the following magic set rules:

mterm(J) :- mexpr(N), expr( _ ,N,H), word(+,H,J).
mterm(J) :- mexpr(N), expr( _ ,N,H), word( - ,H,J).
mterm(N) :- mexpr(N).

The first two rules express that a term/3 is needed when a expr/3 was needed and and expr/3 was parsed followed by a word/3. These magic set rules are derived from the first two grammar rules for expr/3. The third rule expresses that a term/3 is needed when a expr/3 is needed. This magic set rule is derived from the third grammar rule for expr/3.

An automatic magic set algorithm might also derive the rules mexpr(N) :- mexpr(N) and mterm(N) :- mterm(N) from the left recursive occurence of the corresponding grammar predicates. But these rules would only produce unnecessary "if-needed" duplicates. So I didn't include these rules. We now need to add the magic set predicates to the original grammar. Just insert them in the front of trhe grammar rules:

expr(C,N,M) :- mexpr(N), expr(A,N,H),
word(+,H,J), term(B,J,M), C is A+B.
expr(C,N,M) :- mexpr(N), expr(A,N,H),
word( - ,H,J), term(B,J,M), C is A - B.
expr(A,N,M) :- mexpr(N), term(A,N,M).

term(C,N,M) :- mterm(N), term(A,N,H),
word( * ,H,J), factor(B,J,M), C is A * B.
term(C,N,M) :- mterm(N), term(A,N,H),
word(/,H,J), factor(B,J,M), C is A/B.
term(A,N,M) :- mterm(N), factor(A,N,M).

factor(A,N,M) :- word(A,N,M), integer(A).

We have only created magic sets for the grammar predicates expr/3 and term/3, and only the corresponding grammar rules get modified. if we would also have for example a rule "factor(A,N,M) :- word('(',N,H), expr(A,H,J), word(')',J,M)", we could also use a magic set for the grammar predicate factor/3. The screenshot shows an example run. Compared to the naive chart parser, a couple of cell elements are not generated:

Tthe following chart elements are not anymore generated:

expr(2, 2, 3).
expr(6, 2, 5).
expr(3, 4, 5).
term(3, 4, 5).

But the following irrelevant chart elements is still deduced:

expr(3, 0, 3).

And extra storage is needed for the magic sets:

mexpr(0).
mterm(0).
mterm(2).

The Source Code of the Magic Set Gammar:
http://www.xlog.ch/jekejeke/forward/earley.p

Previous Post that shows naive Chart Parser via Forward Chaining: