Parser

Aus SibiWiki
Zur Navigation springen Zur Suche springen


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

Übergangsgraph des KGB-Automaten

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