[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. / [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.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:16821 |
| Date | 31 January 2011 |
| Creators | SERGIO QUEIROZ DE MEDEIROS |
| Contributors | ROBERTO IERUSALIMSCHY |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.0023 seconds