parsingtree.java

C语言的词法、语法分析器 输出语法分析树

/*******************
 * class name: ParsingTree
 * task:	generaing a parsing tree for the grammar and the program.
 * @author Administrator
 */
package cminus;

import java.util.*;
import java.io.*;

class ParsingTree extends ParsingTable {
	//stack for storing tokens int the program
	public Stack stackToken = new Stack();
	//stack for storing token types int the program
	public Stack stackTokenType = new Stack();
	//token file which stored tokens in the program.
	public String tokenFile;
	//token type file which stored token types in the program
	public String tokenTypeFile;
	//the root node of parsing tree
	public ParsingTreeNode root;
	/**
	 * construct function.
	 * @param filename:String  -file which storing the grammar .
	 */
	public ParsingTree(String filename) {
		super(filename);
	}
	
	/**
	 * set the token file generated by the scanner.
	 * @param file:String  -file name of the tokens.
	 */
	public void setTokenFile(String file) {
		this.tokenFile = file;
	}
	/**
	 * set the token type file generated by the scanner.
	 * @param file:String  -file name of the tokens.
	 */
	public void setTokenTypeFile(String file) {
		this.tokenTypeFile = file;
	}
	
	/** 
	 * get toknes from token file to the token stack.
	 */
	public void setStackToken() {
		
		this.setTokenFile("tokenFile");
		
		Stack tmp = new Stack();
		try {
			fileIn = new BufferedReader(new FileReader(this.tokenFile));
		} catch (IOException e) {
			System.out.println("File can not found: " + e.getMessage());
		}
		try {
			String line = fileIn.readLine();
			while (line != null && (!line.equals(""))) {
				tmp.push(line.trim());
				line = fileIn.readLine();
			}
			this.stackToken.push("Line--1 $");
			while(!tmp.empty()){
				this.stackToken.push(tmp.pop());
			}
		} catch (IOException e) {
			System.out.println("File read error:" + e.getMessage());
		} finally{
			try{
				fileIn.close();
			}catch(Exception e){}
		}
	}
	
	/** 
	 * get tokne types from token type file to the token type stack.
	 */
	public void setStackTokenType() {
		this.setTokenTypeFile("tokenTypeFile");
		
		Stack tmp = new Stack();
		try {
			fileIn = new BufferedReader(new FileReader(this.tokenTypeFile));
		} catch (IOException e) {
			System.out.println("File can not found: " + e.getMessage());
		}
		try {
			String line = fileIn.readLine();
			while (line != null && (!line.equals(""))) {
				tmp.push(line.trim());
				line = fileIn.readLine();
			}
			this.stackTokenType.push("Line--1 $");
			while(!tmp.empty()){
				this.stackTokenType.push(tmp.pop());
			}
		} catch (IOException e) {
			System.out.println("File read error:" + e.getMessage());
		} finally{
			try{
				fileIn.close();
			}catch(Exception e){}
		}
	}
	
