Título
[en] CORRESPONDENCE BETWEEN PEGS AND CLASSES OF CONTEXT-FREE GRAMMARS
Título
[pt] CORRESPONDÊNCIA ENTRE PEGS E CLASSES DE GRAMÁTICAS LIVRES DE CONTEXTO
Autor
[pt] SERGIO QUEIROZ DE MEDEIROS
Vocabulário
[pt] INFORMATICA
Vocabulário
[pt] GRAMATICAS LIVRES DE CONTEXTO
Vocabulário
[pt] GRAMATICAS DE EXPRESSOES DE PARSING
Vocabulário
[pt] LINGUAGENS DE PROGRAMACAO
Vocabulário
[en] COMPUTER SCIENCE
Vocabulário
[en] CONTEXT-FREE GRAMMARS
Vocabulário
[en] PARSING EXPRESSION GRAMMARS
Vocabulário
[en] PROGRAMMING LANGUAGES
Resumo
[pt] Gramáticas de Expressões de Parsing (PEGs) são um formalismo que
permite descrever linguagens e que possui como característica distintiva
o uso de um operador de escolha ordenada. A classe de linguagens descrita
por PEGs contém propriamente todas as linguagens livres de contexto determinísticas. Nesta tese discutimos a correspondência de PEGs com dois
outros formalismos usados para descrever linguagens: expressões regulares
e Gramáticas Livres de Contexto (CFGs). Apresentamos uma formalização
de expressões regulares usando semântica natural e mostramos uma transformação
para converter expressões regulares em PEGs que descrevem a
mesma linguagem; essa transformação pode ser facilmente adaptada para
acomodar diversas extensões usadas por bibliotecas de expressões regulares
(e.g., repetição preguiçosa e subpadrões independentes). Também apresentamos
uma nova formalização de CFGs usando semântica natural e
mostramos a correspondência entre CFGs lineares à direita e PEGs equivalentes.
Além disso, mostramos que gramáticas LL(1) com uma pequena
restrição descrevem a mesma linguagem quando interpretadas como CFGs
e quando interpretadas como PEGs. Por fim, mostramos como transformar
CFGs LL(k)-forte em PEGs equivalentes.
Resumo
[en] Parsing Expression Grammars (PEGs) are a formalism that allow us to
describe languages and that has as its distinguishing feature the use of
an ordered choice operator. The class of languages described by PEGs
properly contains all deterministic context-free languages. In this thesis
we discuss the correspondence between PEGs and two other formalisms
used to describe languages: regular expressions and Context-Free Grammars
(CFGs). We present a new formalization of regular expressions that uses
natural semantics and we show a transformation to convert a regular
expression into a PEG that describes the same language; this transformation
can be easily adapted to accommodate several extensions used by regular
expression libraries (e.g., lazy repetition and independent subpatterns). We
also present a new formalization of CFGs that uses natural semantics and we
show the correspondence between right linear CFGs and equivalent PEGs.
Moreover, we show that LL(1) grammars with a minor restriction define the
same language when interpreted as a CFG and when interpreted as a PEG.
Finally, we show how to transform strong-LL(k) CFGs into PEGs that are
equivalent.
Orientador(es)
ROBERTO IERUSALIMSCHY
Banca
ROBERTO IERUSALIMSCHY
Banca
NOEMI DE LA ROCQUE RODRIGUEZ
Banca
EDWARD HERMANN HAEUSLER
Banca
ANAMARIA MARTINS MOREIRA
Banca
ALEX DE VASCONCELLOS GARCIA
Catalogação
2011-01-31
Apresentação
2010-08-18
Tipo
[pt] TEXTO
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Idioma(s)
PORTUGUÊS
Referência [pt]
https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=16821@1
Referência [en]
https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=16821@2
Referência DOI
https://doi.org/10.17771/PUCRio.acad.16821
Arquivos do conteúdo
CAPA, AGRADECIMENTOS, RESUMO, ABSTRACT, SUMÁRIO E LISTAS PDF CAPÍTULO 1 PDF CAPÍTULO 2 PDF CAPÍTULO 3 PDF CAPÍTULO 4 PDF CAPÍTULO 5 PDF REFERÊNCIAS BIBLIOGRÁFICAS PDF