Einfacher Interpreter in C++

[Papa (Gast)]

Für meine Malen nach Zahlen Programmieraufgaben (Studium) hab ich einen 
Taschenrechner geschrieben der nach der Umgekehrten Polnische Notation 
arbeitet. (Siehe Wikipedia)
Alles fertig, und funktioniert, jetzt aber eine Fundamentale Frage:
Wie kann ich einen Interpreter (?? heißt das dann so ??) schreiben der 
diesen Text (z.b. als char-array) in untenstehenden Code umsetetzt?

Straight forward wäre der Ansatz mit strings zu arbeiten, geziehlt die 
operatoren * + - / zu ermitteln, die zahlen zu ermitteln, zähler und 
nenner zu extrahieren, CFractions() zu erstellen usw. das wäre eine 
gigantische unübersichtbare geschubserei, mir fällt aber kein 
allgemeiner Ansatz ein so etwas zu machen.

"5/2 6/5 * 1/2 + 1/3 - 5 1/6 + 11/4 + /"

     pushValue(CFraction(5,2));       // 5/2
        pushValue(CFraction(6,5));       // 6/5
        multiply();                      // *
        pushValue(CFraction(1,2));       // 1/2
        add();                           // +
        pushValue(CFraction(1,3));       // 1/3
        subtract();                      // -
        pushValue(CFraction(5,1));       // 5
        pushValue(CFraction(1,6));       // 1/6
        add();                           // +
        pushValue(CFraction(11,4));      // 11/4
        add();                           // +
        divide();                        // /
        popResult(result);
        cout << result;

|

[Niklas G. (erlkoenig)]

Solche Texte einzulesen und zu Verarbeiten ("parsen") ist eine 
Wissenschaft für sich ("theoretische Informatik"). Lies mal Wikipedia 
über Chomsky-Hierarchie und kontextfreie Grammatik.
Ich habe mal zu Demonstrationszwecken einen sehr einfachen Parser für 
beliebige kontextfreie Grammatiken in ruby (da schön einfach, dürfte 
sich aber auch schmerzfrei in C++ übersetzen lassen) geschrieben, dem 
man die gewünschte Grammatik in einer Art BNF übergibt. Hier ist der 
Sourcecode zu finden: http://games.2g2s.de/?page_id=314
Unten im Code unter der "Parsing-Engine" ist dann eine 
Beispiel-Grammatik für eben solche arithmetischen Ausdrücke und dessen 
einlesen.

[Karl H. (kbuchegg)]

Die Syntax, die du dir da ausgedacht hast, ist schlecht, weil sie nicht 
LL(1) ist.

Kurz gesagt: wenn du als nächstes Symbol von der Eingabe ein / einliest, 
dann kannst du nicht unterscheiden, ob es sich dabei um eine Division 
oder um einen Bruchstrich für eine CFraction handelt.

Theoretisch (mathematisch) sollte das egal sein, weil ein Bruch auch 
nichts anderes als eine Division ist. Bei dir aber nicht.

d.h. du unterscheidest zwischen

  5/2

und

  5 2 /

und das ist schlecht. Denn welcher Fall vorliegt kannst du erst 
entscheiden, nachdem du in 5/2 die zweite Zahl gesehen hast. Die 
Ansicht: ja, aber im ersten Fall sind ja keine Leerzeichen vorhanden ist 
keine gute Entscheidung. Auf Leerzeichen zu setzen ist für einen 
Benutzer recht fehleranfällig, da kein Mensch einsieht, warum

  5 / 2

und

  5/2

bzw

  5 /2

verschiedene Dinge sein sollen.
Weiters: Wie ist

5 2 / 4 *

korrekt zu interpretieren? Ist das nun

         2
   5 * -----
         4

oder ist es

    5
   --- * 4
    2

deine Schreibweise wäre nicht eindeutig in diesem Punkt, wenn du 
Fractions zulässt.


Ansonsten ist sowas eine Standardübung in der ersten Hälfte der 
Vorlesung "Compilerbau". Alles beginnt damit, dass man die EIngabe 
zunächst in Symbole zerlegt. Man macht sich eine Funktion, die die 
Eingabe verwaltet und bei jedem Aufruf das jeweils nächste Symbol 
liefert. Symbole sind bei dir 'Number, Plus, Minus, Times, Divide' (ich 
ignoriere mal deine Fractions). Da deine Notataion bereits UPN ist und 
du auch UPN erzeugen musst, ist das ganze nicht viel mehr als eine Übung 
in der Stringverarbeitung.

Die Hauptfunktion sieht ungefähr so aus

#define numSym     1
#define plusSym    2
#define minusSym   3
#define timesSym   4
#define divideSym  5
#define eofSym    99
....

char InputString[80];
int nextChar;

....

  strcpy( InputString, "5 8 *" );
  nextChar = 0;


  sym = nextSym( &number );

  while( sym != eofSym )
  {
    if( sym == numSym )
    {
      sprintf( buff, "pushValue(CFraction(%d,1);\n", number );
      emit( buff );
    }

    else if( sym == plusSym )
      emit( "add();\n" );

    else if( sym == minusSym )
      emit( "subtract();\n" );

    else if( sym == timesSym )
      emit( "multiply();\n" );

    else if( sym == divideSym )
      emit( "divide();\n" );
  }

  emit( "popResult(result);\n" );
  emit( "cout << result;\n" );

....

dann brauchst du noch eine Funktion nextSym, die aus dem Eingabestring 
das nächste Symbol bestimmt.

Das geht so: die Funktion (Klasse) merkt sich, an welcher Stelle im 
String sie zuletzt aufgehört hat.
Dort macht sie beim nächsten Aufruf weiter.
Zunächst werden alle Leerzeichen überlesen. Mit dem nächsten Zeichen im 
String entscheidest du dann: ist es ein '+', '-', '*', '/' dann liefert 
die Funktion das zugehörige Symbol. Ist das nächste Zeichen aber eine 
Ziffer ('0' bis '9'), dann ist das der Anfang einer Zahl. du liest 
solange Zeichen weiter, wie sie Ziffern sind und setzt die Zahl dabei 
zusammen, während die Ziffern auftauchen. Getreu der Vorschrift

  Zahl = 10*Zahl + Ziffer - '0';

also ca so

int nextSym( int* number )
{
  while( InputString[nextChar] == ' ' )
    nextChar++;

  nChar = InputString[nextChar++];

  switch( nChar )
  {
    case '+':
      return plusSym;
      break;

    case '-':
      return minusSym;
      break;

    case '*':
      return timesSym;
      break;

    case '/':
      return divideSym;
      break;
  }

  *number = 0;
  while( nChar >= '0' && nChar <= '9' )
    *number = *number * 10 + nChar - '0';
  return numberSym;
}

(Fehlerbehandlung bzw. Stringende musst du noch ergänzen.