Recursive Descent Parser for a Calculator

#include <assert.h>
#include <stddef.h>
#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>

#include "lexer.h"
#include "tokenkind.h"

// error handling

void
expectedError(const char *expectedStr)
{
    fprintf(stderr, "%zu.%zu: error expected '%s' got '%s'\n", token.pos.line,
            token.pos.col, expectedStr, strTokenKind(token.kind));
    exit(1);
}

void
expected(enum TokenKind tokenKind)
{
    if (tokenKind != token.kind) {
        expectedError(strTokenKind(tokenKind));
    }
}

// for debugging
void
printWithIndent(size_t indent, const char *str)
{
#ifndef NDEBUG
    for (size_t i = 0; i < indent * 4; ++i) {
        printf(" ");
    }
    printf("%s\n", str);
#endif // NDEBUG
}

// parse functions
void parseInputSequence(size_t);
void parseExprStatement(size_t);
uint64_t parseExpr(size_t);
uint64_t parseTerm(size_t);
uint64_t parseFactor(size_t);

void
parseInputSequence(size_t indent)
{
    while (token.kind != EOI) {
        parseExprStatement(indent + 1);
    }
}

void
parseExprStatement(size_t indent)
{
    printWithIndent(indent, "parseExprStatement");
    printf("> %" PRIu64 "\n", parseExpr(indent + 1));
    expected(SEMICOLON);
    getToken();
}

uint64_t
parseExpr(size_t indent)
{
    printWithIndent(indent, "parseExpr");
    uint64_t val = parseTerm(indent + 1);
    while (token.kind == PLUS || token.kind == MINUS) {
        printWithIndent(indent, strTokenKind(token.kind));
        enum TokenKind op = token.kind;
        getToken();
        uint64_t valRight = parseTerm(indent + 1);
        if (op == PLUS) {
            val += valRight;
        } else {
            val -= valRight;
        }
    }
    return val;
}

uint64_t
parseTerm(size_t indent)
{
    printWithIndent(indent, "parseTerm");
    uint64_t val = parseFactor(indent + 1);
    while (token.kind == ASTERISK || token.kind == SLASH) {
        printWithIndent(indent, strTokenKind(token.kind));
        enum TokenKind op = token.kind;
        getToken();
        uint64_t valRight = parseFactor(indent + 1);
        if (op == ASTERISK) {
            val *= valRight;
        } else {
            val /= valRight;
        }
    }
    return val;
}

uint64_t
parseFactor(size_t indent)
{
    printWithIndent(indent, "parseFactor");
    uint64_t val = 0;
    if (token.kind == DEC_LITERAL) {
        printWithIndent(indent, token.val.cstr);
        val = strtoull(token.val.cstr, 0, 10);
        getToken();
        return val;
    } else if (token.kind == HEX_LITERAL) {
        printWithIndent(indent, token.val.cstr);
        val = strtoull(token.val.cstr, 0, 16);
        getToken();
        return val;
    } else if (token.kind == OCT_LITERAL) {
        printWithIndent(indent, token.val.cstr);
        val = strtoull(token.val.cstr, 0, 8);
        getToken();
        return val;
    } else if (token.kind == LPAREN) {
        printWithIndent(indent, strTokenKind(token.kind));
        getToken();
        val = parseExpr(indent + 1);
        expected(RPAREN);
        printWithIndent(indent, strTokenKind(token.kind));
        getToken();
        return val;
    } else {
        expectedError("factor");
        return val; // never reached
    }
}


// test for the parse

int
main(void)
{
    // we need a current token before we begin parsing
    getToken();
    parseInputSequence(0);
}

#ifndef ABC_LEXER_H
#define ABC_LEXER_H

#include <stddef.h>

#include "str.h"
#include "tokenkind.h"

enum TokenKind getToken(void);

struct Token
{
    enum TokenKind kind;
    struct TokenPos
    {
        size_t line, col;
    } pos;
    struct Str val;
};

extern struct Token token;

#endif // ABC_LEXER_H

#include <stdio.h>
#include <stdlib.h>

#include "tokenkind.h"

const char *
strTokenKind(enum TokenKind tokenKind)
{
    switch (tokenKind) {
        case EOI:
            return "EOI";
        case BAD_TOKEN:
            return "BAD_TOKEN";
        case HEX_LITERAL:
            return "HEX_LITERAL";
        case OCT_LITERAL:
            return "OCT_LITERAL";
        case DEC_LITERAL:
            return "DEC_LITERAL";
        case PLUS:
            return "PLUS";
        case MINUS:
            return "MINUS";
        case ASTERISK:
            return "ASTERISK";
        case SLASH:
            return "SLASH";
        case PERCENT:
            return "PERCENT";
        case EQUAL:
            return "EQUAL";
        case LPAREN:
            return "LPAREN";
        case RPAREN:
            return "RPAREN";
        case SEMICOLON:
            return "SEMICOLON";
        case IDENTIFIER:
            return "IDENTIFIER";
        default:
            fprintf(stderr, "internal error in strTokenKind: tokenKind = %d\n",
                    tokenKind);
            exit(1);
            return "";
    }
}

#ifndef ABC_TOKENKIND_H
#define ABC_TOKENKIND_H

enum TokenKind
{
    EOI,            // end of input
    BAD_TOKEN,
    HEX_LITERAL,
    OCT_LITERAL,
    DEC_LITERAL,
    PLUS,           // '+'
    MINUS,          // '-'
    ASTERISK,       // '*'
    SLASH,          // '/'
    PERCENT,        // '%'
    EQUAL,          // '='
    LPAREN,         // '('
    RPAREN,         // ')'
    SEMICOLON,      // ';'
    IDENTIFIER,
};

const char *strTokenKind(enum TokenKind tokenKind);

#endif // ABC_TOKENKIND_H

#ifndef ABC_STR_H
#define ABC_STR_H

struct Str
{
    char cstr[7];
    char *end;
};

// set str->cstr to empty string
void clearStr(struct Str *str);

// append character to str->cstr
void appendCharToStr(struct Str *str, char c);

#endif // ABC_STR_H

#include <stdlib.h>
#include <stdio.h>

#include "str.h"

void
clearStr(struct Str *str)
{
    *(str->end = str->cstr) = 0;
}

void
appendCharToStr(struct Str *str, char c)
{
    // check if another character and 0 byte fits into string
    if (str->end - str->cstr + 2 > sizeof(str->cstr)) {
        fprintf(stderr, "error in appendCharToStr: string too long\n");
        exit(1);
    }

    *str->end++ = c;
    *str->end = 0;
}