Startseite < Informatik < Algorithmen Datenstrukturen / Software-Engineering / Programmiersprachen < Compiler Interpreter < Setty < Setty-Präprozessor [ DRUCK , 2004 , 2005 , 2006 , 2007 , 2008 , 2009 ] Setty-Scanner Setty-Parser > Tinyray > / Java C/C++ POV-Ray LaTeX > / Künstliche Intelligenz > Schach Privates / Inhalt >
Setty-Scanner
Ein verhältnismäßig einfacher Scanner zur Quellsprache Setty.
Setty-Scanner Der Scanner zur Sprache: Setty
Setty's Scanner
Dieser Scanner kann eine Zeichenkette, in der alle Terminalsymole T folgender Grammatik SG in beliebiger Reihenfolge vorkommen dürfen, tokenweise lesen.
Die Grammatik der Setty-Sprache
Setty-Grammatik SG = (N, T, P, S) mit

N = {Program, SetU, SetI, SetD, Set, From, To},

T = {LPAREN1      := '(',     RPAREN1      := ')',
     LPAREN2      := '[',     RPAREN2      := ']',
     LPAREN3      := '{',     RPAREN3      := '}',
     PLUS         := '+',     MINUS        := '-',
     SEMICOLON    := ';',     QUESTIONMARK := '?',
     COMPLEMENT   := 'C',     UNION        := 'u'|'v',
     INTERSECTION := 'n',     DIFFERENCE   := '\',
     IS           := 'Is',    IN           := 'in',
     NOT          := 'not',
     NUMBER       := ['+'|'-']('0'-'9')+['.'('0'-'9')+],
     INFINITY     := 'inf'},

P = {Program ::= IS NUMBER [ NOT ] IN SetU QUESTIONMARK,
     SetU    ::= SetI ( UNION SetI )*,
     SetI    ::= SetD ( INTERSECTION SetD )*,
     SetD    ::= Set [ DIFFERENCE Set ],
     Set     ::= COMPLEMENT LPAREN1 SetU RPAREN1
               | LPAREN1 SetU RPAREN1
               | LPAREN3 [ NUMBER ( SEMICOLON NUMBER )* ] RPAREN3
               | From SEMICOLON To,
     From    ::= RPAREN2 ( NUMBER | MINUS INFINITY )
               | LPAREN2 NUMBER,
     To      ::= NUMBER ( LPAREN2 | RPAREN2 )
               | [ PLUS ] INFINITY LPAREN2} und

S = Program.
⇑ Die Grammatik der Setty-Sprache ⇑
Nur die Menge der Terminalsymbole!
Zur Entwicklung eines Scanners benötigt man generell nur die Definition der textuellen Zusammensetzung aller Terminalsymbole T einer Grammatik, nichts weiter!

Die anderen Elemente einer Grammatik N, P und S haben nichts mit dem Scanner zu tun. Der Scanner „konzentriert” sich lediglich auf das tokenweise Lesen. Beim Lesen einer unbekannten Fremdsprache, verhält sich der Mensch wie ein Scanner, er liest wortweise, ohne etwas von der Grammatik zu wissen.

Tokens sind fast wie Hieroglyphen, jede Hieroglyphe besitzt eine Bedeutung, die textuell ausgedrückt werden kann.
Implementierung Implementierung des Setty-Scanners
Zeichenstrom -> Tokenstrom
Da die Hauptarbeit eines Scanners darin liegt, einen Zeichenstrom in einen Tokenstrom umzuwandeln, benötigt man Tokens; es sind zumindest die Terminalsymbole der Grammatik. Hier werden die Tokens als Integer-Konstanten repräsentiert.
Die Setty-Tokens mit Java
/**
 * Die Klasse Token deklariert die mnemonischen Bezeichner
 * für jedes Token der Setty-Sprache.
 */
public class Token {

  /** Token UNKNOWN zur Fehlererkennung. */
  public static final int UNKNOWN       =   0; // (Unbekanntes Token)

  /** Token EOS signalisiert das Ende des Quellprogramms. */
  public static final int EOS           =  10; // (End Of String)

  /* Folgende Tokens bezeichnen alle Terminalsymbole der Setty-Grammatik. */

  public static final int LPAREN1       = 100; // "("
  public static final int RPAREN1       = 110; // ")"
  public static final int LPAREN2       = 120; // "["
  public static final int RPAREN2       = 130; // "]"
  public static final int LPAREN3       = 140; // "{"
  public static final int RPAREN3       = 150; // "}"
  public static final int PLUS          = 160; // "+"
  public static final int MINUS         = 170; // "-"
  public static final int SEMICOLON     = 180; // ";"
  public static final int QUESTIONMARK  = 190; // "?"

