gistfile1.prolog

/*
 * Grammar production: [Cat, [Cat]] or [Cat, Term]
 * DI: [Cat, Consumed, Left]
 */
%disr(Rest, Stack, Grammar) :- fail.
disr(Input, Grammar) :- disr(Input, [], Grammar).

% SHIFT: Word of category Cat next word in input: ``push Cat -> Word \dot'' onto stack.
disr([W|Rest], Stack, Grammar) :- grammar_terminal(Grammar, W, Cat), DI = [Cat, [W], []], disr(Rest, [DI|Stack], Grammar).
% SEED: Given a completed DI of category CatB on top of the stack and a production CatA -> CatB ..., replace the top item with a new DI [CatA, [CatB], ...]
disr(In, [DI|Stack], Grammar) :-
    DI = [CatB, _, []],
    grammar_seed(Grammar, CatB, Production),
    Production = [CatA, [CatB|Rest]],
    NewDI = [CatA, [CatB], Rest],
    disr(In, [NewDI|Stack], Grammar).
% PACK: Given a complete DI of category Cat on top of the stack preceded by a partial DI whose next item is Cat, shift the dot of the partial one place to the right.
disr(In, [Complete, Partial|Stack], Grammar) :-
    Complete = [Cat, _, []],
    Partial = [CatP, ConsumedP, [Cat|Rest]],
    append(ConsumedP, [Cat], Consumed),
    NewDI = [CatP, Consumed, Rest],
    disr(In, [NewDI|Stack], Grammar).
% Parse success: Single item on the stack, being a completed DI for the category s.
disr([], [Item], _) :- Item = [s, _, []].

% grammar_terminal: Get the lexical category of a word.
grammar_terminal([Prod|_], Word, Category) :- Prod = [Category, Word].
grammar_terminal([_|Rest], Word, Category) :- grammar_terminal(Rest, Word, Category).

% grammar_seed: Get a production whose first RHS item is Cat.
grammar_seed([Prod|_], Cat, Prod) :- Prod = [_, [Cat|_]].
grammar_seed([_|Rest], Cat, Prod) :- grammar_seed(Rest, Cat, Prod).

test :-
    disr([kim, shovels, snow, in, oslo],
    [
        [s, [np, vp]],
        [vp, [v, np]],
        [vp, [v, np, pp]],
        [v, shovels],
        [np, [np, pp]],
        [np, kim],
        [np, snow],
        [np, oslo],
        [pp, [p, np]],
        [p, in]
    ]).