/** Beispiel eines Backtracking Parsers
 * Soll zeigen, dass man jede Grammatik mit Backtracking 
 * implementieren kann - sofern man vorher Linksrekursionen 
 * beseitigt. */

public class BacktrackParser{

   String[] Start         = { "Programm" };
   String[] Programm      = {"begin", "Anweisungen", "end"}; 
   
   String[][] Anweisungen = { {}, {"Anweisung"}, {"Anweisung", ";", "Anweisungen"} };                           

 
   String[][] Anweisung   = {{"If"}, {"IfElse"},{"While"}, {"Zuweisung"}};

   String[] If            = {"if", "Bexpr", "then", "Anweisung"};
   String[] IfElse        = {"if", "Bexpr", "then", "Anweisung", "else", "Anweisung"};
   String[] While         = {"while", "Bexpr", "do", "Anweisung"};
   String[] Zuweisung     = {"id", ":=", "Expr" };
   String[][] Faktor      = { {"id"}, {"num"}, {"(","Expr",")"}};
   String[][] Term        = { {"Faktor"}, {"Faktor", "*", "Term"},{"Faktor", "/", "Term"} };
   String[][] Expr        = { {"Term"}, {"Term", "+", "Expr"}, {"Term", "-", "Expr"}};
   String[] Bexpr         = {"Expr", "=", "Expr" };


    
//   String[] input = {"begin","id", ":=", "id" ,"end"}; 
    
   boolean parse(){
     return parse(0,(new Liste()).cons("Programm"));
   }

   /** next ist Position in input, s ist der Parserstack, reopräsentiert als Liste*/  
   boolean parse(int next, Liste s){
      if(s.isEmpty())                          // Stack leer?
           return (next==input.length);        // input fertig --> Erfolg
           
      else if(s.car().equals(input[next]))     // top(stack) = next in input 
           return parse(next+1,s.cdr());       // akzeptieren        

      else if(s.car().equals("Programm"))      // Nonterminal auf Stack
           return parse(next,s.mit(Programm)); // Ersetze top durch rechte Seite           
            
      else if(s.car().equals("Anweisungen"))             // NT mit mehreren Produktionen
           return  parse(next,s.mit( Anweisungen[0] ))   // versuche erste Produktion    
               ||  parse(next,s.mit( Anweisungen[1] ))   // versuche zweite Produktion     
               ||  parse(next,s.mit( Anweisungen[2] )) ; //    ...     
    
    // ... etc für jede Regel der Grammatik ....
    
      else if(s.car().equals("Anweisung")) 
           return  parse(next,s.mit( Anweisung[0] ))      
               ||  parse(next,s.mit( Anweisung[1] ))      
               ||  parse(next,s.mit( Anweisung[2] ))      
               ||  parse(next,s.mit( Anweisung[3] )) ;
               
      else if(s.car().equals("If")) 
            return parse(next,s.mit(If));        
            
      else if(s.car().equals("IfElse")) 
            return parse(next,s.mit(IfElse));                
            
      else if(s.car().equals("While")) 
            return parse(next,s.mit(While));            
            
      else if(s.car().equals("Zuweisung")) 
            return parse(next,s.mit(Zuweisung));

      else if(s.car().equals("Expr")) 
           return  parse(next,s.mit( Expr[0] ))      
               ||  parse(next,s.mit( Expr[1] ))      
               ||  parse(next,s.mit( Expr[2] ));      

      else if(s.car().equals("Term")) 
           return  parse(next,s.mit( Term[0] ))      
               ||  parse(next,s.mit( Term[1] ))      
               ||  parse(next,s.mit( Term[2] )) ;     

      else if(s.car().equals("Faktor")) 
           return  parse(next,s.mit( Faktor[0] ))      
               ||  parse(next,s.mit( Faktor[1] ))      
               ||  parse(next,s.mit( Faktor[2] )) ;      

     else if(s.car().equals("Bexpr")) 
            return parse(next,s.mit(Bexpr));            

   // ... und ganz zum Schluss ...             
      else return false;
  }// Ende von parse
  
// Eingabebeispiel: Eine Liste von Token - repräsentiert als Strings */
   String[] input = {"begin", "if", "id", "=", "id", "then", 
                     "id", ":=", "id", "else", "id", ":=", "id", "end"};


}// Ende von BacktrackParser