/* Die Grammatik:
 *
 * KA        ::= Buchstabe | '(' KA ')' | '[' KA ']' | '{' KA '}'
 * Buchstabe ::= 'a' [ Buchstabe] | 'b' { 'a' | 'b'}
 * 
 * Umgeschrieben für den Syntaxchecker:
 *
 * KA                  ::= 'a' BuchstabeOptional | 'b' BuchstabeWiederholt | 
 *                         '(' KA ')' | '[' KA ']' | '{' KA '}'
 * BuchstabeOptional   ::= ['a' BuchstabeOptional | 'b' BuchstabeWiederholt]
 * BuchstabeWiederholt ::= {'a' | 'b'} 
 */

/*--------------------------------------------------------------------------*/

import java.util.StringTokenizer;

/*--------------------------------------------------------------------------*/

public class Syntaxchecker
{
    //Token
    static final int UNDEF = 0;
    static final int RKA   = 1;
    static final int RKZ   = 2;
    static final int EKA   = 3;
    static final int EKZ   = 4;
    static final int GKA   = 5;
    static final int GKZ   = 6;
    static final int A     = 7;
    static final int B     = 8;
    static final int ENDTK = 9;

    //Tokenizer
    static StringTokenizer at;

    //der bereits überprüfte String zur Ausgabe bei Fehlern
    static String parsedSubstring = "";

    //Merker für zurückgelegte Token
    static int lastToken = -1;

    /* --- lexikalische Analyse ------------------------------------------- */

    /* Methode, die das nächste Token ermittelt und zurückgibt
     * Rückgabewert: nächstes Token, dass in einer Regel ausgewertet werden
     *               muss
     */
    public static int getNextToken()
    {
	//wenn ein Token zurückgelegt wurde, muss es zunächst ausgewertet
	//werden
	if(lastToken != -1)
	{
	    //zurückgelegtes Token auf -1 zurücksetzen, da es jetzt verbraucht
	    //wird
	    int help = lastToken;
	    lastToken = -1;
	    return help;
	}

	//am Ende des Strings angekommen, Ende zurückliefern
        if(!at.hasMoreTokens())
	{
	    return ENDTK;
	}

	//das nächste Token holen
	//dieses Token gilt nun als bearbeitet und wird dem bereits parsierten
	//String zugefügt
	String aux = at.nextToken();
	parsedSubstring = parsedSubstring + aux + " ";

	//Überprüfung auf Token
	if(aux.equals("("))
	    return RKA;

	if(aux.equals(")"))
	   return RKZ;
	  
	if(aux.equals("["))
	    return EKA;

	if(aux.equals("]"))
	    return EKZ;

	if(aux.equals("{"))
	    return GKA;
	
	if(aux.equals("}"))
	    return GKZ;

	if(aux.equals("a"))
	    return A;

	if(aux.equals("b"))
	    return B;

	//Leerzeichen überspringen
	if((aux.equals(" ")) || aux.equals("\t"))
	   return getNextToken();

	//Undefiniertes Zeichen, kein Token erkannt
	return UNDEF;
    }

    /* --- syntaktische Analyse ------------------------------------------- */

    /* Methode, mit der die Regel BuchstabeOptional überprüft wird
     * Rückgabewert: true, wenn die Regel korrekt erkannt wurde
     *               false, sonst
     */
    public static boolean checkBuchstabeOptional()
    {
	//wir merken uns das zu überprüfende Token
	int merker = getNextToken();

	//Fallunterscheidung anhand der Regel:
	//bei 'a' müssen wir weiterhin auf optionale Buchstaben überprüfen
	//bei 'b' müssen wir auf wiederholte Buchstaben überprüfen
	//ansonsten trifft der optionale Fall nicht zu, das Token muss 
	//zurückgelegt werden, damit die übergeordnete Regel es als nächstes
	//Token zur Verfügung hat
	switch(merker)
	{
	    case A: 
		return checkBuchstabeOptional();
	    case B:
		return checkBuchstabeWiederholt();
	    case EKA:  
	    case EKZ:
	    case RKA:
	    case RKZ:
	    case GKA:
	    case GKZ:
	    case ENDTK:
		lastToken = merker;
		return true;
	    default:
		return false;
	}
    }

    /* Methode, mit der die Regel BuchstabeWiederholt überprüft wird
     * Rückgabewert: true, wenn die Regel korrekt erkannt wurde
     *               false, sonst
     */
    public static boolean checkBuchstabeWiederholt()
    {
	//wir merken uns das zu überprüfende Token
	int merker = getNextToken();

	//Fallunterscheidung anhand der Regel:
	//bei 'a' oder 'b' müssen wir weiterhin auf Buchstaben überprüfen
	//ansonsten trifft der optionale Fall nicht zu, das Token muss 
	//zurückgelegt werden, damit die übergeordnete Regel es als nächstes
	//Token zur Verfügung hat
	switch(merker)
	{
	    case A: 
	    case B:
		return checkBuchstabeWiederholt();
	    case EKA:
	    case EKZ:
	    case RKA:
	    case RKZ:
	    case GKA:
	    case GKZ:
	    case ENDTK:
		lastToken = merker;
		return true;
	    default:
		return false;
	}
    }

    /* Methode, mit der die Regel KA überprüft wird
     * Rückgabewert: true, wenn die Regel korrekt erkannt wurde
     *               false, sonst
     */
    public static boolean checkKA()
    {
	//die Alternativen Fälle anhand des erkannten Tokens überprüfen
	switch(getNextToken())
	{
	    //runde Klammer auf: nun folgt KA und runde Klammer zu, sonst
	    //Fehler
	    case RKA: 
		if(!checkKA())
		    return false;
		if(getNextToken() != RKZ)
		    return false;
		return true;
	    //eckige Klammer auf: nun folgt KA und eckige Klammer zu, sonst
	    //Fehler
	    case EKA:
		if(!checkKA())
		    return false;
		if(getNextToken() != EKZ)
		    return false;
		return true;
	    //geschweifte Klammer auf: nun folgt KA und geschweifte Klammer zu,
	    //sonst Fehler
	    case GKA:
		if(!checkKA())
		    return false;
		if(getNextToken() != GKZ)
		    return false;
		return true;
	    //'a', optional weitere Buchstaben
	    case A:
		return checkBuchstabeOptional();
	    //'b', Wiederholung möglich
	    case B:
		return checkBuchstabeWiederholt();
	    //irgendetwas anderes wurde erkannt, Fehler!
	    default:
		return false;
	}
    }

    /* main */
    public static void main(String args[])
    {
	//Tokenizer initialisieren:
	//args[0] ist der zu überprüfende String
	//()[]{}ab \t sind die Zeichen, an denen Token abgetrennt werden
	//true besagt, dass die Trennzeichen als Token erkannt werden, bei
	//false würden nur die Zeichen zwischen den Trennzeichen als Token
	//gelten
	at = new StringTokenizer(args[0], "()[]{}ab \t", true);

	//oberste Regel wurde korrekt erkannt, dass letzte Token ist ENDTK
	if(checkKA() && (getNextToken() == ENDTK))
	    System.out.println("Der eingegebene Term ist syntaktisch korrekt.");        //Regel wurde nicht korrekt erkannt, Fehlermeldung anhand des 
	//in parsedSubstring gemerkten Strings
	else
	    System.out.println("Der eingegeben Term ist syntaktisch" +
                               " nicht korrekt: Fehler bei '" +
			       parsedSubstring + "'");
    }
}