1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
|
\subsection{Motivation}
Unter einem inkrementellen Parser \cite{ghezzi1979incremental} verstehen wir ein Programm, das, nach einem initialen Parsevorgang, gegeben eine Spezifikation einer Änderung der textuellen Eingabe i.A. schneller, gewöhnlicherweise in logarithmischer Zeit in der Länge der Eingabe, ein neues Ergebnis erzeugt als es ohne zusätzlichen Kontext möglich wäre.
Es ist nun prinzipiell wünschenswert die algebraische Struktur derartiger Klassen von Programmen zu untersuchen mit dem Ziel, neue Parser mit generischen Mitteln aus bereits Bekannten konstruieren zu können.
In dieser Arbeit versuchen wir, anhand von finite state transducern als Spezialfall, inkrementelle Parser und die unterliegenden edits mit neuerer algebraischer Struktur, edit-lenses \cite{hofmann2012edit}, zu versehen um Komponierbarkeit zu vereinfachen.
Vor Allem versuchen wir somit zu demonstrieren, dass sich bekannte Klassen von Programmen unter Erhalt ihrer vollen Struktur als edit-lenses auffassen lassen, auch dann, wenn die Darstellung als konventionelle funktionale Linse unzufriedenstellend wäre.
\subsection{Inhalt}
Wir stellen in Abschnitt \ref{edit-lenses} die Definitionen und Konstruktion von edit-lenses aus \cite{hofmann2012edit} vor und diskutieren kurz die Kompatibilität unserer Implementierung und edit-lenses im Allgemeinen mit etablierten Frameworks für funktionale Linsen in Haskell.
In Abschnitt \ref{finite-state-transducers} präsentieren wir eine etablierte Version von finite state transducern, für die folgenden Teile relevante Konstruktionen darauf und einige assoziierte Beispiele.
Abschnitt \ref{edit-lenses-fuxfcr-deterministic-finite-state-transducers} beschreibt eine Methode, beliebige deterministische finite state transducers als edit-lenses aufzufassen und stellt somit eine nicht triviale Anwendung der Methoden und Konzepte aus \cite{hofmann2012edit} dar.
In Abschnitt \ref{ausblick-edit-lenses-fuxfcr-nicht-determinische-finite-state-transducers} stellen wir kurz einen Ansatz vor, unsere Konstruktion aus \ref{edit-lenses-fuxfcr-deterministic-finite-state-transducers} auch auf nicht-deterministische finite state transducers zu erweitern.
In Abschnitt \ref{implementierung} kommentieren wir den Implementierungsprozess der Arbeit und die Schlüsse, die wir aus der Implementierung als solcher ziehen konnten.
Abschnitt \ref{ausblick-anwendbarkeit-der-implementierung-auf-andere-parser} beschreibt kurz wie sich das dargestellte Verfahren auf andere Sorten von Parsern anwenden ließe.
\subsection{Historischer Überblick}
Bidirektionale, inkrementelle, und kombinierbare Parser und ihre Analyse sind ein vergleichsweise modernes Konzept und stützen sich in weiten Teilen auf vorhergehende Arbeit:
% [x] a programmable editor
% [x] bidirectional tree transformations
% [x] boomerang
% [x] combinator parser
% [ ] ~~delta lenses & optifibrations~~
% [x] edit languages for information trees
% [x] edit lenses
% [x] efficient and flexible incremental parsing
% [x] general incremental lexical analysis
% [ ] ~~incrementel analysis of real programming languages~~
% [x] incremental parsing
% [x] incremental semantic analysis
% [x] lazy functional incremental parsing
% [ ] ~~lenses and bidirectional programs~~
% [ ] ~~parallel inceremntal compilation~~
% [x] parsing in a broad sense
% [ ] polish parsers
% [x] symmetric lenses
% [x] unifying lenses
% [ ] ~~universal updates for symmetric lenses~~
\begin{description} % TODO: more
\item[1979] \cite{ghezzi1979incremental} präsentieren, in einer der ersten Arbeiten zu dem Thema, einen Ansatz zum inkrementellen Parsen von deterministischen und kontextfreien Sprachen basierend auf dem $LR$-Ansatz.
\item[1992] \cite{hedin1992incremental} präsentieren einen Formalismus zur inkrementellen \emph{semantischen} Analyse\footnote{Das Versehen des Syntax-Baums eines Programms mit Attributen wie z.B. Typen} basierend auf (modifizierten) Attribut-Grammatiken.
\item[1997] \cite{wagner1997general} stellen einen Algorithmus zur inkrementellen lexikalischen Analyse (tokenizing) der auf den selben Spezifikationen arbeiten kann wie die UNIX-Tools \texttt{lex} und \texttt{flex}.
\item[1998] \cite{wagner1998efficient} stellen neue Laufzeit- und Speicher-optimale Methoden zur Konstruktion inkrementeller Parser auf Basis beliebiger $LR(k)$-Grammatiken vor.
\item[2001] \cite{swierstra2001combinator} demonstriert den Nutzen Kombinator-basierter Parser-Konstruktion in der Praxis.
\item[2004] \cite{hu2004programmable} spezifizieren eine algebraisch strukturierte Sprache für bidirektionale Baum-Transformationen unter einer programmierbaren Konsistenzrelation mit Blick auf direkte Anwendung im Editieren von bestehenden Baum-Dokumenten.
\item[2007] \cite{foster2007combinators} präsentieren sowohl eine Sprache bidirektionaler Baum-Transformationen als konventionelle funktionale Linsen im Speziellen, als auch mathematische Resultate für funktionale Linsen und Sammlungen dieser im Allgemeinen.
Auch enthalten ist eine nützliche Klassifikation und ein historischer Überblick diverser bidirektionaler Programmiertechniken.
\item[2008] Analog zur Sprache bidirektionaler Baum-Transformation aus \cite{foster2007combinators}, stellen \cite{bohannon2008boomerang} eine Sprache für semi-strukturierten Text als Serie von vertauschbaren Schlüssel-Wert-Assoziationen vor.
\item[2009] \cite{bernardy2009lazy} implementieren, im Rahmen der Arbeit am Text-Editor Yi, eine Kombinator-basierte Programmbibliothek zum inkrementellen Parsen basierend auf lazy evaluation und aggressivem Caching in Haskell.
\item[2011] \cite{hofmann2011symmetric} definieren symmetrische \emph{set-based}-lenses (funktionale Linsen im konventionellen Sinn), d.h. ohne strukturierte edits.
Es wird auch die umfangreiche algebraische Struktur symmetrischer Linsen besprochen.
Vieles hiervon lassen sich direkt auf edit-lenses als Spezialfall symmetrischer Linsen vererben.
\item[2012] \cite{hofmann2012edit} definieren edit-lenses.
In Abgrenzung zu bestehenden Formalismen symmetrischer funktionaler Linsen arbeiten edit-lenses ausschließlich auf algebraisch strukturierten edit-Sprachen, was sie besonders attraktiv macht.
\item[2013] \cite{hofmann2013edit} stellen eine generelle edit-Sprache (zur Verwendung mit und basierend auf edit-lenses) für eine weite Klasse von container-Datentypen (Listen, Bäume, Graphen, ...) vor
\item[2014] \cite{zaytsev2014parsing} geben einen nützlichen Überblick über die historisch inkonsistente Terminologie und Konzepte im Zusammenhang mit Parsing.
\item[2016] \cite{johnson2016unifying} betrachten Zusammenhänge diverser Klassen funktionaler Linsen (inkl. edit-lenses) und geben dabei einen umfangreichen Überblick über die bestehende Forschung.
Ein relevantes Resultat ist hierbei ein Begriff von asymmetrischen edit-lenses kompatibel mit dem symmetrischen Fall.
\end{description}
\subsection{Begriffsverzeichnis}
Obwohl wir detailliertere Definitionen der folgenden Konzepte im Laufe der Arbeit geben, ist es dennoch nützlich vorab die Bedeutung der verwendeten Begriffe kurz anzuschneiden:
\begin{description}
\item[FST] \emph{Finite-State-Transducer} sind endliche Automaten, die bei jedem Zustandsübergang die Möglichkeit haben ein Zeichen an eine sich akkumulierende Ausgabe anzuhängen.
\item[DFST] \emph{Deterministic Finite-State-Transducer} sind FSTs bei denen für jeden Zustand jedes gelesene Zeichen maximal einen Zustandsübergang zulässt.
\item[Monoid] \emph{Monoiden} sind algebraisch zwischen Halbgruppen und Gruppen angesiedelt.
Wir sagen eine Menge hat Monoidstruktur bzgl. einer zweistelligen Verknüpfung auf jener Menge, wenn sie ein neutrales Element enthält und die Verknüpfung assoziativ ist.
\item[Moduln & edits] \emph{Moduln} verknüpfen eine Trägermenge mit einer Menge von \emph{edits} (mit monoidaler Struktur) auf jener Menge.
Edits beschreiben jeweils eine partielle Abbildung innerhalb der Trägermenge.
\item[Funktionale Linsen] Eine \emph{Funktionale Linse} von $s$ in $a$ in der üblichen Definition (\emph{set-based}) ist ein Paar von Abbildungen $\searrow \colon s \to a$ und $\nearrow \colon (a \to a) \to (s \to s)$ mit umfangreicher algebraischer Struktur, die die Komposition komplexer Linsen aus Einfacheren ermöglicht.
Wir finden es hilfreich von einer Projektion ($\searrow$) und einem \emph{edit-Propagator} ($\nearrow$) zu sprechen.
\item[Van-Laarhoven Linsen] In \cite{laarhoven} wurde eine Darstellung als eine über einen Funktor parametrisierte Funktion dargelegt, die unter anderem auch die soeben beschriebenen funktionalen Linsen einbetten kann.
\item[edit-lenses] \emph{edit-lenses} verknüpfen zwei Moduln-Trägermengen indem sie edits des einen Moduls in die des Anderen übersetzen.
Hierbei wird ein, mit den jeweiligen Elementen der Trägermengen konsistenter, unterliegender Zustand, das \emph{Komplement} der edit-lens, gewahrt.
Intuitiv speichert das Komplement genau jene Information, die nicht in beiden Darstellungen vorkommt.
\item[Parser] \emph{Parser} sind Programme, die einen Text (als Liste von Symbolen $\Sigma^\star$ aus einem Alphabet $\Sigma$) Seiteneffekt-frei verarbeiten $\Sigma^\star \to a$.
\item[Inkrementelle Parser] \emph{Inkrementelle Parser} sind Programme, die sowohl in der Lage sind als Parser zu agieren $\Sigma^\star \to a$, als auch, nach einem vorhergehenden konventionellen Parsevorgang, eine Änderung am Eingabetext in eine Änderung am Ergebnis zu übersetzen $\partial \left ( \Sigma^\star \right ) \to \partial a$.
Hierbei muss die Laufzeitcharakteristik i.A. besser sein als die Änderung auf die alte Eingabe anzuwenden und schlichtweg neu zu Parsen.
\end{description}
|
