Textsuche mit regulären Ausdrucken

[minzee]

Hi

http://wwwiti.cs.uni-magdeburg.de/iti_db/algoj/code/algoj/kap17/NEA.java

Mit dem String "AABA" funktioniert es, mit "XAABA" jedoch nicht.

Dieses Verhalten entspricht doch nicht der Suche mit regulären Ausdrucken, oder? Die sollen schließlich Texte nicht nur am Stringanfang, sondern an jeder beliebigen Stelle im String finden können.

P. S. falls der Compiler bei LinkedList eine Fehlermeldung liefert, dann:
LinkedList<Integer> deque = new LinkedList<Integer>();

 

[njans]

Deine "Fragestellung" ist wirr.
XAABA wird natürlich nicht zugelassen, da X kein Zustand ist. Also was genau ist die Frage oder das Problem?

 

[minzee]

OK, neue Frage

Wie muss states aussehen, damit das Programm wirklich wie ein regulärer Ausdruck funktioniert? Weil darum gehts doch, oder?

 

[njans]

Wie muss states aussehen, damit das Programm wirklich wie ein regulärer Ausdruck funktioniert?

Die Frage ist dann, welchen regulären Ausdruck willst du denn darstellen?
A*BBA*
ABBA
AB*BA
usw.
Es gibt unendlich viele reguläre Ausdrücke mit dem Alphabet (A,B).

Weil darum gehts doch, oder?

Warum fragst du mich das? Du hast die Aufgabe doch gestellt bekommen. Woher soll hier jemand wissen, "worum es hier geht", wenn du es nicht weißt?!

 

[minzee]

Welche Aufgabe?? :noe:

 

[Gucky]

Ich glaube, ihr redet stark aneinander vorbei.
minzee, kannst du noch einmal genau erklären, was dein Plan ist?

 

[minzee]

Das ist interessant. In dem Programm fehlt etwas. Hier das Programm, wie es eigentlich aussehen sollte:

import java.util.LinkedList;

public class nea  {
   public static final int SCAN = -1;
   
   // Klasse zur Repr�sentation der Zust�nde  
   static class State {
      public State(char s, int n1, int n2) {
         symbol = s; next1 = n1; next2 = n2;
      }
      char symbol; // zu akzeptierendes Symbol
      int next1, next2; // Nachfolgezust�nde
   }
   
   // "Programm" des NEA
   State[] states = {
         new State(' ', 1, 3), // 0
         new State('A', 2, 2), // 1
         new State(' ', 3, 1), // 2
         new State('B', 4, 4), // 3
         new State('A', 5, 5), // 4
         new State(' ', 0, 0)  // 5
   };
   
   public nea() {}
   
   public boolean match(String s) {
      
      // Initialisierung
      LinkedList<Integer> deque = new LinkedList<Integer>();
      int j = 0;
      int state = states[0].next1;
      if (states[0].next1 != states[0].next2) {        // Diese Zeilen
         deque.addFirst(new Integer(states[0].next2)); // habe ich nachträglich
      }                                                // eingefügt!
      deque.addLast(new Integer(SCAN));
      
      while (state != 0) {
         
         if (state == SCAN) {
            j++; 
            deque.addLast(new Integer(SCAN));
         }
         else if (states[state].symbol == ' ') {
            // "leeres" Zeichen -> Nullzustand
            int n1 = states[state].next1;
            int n2 = states[state].next2;
            deque.addFirst(new Integer(n1));
            if (n1 != n2) 
               deque.addFirst(new Integer(n2));
         }
         else if (states[state].symbol == s.charAt(j)) {
            // Zeichen akzeptiert 
            deque.addLast(new Integer(states[state].next1));
         }
            
         if (deque.isEmpty() || j > s.length()) {
            // kein Endzustand erreicht -> Fehler
            return false;
         }
         
         // (!) neuen Zustand einnehmen
         state = ((Integer) deque.removeFirst()).intValue();
      }
      // Endzustand: Eingabe akzeptieren
      return true;
   }
   
   public static void main(String[] args) {
      nea nea = new nea();
      System.out.println("accept = " + nea.match("AAB-BA"));
   }
}

Ich versuche herauszufinden, ob der Autor dieses Programms das wirklich so haben wollte, oder ob er einen Fehler gemacht hat.

Hier ein paar Beispiele zu Texten (String s) und Rückgabewerten:

1) "BA" => true
2) "AABA--" => true

3) "-BA" => false
4) "-AABA" => false
5) "AAB-BA" => false

1) ist klar, das muss natürlich true liefert.

2) ist schon interessanter. Betrachtet man das alles als einen typischen regulären Ausdruck, passt alles, muss es natürlich auch true liefern. Bei regulären Ausdrucken darf es schließlich keine Rolle spielen, ob nach dem AABA noch irgendwelche zusätzlichen Zeichen kommen.

Würde man einer RegExp den String von 3), 4) oder 5) übergeben, würde sie true liefern. Nicht jedoch dieses Programm.

Dieses Programm zeigt also definitiv nicht das Verhalten, das man von RegExp-Maschinen gewohnt ist.

Es führt auch keine Wort-Kontrolle durch. Denn dann müsste 2) false liefern.

Statt dessen haben wir einen Automaten, der kontrolliert, ob der Stringanfang(!) einem regulären Ausdruck entspricht. Und das finde ich etwas verwunderlich. Denn solche Funktionen bieten Programmiersprachen nicht an. Darum frage ich mich, ob bei diesem Programm irgendwas schiefgelaufen ist. Ist das eine verunglückte RegExp-Maschine, oder ist das ein verunglückter Wort-Checker?