Parser einer Grammatik

[jochen (Gast)]

Hallo zusammen, ich habe mal ein neues Thema eröffnet, das alte wird zu 
unübersichtlich.
Den ganzen morgen bin ich nun schon dabe, dein Fehler in dem folgenden 
Programm zu suchen. Ich weiß einfach nicht, was daran falsch ist.
Ich habe es versucht, ohne eine while Schleife zu lösen, die anfangs 
weiter geht, soland ein a vorliegt.

Grammatik:

B-> aB | a

 public class Parser {
      public char[] str; // zu parsende Zeichen
      public int pos; // aktuelle Position
      public Parser(String s) {
        str = s.toCharArray();
        pos = 0;
        // Aufruf mit Methode des Startsymbols
        if (B() && pos == str.length)
          System.out.println("Wort erkannt: " + s);
        else
          System.out.println("Wort nicht erkannt: " + s);
      }
    
       

  public boolean B() {
    if(str[pos]=='a'){
        pos++;
        if (B()==true) return true;
        else pos--;
    }
    if (str[pos]=='a'){          
          
        pos++;
        return true;
    }
      return false;
    }

Die Fehlermeldung ist

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 8
  at Parser.B(Parser.java:18)
  at Parser.B(Parser.java:20)
  at Parser.B(Parser.java:20)
  at Parser.B(Parser.java:20)
  at Parser.B(Parser.java:20)
  at Parser.B(Parser.java:20)
  at Parser.B(Parser.java:20)
  at Parser.B(Parser.java:20)
  at Parser.B(Parser.java:20)
  at Parser.<init>(Parser.java:9)
  at haupt.main(haupt.java:10)



Seht ihr, was ich falsch gemacht habe?

[jochen (Gast)]

Die Fehlermeldung kommt übrigens bei folgendem Aufruf:

public class haupt {

  /**
   * @param args
   */
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    String s = "aaaaaaaa";
      new Parser(s);
  }
}

[MartinH (Gast)]

--> java.lang.ArrayIndexOutOfBoundsException:

Offensichtlich wird dein pos > str.length!
Ich denke das ganze passiert beim rekursiven Aufruf von B():
Du musst überprüfen, ob dein Index pos nicht größer wird als 
str.length-1...

Bei dem Übergebenen Wort 'aaaaaaaa' wird pos ja durch den rekursiven 
Aufruf von B() achtmal hochgezählt und dadurch wird das Array 
verlassen...

Gruß

[jochen (Gast)]

Danke für deine Information.

Wieseo gerade str.length-1
wieso -1 ?

[MartinH (Gast)]

die Stringmethode length() gibt die Anzahl der Zeichen zurück.
Die Zählung im Stringarray beginnt aber bei 0.
Also ist das letzte Zeichen im String an str.length() - 1

String str = "Hallo";

str[0] ist 'H'
str[str.length()-1] ist 'o'
str[str.length]  ist "ArrayOutOfBoundsException" ;)

siehe auch z.b. http://wiki.zum.de/Java/String

[jochen (Gast)]

Martin, danke!

D.h. ich erhöhe pos unnötig und somit einmal zu viel.
Insgesamt wird es im Quelltext an 2 Stellen erhöht.
Meiner Meinung nach muss es an diesen Stellen aber auch erhöht werden, 
denn wenn ein Zeichen erkannt wurde, muss ja auf das nächste 
umgesprungen werden.

Siehst du einen klaren Fehler?

[MartinH (Gast)]

Probier mal:

  public boolean B() {
-->    if(pos  == str.length-1 ){
-->        if(str[pos] == 'a') return true;
-->        else return false;
-->    }

    if(str[pos]=='a'){
        pos++;
        if (B()==true) return true;
        else pos--;
    }
    if (str[pos]=='a'){

        pos++;
        return true;
    }
      return false;
    }

[jochen (Gast)]

wow, das funktioniert jetzt :)

Hab eine Frage zu dem Quelltext:

if(pos  == str.length-1 ){
-->        if(str[pos] == 'a') return true;
-->        else return false;
-->    }

Also wenn man an der letzten Stelle ist ( if(pos  == str.length-1 ))
dann wird überprüft ob die letzte Stelle ein a ist ? (if(str[pos] == 
'a'))
Wieso das? Die letzte Stelle muss doch kein a sein, sondern ein b ? Was 
meinst du mit dieser Zeile?

