Parser
Ein Parser zu einer Grammatik ist ein Algorithmus, mit dem sich überprüfen lässt, ob ein Wort zu der von der Grammatik erzeugten Sprache gehört, d.h. ob es syntaktisch korrekt ist. Der Algorithmus lässt sich dann z.B. in Java implementieren.
Ein Parser simuliert den zu der Grammatik gehörenden Automaten.
Beispiel
Es soll ein Parser für den KGB-Automaten (siehe rechts) erstellt werden.
Der KGB-Automat erkennt Wörter, die nur aus den Ziffern 0,...,9 bestehen und die irgendwo die Zahlenkette "007" enhalten.
Implementierung mit switch-case
Die Implementierung mit switch-case bildet den Automaten ab.
Diese Implementierungsvariante wird auch im Zentralabitur verlangt, d.h. man sollte sie mindestens lesen können.
Sie ist jedoch relativ fehleranfällig in der Programmierung.
Robuster ist die Programmierung mit einer HashMap - siehe unten.
import gui.GUI;
public class KGBAutomat {
private char[] alphabet = {'0', '1', '2','3','4','5','6','7','8','9'};
public boolean imAlphabet(char pZeichen){
for(char zeichen: alphabet){
if(zeichen == pZeichen){
return true;
}
}
return false;
}
public boolean parse(String pWort){
char zustand = 'S';
for(char zeichen: pWort.toCharArray()){
if(!imAlphabet(zeichen)){
return false;
}
switch(zustand){
case 'S': switch(zeichen){
case '0': zustand = 'A'; continue;
default: zustand = 'S'; continue;
}
case 'A': switch(zeichen){
case '0': zustand = 'B'; continue;
default: zustand = 'S'; continue;
}
case 'B': switch(zeichen){
case '0': zustand = 'B'; continue;
case '7': zustand = 'C'; continue;
default: zustand = 'S'; continue;
}
case 'C': switch(zeichen){
default: zustand = 'C'; continue;
}
}
}
return (zustand == 'C');
}
public static void main(String[] args) {
new GUI(new KGBAutomat());
}
}
Implementierung mit einer HashMap
Bei dieser Implementierung werden alle Übergänge in eine Hashmap eingetragen! Dann kann man aus der HashMap direkt den neuen Zustand auslesen, der sich aus einem Zustand und einem Zeichen ergibt.
Einfache Implementierung
Bei der einfachen Implementierung wird jeder Übergang einzeln in die HashMap eingetragen.
Das kann ggf. langatmig sein, ist aber logisch sehr einfach.
In der Klausur darf man sich mit "..." Schreibarbeit sparen!
import java.util.HashMap;
import gui.GUI;
public class KGBAutomat {
// parametrisierte HashMap, in der die Uebergange gespeichert werden
private HashMap<String, Character> u;
public KGBAutomat(){
u = new HashMap<String, Character>();
u.put("S0", 'A');
u.put("S1", 'S');
u.put("S2", 'S');
u.put("S3", 'S');
u.put("S4", 'S');
u.put("S5", 'S');
u.put("S6", 'S');
u.put("S7", 'S');
u.put("S8", 'S');
u.put("S9", 'S');
u.put("A0", 'B');
u.put("A1", 'S');
u.put("A2", 'S');
u.put("A3", 'S');
u.put("A4", 'S');
u.put("A5", 'S');
u.put("A6", 'S');
u.put("A7", 'S');
u.put("A8", 'S');
u.put("A9", 'S');
u.put("B0", 'B');
u.put("B1", 'S');
u.put("B2", 'S');
u.put("B3", 'S');
u.put("B4", 'S');
u.put("B5", 'S');
u.put("B6", 'S');
u.put("B7", 'C');
u.put("B8", 'S');
u.put("B9", 'S');
u.put("C0", 'C');
u.put("C1", 'C');
u.put("C2", 'C');
u.put("C3", 'C');
u.put("C4", 'C');
u.put("C5", 'C');
u.put("C6", 'C');
u.put("C7", 'C');
u.put("C8", 'C');
u.put("C9", 'C');
}
public boolean parse(String pWort){
System.out.println(pWort);
// den Startzustand festlegen
char zustand = 'S';
// die Zeichen von pWort mit einer Schleife durchlaufen
for(char zeichen: pWort.toCharArray()){
System.out.println(zustand+": "+zeichen);
// den Schluessel fuer die HashMap bauen
String key = ""+zustand+zeichen;
// den neuen Zustand aus der HashMap auslesen
// man nutzt die Wrapper-Klasse Character,
// damit man abfragen kann, ob neuerZustand null ist.
Character neuerZustand = u.get(key);
if(neuerZustand == null){
return false;
}
// zustand aktualisieren
zustand = neuerZustand;
} // end for
// es wird zurueckgegeben, ob der zustand == 'C' ist.
// d.h. true oder false
return (zustand == 'C');
}
public static void main(String[] args) {
new GUI(new KGBAutomat());
}
}
Kurze Implementierung
Die kurze Implementierung legt die Default-Übergänge mithilfe einer for-Schleife fest und überschreibt dann die Ausnahmen.
import java.util.HashMap;
import gui.GUI;
public class KGBAutomat {
// parametrisierte HashMap, in der die Uebergange gespeichert werden
private HashMap<String, Character> u;
public KGBAutomat(){
u = new HashMap<String, Character>();
// die Default-Uebergaenge fuer alle 4 Zustaende
for(int i=0; i<=9; i++){
u.put("S"+i, 'S');
u.put("A"+i, 'S');
u.put("B"+i, 'S');
u.put("C"+i, 'C');
}
// jetzt kommen die Ausnahmen!
// die ueberschreiben die bisherigen Default-Uebergaenge
u.put("S0", 'A');
u.put("A0", 'B');
u.put("B0", 'B');
u.put("B7", 'C');
}
public boolean parse(String pWort){
System.out.println(pWort);
// den Startzustand festlegen
char zustand = 'S';
// die Zeichen von pWort mit einer Schleife durchlaufen
for(char zeichen: pWort.toCharArray()){
System.out.println(zustand+": "+zeichen);
// den Schluessel fuer die HashMap bauen
String key = ""+zustand+zeichen;
// den neuen Zustand aus der HashMap auslesen
// man nutzt die Wrapper-Klasse Character,
// damit man abfragen kann, ob neuerZustand null ist.
Character neuerZustand = u.get(key);
if(neuerZustand == null){
return false;
}
zustand = neuerZustand;
} // end for
// es wird zurueckgegeben, ob der zustand == 'C' ist.
// d.h. true oder false
return (zustand == 'C');
}
public static void main(String[] args) {
new GUI(new KGBAutomat());
}
}