Mathematischer String Parser

Avedo schrieb:

> Ich habe zwar bereits in C programmiert, jedoch bin ich trotzallem noch
> ein Anfänger in diesem Bereich.

In dem Fall hast du einen Kardinalfehler gemacht:
Du hast viel zu viel Code auf einmal geschieben und jetzt siehst du den 
Wald vor lauter Bäumen nicht mehr.

Schmeiss alles raus und fang noch einmal neu an.
Aber diesmal beginnst du mit der Funktion next() und nur mit dieser 
Funktion. Die rufst du von main() aus in einer Schleife auf, solange bis 
next() mitteilt, dass es nichts mehr hat. Dann soll sich die Schleife in 
main() beenden.

Als nächstes nimmst du dir die Funktion Number vor und schreibst sie. Du 
belegst deinen Input-String mit einer Zahl vor und rufst Number auf. 
Kriegst du die Zahl korrekt zurück? Was ist wenn mehrere Zahlen im 
String enthalten sind? Kriegst du sie alle, bis du (ja, wie eigentlich) 
feststellst, dass nichts mehr im String ist?

Etc. Schrittweise vorgehen. Von den hierarchiemässig unteren Funktionen 
nach oben gehen. Funktionalität suchen, die für sich alleine steht und 
für sich alleine getestet werden kann. Wenn next() funktioniert und 
Number() funktioniert, dann kann man Terminal() schreiben. Funktioniert 
Terminal() kann Faktor() geschrieben (und getestet) werden, etc.

Solche Rundumschläge, wie du sie gemacht hast, sind ein ziemlich 
sicherer Garant dafür, dass das alles schief gehen wird. Vor allen 
Dingen dann, wenn man zusätzlich neben der Aufgabenstellung auch noch 
die Programmiersprache lernen muss.

Oh - und ja. Der Debugger ist dein Freund.

> Außerdem bin ich noch am überlegen, wie ich am besten mit den
> anderen Terminalen (Variabeln, Funktionen, Konstanten und
> geklammerte Expressions) umgehe. Wie verarbeite ich die am
> besten? Jemand eine Idee?

Dazu musst du den kompletten Aufbau verändern.
next() liefert dann nicht einfach nur das nächste Zeichen, sondern das 
nächste Token (= Wort der Sprache). Am besten in Form eines Codes, damit 
man den Parser nicht mit Stringvergleichen überflutet. Aber soweit bist 
du noch lange nicht. Sieh erst mal zu, eine gewisse Sicherheit im Umgang 
mit C zu erlangen.

Avedo schrieb:
> Guten Abend!
>
> Ich arbeite zur Zeit an einem Parser für mathematische Ausdrücke.

Aha, und welches Verfahren? Recursive Descent?
Und wo ist ueberhaupt das Problem?

Michael

Avedo schrieb:
> Vorerst soll dieser nur "einfache" Rechnungen mit Variabeln und den
> wichtigsten Konstanten und Funktionen lösen können.

Nur mal so am Rande: "Lösen" ist ein gefährliches Wort an dieser Stelle: 
Meinst Du jetzt ein Programm zum Lösen von Gleichungen (a la Input "x^2 
= 1" -> Output "x = +/- 1") oder ein Programm zum Berechnen von 
Ausdrücken? Ich denk mal letzteres :-)

> [...]
> Ich habe zwar bereits in C programmiert, jedoch bin ich trotzallem noch
> ein Anfänger in diesem Bereich.

Mein Tip: Such Dir für den Anfang etwas einfacheres. Ich bin vor 15 
Jahren als Programmieranfänger an der selben Aufgabe fast verzweifelt.

> Außerdem bin ich noch am überlegen, wie ich am besten mit den anderen
> Terminalen (Variabeln, Funktionen, Konstanten und geklammerte
> Expressions) umgehe. Wie verarbeite ich die am besten? Jemand eine Idee?
>
> Des weiteren würde mich interessieren, wie ich die gegebene Grammatik am
> geschicktesten Ausbauen kann um logische Operationen zu unterstützen.