	/**
	 * Generate the parsing tree ,the tree is stored in memory , 
	 * and if get the root node, means get the tree.
	 *
	 */
	public void parsingAction() {
		Stack parsingStack = new Stack();
		ParsingTreeNode first  = new ParsingTreeNode();
		first.data = "$";
		parsingStack.push(first);
		//generating the root node of the parsing tree
		this.root = new ParsingTreeNode();
		String rootData =(String)this.listGrammar[0].get(0); 
		root.data = rootData;
		parsingStack.push(root);
		try{
		//Get the top value on the parsing stack
		ParsingTreeNode stackGot = (ParsingTreeNode)parsingStack.get(parsingStack.size()-1);
		String stackGotData = stackGot.data.trim();
		while(!stackGotData.equals("$")){
			String tmp1 = (String)this.stackTokenType.get(this.stackToken.size()-1);
			String tmp2[] = tmp1.split(" ");
			String tokenTypeStackPoped = tmp2[1].trim();
			// if the top of the parsing stack is terminal tokenTypeStackPoped
			// and it is equals with the top the token type stack
			if(this.tokenPro.isTerminal(stackGotData)&& stackGotData.equals(tokenTypeStackPoped)){
				//match;
				parsingStack.pop();	//pop the parsing stack
				this.stackTokenType.pop();//advanced the input
				String tmp3 = (String)this.stackToken.pop();
				String tmp4[] = tmp3.split(" ");
				String tokenStackPoped = tmp4[1].trim();
				if(!tokenTypeStackPoped.equals(tokenStackPoped)){
					ParsingTreeNode tmp = new ParsingTreeNode();
					tmp.data = tokenStackPoped;
					stackGot.child[0] = tmp;
				}
			}
			// else if the top of the stack is nonterminal and 
			// the top of the token type stack is terminal or is '$'
			else if((!this.tokenPro.isTerminal(stackGotData))&&
					(this.tokenPro.isTerminal(tokenTypeStackPoped)||tokenTypeStackPoped.equals("$"))
					){
				String tableContent = this.parsingTable[this.listNonTerminals.indexOf(stackGotData)]
				                                        [this.listTerminals.indexOf(tokenTypeStackPoped)];
				if(tableContent != null && !tableContent.equals("")&&tableContent.length()>0){
					//generate;
					parsingStack.pop();//pop the parsing stack
					
					//reserved the sequence and push to the stack
					String left[] = tableContent.split("→");
					String right[] = left[1].split(" ");
					ParsingTreeNode nodes[] = new ParsingTreeNode[right.length];
					for (int i = 0; i < left.length; i++) {
						left[i] = left[i].trim();
					}
					for (int i = 0; i < right.length; i++) {
						right[i] = right[i].trim();
						nodes[i] = new ParsingTreeNode();
						nodes[i].data = right[i];
					}
					for(int i = right.length-1;i>=0;i--){
						if(stackGot.child[i] == null){
							stackGot.child[i] = new ParsingTreeNode();
							stackGot.child[i] = nodes[i];
							if(!nodes[i].data.equalsIgnoreCase("EMPTY")){
								parsingStack.push(nodes[i]);
							}
						}
						else{
							stackGot.child[i] = nodes[i];
							if(!nodes[i].data.equalsIgnoreCase("EMPTY")){
								parsingStack.push(nodes[i]);
							}
						}
					}
					//pushing to parsing stack has done!
				}
				else{
					System.err.println("-----------------------------------------------------");
					System.err.println("Error: \n\t1.Syntax error has taken place at line: "+tmp2[0].substring(5));
					System.err.println("-----------------------------------------------------");
					try{
						System.in.read();
						System.exit(0);
					}catch(IOException e){
						e.printStackTrace();
					}
				}
			}
			else {
				System.err.println("Generating parsing tree error...");
			}
			stackGot = (ParsingTreeNode)parsingStack.get(parsingStack.size()-1);
			stackGotData = stackGot.data.trim();
		}//end of while
		String tmp6 = (String)this.stackTokenType.get(this.stackToken.size()-1);
		String tmp7[] = tmp6.split(" ");
		String tokenTypeStackPoped  = tmp7[1];
		if(stackGotData.equals("$")&&tokenTypeStackPoped.equals("$")){
			//accept();
			System.out.println("The operation of generating parsing tree has done!");
		}
		else{
			System.err.println("Generating parsing tree error...");
		}
		}
		catch(IndexOutOfBoundsException e){
			System.err.println("Index out of bounds error [parsingAction]:"+e.getMessage());
		}catch(NullPointerException e){
			System.err.println("Null pointer exception "+e.getMessage());
		}
		catch(Exception e){
			System.err.println("Generating parsing tree error:"+e.getMessage());
		}
		
	}//end of function

	/**
	 * Anonymous class for ParsingTree.
	 * The class definit the tree node for parsing tree.
	 * @author Administrator
	 *
	 */
	public class ParsingTreeNode {
		public String data;
		ParsingTreeNode [] child ;
		public ParsingTreeNode(){
			int count = getMaxChildNum();
			child = new ParsingTreeNode[count];
			this.data = null;
		}
		boolean isLeaf(){
			boolean isleaf = false;
			for(int i = 0;i<this.child.length;i++){
				if(child[i]==null){
					isleaf = true;
				}else{
					isleaf = false;
					break;
				}
			}
			return isleaf;
		}
	}
	
	/**
	 * the main function ,just for testing use.
	 * @param args--not used.
	 */
	public static void main(String args[]) {
		ParsingTree tree  = new ParsingTree("test10");
		tree.setStackToken();
		tree.setStackTokenType();
		tree.parsingAction();
		System.out.println("done");
	}
}