Java .StackOverflowError

endlos Rekursion oder endlos Schleife.
wenn du mit eclipse programmierst, dann könntest du die debug funktion 
nutzen, sonst kannst du einfach ein paar System.out.println("stelle 
xyz");
einfügen, um schnell zu lokalisieren wo der Fehler auftritt.

Der Debugger findet keinen Fehler also markiert keine Stelle, die falsch 
ist. (wenn ich F11 drücke und dann auf "Play" gehe)System.out.println 
habe ich an manchen Stellen eingefügt, aber der Fehler kommt weiterhin.

Beim Compilieren wird gesagt die Zeile  if (!A()){ ist falsch.
Korrigiert wird abr leider nichts.


Die EBNF Regel a[A] lautet ja (funktioniert):

1

public boolean A(){         

2

         if( pos >= str.length )

3

              return false;           

4

5

6

        }

7

          if (str[pos]=='a'){

8

                                     pos++;

9

                                     if (!A()){

10

            return true;

11

         }

12

13

         return false;

14

         }

15

 }

16

17

Dementsprechend sollte  [A]a doch so sein (hier tritt der Fehler auf):

1

public boolean A(){         

2

         if( pos >= str.length )

3

              return false;           

4

         if (!A()){

5

6

        }

7

          if (str[pos]=='b'){

8

           pos++;

9

           return true;

10

         }

11

12

         return false;

13

         }

14

 }

kann der Debugger die Fehler finden und korrigieren, oder was ist das?

Ich komme mit der Bedienung von dem Debugger nicht zurecht.
Wie meinst du das, wenn es einmal false ist, bleibt es false?

Ja, das merk ich jetzt auch :(

Wie würdest du das am geschicktesten lösen?

Ich habe zwar eine Idee

1

public boolean A(){         

2

         if( pos >= str.length )

3

              return false;           

4

         pos++;

5

         if (!A()){pos--;

6

7

        }

8

          if (str[pos]=='a'){

9

           pos++;

10

           return true;

11

         }

12

13

         return false;

14

         }

15

 }

Nur dann gibts wenn ich eine richtige Zeichenfolge teste ein weiteres 
Problem.
Ausgehend von meinem ersten Post lässt sich das doch bestimmt ganz 
einfach korrigieren, nicht?

Also mein Ausgangsproblem war

A -> Aa | a
ich habe das dann, so ähnlich wie bei dem Bsp von gestern umgeformt

A -> (A | nichts)a
A -> [A]a

Ja, hier sind die terminalen Anfänge von A bzw. a ja jeweils a, nur ich 
weiß nicht, wie ich das ganze weiter ausklammern kann. A einsetzen 
bringt auch nichts, weil wenn ich es einsetze, hab ich es im nächsten 
Schritt ja wieder drin.

Komisch, irgendwie, hast wie macht man das hier

@Jochen

Habe leider gerade genug Zeit gehabt,
um den Thread (die Threads mittlerweile) zu verfolgen.

Mich würde mal interessieren, Jochen, an was für einer Schule
Du da gerade bist. Gymnasium, FH, oder was genau?
Was für ein Fach oder Studiengang ist das?


Es hilft Dir vielleicht, wenn Du Dir, mit dem kürzesten Satz beginnend,
die Sätze der Reihe nach aufschreibst. Dann wirst Du darauf kommen,
das Du eine solche Syntax schon einmal in dem anderen Thread hattest,
wenn auch die EBNF anders aussah.


Gruss

Oops

@ Karl-Heinz Buchegger

Sieht irgendwie doch nach einem Kurs: "Formale Sprachen" oder 
"Compilerbau" aus aber da passen die Grundkenntnisse irgendwie nicht.
Auch keine Ahnung von Links-Rechts-Rekursion und Look-Ahead oder EBNF 
als Algebra.
Aber es gibt sicher ne einfache Erklärung dafür, aber so langsam werde 
ich neugierig.

Gruss
Oops

@ Karl-Heinz Buchegger

Oops. Gewissensbisse würden hier meiner Meinung nach nicht passen.
Die Profs und Tutis sind ja auch nicht dämlich. Die merken schon, ob er 
denn in der Lage ist zu abstrahieren oder nur ein paar Lösungswege 
auswendig gelernt hat.

Allerdings hoffe ich auch, das er hier was daraus macht. Klar ist, das 
er noch Einiges nachzuholen hat. Wenn er die Übungen aus den Tutorien 
nochmal ganz stramm durchgeht, könnte er es vielleicht packen. Dann sind 
die Wochenenden allerdings gestrichen. Und in Zukunft dann die Übungen 
von Anfang an mitmachen. Und das Drachenbuch lesen!

