slrsyntaxnode.java

java 词法分析器,用于一般的C,C++,VB,PS/SQL 语句的翻译

package fri.patterns.interpreter.parsergenerator.parsertables;

import java.util.*;
import fri.patterns.interpreter.parsergenerator.Token;
import fri.patterns.interpreter.parsergenerator.ParserTables;
import fri.patterns.interpreter.parsergenerator.syntax.*;

/**
	SLR bottom-up parser syntax node.
	The build() method of an no-arg-constructed node is used to fill a
	state node list. The empty list passed to build() will be filled
	with all state nodes after.
	<p>
	Every syntax node provides a fill() method to populate the corresponding
	line (node-index) within PARSE-ACTION and GOTO tables.
	<p>
	After construction the syntax node has state entries represented by
	RuleStateItem instances.
	<p>
	The state of a rule is represented by a dot "." at start, between symbols,
	or at end. To shift an item means to move the dot to left.
	
	@author (c) 2000, Fritz Ritzberger
*/

class SLRSyntaxNode
{
	/** Contains all rule state entries. */
	protected Hashtable entries = new Hashtable();

	private int kernels = 0;
	private Integer hashCache = null;


	/** Do-nothing-constructor, used to call the build() method. */
	public SLRSyntaxNode()	{
	}
	
	/** Factory-method to create a SLRSyntaxNode, to be overridden by other node types. */
	protected SLRSyntaxNode createSyntaxNode()	{
		return new SLRSyntaxNode();
	}
	
	/** Factory-method to create a RuleStateItem, to be overridden by other node types. */
	protected RuleStateItem createRuleStateItem(int ruleIndex, Rule rule)	{
		return new RuleStateItem(ruleIndex, rule);
	}		


	/**
		Construction of start node and all further state nodes.
		After this call the syntaxNodes list is filled with all state-bound nodes.
		@param syntax the grammar, including START rule.
		@param syntaxNodes ampty list that holds all syntax nodes after this call.
		@param kernels empty hashtable for internal buffering.
		@return the syntaxNodes list, now filled.
	*/
	public List build(Syntax syntax, List syntaxNodes, Hashtable kernels)	{
		// insert first rule as state item
		RuleStateItem item = createRuleStateItem(0, syntax.getRule(0));
		entries.put(item, item);
		closure(syntax);	// calculate followers
		
		syntaxNodes.add(this);	// now add startnode to list of syntax nodes

		generateSyntaxNodes(syntaxNodes, syntax, kernels);	// generate all other nodes

		//System.err.println("Built "+syntaxNodes.size()+" states.");
		return syntaxNodes;
	}

	
	/**
		Generates syntax nodes into passed list, whereby every node represents one possible state.
		Every generated node gets appended to list and can generate new nodes by itself.
		@param syntaxNodes list of nodes
		@param syntax the grammar rules
	*/
	protected void generateSyntaxNodes(List syntaxNodes, Syntax syntax, Hashtable kernels)	{
		// newly appended nodes will be found and processed
		for (int i = 0; i < syntaxNodes.size(); i++)	{
			SLRSyntaxNode node = (SLRSyntaxNode)syntaxNodes.get(i);
			node.generateSyntaxNodesFromItems(syntaxNodes, syntax, kernels);
		}
	}
	
	/**
		Generates follower nodes from rule state items into list. The followers are referenced
		by their originators (GOTO-references).
		@param syntaxNodes list of nodes
		@param syntax the grammar rules
	*/
	protected void generateSyntaxNodesFromItems(List syntaxNodes, Syntax syntax, Hashtable kernels)	{
		for (Enumeration e = entries.elements(); e.hasMoreElements(); )	{
			RuleStateItem item = (RuleStateItem)e.nextElement();
			String pending = item.getPendingSymbol();

			if (item.followNodeIndex < 0 && pending != null)	{	// further states are possible
				// create a kernel item
				SLRSyntaxNode node = createSyntaxNode();
				List tmp = node.addShiftedItems(pending, entries);	// get entries that have been taken

				// look if it is already in list
				Integer kernelIndex = (Integer)kernels.get(node);
				int index = kernelIndex != null ? kernelIndex.intValue() : -1;

				// if not in list, add it, compute closure
				if (index < 0)	{
					index = syntaxNodes.size();
					kernels.put(node, new Integer(index));
					syntaxNodes.add(node);
					node.closure(syntax);
				}

				// link originator entries to new or found node
				for (int i = 0; i < tmp.size(); i++)	{
					Tuple t = (Tuple)tmp.get(i);
					linkParentItemToChild(t.o1, index, syntaxNodes, t.o2);
				}
			}
		}
	}
	