  public static final int COMPLEMENT    = 200; // "C" (Komplement)
  public static final int UNION         = 210; // "u" | "v" (Vereinigung)
  public static final int INTERSECTION  = 220; // "n" (Schnitt)
  public static final int DIFFERENCE    = 230; // "\" (Mengenminus)

  public static final int IS            = 300; // "Is"
  public static final int IN            = 310; // "in"
  public static final int NOT           = 320; // "not"

  public static final int NUMBER        = 400; // (Zahl)
  public static final int INFINITY      = 410; // "inf"
}
⇑ Die Setty-Tokens mit Java ⇑
Hierbei kommt es vor allem darauf an, den Tokens sprechende Bezeichnungen (mnemonisch) zu geben. Welche Wertigkeit sich nun hinter einem Tokenbezeichner verbirgt, ist eigentlich egal. Letztendlich müssen die Tokens paarweise unterscheidbar sein.
Um sicherzustellen, dass sich alle aufgeführten Tokens paarweise unterscheiden, können die Tokens auch nach dem Prinzip der Aufzählung deklariert werden:
  1. ...
    public static final int UNKNOWN = 0;
    public static final int EOS = UNKNOWN + 1;
    public static final int LPAREN1 = EOS + 1;
    public static final int RPAREN1 = LPAREN1 + 1;
    ...
Der Scanner würde somit leichter zu warten sein. Neue Tokens können einfach in die Aufzählung eingegliedert werden. Einen Tokenwert nun irrtumlicherweise mehrfach zu verwenden, würde hiermit unmöglich gemacht werden.

Seit der Java-Version 1.5 gibt es erstmals die Möglichkeit mit enum einen Aufzähungstyp in Java zu definieren, was die Deklaration von Token-Typen extrem erleichtert:
  1. public enum TokenType {
    1. UNKNOWN,
      EOS,
      LPAREN1,
      RPAREN1,
      ...
    }
Dank des neuen Enum-Typen muss man sich als Programmierer, nicht mehr um die eindeutige Wertigkeit einzelner Tokens kümmern. Was unter vielen anderen Programmiersprachen schon lange möglich war, ist nun endlich auch mit Java 1.5 möglich.

Sehen Sie hierzu die Tokenklasse von Tinyray-Scanner.
Der Setty-Scanner
Der Setty-Scanner wird dazu verwendet, Setty-Tokens vom gegebenen String source zu lesen.
Folgender Scanner muss zwar nicht viele Token-Typen erkennnen können, dennoch erreicht er eine kaum überschaubare Größe.
Warum das so ist, liegt in der Natur eines jeden Scanners, der zwischen vielen Token-Typen unterscheiden muss, besonders wenn manche Tokens den selben Wortanfang haben wie beispielsweise in und inf (Regel des längsten Musters benötigt viel Programmcode).

Tipp: Der Lesende sollte sich sofort auf die Methode nextToken() stürtzen, da alles andere in der Klasse Scanner nur Detailkram ist und deshalb auch ein bisschen abschreckend wirken könnte.
Der Setty-Scanner mit Java
/**
 * Die Klasse Scanner liest vom aktuellen Zeichen im Setty-Programm stets ein
 * weiteres Token, so dass zu jeder Zeit der Parser dem Scanner befehlen kann:
 * "Gib' mir das nächste Token!" ;-)
 */
public class Scanner {

  /**
   * Repräsentiert das im Konstruktor übergebene Setty-Programm (Source).
   */
  private String source;

  /**
   * Zeigt auf ein Zeichen im Setty-Programm Source.
   */
  private int position;

  /**
   * Das aktuelle Token.
   */
  private int token;

  /**
   * Den Wert des aktuellen Token.
   */
  private String tokenValue;

  /**
   * Prüft, ob noch ein weiteres Zeichen von Source gelesen werden kann.
   * @return true Ja, es kann.
   */
  private boolean hasChar() {
    return (this.position < this.source.length());
  }

  /**
   * Gibt das Zeichen von der aktuellen Position in Source zurück.
   * Die Position wird um 1 erhöht.
   * @return Das Zeichen von der aktuellen Position in Source.
   */
  private char getChar() {
    return this.source.charAt(this.position++);
  }

