<!--  // Hide this just in case this file is read as HTML

// *****************************************************************
// PARSER.JS
// Requires Stack.js and misc.js
// *****************************************************************
// Parser()
// parse(lexObj): parses a LL(1) grammar using tokens returned from lexObj
//		lexObj.nextToken() should return the next token
//
// Contains ParseNode, Token, ParseTable, ParseGrammar objects
// ***************************************************************** 

// *****************************************************************
// Data structure for a parse tree
// *****************************************************************

function ParseNode(type, value)
{
	// This objects represents one entry in the parse tree

	// type is either TERMINAL, NONTERMINAL, or ACTION
	//
	// value for terminals stores the the token representing the terminal

	// value for nonterminals stores a unique string which only purpose is
	// to be used for looking up in parseTable (associative array)

	// value for actions store a pointer to a function
	// if this function returns false, then the parsing process will be aborted
	// the function isn't given any arguments but "this" inside the function
	// will refer to the current parse node

	this.type = type;
	this.value = value;

	// attribute field to store user information during the parse
	this.attribute = null;

	// terminals have a token field
	// this is set by the parser with the actual token that is read from input stream
	this.token = null;

	// nonterminals have a children field that is an array of parseNodes
	// these are maintained consistent by the parser
	this.children = null;	// array of ParseNodes
	this.parent = null;		// a ParseNode
	this.childNumber = -1;	// this == this.parent.children[childNumber]

	this.getRelativeSibling = getRelativeSibling;
	this.clone = copyParseNode;
	this.toString = parseNodeToString;
}

function getRelativeSibling(delta_sibling)
{
	// returns a RELATIVE sibling of this one
	// for example, if this is child number 3
	// and delta_sibling = -1, then this will return
	// the 2nd child of this node's parent
	// this == getRelativeSibling(0)
	return (this.parent.children[this.childNumber + delta_sibling]);
}

function copyParseNode()
{
	// returns a copy of the main fields of this parse node
	// these are the fields that may not depend on one particular parse
	// i.e. ignore attribute and other fields like that
	var newParseNode = new ParseNode(this.type, this.value);
	return (newParseNode);
}

function parseNodeToString()
{
	return (this.value);
}

// *****************************************************************
// Token object
// *****************************************************************

function Token()
{
	// Token constructor

	// If one argument is given then it is another token object to be copied
	// If two arguments are given, then format is Token(type, value)
	// and if no arguments are given, then a default is used.

	// Initialize data members of token type

	// if arguments are given, the token is initialized to those values
	if (arguments.length > 0)
	{
		if (arguments.length == 1)
		{
			tokObj = arguments[0];	// copy constructor
			this.type = tokObj.type;
			this.value = tokObj.value;
		}
		else
		{
			// two arguments should have been passed
			this.type = arguments[0];
			this.value = arguments[1];
		}
	}
	else
	{
		this.type = null;
		this.value = null;
	}

	this.toString = tokenToString;
	this.getValue = tokenGetValue;
	this.equals = tokenEquals;
}

function tokenToString()
{
	return ("token type: (" + this.type + "), value: (" + this.value + ")");
}

function tokenGetValue()
{
	// returns value if not-null
	// otherwise returns type
	if (this.value != null)
	{
		// to solve problem of nested tokens
		if (this.value.getValue)
			return (this.value.getValue());
		else
			return (this.value);
	}
	else
		return (this.type);
}

function tokenEquals(obj)
{
	// return true if the other object is a token and type and value fields are the same

	// first make sure the object is a token
	if (obj.equals != tokenEquals)
		return (false);

	return ((this.type == obj.type) && (this.value == obj.value));
}

// *****************************************************************
// Parse Table
//
// a parse table is an associative array of associative arrays
//
// table[nonterminal][terminal] is an array of ParseNodes
// nonterminal is a ParseNode object. terminal is a token type
// *****************************************************************

function ParseTable(table, start)
{
    this.table = table;
    this.start = start;

    this.toString = parseTableToString;
}

function parseTableToString()
{
    // go through the table

    var numEntries = 0;
    var str = "";
    for (var nonterm in this.table)
    {
        for (var term in this.table[nonterm])
        {
            var rule = this.table[nonterm][term];
            str += "[ " + nonterm + " , " + term + " ] = ";
            for (var i = 0; i < rule.length; i++)
            {
                // don't print actions
                if (rule[i].type == ACTION)
                {
                    str += "<action> ";
                }
                else 
                {
                    str += rule[i] + " ";
                }
            }
            str += "\n";
            numEntries++;
        }
    }

    str += numEntries + " entries in table\n";

    return str;
}

