On the relation between context-free grammars and parsing expression grammars

Medeiros, Sérgio Queiroz de; Mascarenhas, Fabio; Roberto Ierusalimschy, Natural semantics

On the relation between context-free grammars and parsing expression grammars

Página do item simplificado Estatísticas

dc.contributor.author	Medeiros, Sérgio Queiroz de
dc.contributor.author	Mascarenhas, Fabio
dc.contributor.author	Roberto Ierusalimschy, Natural semantics
dc.date.accessioned	2020-12-07T20:07:42Z
dc.date.available	2020-12-07T20:07:42Z
dc.date.issued	2014-09-01
dc.description.resumo	Context-Free Grammars (CFGs) and Parsing Expression Grammars (PEGs) have several similarities and a few differences in both their syntax and semantics, but they are usually presented through formalisms that hinder a proper comparison. In this paper we present a new formalism for CFGs that highlights the similarities and differences between them. The new formalism borrows from PEGs the use of parsing expressions and the recognition-based semantics. We show how one way of removing non-determinism from this formalism yields a formalism with the semantics of PEGs. We also prove, based on these new formalisms, how LL(1) grammars define the same language whether interpreted as CFGs or as PEGs, and also show how strong-LL(k), right-linear, and LL-regular grammars have simple language-preserving translations from CFGs to PEGs. Once these classes of CFGs can be automatically translated to equivalent PEGs, we can reuse classic top-down grammars in PEG-based tools	pt_BR
dc.identifier.citation	MASCARENHAS, Fabio; MEDEIROS, Sérgio; IERUSALIMSCHY, Roberto. On the relation between context-free grammars and parsing expression grammars. Science Of Computer Programming, [S.L.], v. 89, p. 235-250, set. 2014. Disponível em: https://www.sciencedirect.com/science/article/pii/S0167642314000276?via%3Dihub. Acesso em: 06 out. 2020. http://dx.doi.org/10.1016/j.scico.2014.01.012.	pt_BR
dc.identifier.doi	10.1016/j.scico.2014.01.012
dc.identifier.issn	0167-6423
dc.identifier.uri	https://repositorio.ufrn.br/handle/123456789/30875
dc.language	en	pt_BR
dc.publisher	Elsevier	pt_BR
dc.rights	Attribution 3.0 Brazil	*
dc.rights.uri	http://creativecommons.org/licenses/by/3.0/br/	*
dc.subject	Context-free grammars	pt_BR
dc.subject	Parsing expression grammars	pt_BR
dc.subject	LL(1)	pt_BR
dc.subject	LL(k)	pt_BR
dc.subject	Natural semantics	pt_BR
dc.title	On the relation between context-free grammars and parsing expression grammars	pt_BR
dc.type	article	pt_BR