Hallo, ich habe ein Java Programm und darin einen .StackOverflowError
Wie kann ich nun diesen Fehler beseitigen, wie ist das allgemeine
Vorgehen wenn man selber einen Fehler suchen möchte?
In deinem Fall (du bist doch der Parser-Jochen?) tippe ich
mal auf eine endlose Rekursion.
Starte deinen Debugger, steppe den Code durch, betrachte die
Variablen in deinem Code und wie sie sich verändern, und sieh
nach warum die Rekursion nicht abbricht.
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):
Es gibt keine Bedingung, die das Programm davon abhalten würde immer
die Unterfunktion A() aufzurufen.
Wenn
1
if(pos>=str.length)
einmal false ist bleibt's immer false - pos wird ja nie modifiziert.
Geht das Ganze einfach im Einzelschrittmodus durch, dann siehst du, was
da schief läuft - ist meiner Meinung nach recht offensichtlich.
Gruß
Kai
jochen wrote:
> kann der Debugger die Fehler finden und korrigieren, oder was ist das?
Der Debugger ist ein Programm, welches die Kontrolle über
dein Programm übernimmt.
Unter der Kontrolle des Debuggers kannst du zb. eine Anweisung
deines Programmes ausführen lassen. Du kannst auch Variablen
begutachten. Du kannst Breakpoints setzen (ein Breakpoint
ist ein Punkt im Programm, an dem der Debugger wieder die
Kontrolle übernimmt und dein Programm anhält, so dass du
zb. wieder Variablen anschauen kannst) etc.
Der Debugger findet keine Fehler. Er legt sich als Schale
rund um dein Programm und ermöglicht dir, deinem Programm
life zuzuschauen, wie es ausgeführt wird, welche if-Abzweigungen
genommen werden, wie Schleifen ausgeführt werden. Er ermöglicht
dir Variablen auszulesen und so festzustellen, warum eine if-
Abzweigung genommen wurde etc.
Kurz und gut: Ein Debugger ist dein Fenster in das Programm
während das Programm läuft.
Als es noch keine Debugger gab, behalf man sich mit Ausgabeanweisungen
an strategischen Stellen, um aus der Ausgabe rückzuschließen, wie
das Programm durchlaufen wird und wie sich Variablen verändern
und dadurch wieder den Programmablauf beeinflussen. Nur sitzen
diese Ausgaben notorisch immer an den falschen Stellen :-)
Mit einem Debugger braucht man das nicht mehr, man kann dem Programm
direkt zuschauen wie es abläuft.
Ja, das merk ich jetzt auch :(
Wie würdest du das am geschicktesten lösen?
Ich habe zwar eine Idee
1
publicbooleanA(){
2
if(pos>=str.length)
3
returnfalse;
4
pos++;
5
if(!A()){pos--;
6
7
}
8
if(str[pos]=='a'){
9
pos++;
10
returntrue;
11
}
12
13
returnfalse;
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?
Du bist auf dem Holzweg.
Dein Problem ist, dass die EBNF
A -> [A]a
schon nicht zulässig ist :-)
Du kannst ja mal versuchen die terminalen Anfänge der beiden
'Wege' in dieser Regel zu bestimmen.
Ich weiß ehrlich gesagt nicht, was dein Programm eigentlich tun soll -
aber wer globale Variablen für die Steuerung einer Rekursion in
unstrukturierter Form verfasst sollte schon sehr genau wissen, was er
tut... vielleicht nochmal zurück an den Schreibtisch mit dem Problem...
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 wrote:
> 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.
Gar nicht.
Diese Grammatik ist so nicht umsetzbar (mit einem Zeichen Vorausschau).
Da musst du mit dem schweren Geschütz ran und eine völlig
neue Grammatik machen, die das Gleiche bewirkt.
@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
@Oops
> Sieht irgendwie doch nach einem Kurs: "Formale Sprachen" oder> "Compilerbau" aus aber da passen die Grundkenntnisse irgendwie nicht.
Yep.
> Aber es gibt sicher ne einfache Erklärung dafür, aber so langsam werde> ich neugierig.Beitrag "Re: Parser einer Grammatik"Beitrag "Re: Parser einer Grammatik"
Klingt für mich entweder nach einem Quereinsteiger, der gerade
dabei ist sich zu übernehmen, oder jemandem der sich bisher
durchs Studium gemogelt hat.
No offence to Jochen, aber so sieht das für mich aus.
Schön langsam kriege ich nämlich Gewissensbisse, ob das überhaupt
sinnvoll ist, das alles hier so im Detail durchzukauen, was eigentlich
Stoff für 5 oder 6 Übungen am Anfang des Semesters gewesen wäre.
Mit viel Glück schaffst er es durch die Klausur. Aber wie geht es
dann weiter?
@ 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
intacount=0;
2
intbcount=0;
3
publicvoidA(){
4
whilestr[pos]=='a'{
5
pos++
6
acount++;
7
}
8
9
if(C()==true)
10
whilestr[pos]=='b'{
11
pos++
12
bcount++;
13
{if(acount==bcount)
14
returntrue
15
}
16
17
returnfalse;
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
publicbooleanA(){
2
if(str[pos]=='a'){
3
while(str[pos]=='a'){
4
pos++;
5
}
6
returntrue;
7
}
8
returnfalse
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
returntrue;
7
}
8
returnfalse;
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
publicbooleanA(){
2
if(str[pos]=='a'){
3
pos++;
4
if(A())returntrue;
5
}
6
if(str[pos]=='b'){
7
pos++;
8
returntrue;
9
}
10
returnfalse;
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?
@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
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
publicbooleanA(){
2
while(str[pos]=='a'){
3
pos++;
4
}
5
if(str[pos]=='b'){
6
pos++;
7
returntrue;
8
}
9
returnfalse;
10
}
Sätze der Grammatik A-> {a} b erkennt.
während der Code
1
publicbooleanA(){
2
if(str[pos]=='a'){
3
pos++;
4
if(A())
5
returntrue;
6
}
7
if(str[pos]=='b'){
8
pos++;
9
returntrue;
10
}
11
returnfalse;
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
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
Vielen Dank Oops, dass du heute abend für mich eingesprungen bist.
> 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.
Ja klar.
Gemeint war: Jemand hat sich die erste Grammatik angesehen (also
analysiert), sie für gut befunden und festgestellt, dass sie
direkt in ein Programm umgesetzt werden kann.
Bei der zweiten hingegen ging das nicht. Nach dieser Analyse hat
er weiter gemacht, den Sinn der Grammatik analysiert und eine
dazu äquivalente Grammatik geschrieben, die umsetzbar ist.
Der erste Teil der Analyse, der kann nach rein formalen Regeln
erfolgen. Dazu muss man nicht besonders denken, sondern einfach
nur relativ stur gewisse Dinge der Grammatik abprüfen. Wie
zb. ob es Probleme mit den terminalen Anfängen gibt.
Wenn in diesem Teil der Analyse keine Probleme auftauchen, dann
kann man direkt an die Umsetzung in einen rekursiven Abstieg gehen.
Bei der zweiten genannten Grammatik, ist man aber bei diesem
Abklopfen der Grammatik auf Probleme gestossen. Daher kann man
nicht sofort eine Umsetzung machen. Man muss weiter analysieren,
was denn der Sinn der Grammatik sei. Und da kommt jetzt das
'Zurücklehnen' ins Spiel. Hat man den Sinn der Grammatik (also:
was will uns der Autor sagen) erfasst, dann kann man meist eine
dazu äquivalente Grammatik angeben, die sich dann auch in einem
rekursiven Abstieg umsetzen lässt.
So war das gemeint.
Mein Fehler, wenn das nicht richtig rübergekommen ist.
> Bin an einer Uni und das Thema ist Klausurrelevant für die> Vorlesung "praktische Informatik" im ersten Semester (Studiengang> Elektrotechnik).
Muss mich entschuldigen, da hab ich dir was unterstellt.
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.
> 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.
Ich denke, das hier ist die wichtigste Aussage überhaupt.
In einem gewissen Sinne sind EBNF und Java (oder C-Programm)
nur andere Darstellungen desselben Sachverhaltes. Das Programm
folgt mechanisch automatisch aus der EBNF. Wenn man sich also
sicher ist, dass man bei der Übertragung der EBNF in das Programm
keinen Fehler gemacht hat (der häufigste Fehler ist ein vergessenes
Weiterschalten zum nächsten Symbol nachdem ein terminales Symbol
erkannt wurde), und der Parser funktioniert trotzdem nicht, dann
muss man den Fehler immer in der EBNF Grammatik suchen. Dort
hat man dann irgendetwas übersehen.
Wenn die Grammatik verkorkst ist, dann wird es auch der Parser
sein. Es ist aber grundfalsch das Problem lösen zu wollen, indem
man am Parser rumbastelt. Da hilft nur eins: Grammatik her und
die Grammatik ändern.
>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
publicbooleanA(){
2
if(pos>=str.length)
3
returnfalse;
4
if(str[pos]=='b'){
5
pos++;
6
if(B())returntrue;
7
}
8
returnfalse;
9
}
10
11
12
13
publicbooleanB(){
14
if(pos>=str.length)
15
returntrue;//epsilon, wenn kein Zeichen übrig
16
inttmp=pos;
17
if(str[pos]=='a'){
18
pos++;
19
if(B())returntrue;
20
21
}
22
pos=tmp;
23
returntrue;//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 ;)
jochen wrote:
> Ich war davon ausgegangen, dass A-> {a} b = aA|b ist.> Aber das ist ja dann nicht der Fall, wie du sagst.
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
Üblicherweise wird
A -> aA | b
als
A -> ( aA ) | b
gelesen. D.h. direkt aneinanderstehende Symbole binden stärker
als |
>> 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
Das kann nicht stimmen. In deiner Urgrammatik:
A -> Aa | b
kann nach einem b nichts mehr kommen. Wenn b auftaucht ist der Satz
zuende.
In deiner neuen Grammatik muss aber nach einem b noch ein A' kommen.
Ein A' kann zb ein einzelnes a sein.
D.h. der Satz ba ist zwar Satz deiner zweiten Grammatik aber
nicht Satz deiner ersten Grammatik.
> 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.
jochen wrote:
> 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?
Das es darauf ankommt, wie aA|b gelesen wird.
Im Zweifelsfall (wie in der Mathematik) immer Klammern setzen!
jochen wrote:
> 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.
Diesmal hab ich mich ins Boxhorn jagen lassen :-)
ba ist sehr wohl Satz der ersten Grammatik
b a
| |
v |
A |
| |
+-+--+
|
v
A
und damit ist mein Einwand hinfällig. (Sch..ß Linksrekursion)
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
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 ;)
Thread beobachten
Seitenaufteilung abschalten