// *****************************************************************
// ParseGrammar
// Functions to help generate ParseTables from LL(1) grammars
// *****************************************************************

function ParseGrammar(grammar, start)
{
    // start is starting nonterminal for the grammar
    this.grammar = grammar;
    this.start = start;

    // generate the parse table
    this.generateTable = parseGrammarGenerateTable;
    this.addTableEntry = parseGrammarAddEntry;

    // remove left recursion and left factor
    this.eliminateLeftRecursion = parseGrammarEliminateLeftRecursion;
    this.eliminateDirectLeftRecursion = parseGrammarEliminateDirectLeftRecursion;
    this.leftFactor = parseGrammarLeftFactor;
    this.leftFactorNonterm = parseGrammarLeftFactorNonterm;
    this.newNonterm = parseGrammarNewNonterm;
    this.makeLL = parseGrammarMakeLL;

    this.toString = parseGrammarToString;
}

function parseGrammarToString()
{

    var numEntries = 0;
    var str = "";
    for (var nonterm in this.grammar)
    {
        var rules = this.grammar[nonterm];
        for (var i = 0; i < rules.length; i++)
        {
            var rule = rules[i];
            str += nonterm + " -> ";
            for (var j = 0; j < rule.length; j++)
            {
                // don't print actions
                if ((rule[j].type == TERMINAL) || (rule[j].type == NONTERMINAL))
                {
                    str += rule[j] + " ";
                }
            }
            str += "\n";
            numEntries++;
        }
    }

    str += numEntries + " rules in grammar\n";

    return str;
}

function parseGrammarMakeLL()
{
    // does best job it can to make the grammar into LL(1)
    this.eliminateLeftRecursion();
    this.leftFactor();
}

function parseGrammarAddEntry(nonterm, input, rule, conflictFn)
{
    if (this.table[nonterm][input] && this.table[nonterm][input] != rule)
    {
        // conflict. two different rules for same spot
        if (conflictFn)
        {
            var resolve = conflictFn(nonterm, input, this.table[nonterm][input], rule);
            if (resolve)
            {
                if (this.table[nonterm][input] != resolve)
                {
                    this.table[nonterm][input] = resolve;
                    return true;
                }
                else
                    return false;
            }
        }
        assert(0, parseGrammarAddEntry, "conflict for " + nonterm + "," + input + " not resolved");
    }
    else if (!this.table[nonterm][input])
    {

        this.table[nonterm][input] = rule;
        this.first[nonterm][input] = true;
        return true;
    }

    return false;
}

function parseGrammarGenerateTable(conflictFn)
{
    // generate parse table from grammar
    // conflictFn will be called if there is a conflict in generating
    // the parse table from the grammar allowing the function to decide
    // what to do
    // ref: http://home.earthlink.net/~parsersinc/doc/ll1parse.html

    this.first = new Array();
    // set of nonterminals that have the empty string in their first set
    this.nullable = new Array(); 
    this.follow = new Array();

    // generate table while calculating the first/follow sets
    this.table = new Array();

    // initialize arrays
    for (var nonterm in this.grammar)
    {
        this.table[nonterm] = new Array();
        this.first[nonterm] = new Array();
        this.follow[nonterm] = new Array();
    }

    this.follow[this.start][PARSE_END_INPUT] = true;


    // generate first and follow sets and create the table together in one loop
    // this is guaranteed to terminate as the loop can only continue if the
    // tables get larger and there is a finite size for that
    // it should be correct for good LL(1) grammar but for bad grammars, 
    // e.g. S->Sa that is not well defined but we won't get an error
    var changed = true;
    while (changed)
    {
        changed = false;

        // iterate through all productions in grammar
        for (var nonterm in this.grammar)
        {
            rules = this.grammar[nonterm];
            for (var i = 0; i < rules.length; i++)
            {
                var rule = rules[i];

                var donefirst = false;
                var j = 0;

                // go through each symbol in the rule
                for (j = 0; j <= rule.length; j++)
                {

                    // update follow sets for nonterminals
                    if (j < rule.length && rule[j].type == NONTERMINAL)
                    {
                        var addfollow = new Array();
                        var next = i + 1;
                        if (j == rule.length-1)
                        {
                            // last symbol. add Follow(nonterm)
                            addfollow = this.follow[nonterm];
                        }
                        else
                        {
                            // add First() of next symbol to Follow
                            var nextsym = rule[j+1];
                            if (nextsym.type == TERMINAL)
                            {
                                addfollow[nextsym] = true;
                            }
                            else if (nextsym.type == NONTERMINAL)
                            {
                                addfollow = this.first[nextsym];
                                
                                if (this.nullable[nextsym])
                                {
                                    // add follow of nextsym
                                    for (var k in this.follow[nextsym])
                                    {
                                        addfollow[k] = true;
                                    }
                                }
                            }
                        }
                        
                        // add to the follow set
                        for (var k in addfollow)
                        {
                            if (! this.follow[rule[j]][k])
                            {
                                this.follow[rule[j]][k] = true;
                                changed = true;
                            }
                        }
                    }

                    // update first sets
                    if (!donefirst)
                    {
                        donefirst = true;

                        if (j == rule.length)
                        {
                            // can null this nonterm
                            if (! this.nullable[nonterm] )
                            {
                                this.nullable[nonterm] = true;
                                changed = true;
                            }
                            for (var k in this.follow[nonterm])
                            {
                                changed = this.addTableEntry(nonterm, k, rule, conflictFn) || changed;
                            }
                        }
                        else
                        {
                            var sym = rule[j];
                            if (sym.type == NONTERMINAL)
                            {
                                // add everything in first for the nonterminal to this one
                                for (var k in this.first[sym])
                                {
                                    changed = this.addTableEntry(nonterm, k, rule, conflictFn) || changed;
                                }

                                if (this.nullable[sym])
                                {
                                    // if nullable, then have to go check next symbol
                                    donefirst = false;
                                }
                            }
                            else if (sym.type == TERMINAL)
                            {
                                changed = this.addTableEntry(nonterm, sym, rule, conflictFn) || changed;
                            }
                        }
                    }
                }
            }
        }
    }

    return new ParseTable(this.table, this.start);
}

