# Thema Wir möchten inkrementelle Parser sowohl in ihrer algebraischen Struktur als auch in einer Implementierung in Haskell als edit-lenses (alá @hofmann2012edit) auffassen. 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). Unsere Implementierung soll inkrementelle Parser für reguläre- und $LL(1)$-Sprachen sowie für Fragmente von Java und XML bereitstellen. # Bekannte Ergebnisse Parser für kontextfreie Grammatiken ~ @wagner1998efficient haben einen inkrementellen $LL(1)$-Parser mit dem gewünschten Laufzeitverhalten vorgestellt. Für allgemeine kontextfreie Grammatiken haben @wagner1997incremental eine Herangehensweise entwicklet, die Mehrdeutigkeiten direkt im Ergebnis kodiert. Hierbei wird das gewünschte Laufzeitverhalten in den meisten Anwendungsfällen (z.B. C und C++) erreicht (das worst-case Verhalten ist natürlich exponentiell). Wir betrachten auch Beispiele die zwar nicht $LL(1)$ sind jedoch trotzdem eindeutig geparst werden können (z.B. valides XML) und planen nicht nondeterminismus im Parse-Vorgang zu erlauben. Durch die Darstellung unserer Parser planen wir Änderungen in der Eingabe in Änderungen in der Ausgabe zu übersetzen, statt, wie in den referenzierten Arbeiten, in eine bereits neu konstruierte Ausgabe. Zudem planen wir unsere Beispiele möglichst deklarativ (in idiomatischem Haskell) statt imperativ (die referenzierten Arbeiten verwenden C++) zu formulieren. Inkrementelle statische Analyse ~ @maddox1997incremental beschreibt eine deklarative Sprache für kontextsensitive Grammatiken (basierend auf Attributgrammatiken) und ein System um aus jener sowohl einen inkrementellen Parser als auch ein Programm zur inkrementellen semantischen Analyse auf dem Ergebnis abzuleiten. Das präsentierte System ist eng gekoppelt und basiert in wesentlichen Teilen auf der Repräsentation der betrachteten Sprache als Attributgrammatik, was es notwendig macht diverse Fälle mit nur geringer Uniformität zu behandeln. Es lassen sich zwar Kompositionen von Attributsgrammatiken (und daher vmtl. auch von den in dieser Arbeit eingeführten _ADL_-Termen) berechnen es ist jedoch davon auszugehen, dass, vor allem durch das Interface unserer Parser als edit-lens statt als compiler-generator, einfachere Komponierbarkeit erreicht werden kann. Wir wollen zudem versuchen, durch geeignete algebraische Struktur, ohne die diversen expliziten caching-Mechanismen auszukommen, die hier eingesetzt werden. Applikative parser mit lazy evaluation ~ @bernardy2009lazy beschreibt eine Implementierung applikativer Parser (alá @swierstra2001combinator) die noch während dem parse-Vorgang Resultate produziert (der Parser ist _online_) und über einen Mechanismus verfügt partielle Resultate für den Lauf des Parsers auf einem Präfix der Eingabe zu memoisieren. Unter der Verwendung von lazy evaluation lassen sich damit unsere Anforderungen an inkrementelle Parser realisieren. Abgrenzen lassen sich die von uns verfolgten Ziele von den Ergebnissen aus [-@bernardy2009lazy] vor allem durch die Darstellung als edit-lenses und dass wir Parser für eine weitere Auswahl von Grammatiken konkret implementieren möchten. # Verwandte Themen Parser als Linsen ~ @zaytsev2014parsing stellen eine Taxonomie von Darstellungen (als String, Liste von Tokens (wmgl. getypt), Parse-Baum (wmgl. mit Vieldeutigkeiten), …) vor und charakterisieren Prozesse die zwischen Darstellungen konvertieren (insbesondere Parser als funktionale Linsen). @hofmann2012edit erweitern das gewöhnliche Bild von funktionalen Linsen um solche, die direkt auf Differenzen von Strukturen agieren. Die beiden Ergebnisse lassen sich insofern kombinieren, dass inkrementelle Parser als edit lenses aufgefasst werden, was mitunter Ziel der Arbeit sein soll (@zaytsev2014parsing schlagen diese Anwendung in ihrer Arbeit vor). Edit languages ~ @hofmann2013edit spezifizieren eine Sprache zur Beschreibung von edit-Operationen auf _information-trees_. Es ist naheliegend geparste XML-Dokumente als information-tree aufzufassen und Veränderungen in der serialisierten Darstellung des Dokuments vermöge unserer XML-Parser edit-lens auf edit-Operationen aus [-@hofmann2013edit] abzubilden. Bidirectional tree- & string transformations ~ @foster2007combinators spezifizieren eine Sprache für bidirektionale Baum-Transformationen als funktionale Linsen und deren Kompositionen. Sollte sich im Laufe der Implementierung herausstellen, dass eine Repräsentierung der edit-Operationen auf XML als Linsen zusätzliche Uniformität hervorbringt, so ist es zweckmäßig von der Beschreibung alá @hofmann2013edit auf bidirektionale Baum-Transformationen umzusteigen. Es ist abzusehen, dass, falls eine Beschreibung der edit-Operationen auf Bäume nützlich ist, sie es auch auf Strings sein wird. In diesem Fall bieten sich die Methoden von @bohannon2008boomerang an. Symmetrische Linsen ~ Unparsing (pretty-printing) soll in dieser Arbeit nicht behandelt werden. Polish Parsers & Parser-Kombinatoren ~ Es ist nicht auszuschließen, dass wir unsere Beispiel-Parser vermöge einer eigenen Implementierung von Parser-Kombinatoren (alá @swierstra2001combinator) konstruieren. Falls sich eine Implementierung von Parser-Kombinatoren anbietet gibt es keinen offensichtlichen Grund warum sich die Konstruktion aus [-@hughes2003polish] nicht anwenden lassen sollte.