C++ Kleiner Interpreter

master bratack · 4. Juli 2011

Moinsen,
ich will einen eiunfachen Interpreter programmieren. Der soll dann so einfache Sachen wie '1 + 1' interpretieren.
Bis jetzt habe ich folgenden Code:
http://nopaste.me/paste/8570076564e119e47c96f8

Bis jetzt habe ich soweit die Funktion, die die 'Tokens' als String zurückgibt.
Leider habe ich keine Idee, wie ich das rechnen dann Umsetzen könnte. Hat jemand eine Idee?

yama03061989 · 4. Juli 2011

nur für's verständnis: du willst also einen string einlesen z.B. 10+13-2 und er soll dann intern
10
+
13
-
2

rechnen?

master bratack · 4. Juli 2011

Ja. Rechnen & ausgeben. Aber da es in C++ keine eval() Funktion gibt habe ich keinen Plan wie das Funktionieren könnte. Leerzeichen soll der Interpreter aber auch ignorieren...

yama03061989 · 4. Juli 2011

dann musst du den string filtern, sprich du entfernst solche Dinge wie Leerzeichen, etc zuerst, so erhältst du die Rohform 10 + 23 - 0 -> 10+23-0. Die Rohform zerlegst du in einzelne Strings sprich
a_string=10
b_string=+
c_string=23
d_string=-
e_string=0

und mit diesen einzelstrings kannst du dann rechnen

master bratack · 4. Juli 2011

aber wie kann ich den die Leerzeichen ignorieren? Der neue String in der Funktion 'parse' muss ja die gleiche länge haben, wie der eingegebene

Whiz-zarD · 4. Juli 2011

Indem man erstmal eine Funktion schreibt, die den String so anpasst, dass er auch geparsed werden kann.
Also schreibst erstmal eine Funktion, die dir die Leerzeichen aus dem String entfernt.

Martem · 4. Juli 2011

Hi,

schau dir mal die funktion "strtok" in der "strinh.h" an damit kannste Strings zerlegen
nach angabe eines trennzeichens wie etwa das Leerzeichen

hier hier mal ein Link

dann brauchste noch "atof" oder besser die "strtod" aus der "stdlib.h" um deine strings in double umzuwandeln.

"atoi" bzw "atol" wenn du nur mit int oder long rechnen willst

mfg

Kagee · 4. Juli 2011

Das folgende Topic ist zwar bgzl. VB, enthält aber eine Ansi-C-Lösung von mir. Grundgedanke ist die Umgekehrte Polnische Notation.
Da du in C++ OOP und Regex etc nutzen kannst könnte man diesen Algorithmus wesentlich kürzer in Klassen formulieren - das Prinzip bleibt gleich.
https://www.computerbase.de/forum/threads/vb-net-klammern-aufloesen.697087/#post-7349546

Backslash · 4. Juli 2011

Im Anhang ein Programm von mir, dass das tut. Erkennt zwar nicht ganz alle Fehler, sollte für korrekte Eingaben aber funktionieren. Es ist sicher nicht optimal, war auch nur eine Übungsaufgabe.

Aber überlegs dir erstmal selbst, ist wirklich eine ganz interessante Aufgabe.
Bei konkreten Fragen, schau wieder vorbei.

convexus · 4. Juli 2011

zu den Thema gibt es haufenweise Literatur, was wahrscheinlich schon ein Problem darstellt, da man den Wald vor lauter Bäumen nicht erkennt.
Für handgeschriebene Parser eignen sich gut LL(1) mit bestimmten Eigenschaften. Um sich das Leben einfacher zu machen zerlegt man erstmal den zu parsenden/ interpretierenden Text in Token. Z.B. "10+13-2" in die Token-Sequenz (num, 10), plus_op, (num, 14), minus_op, (num, 2). Leerzeichen, Tabs und Zeilenumbrüche werden dabei überlesen. Anhand einer Grammatik lässt sich nun definieren, was man unter einen Ausdruck versteht. Hier gibt es viele Möglichkeiten, eine intuitive Variante ist:

Code:

Ausdruck ::= Term { '+'|'-' Term}
Term ::= Faktor { '*'|'/' Faktor}
Faktor ::= zahl | '(' Ausdruck ')' | '-' Ausdruck

Für jeden Bezeichner auf der linken Seiten (von ::=) schreibt man nun eine Funktion, welche die rechte Seite widerspiegelt und deren Wert als Ergebnis liefert. Im Groben etwa:

Code:

int term();
int faktor();

int ausdruck() {
   int res = term();
   token = next_token();
   while(token == '+' || token == '-') {
      if(token == '+') 
         res += term();
      else
         res -= term();
      token = next_token();
   } 
   return res;
}

int term() {
   int res = faktor();
   token = next_token();
   while(token == '*' || token == '-') {
      if(token == '*')
         res *= faktor();
      else
         res /= faktor();
      token = next_token();
   }  
   return res;
}

