Parser: Unterschied zwischen den Versionen

Aus SibiWiki
Zur Navigation springen Zur Suche springen
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 z.B. in Java implementieren.
=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.<br>
Vorab muss jedoch geprüft werden, ob das Wort ausschließlich aus Buchstaben des Alphabets besteht, d.h. es ergibt sich folgende
 
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 &rarr; Parser &rarr; Interpreter'''
 
=Funktionsweise des Parsers=


'''Ein Parser simuliert den zu der Grammatik gehörenden [[Deterministischer Endlicher Automat|Automaten]]'''.
'''Ein Parser simuliert den zu der Grammatik gehörenden [[Deterministischer Endlicher Automat|Automaten]]'''.
<font color='red'>'''Parser sind nur für den LK relevant!'''</font>


=Beispiel=
=Beispiel=
Zeile 37: Zeile 48:
   }
   }
   
   
   '''public boolean parse(String pWort){'''
   '''public boolean scan(String pWort){'''
      char zustand = 'S';
       for(char zeichen: pWort.toCharArray()){
       for(char zeichen: pWort.toCharArray()){
           if(!imAlphabet(zeichen)){
           if(!imAlphabet(zeichen)){
               return false;
               return false;
           }
           }
      }
      return true;
  }
   
  '''public boolean parse(String pWort){'''
      //erst auf das Alphabet ueberpruefen
      if(scan(pWort) == false){
          return false;
      }
      char zustand = 'S';
      for(char zeichen: pWort.toCharArray()){
           switch(zustand){
           switch(zustand){
               case 'S': switch(zeichen){
               case 'S': switch(zeichen){

Version vom 13. November 2017, 14:49 Uhr


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.
Vorab muss jedoch geprüft werden, ob das Wort ausschließlich aus Buchstaben des Alphabets besteht, d.h. es ergibt sich folgende

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.

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 scan(String pWort){
      for(char zeichen: pWort.toCharArray()){
          if(!imAlphabet(zeichen)){
              return false;
          }
      }
      return true;
  }
   

  public boolean parse(String pWort){
      //erst auf das Alphabet ueberpruefen
      if(scan(pWort) == false){
          return false;
      }
      char zustand = 'S';
      for(char zeichen: pWort.toCharArray()){
          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());
  }
}