[MartinH (Gast)]

Im Konstruktor natürlich auch wieder str.length-1:

--> if (B() && pos == str.length-1)

Bei mir läufts so...

[MartinH (Gast)]

Oh ja äh... Bei den Grammatiken hab ich net so aufgepasst :)

Also wenn an der letzten Stellen ein b sein muss, dann musst halt auf 
'b' prüfen.

[jochen (Gast)]

also ich habe jetzt nur den Zusatz

if(pos  == str.length-1 ){

                return false;
       }

drin, und so funktioniert es. Also wird garnichts an der letzten Stelle 
geprüft.

Dann merk ich mir das mal so ^^
Danke.

Eine Frage hab ic noch und zwar wenn ich eine Grammatik bekomme, die ich 
nicht groß analysieren möchte

z.B.

A -> aB | b
B-> aC | A
C -> d | A

wie kann ich dann einen Parser, ohne groß die Grammatik umzuschreiben, 
programmieren?
Bei der gegebenen Grammatik geht das ja, wie ich hier gelernt habe, 
nicht ohnt weiteres, da der Parser wenn er z.B. auf a  stößt nicht weiß, 
ob nun A oder B das entsprechende terminale Symbol ist.

Oder wenn er auf A stößt, weiß er nicht, ob es von B oder C kommt.
Wie berücksichtigt man so etwas implizit?

[MartinH (Gast)]

Oh also da kann ich dir nicht wirklich weiterhelfen.
Wie gesagt, Grammatiken und Parser sind eigentlich nicht so mein 
Fachgebiet..

Aber wieso das Rad zweimal erfinden?
Google mal nach Java antlr !

Gruß.

[Karl H. (kbuchegg)]

jochen wrote:

> z.B.
>
> A -> aB | b
> B-> aC | A
> C -> d | A
>
> wie kann ich dann einen Parser, ohne groß die Grammatik umzuschreiben,
> programmieren?

Wenn es ein rekursiver Abstieg ist: Gar nicht.
Du musst die Grammatik umschreiben. Ist aber im Regelfall trivial.

[jochen (Gast)]

Danke für die Antworten.
Das macht mir noch Schwierigkeiten.
Trivial finde ich das schonmal garnicht :(
Wie geht man da denn vor, fängt man einfach mal an mehrere Wörter 
aufzubauen ,in der Hoffnung dann zu sehen, wie man das am besten 
programmeiert?
Oder gibt es da mehr oder weniger ein Schema?

z.B. bei

A -> aB | b
B-> aC | A
C -> d | A

also ich wüsste nicht was ich machen soll, wenn ich diese Aufgabe 
vorgelegt bekäme. Ich würd dann anfangen, ein paar Wörter mal von Hand 
zu bilden.

[Karl H. (kbuchegg)]

> wow, das funktioniert jetzt :)

Ist aber im Sinne eines Parser trotzdem falsch.
Du kannst

B-> aB | a

nicht so mir nichts dir nichts in eine Funktion verwandeln.
Die Regel hat 2 Alternativen, nämlich entweder ein B ist ein aB
oder ein B ist ein a alleine. Beide Fälle haben aber denselben
terminalen Anfang, nämlich a. Und damit muss die Grammatik
zuerst umgeformt werden:

B -> a [ B ]

[jochen (Gast)]

Wäre schön, wenn ihr mir dazu eure Gedanken sagen könntet, damit ich in 
diese Denkweise herein komme

[jochen (Gast)]

@
Autor: Karl heinz Buchegger (kbuchegg) (Moderator)
Datum: 17.03.2008 14:10

Danke Heinz, also ich dachte es gäbe 2 Möglichkeiten, einmal indem man 
das explizit und einmal implizit macht (letzter Beitrag von dir im 
vorherigen Post).

Dann geht es in diesem Fall wohl nur, in dem man die Grammatik 
"analysiert"
Das Bsp hatten wir ja dann schon.
Aber du meinst
a{a} und nicht a[a], oder?

[Karl H. (kbuchegg)]

jochen wrote:
>
> z.B. bei
>
> A -> aB | b
> B-> aC | A
> C -> d | A

