From 7cdccabeedda7566ad5164ad297695b4d9f8d0be Mon Sep 17 00:00:00 2001 From: Gregor Kleen Date: Wed, 25 Oct 2017 09:34:11 +0200 Subject: Support includes --- topic.md | 37 ++++++++++++++----------------------- 1 file changed, 14 insertions(+), 23 deletions(-) (limited to 'topic.md') diff --git a/topic.md b/topic.md index 78fe5be..eb633aa 100644 --- a/topic.md +++ b/topic.md @@ -1,25 +1,16 @@ -Ziel ist es eine Methode zu erarbeiten mit der sich Parser beschreiben lassen, -die, gegeben ein vorheriges Ergebnis und eine Beschreibung des Unterschieds -zwischen des damaligen Inputs und dem aktuellen, schneller das neue Ergebnis -produzieren können als es ohne zusätzlichen Kontext möglich wäre. +Wir möchten inkrementelle Parser sowohl in ihrer algebraischen Struktur als auch +in einer Implementierung in Haskell als edit-lenses (alá @hofmann2012edit) +auffassen. -Zunächst wird hierfür nach bereits vorhandener Arbeit recherchiert (z.B. die -inkrementellen Parser des Texteditors “Yi”) und versucht deren Ergebnisse vom -obigen Thema abzugrenzen. +Unter einem inkrementellen Parser verstehen wir (analog zu +@ghezzi1979incremental) ein Programm, das, nach einem initialen Parsevorgang, +gegeben eine Spezifikation einer Änderung der textuellen Eingabe schneller ein +neues Ergebnis erzeugt als es ohne zusätzlichen Kontext möglich wäre +(gewöhnlicherweise in logarithmischer Zeit in der Länge der Eingabe). +Für die Darstellung als edit-lens erweitern wir diese Definition und fordern, +dass statt einem neuen Ergebnis eine Spezifikation einer Änderung am Ergebnis +erzeugt werden soll (das Anwenden dieser Änderung auf ein altes Ergebnis sollte +die Laufzeit nicht verschlechtern). -Die algebraische Darstellung von Parsern als funktionale Linsen und von der -Applikation von Änderungen (sowohl an der Eingabe, als auch, im Optimalfall, an -der Ausgabe eines Parsers) als “edit-lenses” soll verwendet werden. - -Dann wird die naheliegenden Konstruktion für den Speziallfall, dass es sich beim -betrachteten Parser um einen DFA handelt der nur prüft ob eine Eingabe -akzeptiert wird und wmgl. eine Implementierung dieser Konstruktion in Haskell -vorgestellt. -Nun wird versucht die Konstruktion zunächst auf Parser und dann auf mächtigere -Automaten zu erweitern. -Speziell sollen hier Parser betrachtet und implementiert werden, die paarweise -auftretende Klammern gruppieren und sicherstellen, dass Variablen in der Syntax -einer imperativen Programmiersprache nur benutzt werden, nachdem sie deklariert -wurden. -Es soll dann versucht werden iterative Parser für XML und ein Fragment der -Programmiersprache Java zu entwicklen und zu implementieren. +Unsere Implementierung soll inkrementelle Parser für reguläre- und +$LL(1)$-Sprachen sowie für Fragmente von Java und XML bereitstellen. -- cgit v1.2.3