parser.c

/*
 * Parser - Recursive Descent Parser for PL/0
 *
 * Implements a recursive descent parser based on the PL/0 EBNF grammar.
 * Performs semantic analysis (symbol table management) and code generation
 * in a single pass. This is the classic approach used in Wirth's textbook.
 *
 * EBNF Grammar:
 *   program     = parser_block "." ;
 *   parser_block       = [ "const" ident "=" number {"," ident "=" number} ";"]
 *                 [ "var" ident {"," ident} ";"]
 *                 { "procedure" ident ";" parser_block ";" } parser_statement ;
 *   parser_statement   = [ ident ":=" parser_expression | "call" ident
 *                 | "?" ident | "!" parser_expression
 *                 | "begin" parser_statement {";" parser_statement } "end"
 *                 | "if" parser_condition "then" parser_statement
 *                 | "while" parser_condition "do" parser_statement ];
 *   parser_condition   = "odd" parser_expression |
 *                 parser_expression ("="|"#"|"<"|"<="|">"|">=") parser_expression ;
 *   parser_expression  = ["+"|"-"] parser_term { ("+"|"-") parser_term};
 *   parser_term        = parser_factor {("*"|"/") parser_factor};
 *   parser_factor      = ident | number | "(" parser_expression ")" ;
 */

#include "pl0.h"

/*
 * Emit an instruction to the code array.
 */
static void emit(Parser *parser, Opcode op, int value)
{
    if (parser->code->code_count >= MAX_CODE_SIZE) {
        fprintf(stderr, "Error: code segment overflow\n");
        parser->error_count++;
        return;
    }
    parser->code->code[parser->code->code_count].op = op;
    parser->code->code[parser->code->code_count].value = value;
    parser->code->code_count++;
}

/*
 * Report a parser error with location.
 */
static void error(Parser *parser, const char *message)
{
    fprintf(stderr, "Error at line %d: %s\n",
            parser->lexer->current.line, message);
    parser->error_count++;
}

/*
 * Check if current token matches expected type. If so, advance to next token.
 * Returns 1 on match, 0 otherwise.
 */
static int match(Parser *parser, TokenType expected)
{
    if (parser->lexer->current.type == expected) {
        lexer_next(parser->lexer);
        return 1;
    }
    return 0;
}

/*
 * Require a token - reports error if not present but still advances.
 */
static void require(Parser *parser, TokenType expected, const char *what)
{
    if (!match(parser, expected)) {
        fprintf(stderr, "Error at line %d: expected %s, got %d\n",
                parser->lexer->current.line, what,
                parser->lexer->current.type);
        parser->error_count++;
        lexer_next(parser->lexer); /* Advance past the bad token */
    }
}

/*
 * Initialize parser with all required context.
 */
void parser_init(Parser *parser, Lexer *lexer, SymbolTable *symbols, Code *code)
{
    parser->lexer = lexer;
    parser->symbols = symbols;
    parser->code = code;
    parser->level = 0;
    parser->data_addr = 3; /* 0: return addr, 1: static link, 2: first local */
    parser->proc_count = 0;
    parser->error_count = 0;
}

/*
 * program = parser_block "." ;
 *
 * A PL/0 program is simply a parser_block followed by a period.
 */
void parser_program(Parser *parser)
{
    parser_block(parser);
    require(parser, T_PERIOD, ".");

    /* Emit HALT instruction */
    emit(parser, OP_HALT, 0);
}

/*
 * parser_block = [ "const" ident "=" number {"," ident "=" number} ";"]
 *         [ "var" ident {"," ident} ";"]
 *         { "procedure" ident ";" parser_block ";" } parser_statement ;
 *
 * Handles declarations (constants, variables, procedures) and then
 * parses the main parser_statement.
 */
