parsingtable.java

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

package cminus;
/**
 * Class-name:ParsingTable
 * 功能：构造文法的分析表，并将其用一定的数据结构保存。
 * @author Administrator
 *
 */
import java.util.*;
import java.io.*;

public class ParsingTable extends FollowSet {
	// 存储终结符号的链表
	public LinkedList listTerminals;
	// 终结符的个数
	public int numOfTerminals;
	// String型的二维数组，用来存储分析表
	public String [][] parsingTable ;
	// 用来将非终结符号按候选分开存放的链表
	public LinkedList listNonTerminalApartly = new LinkedList();
	
	/**
	 * 构造函数
	 * 
	 * @param fileName -文法文件绝对路径
	 */
	public ParsingTable(String fileName) {
		super(fileName);
	}
	/**
	 * 初始化存储分析表的二维数组
	 *
	 */
	public void initParsingTable(){
		this.getNumOfTerminals();
		this.constructNonTerminalListApartly();
		this.parsingTable = new String[this.numOfNonTerminals][this.numOfTerminals];
		for(int i = 0;i<this.numOfNonTerminals;i++){
			for(int j= 0 ;j<this.numOfTerminals;j++){
				this.parsingTable[i][j] = "";
			}
		}
	}
	/**
	 * 建立非终结字符按照候选的分类列表
	 *
	 */
	public void constructNonTerminalListApartly(){
		for(int i = 0;i<this.vectorFirstSetApart.size();i++){
			LinkedList list = (LinkedList)this.vectorFirstSetApart.get(i);
			this.listNonTerminalApartly.add(list.get(0));
		}
	}
	/**
	 * 打印分析表
	 *
	 */
	public void printParsingTable(){
		System.out.println("\nThe parsing table of the grammar is:");
		/*// print the column header
		String output = "";
		System.out.print("\t");
		for(int s = 0;s<this.listTerminals.size();s++){
			System.out.print(this.listTerminals.get(s)+"\t");
		}
		System.out.println();
		for(int i = 0;i<this.numOfNonTerminals;i++){
			//print the row header
			System.out.print(this.listNonTerminals.get(i)+"\t");
			for(int j= 0 ;j<this.numOfTerminals;j++){
				System.out.print("("+i+","+j+")"+"\t");
				output+="("+i+","+j+")-->"+this.parsingTable[i][j]+"\n";
			}
			System.out.println();
		}
		System.out.println(output);
		*/
		for(int s = 0;s<this.parsingTable.length;s++){
			for(int i = 0;i<this.parsingTable[s].length;i++){
				if(this.parsingTable[s][i].length()>0){
					String nonterminal = (String)this.listNonTerminals.get(s);
					String terminal = (String)this.listTerminals.get(i);
					System.out.println("ParsingTable["+nonterminal+","+terminal+"]: "+this.parsingTable[s][i]);
				}
			}
		}
	}
	/**
	 * Construct the parsing table and store it 
	 * int a array which size of "numOfNonTerminals * numOfNonTerminals". 
	 * 
	 */
	public void constructParsingTable(){
		for(int i = 0 ;i<this.listGrammar.length;i++){
			//对每个候选构造分析表的元素
			String element = "";
			for(int k = 0;k<this.listGrammar[i].size();k++){
				if(k == 1){
					element+="→";
					element +=(String)this.listGrammar[i].get(k)+" ";
				}
				else{
					element +=(String)this.listGrammar[i].get(k)+" ";
				}
			}
			//对由此候选求出的first集合
			String nonterminal = (String)this.listFirstSetApart[i].get(0);
			int row = this.listNonTerminals.indexOf(nonterminal);
			for(int j= 1;j<this.listFirstSetApart[i].size();j++){
				String terminal  = (String)this.listFirstSetApart[i].get(j);
				//如果此token不是空字
				if(!terminal.equalsIgnoreCase("EMPTY")){
					int col = this.listTerminals.indexOf(terminal);
					if(this.parsingTable[row][col].length()==0){
						this.parsingTable[row][col]= element;
					}
					else{
						// report error.
						if(nonterminal.equals("selection-stmt-1")){
							if((this.parsingTable[row][col].trim()).equals("selection-stmt-1 →EMPTY")){
								this.parsingTable[row][col]= element;
							}
						}
						else{
							System.err.println("The grammar is not LL(1)--分析表单元格不为空.\nProgram will exit...");
							int line = this.listNonTerminals.indexOf(nonterminal)+1;
							System.err.println("Line no--"+line+":\t"+nonterminal);
							System.err.println("old elmement: 	"+this.parsingTable[row][col]);
							System.err.println("new elmement: 	"+element);
							try{
								System.in.read();
								System.exit(0);
							}catch(IOException e){
								e.printStackTrace();
							}
						}
					}
				}
				//如果此token是空字，转到follow集
				else{
					for(int kk = 0;kk<this.listFollowSet.length;kk++){
						LinkedList list  = (LinkedList)this.listFollowSet[kk];
						String str = (String)list.get(0);
						if(str.equals(nonterminal)){
							for(int k = 1;k<this.listFollowSet[kk].size();k++){
								terminal = (String)this.listFollowSet[kk].get(k);
								int col = this.listTerminals.indexOf(terminal);
								if(this.parsingTable[row][col].length()==0){
									this.parsingTable[row][col]= element;
								}
								else{
									// report error.
									if(nonterminal.equals("selection-stmt-1")){
										if((this.parsingTable[row][col].trim()).equals("selection-stmt-1 →EMPTY")){
											this.parsingTable[row][col]= element;
										}
									}
									else{
										System.err.println("The grammar is not LL(1)--分析表单元格不为空.\nProgram will exit...");
										int line = this.listNonTerminals.indexOf(nonterminal)+1;
										System.err.println("Line no--"+line+":\t"+nonterminal);
										System.err.println("old elmement: 	"+this.parsingTable[row][col]);
										System.err.println("new elmement: 	"+element);
										try{
											System.in.read();
											System.exit(0);
										}catch(IOException e){
											e.printStackTrace();
										}
									}
								}
							}
						}
						
					}
				}
				
			}
		}//end of for
	}

	/**
	 * Get the number of non-terminal symbol of a grammar
	 * 
	 */
	public  void getNumOfTerminals() {
		listTerminals = new LinkedList();
		for (int i = 0; i < this.numOfNonTerminals; i++) {
			for (int j = 1; j < this.listFirstSet[i].size(); j++) {
				String str = (String) this.listFirstSet[i].get(j);
				if (!str.equalsIgnoreCase("empty")) {
					if (!listTerminals.contains(str)) {
						listTerminals.add(str.trim());
					}
				}
			}
		}
		for (int i = 0; i < this.numOfNonTerminals; i++) {
			for (int j = 1; j < this.listFollowSet[i].size(); j++) {
				String str = (String) this.listFollowSet[i].get(j);
				if (!str.equalsIgnoreCase("empty")) {
					if (!listTerminals.contains(str)) {
						listTerminals.add(str.trim());
					}
				}
			}
		}
		this.numOfTerminals = listTerminals.size();
	}

	public static void main(String args[]) {
		ParsingTable table = new ParsingTable("c-minus-2");
	}
}