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
> 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/formulainterpreter.aspx 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.
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
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
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
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
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.
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_notation#The_postfix_algorithm 6) Fertig - funktioniert für alle Operatoren, die du implementierst (arithmetische, logische, bitweise und sonstige Funktionen)
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
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?
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.
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.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.