Mein Ziel ist es eine Konsolenanwendung in C zu schreiben. Es muss eine Datei geparsed und verarbeitet werden. Jetzt könnte ich mit standard C Strinfunktionen los legen, aber ich glaub das nimmt dann kein Ende mehr. Gibt es irgendwelche C libraries die entsprechende Funktionen (und am besten noch zusätzliche Hilfsfunktionen) beinhalten und sich als standard etabliert haben (sowohl in der Windows als auch in der Linux Welt)? Regex wäre zB ganz nett... Oder schreibt man alle Hilfsfunktionen einfach selbst?
Was verstehst Du unter einer Konsolenanwendung? Bei Datei parsen und verarbeiten fällt mir sofort Perl ein. Das ist aber nicht C. Und Parsen in C ist schwierig und fehleranfällig. Beim Parsen fällt mir dann noch das Gespann flex/bison ein, die C-Code aus der Gramatik-Beschreibung erzeugen. Also etwas genauer mußt Du schon beschreiben, wie die Dateien aussehen. mfg, Stefan.
> Mein Ziel ist es eine Konsolenanwendung in C zu schreiben. Es muss > eine Datei geparsed und verarbeitet werden. Parsen (bspw. von ein paar Integerwerten durch Leerzeichen getrennt) kann ganz leicht sein und mit den Funktionen der Standardbibliothek erschlagen werden. Es kann mittelschwer sein (bspw. Programmcode), dafür werden teilweise Parsergeneratoren (yacc, bison, javacc usw.) eingesetzt. Der Trend scheint allerdings wieder mehr zu handgeschriebenen Parsern zu gehen. Es kann schwer über sauschwer bis unmöglich sein, wenn die zugrundeliegende Grammatikklasse nicht von den einschlägigen Tools unterstützt wird. Deswegen die Frage: Wie sehen denn die zu parsenden Dateien aus?
Marius S. wrote: > Gibt es irgendwelche C libraries die entsprechende Funktionen (und am > besten noch zusätzliche Hilfsfunktionen) beinhalten GLib fällt mir da nur ein. Wenn es hauptsächlich um Stringverarbeitung geht würde ich aber dringend von C abraten und stattdessen Ruby, Python, Perl oder PHP empfehlen, damit kommst du ca. 10 mal so schnell zu einem Ergebnis.
Ich will (C-ähnlichen) code parsen, wollte damit ja nicht so direkt rum
kommen. Will einen kleinen mini Compiler bauen.
> Was verstehst Du unter einer Konsolenanwendung?
Na eine Anwendung die in der Windows bzw Linux Konsole läuft und keine
Fenster hat. Was sonst?
In einer Scriptsprache möchte ich das ganze nicht machen.
Ich hätte gedacht das es mittlerweile Bibliotheken gibt mit denen man
das Rad nicht jedes mal neu erfinden muss.
Wenn es C-ähnlicher Code sein soll, dann nimm flex/bison. Du kannst ja mal Google bemühen und nach Vorlesungsskripten für Compilerbau Ausschau halten. Meine habe ich leider nicht in elektronischer Form parat. >Na eine Anwendung die in der Windows bzw Linux Konsole läuft und keine >Fenster hat. Was sonst? Wenn Du wüsstest, was manche Leute so für Vorstellung über Konsolen haben.... mfg, Stefan.
Und noch ein Beitrag: Wikipedia scheint recht ergiebig zu sein. http://de.wikipedia.org/wiki/Kategorie:Compilerbau
Ja mit diesen flex/lex und bison/yacc wäre es natürlich am feinsten. Aber da muss man sich erstmal rein arbeiten, da hab ich keine Lust zu. Soll ja kein vollwertiger C compiler werden. Tja muss wohl mit den standard C funktionen auskommen.
Dann mach doch Rekursiven Abstieg. Einfach gesagt wird jedes Nichtterminale Symbol Deiner Grammatik in einer Funktion implementiert. Grammatik sagt Dir was? Wie sind Deine Grundlagen? Hast Du schonmal irgendwas von theoretischer Informatik gehört? Naja, auf der einen Seite willst Du eine fertige Bibliothek/Programm und dann willst Du Dich nicht darin einarbeiten. Was bezweckst Du denn mit dieser "Fingerübung"? mfg, Stefan.
Irgend etwas das halbwegs wie C aussieht (und von "vollwertig" noch weit entfernt ist) zu erschaffen, ist ohne Codegeneratoren wie lex/yacc/ragel/lemon/... unnötig hart und garantiert schnelle Frustration. Diese Werkzeuge werden oft auch für viel einfachere Dinge als Programmiersprachen verwendet, z.B. zum Parsen von HTTP-Headern, weil man da mit reinem C einfach auf keinen grünen Zweig kommt.
> Ja mit diesen flex/lex und bison/yacc wäre es natürlich am feinsten. > Aber da muss man sich erstmal rein arbeiten, da hab ich keine Lust > zu. Einen Parser für eine Programmiersprache (auch für eine einfache) setzt ein paar Grundkenntnisse und damit immer eine Einarbeitung voraus. Du kannst dir jetzt aussuchen, ob du dich in irgendwelche Tools (flex, bison) einarbeitest oder lieber lernst, den Parser von Hand (typischerweise nach dem Verfahren des rekursiven Abstiegs) zu programmieren. Unterstützende Bibliotheken kenne ich gerade keine, aber selbst diese erfordern, wenn sie ausreichend mächtig sind, eine nicht zu unterschätzende Einarbeitung. Um einen Eindruck davon zu bekommen, wie ein einfacher Parser für arithmetische Ausdrücke aufgebaut ist, kannst du dir mal dieses Beispiel anschauen: Beitrag "Re: Weis jemand, wie man mathematische Ausdrücke in C++ auswert" Das ist zwar C++, verwendet außer der umschließenden Klassen- deklaration (die du auch weglassen kannst) aber so gut wie keine C++-Elemente. Vielleicht hilft auch dieses Büchlein: http://www.oberon.ethz.ch/WirthPubl/CBEAll.pdf Da wird ein kompletter Compiler für eine kleine Programmiersprache entwickelt und sehr gut die Funktionsweise der einzelnen Bestandteile beschrieben. Wenn dich nur der Parser interessiert, musst du nur bis Seite 39 lesen, der Rest beschreibt Codegenerierung und Laufzeit- umgebung. Auch wenn der Code vielleicht nicht direkt in Assembler übersetzt werden muss, brauchst du irgendetwas, was das Programm ausführt. Das kann bspw. ein Interpreter sein, der einen mit Hilfe des Parsers generierten Zwischencodes ausführt. Am einfachsten ist es, diesen Zwischencode implizit in Form verketteter und verzweigter Listen im Hauptspeicher aufzubauen. Der Kontrollfluss wird dabei durch die Verkettungspointer der Listenelemente dargestellt. Auszuwertende Ausdrücke werden am einfachsten in eine Sequenz von Push- und stackbasierten Rechenoperationen umgeformt.
Für deinen ersten "Compiler" würde ich nicht zu lex/yacc raten, sondern zu einem Tool welches einen rekursiven Abstieg erzeugt. Der Grund: lex/yacc (flex/bison) erzeugen einen tabellengestützten Parser. Diese Parser sind zwar sauschnell und auch sehr flexibel, allerings musst du damit rechnen, dass du einige Fehler in die Grammatik einbauen wirst. Und so toll auch die flex/yacc generierten Parser auch sind, zum Debuggen sind sie ein absoluter Horror.
mir fallen jetzt auf die schnelle zwei mehr oder weniger sinnvolle sprüche ein: 1. jedes problem lässt sich mit dem passenden werkzeug relativ leicht lösen. 2. jede programmiersprache hat ihren zweck, sogar perl. @1: (f)lex/yacc-bison wären das passende werkzeug um einen compiler in C zu schreiben (ich musste sowas mal für pseudo-pascal machen). zu diesem thema findest du garantiert vorlesungsunterlagen unter dem stichwort "compilerbau", "compilerdesign", ... @2: perl ist (fast) ideal zum parsen von texten geeignet durch die (extreme) verwendung von regex. falls es unbedingt c sein muss siehe 1.
yalu wrote: > Du kannst dir jetzt aussuchen, ob du dich in irgendwelche Tools (flex, > bison) einarbeitest oder lieber lernst, den Parser von Hand > (typischerweise nach dem Verfahren des rekursiven Abstiegs) zu > programmieren. Korrigier' mich, falls ich mich irre (bin kein Informatiker), aber ich habe so in Erinnerung, dass rekursiver Abstieg nur für LL(1)- Grammatiken benutzbar ist (Pascal müsste damit machbar sein), dass C aber nur durch eine LALR(1)-Grammatik darstellbar ist und damit auf diese Weise nicht geparst werden kann. Ist natürlich eine Frage, wie viel Ähnlichkeit die zu parsende Sprache mit C am Ende haben soll, aber nichts ist frustrierender, als nach ellenlanger Einarbeitung dann feststellen zu müssen, dass die Methode zur Erreichung des Ziels schlicht ungeeignet ist.
Dieses Buch hat mir damals recht viel geholfen und zu einem kleinen Compiler geführt: http://www.amazon.com/Principles-Compiler-Addison-Wesley-information-processing/dp/0201000229
Jörg Wunsch schrieb: > ... aber ich habe so in Erinnerung, dass rekursiver Abstieg nur für > LL(1)- Grammatiken benutzbar ist ... So ist es. Wenn ich das richtig in Erinnerung habe, ist
wobei Gkf die Menge der kontextfreien Grammatiken ist. Viele (oder vielleicht sogar alle?) kontextfreien Grammatiken lassen sich aber in LL(1)-Grammatiken umformen, auch automatisch. Die Stichworte sind Left-Factoring und Left-Recursion-Elimination. > ... dass C aber nur durch eine LALR(1)-Grammatik darstellbar ist und > damit auf diese Weise nicht geparst werden kann. Das beste Beispiel, dass auch C mit rekursivem Abstieg geparst werden kann, ist der GCC. In früheren Versionen wurde ein per Bison generierter LALR-Parser eingesetzt, in Version 4.irgendwas (müsste ich nachschauen) wurde der Parser neu und von Hand geschrieben. ozo schrieb: > Dieses Buch hat mir damals recht viel geholfen und zu einem kleinen > Compiler geführt: > http://www.amazon.com/Principles-Compiler-Addison-... Ja, das ist der Klassiker. Es gibt mittlerweile auch neuere Auflagen, darunter auch eine deutsche, wobei letztere leider etwas aufgedunsen ist.
yalu wrote: > Das beste Beispiel, dass auch C mit rekursivem Abstieg geparst werden > kann, ist der GCC. In früheren Versionen wurde ein per Bison > generierter LALR-Parser eingesetzt, in Version 4.irgendwas (müsste ich > nachschauen) wurde der Parser neu und von Hand geschrieben. Danke, das wusste ich noch nicht. Das letzte Mal, als ich mir den Teil vom GCC näher angesehen habe, hatte er noch den bison-Parser.
Schauen wir mal, ob man sich nicht auf irgendetwas einheitliches einigen kann... Grammatiken: Chomsky Typ-0: rekursiv aufzählbar, d.h. alle Sprachen die eine Turing-Maschine erkennen kann Typ-1: Kontextsensitive Sprachen Typ-2: Kontextfreie Typ-3: Reguläre Für alle möglichen Typ-2 Sprachen gibt es z.Z. nur GLR, Earley und CYK-Parser. Alle anderen LL, LR/LALR etc. können nur mit eingeschränkten Typ-2 Sprachen umgehen. D.h. deterministischen, kontextfreien Sprachen bzw. Teilmengen davon. DLIN <= DCFL <= CFL <= GCSL <= CSL CSL = Typ-1, CFL = Typ-2 Schönes Tool für LL(k) http://www.antlr.org http://www.antlr.org/grammar/list p.s. Parsing Techniques - A Practical Guide http://www.cs.vu.nl/~dick/PTAPG.html
Marius S. wrote:
> Tja muss wohl mit den standard C funktionen auskommen.
Was sind denn für dich "Standard-C-Funktionen"? Eigentlich gibts erst
mal nix Andres. prinf() und exit() gehören auch schon zu deinen
"Standard-C-Funktionen".
Bitte 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.