Parser: Unterschied zwischen den Versionen

Aus SibiWiki
Zur Navigation springen Zur Suche springen
Zeile 19: Zeile 19:


Diese Implementierungsvariante wird auch im '''Zentralabitur''' verlangt, d.h. man sollte sie <u>mindestens lesen</u> können.
Diese Implementierungsvariante wird auch im '''Zentralabitur''' verlangt, d.h. man sollte sie <u>mindestens lesen</u> können.
Sie ist jedoch relativ fehleranfällig in der Programmierung.
Robuster ist die Programmierung mit einer HashMap - siehe unten.


<code>
<code>
Zeile 75: Zeile 71:
   }
   }
  }
  }
</code>
=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!'''
<code>
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.
            <b>Character neuerZustand = u.get(key);
            if(neuerZustand == null){
                return false;
            }</b>
         
            // zustand aktualisieren
            <b>zustand = neuerZustand;</b>
        }    // 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());
    } 
}
</code>
==Kurze Implementierung==
Die kurze Implementierung legt die Default-Übergänge mithilfe einer for-Schleife fest und überschreibt dann die Ausnahmen.
<code>
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>();
<b>
        // 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');</b>
    }
   
    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());
    }
   
}
</code>
</code>

Version vom 13. September 2015, 12:35 Uhr


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. 

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

Abgerufen von „https://sibiwiki.de/wiki/index.php?title=Parser&oldid=2007“