  /**
   * Prüft, ob noch weitere count Zeichen von Source gelesen werden können.
   * @param count Die Anzahl der Zeichen.
   * @return true Ja, es können.
   */
  private boolean hasString(int count) {
    return (this.position + count <= this.source.length());
  }

  /**
   * Gibt count Zeichen ab der aktuellen Position in Source zurück.
   * Die Position wird um count erhöht.
   * @param count Die Anzahl der Zeichen.
   * @return Die count Zeichen ab der aktuellen Position in Source.
   */
  private String getString(int count) {
    String result = this.source.substring(this.position, this.position + count);
    this.position += count;
    return result;
  }

  /**
   * Prüft, ob aktuell in Source wertemäßig value vorliegt.
   * @return true Ja, es liegt vor.
   */
  private boolean testString(String value) {
    boolean result = false;
    int count = value.length();
    if (this.hasString(count)) {
      result = value.equals(this.getString(count));
      this.back(count);
    }
    return result;
  }

  /**
   * Die Position wird um count heruntergesetzt.
   * @param count Die Anzahl der Zeichen.
   */
  private void back(int count) {
    this.position = Math.max(0, this.position - count);
  }

  /**
   * Erzeugt und initialisiert einen Scanner mit einem Setty-Programm.
   * @param source Das Setty-Programm.
   */
  public Scanner(String source) {
    this.source = source;
    this.position = 0;
    this.token = Token.UNKNOWN;
    this.tokenValue = "";
  }

  /**
   * Gibt das aktuelle Token, welches zuletzt gelesen wurde, zurück.
   * @return Das aktuelle Token.
   */
  public int getToken() {
    return this.token;
  }

  /**
   * Gibt den Wert des aktuellen Tokens, welches zuletzt gelesen wurde, zurück.
   * @return Der Wert des aktuellen Tokens.
   */
  public String getTokenValue() {
    return this.tokenValue;
  }

  /**
   * Liest das nächste Token von der aktuellen Position in Source und
   * gibt es zurück.
   * @return Das nächste Token.
   */
  public int nextToken() {
    this.tokenValue = "";
    this.token = Token.UNKNOWN;

    while (this.hasChar()) {
      char value = this.getChar();

      switch (value) {

        case '\n': case '\r': case '\t': case '\0': case ' ':
          // Whitespaces usw. werden ignoriert! (skip)
          break;

        case '(':
          this.tokenValue = "" + value;
          this.token = Token.LPAREN1;
          return this.token;

        case ')':
          this.tokenValue = "" + value;
          this.token = Token.RPAREN1;
          return this.token;

        case '[':
          this.tokenValue = "" + value;
          this.token = Token.LPAREN2;
          return this.token;

        case ']':
          this.tokenValue = "" + value;
          this.token = Token.RPAREN2;
          return this.token;

        case '{':
          this.tokenValue = "" + value;
          this.token = Token.LPAREN3;
          return this.token;

        case '}':
          this.tokenValue = "" + value;
          this.token = Token.RPAREN3;
          return this.token;

        case ';':
          this.tokenValue = "" + value;
          this.token = Token.SEMICOLON;
          return this.token;

        case '?':
          this.tokenValue = "" + value;
          this.token = Token.QUESTIONMARK;
          return this.token;

        case 'C':
          this.tokenValue = "" + value;
          this.token = Token.COMPLEMENT;
          return this.token;

        case 'u': case 'v':
          this.tokenValue = "" + value;
          this.token = Token.UNION;
          return this.token;

        case 'n':
          this.back(1);
          // Regel des längsten Musters: "n" könnte ja noch zu "not" werden.
          if (this.testString("not")) {
            this.tokenValue = this.getString(3); // "not"
            this.token = Token.NOT;
          } else {
            this.tokenValue = this.getString(1); // "n"
            this.token = Token.INTERSECTION;
          }
          return this.token;

        case '\\':
          this.token = Token.DIFFERENCE;
          return this.token;

        case 'I':
          this.back(1);
          if (this.testString("Is")) {
            this.tokenValue = this.getString(2); // "Is"
            this.token = Token.IS;
          } else {
            this.tokenValue = this.getString(1); // "I"
            this.token = Token.UNKNOWN;
          }
          return this.token;

        case 'i':
          this.back(1);
          // Regel des längsten Musters: "in" könnte ja noch zu "inf" werden.
          if (this.testString("inf")) {
            this.tokenValue = this.getString(3); // "inf"
            this.token = Token.INFINITY;
          } else if (this.testString("in")) {
            this.tokenValue = this.getString(2); // "in"
            this.token = Token.IN;
          } else {
            this.tokenValue = this.getString(1); // "i"
            this.token = Token.UNKNOWN;
          }
          return this.token;

        case '+': case '-':
        case '.':
        case '0': case '1': case '2': case '3': case '4':
        case '5': case '6': case '7': case '8': case '9':
          this.back(1);
          if (this.testString("+")) {
            this.tokenValue += this.getString(1);
            this.token = Token.PLUS;
          } else if (this.testString("-")) {
            this.tokenValue += this.getString(1);
            this.token = Token.MINUS;
          }
          // Regel des längsten Musters:
          // "+" könnte ja noch zu einer Zahl, die mit "+" beginnt, werden.
          // Das Selbe gilt auch für "-".
          while (this.hasChar()) {
            char digit = this.getChar();
            if ("0123456789".indexOf(digit) >= 0) {
              this.tokenValue += digit;
              this.token = Token.NUMBER;
            } else {
              this.back(1);
              break;
            }
          }
          if (this.testString(".")) {
            this.tokenValue += this.getString(1);
            this.token = Token.UNKNOWN;
            while (this.hasChar()) {
              char digit = this.getChar();
              if ("0123456789".indexOf(digit) >= 0) {
                this.tokenValue += digit;
                this.token = Token.NUMBER;
              } else {
                this.back(1);
                break;
              }
            }
          }
          return this.token;

        default:
          this.tokenValue = "" + value;
          this.token = Token.UNKNOWN;
          return this.token;
      }
    }

    this.tokenValue = "";
    this.token = Token.EOS;
    return this.token;
  }
}
⇑ Der Setty-Scanner mit Java ⇑
Scanner-Generator
Wie Sie sehen, ist die händische Implementierung eines Scanners sehr umfangreich. Fehler kann man bei dieser Vorgehensweise quasi nie ausschließen, deshalb sei zur Entwicklung eines Scanners die Verwendung eines Scannergenerators (JLex oder JFlex) als weitaus sicherere Variante erwähnt.

