A simple compiler for a language called Jack

Question

Below is the code for a compiler I created for a language called Jack. This compiler is one of the projects for the book "The Elements of Computing Systems" (http://www1.idc.ac.il/tecs/plan.html) where you build an entire computing system from the ground up. Anyway, what this compiler does is translate code from a high level language (called Jack, it looks similar to Java) and then translates it to intermediate code while also creating a parse tree from it. It takes in a list of tokens (the tokenizing is handled by another component whose code I haven't included) as input.

Can someone take a look at this code and help me improve it? I'm done with the project but I want to make a similar compiler for another language I'm gonna make for this Hack platform.

(Note: I took out some code because it went over the character limit)

class CompilationEngine
{
private $tokens;          // Token list to operate on
private $symbol_table;    // Symbol table that stores all identifiers
private $registry;        // Hash table to store any additional information 

private $xml;        // Contains the XML code in a SimpleXMLElement object
private $vm;         // Contains the VM code in a VMWriter object

private $write_xml;       // Boolean flag that determines whether to output XML code
private $write_vm;        // Boolean flag that determines whether to output VM code

private $current_xml;     // Points to the current XML child object
private $parent_xml;      // Array of parent XML objects


// Initializes the CompilationEngine object with a list of tokens
public function __construct($tokens)
{
    $this->tokens = $tokens;
    $this->symbol_table = new SymbolTable();
    $this->registry = array();

    $this->xml = new SimpleXMLElement('<class></class>');
    $this->vm = new VMWriter();

    $this->current_xml = $this->xml[0]; 
    $this->parent_xml = array(); 

    $this->write_xml = false; 
    $this->write_vm = false; 


    // This is gonna be really hackish, but it's the only way I could think
    // of to implement proper method calling within the same class
    $this->registry['methods'] = array();
    $length = count($this->tokens);

    for ($c = 0; $c < $length; $c++)
    {
        if ($this->tokens[$c][TOKEN_TEXT] == 'method' && ($c + 2) < $length)
            $this->registry['methods'][] = $this->tokens[$c+2][TOKEN_TEXT];
    }
}


// Turns XML code writing on and off
public function setWriteXML($flag)
{
    $this->write_xml = $flag;
}


// Turns VM code writing on and off
public function setWriteVM($flag)
{
    $this->write_vm = $flag;
}


// Creates a child XML node of the current node and shifts focus to it
public function XML_enterChildNode($child_node_name)
{
    if (!$this->write_xml)
        return;

    $this->parent_xml[] = $this->current_xml; 
    $this->current_xml = $this->current_xml->addChild($child_node_name);
}


// Shifts focus back to the parent node of the current node
public function XML_returnToParent()
{
    if (!$this->write_xml)
        return;

    if (empty($this->parent_xml))
        return; 

    $this->current_xml = array_pop($this->parent_xml);
}


// Checks a condition and triggers a warning if it's false
private function check($condition, $message)
{
    if (!$condition)
        trigger_error(sprintf('CompilationEngine: %s', $message), E_USER_WARNING);
}


// Writes primitive token data to the XML output
private function writeTokenData($tokens)
{
    if (!$this->write_xml)
        return;

    if (!is_object($this->current_xml))
        return;

    $tokentype_to_string = array(
        TOKENTYPE_KEYWORD => 'keyword',
        TOKENTYPE_SYMBOL => 'symbol',
        TOKENTYPE_IDENTIFIER => 'identifier',
        TOKENTYPE_INT_CONST => 'integerConstant',
        TOKENTYPE_STRING_CONST => 'stringConstant'
    );

    foreach ($tokens as $token)
    {
        if (!array_key_exists($token[TOKEN_TYPE], $tokentype_to_string))
            trigger_error(sprintf('Unknown token type %d for token text "%s"', $token[TOKEN_TYPE], $token[TOKEN_TEXT]), E_USER_WARNING);

        $this->current_xml->addChild($tokentype_to_string[$token[TOKEN_TYPE]], htmlentities(htmlentities($token[TOKEN_TEXT], ENT_QUOTES)));
    }
}


// This function will write the function declaration
private function VM_writeFunctionDeclaration($name, $type)
{
    $this->vm->writeFunction($name, $this->symbol_table->getIndex(KIND_VAR));

    // If function type is constructor, then allocate memory for it and set "this" to assigned address
    if ($type == 'constructor')
    {
        $this->vm->writePush(SEGMENT_CONSTANT, $this->symbol_table->getIndex(KIND_FIELD));
        $this->vm->writeCall('Memory.alloc', 1);
        $this->vm->writePop(SEGMENT_POINTER, 0);
    }

    // If function type is method, then set "this" to value of first argument
    else if ($type == 'method')
    {
        $this->vm->writePush(SEGMENT_ARG, 0);
        $this->vm->writePop(SEGMENT_POINTER, 0);
    }
}


// Outputs the resulting XML or VM code, or both if specified
public function compile()
{
    $this->compileClass($this->tokens); 

    if ($this->write_xml && !$this->write_vm)
        return $this->xml->asXML();

    else if ($this->write_vm && !$this->write_xml)
        return implode("\n", $this->vm->getCode());

    else if ($this->write_xml && $this->write_vm)
        return array(
            'xml' => $this->xml->asXML(),
            'vm' => implode("\n", $this->vm_->getCode())
        ); 

    return null; 
}


// Compiles a complete class -- this method should be called first
private function compileClass($tokens)
{
    $this->check(JackTokenizer::isKeyword($tokens[0], 'class'), 'class (keyword) is incorrect');
    $this->check(JackTokenizer::isIdentifier($tokens[1]), sprintf('className "%s" is not a valid identifier', $tokens[1][TOKEN_TEXT]));
    $this->check(JackTokenizer::isSymbol($tokens[2], '{'), 'missing { symbol for class declaration');

    $this->writeTokenData(array_slice($tokens, 0, 3));
    $this->registry['className'] = $tokens[1][TOKEN_TEXT]; 

    $position = 3; 
    $length = count($tokens);

    while ($position < $length)
    {
        $token_args = array_slice($tokens, $position);

        if (JackTokenizer::isKeyword($tokens[$position], array('field', 'static')))
        {
            $vardec_length = $this->compileClassVarDec($token_args);
            $position += $vardec_length;
        }

        else if (JackTokenizer::isKeyword($tokens[$position], array('constructor', 'function', 'method')))
        {
            $subroutine_length = $this->compileSubroutine($token_args);
            $position += $subroutine_length;
        }

        else
        {
            break;
        }
    }

    $this->check(JackTokenizer::isSymbol($tokens[$position], '}'), 'missing } symbol for class declaration');
    $this->writeTokenData(array($tokens[$position]));
    $position += 1; 

    return $position; 
}


// Compiles a class static/field variable declaration
private function compileClassVarDec($tokens)
{
    $this->check(JackTokenizer::isKeyword($tokens[0], array('static', 'field')), 'Class variable declarations must use static or field keyword');
    $this->check(JackTokenizer::isType($tokens[1]), 'Type in class variable declaration is not a valid type');

    $this->XML_enterChildNode('classVarDec');

    $length = count($tokens);
    $position = 2; 
    $comma_needed = false;

    for ($c = $position; $c < $length && $tokens[$c][TOKEN_TEXT] != ';'; $c++)
    {
        if ($comma_needed && JackTokenizer::isSymbol($tokens[$c], ','))
        {
            $comma_needed = false;
            $position++; 
        }

        else if (!$comma_needed && JackTokenizer::isIdentifier($tokens[$c]))
        {
            $comma_needed = true; 
            $position++; 

            // Add class variables (static and field) to the symbol table
            $this->symbol_table->define($tokens[$c][TOKEN_TEXT], $tokens[1][TOKEN_TEXT], $tokens[0][TOKEN_TEXT] == 'static' ? KIND_STATIC : KIND_FIELD);
        }

        else
        {
            break; 
        }
    }

    $this->check($comma_needed, 'Trailing comma after class variable declaration');

    $this->check(JackTokenizer::isSymbol($tokens[$position], ';'), 'Class variable declaration must end with a semicolon');
    $position += 1; 

    $this->writeTokenData(array_slice($tokens, 0, $position));
    $this->XML_returnToParent();

    return $position; 
}


// Compiles a complete method
private function compileSubroutine($tokens)
{
    $this->check(JackTokenizer::isKeyword($tokens[0], array('constructor', 'function', 'method')),
        sprintf('Subroutine declaration "%s" is incorrect, must be either constructor, function or method', $tokens[0][TOKEN_TEXT]));

    $this->check(JackTokenizer::isTypeOrVoid($tokens[1]),
        'Class variable type must be a valid primitive type, void or identifier of a class');

    $this->check(JackTokenizer::isIdentifier($tokens[2]),
        sprintf('%s is not a valid identifier for subroutine method', $tokens[2][TOKEN_TYPE])); 

    $this->check(JackTokenizer::isSymbol($tokens[3], '('), 'Missing ( symbol for subroutine declaration');

    //
    $this->XML_enterChildNode('subroutineDec');
    $this->writeTokenData(array_slice($tokens, 0, 4));

    $position = 4; 

    $this->symbol_table->resetSubroutineTable();

    // Because this = arg[0], then arg[1] = arg[0], arg[2] = arg[1], ... (for methods)
    // So all indexes for arguments now need to be shifted up by one
    if ($tokens[0][TOKEN_TEXT] == 'method')
        $this->symbol_table->incrementIndex(KIND_ARG);

    // Compile parameter list
    $paramlist_length = $this->compileParameterList(array_slice($tokens, $position));
    $position += $paramlist_length;

    $this->check(JackTokenizer::isSymbol($tokens[$position], ')'), 'Missing ) symbol for subroutine declaration');
    $this->writeTokenData(array($tokens[$position]));
    $position += 1; 


    // Compile subroutine body
    $this->check(JackTokenizer::isSymbol($tokens[$position], '{'), 'Subroutine body is missing { symbol');
    $position += 1; 

    $this->XML_enterChildNode('subroutineBody');
    $this->writeTokenData(array($tokens[$position - 1]));

    $length = count($tokens);
    $function_declaration_written = false; 
    $vm_function_name = $this->registry['className'] . '.' . $tokens[2][TOKEN_TEXT];


    // Check for local variable declarations and statements
    while ($position < $length)
    {
        $token_args = array_slice($tokens, $position);

        if (JackTokenizer::isKeyword($tokens[$position], 'var'))
        {
            $var_length = $this->compileVarDec($token_args);
            $position += $var_length; 
        }

        else if (JackTokenizer::isKeyword($tokens[$position], array('do', 'if', 'while', 'return', 'let')))
        {
            // If we detect an expression, that signals the end of local variable declarations
            // in the current function. If the VM function declaration has not been written yet,
            // then declare the function. 

            if (!$function_declaration_written)
            {
                $function_declaration_written = true;  
                $this->VM_writeFunctionDeclaration($vm_function_name, $tokens[0][TOKEN_TEXT]);
            }

            $statements_length = $this->compileStatements($token_args);
            $position += $statements_length; 
        }

        else
        {
            break;
        }
    }


    // If there are no statements in the function, then the function declaration will not have been written
    // So check again after the subroutine body has been processed
    if (!$function_declaration_written)
    {
        $function_declaration_written = true;  
        $this->VM_writeFunctionDeclaration($vm_function_name, $tokens[0][TOKEN_TEXT]);
    }


    $this->check(JackTokenizer::isSymbol($tokens[$position], '}'), 'Subroutine body is missing } symbol');
    $this->writeTokenData(array($tokens[$position]));
    $position += 1; 

    $this->XML_returnToParent();
    $this->XML_returnToParent();

    return $position; 
}


// Compiles a parameter list for a method
private function compileParameterList($tokens)
{
    $this->XML_enterChildNode('parameterList');

    $length = count($tokens);
    $position = 0; 
    $comma_needed = false; 
    $type_on = false; 

    for ($c = 0; $c < $length; $c++)
    {
        if ($comma_needed && JackTokenizer::isSymbol($tokens[$c], ','))
        {
            $comma_needed = false;
            $position++;
        }

        else if (!$comma_needed && !$type_on && JackTokenizer::isTypeOrVoid($tokens[$c]))
        {
            $type_on = true;
            $position++;
        }

        else if (!$comma_needed && $type_on && JackTokenizer::isIdentifier($tokens[$c]))
        {
            $comma_needed = true; 
            $type_on = false; 
            $position++; 

            // Add variable to symbol table
            $this->symbol_table->define($tokens[$c][TOKEN_TEXT], $tokens[$c-1][TOKEN_TEXT], KIND_ARG);
        }

        else
        {
            break; 
        }
    }

    $this->check(!$type_on, 'Trailing comma or type expression at end of parameter list');

    $this->writeTokenData(array_slice($tokens, 0, $position));
    $this->XML_returnToParent();

    return $position;
}


// Compiles a variable declaration
private function compileVarDec($tokens)
{
    $this->check(JackTokenizer::isKeyword($tokens[0], 'var'), 'Variable declarations must start with "var" keyword');
    $this->check(JackTokenizer::isType($tokens[1]), 'Type in variable declaration is not a valid type');
    $this->check(JackTokenizer::isIdentifier($tokens[2]), 'First variable in var declaration is not a valid identifier');

    $this->XML_enterChildNode('varDec');

    $length = count($tokens);
    $position = 2; 
    $comma_needed = false;

    for ($c = $position; $c < $length && $tokens[$c][TOKEN_TEXT] != ';'; $c++)
    {
        if (!$comma_needed && JackTokenizer::isIdentifier($tokens[$c]))
        {
            $comma_needed = true; 
            $position++; 

            // Add variable to symbol table
            $this->symbol_table->define($tokens[$c][TOKEN_TEXT], $tokens[1][TOKEN_TEXT], KIND_VAR);
        }

        else if ($comma_needed && JackTokenizer::isSymbol($tokens[$c], ','))
        {
            $comma_needed = false; 
            $position++; 
        }

        else
        {
            break;
        }
    }

    $this->check($comma_needed, 'Trailing comma at end of variable declaration');

    $this->check(JackTokenizer::isSymbol($tokens[$position], ';'), 'Variable declaration must end with a semicolon');
    $position += 1; 

    $this->writeTokenData(array_slice($tokens, 0, $position));
    $this->XML_returnToParent();

    return $position; 
}


// Compiles a sequence of statements
private function compileStatements($tokens)
{
    $this->XML_enterChildNode('statements');

    $length = count($tokens);
    $position = 0;

    while ($position < $length)
    {
        // If a statement keyword is detected, then process that statement and update the position pointer to the next statement
        if (JackTokenizer::isKeyword($tokens[$position], array('let', 'if', 'while', 'do', 'return')))
        {
            $function_name = 'compile' . ucwords($tokens[$position][TOKEN_TEXT]);
            $statement_length = call_user_func_array(array($this, $function_name), array(array_slice($tokens, $position)));
            $position += $statement_length; 

        }

        // If the entry is not a valid statement keyword, then there are no more statements to compile
        else
        {
            break;
        }
    }

    $this->XML_returnToParent();

    return $position; 
}


// Compiles a let statement
private function compileLet($tokens)
{
    $this->check(JackTokenizer::isKeyword($tokens[0], 'let'), 'Let statement must begin with keyword let');
    $this->check(JackTokenizer::isIdentifier($tokens[1]), 'Invalid identifier for variable name in let statement');

    $this->XML_enterChildNode('letStatement');
    $this->writeTokenData(array_slice($tokens, 0, 2));

    $position = 2; 
    $has_index = false; 
    $text = $tokens[1][TOKEN_TEXT]; 

    $kind_to_segment = array(
        KIND_STATIC => SEGMENT_STATIC,
        KIND_FIELD => SEGMENT_THIS,
        KIND_VAR => SEGMENT_LCL, 
        KIND_ARG => SEGMENT_ARG
    );


    // Check for indexing
    if (JackTokenizer::isSymbol($tokens[$position], '['))
    {
        $this->writeTokenData(array($tokens[$position]));
        $position += 1; 
        $has_index = true; 

        $this->vm->writePush($kind_to_segment[$this->symbol_table->kindOf($text)], $this->symbol_table->indexOf($text));
        $position += $this->compileExpression(array_slice($tokens, $position)); 

        $this->vm->writeArithmetic(COMMAND_ADD);
        $this->vm->writePop(SEGMENT_TEMP, 1);

        $this->check(JackTokenizer::isSymbol($tokens[$position], ']'), 'Let statement is missing ] symbol after index expression'); 
        $this->writeTokenData(array($tokens[$position]));

        $position += 1; 
    }

    $this->check(JackTokenizer::isSymbol($tokens[$position], '='), 'Missing or misplaced = symbol in let statement');
    $this->writeTokenData(array($tokens[$position]));
    $position += 1; 

    $position += $this->compileExpression(array_slice($tokens, $position));

    $this->check(JackTokenizer::isSymbol($tokens[$position], ';'), 'Missing semicolon at end of let statement');
    $this->writeTokenData(array($tokens[$position]));
    $position += 1; 


    // Store the result in the variable (VM)
    if ($has_index)
    {
        $this->vm->writePush(SEGMENT_TEMP, 1);
        $this->vm->writePop(SEGMENT_POINTER, 1);
        $this->vm->writePop(SEGMENT_THAT, 0);
    }
    else
    {   
        $this->vm->writePop($kind_to_segment[$this->symbol_table->kindOf($text)], $this->symbol_table->indexOf($text));
    }

    $this->XML_returnToParent();

    return $position; 
}


// Compiles a while statement
private function compileWhile($tokens)
{
    $this->check(JackTokenizer::isKeyword($tokens[0], 'while'), 'While statement must begin with keyword while');
    $this->check(JackTokenizer::isSymbol($tokens[1], '('), 'Missing ( symbol for start of expression in while statement');

    $this->XML_enterChildNode('whileStatement');
    $this->writeTokenData(array_slice($tokens, 0, 2));

    $id = uniqid();
    $loop_id = sprintf('WHILE_LOOP_%s', $id);
    $end_id = sprintf('WHILE_END_%s', $id);

    $this->vm->writeLabel($loop_id);

    // Compile while expression
    $position = 2; 
    $position += $this->compileExpression(array_slice($tokens, $position)); 

    $this->check(JackTokenizer::isSymbol($tokens[$position], ')'), 'Missing ) symbol for end of expression in while statement');
    $this->writeTokenData(array($tokens[$position])); 
    $position += 1; 

    $this->vm->writeArithmetic(COMMAND_NOT);
    $this->vm->writeIfGoto($end_id);


    // Compile while statements
    $this->check(JackTokenizer::isSymbol($tokens[$position], '{'), 'Missing { symbol for start of statements in while statement');
    $this->writeTokenData(array($tokens[$position]));
    $position += 1; 

    $position += $this->compileStatements(array_slice($tokens, $position));

    $this->check(JackTokenizer::isSymbol($tokens[$position], '}'), 'Missing } symbol for end of statements in while statement');
    $this->writeTokenData(array($tokens[$position]));
    $position += 1; 

    $this->vm->writeGoto($loop_id);
    $this->vm->writeLabel($end_id);

    $this->XML_returnToParent(); 

    return $position; 
}


// Compiles a return statement
private function compileReturn($tokens)
{
    $this->check(JackTokenizer::isKeyword($tokens[0], 'return'), 'Return statement must begin with keyword return');

    $this->XML_enterChildNode('returnStatement');

    $this->writeTokenData(array($tokens[0]));
    $position = 1; 

    // If next token is a semicolon, then there is no expression to parse
    if (JackTokenizer::isSymbol($tokens[$position], ';'))
    {
        $this->writeTokenData(array($tokens[$position])); 
        $position += 1; 

        // If return statement has no arguments, then it is returning from a void function
        // In this case, we must manually push a constant zero onto the stack to be returned by the VM
        $this->vm->writePush(SEGMENT_CONSTANT, 0);
        $this->vm->writeReturn();
    }

    // Otherwise, parse the expression and check for a semicolon at the end
    else
    {
        $position += $this->compileExpression(array_slice($tokens, $position));

        $this->check(JackTokenizer::isSymbol($tokens[$position], ';'), 'Return statement is missing semicolon ending symbol');
        $this->writeTokenData(array($tokens[$position]));
        $position += 1; 

        // Write return statement (VM)
        $this->vm->writeReturn();
    }

    $this->XML_returnToParent();

    return $position; 
}


// Compiles an if statement
private function compileIf($tokens)
{
    $this->check(JackTokenizer::isKeyword($tokens[0], 'if'), 'If statement must begin with if keyword');
    $this->check(JackTokenizer::isSymbol($tokens[1], '('), 'If statement missing ( for start of expression in if clause');

    $this->XML_enterChildNode('ifStatement');
    $this->writeTokenData(array_slice($tokens, 0, 2));

    $id = uniqid();
    $else_id = sprintf('IF_ELSE_%s', $id);
    $end_id = sprintf('IF_END_%s', $id);


    // Compile the "if" clause
    $position = 2; 
    $position += $this->compileExpression(array_slice($tokens, $position));

    $this->vm->writeArithmetic(COMMAND_NOT);
    $this->vm->writeIfGoto($else_id);

    $this->check(JackTokenizer::isSymbol($tokens[$position], ')'), 'If statement missing ) for end of expression in if clause');
    $this->check(JackTokenizer::isSymbol($tokens[$position+1], '{'), 'If statement missing { for start of statements in if clause');

    $this->writeTokenData(array_slice($tokens, $position, 2)); 
    $position += 2; 

    $position += $this->compileStatements(array_slice($tokens, $position)); 

    $this->check(JackTokenizer::isSymbol($tokens[$position], '}'), 'If statement missing } for end of statements in if clause');
    $this->writeTokenData(array($tokens[$position]));

    $position += 1; 

    $this->vm->writeGoto($end_id);


    // Check for an "else" clause, and compile it if it exists
    $this->vm->writeLabel($else_id);

    if ($position < count($tokens) && JackTokenizer::isKeyword($tokens[$position], 'else'))
    {
        $this->check(JackTokenizer::isSymbol($tokens[$position+1], '{'), 'If statement missing { for start of statements in else clause');

        $this->writeTokenData(array($tokens[$position], $tokens[$position+1]));
        $position += 2; 

        $position += $this->compileStatements(array_slice($tokens, $position)); 

        $this->check(JackTokenizer::isSymbol($tokens[$position], '}'), 'If statement missing } for end of statements in else clause');
        $this->writeTokenData(array($tokens[$position]));

        $position += 1; 
    }

    $this->vm->writeLabel($end_id); 
    $this->XML_returnToParent();

    return $position; 
}


// Compiles an expression
private function compileExpression($tokens, $return_on_no_terms = false)
{
    $this->XML_enterChildNode('expression');


    // Check if first term exists and compile it if it does
    $term_length = $this->compileTerm($tokens);

    if ($term_length == 0 && $return_on_no_terms)
    {
        $this->XML_returnToParent();
        $this->XML_returnToParent();  // For some reason you need a second return-to-parent, not sure why

        return 0; 
    }

    $this->check($term_length > 0, 'Expression missing first term');

    $position = $term_length; 


    // If there are more entries in the form (op term), then compile them as well
    $length = count($tokens); 
    $op_used = false; 
    $last_op = ''; 

    $op_to_command = array(
        '+' => COMMAND_ADD,
        '-' => COMMAND_SUB,
        '*' => COMMAND_MUL,
        '/' => COMMAND_DIV,
        '=' => COMMAND_EQ,
        '>' => COMMAND_GT,
        '<' => COMMAND_LT,
        '&' => COMMAND_AND, 
        '|' => COMMAND_OR,
    );

    for (; $position < $length; $position++)
    {
        $token_args = array_slice($tokens, $position);

        // If an operator was found and there is no previous un-used operator, then compile it
        if (JackTokenizer::isOp($tokens[$position]) && !$op_used)
        {
            $this->writeTokenData(array($tokens[$position]));
            $op_used = true;
            $last_op = $tokens[$position][TOKEN_TEXT]; 
        }


        // If there is a previous un-used operator and a term is found, then compile the term
        else if ($op_used)
        {   
            $term_length = $this->compileTerm($token_args);
            $this->check($term_length > 0, 'Invalid additional term in expression');

            $position += $term_length - 1; 
            $op_used = false; 

            // Write arithmetic operation (VM)
            $this->vm->writeArithmetic($op_to_command[$last_op]);
            $last_op = ''; 
        }


        // If there is no operator and no term, then that signals the end of the expression
        else
        {
            break; 
        }
    }


    // If an operator was the last entry in the expression and it wasn't used, then that is a syntax error
    if ($this->write_xml) 
        $this->check(!$op_used, 'Syntax error in expression, operator cannot be the last entry');


    $this->XML_returnToParent();

    return $position; 
}


// Compiles a term for an expression
private function compileTerm($tokens)
{
    $this->XML_enterChildNode('term');

    $length = count($tokens);
    $position = 0; 

    // Integer constants, string constants and keyword constants
    if ($tokens[0][TOKEN_TYPE] == TOKENTYPE_INT_CONST || $tokens[0][TOKEN_TYPE] == TOKENTYPE_STRING_CONST
        || JackTokenizer::isKeywordConstant($tokens[0]))
    {
        $this->writeTokenData(array($tokens[0])); 
        $position += 1; 

        // Write constant (VM)
        if ($tokens[0][TOKEN_TYPE] == TOKENTYPE_INT_CONST)
        {
            $this->vm->writePush(SEGMENT_CONSTANT, $tokens[0][TOKEN_TEXT]);
        }

        else if ($tokens[0][TOKEN_TYPE] == TOKENTYPE_STRING_CONST)
        {
            $text = $tokens[0][TOKEN_TEXT];
            $length = strlen($text);

            $this->vm->writePush(SEGMENT_CONSTANT, $length);
            $this->vm->writeCall('String.new', 1);
            $this->vm->writePop(SEGMENT_TEMP, 1);

            for ($c = 0; $c < $length; $c++)
            {
                $this->vm->writePush(SEGMENT_TEMP, 1);
                $this->vm->writePush(SEGMENT_CONSTANT, ord($text[$c]));
                $this->vm->writeCall('String.appendChar', 2);
                $this->vm->writePop(SEGMENT_TEMP, 1); 
            }

            $this->vm->writePush(SEGMENT_TEMP, 1);
        }

        else
        {   
            $text = $tokens[0][TOKEN_TEXT]; 

            if ($text == 'null' || $text == 'false')
            {
                $this->vm->writePush(SEGMENT_CONSTANT, 0);
            }

            else if ($text == 'true') 
            {
                $this->vm->writePush(SEGMENT_CONSTANT, 1); 
                $this->vm->writeArithmetic(COMMAND_NEG);
            }

            else if ($text == 'this')
            {
                $this->vm->writePush(SEGMENT_POINTER, 0);
            }
        }
    }


    // varName, varName[expr], subroutineCall
    else if (JackTokenizer::isIdentifier($tokens[0]))
    {
        $kind_to_segment = array(
            KIND_STATIC => SEGMENT_STATIC,
            KIND_FIELD => SEGMENT_THIS,
            KIND_VAR => SEGMENT_LCL, 
            KIND_ARG => SEGMENT_ARG
        );


        // If next token is [ symbol, then it's a varName with an index
        if (JackTokenizer::isSymbol($tokens[1], '[') && $length >= 3)
        {
            $this->writeTokenData(array($tokens[0], $tokens[1]));
            $position += 2; 

            $text = $tokens[0][TOKEN_TEXT]; 
            $this->vm->writePush($kind_to_segment[$this->symbol_table->kindOf($text)], $this->symbol_table->indexOf($text));
            $position += $this->compileExpression(array_slice($tokens, $position));

            $this->vm->writeArithmetic(COMMAND_ADD);
            $this->vm->writePop(SEGMENT_POINTER, 1);
            $this->vm->writePush(SEGMENT_THAT, 0);

            $this->check(JackTokenizer::isSymbol($tokens[$position], ']'), 'End of index expression in term missing ] symbol');
            $this->writeTokenData(array($tokens[$position]));

            $position += 1; 
        }


        // If next token is ( or . symbol, then it's a subroutine call
        else if (JackTokenizer::isSymbol($tokens[1], array('(', '.')) && $length >= 3)
        {
            $position += $this->compileSubroutineCall($tokens); 
        }


        // Otherwise, it's just a regular varName
        else
        {
            $this->writeTokenData(array($tokens[0]));
            $position += 1;

            // Write varName (VM)
            $text = $tokens[0][TOKEN_TEXT]; 

            if (!$this->symbol_table->exists($text))
                trigger_error(sprintf('Variable "%s" used in expression does not exist', $text), E_USER_WARNING);

            $this->vm->writePush($kind_to_segment[$this->symbol_table->kindOf($text)], $this->symbol_table->indexOf($text));

        }
    }

    // (expr)
    else if (JackTokenizer::isSymbol($tokens[0], '(') && $length >= 2)
    {   
        $this->writeTokenData(array($tokens[0]));
        $position += 1; 

        $position += $this->compileExpression(array_slice($tokens, 1));

        $this->check(JackTokenizer::isSymbol($tokens[$position], ')'), 'End of expression in term missing ) symbol');
        $this->writeTokenData(array($tokens[$position]));

        $position += 1; 
    }


    // Term with a preceding unary operator
    else if (JackTokenizer::isUnaryOp($tokens[0]) && $length >= 2)
    {
        $this->writeTokenData(array($tokens[0]));
        $token_args = array_slice($tokens, 1); 

        $term_length = $this->compileTerm($token_args);
        $this->check($term_length > 0, 'Invalid sub-term after unary operator in term');

        $position += 1 + $term_length; 

        // Write term (VM)
        $this->vm->writeArithmetic($tokens[0][TOKEN_TEXT] == '-' ? COMMAND_NEG : COMMAND_NOT);
    }

    $this->XML_returnToParent(); 

    return $position; 
}

Answer 1

Alright, I'm not going to pretend I understand what's going on here. First, there's just too much. Second, I don't know Jack about Jack, all puns intended. I'm only going to do a once over on this. Usually I'm a bit more thorough, but you have entirely too much here. And by that I mean you really need to break this up into tinier, more efficient, classes.

First thing, since this is something that is going to be shared (you mentioned a book), then you should use proper PHPDoc as if this were a traditional API. Will make importing this into an IDE much easier and make documentation easier too. I'll demonstrate with your properties and constructor.

private
    /** Token list to operate on */
    $tokens,
    /** Symbol table that stores all identifiers */
    $symbol_table,
    //etc...
    /** Array of parent XML objects */
    $parent_xml
;

/** Initializes the CompilationEngine object with a list of tokens
  *
  * @param array Token list to operate on
  */
public function __construct($tokens)

You can assign default property values when initially declaring the property, no need to clutter the constructor. For instance, $write_xml and $write_vm are both statically set to FALSE, so they could easily be moved into the initial declaration. There are more, these are just two.

This for loop looks like the $token array should have been a multidimensional associative array. Some things I'm seeing later on seem to confirm this suspicion. This would make needing to check for every two elements unnecessary, I'm assuming these are parameters or something? Ideally, you would want to look at changing this, if possible. I'm not sure of the source, so maybe not.

If setWriteXML() is just a toggle, why accept a flag? Same for vm. Just toggle it.

public function setWriteXML() {
    $this->write_xml = ! $this->write_xml;
}

I would try to avoid braceless statements. They can cause confusion and can lead to mistakes. This isn't Python so the syntax is inherently necessary. Maybe, as people are starting to point out to me, this is a stylistic choice, but I believe its one PHP should not have introduced, at least not halfheartedly as they have.

You should remain consistent in your style. CamelCase or Under_Score, at least for the same data type. You can switch between them for methods and variables if you want, but methods should be identical in style to other methods, as should variables. For instance, you have combined camelcase and underscore with your XML prefixed methods, all other methods are camelcase only. Also, because of the wide usage of this prefix, and other prefixes, I think this is pretty indicative of a need for a new class. You are essentially namespacing your methods.

Why are you using sprintf? Yes, its fine and dandy for templating larger strings, but for simpler strings you can just concatenate. Much quicker, and cleaner, and less overhead.

trigger_error( "CompilationEngine: $message", E_USER_WARNING );

I can't decide if these all caps words are constants, or just WANT to be constants. They aren't defined here, so I can't be sure. If you have them defined as constants somewhere you can skip over this section. If these aren't constants, PHP is throwing silent warnings every time this comes up saying that these are "Undefined, assuming 'TOKENTYPE_KEYWORD'". Meaning its using these as strings. If you want to use them as strings, make them strings, if you want to use them as constants, make them constants. Unless these are PHP constants, then continue.

"Don't Repeat Yourself" (DRY) Principle. Your compile() method is repeating itself, moving the xml and vm out of this class and into their own will help, but you will still need to avoid calling the functions more than once.

$xml = $this->write_xml ? $this->xml->asXML() : '';
$vm = $this->write_vm ? implode( "\n", $this->vm->getCode() ) : '';

if( $xml && $vm ) {
    return compact( 'xml', 'vm' );
} else if( $xml || $vm ) {
    return $xml . $vm;//one's empty, so concatenating won't hurt
}

Another DRY violation. You have at least two methods that have $isCommaNeeded routines that appear to be almost identical. Try combining these into a new method where you can.

And another. You use a similar routine each time you iterate over the tokens. Make this a method.

$this->check(JackTokenizer::isSymbol($tokens[$position], '}'), 'Missing } symbol for end of statements in while statement');
$this->writeTokenData(array($tokens[$position]));
$position += 1; 

I stopped about here, I'm starting to get lost in your code. I would suggest, if you take nothing else from this review, that you split this class up into more logical subclasses. Your "namespacing" should help you get started. Another suggestion, put this on github or something. You are liable to get a lot of help there. And let me know if you do, I might just stop by, been trying to convince myself to get into that side of things anyways.

Answer 2

Needs more classes, this one class does too many different things.

Firstly, I'd suggest a Scanner class. This class will hold the array of tokens and the current position. It will then also have a number of methods to operate on it. It'll also keep track of errors during the parsing process. Here is one of your functions as I'd rewrite it, (skipping XML for now)

private function compileClassVarDec($scanner)
{

    $field_scope = $scanner->matchKeyword( array('static','field') );
    $field_scope = $field_scope == 'static' ? KIND_STATIC : KIND_FIELD;
    $field_type = $scanner->matchType();
    // the match* functions increment the position, and record errors
    // if the provided tokens did not actually match

    while(true)
    {
         $identifier = $scanner->matchIdentifier();
         $this->symbol_table->define($identifier, $field_type, $field_scope);

         if( $scanner->isSymbol(",") )
         {
             $scanner->matchSymbol(",");
         }else{
             break;
         }
    }

    $scanner->matchSymbol(";");
}

I think a scanner class would really help clean up the parsing code.

Next, I'd have this class solely worry about parsing, not generating the code or the xml. I'd have it generate an AST, which you could then pass either to a XML dumper or a code generator class. I'd have a seperate AST class to handle the generation logic, and do something like this:

private function compileSubroutine($scanner)
{

    $this->ast->pushScope('subroutineDec', $scanner);
    // pushScope records the current position for later

    $this->ast->attribute('category', $scanner->matchKeyword( array('constructor', 'function', 'method') ));
    $this->ast->attribute('type', $scanner->matchType());
    $this->ast->attribute('name' $scanner->matchIdentifier());
    $scanner->matchSymbol('(');
    $this->ast->attribut('parameterlist', $this->parseParameterList($scanner));    
    $scanner->matchSymbol(')');
    $scanner->matchSymbol('{');
    $this->parseBody($scanner);
    $scanner->matchSymbol('}');

    $this->ast->popScope($scanner); // records ending position
}