www.mikrocontroller.net

Forum: PC-Programmierung Mathematischer String Parser


Autor: Avedo (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Guten Abend!

Ich arbeite zur Zeit an einem Parser für mathematische Ausdrücke. 
Vorerst soll dieser nur "einfache" Rechnungen mit Variabeln und den 
wichtigsten Konstanten und Funktionen lösen können. Später soll das 
ganze noch um logische Ausdrücke erweitert werden. Der Parser, den ich 
momentan implementieren möchte, wird durch die folgende Grammatik 
beschrieben.

Expression = Term | Term ('+' | '-') Expression
Term = Factor | Factor ('*' | '/') Term
Factor = Terminal | Terminal '^' Factor
Terminal = ['+' | '-'] (Number | Variable | Constant | Function | '(' 
Expression ')')

Function = identifier '(' Expression ')'

Ich habe zwar bereits in C programmiert, jedoch bin ich trotzallem noch 
ein Anfänger in diesem Bereich. Wahrscheinlich funktioniert deshalb mein 
erster Versuch vorn und hinten nicht und ich habe wirklich keine Ahnung 
warum. Wäre nett, wenn mal jemand drüberschauen könnte.

Wäre auch sehr dankbar für Anmerkungen und Anregungen zur weiteren 
Umsetzung. Verbesserungsvorschläge sind auch immer gern gesehen.

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.

Vielen Dank!

MfG, Andy

Autor: MaWin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Ich habe zwar bereits in C programmiert

Was liegt dir denn besser? Basic?

http://freenet-homepage.de/mawin/basic.htm#BASIC

Der hier ist in C/C++:

http://www.frank-buss.de/formula/index.html
http://www.codeproject.com/KB/recipes/formulainter...

oder PASCAL/Delphi

http://delphi.zsg-rottenburg.de/parser.html

geht aber wahrscheinlich über dein Verständnis.

Man programmiert von der Grammaik ausgehend nicht
mehr unbedingt selber, sondern nutzt LEX und YACC,
aber wenn es klein sein soll, auf einen uC passen
soll, ist der Weg wohl Unsinn.

Autor: Simon (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
OK, ich konzentriere mich erstmal nur drauf, das Ding zum Compilieren zu 
bringen:

das #include "defines.c" hilft uns hier nix, weil wir es nicht kennen. 
Abgesehen davon ist es schlechter Stil ".c"-Dateien einzubinden, weil so 
u.U. Code mehrfach compiliert wird. Ich habe es bei mir ersatzlos 
rausgelöscht.

Möglicherweise standen da jedoch ein paar Prototypen für die Funktionen 
des Parsers drin, ich habe die jetzt an den Anfang explizit 
reingeschrieben. Ansonsten werden die defaultmäßig implizit mit einem 
"int"-Rückgabewert deklariert, was später zu Fehlern führt.

Du hast "extern" falsch verstanden. Das brauchst Du nur, wenn Du auf 
Variablen referenzierst, die in einer anderen .c-Datei definiert werden. 
Ich habe "input" jetzt als globale Variable, die man innerhalb der 
Funktionen einfach so verwenden kann.

Das "%d" in dem printf ist für doubles falsch, man braucht "%f". Genauso 
wird das float direkt übergeben und nicht dessen Adresse.

next() soll wohl einen char * zurückgeben.

Innerhalb von "Terminal" ist das '+' nicht als Character-Konstante 
definiert - das ist ein Syntaxfehler. Außerdem kann es passieren, dass 
die Funktion durch die If-Zweige so durchläuft, dass kein return 
erreicht wird, was bei einer Funktion mit Rückgabewert fatal ist.

Uffbasse bei dem "endp"-Argument von dem strtod. Es muss heißen current 
= *endp.

So. Das alles gefixt, dann compiliert das Programm ohne 
Compilerwarnungen knallt dann mit einem Segfault, ich gebe aber zu, dass 
ich da jetzt nur begrenzt Lust habe, tiefer in das Debugging 
einzusteigen. Von der Grobstruktur her macht das Programm schon einen 
sinnvollen Eindruck, es sieht halbwegs wie ein rekursiver Abstiegsparser 
aus. Allerdings verhaut man sich bei C leicht mit dem Stringhandling, 
das kann noch beliebig eklig werden...

Mein diff habe ich mal angehängt.

Viele Grüße,
        Simon

Autor: Simon (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Oh, und den Quellcode der da hinter dem ...codeproject...-Link 
auftaucht, den würde ich nicht mal mit spitzen Fingern anfassen wollen. 
Der Autor von dem Zeugs muss sich dringend mal mit Begriffen wie 
"Syntax" auseinandersetzen und etwas Literatur über Parser wälzen. 
Grusel

...und die Auswertungsfunktion liefert im Fehlerfalle den Wert 0 zurück. 
Dolle Wurst...  lach

Viele Grüße,
        Simon

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Michael G. (linuxgeek) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Stephan M. (stephanm)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Avedo (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Guten Abend!

Zuerst mal ein Danke an dieser Stelle für die vielen und erhellenden 
Antworten.

Ich habe vergessen zu erwähnen, dass ich diesen Parser aus mehreren 
Beweggründen schreibe. Deshalb möchte ich dies nun nachholen um auch 
einige eurer Fragen zu klären.

Ich bin Informatik-Student im 2.Semester und darf mich momentan auf eine 
Klausur vorbereiten, die sich unter anderem mit den Themenkomplexen 
Formale Sprachen, Grammatiken, Automaten und Compilerbau beschäftigt. 
Zur Übung hat mein Professor uns ans Herz gelegt einen einfachen Parser 
zu implementieren, um den größeren Zusammenhang besser zu verstehen. Ich 
programmiere zwar schon seit einigen Jahren PHP und zudem sind mir C# 
und Java nicht fremd, jedoch werden wir in der Uni in Zukunft vorallem C 
verwenden um gestellte Aufgaben zu lösen. Deshalb und da mir C so oder 
so als Sprache sehr gefallen hat, habe ich mich für diese Sprache 
entschieden. Des weiteren kommt hinzu, dass ich momentan im Rahmen 
meiner Vorlesungsfreien Zeit ein freiwilliges Praktikum mache. Dort soll 
ich neben der Programmierung einer CNC-Steuerung, was mir bisher auch 
wirklich gut gelingt, auch einen mathematischen Parser schreiben, der 
später bei der Erzeugung von Schritttabellen helfen soll. Auch hier 
bietet sich C als Programmiersprache an. Zu guter letzt sind wir im 
Rahmen unserer mathematischen Vorlesungen immer wieder dazu verpflichtet 
verschiedene Algorithmen, wie zum Beispiel den Gauß-Jordan-Algorithmus, 
(vorzugsweise in C) zu implementieren. Dabei wäre es oftmals hilfreich 
einfache Funktionen von der Linux-Shell einlesen zu können.

Ihr sehr es gibt für mich genügend Beweggründe einen solchen Parser zu 
schreiben und dafür nicht die gängigen Code-Generatoren wie flex/lex und 
bison zu verwenden, auch wenn dies sicherlich deutlich einfacher wäre 
und mir sicherlich auch mehr Spaß bereiten würde.

Das Programm soll am Ende aber definitiv auf einem ganz normalen PC und 
nicht auf der CNC-Steuerung oder einem Mikrocontroller laufen (auch wenn 
mir dafür später sicherlich eine nette Anwendung einfällt).

An dieser Stelle möchte ich nochmal Simon für seine wirklich großartige 
Hilfe danken. Habe es dank dir nun soweit geschafft, dass das Programm 
kompiliert und ohne Segmentation Fault durchläuft. Leider erhalte ich 
ein falsches Ergebnis. Doch ich denke das kann ich nun, da ich mit dem 
Debugger von Visual Studio Express Edition 2008 für C++ arbeite auch 
ausmerzen. Zudem werde ich das Programm aber nochmal Schritt für 
Schritt, so wie Karl es mir empfohlen hat durchgehen um so sicher zu 
stellen, dass die einzelnen Funktionen auch das tun, was sie sollen.

Ich habe aber noch eine Frage zu dem Beitrag von Karl. Er erwähnte, dass 
ich, wenn ich die verschiedenen Terminale verarbeiten möchte, nicht nur 
mit dem nächsten Zeichen, sondern mit dem nächsten Token (dem nächsten 
Wort der Sprache) arbeiten müsste. Wie könnte eine einfache 
Implementierung dafür aussehen? Wie müsste ich eine entsprechende 
next()-Funktion implementieren? Kennt jemand vielleicht ein einfaches 
Beispiel mit einer unterscheidung von zwei bis drei Token-Typen?

Michaels Frage betreffend bin ich im übrigen der Meinung, dass ein 
Top-Down (oder auch Recursive Descent) Parser die einfachste Lösung für 
mein problem darstellt und mir auch die dahinter stehende Theorie am 
einfachsten veranschaulicht. Das Problem sollte klar geworden sein. ich 
weiß nicht, wie ich anstatt von einzelnen Zeichen bestimte Tokens 
einlsen und diese dann wiederum einem Terminal-Typ zuordnen kann.

Zuletzt möchte ich noch auf Stephans Beitrag eingehen. Lösen ist hier 
tatsächlich das falsche Wort. Ich möchte Ausdrücke verarbeiten. gebe ich 
also später 3 + 2 * 5 soll mir mein Programm 13 zurückgeben. Gebe ich 
jedoch 3 * x + 2 - y^2, sowie 2 und 1 ein, so soll mir mein Programm 7 
als Ergebnis liefern. Das letztere ist wichtig um später die 
Schritttabelle für die CNC-Steuerung anhand einer gegebenen Funktion 
bestimmen zu können. Natürlich würde ich auch gerne mit etwas 
einfacherem starten bzw. weiter machen, jedoch erlauben das die umstände 
nicht. Zudem habe ich schon ein paar Dinge, wie zum Beispiel einen 
Backtrackin-Algorithmus zum Lösen des Springer-Problems oder auch das 
Gauß-Jordan-verfahren zum Lösen von Matrizen in C implementiert. Auch 
nicht ganz trivial, aber immernoch einfacher, wenn man mal die 
Mathematik dahinter verstanden hat.

Ich hoffe weiterhin auf eure Hilfestellungen, Anmerkungen und 
Anregungen. Links und Codeschnipsel sind natürlich auch gerne gesehen. 
Da ich leider meinen Stick mit dem momentanen Stand der Dinge an meinem 
Praktikumsplatz vergessen habe, werde ich hier morgen nochmal die 
parser.c nachreichen.

Vielen vielen Dank nochmal für die bisherige Hilfe.

Liebe Grüße,

Andreas

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

/* 
 * Terminal = ['+' | '-'] (
 *                           Number |
 *                           Identifier |
 *                           "sin" "(" Expression ")" |
 *                           "cos" "(" Expression ")" |
 *                           "(" Expression ")"
 *                        ) .
 */

void Terminal( unsigned char * NextToken )
{
  if( *NextToken == PLUS )
    *NextToken = next();

  if( *NextToken == MINUS )
    *NextToken = next();

  if( *NextToken == NUMBER ) {
    // mach was mit NextNumber, einer globalen Variablen, die von
    // next gefüllt wurde, wenn es NUMBER geliefert hat
    *NextToken = next();
  }

  else if( *NextToken == IDENTIFIER ) {
    // mach was mit NextId, einer globalen Variablen, die von
    // next gefüllt wurde, wenn es IDENTIFIER oder STRING geliefert hat
    *NextToken = next();
  }

  else if( *NextToken == SIN ) {
    *NextToken = next();

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

    if( *NextToken != LPAREN )
      Error();
    *NextToken = next();
    Expression( NextToken );
    if( *NextToken != RPAREN )
      Error();
    *NextToken = next();
  }

  else if( *NextToken == LPAREN ) {
    *NextToken = next();
    Expression( NextToken );
    if( *NextToken != RPAREN )
      Error();
  }
}

> 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.

Autor: Stephan M. (stephanm)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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

Autor: Stephan M. (stephanm)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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 } .

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: pp (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Dies wäre mein Vorgehen:
1) eine Queue implementieren
2) einen Stack implementieren
3) alle Tokens des Input-Strings in Queue rein
4) Queue (Infix Notation) in Reverse Polish Notation (RPN) umwandeln 
Ergebnis wird in einer Queue abgelegt (Shunting Yard Algorithmus - damit 
wirst du die Rangfolge und Assoziativität von Operatoren sowie alle 
Klammern los)
5) RPN Queue auswerten wie hier beschrieben: 
http://en.wikipedia.org/wiki/Reverse_Polish_notati...
6) Fertig - funktioniert für alle Operatoren, die du implementierst 
(arithmetische, logische, bitweise und sonstige Funktionen)

