BOHEMIA – A VALIDATOR FOR PARSER FRAMEWORKS

Open Access
Author:
Paranjpe, Anish
Graduate Program:
Computer Science
Degree:
Master of Science
Document Type:
Master Thesis
Date of Defense:
March 25, 2019
Committee Members:
  • Gang Tan, Thesis Advisor
Keywords:
  • Parser
  • Fuzzy Testing
  • Equivalence Modulo Inputs
Abstract:
Parsing is ubiquitous in different software projects, ranging from small command-line utilities, highly secure network clients to large compilers. A wide range of parsing algorithms provides programmer with a plethora of parser libraries to choose from. However, all widely known parsing libraries and other small parser projects fail to provide user the guarantee that the library is bug free, meaning the parsing output for the provided input grammar is as expected for all possible grammars. In this thesis we describe a framework that a parser library developer can rely upon as an integration test suite. The framework makes use of the concept of Equivalence Modulo Inputs in order to generate large scale of input grammars to stress-test the parser library. We also describe the result of evaluation of the framework against different parsing libraries across a variety of programming languages, utilizing distinct parsing algorithms.