Ich wieder mit meinem Parser

Codehure

Moin Moin

Punkt vor Strich Rechnung!
Also erst die Punkt Rechnungen suchen und ausrechnen. Dann Ergebnis anstatt der Berechnung einfügen (Liste müste es erlauben das sich die Länge bzw die Elemente dynamisch ändert) Nun die Strichrecnung ausführen bis du zu 23=a kommst und fertig!

cu Jens

otze

du musst das vor der erstellung des Baumes erst in folgende form bringen:

= a + 10 / * 40 66 2

Dies passiert meistens direkt irgendwie beim Parsen,dazu werden dann grammatiken benutzt. such mal nach EBNF

aufjedenfall daraus kannst du dann direkt folgenden baum machen:

=
 /   \
a      +
     /   \
    10   (durch)   
         /   \          
        *     2
      /   \
     40   66

Hmmm, habe jetzt nicht ganz verstanden wozu das EBNF gut sein soll.

Wenn ich jetzt einen String wie z.B. a = 10 + 4 * 3 in seine Einzelteile zerlege.

a

10
+
4
*
3

Wo kommt das EBNF zum Einsatzt.

Ich würde jetzt mal sagen ich laufe jetzt die List durch bis zum Ende. Und versuche die einzelnen Tokken( nennt man das so? ) richtig zu sortieren.

Hui

ich habe gerade gelesen das was ich da bis jetz gemacht habe ein Lexer ist.

Also er zerteilt einen String in Tokken. Und der Parser arbeitet mit den Tokken.

wird ja immer komplizierter.

otze

und der parser arbeitet mit normalerweise mit einer EBNF grammatik(deshalb sollteste danach suchen)

das EBNF kommt zum einsatz wenn du aus

a = 10 + 4 * 3

das von mir vorgestellte

= a + 10 / * 40 66 2

machen willst,also die token sortiert werden *seufz*

*Rammt seinen Kopf gegen die Wand um niewieder einen hilfreichen post schreiben zu müssen, der eh nicht aufmerksam gelesen wird*

Nein, nein. Die Hilfe von dir war sicher nicht umsonst. Natürlich habe ich danach gesucht.

Aber ich kann nichts brauchbares finden.

Hier ein Beispiel:
http://www.informatik.fh-muenchen.de/~schieder/programmieren-1-ws95-96/ebnf.html

Also ich verstehe nur Bahnhof.

Gibt es nicht wo an einem einfachen Beispiel gezeigt wird wie das funktioniert.

ness

Es geht darum, dass dein Parser eine grammatik in ebnf erhält. Darin ist notiert, was wie sein darf und wie das aufzufassen ist (richtig so?).

Ja das ist schon klar. Nur kommen mir die Erklärungen im Internet nicht gerade verständlich vor. Ich nehme mal an das die Verfasser selber nicht wissen was sie da schreiben

Aus

a = 10 + 4 * 3

muss

= a + 10 / * 40 66 2

werden. Ich habe mir schon Gedanken gemacht. Aber die sind nicht immer Allgemein. So das sie bei einer anderen Zusammenstellung nicht funktioniert.

otze

mal schnell eine ganz einfache grammatik(keine ahnung ob die EBNF syntax so vollständig korrekt ist):

expression::=variable "=" summ.
summ::=term {"+"|"-" term}*.
term::=integer {"*"|"/" integer}* .

diese grammatik kannst du dann abtippen, sie ist dein algorithmus. in ihr stecken nicht nur das erkennen der variablen/zahlen sondern auch die operator regeln.

da du die token ja nun voneinander trennen kannst, musst du jetzt nurnoch erkennen, was welcher token ist und ihn richtig zuordnen, mithilfe dieser grammatik geht das erstmal sehr schön

zb könntest du summ vielleicht so schreiben:

Value summ (tokeniterator& first,const  tokeniterator& last){
    term(first,last);
    for(;first!=last;++first){
        if(*first=="+"||*first=="-"){
            ++first;
            term(first,last);
        }
        else
        {
              throw ParseError(std::string("wanted \"+\" or \"-\""));
        }
    }
}

ist es nicht schön, wie schnell sich die zeile der ebnf syntax übertragen ließ?

als nächsten schritt kommt dann die umstellung der token, dies kann man in die beispielfunktion von oben direkt integrieren(bzw muss es), aber das erspar ich mir jetzt

im summ beispiel musst du aus dem tokensatz
term1 + term2

ein
+ term2 term1
machen, also immer der ausdruck der vor dem ersten operator steht direkt als erstes hinter den operator stellen

in einem komplexeren beispiel:

term1 + term2 + term3 - term4

wird schrittweise:

+ (term2 + term3 - term4) term1//das in Klammern ist unverändert
+ + (term3 -term4) term2 term1
+ + - term4 term 3 term2 term1

oder mit zahlen:
1+2+3-4

- + + 1 2 3 4

und daraus erstellst du dann den baum nach folgendem prinzip:

du schaust dir token 1 an->operator -, also erstellst du einen neuen Knoten

Knoten(-)

nächstes token: der op+. da der op+ wieder operanden hat, müssen erst diese ind en baum eingefügt werden, bevor man mit dem op- weitermachen kann

Knoten(-)
             /      
         Knoten(+)

also wird der nächste token rausgesucht, wieder ein op+, also wieder ne neue ebene...

Knoten(-)
             /       
         Knoten(+)    
         /        
     Knoten(+)

der nächste token ist ein integer
der wird natürlich sofort an den untersten knoten angefügt:

Knoten(-)
             /       
         Knoten(+)    
         /        
     Knoten(+)    
    /      
integer(1)

der nächste token kompletiert den Knoten

Knoten(-)
             /       
         Knoten(+)    
         /        
     Knoten(+)    
    /      \
integer(1)  integer(2)

da der knoten fertig ist, springen wir nächst höheren op+, da der nächste tokenw ieder eine zahl ist, wird auchd er fertig, genauso wies beim op- aussieht.

so sieht der baum am ende aus:

Knoten(-)
             /       \
         Knoten(+)    integer(4)
         /        \
     Knoten(+)    integer(3)
    /      \
integer(1)  integer(2)

so, ich hoffe du kommst nun klar

//edit huch da hab ich ja in nem vorherigen post falsch gepastest...

ist klar, dass aus

a = 10 + 4 * 3

kein

= a + 10 / * 40 66 2

werden kann...böser fehler

//edit2
mir is grad im bett nochn viel schlimmerer fehler aufgefallen:

ich hab die ganze zeit beim umformen der token geschludert, schon im ersten post ich hab immer die reigenfolge der operanden vertauscht, bei op+/op- kein problem, beim op/ siehts aber anders aus

tut mir leid, dass ich vielleicht für verwirrung gesorgt hab :(, aber habs noch oben schnell korrigiert, das was über dem edit steht müsste also alles richtig sein.

Danke für die ausführliche Beschreibung. Ich werde mir das mal reinziehen.

cu