thouffle.dl

.type TokenStream = [first: Token, rest: TokenStream]
.symbol_type Token

// TODO: better types, including tokens having associated literals

// -- scanner --

/**
 * tokens(program, start, tokens) is true iff:
 *  - @program is an input program,
 *  - @start is a valid index in the program
 *  - @tokens is the stream of tokens starting from @start
 */
.decl tokens(program:symbol, start:number, tokens:TokenStream)

tokens(program, strlen(program), ["EOF", nil]) :- input_program(program). // EOF if we are at the end of the program
tokens(program, start, tokens) :-
    start != strlen(program),
    input_program(program),
    is_valid_index(program, start),
    next_token(program, start, token, end),
    (
        (token = "SPACE", tokens = rest);           // ignore whitespace tokens
        (token != "SPACE", tokens = [token, rest])  // the token read is the start of the current stream
    ),
    tokens(program, end, rest).

/**
 * next_token(program, start, token, end) is true iff:
 *  - @program is an input program
 *  - @start is a valid index in the program
 *  - @token is the next token in the stream
 *  - @end is the index of the program right after the current token is read
 */
.decl next_token(program:symbol, start:number, token:Token, end:number)
next_token(program, start, token, end) :-
    input_program(program),
    is_valid_index(program, start),
    (
        (start = strlen(program), token = "EOF", end = start + 1);      // handle EOF
        (start != strlen(program), is_valid_index(program, end),        // otherwise, end is a valid index
            (
                // handle print
                ("print" = substr(program, start, 5), token = "PRINT", end = start + 5);

                // handle numbers
                (next_char = substr(program, start, 1), is_digit(next_char), next_number(program, next_num, start, end),
                    token = cat("NUMBER(", next_num, ")"));

                // handle single-character tokens
                ("print" != substr(program, start, 5), next_char = substr(program, start, 1), end = start + 1,
                    (
                        (next_char = "+", token = "PLUS", end = start + 1);
                        (next_char = "-", token = "MINUS", end = start + 1);
                        (next_char = "/", token = "SLASH", end = start + 1);
                        (next_char = "*", token = "STAR", end = start + 1);
                        (next_char = "(", token = "LPAREN", end = start + 1);
                        (next_char = ")", token = "RPAREN", end = start + 1);
                        (is_whitespace(next_char), token = "SPACE", end = start + 1);

                        // error - nothing matches
                        (next_char != "+", next_char != "-", next_char != "/", next_char != "*", next_char != "(", next_char != ")",
                            !is_whitespace(next_char), !is_digit(next_char),
                            token = "ERROR", end = start + 1)
                    )
                )
            )
        )
    ).

/**
 * next_number(program, start, end) is true iff:
 *  - @program is an input program
 *  - @literal is the string representation of the number read from that point
 *  - @start is a valid index in the program
 *  - @end is the index just after the current number is read
 */
.decl next_number(program:symbol, literal:symbol, start:number, end:number)
next_number(program, literal, start, end) :-
    input_program(program),
    is_valid_index(program, start),
    (
        // reached the end of the program
        (start = strlen(program), end = start, literal = "");

        // still within the program
        (start != strlen(program), next_char = substr(program, start, 1),
            (
                // still in the number!
                (is_digit(next_char), next_number(program, next_num, start+1, end), literal = cat(next_char, next_num));

                // number has finished
                (!is_digit(next_char), start = end, literal="")
            )
        )
    ).

// -- parser --

/**
 * parser(program, cpp) is true iff:
 *  - @program is an input program
 *  - @cpp is the C++ program that generates the output
 */
.decl parser(program:symbol, cpp:symbol)
parser(program, cpp) :-
    input_program(program),
    tokens(program, 0, ts),
    parse_program(ts, _, cpp).

// TODO: change to [program -> (expression)*] (instead of program -> expression)

/**
 * parse_program(ts, rest, cpp) is true iff:
 *  - @ts is a stream of tokens
 *  - @rest is the stream of tokens after a program has been parsed
 *  - @cpp is the C++ program generated from the parsed program
 */
.decl parse_program(ts:TokenStream, rest:TokenStream, cpp:symbol)
parse_program(ts, nil, cpp) :-
    parse_expression(ts, ["EOF", nil], cpp_expr),
    cpp_head = "#include <iostream>\n int main(void) {",
    cpp_tail = "}",
    cpp = cat(cpp_head, cpp_expr, cpp_tail).

// TODO: error handling for the parser

/**
 * parse_expression(ts, rest, cpp) is true iff:
 *  - @ts is a stream of tokens
 *  - @rest is the stream of tokens after an expression has been parsed
 *  - @cpp is the C++ program generated from the parsed expression
 */
.decl parse_expression(ts:TokenStream, rest:TokenStream, cpp:symbol)
parse_expression(ts, rest, cpp) :-
    tokens(_, _, rest),
    tokens(_, _, ts),
    (
        // empty token stream
        (ts = nil, rest = nil, cpp = "");

        // number
        (ts = [token, rest], "NUMBER" = substr(token, 0, 6), number = substr(token, 7, strlen(token)-8),  cpp = cat("(", number, ")"));

        // (OP ... ...)
        (ts = ["LPAREN", [op, tail]], parse_expression(tail, first, cpp_first), parse_expression(first, ["RPAREN", rest], cpp_second), cpp = cat("(", cpp_first, nop, cpp_second, ")"),
            (
                (op = "PLUS", nop = "+");
                (op = "MINUS", nop = "-");
                (op = "STAR", nop = "*");
                (op = "SLASH", nop = "/")
            )
        );

        // print function
        (ts = ["LPAREN", ["PRINT", tail]], parse_expression(tail, ["RPAREN", rest], cpp_rest), cpp = cat("std::cout << ", cpp_rest, " << std::endl;"))
    ).

// -- helpers --

/**
 * is_valid_index(program, idx) is true iff:
 *  - @program is an input program
 *  - @idx is between 0 and strlen(program), inclusive
 */
.decl is_valid_index(program:symbol, idx:number)
is_valid_index(program, 0) :- input_program(program).
is_valid_index(program, x+1) :- is_valid_index(program, x), x < strlen(program).

/**
 * is_whitespace(x) is true iff x is a whitespace character
 */
.decl is_whitespace(x:symbol)
is_whitespace(" ").

/**
 * is_whitespace(x) is true iff x is a digit
 */
.decl is_digit(x:symbol)
is_digit("0"). is_digit("1").
is_digit("2"). is_digit("3").
is_digit("4"). is_digit("5").
is_digit("6"). is_digit("7").
is_digit("8"). is_digit("9").

/**
 * ts_to_string(tokens, rep) is true iff:
 *  - @tokens is a stream of tokens
 *  - @rep is the string representation of tokens
 */
.decl ts_to_string(tokens:TokenStream, rep:symbol)
ts_to_string(nil, "").
ts_to_string([token, rest], cat(token, cat(".", rest_rep))) :-
    tokens(_, _, [token,rest]),
    ts_to_string(rest, rest_rep).

// -- input --
.decl input_program(program:symbol)
.input input_program()

// -- output --
.decl tokenizer_out(out:symbol)
tokenizer_out(out) :- input_program(program), tokens(program, 0, ts), ts_to_string(ts, stream), out = cat("INPUT: [ ", cat(program, cat(" ], OUTPUT: [ ", cat(stream, " ]")))).

.decl parser_out(out:symbol)
parser_out(out) :- parser(program, cpp), out = cat("INPUT: [ ", cat(program, cat(" ], OUTPUT: [ ", cat(cpp, " ]")))).

.output input_program()
.output tokenizer_out()
.output parser_out()