#include <stdio.h>
#include <string.h> 

/*-------------------------------------------------------------
Beispiel für einen Syntaxchecker.

Dieser prüft Klammerausdruecke <KA> nach der Grammatik

<KA> ::= <Buchstabe> | '(' <KA> ')' | '[' <KA> ']' | '{' <KA> '}'
<Buchstabe> ::= 'a' [ <Buchstabe> ] | 'b' [ <Buchstabe> ]

In dieser Syntax sind also alle Klammerungen von 'a' oder 'b' 
erlaubt, bei denen  der Typ jeder offenen Klammer
auch der schließenden Klammer an der entsprechenden 
Position gleicht:
  
Beispiel: (({[aabab]})) ist erlaubt, (({[a]))) aber nicht.

Der Klammerausdruck wird über die Kommandozeile übergeben.

 */

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

/*--- ka enthaelt den gesamten Klammerausdruck.
      ka_rest zeigt auf den Character in ka, von dem
      ab noch Syntax zu checken ist.
      ----*/
char *ka;

char *ka_rest;

char *ka_last;

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

/*--- Aufzählung der Lexeme unserer Sprache  ---*/ 
typedef enum { runde_klammer_auf, 
               eckige_klammer_auf, 
               geschweifte_klammer_auf, 
               runde_klammer_zu, 
               eckige_klammer_zu, 
               geschweifte_klammer_zu, 
               buchstabe_a,
               buchstabe_b,
               unbekannt,
               string_ende }
ka_tokens_t;

typedef enum { check_ok, check_fehlerhaft } check_ergebnis_t;

/*------------------------------------------------------------
 * Der Scanner getToken() abstrahiert die konkrete 
 * Zeichendarstellung zu enum-Werten. Dadurch muss
 * bei Änderung des Zeichensatzes NUR der Scanner, aber nicht
 * der Syntax-Checker angepasst werden.
 *------------------------------------------------------------*/

ka_tokens_t getToken(void) {

    ka_tokens_t retcode;

    /*
    Wir merken uns, wo wir gerade stehen.
    Dann kann putToken() durch Verwendung
    von ka_last den vorherigen Zustand
    wieder herstellen.*/
    ka_last = ka_rest;

    /*--- lasse Leerzeichen oder Tabs verschwinden ---*/
    while ( strlen(ka_rest) != 0 
	    && ( *ka_rest == ' '  || *ka_rest == '\t' ) )
	ka_rest++;

    if ( strlen(ka_rest) == 0 ) return string_ende;

    switch(ka_rest[0]) {
	case '(': retcode = runde_klammer_auf; break;
	case '[': retcode = eckige_klammer_auf; break;
 	case '{': retcode = geschweifte_klammer_auf; break;
 	case '}': retcode = geschweifte_klammer_zu; break;
	case ']': retcode = eckige_klammer_zu; break;
	case ')': retcode = runde_klammer_zu; break;
 	case 'a': retcode = buchstabe_a; break;
 	case 'b': retcode = buchstabe_b; break;
	default: retcode =  unbekannt; break; 
    }

    ka_rest = ka_rest + 1;

    return retcode;

}

/*-------------------------------------------------------------
 * putToken() "legt das aktuelle Token zurueck": Wir gehen zurueck
 * an die Stelle im String, von der aus das letzte Token 
 * ermittelt wurde.
 *-------------------------------------------------------------*/
void putToken(void) {
    ka_rest = ka_last;
}

/*-----------------------------------------------------------
 * Ein Buchstabe muss mindestens kommen. Dies wird in 
 * checkBuchstabe() geprueft. Weitere Buchstaben sind optinal.
 * Dies checken wird in checkBuchstabeOptional().
 *----------------------------------------------------------*/


check_ergebnis_t checkBuchstabeOptional(void) {

    ka_tokens_t tok = getToken();

    switch (tok) {
	case buchstabe_a:
	case buchstabe_b:
	    return checkBuchstabeOptional();
	case runde_klammer_auf:
	case eckige_klammer_auf:
	case geschweifte_klammer_auf:
	case runde_klammer_zu:
	case eckige_klammer_zu:
	case geschweifte_klammer_zu:
            /*
            Lege das aktuelle Token zurueck.
            Der andere Checker wird sich um
            dessen Pruefung kuemmern. Aus
            Sicht des Buchstaben-Checkers ist bis hierhin
            alles ok.
	    */
	    putToken();
	    return check_ok;
	case string_ende:
	    return check_ok;
	default: 
            return check_fehlerhaft;
    }

}


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

check_ergebnis_t checkBuchstabe(void) {

    ka_tokens_t tok = getToken();

    switch (tok) {
	case buchstabe_a:
	case buchstabe_b:
	    return checkBuchstabeOptional();
	default: 
            return check_fehlerhaft;
    }

}

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

check_ergebnis_t checkKA(void) {

    ka_tokens_t tok = getToken();

    /* Grammatik zeigt im anzuwendenden nicht-terminalen
       Symbol (hier <KA>), dass Alternativen zu pruefen sind.
       ( | ). Dies fuehrt im Checker auf ein switch()-Statement
    */
    switch ( tok ) {

	case string_ende: return check_ok;

	case runde_klammer_auf:
            /*
            Hier zeigt die Grammatik, dass eine Sequenz
            von nicht-terminalen und terminalen Symbolen
            (an dieser Stelle  "<KA> ')'" ) zu pruefen ist.
            Dies kann immer durch das folgende Muster mit
            Sequenzen von if-statements 
            realisiert werden:
	    */ 
	    if ( checkKA() == check_fehlerhaft ) 
                     return check_fehlerhaft;
            if ( getToken() != runde_klammer_zu )
                     return check_fehlerhaft;
	    return check_ok;

	case eckige_klammer_auf:
	    if ( checkKA() == check_fehlerhaft )
                      return check_fehlerhaft;
            if ( getToken() != eckige_klammer_zu )
                      return check_fehlerhaft;
	    return check_ok;

	case geschweifte_klammer_auf:
	    if ( checkKA() == check_fehlerhaft )
                 return check_fehlerhaft;
            if ( getToken() != geschweifte_klammer_zu )
                 return check_fehlerhaft;
	    return check_ok;

	default: 
            putToken(); 
            return checkBuchstabe();
    }

}


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

check_ergebnis_t syntaxChecker(void) {

    return checkKA();

}


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

int main(int argc, char **argv) {

    check_ergebnis_t erg;

    if ( argc < 2 ) {
     printf("%s: Klammerausdruck fehlt als Parameter - stop\n",
        argv[0]);
	exit(1);
    }

    /*
      strdup(s) legt dynamisch Speicher an und kopiert den
      Inhalt von s samt terminierendem 0-char in den neuen
      Speicher. Ein Pointer auf den neuen Speicher wird
      zurueckgegeben.

      a = b = c; sind Mehrfachzuweisungen: c wird nach a UND
      b zugewiesen.
    */
    ka = ka_rest = strdup(argv[1]);
    ka_last = NULL;

    erg = syntaxChecker();

    if ( erg == check_ok ) {
	if ( strlen(ka_rest) == 0 ) {
	    printf("%s: Klammerausdruck %s ist korrekt\n",
                   argv[0],ka);
	}
	else {
	    printf("%s: illegaler Rest %s\n",
                   argv[0],ka_rest);
	}
    }
    else {

	printf("%s: Klammerausdruck %s ist falsch ab ",
               argv[0],ka);

	ka_rest--;
	*ka_rest = 0;
	printf("%s\n",ka);

    }

    exit(0);

   
}