www.pudn.com > ParseAna.rar > Parse.java
/**
* this class is the main parse analysis class
* @ author :ºØ¾²
* @ version: 1.2
*/
import java.io.IOException;
import java.util.Stack;
public class Parse {
private LexAna lex;
private Token currentToken = new Token();
private int[][] tableLL = new int[35][30];
private String errorToken = "";
private Error error = new Error();
private String printStr = "";
private int index = 0;
public static Stack treeStack;
public static Stack signStack;
public static Stack opStack;
public static Stack numStack;
public Parse(LexAna lex) {
this.lex = lex;
}
/**
* create LL(1) table
*/
private void createLLTable() {
tableLL[Type.Program][-Type.CLASS] = 1;
tableLL[Type.ProgramHead][-Type.CLASS] = 2;
tableLL[Type.ProgramBody][-Type.LEFTBig] = 3;
tableLL[Type.Stmt_Sequence][-Type.RIGHTBig] = 4;
tableLL[Type.Stmt_Sequence][-Type.IF] = 5;
tableLL[Type.Stmt_Sequence][-Type.WHILE] = 5;
tableLL[Type.Stmt_Sequence][-Type.READ] = 5;
tableLL[Type.Stmt_Sequence][-Type.WRITE] = 5;
tableLL[Type.Stmt_Sequence][-Type.INT] = 5;
tableLL[Type.Stmt_Sequence][-Type.REAL] = 5;
tableLL[Type.Stmt_Sequence][-Type.ID] = 5;
tableLL[Type.Stmt_Sequence][-Type.MINUSUNI] = 5;
tableLL[Type.Stmt_Sequence][-Type.SEMI] = 5;
tableLL[Type.Stmt][-Type.SEMI] = 6;
tableLL[Type.Stmt][-Type.IF] = 7;
tableLL[Type.Stmt][-Type.WHILE] = 8;
tableLL[Type.Stmt][-Type.ID] = 9;
tableLL[Type.Stmt][-Type.MINUSUNI] = 9;
tableLL[Type.Stmt][-Type.READ] = 10;
tableLL[Type.Stmt][-Type.WRITE] = 11;
tableLL[Type.Stmt][-Type.INT] = 12;
tableLL[Type.Stmt][-Type.REAL] = 12;
tableLL[Type.varDec_stmt][-Type.INT] = 13;
tableLL[Type.varDec_stmt][-Type.REAL] = 13;
tableLL[Type.TypeDef][-Type.INT] = 14;
tableLL[Type.TypeDef][-Type.REAL] = 14;
tableLL[Type.BaseType][-Type.INT] = 15;
tableLL[Type.BaseType][-Type.REAL] = 16;
tableLL[Type.TypeMore][-Type.ID] = 17;
tableLL[Type.TypeMore][-Type.LEFTMid] = 18;
tableLL[Type.varIdList][-Type.ID] = 19;
tableLL[Type.varListMore][-Type.SEMI] = 20;
tableLL[Type.varListMore][-Type.COMMA] = 21;
tableLL[Type.read_stmt][-Type.READ] = 22;
tableLL[Type.write_stmt][-Type.WRITE] = 23;
tableLL[Type.assign_stmt][-Type.ID] = 24;
tableLL[Type.variable][-Type.ID] = 25;
tableLL[Type.variMore][-Type.ASSIGN] = 26;
tableLL[Type.variMore][-Type.SEMI] = 26;
tableLL[Type.variMore][-Type.RIGHTMid] = 26;
tableLL[Type.variMore][-Type.RIGHTSmall] = 26;
tableLL[Type.variMore][-Type.LESS] = 26;
tableLL[Type.variMore][-Type.EQUAL] = 26;
tableLL[Type.variMore][-Type.BIGGER] = 26;
tableLL[Type.variMore][-Type.NOTEQUAL] = 26;
tableLL[Type.variMore][-Type.ADD] = 26;
tableLL[Type.variMore][-Type.MINUSBI] = 26;
tableLL[Type.variMore][-Type.MULTI] = 26;
tableLL[Type.variMore][-Type.DIVID] = 26;
tableLL[Type.variMore][-Type.LEFTMid] = 27;
tableLL[Type.if_stmt][-Type.IF] = 28;
tableLL[Type.ifMore][-Type.SEMI] = 29;
tableLL[Type.ifMore][-Type.ELSE] = 30;
tableLL[Type.elseMore][-Type.IF] = 31;
tableLL[Type.elseMore][-Type.LEFTBig] = 32;
tableLL[Type.while_stmt][-Type.WHILE] = 33;
tableLL[Type.Exp][-Type.ID] = 34;
tableLL[Type.Exp][-Type.NUM] = 34;
tableLL[Type.Exp][-Type.LEFTSmall] = 34;
tableLL[Type.Exp][-Type.MINUSUNI] = 34;
tableLL[Type.otherTerm][-Type.RIGHTMid] = 35;
tableLL[Type.otherTerm][-Type.SEMI] = 35;
tableLL[Type.otherTerm][-Type.RIGHTSmall] = 35;
tableLL[Type.otherTerm][-Type.EQUAL] = 35;
tableLL[Type.otherTerm][-Type.LESS] = 35;
tableLL[Type.otherTerm][-Type.BIGGER] = 35;
tableLL[Type.otherTerm][-Type.NOTEQUAL] = 35;
tableLL[Type.otherTerm][-Type.ADD] = 36;
tableLL[Type.otherTerm][-Type.MINUSBI] = 36;
tableLL[Type.Term][-Type.NUM] = 37;
tableLL[Type.Term][-Type.ID] = 37;
tableLL[Type.Term][-Type.LEFTSmall] = 37;
tableLL[Type.Term][-Type.MINUSUNI] = 37;
tableLL[Type.otherFactor][-Type.RIGHTMid] = 38;
tableLL[Type.otherFactor][-Type.RIGHTSmall] = 38;
tableLL[Type.otherFactor][-Type.BIGGER] = 38;
tableLL[Type.otherFactor][-Type.LESS] = 38;
tableLL[Type.otherFactor][-Type.EQUAL] = 38;
tableLL[Type.otherFactor][-Type.NOTEQUAL] = 38;
tableLL[Type.otherFactor][-Type.ADD] = 38;
tableLL[Type.otherFactor][-Type.MINUSBI] = 38;
tableLL[Type.otherFactor][-Type.SEMI] = 38;
tableLL[Type.otherFactor][-Type.MULTI] = 39;
tableLL[Type.otherFactor][-Type.DIVID] = 39;
tableLL[Type.Factor][-Type.LEFTSmall] = 40;
tableLL[Type.Factor][-Type.ID] = 40;
tableLL[Type.Factor][-Type.MINUSUNI] = 40;
tableLL[Type.Factor][-Type.NUM] = 41;
tableLL[Type.factorMore][-Type.LEFTSmall] = 42;
tableLL[Type.factorMore][-Type.ID] = 43;
tableLL[Type.Sign][-Type.ID] = 44;
tableLL[Type.Sign][-Type.LEFTSmall] = 44;
tableLL[Type.Sign][-Type.MINUSUNI] = 45;
tableLL[Type.TestExp][-Type.NUM] = 46;
tableLL[Type.TestExp][-Type.ID] = 46;
tableLL[Type.TestExp][-Type.LEFTSmall] = 46;
tableLL[Type.TestExp][-Type.MINUSUNI] = 46;
tableLL[Type.otherExp][-Type.BIGGER] = 47;
tableLL[Type.otherExp][-Type.LESS] = 47;
tableLL[Type.otherExp][-Type.EQUAL] = 47;
tableLL[Type.otherExp][-Type.NOTEQUAL] = 47;
tableLL[Type.AddOp][-Type.ADD] = 48;
tableLL[Type.AddOp][-Type.MINUSBI] = 49;
tableLL[Type.MultiOp][-Type.MULTI] = 50;
tableLL[Type.MultiOp][-Type.DIVID] = 51;
tableLL[Type.CmpOp][-Type.LESS] = 52;
tableLL[Type.CmpOp][-Type.BIGGER] = 53;
tableLL[Type.CmpOp][-Type.NOTEQUAL] = 54;
tableLL[Type.CmpOp][-Type.EQUAL] = 55;
tableLL[Type.AssignOp][-Type.ASSIGN] = 56;
tableLL[Type.SemiOp][-Type.SEMI] = 57;
// create the first row and second row's error number
for (int j = 0; j < 2; j++) {
for (int i = 0; i < 30; i++) {
if (tableLL[j][i] == 0)
tableLL[j][i] = -1;
}
}
// create the third row's error number
for (int i = 0; i < 30; i++) {
if (tableLL[3][i] == 0)
tableLL[3][i] = -2;
}
// create the first column's error number
for (int i = 0; i < 30; i++) {
if (tableLL[i][0] == 0)
tableLL[i][0] = -3;
}
}
/**
* if the type is less than 0 and bigger than -30
*
* @return true
*/
private boolean isTerminal(int i) {
if (i < 0 && i > -30) {
return true;
} else
return false;
}
// judge the terminal whether match
private boolean match(Token token, int i) {
if (token.getType() == i) {
return true;
}
return false;
}
/**
* this method is used for indent index is the height of the tree
*/
private String tabs() {
String s = "";
for (int i = 0; i < index; i++) {
s += " ";
}
return s;
}
/**
* the main methor to get the root node's printed stringS
*/
private void print(AST node) {
AST node2;
for (node2 = node; node2 != null; node2 = node2.getRight()) {
if (node2.getText() != null) {
printStr += tabs();
infoIncre(node2);
printStr += node2.getText() + " " + node2.info + "\n";
}else if(node2.getType()==Type.Program){
errorToken+=" Please input class name!";
}
if (node2.getDown() != null) {
index++;
print(node2.getDown());
index--;
}
}
}
/**
* increase the information of the parameter node its main intention is for
* print the tree
*
* @param node
*/
private void infoIncre(AST node) {
switch (node.getType()) {
case Type.Program:
node.info = ": Program";
break;
case Type.INT:
case Type.REAL:
if (node.getDown().getType() == Type.Exp) {
node.getDown().info = ": size";
node.info = ": array";
}
break;
case Type.ID:
if(!node.info.equals(""))
break;
if (node.getDown() != null) {
node.getDown().info = ": index";
}
node.info = ": ID";
break;
case Type.MINUSUNI:
node.info = ": uninary minus";
break;
case Type.MINUSBI:
node.info = ": binary minus";
break;
case Type.NUM:
if(!node.info.equals(""))
break;
node.info = ": Num ";
break;
default:
break;
}
}
public AST parseAna() throws IOException {
createLLTable();
treeStack = new Stack();
signStack = new Stack();
opStack = new Stack();
numStack = new Stack();
signStack.push(Type.Program);
AST program = new AST(Type.Program);
treeStack.push(program);
opStack.push(new AST(Type.END));
numStack.push(new AST(Type.END));
currentToken = lex.getToken();
while (!signStack.isEmpty()) {
// deal with the error form the lex analysis
if (currentToken.getType() < -29) {
errorToken = "ERROR!!! LINE " + currentToken.getLineNum()
+ " " + currentToken.getName() + " "
+ error.getError(currentToken.getType());
program.setType(Type.Program);
return program;
}
if (isTerminal(signStack.peek())) {
// judge currentToken whether match with the top element of the
// signStack
if (match(currentToken, signStack.peek())) {
signStack.pop();
AST ast = treeStack.peek();
if (ast.getType() == currentToken.getType()) {
ast.setText(currentToken.getName());
if (ast.isLeaf)
// if current node is leaf,pop it form the stack
treeStack.pop();
}
currentToken = lex.getToken();
} else {
// current token doesn't match with the top element of the
// signStack , Error! and end the analysis
errorToken = "ERROR!!! LINE " + currentToken.getLineNum()
+ error.getError(-34);
program.setType(Type.Program);
return program;
}
} else {// the top element of the signStack is non-terminal
// get the expression number from the LL(1) table
int num = tableLL[signStack.peek()][-currentToken.getType()];
if (num <= 0) {
// error number
if (num < 0) {
errorToken = "!!!Error LINE "
+ currentToken.getLineNum()
+ error.getError(num);
} else
errorToken = "!!!Error Line "
+ currentToken.getLineNum()
+ error.getError(-34);
program.setType(Type.Program);
return program;
}
Predict predict = new Predict();
signStack.pop();
// according to the expression number ,select the suitable
// dealing method
predict.predict(num);
}
}
// when signStack is empty, currentToken should be end sign, or else
// error!
if (currentToken.getType() != Type.END) {
errorToken = "Error!!! LIEN " + currentToken.getLineNum()
+ error.getError(-4);
}
program.setType(Type.Program);
treeStack.pop();// empty the treeStack
return program;
}
/**
* @return error information
*/
public String getErrorToken() {
return errorToken;
}
/**
* @param node
* @return the parameter node's print information
*/
public String getPrint(AST node) {
print(node);
return printStr;
}
}