firstset.java

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

package cminus;

/**
 * Class name：FirstSet.
 * 功能：
 * 		得到文法的first集合，并且判断文法是否是LL(1)文法。
 * 		同时得到文法中所有非终结符号的个数并且格式化存储之。
 * @author Administrator
 */
import java.io.*;
import java.util.*;

public class FirstSet {

	public BufferedReader fileIn;// 读取文件的文件数入流

	public Vector vectorGrammar = new Vector();// 格式化存储文法结构的向量

	public Vector vectorGrammarTogether = new Vector();// 格式化存储文法结构的向量

	public Vector vectorFirstSetApart = new Vector();// 存储按照候选分开的各个非终结符的first集合

	public Vector vectorFirstSet = new Vector();// 存储每个非终结符的first集合，按照非终结符分类

	public int numOfNonTerminals = 0;// 非终结字符的数目

	public LinkedList listNonTerminals = new LinkedList();// 存储非终结字符的链表对象

	public TokenProcess tokenPro = new TokenProcess();// token对象，用以判断一个符号是否终结符号

	// 装有每条文法的链表数组
	public LinkedList listGrammar[];

	// 按照候选装每个非终结符号的First集链表数组
	public LinkedList listFirstSetApart[];

	// 按照非终结符号装每个符号的First集的链表数组
	public LinkedList listFirstSet[];

	// 文法文件的行数
	int lineNO = 1;

	/**
	 * 构造函数：负责调用本类的函数生成first集合
	 */
	public FirstSet(String fileName) {
		this.loadFile(fileName);

	}

	public void printGrammar() {
		for (int i = 0; i < this.vectorGrammar.size(); i++) {
			LinkedList list = (LinkedList) this.vectorGrammar.get(i);
			for (int j = 0; j < list.size(); j++) {
				System.out.print(list.get(j) + " ");
			}
			System.out.println();
		}
	}

	/**
	 * 得到所有的候选中token的最大数目。
	 * 
	 * @return:int --token的最大数目
	 */
	public int getMaxChildNum() {
		int count = 0;
		for (int i = 0; i < listGrammar.length; i++) {
			int tmp = listGrammar[i].size() - 1;
			if (tmp > count) {
				count = tmp;
			}
		}
		return count;
	}

	/**
	 * 打印first set到标准输出流
	 * 
	 */
	public void printFirstSet() {
		// print first set
		System.out.println("\nThe first set of the grammar:");
		for (int i = 0; i < this.vectorFirstSet.size(); i++) {
			LinkedList list = (LinkedList) this.vectorFirstSet.get(i);
			for (int j = 0; j < list.size(); j++) {
				if(j==0){
					System.out.print(list.get(j)+":\t");
				}else{
					System.out.print(list.get(j) + " ");
				}
			}
			System.out.println();
		}
	}

	/**
	 * 初始化文件输入流，得到要分析的文法所在的文件
	 * 
	 * @param fileName
	 *            文件名称
	 */
	public void loadFile(String fileName) {
		try {
			fileIn = new BufferedReader(new FileReader(fileName));
		} catch (Exception e) {
			System.err.println("文件无法找到："+e.getMessage());
			try{
				System.in.read();
				System.exit(0);
			}catch(IOException ee){
				e.printStackTrace();
			}
		}
	}

	/**
	 * 将文件中的文法格式化存储成一定的数据结构，本函数将文法存储成为链表形式。
	 * 
	 */
	public void addToList() {
		try {
			String line = "";

			StringTokenizer token = null;

			line = fileIn.readLine();
			while ((line != null) && (!line.equals(""))) {
				// 声明三个数组，分别用来存放非终结符号、候选和每个候选中的因子
				String first[] = new String[getSymbolNum(line, '→') + 1];// 存放
				// 非终结符号
				String choice[] = new String[getSymbolNum(line, '|') + 1];// 存放候选
				String factor[][] = new String[getSymbolNum(line, '|') + 1][10];// 存放每个候选中的因子
				// 初始化factor数组，都为""
				for (int i = 0; i < getSymbolNum(line, '|') + 1; i++) {
					LinkedList list = new LinkedList();
					for (int j = 0; j < factor[i].length; j++) {
						factor[i][j] = "";
					}
				}
				// 装入first数组
				first = line.split("→");
				for (int s = 0; s < first.length; s++) {
					first[s] = first[s].trim();
				}
				if (first[0].indexOf(' ') != -1) {
					System.err
							.println("Syntax error happened in grammar file, line no.:"
									+ lineNO + " -->" + line);
					System.err.println("\t-->\"" + first[0]
							+ "\" is invalid non-terminal symbol.");
					System.err.println("System will exit...");
					try{
						System.in.read();
						System.exit(0);
					}catch(IOException e){
						e.printStackTrace();
					}
				}
				if (first.length != 2) {
					if (first.length == 1) {
						System.err
								.println("Syntax error happened in grammar file, line no.:"
										+ lineNO + " -->" + line);
						System.err
								.println("\t-->There is no \"→\" found or \"→\" is in the wrong position in the grammar line.");
						System.err.println("System will exit...");
						try{
							System.in.read();
							System.exit(0);
						}catch(IOException e){
							e.printStackTrace();
						}
					} else {
						System.err
								.println("Syntax error happened in grammar file, line no.:"
										+ lineNO + " -->" + line);
						System.err.println("\t-->Too many \"→\"");
						System.err.println("System will exit...");
						try{
							System.in.read();
							System.exit(0);
						}catch(IOException e){
							e.printStackTrace();
						}
					}
				}
				// 装入choice数组
				token = new StringTokenizer(first[1], "|");
				int i = 0;
				while (token.hasMoreTokens()) {
					choice[i++] = token.nextToken();
				}
				// 装入factor数组
				for (i = 0; i < choice.length; i++) {
					token = new StringTokenizer(choice[i], " ");
					int j = 0;
					while (token.hasMoreTokens()) {
						factor[i][j++] = token.nextToken();
					}
				}

				// 将生成的文法按行存储
				LinkedList list1 = new LinkedList();
				list1.add(first[0]);
				for (int a = 0; a < factor.length; a++) {
					for (int b = 0; b < factor[a].length; b++) {
						if (factor[a][b].length() != 0) {
							list1.add(factor[a][b]);
						}
					}
				}
				this.vectorGrammarTogether.add(list1);
				// 将生成的链表对象加入到vector中,按候选存储
				LinkedList list = null;
				for (i = 0; i < getSymbolNum(line, '|') + 1; i++) {
					list = new LinkedList();
					int flag = 0;
					for (int j = 0; j < factor[i].length; j++) {
						if (!factor[i][j].equals("")) {
							if (flag == 0) {
								list.add(first[0].trim());
								flag = 1;
							}
							list.add(factor[i][j].trim());
						}
					}
					vectorGrammar.addElement(list);
				}
				line = fileIn.readLine();// 读取下一行
				this.lineNO++;
				numOfNonTerminals++;// 非终结符号个数加一
				this.listNonTerminals.add(first[0].trim());// 存储非终结符号
			}
			line = fileIn.readLine();// 再往下读一行，看不是有空行在文法文件里。
			if (line!=null&&line.length() > 0) {
				System.err
						.println("Syntax error happened in grammar file, line no.:"
								+ lineNO);
				System.err.println("\t-->Line can not be empty.");
				System.err.println("System will exit...");
				try{
					System.in.read();
					System.exit(0);
				}catch(IOException e){
					e.printStackTrace();
				}
			}
			fileIn.close();