Ad Hoc Syntax-Guided Program Reduction

Program reduction is a widely adopted, indispensable technique for debugging language implementations such as compilers and interpreters. Given a program and a bug triggered by , a program reducer can produce a minimized program - that is derived from and still triggers the same bug. Perses is one of the state-of-the-art program reducers. It leverages the syntax of to guide the reduction process for efficiency and effectiveness. It is language-agnostic as its reduction algorithm is independent of any language-specific syntax. Conceptually to support a new language, Perses only needs the context-free grammar of the language; in practice, it is not easy. One needs to first manually transform into a special grammar form PNF with a tool provided by Perses, second manually change the code base of Perses to integrate the new language, and lastly build a binary of Perses. This paper presents our latest work to improve the usability of Perses by extending Perses to perform ad hoc program reduction for any new language as long as the language has a context-free grammar . With this extended version (referred to as Perses^adhoc), the difficulty of supporting new languages is significantly reduced: a user only needs to write a configuration file and execute one command to support a new language in Perses, compared to manually transforming the grammar format, modifying the code base, and re-building Perses. Our case study demonstrates that with Perses^adhoc, the Perses related infrastructure code required for supporting GLSL can be reduced from 190 lines of code to 20. Our extensive evaluations also show that Perses^adhoc is as effective and efficient as Perses in reducing hoc programs, and only takes 10 seconds to support a new language, which is negligible compared to the manual effort required in Perses. A video demonstration of the tool can be found at https://youtu.be/trYwOT0mXhU.