void parser_block(Parser *parser)
{
    /* const ident = number {, ident = number } ; */
    if (match(parser, T_CONST)) {
        do {
            require(parser, T_IDENT, "identifier");
            char name[MAX_IDENT_LEN];
            strncpy(name, parser->lexer->current.ident, MAX_IDENT_LEN - 1);
            name[MAX_IDENT_LEN - 1] = '\0';

            require(parser, T_EQ, "=");
            require(parser, T_NUMBER, "number");
            int value = parser->lexer->current.value;

            /* Add constant to symbol table */
            symbol_add(parser->symbols, name, SYM_CONST, value, parser->level);

        } while (match(parser, T_COMMA));
        require(parser, T_SEMICOLON, ";");
    }

    /* var ident {, ident } ; */
    if (match(parser, T_VAR)) {
        do {
            /* Save identifier BEFORE requiring it (since require advances) */
            char name[MAX_IDENT_LEN];
            if (parser->lexer->current.type == T_IDENT) {
                strncpy(name, parser->lexer->current.ident, MAX_IDENT_LEN - 1);
                name[MAX_IDENT_LEN - 1] = '\0';
            } else {
                name[0] = '\0';
            }
            require(parser, T_IDENT, "identifier");

            /* Add variable to symbol table with its address */
            symbol_add(parser->symbols, name, SYM_VAR, parser->data_addr, parser->level);
            parser->data_addr++;

        } while (match(parser, T_COMMA));
        require(parser, T_SEMICOLON, ";");
    }

    /* { procedure ident ; parser_block ; } */
    while (match(parser, T_PROCEDURE)) {
        require(parser, T_IDENT, "procedure name");
        char name[MAX_IDENT_LEN];
        strncpy(name, parser->lexer->current.ident, MAX_IDENT_LEN - 1);
        name[MAX_IDENT_LEN - 1] = '\0';

        /* Record position for jump around procedure */
        int proc_start = parser->code->code_count;
        emit(parser, OP_JMP, 0); /* Will patch later */

        /* Procedure address is AFTER the JMP instruction */
        int proc_addr = parser->code->code_count;

        /* Enter new scope - note procedure does not increase data_addr */
        symbol_add(parser->symbols, name, SYM_PROC, proc_addr, parser->level);

        require(parser, T_SEMICOLON, ";");

        parser->level++;
        parser_block(parser);
        parser->level--;

        /* Return from procedure */
        emit(parser, OP_RET, 0);

        /* Patch jump over procedure */
        parser->code->code[proc_start].value = parser->code->code_count;

        require(parser, T_SEMICOLON, ";");
    }

    /* Statement follows */
    parser_statement(parser);
}

/*
 * parser_statement = [ ident ":=" parser_expression
 *             | "call" ident
 *             | "?" ident
 *             | "!" parser_expression
 *             | "begin" parser_statement {";" parser_statement } "end"
 *             | "if" parser_condition "then" parser_statement
 *             | "while" parser_condition "do" parser_statement ];
 */
