Sergio Medeiros, Fabio Mascarenhas, Roberto Ierusalimschy.
Regular expressions are a formalism for expressing regular languages. Regex pattern matching libraries borrow the syntax of regular expressions, but introduce ad-hoc extensions that cannot be expressed within the regular expression formalism, and whose efficiency is difficult to estimate. PEGs are a formalism that can describe all deterministic context-free languages and that has a simple computational model. We present a new formalization of regular expressions via transformation to PEGs, and show that this formalization easily accommodates some of the extensions, and helps estimate the efficiency of expressions.
http://www.lbd.dcc.ufmg.br/colecoes/sblp/2011/001.pdfCaso o link acima esteja inválido, faça uma busca pelo texto completo na Web: Buscar na Web