Weil einerseits solche Parser immer wieder mal implementiert werden 
müssen und andererseits diese Aufgabe nicht wirklich trivial ist, wurden 
Code-Generatoren wie yacc, antlr oder bison entwickelt. In der Doku zu 
bison findest Du ein komplettes Taschenrechnerbeispiel (Infix-Notation 
und RPN). Zusammen mit lex/flex braucht man fast keinen Code mehr selber 
schreiben :-)

Mir ist schon klar, dass es gerade für einen Anfänger sinnvoll und auch 
reizvoll ist, solche Dinge mal selbst zu programmieren. Aber lass Dir 
gesagt sein: Diese Aufgabe lässt sich deutlich einfacher und 
erhellender lösen, wenn Du entweder (a) mehr Programmiererfahrung hast 
oder (b) die entsprechenden Utilities verwendest. Allerdings tendiert 
man, wenn man die Voraussetzung (a) erfüllt, meist auch zu (b).

Jetzt hoff ich mal dass ich Dich nicht völlig demotiviert habe und 
wünsch Dir noch viel Erfolg!

Stephan

Ich bin verwirrt.
Du schreibst, du bist auf der Uni und hörst die Vorlesungen über 
Compilerbau und formale Sprachen. Soweit so gut. Aber gibt es dazu keine 
Übungen? Als ich dieselben Vorlesungen machte, war es völlig normal, 
dass im Laufe eines Semesters ein vollständiger, wenn auch einfacher 
Compiler samt Runtime System entstanden ist.

Token.
next soll nicht einfach nur das nächste Zeichen liefern, sondern es soll 
das nächste Wort aus der Sprache liefern. Am besten in Form eines 
Zahlencodes.
In deiner Sprache gibt es zb die Worte

NUMBER       eine Zahl
LPAREN       linke, öffnende Klammer
RPAREN       rechte, schliesende Klammer
PLUS         das Zeichen +
MINUS        das Zeichen -
SQRT         Schlüsselwort "sqrt"
SIN          Schlüsselwort "sin"
LOG          Schlüsselwort "log"
etc.

Jedem dieser Tokens gibst du eine Nummer. NUMBER wird zu 1, LPAREN zu 2, 
RPAREN zu 3 etc.

deine next Funktion zerlegt nun den Eingabestring in diese Tokens
Lautet der Eingabetext
   sin(2+23)

dann liefert next nacheinenander
SIN LPAREN NUMBER PLUS NUMBER RPAREN

