Einführung in formale Sprachen & Compilerbau

Für allgemeine Fragen zur Programmierung, welche nicht! direkt mit Lazarus zu tun haben.
Antworten
Live
Beiträge: 144
Registriert: So 22. Aug 2010, 16:06
OS, Lazarus, FPC: Backtrack 5 RC4 - 64bit Gnome
CPU-Target: 64bit
Wohnort: NRW
Kontaktdaten:

Einführung in formale Sprachen & Compilerbau

Beitrag von Live »

Hallo alle zusammen,

ich habe mich mal zu Hause hingesetzt und ein paar Ergebnisse aus meinem Informatik-Unterricht zusammen gesammelt und versucht das ganze anschaulich als PDF-Datei darzustellen. Im wesentlichen geht es dabei um die Einführung in formale Sprachen und den Compilerbau.

Inhalt Teil 1:
1. Einleitung
2. Was ist ein Compiler?
3. Deterministische endliche Automaten (DEA)
4. L als Sprache von Automaten
5. Nicht-deterministische endliche Automaten (NDEA)
6. Vom NDEA zum DEA
7. Menge der regulären Sprachen
8. Pumping Lemma als Beweiswerkzeug für nicht-reguläre Sprachen


Ich hoffe ihr könnt damit etwas anfangen und es hilft dem einen oder anderem!
Dateianhänge
compilerbau_I.pdf
Einführung in formale Sprachen & Compilerbau Teil I
(221.7 KiB) 127-mal heruntergeladen

Teekeks
Beiträge: 359
Registriert: Mi 27. Mai 2009, 20:54
OS, Lazarus, FPC: OpenSuse11.4 x86 (Lazarus: 0.9.30 FPC 2.4.2)
CPU-Target: x86
Wohnort: Cottbus

Re: Einführung in formale Sprachen & Compilerbau

Beitrag von Teekeks »

Hallo!
Ich muss sagen: mir gefällt deine Aufarbeitung.
Sehr schön übersichtlich und verständlich geschrieben (wenn man sich ein klein wenig mit der Materie auskennt).

Da ich mich auch schon mit Compilerbau beschäftigt habe (leider nicht in der Schule :( )weiß ich wie schwer es ist aus diesem Thema halbwegs was gutes da heraus zu filtern.
Gruß Teekeks

carli
Beiträge: 657
Registriert: Sa 9. Jan 2010, 17:32
OS, Lazarus, FPC: Linux 2.6.x, SVN-Lazarus, FPC 2.4.0-2
CPU-Target: 64Bit

Re: Einführung in formale Sprachen & Compilerbau

Beitrag von carli »

Der Automat, der angeblich reelle Zahlen erzeugen kann, hat noch nicht mal ein Komma.

Live
Beiträge: 144
Registriert: So 22. Aug 2010, 16:06
OS, Lazarus, FPC: Backtrack 5 RC4 - 64bit Gnome
CPU-Target: 64bit
Wohnort: NRW
Kontaktdaten:

Re: Einführung in formale Sprachen & Compilerbau

Beitrag von Live »

carli hat geschrieben:Der Automat, der angeblich reelle Zahlen erzeugen kann, hat noch nicht mal ein Komma.


Das stimmt, da ist mir ein Fehler unterlaufen. Werde es die Tage updaten und den Anhang aktualisieren.

Wäre allerdings auch eine gute Übung für Leute das Komma selber in den DEA einzubauen ;)

Keifor
Beiträge: 31
Registriert: Sa 28. Aug 2010, 15:15
OS, Lazarus, FPC: pc-linux-gnu - Funtoo stable, L trunk, FPC trunk
CPU-Target: i686/x86_64

Re: Einführung in formale Sprachen & Compilerbau

Beitrag von Keifor »

Hi,

eine nette Zusammenfassung. Ein paar Anmerkungen hätte ich da noch.

1. Zu den Begriffen und Abkürzungen (bzw. Definitionen) wäre es gut noch anzumerken, dass diese in anderen Quellen abweichen können.
Bspw. hab ich nie was von einer "formalen" Grammatik gehört, dafür wurde bei mir immer, die von einer Grammatik erzeugte Sprache L(G) als
"formale", durch Grammatik G erzeugte Sprache beschrieben. Der Nicht-deterministische Automat wurde immer als NEA bezeichnet usw.
Synthetische Analyse ist mir ehrlich gesagt auch gänzlich neu.

Das selbe gilt für Definitionen. Die Definition von Grammatik (nach Chomsky) sind rel. weit verbreitet, aber bei Automaten gibt es Unterschiede wie z.b. den Epsilon Automaten (mit spontane Übergänge, also Übergänge die Immer genommen werden) der vor allem in der Compiler Theorie gern als NEA bezeichnet/genommen wird (wahrscheinlich weil die Übersetzung von Regulären Ausdrücken in Epsilon NEAs einfacher ist). Dagegen in der eigentlichen Sprachtheorie eher als epsilon-NFA.

Das heißt nicht das diese Formulierungen falsch sind, es gibt halt nur unterschiedliche. Dies kann vor allem für Leute ohne entsprechendes Hintergrundwissen sehr irritierend sein, wenn auch noch andere Quellen gelesen werden.

2. Theoretische und praktische Zusammenhänge.

