[Colloquium] Riehl/M.S. Presentation/May 5, 2004

[Margaret Jaffey]

This is an announcement for Jonathan Riehl's Master's Presentation.

---------------------
Date:  Wednesday, May 5, 2004

Time:  2:30 p.m.

Place:  Ryerson 251

M.S. Candidate:  Jonathan Riehl

M.S. Paper Title:  Grammar Based Unit Testing for Parsers

Abstract:
White box unit testing is the use of test inputs, derived from source
code, to drive code coverage.  While approaches based on control flow
analysis exist for generating unit test inputs, these approaches are
not readily applied to code that embeds control flow as static data.
One specific example of such codes are the state machines built by
parser generators.  Control flow in these machine abstractions is
based on static data that encodes a set of state transition rules.
However, these rules also correspond to the recognition of productions
in the grammar input to the parser generator.  It is therefore
feasible to develop white box tests for a parser based on an analysis
of the input grammar.

Using the structure of grammars, a methodology for white box unit
testing a parser has been developed and will be presented in this
thesis.  Furthermore, a tool set that assists in automation of test
generation will be described.  This tool set is based on the use of a
language grammar to create grammatical strings in that language.  It
will be shown how the set of strings in a language may be navigated in
a principled fashion for the purpose of spanning the set of all
language productions, and heuristics developed for resolving
nonterminal symbols into strings of terminal symbols.  A demonstration
of how these tools were used to test a simple parser for the C
programming language will also be given.

Advisor:  Prof. David Beazley

A draft copy of Jonathan Riehl's MS Paper will be available shortly in 
Ry 161A.
-- 
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Margaret P. Jaffey				margaret at cs.uchicago.edu
Department of Computer Science
Student Support Rep (Ry 161A)		(773) 702-6011
The University of Chicago		http://www.cs.uchicago.edu
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-