	/**
		Adopt all rule-states from originator node, which have the passed symbol
		as pending to the right of dot. This is done when a new node was generated,
		which happens when the dot is moved to the right.
		All adopted items together form the kernel of the syntax node.
		The number of kernel items is calculated, which is important when searching
		existing nodes.
		@param symbol the symbol that must be the pending symbol right of the dot within rule state item
		@param originatorEntries map containing all rule state items of the originator node (as value).
		@return a Tuple list containing pairs of original and new item, the new item is the shifted one.
	*/
	protected List addShiftedItems(String symbol, Hashtable originatorEntries)	{
		List list = new ArrayList();
		for (Enumeration e = originatorEntries.elements(); e.hasMoreElements(); )	{
			RuleStateItem item = (RuleStateItem) e.nextElement();
			String pending = item.getPendingSymbol();
			
			if (pending != null && symbol.equals(pending))	{
				RuleStateItem newitem = item.shift();
				this.entries.put(newitem, newitem);
				list.add(new Tuple(item, newitem));	// return all derived originator items
			}
		}
		
		kernels = list.size();	// remember count of kernel items
		
		return list;	// return list of entries that were shifted
	}


	/**
		Store the follow state (node index) within rule state item.
		This is a sparate protected method as LALR nodes do further work here.
	*/
	protected void linkParentItemToChild(RuleStateItem parent, int newIndex, List syntaxNodes, RuleStateItem child)	{
		parent.followNodeIndex = newIndex;
	}



	/**
		Closure - do for all rule states:
		Adopt all rules from grammar that derive one of the pending nonterminals
		(right of dot) within entries list. This is done recursively, appending
		new rules at end, so that they can adopt further rules.
		The closure method calls <i>addRulesDerivingPendingNonTerminal()</i>.
	*/
	protected void closure(Syntax syntax)	{
		// put Hashtable to List for sequential work
		List todo = new ArrayList(entries.size() * 2);
		for (Enumeration e = entries.elements(); e.hasMoreElements(); )
			todo.add(e.nextElement());

		// loop todo list and find every added new item
		for (int i = 0; i < todo.size(); i++)	{
			RuleStateItem rsi = (RuleStateItem)todo.get(i);
			String nonterm = rsi.getPendingNonTerminal();
			if (nonterm != null)
				addRulesDerivingPendingNonTerminal(rsi, nonterm, syntax, todo);
		}
	}
	
	/**
		Closure call for one rule state item. All rules in grammar that have passed
		nonterm on left side get appended to todo list and put into item entries when not already in entries.
	*/
	protected void addRulesDerivingPendingNonTerminal(RuleStateItem item, String nonterm, Syntax syntax, List todo)	{
		// make the closure for one item:
		// if pointer before a nonterminal, add all rules that derive it
		for (int i = 0; i < syntax.size(); i++)	{
			Rule rule = syntax.getRule(i);
			
			if (rule.getNonterminal().equals(nonterm))	{
				RuleStateItem rsi = createRuleStateItem(i, rule);

				if (entries.containsKey(rsi) == false)	{
					entries.put(rsi, rsi);	// real entry list
					todo.add(rsi);	// work list
				}
			}
		}
	}



	/**
		Fill the line of GOTO table this state corresponds to.
		@param state the index of this state within list
		@return Hashtable with all terminals/nonterminals to handle, and their follower states.
	*/
	public Hashtable fillGotoLine(int state)	{
		Hashtable h = new Hashtable(entries.size() * 3 / 2);	// load factor 0.75
		
		// fill one row of GOTO-table
		for (Enumeration e = entries.elements(); e.hasMoreElements(); )	{
			// store temporary
			RuleStateItem item = (RuleStateItem)e.nextElement();
			String symbol = item.getPendingSymbol();
			
			if (symbol != null)	{	// if pointer not at end of rule
				//System.err.println("Regel-Zustand:	"+item);
				setTableLine("GOTO", state, h, item, new Integer(item.followNodeIndex), symbol);
			}
		}
		return h;
	}


	/**
		Fill the line of PARSE-ACTION table this state corresponds to.
		@param state the index of this state within list
		@param firstSets all FIRST-sets of all nonterminals
		@param followSets all FOLLOW-sets of all nonterminals
		@return Hashtable with all terminals to handle, and their actions.
	*/
	public Hashtable fillParseActionLine(int state, FirstSets firstSets, FollowSets followSets)	{
		// fill one row of PARSE-ACTION-table
		Hashtable h = new Hashtable(entries.size() * 10);
		
		for (Enumeration e = entries.elements(); e.hasMoreElements(); )	{
			// store temporary
			RuleStateItem item = (RuleStateItem)e.nextElement();
			String symbol = item.getPendingSymbol();
			
			if (symbol != null)	{	// pointer not at end of rule, SHIFT
				if (Token.isTerminal(symbol))	{	// enter SHIFT at terminal symbol
					// first-set of terminal is terminal
					setParseTableLine(state, h, item, ParserTables.SHIFT, symbol);
				}
				else	{	// put SHIFT at all terminals of FIRST-set
					List firstSet = getNontermShiftSymbols(firstSets, item.getNonterminal());
					
					if (firstSet != null)	{	// LALR will return null, SLR not null
						for (int i = 0; i < firstSet.size(); i++)	{
							String terminal = (String) firstSet.get(i);
							setParseTableLine(state, h, item, ParserTables.SHIFT, terminal);
						}
					}
				}
			}