2014/05/31 by Aaron Moss
Computer Science · #Algorithm #Algorithms and Data Compression #Artificial intelligence #Backtracking #Bottom-up parsing #Computer science #Constant (computer programming) #Context-free grammar #Derivative (finance) #L-attributed grammar #Natural Language Processing Techniques #Parsing #Parsing expression grammar #Programming language #Theoretical computer science #Top-down parsing #cs.FL #semigroups and automata theory
paper · pdf · doi:10.4204/eptcs.252.18
published as EPTCS 252, 2017, pp. 180-194 · In Proceedings AFL 2017, arXiv:1708.06226
openalex publication_date 2017/08/21 · arxiv created 2017/08/22 · arxiv updated 2017/08/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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.