parser.java

这个是java语言实现的lr0词法语法分析器

import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;

public class Parser {

	private String input; // input String

	private int[][] parseTable; // LR(1) parse table

	private Stack<Integer> states; // state stack

	private Stack<Character> symbols; // symbol stack

	private ArrayList<Double> digits; // digit
	
	private ArrayList<TreeNode> tree;
	
	private PrintWriter out;

	public Parser() { //Default Construction Function
		this("input.txt", "output.txt", "LR-Table.txt");
	}

	public Parser(String inputPath, String outputPath, String filePath) {
		try {
			out = new PrintWriter(new FileWriter(new File(outputPath)));
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		this.input = getInputString(inputPath);
		parseTable = new int[18][7];
		states = new Stack<Integer>();
		symbols = new Stack<Character>();
		digits = new ArrayList<Double>();
		tree = new ArrayList<TreeNode>();		
		
		states.push(0);
		symbols.push('#');

		if (readLRTable(new File(filePath))) {
			System.out.println("Successfully load the LR-parse Table!");
			System.out.println("=====================================");
			out.println("Successfully load the LR-parse Table!");
			out.println("=====================================");
			tranform();
			parse();
			System.out.println("===========LR(1) parse FINISHED===========");
			out.println("============LR(1) parse FINISHED===========");
			print();
			out.close();
		} else {

		}
	}

	private boolean readLRTable(File file) { // read LR(1) parse table from file
		try {
			Scanner in = new Scanner(new FileInputStream(file));
			int no = 0;
			while (in.hasNextLine()) {
				String line = in.nextLine();
				stringtoIntArray(line, no);
				no++;
			}
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
			return false;
		}
		return true;
	}

	private boolean stringtoIntArray(String line, int no) { // some convert method 
		StringTokenizer tokens = new StringTokenizer(line);
		int a = 0;
		while (tokens.hasMoreTokens()) {
			parseTable[no][a] = Integer.parseInt(tokens.nextToken());
			a++;
		}
		return true;
	}

	private void tranform() { //do some nessery change to the orginal string using regular expression
		/*save all of the digits*/
		System.out.println("The input string is : " + input);
		System.out.println("=====================================");
		out.println("The input string is : " + input);
		out.println("=====================================");
		String expr = input;
		expr = expr.replaceAll("[*+()]", "|");

		System.out.print("The digits contained in the expression is : ");
		out.print("The digits contained in the expression is : ");
		StringTokenizer tokens = new StringTokenizer(expr, "|");
		while (tokens.hasMoreTokens()) {
			String digit = tokens.nextToken();
			System.out.print(digit + " ");
			out.print(digit + " ");
			digits.add(Double.parseDouble(digit));
		}
		System.out.println("\n=====================================");
		out.println("\n=====================================");
		/*change all of the digits to i using Regxp which can solve not only integer but also negative number and double*/
		input = input.replaceAll("-?[0-9]+\\.?[0-9]*", "i");
		System.out.println("Convert the orginal input to :" + input);
		System.out.println("=====================================");
		out.println("Convert the orginal input to :" + input);
		out.println("=====================================");
	}

	private void parse() { // the LR(1) parse method
		input += "#";
		int length = input.length();
		int index = 0;
		for (int a = 0; a < length; a++) {
			char ch = input.charAt(a);
			int state = states.peek();
			switch (ch) {
			case '*':
			case '+':
			case '(':
			case ')':
			case 'i':
			case '#':
				ACTION(state, ch);
				break;
			default: // 
				System.out
						.println("Illegal characters detected, please check your input!");
				out.println("Illegal characters detected, please check your input!");
				return;
			}
		}
	}

	private void ACTION(int state, char chr) {//the action
		int action = parseTable[state][getColumnPos(chr)];
		if (action > 0 && action != 99) //do shifting
		{
			System.out.println("Now, do shifting, \'" + chr + "\' will be moved to the symbol stack");
			out.println("Now, do shifting, \'" + chr + "\' will be moved to the symbol stack");
			symbols.push(chr);
			states.push(action);
			printCurrentStatesStack();
			printCurrentSymbolStack();
		} else if (action < 0) //do reducing
		{
			System.out.println("Now, do reducing according to the LR parse table when \'" + chr + "\' appears");
			out.println("Now, do reducing according to the LR parse table when \'" + chr + "\' appears");
			
			int length = 0;
			int no = Math.abs(action); // obtain which products
			if (no == 5) {
				length = 1;
			} else {
				length = 3;
			}
			System.out.print("Do as the products : E-->");
			out.print("Do as the products : E-->");
			
			Stack<Character> tmp = new Stack<Character>();
			for (int a = 0; a < length; a++) {
				states.pop();
				tmp.push(symbols.pop());
			}
			StringBuffer child = new StringBuffer();
			for(int b = 0; b < length; b++)
			{
				char ch = tmp.pop();
				System.out.print(ch);
				out.print(ch);
				child.append("" + ch + "--");
			}
			int strLength = child.length();
			child.delete(strLength - 2, strLength);
			tree.add(new TreeNode(0, "E", child.toString()));
			System.out.println();
			out.println();
			states.push(GOTO(states.peek()));
			symbols.push('E');
			printCurrentStatesStack();
			printCurrentSymbolStack();
			ACTION(states.peek(), chr);

		} else if (action == 0) {
			error(chr, action);
			return;
		} else if (action == 99) // success
		{
			System.out.println("ACCEPTED");
			out.println("ACCEPTED");
		}

	}

	private int GOTO(int state) {
		return parseTable[state][6];
	}

	private void error(char chr, int state) {
		System.out.println("Error occurs while handling : \'" + chr
				+ "\'; Current state is :\'" + state + "\'");
		out.println("Error occurs while handling : \'" + chr
				+ "\'; Current state is :" + state + "\'");
	}
	
	private void print()
	{
		Iterator<TreeNode> iter = tree.iterator();
		while(iter.hasNext())
		{
			String node = iter.next().toString();
			System.out.println(node);
			out.println(node);
		}
	}

	private int getColumnPos(char chr) {
		switch (chr) {
		case '+':
			return 0;
		case '*':
			return 1;
		case '(':
			return 2;
		case ')':
			return 3;
		case 'i':
			return 4;
		case '#':
			return 5;
		case 'E':
			return 6;
		default:
			System.out.println("THIS LINE SHOULD NEVER BEEN SEEN!!");
			out.println("THIS LINE SHOULD NEVER BEEN SEEN!!");
			return -1;
		}
	}
	
	private void printCurrentStatesStack()
	{
		System.out.print("Currently, the State stack contains : ");
		out.print("Currently, the State stack contains : ");
		Iterator<Integer> iter = states.iterator();
		while(iter.hasNext())
		{
			Integer state = iter.next();
			System.out.print(state + " ");
			out.print(state + " ");
		}
		System.out.println();
		out.println();
	}
	
	private void printCurrentSymbolStack()
	{
		System.out.print("Currently, the Symbol stack contains : ");
		out.print("Currently, the Symbol stack contains : ");
		Iterator<Character> iter = symbols.iterator();
		while(iter.hasNext())
		{
			Character symbol = iter.next();
			System.out.print(symbol + " ");
			out.print(symbol + " ");
		}
		System.out.println();
		out.println();
	}
	
	private String getInputString(String inputPath) 
	{
		Scanner input = null;
		String str = new String();
		try {
			input = new Scanner(new FileInputStream(new File(inputPath)));
			str = input.next();
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return str;
	}

	public static void main(String[] args) {
		/*Scanner in =  new Scanner(System.in);
		 
		 String input = in.nextLine();
		 System.out.println(input.replaceAll("-?[0-9]+\\.?[0-9]*", "i"));*/
		/*
		int argc = args.length;
		if(argc == 2)
		{
			new LR1Parse(args[0], args[1]);
		}
		else if(argc == 1)
		{
			new LR1Parse(args[0], "LR-Table.txt");
		}
		else
		{
			System.out.println("USEAGE: LR1Parse 1*((2+5)*3+0.1)");
		}
		*/
		new Parser();
	}

}

class TreeNode
{
	private int index;
	private String child;
	private String parent;
	
	TreeNode(int index, String parent, String child)
	{
		this.child = child;
		this.parent = parent;
		this.index = index;
	}
	
	public String toString()
	{
		return parent + "+\n |\n |--" + child + "\n";
	}
	
	public String getChild() {
		return child;
	}
	public void setChild(String child) {
		this.child = child;
	}
	public int getIndex() {
		return index;
	}
	public void setIndex(int index) {
		this.index = index;
	}
	public String getParent() {
		return parent;
	}
	public void setParent(String parent) {
		this.parent = parent;
	}
}