Sie definieren die Tokenmenge in der Regel mit regulären Ausdrücken, damit der Scannergenerator eine Scannerklasse (hier: eine Java-Klasse) automatisch generieren kann, d. h. die Scannerklasse müssen Sie somit nicht selbst schreiben, weil dies der Scannergenerator für Sie erledigt.
Test Der Setty-Scanner wird getestet
Arbeitsweise des Scanners
Folgende Testklasse zeigt die einfache Handhabung des Setty-Scanners.
Der Setty-Scanner wird getestet
public class TestScanner {

  public static void main(String[] arguments) {

    String testSource = "Is 4711 not in C(]-inf;+inf[)?";

    if (arguments.length > 0) {
      testSource = arguments[0];
    }

    System.out.println("Source: '" + testSource + "'");
    System.out.println("");

    Scanner scanner = new Scanner(testSource);

    do {
      scanner.nextToken();

      switch (scanner.getToken()) {
        case Token.UNKNOWN:      System.out.print("     UNKNOWN"); break;
        case Token.EOS:          System.out.print("         EOS"); break;
        case Token.LPAREN1:      System.out.print("     LPAREN1"); break;
        case Token.RPAREN1:      System.out.print("     RPAREN1"); break;
        case Token.LPAREN2:      System.out.print("     LPAREN2"); break;
        case Token.RPAREN2:      System.out.print("     RPAREN2"); break;
        case Token.LPAREN3:      System.out.print("     LPAREN3"); break;
        case Token.RPAREN3:      System.out.print("     RPAREN3"); break;
        case Token.PLUS:         System.out.print("        PLUS"); break;
        case Token.MINUS:        System.out.print("       MINUS"); break;
        case Token.SEMICOLON:    System.out.print("   SEMICOLON"); break;
        case Token.QUESTIONMARK: System.out.print("QUESTIONMARK"); break;
        case Token.COMPLEMENT:   System.out.print("  COMPLEMENT"); break;
        case Token.UNION:        System.out.print("       UNION"); break;
        case Token.INTERSECTION: System.out.print("INTERSECTION"); break;
        case Token.DIFFERENCE:   System.out.print("  DIFFERENCE"); break;
        case Token.IS:           System.out.print("          IS"); break;
        case Token.IN:           System.out.print("          IN"); break;
        case Token.NOT:          System.out.print("         NOT"); break;
        case Token.NUMBER:       System.out.print("      NUMBER"); break;
        case Token.INFINITY:     System.out.print("    INFINITY"); break;
        default:                 System.out.print(" [undefined]");
      }

      System.out.println(": '" + scanner.getTokenValue() + "'");

    } while (scanner.getToken() != Token.EOS);

  }
}
⇑ Der Setty-Scanner wird getestet ⇑
java TestScanner "Is 4711 not in C(]-inf;+inf[)?"
Source: 'Is 4711 not in C(]-inf;+inf[)?'

          IS: 'Is'
      NUMBER: '4711'
         NOT: 'not'
          IN: 'in'
  COMPLEMENT: 'C'
     LPAREN1: '('
     RPAREN2: ']'
       MINUS: '-'
    INFINITY: 'inf'
   SEMICOLON: ';'
        PLUS: '+'
    INFINITY: 'inf'
     LPAREN2: '['
     RPAREN1: ')'