Gruss
Oops

@ Karl-Heinz Buchegger

>> Und das Drachenbuch lesen!
>Ui. Das ist aber heavy :-)
Sozusagen der Mangoldt/Knopp des Compilerbaus. Nur enger gedruckt. Ha!
Aho war auch mehr für nach den Übungen gemeint :-)

Aber im Ernst. Wirth finde ich auch gut. Ist nur ein bischen kurz
der schmale Band. Jobst fand ich noch ganz nett.


Gruss
Oops

@OOps
Wieso ahst du "leider" genug Zeit gehabt ? Ist doch kein Grund "leider" 
zu   sagen ;) Bin an einer Uni und das Thema ist Klausurrelevant für die 
Vorlesung "praktische Informatik" im ersten Semester (Studiengang 
Elektrotechnik).

Ich habe in einem anderen Thread eine Folie gepostet (ganz zu Anfang), 
in der erklärt wurde, wie ein Parser funktioniert. Viel mehr haben wir 
in der Vorlesung / Übung nicht dazu gesagt. Vielleicht noch 1, 2 Folien 
dazu, das wars. Diese ganzen Spezialfälle die ich hier anspreche, kamen 
nie dran, können aber in der Klausur aber durchaus drankommen.

Mich würde blendend interessieren, welcher Grammatik aus einem 
vorherigen Post das entspricht, wärst du so freundlich und sagst mir 
das?
Sehe ich richtig, dass man nicht sofort los programmieren kann, weil der 
terminale Anfang hier nicht definiert ist, der aber definiert sein muss 
(um  festzustellen, dass innerhalb einer Produktion ein terminaler 
Anfang nicht doppelt vorkommt) ? Leider hat mich verwirrt, dass es hier 
2 grundsätzliche Lösungsansätze gibt (explizit, implizit / rekrsiv, mit 
Schleifen) und ich würde mich jetzt auf den mit reiner Rekursion 
beschränkten.

Danke!

PS
doch, doch ich war von Anfang an mit dem Stoff beschäftigt, nicht dass 
der falsche Eindruck entsteht, ich lerne jetzt 2 Wochen im Crashkurs. 
Nur, damit war ich beschäftigt, zu lernen was Schleifen sind, wie man 
einen Taschenrechner programmiert, sowas eben.
1 Semester Informatik im gesamten Studiengang kann ganz schön 
anstrengend sein!

@ Jochen

>Wieso hast du "leider" genug Zeit gehabt ?
Die Zeit hat nur ausgereicht um, mitzulesen und nicht um zu antworten.

>Bin an einer Uni und das Thema ist Klausurrelevant für die Vorlesung >"praktische 
Informatik" im ersten Semester (Studiengang Elektrotechnik).

Aha.

>Ich habe in einem anderen Thread eine Folie gepostet ... können aber in der 
>Klausur aber durchaus drankommen.
Und da gab es keine Literaturliste dazu? Kein Tutorium?

>Mich würde blendend interessieren, welcher Grammatik aus einem
>vorherigen Post das entspricht
Das kann ich mir vorstellen. :-) Hast Du die Sätze aufgeschrieben? Sei 
mir bitte nicht böse, aber es macht glaube ich keinen Sinn Dir das 
vorzusagen, falls das Ziel ein Verständnis sein soll. Vor allem ist 
Lösung trivial.

>Sehe ich richtig, dass man nicht sofort los programmieren kann, weil der
>terminale Anfang hier nicht definiert ist, der aber definiert sein muss
>(um  festzustellen, dass innerhalb einer Produktion ein terminaler
>Anfang nicht doppelt vorkommt) ?
Kann ich gerade nicht nachvollziehen. Welche Grammatik meinst Du?
A -> Aa | a
hat ja nur EIN Nicht-Terminal!