und natürlich benutzt auch deine Grammatik diese Tokens (also die 
Codezahlen, denen man am besten mit einem #define einen Namen gibt

#define UNKNOWN  0
#define NUMBER   1
#define LPAREN   2
#define RPAREN   3
....

Deine Terminal Funktion sieht dann zb so aus

1

/* 

2

 * Terminal = ['+' | '-'] (

3

 *                           Number |

4

 *                           Identifier |

5

 *                           "sin" "(" Expression ")" |

6

 *                           "cos" "(" Expression ")" |

7

 *                           "(" Expression ")"

8

 *                        ) .

9

 */

10

11

void Terminal( unsigned char * NextToken )

12

{

13

  if( *NextToken == PLUS )

14

    *NextToken = next();

15

16

  if( *NextToken == MINUS )

17

    *NextToken = next();

18

19

  if( *NextToken == NUMBER ) {

20

    // mach was mit NextNumber, einer globalen Variablen, die von

21

    // next gefüllt wurde, wenn es NUMBER geliefert hat

22

    *NextToken = next();

23

  }

24

25

  else if( *NextToken == IDENTIFIER ) {

26

    // mach was mit NextId, einer globalen Variablen, die von

27

    // next gefüllt wurde, wenn es IDENTIFIER oder STRING geliefert hat

28

    *NextToken = next();

29

  }

30

31

  else if( *NextToken == SIN ) {

32

    *NextToken = next();

33

34

    // "sin" "(" Expression ")"

35

36

    if( *NextToken != LPAREN )

37

      Error();

38

    *NextToken = next();

39

    Expression( NextToken );

40

    if( *NextToken != RPAREN )

41

      Error();

42

    *NextToken = next();

43

  }

44

45

  else if( *NextToken == LPAREN ) {

46

    *NextToken = next();

47

    Expression( NextToken );

48

    if( *NextToken != RPAREN )

49

      Error();

50

  }

51

}

> ich
> weiß nicht, wie ich anstatt von einzelnen Zeichen bestimte Tokens
> einlsen und diese dann wiederum einem Terminal-Typ zuordnen kann.

Einfach Zeichen für Zeichen einlesen und bei jedem Zeichen entscheiden, 
ob es noch zum Wort gehören kann.
Beginnt etwas mit einer Ziffer, dann kommen solange weitere Ziffern, bis 
das erste Nichtziffernzeichen auftaucht. Beginnt etwas mit einem 
Buchstaben, dann gehören alle weitere Buchstaben und ein paar 
Sonderzeichen (du bestimmst welche), zu diesem Wort. Ein +, -, *, / sind 
Token für sich selbst, die nur aus diesem einen Zeichen bestehen.
Das Wort "sin" zb. ist ein reserviertes Schlüsselwort und kann daher 
kein Identifier sein, sondern liefert das Token SIN. Ebenso alle anderen 
Schlüsselwörter.
Das alles ist reine Stringverarbeitung. Das erste Zeichen lesen, 
entscheiden worum es sich handelt: Ziffer, Buchstabe oder Sonderzeichen.
Sonderzeichen ist klar: Token sofort liefern. Buchstabe: Lesen bis das 
Ende des Wortes da ist. Den gelesenen String mit einer Liste der 
Schlüsselwörter vergleichen. Ist es da drinnen, dann wird der zu diesem 
Schlüsselwort gehörende Token geliefert, ansonsten ist es ein 
Variablenname und next liefert IDENTIFIER (und speichert das gelesene 
Wort in NextId zur späteren Verwendung ab). Da du ein Wortende erst dann 
erkennen kannst, wenn du schon darüber hinausgeschossen bist, benötigst 
du eine Möglichkeit um ein Zeichen wieder in den Input zurückzustellen. 
Bei dir, mit dem Array und dem Index ist das ja kein Problem.

> ich weiß nicht, wie ich anstatt von einzelnen Zeichen bestimte Tokens
> einlsen und diese dann wiederum einem Terminal-Typ zuordnen kann.

Die Tokens deiner Sprache werden vermutlich einerseits einzelne Zeichen 
wie +, -, * oder ^ sein, andererseits aber auch Folgen mehrerer Zeichen 
wie z.B. 1.0, PI, sin oder &&. Der erste Schritt bei der Konstruktion 
des Parsers besteht also darin, einen Lexical Analyzer (LA) zu basteln, 
der die Folge von Eingabezeichen (vermutlich ein char * oder so) in eine 
Sequenz von Token umwandelt.

Ein solcher LA muss also den Eingabestring

"cos(x)^2.0 + sin(x)^2"

umwandeln in eine Sequenz der Art

FUNCTION_NAME LPAREN IDENTIFIER RPAREN POW FLOAT_LITERAL PLUS 
FUNCTION_NAME LPAREN IDENTIFIER RPAREN POW INT_LITERAL

Das ist schon mal vergleichbar mit dem, wie der Eingabestring abstrakt 
in BNF formuliert werden hätte können. Wichtig ist, dass der LA hier 
z.B. die Zeichenfolge "cos" (drei Zeichen) zu einem Token des Typs 
FUNCTION_NAME gruppiert, während bestimmte einzelne Zeichen (z.B. +) auf 
ein einzelnes Token abgebildet werden. (Bem.: LPAREN = Left parentheses, 
RPAREN = right parentheses, etc.; Literale sind üblicherweise sowas wie 
hartcodierte Konstanten, d.h. direkt im Eingabetext auftauchende 
Zahlenwerte etc.)

FUNCTION_NAME, IDENTIFIER usf. sind hier Namen bestimmter Typen von 
Token. Neben einem Typen zeichnet sich ein Token zusätzlich durch einen 
Wert aus. Beispielsweise steht das erste Token vom Typ FUNCTION_NAME 
hier für eine Funktion mit dem Namen "cos", das zweite Token desselben 
Typs jedoch für eine Funktion mit dem Namen "sin". Mithin spuckt der LA 
eine Liste von Tokens aus, wobei "Token" hier im Sinne von "Token-Typ 
zusammen mit dem konkreten Wert des Tokens" zu verstehen ist:

enum {
  TOKEN_int_literal,
  TOKEN_float_literal,
  TOKEN_function_name,
  TOKEN_lparen,
  TOKEN_rparen,
  ...
};

struct Token {
  int type;
  VARIANT *value;
};

VARIANT steht hier stellvertretend für einen Datentypen, dass beliebige 
(na ja, fast) Inhalte haben kann. Das kann man in C leicht mit einer 
(hier anonymen) Union lösen:

enum {
  VARIANT_int_value,
  VARIANT float_value,
  VARIANT_function_name,
  ...
};

struct VARIANT {
  int value_type;
  union {
    int int_value;
    float float_value;
    char *function_name_value;
    ...
  };
};

Mit dem Parser kann man dann die vom LA generierte Folge von Token in 
einen AST (abstract syntax tree) umwandeln und mit diesem arbeiten, was 
auch immer man dann halt damit anfangen will.

Stephan

Oh, das hätte ich mir schenken können. Da war jemand (Karl heinz 
Buchegger) schneller und vermutlich auch besser im Erklären. Trotzdem 
viel Erfolg an den TS.

In deinem Code hast du es zwar so lala berücksichtigt, aber das hier

Term = Factor | Factor ('*' | '/') Term

ist nicht LL(1), eine wichtige Voraussetzung für einen recursive decent 
Parser, wenn man auf den simplen Lookup von nur einem Zeichen (nämlich 
dem was next liefert) nicht verzichten will.

Es ist aber einfach, das auf LL(1) umzuformen

Term = Factor { ( '*' | '/' ) Factor } .

Stephan M. schrieb:
> Oh, das hätte ich mir schenken können. Da war jemand (Karl heinz
> Buchegger) schneller und vermutlich auch besser im Erklären.

Würde ich nicht sagen.
Die grundlegende Idee ist ja bei uns beiden dieselbe. Du hast ein paar 
andere Ansätze gewählt und das ist auch gut so. Damit sieht man auch 
eine alte Binsenweisheit: Viele Wege führen nach Rom. Aus den beiden 
Ansätzen kann man aber, denke ich, die grundlegende Idee ganz gut 
herauslesen (die ist ja auch nicht wirklich schwer) und 
Implementierungsanregungen entnehmen.

In dem Code ist soviel falsch, dass man gar nicht weiß, wo man anfangen 
soll. Tu dir einen Gefallen und geh in die Uni-Bibliothek und sieh nach, 
ob sie einen "Kernighan&Ritchie Programmieren in C" haben, leih ihn dir 
aus und arbeite ihn durch. Das hat so keinen Sinn, solange du mit 
Stringverarbeitung auf Kriegsfuss stehst.

(*) Wenn du ernsthaft C programmieren willst, kommst du um einen K&R 
sowieso nicht herum. Wenn also in der Bibliothek keiner vorrätig ist, 
solltest du ernsthaft in Erwägung ziehen dir einen zu kaufen.

PS: Mach mal im Visual Studio das Output Fenster auf/größer. Da sollten 
einige Fehlermeldungen drinn sein.

Noch ein Tip:
Am Anfang sieht es verführerisch aus, sich für 'Pointer auf irgendwas' 
mittels typedef einen Datentypalias zu schaffen. Aber irgendwann gibt 
das jeder wieder auf. Der Code wird dadurch eher verschleiert als klarer 
und tipparbeitmässig bringt es auch nichts.

Noch ein Tip:
Für den Anfang reicht es völlig aus, wenn deine 'Queue' bzw. der 'Stack' 
einfach nur ein fix allokiertes Array von int ist. Jeder int ist ein 
Tokencode. Den ganzen Aufwand mit dynamischer Allokierung brauchst du 
noch nicht machen. Vor allen Dingen dann nicht, wenn du eh in Zeitnot 
bist und den Umgang mit dynamischen Strukturen noch nicht kannst. Deine 
Queue, so denn alle Syntaxfehler raus sind, würde ziemlich Amok laufen, 
weil du denselben Speicherbereich in mehreren Knoten als Daten 
eingehängt hast, dir Daten unter dem Arsch wegge-free-t hast, etc.


Im Moment verzettelst du dich, indem du 5 Fronten gleichzeitig öffnest 
und an allen Ecken und Enden mit Problemen kämpfst. Du musst 
vereinfachen, um weiterzukommen. Es bringt nichts, immer neue Verfahren 
und Strukturen einzuführen, mit denen du dann erst recht nicht 
klarkommst. Im Moment solltest du dich für die einfachstmögliche 
Implementierung entscheiden. Und wenn das zb. heißt, dass dein Stack nur 
100 Elemente fassen kann, dann heißt es das eben. Mit einem 100-er Stack 
kann man schon eine Menge machen und eine Expression die aus 100 Tokens 
besteht, ist auch schon nicht ohne. Wenn das nicht reicht, dann geht man 
eben auf 200 hoch. Aber bring das Baby erst mal zum Laufen! Den Stack 
und die Queue gegen etwas Ausgefuchsteres austauschen kannst du immer 
noch.

Schrittweise arbeiten. Nicht zuviel Code auf einmal schreiben. Immer 
wieder die Arbeit in einen Zustand bringen, dass man den Compiler 
drüberjagen kann und das Zwischenergebnis auch testen kann.

Und noch ein PS:
Ob du die Expressionauswertung jetzt mit einem Parser machst oder mit 
Queue/Stack, ist gehupft wie gesprungen, denn den lexikalischen Analyzer 
(also deine next Funktion), die den Eingabestring tokenisiert, brauchst 
du da wie dort. Hast du die schon? Die ist dein erstes Zwischenziel! An 
der solltest du arbeiten!

Und dann hab ich noch ein PS:
Nichts gegen den Shunt-Yard Algorithmus. Aber wie dich der bei einer 
Compilerbauklausur weiterbringen soll, bei der du den rekursiven Abstieg 
für zb. Vergleiche implementieren sollst, ist mir nicht ganz klar :-) 
Was ist eigentlich aus deinem Einfachparser aus dem Eröffnungsposting 
geworden? Funktioniert der? Erkennt er Ausdrücke richtig, mit den 
bekannten Einschränkungen, die dadurch entstehen, dass du keine Tokens 
hast. Aber arithmetische Ausdrücke mit +-*/ und Zahlen sollte er ja 
können. Kannst du die Ausdrücke auch auswerten? Kommt das richtige 
Ergebnis raus?