function parseGrammarNewNonterm(original)
{
    // return an unused nonterminal based on original
    var newnonterm = original;

    while (this.grammar[newnonterm])
    {
        newnonterm = newnonterm + "'";
    }

    return newnonterm;
}

function parseGrammarLeftFactorNonterm(nonterm)
{
    // find common prefixes
    var rules = this.grammar[nonterm];
    var prefixes = new Array();
    var common = new Array();
    var newnonterm = new Array();
    var newrules = new Array();
    for (var i = 0; i < rules.length; i++)
    {
        var rule = rules[i];
        if (rule.length == 0)
        {
            // empty rule
        }
        else if (prefixes[rule[0]])
        {
            // have to factor. do most of the work later
            if (! common[rule[0]] )
            {
                common[rule[0]] = rule[0];
                newnonterm[rule[0]] = this.newNonterm(nonterm);
                newrules[rule[0]] = new Array();

            }
        }
        else
        {
            prefixes[rule[0]] = rule;
        }
    }

    // factor everything in common
    var oldrules = new Array();
    for (var i = 0; i < rules.length; i++)
    {
        // find all rules that begin with a common symbol
        var rule = rules[i];
        if (rule.length != 0 && common[rule[0]])
        {
            // factor this into the new nonterminal
            var sym = rule[0];
            var newrule = new Array();
            arraycopy(rule, 1, newrule, 0);
            newrules[sym][newrules[sym].length] = newrule;
        }
        else
        {
            // keep this rule
            oldrules[oldrules.length] = rule;
        }
    }

    // add all the factored rules
    for (var sym in common)
    {
        oldrules[oldrules.length] = new Array(common[sym], new ParseNode(NONTERMINAL, newnonterm[sym]));
        this.grammar[newnonterm[sym]] = newrules[sym];

        // factor the new nonterminal
        this.leftFactorNonterm(newnonterm[sym]);
    }

    this.grammar[nonterm] = oldrules;
}

function parseGrammarLeftFactor()
{
    for (var nonterm in this.grammar)
    {
        this.leftFactorNonterm(nonterm);
    }
}

function parseGrammarEliminateDirectLeftRecursion(nonterm)
{
    // eliminate all rules of form nonterm -> nonterm alpha
    var rules = this.grammar[nonterm];
    var recursive = new Array();
    var nonrecursive = new Array();
    for (var i = 0; i < rules.length; i++)
    {
        var rule = rules[i];
        if (rule.length != 0 && rule[0] == nonterm)
        {
            recursive[recursive.length] = rule;
        }
        else
        {
            nonrecursive[nonrecursive.length] = rule;
        }
    }

    if (recursive.length != 0)
    {
        // have recursion
        var newnonterm = this.newNonterm(nonterm);
        var newparsenode = new ParseNode(NONTERMINAL, newnonterm);
        var rules = new Array();
        for (var i = 0; i < nonrecursive.length; i++)
        {
            // have to be at least one, other grammar wouldn't have been valid
            var rule = nonrecursive[i];
            rule[rule.length] = newparsenode;
            rules[rules.length] = rule;
        }
        this.grammar[nonterm] = rules;

        rules = new Array();
        for (var i = 0; i < recursive.length; i++)
        {
            var rule = recursive[i];
            var newrule = new Array();
            arraycopy(rule, 1, newrule, 0);
            newrule[newrule.length] = newparsenode;
            rules[rules.length] = newrule;
        }
        // add an -> epsilon production
        rules[rules.length] = new Array();
        this.grammar[newnonterm] = rules;
    }
}

