Parser.cc

#include "Parser.h"
#include "../test/Tookit.h"
#include "../test/TestParser.h"

/**
 * This is a helper function that will just iterate through every token that was
 * generated in the lexical analyzer (scanner), and print it off. While this was
 * more useful in earlier parts of the project, its used now only for debugging.
 */
void Parser::printTokens() {
    Token t = scanner.getCurrentToken();
    while (
        t.getTokenType() != eof &&
        t.getTokenType() != error
    ) {
        std::cout << t.repr() << std::endl;
        scanner.moveToNextToken();
        t = scanner.getCurrentToken();
    }
}

/**
 * Here we begin the process of parsing expressions in our lisp program. As long
 * as the current token isn't an EOF, we want to continue iterating through
 * expressions to build our parse tree (see parseExpression() for more info).
 */
void Parser::start() {
    do {
        if (isAtom(scanner.getCurrentToken())) {
            std::cout << scanner.getCurrentToken().repr() << std::endl;
            scanner.moveToNextToken();
        } else {
            ExpressionTreeNode *root = new ExpressionTreeNode();
            parseExpression(root);
            std::cout << printExpression(root->leftChild, isList) << std::endl;
        }
    } while (scanner.getCurrentToken().getTokenType() != eof);
}

/**
 * This method is able to parse a single expression, corresponding to our CFG:
 *
 *     <Start> ::= <Expr> <Start> | <Expr> eof
 *     <Expr>  ::= atom | ( <List> )
 *     <List>  ::= <Expr> <List>
 *
 * The result is a binary parse tree that will allow us to traverse the program
 * later on in our interpreter. In this binary tree, the left child of the root
 * will be the head of a lisp statement, and the right child will be its tail.
 */
void Parser::parseExpression(ExpressionTreeNode *root) {
    ExpressionTreeNode *nodeNIL = new ExpressionTreeNode;

    // Scaffold out an empty node.
    ExpressionTreeNode *current = root;
    current->leftChild = nodeNIL;
    current->rightChild = nodeNIL;

    if (isAtom(scanner.getCurrentToken())) {
        // In this case, we have an atom. Construct a ETN with the left child
        // containing the atom itself; the right child remains NIL.
        ExpressionTreeNode *newAtomicNode = new ExpressionTreeNode();
        newAtomicNode->atom = scanner.getCurrentToken();
        current->leftChild = newAtomicNode;
        scanner.moveToNextToken();
    } else if (scanner.getCurrentToken().getTokenType() == parenOpen) {
        ExpressionTreeNode *temp = current;
        scanner.moveToNextToken(); // Consume opening parenthesis.
        if (scanner.getCurrentToken().getTokenType() == parenClose) {
            // Here, we have a NIL token.
            scanner.moveToNextToken();
            temp = temp->leftChild;
        } else {
            // We have a LIST.
            ExpressionTreeNode *newList = new ExpressionTreeNode();
            temp->leftChild = newList;
            while (scanner.getCurrentToken().getTokenType() != parenClose) {
                parseExpression(newList);
                newList = newList->rightChild;
            }
            scanner.moveToNextToken();
        }
    } else {
        std::cout << "Parse error: expected atom (numeric, literal) or list: "
                  << scanner.getCurrentToken().repr()
                  << std::endl;

        exit(EXIT_FAILURE);
    }
}

/**
 * Traverses through a parse tree generated by parseExpression() which allows
 * us to print an expression in a way that is understandable to users.
 */
std::string Parser::printExpression(ExpressionTreeNode *root, bool isList) {
    std::string result = "";

    if (root) {
        if (root->leftChild) {
            result.append("(");
            result.append(printExpression(root->leftChild, IS_NOT_ATOM));
            result.append(" . ");
            if (root->rightChild) {
                result.append(printExpression(root->rightChild, IS_NOT_ATOM));
            } else {
                result.append("NIL");
            }
            result.append(")");
        } else {
            result.append(root->atom.repr());
        }
    }

    return result;
}

bool Parser::isAtom(Token t) {
    return t.getTokenType() == atomLiteral ||
           t.getTokenType() == atomNumeric ||
           t.getTokenType() == nil;
}

valgrind.out