Ich weiss Du willst es selber machen, aber als Plan B kann ich uCalc 
sehr empfehlen, das hatte ich früher mal eingesetzt und war sehr 
zufrieden. Es lässt sich als DLL sehr einfach einbinden und die Rechnung 
kann dann als String übergeben werden, so wie man es auch auf Papier 
schreiben würde.
http://www.ucalc.com/ucalcfmp.html

pp schrieb:
> Karl heinz Buchegger schrieb:
>> Nichts gegen den Shunt-Yard Algorithmus. Aber wie dich der bei einer
>> Compilerbauklausur weiterbringen soll, bei der du den rekursiven Abstieg
>> für zb. Vergleiche implementieren sollst, ist mir nicht ganz klar :-)
>
> Für die Auswertung von arithmetischen und logischen Ausdrücken wie hier
> gefordert (oder hab ich etwas übersehen - ich hab mir nämlich nicht
> alles durchgelesen) sind der Shunting Yard Algorithmus und Postfix
> Algorithmus vollkommen ausreichend und dazu auch noch sehr einfach zu
> implementieren.

Schon klar.
Aber irgendwo zwischendrinn hat der TO einmal erwähnt, dass ihm sein 
Prof als Vorbereitung für die Klausur in Compilerbau/Formale Sprochen 
empfohlen hat, so etwas zu implementieren.
Was mich irgendwie verblüfft hat, da es zu so einer Vorlesung ja auch 
normalerweise Übungen gibt, in denen ein Compiler implementiert werden 
soll. Kann natürlich auch sein, dass sich dieser Usus seit meiner Uni 
Zeit verändert hat.

Und ein Parser, der einfache arithmetische Ausdrücke symbolisch 
differenzieren kann, ist ja kein Hexenwerk, wenn man verstanden hat wie 
das alles funktioniert und für eine längere Klausur ein schönes 
Beispiel.