java - Java 中的解析错误

Question

这是 LL(1) 解析器的代码。当我输入 I + I ;

不是按照语法进行解析，

生产如下

> E > TFE > VUTFE > IVUTFE

在最后的生产中，有一个问题...在匹配第一个 I 后，应消除 V。

但这并没有发生。

语法规则是

( docs )

下面是代码

( Docs )

请帮忙找出错误!

package llparser;
import java.io.*;
import java.util.logging.Level;
import java.util.logging.Logger;
class finiteAutomaton{  
        static String[] move = {"TF","+E","","VU","*T","I"};

    static int[][] transition = { {0,-1,-1,-1},
                                        {-1,1,-1,2},
                                        {3,-1,-1,-1},
                                        {-1,2,4,2},
                                        {5,-1,-1,-1}   };     
}



public class LLParser {

    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            String str=null;
            System.out.println("Enter a String for Parsing [ end with [;] ] :");
            str=br.readLine();
            str=str.toUpperCase();
            if(!str.endsWith(";"))
                throw new Exception("String should end with [;]");

            str=str.substring(0,str.length()-1);
            String temp = str.replaceAll(" ", "");       
            System.out.println(temp);
            String tokenizedString;
            String left;
            String right="";
            str=temp;
            String CSF="E";
            boolean flag=true;
            char symbol;
            int index=0;
            int SSM=0;
            int row,col;
            symbol = str.charAt(index);
            while(flag){

                     if(CSF.charAt(SSM)=='E') row=0;
                else if(CSF.charAt(SSM)=='F') row=1;
                else if(CSF.charAt(SSM)=='T') row=2;
                else if(CSF.charAt(SSM)=='U') row=3;
                else if(CSF.charAt(SSM)=='V') row=4;
                else                          row=-1;

                     if(symbol=='I') col=0;
                else if(symbol=='+') col=1;
                else if(symbol=='*') col=2;
                else if(symbol==';') col=3;
                else                 col=-1;

                if(row==-1 || col==-1 || finiteAutomaton.transition[row][col]==-1){
                        System.out.println("Error in Expression!");
                        System.exit(0);
                }
                tokenizedString=finiteAutomaton.move[finiteAutomaton.transition[row][col]];

                left = CSF.substring(0, SSM);
                int len=CSF.length();
                if(SSM<len)
                    right= CSF.substring(SSM);
                else
                    right="";
                left = left + tokenizedString + right;
                CSF = left;

                if(symbol==tokenizedString.charAt(0)){
                    SSM++;
                    symbol = str.charAt(++index);
                    System.out.println("SSM=" + SSM + " symbol="+ symbol);
                }

                if(str.equals(CSF))
                {
                    flag=false;
                }
            }
            if(!flag){
                System.out.println("String Accepted by Parser!");
            }



        } catch (IOException ex) {
            Logger.getLogger(LLParser.class.getName()).log(Level.SEVERE, null, ex);
        } catch (Exception ex) {
            Logger.getLogger(LLParser.class.getName()).log(Level.SEVERE, null, ex);
        }



    }
}

/*

Output

run:
Enter a String for Parsing [ String should end with [;] ] :
i+i;
I+I
SSM=1 symbol=+
Error in Expression! CSF=IVUTFE  Symbol=+
BUILD SUCCESSFUL (total time: 6 seconds)*/


I have performed debugg and problem is

CSF = E

E -> TF   CSF = TFE    [col=0 as CSF(0)==E and row=4 as symbol==I]

Here E should be replaced by TF but in my code
E remains in CSF and TF is appended before it.


Now T should be replaced by VU but in my code
T remains in CSF and VU is appended before it.
T -> VU   CSF = VUTFE



in next iteration.

V -> I   CSF = IVUTFE 

希望它有助于理解我的错误。

Answer 1

/*The grammar recognised is : 

E ::= TF 
F ::= +TF | # 
T ::= VU 
U ::= *VU | # 
V ::= I 
where I is any valid Identifer 

___________________________________________________ 
|                      | Source Symbol | 
|Non terminal|-------------------------------------| 
|            |     I   |     +   |     *   |     ; | 
|------------|---------|---------|---------|-------| 
| E          | E => TF |         |         |       | 
|------------|---------|---------|---------|-------| 
| F          |         | F => +TF|         | E => #| 
|------------|---------|---------|---------|-------| 
| T          | T => VU |         |         |       | 
|------------|---------|---------|---------|-------| 
| U          |         | U => #  | U => *VU| U => #| 
|------------|---------|---------|---------|-------| 
| V          | V => I  |         |         |       | 
|____________|_________|_________|_________|_______| 

*/
package llparser;
import java.io.*;
import java.util.logging.Level;
import java.util.logging.Logger;

class finiteAutomaton{  
        static String[] move = {"TF","+E","","VU","*T","I"};

    static int[][] transition = { {0,-1,-1,-1},
                                        {-1,1,-1,2},
                                        {3,-1,-1,-1},
                                        {-1,2,4,2},
                                        {5,-1,-1,-1}   };



}
public class LLParser {

    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

            String str=null;

            System.out.println("Enter a String for Parsing [ String should end with [;] ] :");
            str=br.readLine();
            str=str.toUpperCase();

            if(!str.endsWith(";"))
                throw new Exception("String should end with [;]");

            str=str.substring(0,str.length()-1); /* removing ; from string */
            String temp = str.replaceAll(" ", "");        /* removing spaces */
            str=temp;

            String tokenizedString;
            String left;
            String right="";

            String CSF="E";
            char symbol;
            int index=0;
            int SSM=0;
            int row,col;

            symbol = str.charAt(index);

            while(!str.equals(CSF)){

                System.out.println();
                System.out.println("Input String="+str +"\tSSM="+SSM+" Symbol="+symbol + " CSF="+CSF );
                     if(CSF.charAt(SSM)=='E') row=0;
                else if(CSF.charAt(SSM)=='F') row=1;
                else if(CSF.charAt(SSM)=='T') row=2;
                else if(CSF.charAt(SSM)=='U') row=3;
                else if(CSF.charAt(SSM)=='V') row=4;
                else                          row=-1;

                     if(symbol=='I') col=0;
                else if(symbol=='+') col=1;
                else if(symbol=='*') col=2;
                else if(symbol==';') col=3;
                else                 col=-1;

                    if(row==-1 || col==-1 || finiteAutomaton.transition[row][col]==-1){
                            System.out.println("Error in Expression!" + "CSF=" + CSF + " Symbol=" + symbol);
                            System.exit(0);
                    }
                tokenizedString=finiteAutomaton.move[finiteAutomaton.transition[row][col]];

                left = CSF.substring(0, SSM);

                int len=CSF.length();
                if(SSM<len-1)
                    right= CSF.substring(SSM+1,len);
                else
                    right="";

                left = left + tokenizedString + right;
                CSF = left;

                if(  tokenizedString.equals("")){
                    continue;
                }

                if(symbol==tokenizedString.charAt(0)){
                    SSM++;
                    char prev=symbol;
                    if(index<str.length()-1)
                        symbol = str.charAt(++index);
                    else
                        symbol = ';';
                    System.out.println("\n\tMatch Found Previous Symbol="+ prev + " New Symbol="+ symbol);
                }


            }

                System.out.println("String Accepted by Parser!");




        } catch (IOException ex) {
            Logger.getLogger(LLParser.class.getName()).log(Level.SEVERE, null, ex);
        } catch (Exception ex) {
            Logger.getLogger(LLParser.class.getName()).log(Level.SEVERE, null, ex);
        }



    }
}