[roth.375@sl2 lisp-interpreter]$ valgrind --track-origins=yes ./bin/interpreter < ./examples/ex5.lisp
==20690== Memcheck, a memory error detector
==20690== Copyright (C) 2002-2012, and GNU GPL'd, by Julian Seward et al.
==20690== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info
==20690== Command: ./bin/interpreter
==20690==
123
==20690== Conditional jump or move depends on uninitialised value(s)
==20690==    at 0x40ACC1: Parser::printExpression(ExpressionTreeNode*, bool) (in /home/8/roth.375/courses/AU17/6341-foundations-pl/lisp-interpreter/bin/interpreter)
==20690==    by 0x40AD6A: Parser::printExpression(ExpressionTreeNode*, bool) (in /home/8/roth.375/courses/AU17/6341-foundations-pl/lisp-interpreter/bin/interpreter)
==20690==    by 0x40ACF3: Parser::printExpression(ExpressionTreeNode*, bool) (in /home/8/roth.375/courses/AU17/6341-foundations-pl/lisp-interpreter/bin/interpreter)
==20690==    by 0x40AD6A: Parser::printExpression(ExpressionTreeNode*, bool) (in /home/8/roth.375/courses/AU17/6341-foundations-pl/lisp-interpreter/bin/interpreter)
==20690==    by 0x40AD6A: Parser::printExpression(ExpressionTreeNode*, bool) (in /home/8/roth.375/courses/AU17/6341-foundations-pl/lisp-interpreter/bin/interpreter)
==20690==    by 0x40A6B5: Parser::start() (in /home/8/roth.375/courses/AU17/6341-foundations-pl/lisp-interpreter/bin/interpreter)
==20690==    by 0x401D52: main (in /home/8/roth.375/courses/AU17/6341-foundations-pl/lisp-interpreter/bin/interpreter)
==20690==  Uninitialised value was created by a heap allocation
==20690==    at 0x4A075FC: operator new(unsigned long) (vg_replace_malloc.c:298)
==20690==    by 0x40A7A3: Parser::parseExpression(ExpressionTreeNode*) (in /home/8/roth.375/courses/AU17/6341-foundations-pl/lisp-interpreter/bin/interpreter)
==20690==    by 0x40AAEC: Parser::parseExpression(ExpressionTreeNode*) (in /home/8/roth.375/courses/AU17/6341-foundations-pl/lisp-interpreter/bin/interpreter)
==20690==    by 0x40AAEC: Parser::parseExpression(ExpressionTreeNode*) (in /home/8/roth.375/courses/AU17/6341-foundations-pl/lisp-interpreter/bin/interpreter)
==20690==    by 0x40A68A: Parser::start() (in /home/8/roth.375/courses/AU17/6341-foundations-pl/lisp-interpreter/bin/interpreter)
==20690==    by 0x401D52: main (in /home/8/roth.375/courses/AU17/6341-foundations-pl/lisp-interpreter/bin/interpreter)
==20690==
==20690== Conditional jump or move depends on uninitialised value(s)
==20690==    at 0x40ACC1: Parser::printExpression(ExpressionTreeNode*, bool) (in /home/8/roth.375/courses/AU17/6341-foundations-pl/lisp-interpreter/bin/interpreter)
==20690==    by 0x40AD6A: Parser::printExpression(ExpressionTreeNode*, bool) (in /home/8/roth.375/courses/AU17/6341-foundations-pl/lisp-interpreter/bin/interpreter)
==20690==    by 0x40AD6A: Parser::printExpression(ExpressionTreeNode*, bool) (in /home/8/roth.375/courses/AU17/6341-foundations-pl/lisp-interpreter/bin/interpreter)
==20690==    by 0x40AD6A: Parser::printExpression(ExpressionTreeNode*, bool) (in /home/8/roth.375/courses/AU17/6341-foundations-pl/lisp-interpreter/bin/interpreter)
==20690==    by 0x40AD6A: Parser::printExpression(ExpressionTreeNode*, bool) (in /home/8/roth.375/courses/AU17/6341-foundations-pl/lisp-interpreter/bin/interpreter)
==20690==    by 0x40A6B5: Parser::start() (in /home/8/roth.375/courses/AU17/6341-foundations-pl/lisp-interpreter/bin/interpreter)
==20690==    by 0x401D52: main (in /home/8/roth.375/courses/AU17/6341-foundations-pl/lisp-interpreter/bin/interpreter)
==20690==  Uninitialised value was created by a heap allocation
==20690==    at 0x4A075FC: operator new(unsigned long) (vg_replace_malloc.c:298)
==20690==    by 0x40A7A3: Parser::parseExpression(ExpressionTreeNode*) (in /home/8/roth.375/courses/AU17/6341-foundations-pl/lisp-interpreter/bin/interpreter)
==20690==    by 0x40AAEC: Parser::parseExpression(ExpressionTreeNode*) (in /home/8/roth.375/courses/AU17/6341-foundations-pl/lisp-interpreter/bin/interpreter)
==20690==    by 0x40A68A: Parser::start() (in /home/8/roth.375/courses/AU17/6341-foundations-pl/lisp-interpreter/bin/interpreter)
==20690==    by 0x401D52: main (in /home/8/roth.375/courses/AU17/6341-foundations-pl/lisp-interpreter/bin/interpreter)
==20690==
(3 . (5 . ((XYZ . NIL) . (7 . NIL))))
(DEFUN . (F23 . ((X . NIL) . ((PLUS . (X . (12 . (55 . NIL)))) . NIL))))
(NIL . (5 . (NIL . ((NIL . NIL) . (7 . ((NIL . (9 . (NIL . NIL))) . NIL))))))
==20690==
==20690== HEAP SUMMARY:
==20690==     in use at exit: 2,593 bytes in 68 blocks
==20690==   total heap usage: 291 allocs, 223 frees, 14,985 bytes allocated
==20690==
==20690== LEAK SUMMARY:
==20690==    definitely lost: 120 bytes in 3 blocks
==20690==    indirectly lost: 2,473 bytes in 65 blocks
==20690==      possibly lost: 0 bytes in 0 blocks
==20690==    still reachable: 0 bytes in 0 blocks
==20690==         suppressed: 0 bytes in 0 blocks
==20690== Rerun with --leak-check=full to see details of leaked memory
==20690==
==20690== For counts of detected and suppressed errors, rerun with: -v
==20690== ERROR SUMMARY: 8 errors from 2 contexts (suppressed: 8 from 6)