Es wäre gut bestimmte praktische Zusammenhänge sofort zu beschreiben bzw. Anzumerken wo diese nützlich sind, da die Theorie am Anfang sehr abschreckend für praktisch veranlagte Menschen sein kann. Bei Automaten ist das relativ einsichtig, dass sie genutzt werden können um irgendwas zu Akzeptieren. Grammatiken dienen im Compilerbau der Beschreibung von Parsern (hier synthetische Analyse), Reguläre Ausdrücke werden gern genutzt um Lexer zu beschreiben (hier lexikalische Analyse).

Ähnlich ist es mit dem Pumping Lemma für Reguläre Sprache. Es gibt auch hier verschiedene Lemmata für verschiedene Sprachklassen. Der praktische nutzen ist zwar ersichtlich (Test/Falsifikation der Zugehörigkeit einer Sprachklasse), aber i.d.R. wird in vielen Compilerbau Werkzeugen auf Pumping Lemmata verzichtet und andere, effizientere bzw. speziellere Methoden genutzt. Bspw. die Angabe der Lexik als Reguläre Ausdrücke, Test von verschiedenen Kf.G. Unterklassen wie LL(k)/SLL(k), LR(k)/SLR(k)/LARL(k) usw. oder bei Rekursive Absteigenden Parsern wird als Beschreibung einfach eine Typ-2 Grammatik vorausgesetzt, damit ist der Parser auf jeden Fall (theoretisch) mittels einem Deterministischen Pushdown-Automaten akzeptierbar.

Andere Theoretische Zusammenhänge fehlen wiederum. Beispielsweise wird bei Grammatiken von Kontextfreiheit und Chomsky Typen (Chomsky Typ 3) gesprochen was wenig weiter erläutert wird. Eine kurze Erläuterung der Chomsky Hierarchie (Kontextfreie Grammatiken sind bspw. Typ 2) und den Zusammenhang mit lexikalischer/synthetischer (bzw. syntaktischer) Analyse wäre gut oder das ganze einfach weglassen und Später erklären, wenn es genutzt wird.

3. Kurze Zusammenfassung/Fazit /Konsens für die Grundlagen: kann auch nur ein Satz sein wie z.B. "Mit diesem Kapitel wurden die Grundlagen geschaffen, als nächstes stürzen wir uns auf die Praxis..." öhm.. oder etwas besser klingendes. Wirkt sonst halt nur so abgehakt. :mrgreen:

Kurz
Zielorientiert: Am Anfang hast du bereits beschrieben, das die Zielgruppe aus Personen mit mathematischem (Grundlagen) Wissen besteht. Lese dir das ganze am besten nochmal durch und überlege bei jedem Wort (Begriff, Definition etc.) ob dieses für die Zielgruppe vorhandenes/überflüssiges/wichtiges Wissen ist, bzw. ob die Zusammenhänge knüpf-bar sind und in wie weit das für weitere Kapitel Erläutert werden muss.
Auflockernd: Überleitungen/Abschlüsse um Zusammenhänge nochmal zu festigen.

PS: Ich hoffe du siehst das nicht als "niedermachen deiner Arbeit". Die Anmerkungen sind reines Feedback um selbst nochmal die ein oder andere Frage zu stellen und evt. etwas zu Ändern/Auszubauen. Persönlich hab ich die Erfahrung gemacht, das eine kritische 2te/3te.. Meinung ungemein helfen kann. :oops:

PPS:
Evt. nützliche weiterführende Infos (Epsilon NFA, RE Transformation etc.), kurz und Knackig (einfach den Haskell Code ignorieren)
http://www.fh-wedel.de/~si/vorlesungen/ ... nhalt.html

Live
Beiträge: 144
Registriert: So 22. Aug 2010, 16:06
OS, Lazarus, FPC: Backtrack 5 RC4 - 64bit Gnome
CPU-Target: 64bit
Wohnort: NRW
Kontaktdaten:

Re: Einführung in formale Sprachen & Compilerbau

Beitrag von Live »

Danke für deine Kritik Keifor :)

Werde sie mir auf jedenfall zu Herzen nehmen und wie bereits gesagt, versuchen das ganze noch ausführlicher zu gestalten und mit praktischen Beispielen zu versehen.

Euklid
Lazarusforum e. V.
Beiträge: 2808
Registriert: Fr 22. Sep 2006, 10:38
OS, Lazarus, FPC: Lazarus v2.0.10, FPC 3.2.0
Wohnort: Hessen
Kontaktdaten:

Re: Einführung in formale Sprachen & Compilerbau

Beitrag von Euklid »

Hallo Live,

ich finde es toll, dass Du ein Skipt zum Thema Compiler und Compilerbau rausgibst. Habe zuvor noch nie etwas von DEAs und NDEAs gehört und habe das dank des Skripts verstanden. Fand auch das Beispiel, den nichtdeterministischen Automaten über einen Deterministischen auszudrücken interessant und für das Verständnis hilfreich. Die Abbildungen tragen ihren Teil dazu bei.

Nur bruchstückhaft nachvollziehen konnte ich den Abschnitt "Menge der regulären Sprachen" - vermutlich, weil er viele mir unbekannte Begriffe enthält. Derzeit habe ich beispielsweise auch nach dem Lesen des Textes keine klare Vorstellung von den Begriffen "reguläre Sprache/Ausdrücke, überhaupt regulär in diesem Sinne", "Terminale/Nichtterminale", "Produktionsregeln". Wenn der Text beim Leser lediglich mathematische Vorkenntnisse voraussetzt, wäre es denke ich gut, wenn an dieser Stelle noch etwas detaillierter darauf eingegangen werden würde.

Ansonsten ist der Text denke ich auf einem guten Weg hin zum verständlichen Einstieg.

Viele Grüße, Euklid

Antworten