function parseGrammarEliminateLeftRecursion()
{
    // eliminate all direct/indirect left recursion
    // assumes the grammar has no cycles and there are no epsilon-productions

    // put the non-terminals into some order
    var nonterms = new Array();
    var num = 1;
    for (var nonterm in this.grammar)
    {
        nonterms[nonterm] = num;
        num++;
    }

    var rules;
    var newrules;
    for (var nonterm in nonterms)
    {
        var i = nonterms[nonterm];
        rules = this.grammar[nonterm];

        newrules = new Array();
        for (var r = 0; r < rules.length; r++)
        {
            // replace all productions of form Ai -> Aj B by Ai -> C B where Aj->C
            // and j < i
            var rule = rules[r];
            if (rule.length != 0 && nonterms[rule[0]] && nonterms[rule[0]] < i)
            {
                // production of form Ai -> Aj B
                var j = nonterms[rule[0]];
                var replacerules = this.grammar[rule[0]];
                var B = new Array();
                arraycopy(rule, 1, B, 0);
                for (var l = 0; l < replacerules.length; l++)
                {
                    newrules[newrules.length] = arrayappend(replacerules[l], B);
                }
            }
            else
            {
                newrules[newrules.length] = rule;
            }
        }

        this.grammar[nonterm] = newrules;

        // replace direct left recursion productions
        this.eliminateDirectLeftRecursion(nonterm);
    }
}

function parseGrammarEliminateEpsilons()
{
    // remove empty productions
    // *** TODO
}

// *****************************************************************
// The Parser
// *****************************************************************

// Parser constants

var PARSE_END_INPUT = "$END$";

// These tell the parser what to do during parsing
var TERMINAL = 0;
var NONTERMINAL = 1;
var ACTION = 2;

function Parser(parseTable, parseError, beginParse, endParse)
{
	// creates a parser with the given options

	// this table drives the whole parsing process
	this.parseTable = parseTable;

	this.endOfInputToken = new Token(PARSE_END_INPUT, "end of input");

	// this is function to call on parse error
	if ((arguments.length < 2) || (parseError == null))
		this.parseError = defaultParseError;
	else
		this.parseError = parseError;

	// this is function to call before every parse
	if ((arguments.length < 3) || (beginParse == null))
		this.beginParse = defaultBeginParse;
	else
		this.beginParse = beginParse;

	// this is function to call after every parse
	if ((arguments.length < 4) || (endParse == null))
		this.endParse = defaultEndParse;
	else
		this.endParse = endParse;

	this.parse = doParse;		// entry point for the actual parsing
}

// These are default functions that don't do much
// These defaults can be overrided by defining another function with the same name
function defaultBeginParse()
{
}

// Called at end of a successful parse
// parseTree is the parseTree of the parse
// the value returned from this function will be what is returned
// from the call to parse()
// default is to just return the parseTree
function defaultEndParse(parseTree)
{
	return (parseTree);
}

function defaultParseError(errorMsg)
{
}

// The array of ParseNodes are put on to the stack in the given order
// (that is, the first element of the array will be on the top of the stack)
// parsing goes through the stack until it is empty
// Note that the array can be empty which therefore performs something
// like X->*empty*.
//
// if the top of the stack is a NONTERMINAL, then it pops it and the 
// NONTERMINAL node is used in conjunction with parseTable
// to find the next thing to push on to the stack. 
//
// If the top of the stack is a TERMINAL, the type of the parse node
// must match the type of the lookahead token or a parse error occurs. 
// If it matches, the token for the parseNode is set to the lookahead token.
//
// If the top of the stack is an ACTION, then the function corresponding
// to the action is called. If this function returns false, stop parsing
//
// When the end of input is reached, parseTable[X][PARSE_END_INPUT] is
// done for all X remaining on the stack. If the stack does not
// end up being empty then a parse error has occurred.
//
// I have now added automatically passing up of attributes
// After finishing parsing each array, there is an implicit passing up
// to the parent of attributes. It works as follows. First, the parent
// attribute must be null. Otherwise, nothing is done. If the parent
// attribute is null, the LAST child with a non-null attribute has its
// attribute copied to the parent. If there are no children with attributes
// then again nothing is done.

