Parser: Unterschied zwischen den Versionen

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


=Fachbegriffe=
Scanner, Parser, Interpreter, Zustand, Wort, Buchstabe, switch-case
=Begriffsklärung: Scanner, Parser, Interpreter=
=Begriffsklärung: Scanner, Parser, Interpreter=
Ein '''Scanner''' zu einem Alphabet überprüft, ob ein Wort ausschließlich aus Buchstaben des Alphabets besteht.
Ein '''Scanner''' zu einem Alphabet überprüft, ob ein Wort ausschließlich aus Buchstaben des Alphabets besteht.


Zeile 29: Zeile 31:


Der KGB-Automat erkennt Wörter, die nur aus den Ziffern 0,...,9 bestehen und die irgendwo die Zahlenkette "007" enhalten.
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=
=Implementierung mit switch-case=
Die Implementierung mit switch-case bildet den Automaten ab.
Die Implementierung mit switch-case bildet den Automaten ab.


<code>
'''Diese Implementierungsvariante ist nur bedingt klausurgeeignet.'''<br/>
'''Für Klausuren nimmt man besser die Variante mit <code>else if</code>.'''


  import gui.GUI;
<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>import gui.GUI;
   
   
  '''public class KGBAutomat {'''
  public class KGBAutomat {
   
   
  '''private char[] alphabet''' = {'0', '1', '2','3','4','5','6','7','8','9'};
  private char[] alphabet = {'0', '1', '2','3','4','5','6','7','8','9'};
   
   
  '''public boolean imAlphabet(char pZeichen){'''
  '''public boolean imAlphabet(char pZeichen){'''
      for(char zeichen: alphabet){
      for(int i=0; i<alphabet.length; i++){
          if(zeichen == pZeichen){
          char zeichen = alphabet[i];
              return true;
          if(zeichen == pZeichen){
          }
              return true;
      }
          }
      return false;
      }
  }
      return false;
  }
   
   
  '''public boolean scan(String pWort){'''
  // ueberprueft, ob pWort aus Buchstaben des Alphabets besteht
      for(char zeichen: pWort.toCharArray()){
  '''public boolean scan(String pWort){'''
          if(!imAlphabet(zeichen)){
      for(int i=0; i<pWort.length(); i++){
              return false;
          char zeichen = pWort.charAt(i);
          }
          if(!imAlphabet(zeichen)){
      }
              return false;
      return true;
          }
  }
      }
   
      return true;
  }
 
   
   
  '''public boolean parse(String pWort){'''
  '''public boolean parse(String pWort){'''
      //erst auf das Alphabet ueberpruefen
      //erst auf das Alphabet ueberpruefen
      if(scan(pWort) == false){
      if(scan(pWort) == false){
          return false;
          return false;
      }
      }
      char zustand = 'S';
      int zustand = 0;
      for(char zeichen: pWort.toCharArray()){
      for(int i=0; i<pWort.length(); i++){
          switch(zustand){
          char zeichen = pWort.charAt(i);
              case 'S': switch(zeichen){
          switch(zustand){
                          case '0': zustand = 'A'; continue;
              case 0: switch(zeichen){
                          default: zustand = 'S'; continue;
                          case '0': zustand = 1; continue;
                      }
                          default: zustand = 0; continue;
           
                      }
              case 'A': switch(zeichen){
         
                          case '0': zustand = 'B'; continue;
              case 1: switch(zeichen){
                          default: zustand = 'S'; continue;
                          case '0': zustand = 2; continue;
                      }
                          default: zustand = 0; continue;
                   
                      }
              case 'B': switch(zeichen){
                 
                          case '0': zustand = 'B'; continue;
              case 2: switch(zeichen){
                          case '7': zustand = 'C'; continue;
                          case '0': zustand = 2; continue;
                          default: zustand = 'S'; continue;
                          case '7': zustand = 3; continue;
              }
                          default: zustand = 0; continue;
              case 'C': switch(zeichen){
              }
                          default: zustand = 'C'; continue;
              case 3: switch(zeichen){
              }
                          default: zustand = 3; continue;
          }
              }
      }
          }
      return (zustand == 'C');
      }
  }
      return (zustand == 3);
  }
  public static void main(String[] args) {
      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>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;
        }
    }
   
   
  public static void main(String[] args) {
    //zurueckgeben, ob der Zustand 3 erreicht wurde.
      new GUI(new KGBAutomat());
    return (zustand == 3);
  }
  }</code>
}
</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);
 }