2018/01/31 by Tony Garnock-Jones, Garnock-Jones, Tony, Mahdi Eslamimehr +3
Computer Science · #FOS: Computer and information sciences #Natural Language Processing Techniques #Programming Languages (cs.PL) #Software Engineering Research #Software Testing and Debugging Techniques
paper · pdf · doi:10.48550/arxiv.1801.10490
openalex publication_date 2018/01/31 · openalex created_date 2018/02/23 · openalex updated_date 2026/07/28
Grammar-based sentence generation has been thoroughly explored for Context-Free Grammars (CFGs), but remains unsolved for recognition-based approaches such as Parsing Expression Grammars (PEGs). Lacking tool support, language designers using PEGs have difficulty predicting the behaviour of their parsers. In this paper, we extend the idea of derivatives, originally formulated for regular expressions, to PEGs. We then present a novel technique for sentence generation based on derivatives, applicable to any grammatical formalism for which the derivative can be defined--now including PEGs. Finally, we propose applying derivatives more generally to other problems facing language designers and implementers.