>...(explizit, implizit / rekrsiv...
Da stehe ich wohl gerade auf der Leitung. Habe ich was überlesen?
Was meinst Du mit "explizit"?


Der Terminus "Rekursiver Abstieg" ist hier ein wenig irreführend.
Er bezieht sich nämlich auf die Methode der Implementierung eines 
Parsers allgemein und nicht zwangsweise auf die konkrete Implementierung 
(also den letzendlichen Programmtext des Parsers). Die muss nämlich gar 
keine Rekursion enthalten auch wenn sie gemäß der Methode des 
"rekursiven Abstiegs" programmiert ist.
Die Methode sagt ja nur, das jedes Nicht-Terminal einem Funktionsaufruf 
entspricht. Wenn die Grammatik keine Rekursion enthält ist auch kein 
rekursiver Funktionsaufruf nötig. Allenfalls könnte man dem Gedanken 
nähertreten, das immer wieder der Teilschritt "Funktion für 
Nicht-Terminal implementieren/aufrufen" erfolgt; Rekursion sich hier 
also auf die Tatsache bezieht, das für eine verbleibenden Teilabschnitt 
der Grammatik die Methode wiederum angewendet wird.

Im übrigen ist es aus mehreren Gründen besser die Grammatik so 
umzuformulieren, das aus der Rekursion eine Iteration wird. Du siehst 
selbst das Rekursion im Programm nicht ganz simpel ist. ("Java 
.StackOverflowError") Das ist auch eine beliebte Übung. Du wirst sehen, 
das die in vielen Fällen Rekursion durch Iteration ersetzen kannst.

Gruss
Oops

Zum Thema  Iteration statt Rekursion (ich weiß nicht wie man hier 
zietiert):

Wir haben ausschließelich "Recursive Descent Parser" kennengelernt, ich 
denke mal, wenn die Aufgabenstellung lautet so einen Parser zu 
programmieren, dann muss ich mit reiner Rekursion arbeiten, oder?

Also ich dachte, es gibt 2 grundsätzliche Vorgehensweisen,  wie ich hier 
verstanden habe.  Ich erkläre das am besten an einem Beispiel:

Grammatik:
A -> aCd
C -> aCd | b

einmal kann man die Grammatik analysieren und dann den folgenden Code 
schreiben:

1

int acount = 0;

2

int bcount = 0;

3

public void A(){

4

while str[pos] =='a' {

5

pos ++

6

acount++;

7

}

8

9

if (C () ==true)

10

while str[pos] =='b' {

11

pos ++

12

bcount++;

13

 {if(acount == bcount)

14

  return true

15

 }

16

17

return false;

Oder aber, man wendet stur die Regeln an und schreibt:

A -> aCd
C -> aCd | b
[/c]
public boolean A(){
if( pos >= str.length )
return false;

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

public boolean C(){
 if (str[pos]=='b'){
 pos++
 return true;
 }

if (str[pos]=='a')
 pos++;
 if (C(){
  if (str[pos] =='d'){
  pos ++;
  return true;
 }
}
}
}
[/c]
Also wie erklärt wurde, bei einem terminalen Symbol schaut man ob es da 
ist, bei einem nicht terminalen Symbol ruft man die entsprechende 
Methode auf. Wenn alles okay ist return true.

Wenn ich das Bsp von oben

A -> Aa | a
ich habe das dann, so ähnlich wie bei dem Bsp von gestern umgeformt

A -> (A | nichts)a
A -> [A]a

analysieren würde, dann ist doch folgender Ansatz okay, oder:

1

public boolean A(){

2

if (str[pos] =='a'){

3

 while(str[pos]=='a'){

4

 pos ++;

5

 }

6

return true;

7

}

8

return false

9

}

stimmt doch, oder?
M.e. wäre das in Analogie zum obigen Beispiel in meinem Post von grad 
eben die Lösung, wenn man die Grammatik analysiert hat.
Gibt es noch eine Lösung, wo man das nicht brauch?

@Jochen

>(ich weiß nicht wie man hier zitiert):
Zitieren tut man mit dem mathematischen Grösser-Zeichen ">".

>Wir haben ausschließelich "Recursive Descent Parser" kennengelernt, ich
>denke mal, wenn die Aufgabenstellung lautet so einen Parser zu
>programmieren, dann muss ich mit reiner Rekursion arbeiten, oder?
Eben nicht. Schon deswegen nicht, weil nicht jede Grammatik eine 
Rekursion enthält. Siehe auch den langen Text am Ende von meinem Post 
von 20:12.
Mit welchem Kopfstand würdest Du eine Rekursion in A->a b C d e. C-> e|f 
reinbringen?

Die Methode heist "rekursiver Abstieg" und erzeugt eine 
Implementierung.
Die Implementierung kann, muss aber keine Rekursion enthalten. Dies 
hängt ausschliesslich von der Grammatik ab.

Es ist zwar üblich "Recursive Descent Parser" zu sagen, aber 
genaugenommen falsch. Es müsste heissen: "Ein durch die Methode des 
rekursiven Abstiegs erzeugter Parser".

>Also ich dachte, es gibt 2 grundsätzliche Vorgehensweisen,  wie ich hier
>verstanden habe.  Ich erkläre das am besten an einem Beispiel:
Das müssen wir nochmal genauer besprechen.
Du scheinst anzunehmen es gäbe einen Unterschied in der Vorgehensweise 
bzw. im Ergebnis wenn man die Grammatik analysiert und wenn man sie 
nicht analysiert.
>einmal kann man die Grammatik analysieren und dann den folgenden Code
schreiben:
und
>Oder aber, man wendet stur die Regeln an und schreibt:
bzw.
>M.e. wäre das in Analogie zum obigen Beispiel in meinem Post von grad
>eben die Lösung, wenn man die Grammatik analysiert hat.

Dieser Gedanke ist abwegig. (Wie kommst Du darauf?). Analyse einer 
Grammatik macht hier nur Sinn um herauszufinden ob eine Grammatik etwa 
rekursiv oder nicht-rekursiv ist, welchen Look-Ahead sie benötigt oder 
welche ersten terminalen Symbole die Alternativen haben. Sonst keinen!

Deine Beispiele von 20:28 implementieren nicht beide einen Parser für 
die Grammatik:

A -> aCd
C -> aCd | b

Der erste Parser implementiert vielmehr einen Parser für:

A -> a{a}Cd{d}
C -> aCd | b

wobei die Funktion C nicht angegeben ist.
Wenn das der Kernpunkt Deiner Beispiele ist, dann ist die Antwort nein.
Mal abgesehen davon, das es keinen Sinn macht eine Grammatik zu 
implementieren ohne sie zu analysieren, muss, egal ob man analysiert 
oder nicht immer zwei Parser herauskommen, die die Menge derselben Sätze 
als richtig und die komplementäre Menge als falsch beurteilt.

Bei deinem nachfolgenden Post von 20:33 scheint es so zu sein,
das Du meinem Tip gefolgt bist. Allerdings hast Du die Sätze nicht 
hingeschrieben und ich hätte mit an Sicherheit grenzender 
Wahrscheinlichkeit ein "Ahaaaa" erwartet.

Dein Code jedenfalls könnte bedeuten, das Du den Knackpunkt verstanden 
hast. Das hat aber nicht mit analysieren oder nicht analysieren zu tun.

Schreibe mal die Sätze von:

A -> Aa | a

auf.

Gruss
Oops

Oops

Ich habe was falsch gelesen. Sorry.

Beide Beispiele von 20:28 implementieren die selbe Grammatik.
Wobei aber nach wie vor im ersten der Code für C fehlt.

WIe auch immer. Das hat nichts mit analysieren oder nicht analysieren zu 
tun.

Gruss
Oops

Das war doch mal ein Beispiel aus einem alten Thread,
wo es darum ging, ob und wie man feststellen kann ob zwei Gruppen von 
Terminalen in gleicher Anzahl vorkommen.
Oder ob es über die Formulierung der Grammatik geht oder ob man in 
Variablen zählen und sie vergleichen muss.

Was hat das mit analsysieren zu tun?

Gruss
Oops

>Das müssen wir nochmal genauer besprechen.
>Du scheinst anzunehmen es gäbe einen Unterschied in der Vorgehensweise
>bzw. im Ergebnis wenn man die Grammatik analysiert und wenn man sie
>nicht analysiert.

Ja. Alles mein Eigenschluss nach den ganzen Lehveranstaltungen hier im 
Forum ;)
z.B. bei
A -> aA | b

wäre mit der Analyste die Lösung

1

while(str[pos] == 'a'){

2

 pos++;

3

}

4

if (str[pos] == 'b') {

5

pos++;

6

return true;

7

}

8

return false;

Hat man keine Ahnung wie die Grammatik aussieht,  stellt man fest, dass 
in der Produktion ein terminaler Anfang nicht zweimal auftaucht. Man 
kann also mit dem Niederschreiben beginnen:

1

public boolean A(){

2

if (str[pos] == 'a'){

3

 pos ++;

4

 if ( A() ) return true;

5

}

6

if (str[pos] =='b') {

7

pos ++;

8

return true;

9

}

10

return false;

11

}

Ich dachte in dem Beispiel, das ich einführend zu diesem  Thema hier 
gebracht habe gäbe es auch 2 solcher Möglichkeiten.
Dann scheint es im Fall
A -> [A]a  oder A -> [A]b  usw nur eine Lösung,
im fall

A -> a[A] , A -> b[A] aber zwei Lösungen (die beiden von diesem Post 
hier) zu geben. Ist das soweit korrekt?


>Schreibe mal die Sätze von:

>A -> Aa | a

>auf.

>Gruss
>Oops

Das ist doch a{a}

während

A -> a[A] gleichbedeutend mit {a} ist, oder?

Das ist doch a{a}

während

A -> a[A] gleichbedeutend mit {a}a ist, oder?

@Jochen
Oh. Da muss was elementares schiefgegangen sein.
Klären wir das mal Stück für Stück.

>Ja. Alles mein Eigenschluss nach den ganzen Lehveranstaltungen hier im Forum
OK. Wäre halt wichtig zu wissen, wie, d.h. durch welche Aussage Du 
darauf gekommen bist.

Zuerst:
>Hat man keine Ahnung wie die Grammatik aussieht...
Wie meinst Du das? Wie soll man denn keine Ahnung haben wie die 
Grammatik aussieht? Nenne ein Beispiel.

Gruss
Oops

@Jochen
Ich glaube, ich ahne da was.

Hat das damit zu tun, das Du bei
A -> Aa | a.

nicht weisst, wievielmal das A rekursiv aufgerufen wird?

Gruss
Oops

Freundlich von dir!

Die Aussage von Heinz

>Der Unterschied zwischen den beiden Lösungen ist ganz einfach der:
>In der ersten Lösung ergibt sich das Verhalten, daß immer gleich
>viele 'a' wie 'b' enthalten sein müssen, implizit. Es ist quasi
>ein Nebenprodukt. In der zweiten Lösung hat sich jemand zurückgelehnt
>und die Grammatik analysiert und festgestellt, daß das so sein muß
>und hat dieses Wissen explizit hineinkodiert.

in Beitrag "Parser für Grammatiken"

und auch die Tatsache, dass es (siehe mein Post hier um 21:21, die 
beiden Code Stücke sind doch gleichwertig?) 2 Lösungen für das Problem 
gibt, eine die man sich clever überlegen muss und deine, die man direkt 
hinschreiben kann.

>> Wie meinst du das?  Wie soll man denn keine Ahnung haben ....

Naja aussieht, okay. Die Grammatik ist ja gegeben. Aber man muss ja 
nicht unbedingt einen Plan haben, welche Wörter durch die Grammatik 
erzeugt werden, bzw. welchen Sinn die Grammatik hat. Das findet man ja 
oftmals nur durch das Aufschreiben und herumexperimentieren raus, mich 
leider eher später als früher.


Aber das mit den 2 Lösungn,  ist doch soweit richtig, oder kannst du mir 
mein Missverständnis erklären ? Ich habe ja um 21:21 hier 2 Codestücke 
geschrieben, das sollte doch ein und die selbe Grammatik in beiden Code 
Stücken sein, oder?

Davon unabhängig, das generelle Vorgehen ist doch:
Schauen, dass in eine Produktion keine terminalen Anfänge gleich sind. 
Falls doch, ausklammern und dann hat man das entsprechend umgeformt.
Taucht man bei der Umformung auf den Ausdruck (A | nichts) a bzw. [A]a 
hilft nur eine while Schleife, um diesen Ausdruck zu realisieren.

@Jochen

Ahaaaa. ;-)

>Der Unterschied zwischen den beiden Lösungen ist ganz einfach der:
>In der ersten Lösung ergibt sich das Verhalten, daß immer gleich
>viele 'a' wie 'b' enthalten sein müssen, implizit. Es ist quasi
>ein Nebenprodukt. In der zweiten Lösung hat sich jemand zurückgelehnt
>und die Grammatik analysiert und festgestellt, daß das so sein muß
>und hat dieses Wissen explizit hineinkodiert.

Da ist wirklich was schiefgegangen. Jetzt sehe ich auch das Wort 
"implizit".

Zunächst einmal rufe Dir bitte den Kontext der Frage ins Gedächtnis. Es 
ging um Deine Fragestellung welcher der beiden Wege (der von mir mit den 
Zählern für as und bs oder der von Karl-Heinz, der "richtige" wäre.

Daraufhin hat Dir Karl-Heinz erklärt, das es keinen "richtigen" Weg 
gibt,
sondern das es wichtig ist, das die "Lösungen" der Aufgabe korrekt 
funktionieren. (Es gibt noch weitere Aspekte, aber auf die kommt es hier 
nicht an). Es ist völlig egal wie die Lösungen das machen. Wenn Du ein 
Eichhörnchen zum Parser erziehen kannst ist das eine korrekte Lösung.

Dann hat er Dir erklärt was der Unterschied der beiden Lösungen ist.

Hier hat er, ganz sicher unabsichtlich, eine Analyse nur bei der zweiten 
Lösung unterstellt. Das ist aber so nicht ganz richtig. Denn die 
Umsetzung der Grammatik erfordert immer eine systematische 
Untersuchung der Grammatik. Das ist eben eine Analyse. Und auch die 
erste Lösung erfordert eine "Analyse". Es kann also keinen Parser (egal 
welchen) ohne Analyse der Grammatik (egal welche) geben. Demzufolge kann 
es auch keinen Unterschied zwischen Parsern die mit Analyse und solchen 
die ohne Analyse erstellt worden sind. Die Unterscheidung macht gar 
keinen Sinn!

Der zweite Unterschied bezieht sich auf "implizit" und "explizit". Die 
Bedeutung beider Worte ist Dir sicherlich bekannt. Ich möchte daher nur 
auf die Verwendung in diesem Kontext eingehen.

Die Grammatik (aus Deinem Post 
Beitrag "Re: Parser für Grammatiken" )

> A -> aCd
> C -> aCd | b

hat die Eigenschaft, das die Anzahl der a gleich der Anzahl der d sein 
muss, damit die Sätze korrekt sind. Die Eigenschaft der Anzahl von 
Terminalen und ihrer Gleichheit ist nirgendwo ausdrücklich genannt. Es 
gibt ja auch keine sprachlichen Mittel für solche Ausdrücke in (dieser 
Form) der EBNF. Vielmehr ergibt sie sich implizit aus der Beschreibung. 
Wenn man nach der Methode des rekursiven Abstiegs einen Parser für diese 
Grammatik konstruiert, dann wird sich ein Programm ergeben. Auch in 
diesem Programm wird dann nirgends die Anzahl der Terminale oder deren 
Gleichheit genannt.

Meine Lösung hat sich unmittelbar aus Deinem Post 
Beitrag "Re: Parser für Grammatiken" mit der Grammatik

A -> aCd
C -> b

ergeben. Ich habe keine neue Grammatik beschrieben, sondern direkt den 
Programmcode des Parsers. Für den beschriebenen Parser hätte die 
Grammatik um den Zusatz "Die Anzahl der a muss gleich der Anzahl der d 
sein" ergänzt werden müssen. Genaugenommen ist dies in EBNF nicht 
möglich denn sie enthält keine natürlichsprachlichen Sätze. (Es gibt da 
inzwischen ein Änderung, aber das ist hier nicht relevant).

Aber in meinem Code tauchen die Anzahl der Terminale und ihre Gleichheit 
ausdrücklich in Ausdrücken der Sprache C auf. Deswegen das "explizit".

Die Begriffe "explizit" und "implizit" beziehen sich hier nicht auf eine 
Vorgehensweise bei der Analyse. Sondern vielmehr darauf, ob eine 
Eigenschaft der Grammatik im Programmtext des Parsers ausdrücklich 
genannt wird oder nicht.

>Leider hat mich verwirrt, dass es hier 2 grundsätzliche Lösungsansätze >gibt 
(explizit, implizit / rekursiv, mit Schleifen) und ich würde mich >jetzt auf den 
mit reiner Rekursion beschränkten.

Der Lösungsansatz heisst "Rekursiver Abstieg". Die Grammatik selbst 
schreibt Dir vor ob im Programmtext Rekursionen vorkommen oder nicht. Da 
hast Du keine Wahl.

Allerdings, und das betrifft einen Teil der Rückfragen von Karl-Heinz 
und mir, gibt es mehrer Wege, ein und diesselbe Grammatik 
niederzuschreiben.

Ist das soweit klar?

Gruss
Oops

Oops, vielen Dank für deine ausführliche Klarstellung ;)
Ich bin jetzt sehr müde,  und habe schon Kopfschmerzen.
Dann habe ich noch einen Link entdeckt, den ich mir morgen genau ansehe:
http://www.inf.fu-berlin.de/lehre/WS04/uebersetzerbau/beispiele/Linksrekursion.pdf

Ich  schreibe morgen nochmal meinen Fortschritt / Fragen, wenn du magst 
kannst du ja nochmal vorbeischauen :-)
Danke, Oops, du / ihr helft mir echt wahnsinnig !

Also ich schreibe mal schon weiter.

>und auch die Tatsache, dass es (siehe mein Post hier um 21:21, die beiden >Code 
Stücke sind doch gleichwertig?) 2 Lösungen für das Problem
>gibt, eine die man sich clever überlegen muss und deine, die man direkt
>hinschreiben kann.

Das ist eben der Irrtum, den ich in meinem Post vorher hoffentlich jetzt 
aufgeklärt habe. Die Methode des "rekursiven Abstiegs" schreibt Dir 
genau vor, wie Du vorgehst und jeder wird auf das selbe Ergebnis kommen.
(Leider ist das nicht vollständig, aber diese Sachen sind hier nicht 
relevant).

Wenn Du Deinen Code von 21:21 wieder rückwärts in eine Grammatik 
übersetzt wirst Du feststellen, das der Code

1

public boolean A(){

2

   while(str[pos] == 'a') {

3

      pos++;

4

   }

5

   if (str[pos] == 'b') {

6

      pos++;

7

      return true;

8

   }

9

   return false;

10

}

Sätze der Grammatik A-> {a} b erkennt.
während der Code

1

public boolean A() {

2

   if (str[pos] == 'a'){

3

      pos ++;

4

      if ( A() ) 

5

         return true;

6

   }

7

   if (str[pos] =='b') {

8

      pos ++;

9

      return true;

10

   }

11

   return false;

12

}

Sätze der Grammatik A->aA|b erkennt.

Beide Sprachen sind verschieden.

Die erste umfasst die Sätze: b, ab, aab, aaab, und weitere beliebige 
Folgen von a gefolgt von b.
Die zweite umfasst die Sätze ab, aab, und weitere beliebige Folgen von a 
gefolgt von b.
Der Satz b aber ist in der zweiten Grammatik nicht enthalten.

Ist das soweit klar?

Gruss
Oops

@ Jochen

Ja, gut. Ich schreib schon mal weiter. Gute Besserung.

Gruss
Oops

@ Jochen

Also gut, weiter gehts.

Wenn ich mir Deine Beispiele für Code der aus einer "analysiertem" 
Grammatik entstanden ist, und solchem, bei dem Du stur dem Verfahren 
gefolgt bist, dann fällt mir folgendes auf.

1. Cleverer Code enthält while-Schleifen.
2. Dummer Code enthält Funktionsaufrufe.


Teilweise haben wir das ja jetzt oben schon geklärt.

Es gibt immer eine Code-Entsprechung zwischen dem EBNF-Sprachelement und 
einem Teil des Parsers.
Das hast Du ja auch soweit gut erfasst. Du setzt while-Schleifen ein und 
ifs usw. Alles OK.

Aber ob Du eine while-Schleife oder ein if einsetzt ist von der 
Grammatik vorgegeben. Da hast Du keine Wahl. Du bist auch nicht 
gefordert hier clever zu sein. Nicht an dieser Stelle. Sondern 
woanders, bei der Grammatik selbst.

Die Methode sagt: Ein if bzw. while usw. für jedes terminale Zeichen. 
Ein Funktionsaufruf für jedes Nicht-Terminale.
So geht das. Nicht anders.

Du fragtest z.B. um 21:21
>A -> a[A] ... aber zwei Lösungen
Ganz klar: _Nein!_ Aus der Methode des rekursiven Abstiegs ergibt sich 
(im Rahmen der momentanen Fragestellung) genau eine Lösung.

Ist das klar soweit?

OK. Und um Deine Frage nach den Umformungen zu beantworten:
>A -> Aa | a            Das ist doch a{a}
Stimmt. Aber nicht ausschliesslich. Es gibt noch andere Ausdrücke die zu 
A->Aa|a und a{a} äquivalent sind.

>A -> a[A] gleichbedeutend mit {a}a ist, oder?
Stimmt. Aber nicht ausschliesslich. Es gibt noch andere Ausdrücke die zu
A -> a[A] und {a}a äquivalent sind.

Gruss

>Wenn Du Deinen Code von 21:21 wieder rückwärts in eine Grammatik
>übersetzt wirst Du feststellen, das der Code
>
> [...]
>
>Sätze der Grammatik A-> {a} b erkennt.
>während der Code
>
>[...]
>
>Sätze der Grammatik A->aA|b erkennt.
>
>Beide Sprachen sind verschieden.

Insbesondere dieser Teil hat sehr dazu beigetragen, dass ich es nun 
weitestgehend hoffe, verstanden zu haben.

Ich war davon ausgegangen, dass A-> {a} b = aA|b ist.
Aber das ist ja dann nicht der Fall, wie du sagst.
Ich war nur nach folgendem Beitrag davon ausgegangen, den ich dann 
irgendwie Missverstanden haben muss:


------------------------------------------------------------------------ 
---------------------
Autor:  Karl heinz Buchegger (kbuchegg) (Moderator)
Datum: 27.02.2008 11:16

jochen wrote:

> funktioniert er. Ich habe versucht, ihn umzuschreiben für die folgende
> Grammatik
>
> B-> aB
> B-> b

Du musst diese Grammatik noch mal umschreiben. Diese hier eignet
sich nicht für einen rekursiven Abstieg.
Insbesondere kann es nicht 2 Regeln für 'B' geben. Für jedes
nicht terminale Symbol kann es nur 1 Regel geben.

B -> { a } b.

(Heist soviel wie: Ein B ist eine (möglicherweise auch 0
lange) Sequenz von a gefolgt von einem b.
------------------------------------------------------------------------ 
---------------------


Ich habe mir jetzt in dem Zusammenhang mit dem Bsp.
A-> Aa | b, was ja in abgewandelter Weise das Ausgangsproblem war, mal 
das Thema  Linksrekursionen angeschaut.
 demzufolge kann man die Grammatik umschreiben in

A -> bA'
A' -> a A' | epsilon

und diese hab ich dann direkt in Code verfasse (im folgenden Code steht 
B für A' in der genannten Grammatik)

1

public boolean A(){         

2

         if( pos >= str.length )

3

              return false;           

4

         if (str[pos] =='b'){

5

           pos++;

6

           if ( B() ) return true;

7

         }

8

         return false;

9

         }

10

11

12

13

      public boolean B(){

14

        if( pos >= str.length )

15

            return true;    //epsilon, wenn kein Zeichen übrig

16

                int  tmp =pos;

17

        if (str[pos]=='a'){

18

          pos++;

19

          if ( B() ) return true;

20

21

        }

22

      pos = tmp;

23

      return true; //epsilon

24

      }

und das schöne ist, es funktioniert auch ;)
Nochmal an dieser Stelle vielen Dank, ich werde auf jeden Fall von der 
Klausur berichten, aber vielleicht gibts ja zu meinem Beitrag von Euch 
noch  Hinweise ;)

> Wenn Du Deinen Code von 21:21 wieder rückwärts in eine Grammatik
> übersetzt wirst Du feststellen, das der Code
>
>[...]
>Sätze der Grammatik A-> {a} b erkennt.
>während der Code
>[...]
>Sätze der Grammatik A->aA|b erkennt.

>Beide Sprachen sind verschieden.
------------------
>Moment.
>Wie ist hier die Klammernsetzung?

>ist  A -> aA|b

>als

>A -> a ( A | b )

>zu lesen, oder ist es als

>A -> ( aA ) | b

>zu lesen?

>Beide Sprachen sind wiederrum verschieden, und die zweite
>Form ist äquivalent zu

>A -> { a } b
--------------------
Wenn Oops sagt, A-> {a} b  und A->aA|b sind verschieden,
Heinz aber meint  A -> ( aA ) | b ist äquivalent zu A -> { a } b, wie 
habe ich das zu verstehen?


Wenn
A -> Aa | b

nicht gleich

A -> bA'
A' -> a A' | epsilon

ist, was habe ich dann bei der Umwandlung falsch gemacht?
Die Regel, nach der umgwandelt wird, habe ich im Anhang.

Okay, vielen Dank, ich weiß garnicht wie sehr ich zum Ausdruck brigen 
kann wie ich mich über Eure Hilfe hier freue.
Werd noch etwas rumspielen, weitere Parser schreiben usw ...

@ Karl-Heinz Buchegger

>Aber im Ernst: Euer Prof hat schon einen Hieb. Das Thema
>Compilerbau ist Vorlesungsstoff im Informatik-Studium im 4. Semester.
>Und da gehts ein ganzes Semester nur so dahin. Sowas in einem
>Einführungskurs im ersten Semester zu bringen ist sträflicher
>Leichtsinn und führt zu nichts.

Full Ack. Teeren und federn den Mann.
Und dann im Winter auf der Terasse einen Ada-Compiler schreiben lassen.


@Jochen:
Falls möglich würde ich gerne mal die ganzen Folien sehen.

Gruss
Oops

@Jochen

>Wenn Oops sagt, A-> {a} b  und A->aA|b sind verschieden,

dann hat er da was Falsches gesagt,
und wenn

>Heinz aber meint  A -> ( aA ) | b ist äquivalent zu A -> { a } b

und vor allem auch A -> aA|b = A ->(aA)|b
dann hat er da was gesagt, was Oops so auch hätte sagen (s|w)ollen.


Und das wird jetzt in aller Ewigkkeit in irgendeinem Speicher sein. ;-)

Gruss
Oops

OOps, gerne schicke ich dir die gesamten Folien. Kannst du mir deine 
Mail adresse zukommen lassen ?

@Jochen
Dachte eher, das man sie auf der Uni-Seite irgendwo beim 
Vorlesungsmaterial anschauen kann.

Danke.

Gruss
Oops

Da muss man eingeloggt zu sein.
Ich lads grad hoch. Bist du so ca. in 20 Min hier, dann kannst du es 
runterladen, ich möchts nur so lange drin haben, wie du es dir lädst. 
Kannst mir ja bescheid geben, wenn du grad hier bist ;)

@Jochen
Oh. Das wäre nett gewesen. Leider musste ich noch was arbeiten.
Naja. Ist nicht so schlimm.

Gruss
Oops

Kannst du mir eine mail an hardice at lycos.de
schicken? Dann geb ich dir den Link davon