To be effective, software test generation needs to well cover the space of possible inputs. Traditional \emph{fuzzing} generates large numbers of random inputs, which however are unlikely to contain keywords and other specific inputs of non-trivial input languages. \emph{Constraint-based test generation} solves conditions of paths leading to uncovered code, but fails on programs with complex input conditions because of path explosion.
In this paper, we present a test generation technique specifically directed at \emph{input parsers.} We systematically produce inputs for the parser and track comparisons made; after every rejection, we satisfy the comparisons leading to rejection. This approach effectively covers the input space: Evaluated on five subjects, from CSV files to JavaScript, our \textsc{pFuzzer} prototype covers more tokens than both random-based and constraint-based approaches, while requiring no symbolic analysis and far fewer tests than random fuzzers.