slrsyntaxnode.java

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

			else	{	// pointer at end, REDUCE to rule number
				for (Iterator reduceSymbols = getReduceSymbols(followSets, item); reduceSymbols.hasNext(); )	{
					String terminal = (String) reduceSymbols.next();
					
					if (item.ruleIndex == 0)	// is startnode
						setParseTableLine(state, h, item, ParserTables.ACCEPT, terminal);
					else	// ruleIndex > 0 means REDUCE
						setParseTableLine(state, h, item, new Integer(item.ruleIndex), terminal);
				}
			}
		}
		return h;
	}

	/**
		Returns all symbols for which SHIFT must be put into PARSE-ACTION table for a nonterminal.
		For SLR this is the FIRST set of the nonterminal.
	*/
	protected List getNontermShiftSymbols(FirstSets firstSets, String nonterm)	{
		return (List) firstSets.get(nonterm);
	}

	/**
		Returns all symbols for which REDUCE must be put into PARSE-ACTION table.
		For SLR this is the FOLLOW set of the nonterminal.
	*/
	protected Iterator getReduceSymbols(FollowSets followSets, RuleStateItem item)	{
		return ((List) followSets.get(item.getNonterminal())).iterator();
	}




	/**
		Set a position in PARSE-ACTION table.
		This is the place where SHIFT/REDUCE and REDUCE/REDUCE conflicts are solved.
	*/
	protected void setParseTableLine(int state, Hashtable line, RuleStateItem item, Integer action, String terminal)	{
		// set one action into a parse-table row and resolve conflicts
		
		if (setTableLine("PARSE-ACTION", state, line, item, action, terminal) == false)	{
			// shift/reduce or reduce/reduce conflict
			Object o = line.get(terminal);
			
			if (action.equals(ParserTables.SHIFT) || o.equals(ParserTables.SHIFT))	{
				// prefer SHIFT operation
				line.put(terminal, ParserTables.SHIFT);
				System.err.println("WARNING: shift/reduce conflict, SHIFT is preferred.");
			}
			else	{
				System.err.println("WARNING: reduce/reduce conflict, rule with smaller index is preferred.");
				// prefer rule with smaller index
				if (((Integer)o).intValue() > action.intValue())
					line.put(terminal, action);
			}
		}
	}
	
	
	/**
		Set a position in one of the tables.
		Here SHIFT/SHIFT, SHIFT/REDUCE and REDUCE/REDUCE conflicts are detected.
		@return true when no conflict was detected
	*/
	protected boolean setTableLine(String table, int state, Hashtable line, RuleStateItem item, Integer action, String terminal)	{
		// set one action into a table row and detect conflicts
		Object o = line.get(terminal);
		if (o == null)	{	// no conflict
			line.put(terminal, action);
		}
		else	{	// conflict?
			if (o.equals(action) == false)	{	// conflict!
				System.err.println("========================================================");
				System.err.println("WARNING: "+table+" state "+state+", terminal "+
						terminal+" is "+
						displayAction(o)+" and was overwritten by action "+
						displayAction(action));
				System.err.println("... from rule state: "+item);
				System.err.println("... current state:\n"+this);
				System.err.println("========================================================");
				return false;
			}
		}
		return true;
	}
	
	private String displayAction(Object action)	{
		if (action.equals(ParserTables.SHIFT))
			return "SHIFT";
		return "REDUCE("+action.toString()+")";
	}
	

	/**
		The count of kernel items must be equal. All kernel items must exist in passed node.
		@param o new node that contains only kernel items (which do not have dot at start).
	*/
	public boolean equals(Object o)	{
		//System.err.println("SLRSyntaxNode.equals: \n"+this+"\n with \n"+o);
		SLRSyntaxNode node = (SLRSyntaxNode)o;
		
		if (node.kernels != kernels)
			return false;
		
		// look if all entries are in the other node
		for (Enumeration e = entries.elements(); e.hasMoreElements(); )	{
			RuleStateItem item = (RuleStateItem)e.nextElement();
			// kernel items have pointer not at start
			if (item.pointerPosition > 1 && node.entries.containsKey(item) == false)
				return false;
		}
		return true;
	}

	/** Returns the hashcodes of all rule state items, associated by ^. The result gets buffered on first call. */
	public int hashCode()	{
		if (hashCache == null)	{
			int result = 0;
			for (Enumeration e = entries.elements(); e.hasMoreElements(); )
				result ^= e.nextElement().hashCode();
			hashCache = new Integer(result);
		}
		return hashCache.intValue();
	}


	/** Outputs this syntax node with all its rule state entries sorted. */
	public String toString()	{
		StringBuffer sb = new StringBuffer();
		// we want a sorted output of items, order by ruleIndex
		List list = new ArrayList(entries.size());
		for (Enumeration e = entries.elements(); e.hasMoreElements(); )	{
			RuleStateItem rsi = (RuleStateItem)e.nextElement();
			int index = -1;
			for (int i = 0; index == -1 && i < list.size(); i++)	{
				RuleStateItem rsi1 = (RuleStateItem) list.get(i);
				if (rsi1.ruleIndex > rsi.ruleIndex || rsi1.ruleIndex == rsi.ruleIndex && rsi.pointerPosition > 1)
					index = i;
			}
			if (index < 0)
				list.add(rsi);
			else
				list.add(index, rsi);
		}
		for (int i = 0; i < list.size(); i++)	{
			sb.append("  ");
			sb.append(list.get(i).toString());
			sb.append("\n");
		}
		return sb.toString();
	}



	// Helper that hold two RuleStateItems
	private class Tuple
	{
		RuleStateItem o1, o2;
		
		Tuple(RuleStateItem o1, RuleStateItem o2)	{
			this.o1 = o1;
			this.o2 = o2;
		}
	}



	/**
		Rule state entry item class, contained within SLR syntax node.
	*/
	protected class RuleStateItem
	{
		Rule rule;
		int pointerPosition = 1;
		int ruleIndex;
		int followNodeIndex = -1;
		protected Integer hashCache = null;
		
		
		/** Constructor with syntax rule index and rule. */
		public RuleStateItem(int ruleIndex, Rule rule)	{
			this.rule = rule;
			this.ruleIndex = ruleIndex;
		}
		
		/** Internal construction of shifted rule states. */
		protected RuleStateItem(RuleStateItem orig)	{
			this.rule = orig.rule;
			this.pointerPosition = orig.pointerPosition;
			this.ruleIndex = orig.ruleIndex;
		}

		
		/** Factory-method, to be overridden by subclasses. */
		protected RuleStateItem createRuleStateItem(RuleStateItem orig)	{
			return new RuleStateItem(orig);
		}
		
		/** Returns the nonterminal on the left side of the rule. */
		String getNonterminal()	{
			return rule.getNonterminal();
		}
		
		/** Returns a new shifted rule state item (dot has moved one position right). */
		RuleStateItem shift()	{
			RuleStateItem clone = createRuleStateItem(this);
			clone.pointerPosition++;
			return clone;
		}
		
		/** Returns null when no nonterminal is after dot, else the nonterminal to the right of the dot. */
		String getPendingNonTerminal()	{
			if (pointerPosition > rule.rightSize())
				return null;
				
			String symbol = getPendingSymbol();
			if (Token.isTerminal(symbol))
				return null;	// is a terminal
					
			return symbol;
		}
		
		/** Return pending symbol if pointer position is not at end, else null. */
		String getPendingSymbol()	{
			if (pointerPosition > rule.rightSize())
				return null;

			return rule.getRightSymbol(pointerPosition - 1);
		}

		/** The rule number and dot position must match for equality. */
		public boolean equals(Object o)	{
			RuleStateItem item = (RuleStateItem)o;
			return ruleIndex == item.ruleIndex && pointerPosition == item.pointerPosition;
		}
	
		/** Returns rule index * 13 + position of dot. */
		public int hashCode()	{
			if (hashCache == null)
				hashCache = new Integer(ruleIndex * 13 + pointerPosition);
			return hashCache.intValue();
		}
	
		/** String representation of rule state, showing index, rule and dot position. */
		public String toString()	{
			StringBuffer sb = new StringBuffer("(Rule "+ruleIndex+") "+getNonterminal()+" : ");
			int i = 0;
			for (; i < rule.rightSize(); i++)	{
				if (i == pointerPosition - 1)
					sb.append(".");
				sb.append(rule.getRightSymbol(i));
				sb.append(" ");
			}
			if (i == pointerPosition - 1)
				sb.append(".");
			if (followNodeIndex >= 0)
				sb.append(" -> State "+followNodeIndex);
			return sb.toString();
		}
	
	}

}