QUESTIONMARK: '?'
         EOS: ''
⇑ java TestScanner "Is 4711 not in C(]-inf;+inf[)?" ⇑
java TestScanner "Is +5.0 in {30.0;-1}?"
Source: 'Is +5.0 in {30.0;-1}?'

          IS: 'Is'
      NUMBER: '+5.0'
          IN: 'in'
     LPAREN3: '{'
      NUMBER: '30.0'
   SEMICOLON: ';'
      NUMBER: '-1'
     RPAREN3: '}'
QUESTIONMARK: '?'
         EOS: ''
⇑ java TestScanner "Is +5.0 in {30.0;-1}?" ⇑
Der Setty-Scanner erkennt aber auch Fehler, wenn die gegebene Zeichenkette ungültige Zeichenfolgen enthält.

Das Gute hierbei ist, dass der Scanner keine Exception wirft, was den Lesefluss unterbrechen würde, sondern das definierte Ausnahmetoken UNKNOWN zurückgibt. So kann trotz eines Fehlers im Quellprogramm einfach weitergelesen werden. Da dieser Scanner stets einen definierten Folgezustand besitzt, kann dieser Scanner auch als totaler Automat bezeichnet werden. Ohne dem Ausnahmetoken UNKNOWN wäre dieser Scanner nur ein partieller Automat, was nicht praktikabel wäre.

Genauer gesagt, handelt es sich beim vorliegenden Scanner um einen totalen, deterministischen, endlichen Automaten.
java TestScanner "Is dee 3 a drinn?"
Source: 'Is dee 3 a drinn?'

          IS: 'Is'
     UNKNOWN: 'd'
     UNKNOWN: 'e'
     UNKNOWN: 'e'
      NUMBER: '3'
     UNKNOWN: 'a'
     UNKNOWN: 'd'
     UNKNOWN: 'r'
          IN: 'in'
INTERSECTION: 'n'
QUESTIONMARK: '?'
         EOS: ''
⇑ java TestScanner "Is dee 3 a drinn?" ⇑
Im Folgenden kommen ausnahmslos gültige Tokens vor, jedoch mit falscher Grammatik — kein Problem für den Setty-Scanner. Der Parser allerdings würde schon beim ersten Token eine ParseException werfen, weil ein Setty-Programm nicht mit IN, sondern gemäß der Grammatik mit IS beginnt.
java TestScanner "innotnun?Is+-+0815.000Cu)}[-inf"
Source: 'innotnun?Is+-+0815.000Cu)}[-inf'

          IN: 'in'
         NOT: 'not'
INTERSECTION: 'n'
       UNION: 'u'
INTERSECTION: 'n'
QUESTIONMARK: '?'
          IS: 'Is'
        PLUS: '+'
       MINUS: '-'
      NUMBER: '+0815.000'
  COMPLEMENT: 'C'
       UNION: 'u'
     RPAREN1: ')'
     RPAREN3: '}'
     LPAREN2: '['
       MINUS: '-'
    INFINITY: 'inf'
         EOS: ''
⇑ java TestScanner "innotnun?Is+-+0815.000Cu)}[-inf" ⇑
Startseite   Sitemap   Downloads   Hilfe   Impressum  
Startseite < Informatik < Algorithmen Datenstrukturen / Software-Engineering / Programmiersprachen < Compiler Interpreter < Setty < Setty-Präprozessor [ DRUCK , 2004 , 2005 , 2006 , 2007 , 2008 , 2009 ] Setty-Scanner Setty-Parser > Tinyray > / Java C/C++ POV-Ray LaTeX > / Künstliche Intelligenz > Schach Privates / Inhalt >