  This paper introduces a new derivative parsing algorithm for recognition of
parsing expression grammars. Derivative parsing is shown to have a polynomial
worst-case time bound, an improvement on the exponential bound of the recursive
descent algorithm. This work also introduces asymptotic analysis based on
inputs with a constant bound on both grammar nesting depth and number of
backtracking choices; derivative and recursive descent parsing are shown to run
in linear time and constant space on this useful class of inputs, with both the
theoretical bounds and the reasonability of the input class validated
empirically. This common-case constant memory usage of derivative parsing is an
improvement on the linear space required by the packrat algorithm.
