Go to page
 

Bibliographic Metadata

Title
An ECMAScript 2015-Compliant Automata-based Regular Expression Engine for Graal.js / submitted by Josef Haider
AuthorHaider, Josef
CensorMössenböck, Hanspeter
PublishedLinz, 2018
Description49 Seiten : Illustrationen
Institutional NoteUniversität Linz, Masterarbeit, 2018
LanguageEnglish
Document typeMaster Thesis
Keywords (DE)reguläre Ausdrücke / endliche Automaten
Keywords (EN)regular expressions / regular expression engine / finite automata
URNurn:nbn:at:at-ubl:1-24940 Persistent Identifier (URN)
Restriction-Information
 The work is publicly available
Files
An ECMAScript 2015-Compliant Automata-based Regular Expression Engine for Graal.js [0.54 mb]
Links
Reference
Classification
Abstract (German)

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.

Abstract (English)

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.

Stats
The PDF-Document has been downloaded 10 times.