void parser_statement(Parser *parser)
{
    /* ident := parser_expression (assignment) */
    if (parser->lexer->current.type == T_IDENT) {
        char name[MAX_IDENT_LEN];
        strncpy(name, parser->lexer->current.ident, MAX_IDENT_LEN - 1);
        name[MAX_IDENT_LEN - 1] = '\0';

        lexer_next(parser->lexer); /* consume identifier */

        Symbol *sym = symbol_lookup(parser->symbols, name);
        if (sym == NULL) {
            error(parser, "Undefined identifier");
        }

        require(parser, T_ASSIGN, ":=");
        parser_expression(parser);

        if (sym != NULL && sym->type == SYM_VAR) {
            emit(parser, OP_STORE, sym->value);
        }
        return;
    }

    /* call ident */
    if (match(parser, T_CALL)) {
        require(parser, T_IDENT, "procedure name");
        char name[MAX_IDENT_LEN];
        strncpy(name, parser->lexer->current.ident, MAX_IDENT_LEN - 1);
        name[MAX_IDENT_LEN - 1] = '\0';

        Symbol *sym = symbol_lookup(parser->symbols, name);
        if (sym != NULL && sym->type == SYM_PROC) {
            emit(parser, OP_CALL, sym->value);
        } else {
            error(parser, "Undefined procedure");
        }
        return;
    }

    /* ? ident (read input) */
    if (match(parser, T_READ)) {
        require(parser, T_IDENT, "variable name");
        char name[MAX_IDENT_LEN];
        strncpy(name, parser->lexer->current.ident, MAX_IDENT_LEN - 1);
        name[MAX_IDENT_LEN - 1] = '\0';

        Symbol *sym = symbol_lookup(parser->symbols, name);
        if (sym != NULL && sym->type == SYM_VAR) {
            /* Input is read at runtime - emit code to read */
            emit(parser, OP_READ, sym->value);
        } else {
            error(parser, "Undefined variable");
        }
        return;
    }

    /* ! parser_expression (write output) */
    if (match(parser, T_WRITE)) {
        parser_expression(parser);
        emit(parser, OP_WRITE, 0);
        return;
    }

    /* begin parser_statement { ; parser_statement } end */
    if (match(parser, T_BEGIN)) {
        parser_statement(parser);
        while (match(parser, T_SEMICOLON)) {
            parser_statement(parser);
        }
        require(parser, T_END, "end");
        return;
    }

    /* if parser_condition then parser_statement [else parser_statement] */
    if (match(parser, T_IF)) {
        parser_condition(parser);
        require(parser, T_THEN, "then");

        /* Jump to else or past if */
        int jz_pos = parser->code->code_count;
        emit(parser, OP_JZ, 0);

        parser_statement(parser);

        /* Check for else */
        if (match(parser, T_ELSE)) {
            /* Jump past else block after then block */
            int jmp_pos = parser->code->code_count;
            emit(parser, OP_JMP, 0);

            /* Patch the first jump to here (else start) */
            parser->code->code[jz_pos].value = parser->code->code_count;

            parser_statement(parser);

            /* Patch the jump over else */
            parser->code->code[jmp_pos].value = parser->code->code_count;
        } else {
            /* Patch the jump to here (past then block, no else) */
            parser->code->code[jz_pos].value = parser->code->code_count;
        }
        return;
    }

    /* while parser_condition do parser_statement */
    if (match(parser, T_WHILE)) {
        int loop_start = parser->code->code_count;

        parser_condition(parser);
        require(parser, T_DO, "do");

        int jz_pos = parser->code->code_count;
        emit(parser, OP_JZ, 0);

        parser_statement(parser);

        /* Jump back to loop start */
        emit(parser, OP_JMP, loop_start);

        /* Patch the parser_conditional jump to exit loop */
        parser->code->code[jz_pos].value = parser->code->code_count;
        return;
    }
}

/*
 * parser_condition = "odd" parser_expression |
 *              parser_expression ("="|"#"|"<"|"<="|">"|">=") parser_expression ;
 */
void parser_condition(Parser *parser)
{
    /* odd parser_expression */
    if (match(parser, T_ODD)) {
        parser_expression(parser);
        emit(parser, OP_ODD, 0);
        return;
    }

    /* parser_expression rel-op parser_expression */
    parser_expression(parser);

    TokenType relop = parser->lexer->current.type;

    /* Check for valid operator before consuming */
    if (relop != T_EQ && relop != T_NEQ && relop != T_LT &&
        relop != T_LTE && relop != T_GT && relop != T_GTE) {
        error(parser, "Expected relational operator");
        return;
    }

    lexer_next(parser->lexer); /* consume operator */
    parser_expression(parser);

    /* Emit the relational operator AFTER both expressions */
    switch (relop) {
    case T_EQ:
        emit(parser, OP_EQ, 0);
        break;
    case T_NEQ:
        emit(parser, OP_NEQ, 0);
        break;
    case T_LT:
        emit(parser, OP_LT, 0);
        break;
    case T_LTE:
        emit(parser, OP_LTE, 0);
        break;
    case T_GT:
        emit(parser, OP_GT, 0);
        break;
    case T_GTE:
        emit(parser, OP_GTE, 0);
        break;
    default:
        break; /* Should not reach here - already validated */
    }
}