Autor: Avedo (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Hallo zusammen!

Danke für eure tollen Beiträge. Habe mich nun daran gemacht erst einmal 
einen Stack und einen Queue zu implementieren. Leider habe ich dabei 
noch ein paar Probleme und einige neue Fragen.

Zu den Problemen. Wie ihr vielleicht schon bemerkt habt, habe ich die 
Datei Queue.c an diesen Post angehängt. Ich habe sie mit Visual Studio 
Express 2008 für C++ geschrieben. Der Compiler wurde in den 
Einstellungen für das projekt auf C umgestellt. Das Problem ist aber, 
dass das Programm compiliert, aber dann nur für den Bruchteil einer 
Sekunde ein Terminal anzeigt. Ich konnte nur durch Debuggen 
herausfinden, dass die main()-Funktion überhaupt nicht betreten wird. 
Compiliere ich das Programm mit Pelles C für Windows, so erhalte ich 
einige Fehler, mit denen ich aber leider nichts anfangen kann. Er 
scheint ein problem mit den Strukturen für die Queue zu haben. kann mir 
jemand sagen, was daran falsch ist?

Meine eben erwähnte Frage bezieht sich daarauf, wie ich aus einer 
"normalen" C-Datei einen header-File machen kann. Mir wurde ja 
angetragen keine C-Dateien zu includen. Zudem wäre es auch interessant 
zu wissen, ob es notwendig ist die Token-Struktur dann in dieser 
header-Datei zu definieren, oder ob ich das auch in der einbindenen 
C-Datei machen kann. Das würde mir später nämlich erlauben den 
Header-File ohne etwas daran ändern zu müssen für andere Aufgaben zu 
gebrauchen.

Vielen Dank nochmal.

MfG, Andy

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: pp (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Johnny B. (johnnyb)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.