Hardware-Accelerated PEG Parsing Machine

Hardware-Accelerated PEG Parsing Machine

Bakker, Roy (TU Delft Electrical Engineering, Mathematics and Computer Science; TU Delft Computer Engineering)

Wong, J.S.S.M. (mentor)
Wiersma, Ard (mentor)
Poulsen, C.B. (graduation committee)

Delft University of Technology

Computer Engineering

2022-09-29

Information exchange through the countless webservices is central in the current age of technology, which increases the importance for security in these developments. One such security feature is the validation of data based on standardized data structures. The aim of this thesis is to develop a flexible hardware-accelerated text-based recognizer that provides this strict syntax validation.

To this end, a parsing machine architecture was adopted in order to fulfill the flexibility and strict recognition requirements. The parsing machine architecture was developed by formalizing the fundamental PEG expressions and creating a micro-architecture based on these PEG expressions, which led to the specification of the PPEG instruction set architecture. This architecture was then mathematically formalized and a proof for its strict adherence to the formalized PEG behavior was provided. The parsing machine architecture was implemented on an FPGA, a virtualization of the parsing machine was implemented in Python for easy analysis of its behavior, and a PEG compiler and assembler were developed for the PEG-PPEG translation. Finally, a memoization unit was developed as an extension to the parsing machine for an improved parsing throughput.

By running benchmarks for CSV, XML, JSON, and Java files on the PPEG parsing machine implementation, its parsing behavior was analyzed and compared to existing solutions. This showed that the minimum stack sizes depend solely on the size and complexity of the PEG; the percentage of clock cycles spent on jumps in instruction and data memory is substantial, ranging from 18\% and 40\%; the PPEG-compiled binary code size is relatively small compared to other solutions; and the throughput of the PPEG parsing machine is comparable if not better than other solutions running on faster hardware. Finally, the memoization unit was found to benefit large complex grammars more than small grammars.

Parsing
Parsing Expression Grammar
PEG
PPEG
Parsing Machine
FPGA

http://resolver.tudelft.nl/uuid:5acb18fc-b412-40da-8472-9bf7a02730ab

Student theses

master thesis

© 2022 Roy Bakker