Nach ein bischen Rumspielen mit der Grammatik komme ich
zu dem Schluss, dass diese Grammatik nicht eindeutig ist.
Das heist, es gibt verschiedene Ableitungen ausgehend vom
Startsymbol, so dass sich auf verschiedenen Wegen derselbe
Satz ergibt


A                ich wähle aB
aB               Für B wähle ich aC
aaC              Für C wähle ich A
aaA              Für A wähle ich b
aab


A               ich wähle aB
aB              Für B wähle ich A
aA              Für A wähle ich aB
aaB             Für B wähle ich A
aaA             Für A wähle ich b
aab

-> der Satz aab kann auf 2 verschiedenen Wegen geparst werden.

[jochen (Gast)]

P.S.

woher weiß man denn wenn man eine Grammatik z.B.
B-> aB | a
umschreiben muss in
B -> a [ B ]

und wann man direkt mit dem Programmieren beginnen kann.

Ich dachte |  wird zu einem else if Zweig und fertig ?

[jochen (Gast)]

folgende Fälle sind zu beachten:

- keine 2 Regeln für ein nicht Terminal Symbol
- der rechte Teil Der Produktion darf nur bei einem Nicht Terminalsymbol 
sein
(z.B. A-> As und B -> s ) geht nicht, weil das s doppelt vorkommt
- Innerhalb einer Produktion darf ein nicht terminales Symbol nur bei 
einer Alternative vorkommen
(wie im letzten Fall, a kommt zweimal vor, einmal bei aA und bei a)

Trifft eine dieser Regeln nicht zu, muss umgeschrieben werden ??
Kann man das so sagen?

[jochen (Gast)]

Trifft keiner der Fälle zu, kann man gemäß


"Ich hoffe man kann sehen, wie die Grammatikregel sich praktisch
von alleine in Code umwandelt.
Steht in der Grammatik ein terminales Symbol, dann wird verglichen
ob es tatsächlich vorliegt. Wenn nein -> Fehler, return false
Liegt es vor, dann nächstes Symbol und weiter gehts.
Steht in der Grammatik ein nicht terminiales Symbol, dann wird
die Funktion gleichen Namens aufgerufen, die true oder false
zurückliefert. Liefert sie false, dann wird ebenfalls mit false
ausgestiegen. Liefert sie true, dann gehts weiter.

Das | in der Grammatik übersetzt sich zu einem if - else if - else"

einfach beginnen, "ohne groß nachzudenken " ???

[Karl H. (kbuchegg)]

jochen wrote:
> P.S.
>
> woher weiß man denn wenn man eine Grammatik z.B.
> B-> aB | a
> umschreiben muss in
> B -> a [ B ]
>

Ich glaub das hab ich jetzt schon mindestens 5 mal in den
letzten 3 Wochen geschrieben :-)

Wenn die terminalen Anfänge der einzelnen Varianten gleich sind,
dann muss man die Grammatik umschreiben, damit sie mit einem
Zeichen Vorausschau (genau das machst du ja, du betrachtest immer
nur das nächste Zeichen) parsbar ist.

B -> aB | a

Die Regel besteht aus 2 möglichen Wegen. Entweder ein B wird
als aB geparst oder es wirdf als a geparst. Die terminalen
Anfänge von aB und a sind aber gleich, nämlich a. Ergo muss
man sie umschreiben. In dem Fall geht das besonders einfach,
weil man das a sozusagen wie in der Mathematik herausheben
kann:

  B ->  a ( B | nichts )

(Für nichts verwendet man auch den Begriff 'epsilon' )
B | nichts     ist aber gleichbedeutend mit  [ B ]

Wenn eine Regel mehrere Alternativen hat, dann muss man sich den
terminalen Anfang jeder Alternative ansehen.

C ->  ab | Ba | cd | ag
B ->  ah

Die Regel für C hat 4 Möglichkeiten. Ein C kann sein:
ein ab oder ein Ba oder ein cd oder ein ag.
Was sind die jeweiligen terminalen Anfänge (also das jeweils erste
terminale Symbol)

ab  :  a
Ba  :  die terminalen Anfänge dieser Alternative sind gleich den
       terminalen Anfängen von B. Welche sind das? Das ist a, weil
       ein B ja nur ein ah sein kann
