
% Input language: CR-separated lines of the form
%
%   <line>       ::= for <index_list>    |
%                    idx id              |
%                    fun id <index_list> |
%                    var id              |
%                    arr <index_list>    |
%
%   <index_list> ::= <lambda>            |
%                    <non_empty_index_list>
%
%   <non_empty_index_list> ::= id        |
%                              id, <non_empty_index_list>
%
% `id' is an identifer (which shouldn't be capitalised).
% Tree-structure is defined by indentation of lines---occam-like
% conventions will do, although the parser is actually a bit freer.

% Output: a node of one of the forms
%   for(I, D)
%   idx(X)
%   fun(F, I, D)
%   var(V, D)
%   arr(I, D)
% where
%   D is a list of nodes.
%   I is list of indices.
%   X is an index.
%   F is a function.
%   V is a variable.

getNode(P) :- getLines(Ls), lexLines(Ls, T), parseLines(T, P).

% `getLines' gets a list of lines from the input.

getLines(Ls) :- get0(X), getRest(X, Ls).

getRest(X, [])             :- isEOF(X), !.
getRest(X, [[] | Ls])      :- isCR(X), !, getLines(Ls).
getRest(X, [[X | L] | Ls]) :- getLines([L | Ls]).

% `lexLines' takes a list of input lines, and returns a list
% tokenised lines, including the numeric value of the indentation.

lexLines([], []) :- !.
lexLines([L | T], [M | S]) :- lexLine(L, M), lexLines(T, S).

lexLine(List, line(I, L)) :-
    indentation(List, Tail, I),
    getTokens(Tail, L).

indentation([X | List], Tail, I) :-
    isSpace(X), !,
    indentation(List, Tail, J),
    I is J + 1.
indentation(List, List, 0).

getTokens([], [])        :- !.
getTokens([X | _], [])   :- isBeginComment(X).
getTokens(List, [T | L]) :-
    getToken(List, InterTail, T),
    isWhiteSpace(InterTail, Tail),
    getTokens(Tail, L).

getToken([X | Tail], Tail, comma) :- isComma(X), !.
getToken(List, Tail, T) :-
    isString(List, Tail, S),
    tokenise(S, T).

tokenise("for", for) :- !.
tokenise("idx", idx) :- !.
tokenise("fun", fun) :- !.
tokenise("var", var) :- !.
tokenise("arr", arr) :- !.
tokenise(S,   id(X)) :- name(X, S), ground(X).

isWhiteSpace([X | List], Tail) :-
    isSpace(X), !,
    isWhiteSpace(List, Tail).
isWhiteSpace(List, List).

isString([X, Y | List], [Y | List], [X])     :- isSpace(Y), !.
isString([X, Y | List], [Y | List], [X])     :- isComma(Y), !.
isString([X],           [],         [X])     :- !.
isString([X | List],    Tail,       [X | I]) :- isString(List, Tail, I).

isCR(10).
isEOF(-1).
isSpace(32).
isBeginComment(37).
isComma(44).

% `parseLines' takes the output of `lexLines', and builds a syntax tree,
% guided by indentation of original text.

parseLines(List, T) :- parseNode(List, Tail, T), areBlanks(Tail).

parseNode([line(_, []) | List], Tail, X) :- parseNode(List, Tail, X).
parseNode([line(Indent, [for | A]) | List], Tail, for(I, D)) :-
    parseIdList(A, I),
    parseDaughters(Indent, List, Tail, D).
parseNode([line(_, [idx, id(X)]) | Tail], Tail, idx(X)).
parseNode([line(Indent, [fun, id(F) | A]) | List], Tail, fun(F, I, D)) :-
    parseIdList(A, I),
    parseDaughters(Indent, List, Tail, D).
parseNode([line(Indent, [var, id(V)]) | List], Tail, var(V, D)) :-
    parseDaughters(Indent, List, Tail, D).
parseNode([line(Indent, [arr | A]) | List], Tail, arr(I, D)) :-
    parseIdList(A, I),
    parseDaughters(Indent, List, Tail, D).

parseDaughters(_, [], [], []) :- !.
parseDaughters(Indent, [X | List], [X | List], []) :- outdented(Indent, X), !.
parseDaughters(Indent, List, Tail, [N | L]) :-
    parseNode(List, InterTail, N), !,
    parseDaughters(Indent, InterTail, Tail, L).

areBlanks([]).
areBlanks([line(_, []) | List]) :- areBlanks(List).

parseIdList([], [])       :- !.
parseIdList(A,  I)        :- parseNonEmptyIdList(A, I).

parseNonEmptyIdList([id(X)], [X]) :- !.
parseNonEmptyIdList([id(X), comma | L], [X | M]) :-
    parseNonEmptyIdList(L, M).

outdented(Indent, line(Jndent, _)) :- Jndent =< Indent.

