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 in Java implementieren.

Man könnte auch sagen: Ein Parser simuliert den zu der Grammatik gehörenden Automaten.

Beispiel

Es soll ein Parser für den KGB-Automaten 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.

Sie ist jedoch relativ fehleranfällig in der Programmierung.

Einfacher 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());
   }
   
}