Detailansicht
Dynamic generalized parsing and natural mathematical language
Kevin Kofler
Art der Arbeit
Dissertation
Universität
Universität Wien
Fakultät
Fakultät für Mathematik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Dr.-Studium der Naturwissenschaften Mathematik
Betreuer*in
Arnold Neumaier
DOI
10.25365/thesis.48835
URN
urn:nbn:at:at-ubw:1-22774.60262.698452-1
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Diese Dissertation stellt den dynamischen verallgemeinerten Parser DynGenPar und
seine Anwendungen vor. Der Parser zielt hauptsächlich auf natürliche
mathematische Sprache ab. Er wurde auch erfolgreich für mehrere formale Sprachen
verwendet.
Die Dissertation präsentiert die algorithmischen Ideen hinter DynGenPar, gibt
eine kurze Übersicht über die Implementierung, dokumentiert die Applikationen,
für die der Parser derzeit verwendet wird, und präsentiert einige
Effizienzergebnisse. Teile dieser Dissertation, vor allem in Kapitel 2,
basieren auf dem referierten Konferenzartikel K. Kofler and A. Neumaier:
DynGenPar – A Dynamic Generalized Parser for Common Mathematical Language.
Proceedings of CICM/DML 2012 (Springer LNAI 7362), 2012.
Der DynGenPar-Algorithmus kombiniert die Effizienz verallgemeinerten LR-Parsens
(GLR), die dynamische Erweiterbarkeit tabellenloser Ansätze, sowie die
Ausdrucksstärke erweiteter kontextfreier Grammatiken wie paralleler mehrfacher
kontextfreier Grammatiken (PMCFG). Insbesondere unterstützt er das effiziente
Hinzufügen von Regeln zur Grammatik zu jedem Zeitpunkt. Der Algorithmus ist
komplett inkrementell konzipiert, erlaubt also, einen unterbrochenen
Parsingvorgang mit zusätzlichen Tokens fortzusetzen, ohne den Parsingvorgang neu
zu starten, und kann mögliche nächste Tokens vorhersagen. Zusätzlich behandelt
er vorgegebene Einschränkungen (constraints) für den auf eine Regel folgenden
Token. Diese erlauben grammatikalisch korrekte englische indefinite Artikel,
wenn mit Wörtern als Tokens gearbeitet wird. Sie können auch typische
Operationen für scannerloses Parsen wie etwa das Finden einer Übereinstimmung
maximaler Länge (maximales Matchen) darstellen, wenn mit Zeichen als Tokens
gearbeitet wird.
Mehrere erfolgreiche Anwendungen von DynGenPar sind in dieser Dissertation
dokumentiert. DynGenPar ist eine Kernkomponente des Concise-Projekts, eines
Frameworks zum Manipulieren semantischer Information sowohl in graphischer als
auch in programmatischer Form, entwickelt an der Universität Wien. DynGenPar
wird verwendet, um die von Concise definierten formalen Sprachen zu parsen, die
Typsysteme, Programme, sowie Recordumwandlungen von einem Typsystem in ein
anderes spezifizieren. Andere formale Sprachen mit einer DynGenPar-Grammatik
sind eine Modellierungssprache für chemische Prozesse, eine als
Machbarkeitsbeweis dienende, dynamisches Hinzufügen von Regeln verwendende
Grammatik für Optimierungsprobleme, sowie eine Teilmenge der
Modellierungssprache für Optimierungsprobleme AMPL, erweitert, um auch
Intervalle zu erlauben, wo immer AMPL eine Zahl erwartet. DynGenPar kann
kompilierte Grammatiken des Grammatical Framework (GF) importieren und Text mit
ihnen parsen. Eine DynGenPar-Grammatik existiert auch für die kontrollierte
natürliche mathematische Sprache Naproche. Die Benutzung dynamischem Hinzufügens
von Regeln, um mathematische Definitionen zu unterstützen, wurde in einer
Grammatik als Machbarkeitsbeweis implementiert. Eine Grammatik für die
kontrollierte natürliche mathematische Sprache MathNat ist in Arbeit.
Schließlich gibt es auch eine gut funktionierende DynGenPar-Grammatik für
LaTeX-Formeln aus zwei Mathematik-Textbüchern auf Universitätsniveau. Das
langfristige Ziel ist, eine große Bibliothek bestehenden mathematischen Wissens
mittels DynGenPar zu computerisieren.
Abstract
(Englisch)
This thesis introduces the dynamic generalized parser DynGenPar and its
applications. The parser is aimed primarily at natural mathematical language.
It was also successfully used for several formal languages. DynGenPar is
available at https://www.tigen.org/kevin.kofler/fmathl/dyngenpar/ .
The thesis presents the algorithmic ideas behind DynGenPar, gives a short
overview of the implementation, documents the applications the parser is
currently used for, and presents some efficiency results. Parts of this thesis,
mainly in Chapter 2, are based on the refereed conference paper K. Kofler and
A. Neumaier: DynGenPar – A Dynamic Generalized Parser for Common Mathematical
Language. Proceedings of CICM/DML 2012 (Springer LNAI 7362), 2012.
The DynGenPar algorithm combines the efficiency of Generalized LR (GLR) parsing,
the dynamic extensibility of tableless approaches, and the expressiveness of
extended context-free grammars such as parallel multiple context-free grammars
(PMCFGs). In particular, it supports efficient dynamic rule additions to the
grammar at any moment. The algorithm is designed in a fully incremental way,
allowing to resume parsing with additional tokens without restarting the parse
process, and can predict possible next tokens. Additionally, it handles
constraints on the token following a rule. These allow for grammatically correct
English indefinite articles when working with word tokens. They can also
represent typical operations for scannerless parsing such as maximal matches
when working with character tokens.
Several successful applications of DynGenPar are documented in this thesis.
DynGenPar is a core component of the Concise project, a framework for
manipulating semantic information both graphically and programmatically,
developed at the University of Vienna. DynGenPar is used to parse the formal
languages defined by Concise, specifying type systems, programs, and record
transformations from one type system to another. Other formal languages with a
DynGenPar grammar are a modeling language for chemical processes, a
proof-of-concept grammar for optimization problems using dynamic rule additions,
and a subset of the AMPL modeling language for optimization problems, extended
to also allow intervals wherever AMPL expects a number. DynGenPar can import
compiled grammars from the Grammatical Framework (GF) and parse text using them.
A DynGenPar grammar also exists for the controlled natural mathematical language
Naproche. The use of dynamic rule additions to support mathematical definitions
was implemented in a grammar as a proof of concept. There is work in progress on
a grammar for the controlled natural mathematical language MathNat. Finally,
there is also a well-working DynGenPar grammar for LaTeX formulas from two
university-level mathematics textbooks. The long-term goal is to computerize a
large library of existing mathematical knowledge using DynGenPar.
Schlagwörter
Schlagwörter
(Englisch)
dynamic generalized parser dynamic parser tableless parser scannerless parser parser parallel multiple context-free grammars common mathematical language natural mathematical language controlled natural language mathematical knowledge management formalized mathematics digital mathematical library
Schlagwörter
(Deutsch)
dynamischer verallgemeinerter Parser dynamischer Parser tabellenloser Parser scannerloser Parser Parser parallele mehrfache kontextfreie Grammatiken gewöhnliche mathematische Sprache natürliche mathematische Sprache kontrollierte natürliche Sprache mathematische Wissensverwaltung formalisierte Mathematik digitale mathematische Bibliothek
Autor*innen
Kevin Kofler
Haupttitel (Englisch)
Dynamic generalized parsing and natural mathematical language
Paralleltitel (Deutsch)
Dynamisches verallgemeinertes Parsing und natürliche mathematische Sprache
Publikationsjahr
2017
Umfangsangabe
200 Seiten : Illustrationen, Diagramme
Sprache
Englisch
Beurteiler*innen
Aarne Ranta ,
Michael Kohlhase
AC Nummer
AC15002232
Utheses ID
43156
Studienkennzahl
UA | 091 | 405 | |