package re.sa;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class LL1SA {
/*
* 原始文法：
*
* E→E+T|E/T|T
* T→T-F|T*F|F
* F→(E)|i
*/
/*
* 消除左递归
*
* E→TM
* M→+TM|/TM|ε
* T→FN
* N→-FN|*FN|ε
* F→(E)|i
*/
/*
* 求First集和Follow集
*
* First(E)={(,i} Follow(E)={),#}
* First(T)={(,i} Follow(T)={+,/,#}
* First(F)={(,i} Follow(F)={-,*,#}
* First(M)={+,/,ε} Follow(M)={),#}
* First(N)={-,*,ε} Follow(N)={+,/,#}
*/
// 构造预测分析表
private String[] Vt = {"+", "/", "-", "*", "(", ")", "i"};
private String[] Vn = {"E", "T", "F", "M", "N"};
private String[][] M = {
//+=0 /=1 -=2 *=3 (=4 )=5 i=6 #=7
{ "", "", "", "", "TM", "", "TM", ""}, //E=0
{ "", "", "", "", "FN", "", "FN", ""}, //T=1
{ "", "", "", "", "(E)", "", "i", ""}, //F=2
{ "+TM", "/TM", "", "", "ε", "", "", "ε"}, //M=3
{ "ε", "ε", "-FN", "*FN", "", "", "", "ε"} //N=4
};
//开始分析
private String[] stack = new String[256];
private String stack_top;
private int stack_ptr = -1;
private int ptr = 0;
private char c_temp;
private int Vt_code;
private int Vn_code;
private void get_char(String sentence){
c_temp = sentence.charAt(ptr);
ptr++;
if(c_temp == '+'){
Vt_code = 0;
}else if(c_temp == '/'){
Vt_code = 1;
}else if(c_temp == '-'){
Vt_code = 2;
}else if(c_temp == '*'){
Vt_code = 3;
}else if(c_temp == '('){
Vt_code = 4;
}else if(c_temp == ')'){
Vt_code = 5;
}else if(c_temp == 'i'){
Vt_code = 6;
}else if(c_temp == '#'){
Vt_code = 7;
}
}
private void push(String str){
stack_ptr++;
stack[stack_ptr] = str;
}
private void pull(){
stack_top = stack[stack_ptr];
stack[stack_ptr] = null;
stack_ptr--;
if(stack_top.equals("E")){
Vn_code = 0;
}else if(stack_top.equals("T")){
Vn_code = 1;
}else if(stack_top.equals("F")){
Vn_code = 2;
}else if(stack_top.equals("M")){
Vn_code = 3;
}else if(stack_top.equals("N")){
Vn_code = 4;
}
}
private boolean isVt(String str){
for(int i = 0; i < Vt.length; i++){
if(str.equals(Vt[i])){
return true;
}
}
return false;
}
private boolean isVn(String str){
for(int i = 0; i < Vn.length; i++){
if(str.equals(Vn[i])){
return true;
}
}
return false;
}
public boolean SyntaxAnalyse(String sentence){
push("#");
push("E");
get_char(sentence);
boolean flag = true;
while(flag){
pull();
if(isVt(stack_top)){
if(stack_top.equals(String.valueOf(c_temp))){
get_char(sentence);
}else{
return false;
}
}else if(stack_top.equals("#")){
if(stack_top.equals(String.valueOf(c_temp))){
flag = false;
}else{
return false;
}
}else if(M[Vn_code][Vt_code] != null){
if(!M[Vn_code][Vt_code].equals("ε")){
for(int i = M[Vn_code][Vt_code].length() - 1; i >= 0 ; i--){
push(String.valueOf(M[Vn_code][Vt_code].charAt(i)));
}
}
}else{
return false;
}
}
return true;
}
public static void main(String[] args) throws IOException{
while(true){
LL1SA sa = new LL1SA();
System.out.print("请输入语句：");
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String str = in.readLine();
String sentence = str + "#";
boolean result = sa.SyntaxAnalyse(sentence);
if(result == true){
System.out.println(str + " 是正确表达式！");
}else if(result == false){
System.out.println(str + " 是错误表达式！");
}else{
System.out.println("分析程序出现错误！");
}
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
前往页