cd  :  c
ag  :  a

Die einzige Überschneidung der terminalen Anfänge besteht im Symbol a
Sowohl ab als auch Ba als auch ag beginnen mit a, also versuche ich
die mal zusammenzufassen. Dazu muss ich aber zuerst mal B einsetzen,
damit in weiterer Folge a ausgeklammert werden kann:

C ->  ab | ah | cd | ag

C -> ( a ( b | h | g ) ) | cd

(Das Ganze ist fast wie Formelumformen in der Mathematik)

Und das kann jetzt programmiert werden. Entweder das nächste Symbol
ist ein a oder ein c. Wenn es ein a ist, dann muss es mit entweder
b oder h oder g weitergehen. Oder aber es war kein a, dann muss es
ein c sein und es muss mit d weitergehen

Also mal das erste Kriterium in Code giessen: Entweder es ist
ein a oder ein c

   if( buff[pos] == 'a' ) {
     pos++;
     ...
   }
   else if( buff[pos] == 'c' )
     pos++;
     ...
   }

   return false;

Beachte: Wann immer ein terminales Symbol erkannt wird (das if
also mit wahr bewertet wird), dann erfolgt als nächste Aktion
sofort das Erhöhen von pos (das Bereitstellen des nächsten Zeichens)

Wenn es ein c war, dann muss als nächstes ein d kommen

   if( buff[pos] == 'a' ) {
     pos++;
     ...
   }
   else if( buff[pos] == 'c' )
     pos++;
     if( buff[pos] == 'd' ) {
       pos++;
       return true;
     }
     return false;
   }

   return false;

wenn es hingegen ein a war, dann gibt es wieder 3 Möglichkeiten:
es muss entweder ein b, ein h oder ein g folgen. Auch das
kodiere ich wieder runter.

   if( buff[pos] == 'a' ) {
     pos++;
     if( buff[pos] == 'b' ) {
       pos++;
       return true;
     }
     else if( buff[pos] == 'h' ) {
       pos++;
       return true;
     }
     else if( buff[pos] == 'g' ) {
       pos++;
       return true;
     }
     return false;
   }
   else if( buff[pos] == 'c' )
     pos++;
     if( buff[pos] == 'd' ) {
       pos++;
       return true;
     }
     return false;
   }

   return false;

und erst jetzt schau ich mir an, ob es irgendwelche offensichtlichen
Optimierungen gibt.

[jochen (Gast)]

Der lezte Beitrag war für mich sehr aufschlussreich, danke!

Eine Frage dazu habe ich:

"Die einzige Überschneidung der terminalen Anfänge besteht im Symbol a
Sowohl ab als auch Ba als auch ag beginnen mit a, also versuche ich
die mal zusammenzufassen. Dazu muss ich aber zuerst mal B einsetzen,
damit in weiterer Folge a ausgeklammert werden kann:

C ->  ab | ah | cd | ag"
------
Die Grammatik war

C ->  ab | Ba | cd | ag
B ->  ah

Wenn ich für das B den Wert ah einstze, ist es dann nicht

C ->  ab | aha | cd | ag

[Karl H. (kbuchegg)]

jochen wrote:

> Die Grammatik war
>
> C ->  ab | Ba | cd | ag
> B ->  ah
>
> Wenn ich für das B den Wert ah einstze, ist es dann nicht
>
> C ->  ab | aha | cd | ag

Mein Fehler. Du hast recht.

[jochen (Gast)]

OK, dann hat man eine if Abfrage mehr drin, und zzwar nach Erkennung von 
ah noch nach dem a schauen.

Die Umsetzung von B-> aB | a


dürfte dann der wie in einem vorherigen Beitrag

 public boolean B() {
    
     
      if( str[pos] != 'a' )
        return false;
      pos++;
      
      if( !B() ) {
        // A war nicht da. macht aber nichts A muss ja auch
        // nicht da sein
        ;
      }

      return true;
    }

 
}

ensprechen, oder?

[jochen (Gast)]

Nur das funktioniert nicht, da gibts dann wieder den Fehler


Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 3
  at Parser.B(Parser.java:19)
  at Parser.B(Parser.java:23)
  at Parser.B(Parser.java:23)
  at Parser.B(Parser.java:23)
  at Parser.<init>(Parser.java:8)
  at haupt.main(haupt.java:17)