int faktor() {
   token = next_token();
   if(token == num)
     return "wert der zahl";
   else if(token == '(') {
      int res = ausdruck();
      if(next_token != ')')
          cerr << "Fehler schliessenden Klammer fehlt!";
      return res;
   }
   else if(token == '-') 
      return -ausdruck();
   else
      cerr << "Huch, unerwartetes token!";  
   return 0;    

}

Der Code soll nur zur Verdeutlichung des Prinzips dienen. Ich hoffe es hilft dir weiter.

[GP] mino · 5. Juli 2011

jup, kann dir auch nur den ansatz über kontextfreie grammatiken empfehlen.

tools, die dir aus KFGs einen c++ parser bauen sind zb. ANTLR und LAPG. beispiele findest du dann auch direkt auf deren seiten.

könnte dir noch paar beispiele anhängen, falls interesse.

einmal diese disziplin gemeistert und du wirst nie wieder handgeschriebene parser mehr schreiben.

asdfman · 5. Juli 2011

Ich will ja nicht sagen, dass in SICP steht, wie man einen Interpreter baut, der beliebige Ausdrücke auswerten
kann, aber: In SICP steht, wie das geht. Siehe Links in meiner Sig.

Der Interpreter aus SICP kann zwar viel mehr als OP will, aber er kann sich ja entpsrechend die Teile nehmen,
die er braucht

€: Wenn jetzt Leute kommen und sagen ABER ABER ABER DER INTERPRETER IST DOCH FÜR LISP:
Er ist in sehr abstrakt gehalten und kann so für jede beliebige Sprache angepasst werden. Ohne
großen Aufwand. Auch für Mathematische Ausdrücke muss man keine großen Anpassungen vornehmen.

Yuuri · 5. Juli 2011

asdfman schrieb:
Auch für Mathematische Ausdrücke muss man keine großen Anpassungen vornehmen.

Der Interpreter kann aber nur einfache Gleichungen aufschlüsseln oder? Mir schwebt da was wie z.B. 1/5x^4+2x^2+1 oder solche Scherze wie e-Funktionen und Logarithmen ein (kurz gesagt Kurvendiskussion). Wenn er auch solche "komplexen" Gleichungen aufschlüsselt, würde ich mal einen Blick rein werfen.

[GP] mino · 5. Juli 2011

wenns erlaubt ist, kann man auch einfach matlab in c++ einbinden. dann über schnittstellen matlab einfach mit den strings füttern und fertige ergebnisse erhalten

zum deployen brauchst später nur noch paar *.dlls.

master bratack · 5. Juli 2011

War matlab nicht sone teure Software? Ich glaub Matlab läuft nichtmal unter Linux.
@convexus
Bei der BNF sehe ich nicht durch, d.h. nutze ich nicht Bison/Flex

Ich habe mir zu dem Thema schon viel zu viel Wissen angelesen (Könnten rund 1GB an Ebooks sein), aber das war mir alles zu theoretisch, also dachte ich mir: lerning by doing!

jedenfalls an einen Top-Down Parser, der von Links nach recht einliest hatte ich von anfang an gedacht.

ich werde ersteinmal eine Funktion schreiben, um die Leerzeichen zu entfernen & dann gehts weiter

[GP] mino · 5. Juli 2011

doch doch. ist für linux und für studenten für 50 flocken zu haben.

master bratack · 5. Juli 2011

50? Nene, da bleibe ich lieber bei OpenSource etc.

[GP] mino · 5. Juli 2011

vielleicht gibts aber wo anders auch offene mathe-bibliotheken. eine art von stringeingabe müssten die auch haben um ausdrücke wie den von Yuuri einzulesen. meine, time is money.. außer du machst es aus neugierde/hobby.

apropos, bei ausdrücken wie den von Yuuri, wirst dich noch mit operatorpräzedenzen und korrekter klammerung rumschlagen müssen. würde mir zweimal überlegen deine anforderung per hand zu implementieren.

master bratack · 5. Juli 2011

Ich mach das nur als Hobby, da mich Interpreterbau schon immer interessiert hat. Sowas kompliziertes wie der Term von Yuuri war/ist nicht mein Ziel. Soll ersteinmal nur + & - können

[GP] mino · 5. Juli 2011

weiß nun nicht welche andere libs du momentan benutzt. um aber die blanks ohne zusätzliche mittel aus den strings zu entfernen, kann ich dir den weg über reguläre ausdrücke empfehlen. könntest somit auch andere nützliche sachen mit machen.

schau mal dazu just hier drübber und danach hier. das netz ist aber voll von weiteren beispielen dieser art.

C++ Kleiner Interpreter

Ensign

Lt. Commander

Ensign

Lt. Commander

Ensign

Whiz-zarD

Gast

Cadet 4th Year

Lt. Junior Grade Pro

Captain

Anhänge

Ensign

Lt. Commander

Commander

Fleet Admiral

Lt. Commander

Ensign

Lt. Commander

Ensign

Lt. Commander

Ensign

Lt. Commander

Ähnliche Themen