arXiv:1210.4992cs.FL
From Regexes to Parsing Expression Grammars
Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.
Abstract
Most scripting languages nowadays use regex pattern-matching libraries. These regex libraries borrow the syntax of regular expressions, but have an informal semantics that is different from the semantics of regular expressions, removing the commutativity of alternation and adding ad-hoc extensions that cannot be expressed by formalisms for efficient recognition of regular languages, such as deterministic finite automata. Parsing Expression Grammars are a formalism that can describe all deterministic context-free languages and has a simple computational model. In this paper, we present a formalization of regexes via transformation to Parsing Expression Grammars. The proposed transformation easily accommodates several of the common regex extensions, giving a formal meaning to them. It also provides a clear computational model that helps to estimate the efficiency of regex-based matchers, and a basis for specifying provably correct optimizations for them.
> Which makes me wonder: what’s the appeal of PEGs or parser generators now? I just had the robots write a PEG parser generator... Which can do analysis on the grammars which, I suspect, a hand (or LLM) written one can't do so you don't end up chasing infinite recursion, dead…
UncleEntityView on HNParent context