Wenn ich die obige Lösung anwende, erkennt er die Wörter falsch

[Karl H. (kbuchegg)]

Was bisher immer ignoriert wurde, und sich in C fast von
selbst regelt, ist, dass du nach einem Erhöhen von
pos auch prüfen musst, ob dadurch nicht das Ende des Strings
erreicht wurde.

In C erübrigt sich diese Abfrage, da ein C-String immer mit
einem speziellen Zeichen endet, wodurch die ganzen weiteren
Zeichenvergleiche alle auf false evaluieren.

[jochen (Gast)]

ich werde es selbstständig versuchen.

Ich habe jetzt einen Satz von dir ganz in und auswendig gelernt:

2 Alternative Pfade in einer Regel können niemals den selben derminalen 
Anfang haben.
ODer von weiter oben: Wenn die terminalen Anfänge der einzelnen 
Varianten gleich sind,....

dann mussich umschreiben.
Also ganz sicher z.B. bei A->  a | ab | U   U-> a | A
dann muss ich schonmal das A nach dem Schema von Dir, was mir sehr viel 
bringt, umscheiben.

Gilt das jetzt nur innerhalb einer Produktion, oder muss man 
verschiedene Produktionen auch noch vergleichen?
Bsp.:
A-> aCd
C-> aCd | b

wir hatten das Bsp ja schon einmal, da haben wir das mit einer while 
Schleife gelöst, das hatte ich so  auch verstanden.

Nur kann man das jetzt auch direkt ohne groß mit while Schleifen zu 
überlegen, in einen Parser umsetzen (ohne umzuschreiben), oder muss man 
hier umschreiben, da  aCd sowohl bei A als auch bei C vorkommt. Der 
terminale Anfang innerhalb einer Produktion ist allerdings aber nie 
gleich.

[MartinH (Gast)]

>Was bisher immer ignoriert wurde, und sich in C fast von
>selbst regelt, ist, dass du nach einem Erhöhen von
>pos auch prüfen musst, ob dadurch nicht das Ende des Strings
>erreicht wurde.

Hab ich doch schon ganz am Anfang angemerkt ;)

[jochen (Gast)]

Also, die 2 Fragen sind mir noch offen, einmal die in meinem vorherigen 
Beitrag wegen dem umschreiben und dann, wie ich diese Überprüfung am 
geeignetsten mache. Dann hab ich es aber ein für alle mal verstanden!

Ich habe die besagte Überprüfung nun eingeführt, jetzt funktioniert das 
Programm an sich, jedoch nicht in seiner Funktion:

 public class Parser {
      public char[] str; // zu parsende Zeichen
      public int pos; // aktuelle Position
      public Parser(String s) {
        str = s.toCharArray();
        pos = 0;
        // Aufruf mit Methode des Startsymbols
        if (B() && pos == str.length)
          System.out.println("Wort erkannt: " + s);
        else
          System.out.println("Wort nicht erkannt: " + s);
      }
    
       

      public boolean B() {
        

        if( str[pos] != 'a' )
              return false;
            pos++;
            if(pos == str.length-1)
              return true;
            if( !B() ) {
               
              ;
            }

            return true;
          }
    }

Die Ausgabe lautet: Wort nicht erkannt: aaa

[Karl H. (kbuchegg)]

jochen wrote:
> geeignetsten mache. Dann hab ich es aber ein für alle mal verstanden!

Das sollte aber eigentlich schon klar sein, wenn man bedenkt,
warum man unterschiedliche terminale Anfänge haben muss:

Um innerhalb einer Regel entscheiden zu können, wie es in dieser
Regel weiter geht. Also braucht man nur innerhalb einer Regel
feststellen ob alle terminalen Anfänge, die in dieser Regel
vorkommen, verschieden sind.

>
> Ich habe die besagte Überprüfung nun eingeführt, jetzt funktioniert das
> Programm an sich, jedoch nicht in seiner Funktion:

Dann funktioniert es per Definition nicht.


