import java.util.*;
/**
* ------------------------
* LL(1)预测语法分析器识别下列表达式
* E->T|E+T
* T->F|T*F
* F->i|(E)
* -------------------------
*
* @author longth
* 2009-5-10
* email:longth_lang@qq.com
*/
public class LL1
{
static StringBuilder stack = new StringBuilder();// 符号栈
static StringBuilder inStr = null;// 输入串
static int z = 0, t = 0, i = 0, j = 0, index;
static char s_top, l_top;// 栈顶的元素，输入串的头字母
static StringBuilder exp = new StringBuilder();// 表达式
static boolean a = true;
static int no = 0;
static String tstring[][] = // 分析表
{
/* 0 1 2 3 4 5 */
/* i + * ( ) # */
{ "E->TE'", "ERROR", "ERROR", "E->TE'", "ERROR", "ERROR" },// E
{ "ERROR", "E'->+TE'", "ERROR", "ERROR", "E'->ε", "E'->ε" },// e
{ "T->FT'", "ERROR", "ERROR", "T->FT'", "ERROR", "ERROR" },// T
{ "ERROR", "T'->ε", "T'->*FT'", "ERROR", "T'->ε", "T'->ε" },// t
{ "F->i", "ERROR", "ERROR", "F->(E)", "ERROR", "ERROR" } // F
};
/**
* 入栈
*
* @param pchar
*/
static void push(char pchar)
{
stack.insert(t, pchar);
t++;
}
/**
* 获得分析表中的位置
*/
static void getLocal()
{
switch (s_top)
{
case 'E':
i = 0;
break;
case 'e':
i = 1;
break;
case 'T':
i = 2;
break;
case 't':
i = 3;
break;
case 'F':
i = 4;
break;
}
switch (l_top)
{
case 'i':
j = 0;
break;
case '+':
j = 1;
break;
case '*':
j = 2;
break;
case '(':
j = 3;
break;
case ')':
j = 4;
break;
case '#':
j = 5;
break;
}
}
/**
* 将栈顶元素出栈
*/
static void pop()
{
t--;
stack.deleteCharAt(t);
}
/**
* 改变栈中元素和找到对应表达式
*
* @param tt
*/
static void modifyStack(int tt)
{
switch (tt)
{
case 0:
pop();
push('e');
push('T');
exp.delete(0, exp.length());
exp.append(tstring[i][j]);
break;
case 3:
pop();
push('e');
push('T');
exp.delete(0, exp.length());
exp.append(tstring[i][j]);
break;
case 7:
pop();
push('e');
push('T');
push('+');
exp.delete(0, exp.length());
exp.append(tstring[i][j]);
break;
case 12:
pop();
push('t');
push('F');
exp.delete(0, exp.length());
exp.append(tstring[i][j]);
break;
case 15:
pop();
push('t');
push('F');
exp.delete(0, exp.length());
exp.append(tstring[i][j]);
break;
case 20:
pop();
push('t');
push('F');
push('*');
exp.delete(0, exp.length());
exp.append(tstring[i][j]);
break;
case 24:
pop();
push('i');
exp.delete(0, exp.length());
exp.append(tstring[i][j]);
break;
case 27:
pop();
push(')');
push('E');
push('(');
exp.delete(0, exp.length());
exp.append(tstring[i][j]);
break;
case 10:
case 11:
case 19:
case 22:
case 23:
pop();
exp.delete(0, exp.length());
exp.append(tstring[i][j]);
break;
default:
a = false;
break;
}
}
/**
* 求出栈顶元素
*/
static void top()
{
s_top = stack.charAt(stack.length() - 1);
}
/**
* 打印栈中所有元素
*/
static void printStack()
{
System.out.print(no + "\t");
for (int q = 0; q < stack.length(); q++)
{
if (stack.charAt(q) == 'e')
System.out.print("E");
else if (stack.charAt(q) == 't')
System.out.print("T'");
else
System.out.print(stack.charAt(q));
}
no++;
}
public static void main(String args[])
{
System.out.print("输入一个以＃结束的符号串(包括i+*()#)\n");
Scanner sc = new Scanner(System.in);
inStr = new StringBuilder(sc.next());
System.out.print("步骤 符号栈 输入串 所用产生式\n");
push('#');
push('E');
printStack();
System.out.print("\t");
System.out.print(inStr.toString() + "\n");
while (s_top != '#' || l_top != '#'){
if (a == false)
{
break;
}
if (s_top == l_top && l_top != 0){
for (int u = 0; u < inStr.length() - 1; u++)
inStr.setCharAt(u, inStr.charAt(u + 1));
inStr.deleteCharAt(inStr.length() - 1);
pop();
printStack();
System.out.print("\t");
System.out.print(inStr.toString() + "\n");
top();
l_top = inStr.charAt(0);
}
else{
top();
l_top = inStr.charAt(0);
getLocal();
index = 6 * i + j;
modifyStack(index);
top();
printStack();
System.out.print("\t" + inStr.toString() + "\t\t"
+ exp.toString() + "\n");
}
}
if (a)
System.out.print("分析成功！\n");
else
System.out.print("分析失败！\n");
}
}
