Parser: Unterschied zwischen den Versionen

Aus SibiWiki
Zur Navigation springen Zur Suche springen
 
(21 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 4: Zeile 4:
[[Kategorie:Informatik]]
[[Kategorie:Informatik]]


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.
=Fachbegriffe=


Man könnte auch sagen: <u>'''Ein Parser simuliert den zu der Grammatik gehörenden Automaten'''</u>.
Scanner, Parser, Interpreter, Zustand, Wort, Buchstabe, switch-case
=Begriffsklärung: Scanner, Parser, Interpreter=
Ein '''Scanner''' zu einem Alphabet überprüft, ob ein Wort ausschließlich aus Buchstaben des Alphabets besteht.


=Beispiel=
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.<br>
[[File:Automat007.png|thumb|KGB-Automat |456px]]
 
Ein '''Interpreter''' (im Sinne der Softwaretechnik) ist ein Computerprogramm, das einen Programm-Quellcode einliest, analysiert und ausführt.


Es soll ein Parser für den KGB-Automaten (siehe rechts) erstellt werden.
Im Umgang mit Programm-Quellcode ergibt sich folgende Arbeitsfolge:


Der KGB-Automat erkennt Wörter, die nur aus den Ziffern 0,...,9 bestehen und die irgendwo die Zahlenkette "007" enhalten.
'''Scanner &rarr; Parser &rarr; Interpreter'''


=Implementierung mit switch-case=
=Funktionsweise des Parsers=
Die Implementierung mit switch-case bildet den Automaten ab.


Sie ist jedoch relativ fehleranfällig in der Programmierung.
'''Ein Parser simuliert den zu der Grammatik gehörenden Automaten'''.


Einfacher ist die Programmierung mit einer HashMap - siehe unten.
* Im folgenden wird der Parser für einen '''[[Deterministischer Endlicher Automat|Deterministischen Endlichen Automaten]]''' beschrieben.
* Der Parser für einen '''[[Kellerautomat]]''' findet sich '''[[Kellerautomat#Parser_für_einen_Kellerautomaten|hier]]'''.


<code>
=Beispiel=
[[File:007automat.png|thumb|Übergangsgraph des KGB-Automaten |557px]]
 
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.


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


=Implementierung mit einer HashMap=
=Implementierung mit switch-case=
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==
Die Implementierung mit switch-case bildet den Automaten ab.
Bei der einfachen Implementierung wird jeder Übergang einzeln in die HashMap eingetragen.


Das kann ggf. langatmig sein, ist aber logisch sehr einfach.
'''Diese Implementierungsvariante ist nur bedingt klausurgeeignet.'''<br/>
'''Für Klausuren nimmt man besser die Variante mit <code>else if</code>.'''


'''In der Klausur darf man sich mit "..." Schreibarbeit sparen!'''
<u>Hinweis:</u> Die Zustände werden duch '''Zahlen''' (<code>int</code>) abgebildet, die "Buchstaben" des zu prüfenden Wortes dagegen sind <code>char</code>, d.h. z.B. <code>'0'</code>


<code>
<code>import gui.GUI;
import java.util.HashMap;
   
   
  import gui.GUI;
  public class KGBAutomat {
   
   
  private char[] alphabet = {'0', '1', '2','3','4','5','6','7','8','9'};
   
   
public class KGBAutomat {
  '''public boolean imAlphabet(char pZeichen){'''
    // parametrisierte HashMap, in der die Uebergange gespeichert werden
      for(int i=0; i<alphabet.length; i++){
    '''private HashMap<String, Character> u;'''
          char zeichen = alphabet[i];
   
          if(zeichen == pZeichen){
    '''public KGBAutomat(){'''
              return true;
        '''u = new HashMap<String, Character>();'''
          }
      }
      return false;
  }
   
   
        u.put("S0", 'A');
  // ueberprueft, ob pWort aus Buchstaben des Alphabets besteht
        u.put("S1", 'S');
  '''public boolean scan(String pWort){'''
        u.put("S2", 'S');
      for(int i=0; i<pWort.length(); i++){
        u.put("S3", 'S');
          char zeichen = pWort.charAt(i);
        u.put("S4", 'S');
          if(!imAlphabet(zeichen)){
        u.put("S5", 'S');
              return false;
        u.put("S6", 'S');
          }
        u.put("S7", 'S');
      }
        u.put("S8", 'S');
      return true;
        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;'''
  '''public boolean parse(String pWort){'''
         
      //erst auf das Alphabet ueberpruefen
            // den neuen Zustand aus der HashMap auslesen
      if(scan(pWort) == false){
            // man nutzt die Wrapper-Klasse Character,
          return false;
            // damit man abfragen kann, ob neuerZustand null ist.
      }
            <b>Character neuerZustand = u.get(key);
      int zustand = 0;
            if(neuerZustand == null){
      for(int i=0; i<pWort.length(); i++){
                return false;
          char zeichen = pWort.charAt(i);
            }</b>
          switch(zustand){
              case 0: switch(zeichen){
                          case '0': zustand = 1; continue;
                          default: zustand = 0; continue;
                      }
            
            
            // zustand aktualisieren
              case 1: switch(zeichen){
            <b>zustand = neuerZustand;</b>
                          case '0': zustand = 2; continue;
        }   // end for
                          default: zustand = 0; continue;
     
                      }
        // es wird zurueckgegeben, ob der zustand == 'C' ist.
                 
        // d.h. true oder false
              case 2: switch(zeichen){
        return (zustand == 'C');
                          case '0': zustand = 2; continue;
    }
                          case '7': zustand = 3; continue;
                          default: zustand = 0; continue;
              }
              case 3: switch(zeichen){
                          default: zustand = 3; continue;
              }
          }
      }
      return (zustand == 3);
  }
   
   
    public static void main(String[] args) {
  public static void main(String[] args) {
        new GUI(new KGBAutomat());
      new GUI(new KGBAutomat());
    }
  }
  }
  }</code>


=Implementierung mit <code>else if</code>=


'''Die Implementierung mit <code>else if</code> ist vor allem für Klausuren geeignet, weil man sich so keine neue Syntax merken muss!'''


</code>
<code>public boolean parse(String pWort){
 
    int zustand = 0;
==Kurze Implementierung==
    for(int i=0; i<pWort.length(); i++){
Die kurze Implementierung legt die Default-Übergänge mithilfe einer for-Schleife fest und überschreibt dann die Ausnahmen.
        char zeichen = pWort.charAt(i);
 
        '''if'''(zustand == 0){
 
            '''if'''(zeichen == '0') zustand = 1;
<code>
            '''else''' zustand = 0;
import java.util.HashMap;
        }
        '''else if'''(zustand == 1){
import gui.GUI;
            '''if'''(zeichen == '0') zustand = 2;
            '''else''' zustand = 0;
        }
        '''else if'''(zustand == 2){
            '''if'''(zeichen == '0') zustand = 2;
            '''else if'''(zeichen == '7') zustand = 3;
            '''else''' zustand = 0;
        }
        // die einzig verbleibende Moeglichkeit ist zustand==3
        // d.h. man braucht kein else if mehr!
        '''else''' {
            zustand = 3;
        }
    }
   
   
 
    //zurueckgeben, ob der Zustand 3 erreicht wurde.
public class KGBAutomat {
    return (zustand == 3);
    // parametrisierte HashMap, in der die Uebergange gespeichert werden
  }</code>
    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>

Aktuelle Version vom 10. April 2024, 06:58 Uhr


Fachbegriffe

Scanner, Parser, Interpreter, Zustand, Wort, Buchstabe, switch-case

Begriffsklärung: Scanner, Parser, Interpreter

Ein Scanner zu einem Alphabet überprüft, ob ein Wort ausschließlich aus Buchstaben des Alphabets besteht.

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 Interpreter (im Sinne der Softwaretechnik) ist ein Computerprogramm, das einen Programm-Quellcode einliest, analysiert und ausführt.

Im Umgang mit Programm-Quellcode ergibt sich folgende Arbeitsfolge:

Scanner → Parser → Interpreter

Funktionsweise des Parsers

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 ist nur bedingt klausurgeeignet.
Für Klausuren nimmt man besser die Variante mit else if.

Hinweis: Die Zustände werden duch Zahlen (int) abgebildet, die "Buchstaben" des zu prüfenden Wortes dagegen sind char, d.h. z.B. '0' 

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(int i=0; i<alphabet.length; i++){
         char zeichen = alphabet[i];
         if(zeichen == pZeichen){
             return true;
         }
     }
     return false;
 }

 // ueberprueft, ob pWort aus Buchstaben des Alphabets besteht
 public boolean scan(String pWort){
     for(int i=0; i<pWort.length(); i++){
         char zeichen = pWort.charAt(i);
         if(!imAlphabet(zeichen)){
             return false;
         }
     }
     return true;
 }
 

 public boolean parse(String pWort){
     //erst auf das Alphabet ueberpruefen
     if(scan(pWort) == false){
         return false;
     }
     int zustand = 0;
     for(int i=0; i<pWort.length(); i++){
         char zeichen = pWort.charAt(i);
         switch(zustand){
             case 0: switch(zeichen){
                         case '0': zustand = 1; continue;
                         default: zustand = 0; continue;
                     }
          
             case 1: switch(zeichen){
                         case '0': zustand = 2; continue;
                         default: zustand = 0; continue;
                     }
                  
             case 2: switch(zeichen){
                         case '0': zustand = 2; continue;
                         case '7': zustand = 3; continue;
                         default: zustand = 0; continue;
             }
             case 3: switch(zeichen){
                         default: zustand = 3; continue;
             }
         }
     }
     return (zustand == 3);
 }

 public static void main(String[] args) {
     new GUI(new KGBAutomat());
 }
}

Implementierung mit else if

Die Implementierung mit else if ist vor allem für Klausuren geeignet, weil man sich so keine neue Syntax merken muss! 

public boolean parse(String pWort){
    int zustand = 0;
    for(int i=0; i<pWort.length(); i++){
        char zeichen = pWort.charAt(i);
        if(zustand == 0){
            if(zeichen == '0') zustand = 1;
            else zustand = 0;
        }
        else if(zustand == 1){
            if(zeichen == '0') zustand = 2;
            else zustand = 0;
        }
        else if(zustand == 2){
            if(zeichen == '0') zustand = 2;
            else if(zeichen == '7') zustand = 3;
            else zustand = 0;
        }
        // die einzig verbleibende Moeglichkeit ist zustand==3
        // d.h. man braucht kein else if mehr!
        else {
            zustand = 3;
        }
    }

    //zurueckgeben, ob der Zustand 3 erreicht wurde.
    return (zustand == 3);
 }
Abgerufen von „https://sibiwiki.de/wiki/index.php?title=Parser&oldid=3697“