function doParse(lexObj)
{
	// lexObj should be an object
	// lexObj.nextToken() should return the next token
	// lexObj.nextToken() should return false if error occurs
	// and it should return null if there is no more input

	// Parses the given string and returns a parse tree (ParseNode object)
	// Returns null on parse errors

	var parseStack = new Stack();
	var parseTree = this.parseTable.start.clone();
	var currentNode;
	var lookahead;
	var nextNodes;
	var passAttributeNode;
	var tempNodeArray;
	var i;

	this.beginParse();

	lookahead = lexObj.nextToken();

	if (lookahead == false)
		return (null);		// error in lexical analyzer
	else if (lookahead == null)
	{
		// means there was no input!
		// set to this.endOfInputToken and will stay this way
		// until stack is empty or error occurs
		lookahead = this.endOfInputToken;
	}

	// push the first ParseNode on to the stack
	// and begin parsing
	parseStack.push(parseTree);

	while (!parseStack.isEmpty())
	{
		// get the current node that we're on
		currentNode = parseStack.pop();

//		alert(currentNode);	// debugging

		if (currentNode.type == NONTERMINAL)
		{
			var entry = this.parseTable.table[currentNode];

			// should be in the parse table
			if (!entry)
			{
				assert(0, "doParse", "invalid nonterminal '" + currentNode.value + "'.");
				return (null);
			}

			nextNodes = entry[lookahead.type];

			if (!nextNodes)
			{
				// nothing was found in the table
				this.parseError("Unexpected '" + lookahead.getValue() + "'.");
				return (null);
			}

			// add the next nodes to be added as children of the current
			// node and also add it to the parse stack

			// need to make a copy of each ParseNode in the array
			tempNodeArray = new Array(nextNodes.length);

			for (i = 0; i < nextNodes.length; i++)
			{
				tempNodeArray[i] = nextNodes[i].clone();
				tempNodeArray[i].parent = currentNode;
				tempNodeArray[i].childNumber = i;
			}

			currentNode.children = tempNodeArray;

			// 
			// Implementing auto pass up of attributes
			//
			// Add another parse node here that will be
			// parsed AFTER all other nodes at this layer
			// This node's parent is set to the currentNode
			// but we DON'T set this as one of the node's
			// children. Perhaps we are leaving it in an
			// inconsistent state, but from the outside,
			// we want to make sure this extra node is not visible.
			// we need to set the parent so the node will know
			// what to do in passUpAttribute()

			passAttributeNode = new ParseNode(ACTION, passUpAttribute);
			passAttributeNode.parent = currentNode;
			parseStack.push(passAttributeNode);

			// now push the other nodes on to the stack in reverse order so that
			// the first child will be on top of the stack
			parseStack.pushArray(tempNodeArray);
		}
		else if (currentNode.type == TERMINAL)
		{
			// must match the lookahead type
			if (currentNode.value != lookahead.type)
			{
				this.parseError("Parse error around '" + lookahead.getValue() + "'." +
							" Expected '" + currentNode.value + "'.");
				return (null);
			}
			else
			{
				// set the currentNode's token to the lookahead one
				// so now this node has the correct info about this parse
				currentNode.token = lookahead;

				// now get the next token
				lookahead = lexObj.nextToken();

				// note that null isn't the same as false!
				if (lookahead == false)
					return (null);	// error occurred in lexer
				else if (lookahead == null)
				{
					// means no more input
					// set to this.endOfInputToken and will stay this way
					// until stack is empty or error occurs
					lookahead = this.endOfInputToken;
				}
			}
		}
		else
		{
			// action
			// function has to return true for us to continue
			if (!currentNode.value())
				return (null);
		}
	}

	if (parseStack.isEmpty() && (lookahead != this.endOfInputToken))
	{
		this.parseError("Parse error around '" + lookahead.getValue() + "'.");
		return (null);
	}
	else
		return (this.endParse(parseTree));
}

function passUpAttribute()
{
	// parser now automatically passes up parse node attributes
	// for productions of the form A->BCD
	// assign A the value of D if it is defined. 
	// otherwise assign A the attribute of C if it is defined, etc.

	// don't do anything if parent already has an attribute
	if (this.parent.attribute != null)
		return (true);

	// find the last child with an attribute
	var child;
	var attribute;
	for (child = this.parent.children.length - 1; child >= 0; child--)
	{
		attribute = this.parent.children[child].attribute;
		if (attribute)
		{
			// bingo. found one
			this.parent.attribute = attribute;
			return (true);
		}
	}

	// no child found. oh well.
	return (true);
}

// Stop hiding -->