Zur Seitenansicht
 

Titelaufnahme

Titel
An ECMAScript 2015-Compliant Automata-based Regular Expression Engine for Graal.js / submitted by Josef Haider
AutorInnenHaider, Josef
Beurteiler / BeurteilerinMössenböck, Hanspeter
ErschienenLinz, 2018
Umfang49 Seiten : Illustrationen
HochschulschriftUniversität Linz, Masterarbeit, 2018
SpracheEnglisch
DokumenttypMasterarbeit
Schlagwörter (DE)reguläre Ausdrücke / endliche Automaten
Schlagwörter (EN)regular expressions / regular expression engine / finite automata
URNurn:nbn:at:at-ubl:1-24940 Persistent Identifier (URN)
Zugriffsbeschränkung
 Das Werk ist gemäß den "Hinweisen für BenützerInnen" verfügbar
Dateien
An ECMAScript 2015-Compliant Automata-based Regular Expression Engine for Graal.js [0.54 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

Reguläre Ausdrücke sind ein gängiges Werkzeug zur Suche von Mustern in Text, das in vielen Programmiersprachen standardmäßig unterstützt wird. Ihre Flexibilität und beliebige Komplexität macht die Implementierung einer schnellen Regular Expression Engine zu einer Herausforderung. Diese Arbeit beschreibt TRegex, eine Automaten-basierte, ECMAScript2015-konforme Regular Expression Engine, die auf dem Truffle Language Framework basiert und zur gemeinsamen Verwendung mit dem Graal Compiler gedacht ist. TRegex bildet reguläre Ausdrücke auf nicht-deterministische endliche Automaten ab, die in weiterer Folge mittels Potenzmengen-Konstruktion zu deterministischen endlichen Automaten transformiert werden, welche wiederum zur Suche nach Übereinstimmungen mit dem Ausdruck genutzt werden. Diese (Potenzmengen-/Power-Set-) Automaten-basierte Herangehensweise nimmt lange Kompilier-zeiten und hohen Speicherverbrauch für höhere Leistung in Kauf, und zeigt im Test vielversprechende Ergebnisse: TRegex ist im Durchschnitt vier mal schneller als sein Vorgänger Joni, und konnte 98% von über 200.000 Ausdrücken in einem aus NPM extrahierten Abdeckungs-Test-Set korrekt verarbeiten.

Zusammenfassung (Englisch)

Regular expressions are a commonly used pattern matching tool present in the core libraries of many programming languages. Their great flexibility and arbitrary complexity makes writing well-performing regular expression engines a challenge. This thesis presents TRegex, an automata-based ECMAScript2015-compliant regular expression engine implemented on top of the Truffle language framework and tailored to be used in conjunction with the Graal compiler. TRegex maps regular expressions to non-deterministic finite automata, which are transformed to deterministic finite automata by power-set construction. The deterministic automata are used for regular expression matching. This (power-set) automaton-based approach sacrifices compilation time and memory usage for performance, and shows promising results during evaluation: TRegex is on average four times faster than its predecessor Joni, and was able to correctly handle 98% of a completeness test set of over 200.000 regular expressions extracted from NPM.

Statistik
Das PDF-Dokument wurde 7 mal heruntergeladen.