>       public boolean B() {
>
>
>         if( str[pos] != 'a' )
>               return false;
>             pos++;
>             if(pos == str.length-1)
>               return true;

Das ist eine schlechte Wahl. Denn nachdem das letzte 'a'
erkannt wurde, kann und wird pos ja am Ende des Strings
sein.
Was gilt es denn abzutesten?
Es gilt abzuklären, ob es überhaupt ein nächstes Zeichen gibt
und wenn ja, ob dieses Zeichen ein 'a' ist. Wann gibt es kein
nächhstes Zeichen mehr? Wenn pos gleich str.length geworden
ist. Zur Sicherheit mach ich keinen Vergleich auf Gleichheit
sondern auf Größer/Gleich.

public boolean B() {

  if( pos >= str.length || str[pos] != 'a' )
    return false;

  pos++;

  if( !B() ) {
    ;
  }

  return true;
}


Jetzt hab ich mal eine Frage:
Wazu brauchst du das überhaupt? Deine Programmierkenntnise sind
so schwach, daß du mit formalen Sprachen und Compilerbau eigentlich
noch nicht anfangen solltest. Da gibt es noch wesentlich Wichtigeres,
das du lernen solltest.

[jochen (Gast)]

Dann könnte ich bei
A-> aCd
C-> aCd | b
also direkt loslegen ohne eine while Schleife, wie damals, zu benutzen. 
Richtig?


Ich brauche das für meine Klausur in 2 Wochen. Die Programmierkenntnisse 
(if, , Rekursion, for/while Schleifen, Klassen, Methoden) hab ich schon 
hoffe ich doch :)

Vielen, vielen Dank für deine Gedult und Hilsbereitschaft. Bin sehr froh 
darüber, andernfalls hätte ich das nie und nimmer verstanden!

[Karl H. (kbuchegg)]

jochen wrote:
>
> Ich brauche das für meine Klausur in 2 Wochen. Die Programmierkenntnisse
> (if, , Rekursion, for/while Schleifen, Klassen, Methoden) hab ich schon
> hoffe ich doch :)

Nicht wirklich.
Du findest die einfachsten Fehler nicht. Es scheint so, als
ob du dieses Semester keine einzige Übung selbst gemacht hättest
und jetzt mit Gewalt alles nachholen willst.
Und mit einem Debugger, der dir helfen würde, kannst du anscheinend
auch nicht umgehen.

[jochen (Gast)]

Mit einem Debugger kann ich auch nicht umgehen, ja... Das muss ich mir 
mal anschauen!
Ich habe vor der Vorlesung nicht programmiert und da ist es ziemlich 
schwer in kurzer Zeit einzusteigen, wenn man noch keine Erfahrung darin 
hat. Deswegen war es für mich äußerst schwer die Übungen selbst zu 
machen, weil die ja nochmal ein paar Stufen höher als das Klausurniveau 
liegen.

Aber jetzt wo ichs sehe ist mir das ganze  klar.

[jochen (Gast)]

Aber beschäftigt hab ich mich mit dem Stoff die ganze Zeit schon ;)

Dank dir nochmals, bin ja so froh !

[gast (Gast)]

Schon mal javaCC angeschaut.

[jochen (Gast)]

Ja habs mir grad eben angeschaut.
Eine Sache wollt ich noch sagen, ich habe mir jetzt ein paar Grammatiken 
erzeugt und den Parser dazu gschrieben, klappt ganz gut ;)

Nur mir ist aufgefallen, dass immer der letzte Buchstabe meiner 
Testzeichenkette Probleme macht. Manche Ketten werden fälschlicherweise 
als "Wort erkannt" eingestuft, obwohl sie falsch sind (falsch aufgrund 
des letzten Buchstabens der Kette).
Ich habe dann etwas rumexperimentiert und bin zu dem Entschluss 
gekommen, dass z.B. in dem Fall

A- > aA

wonach der Code  nach der mich rettenden Hilfestellung hier

 
if (str[pos]=='a'){
 pos++;
 if(A)
return true;
}
return false;

lautet

noch in

 
if (str[pos]=='a'){
 pos++;
 if(A)
return true;
else pos--;
}
return false;

umgeschrieben werden müsste.
Denn wenn bei aA das a erkannt, das A aber nicht erkannt wird, gibt es 
ja keinen Grund, pos zu erhöhen.
Also mit dieser Änderung fuktioniert alles von mir getestete wunderbar, 
ich denk mal dann muss das so sein
Wollt ihr noch ergänzt haben :)