/*
 * parser_expression = ["+"|"-"] parser_term { ("+"|"-") parser_term} ;
 */
void parser_expression(Parser *parser)
{
    /* Optional unary + or - */
    int unary_minus = 0;
    if (match(parser, T_PLUS)) {
        /* Unary plus - no-op */
    } else if (match(parser, T_MINUS)) {
        unary_minus = 1;
    }

    parser_term(parser);

    /* Handle leading unary minus */
    if (unary_minus) {
        emit(parser, OP_CONST, 0);
        emit(parser, OP_SUB, 0);
    }

    /* { ("+"|"-") parser_term } */
    while (parser->lexer->current.type == T_PLUS ||
           parser->lexer->current.type == T_MINUS) {
        TokenType op = parser->lexer->current.type;
        lexer_next(parser->lexer);
        parser_term(parser);

        if (op == T_PLUS) {
            emit(parser, OP_ADD, 0);
        } else {
            emit(parser, OP_SUB, 0);
        }
    }
}

/*
 * parser_term = parser_factor {("*"|"/") parser_factor} ;
 */
void parser_term(Parser *parser)
{
    parser_factor(parser);

    /* { ("*"|"/") parser_factor } */
    while (parser->lexer->current.type == T_MUL ||
           parser->lexer->current.type == T_DIV) {
        TokenType op = parser->lexer->current.type;
        lexer_next(parser->lexer);
        parser_factor(parser);

        if (op == T_MUL) {
            emit(parser, OP_MUL, 0);
        } else {
            emit(parser, OP_DIV, 0);
        }
    }
}

/*
 * parser_factor = ident | number | "(" parser_expression ")" ;
 */
void parser_factor(Parser *parser)
{
    /* ident - could be constant or variable */
    if (parser->lexer->current.type == T_IDENT) {
        char name[MAX_IDENT_LEN];
        strncpy(name, parser->lexer->current.ident, MAX_IDENT_LEN - 1);
        name[MAX_IDENT_LEN - 1] = '\0';

        lexer_next(parser->lexer);

        Symbol *sym = symbol_lookup(parser->symbols, name);
        if (sym == NULL) {
            error(parser, "Undefined identifier");
            return;
        }

        if (sym->type == SYM_CONST) {
            /* Push constant value */
            emit(parser, OP_CONST, sym->value);
        } else if (sym->type == SYM_VAR) {
            /* Load variable value */
            emit(parser, OP_LOAD, sym->value);
        } else {
            error(parser, "Cannot use procedure in parser_expression");
        }
        return;
    }

    /* number - push constant */
    if (parser->lexer->current.type == T_NUMBER) {
        int value = parser->lexer->current.value;
        lexer_next(parser->lexer);
        emit(parser, OP_CONST, value);
        return;
    }

    /* ( parser_expression ) */
    if (match(parser, T_LPAREN)) {
        parser_expression(parser);
        require(parser, T_RPAREN, ")");
        return;
    }

    error(parser, "Expected identifier, number, or (");
}

/* ============================================================================
 * Main Compile Entry Point
 * ============================================================================ */

int compile(const char *source, Code *code, SymbolTable *symbols)
{
    Lexer lexer;
    Parser parser;

    /* Initialize code buffer */
    code->code_count = 0;

    /* Initialize symbol table */
    symbol_init(symbols);

    /* Initialize lexer */
    lexer_init(&lexer, source);

    /* Initialize parser */
    parser_init(&parser, &lexer, symbols, code);

    /* Parse program */
    parser_program(&parser);

    if (parser.error_count > 0) {
        fprintf(stderr, "Compilation failed with %d error(s)\n", parser.error_count);
        return -1;
    }

    return code->code_count;
}