- About
-
The Global ETD Search service is a free service for researchers
to find electronic theses and dissertations. This service is
provided by the
Networked Digital Library of Theses and Dissertations.
Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
Search results
Showing 1 to 3 of 3 (0.1 seconds)Spelling suggestions: "subject:"parsing expression grammar""
| 1 |
[en] CORRESPONDENCE BETWEEN PEGS AND CLASSES OF CONTEXT-FREE GRAMMARS / [pt] CORRESPONDÊNCIA ENTRE PEGS E CLASSES DE GRAMÁTICAS LIVRES DE CONTEXTOSERGIO QUEIROZ DE MEDEIROS 31 January 2011 (has links)
[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.
|
| 2 |
Well-Formed and Scalable Invasive Software Composition / Wohlgeformte und Skalierbare Invasive SoftwarekompositionKarol, Sven 26 June 2015 (has links) (PDF)
Software components provide essential means to structure and organize software effectively. However, frequently, required component abstractions are not available in a programming language or system, or are not adequately combinable with each other. Invasive software composition (ISC) is a general approach to software composition that unifies component-like abstractions such as templates, aspects and macros. ISC is based on fragment composition, and composes programs and other software artifacts at the level of syntax trees. Therefore, a unifying fragment component model is related to the context-free grammar of a language to identify extension and variation points in syntax trees as well as valid component types. By doing so, fragment components can be composed by transformations at respective extension and variation points so that always valid composition results regarding the underlying context-free grammar are yielded. However, given a language’s context-free grammar, the composition result may still be incorrect.
Context-sensitive constraints such as type constraints may be violated so that the program cannot be compiled and/or interpreted correctly. While a compiler can detect such errors after composition, it is difficult to relate them back to the original transformation step in the composition system, especially in the case of complex compositions with several hundreds of such steps. To tackle this problem, this thesis proposes well-formed ISC—an extension to ISC that uses reference attribute grammars (RAGs) to specify fragment component models and fragment contracts to guard compositions with context-sensitive constraints. Additionally, well-formed ISC provides composition strategies as a means to configure composition algorithms and handle interferences between composition steps.
Developing ISC systems for complex languages such as programming languages is a complex undertaking. Composition-system developers need to supply or develop adequate language and parser specifications that can be processed by an ISC composition engine. Moreover, the specifications may need to be extended with rules for the intended composition abstractions.
Current approaches to ISC require complete grammars to be able to compose fragments in the respective languages. Hence, the specifications need to be developed exhaustively before any component model can be supplied. To tackle this problem, this thesis introduces scalable ISC—a variant of ISC that uses island component models as a means to define component models for partially specified languages while still the whole language is supported. Additionally, a scalable workflow for agile composition-system development is proposed which supports a development of ISC systems in small increments using modular extensions.
All theoretical concepts introduced in this thesis are implemented in the Skeletons and Application Templates framework SkAT. It supports “classic”, well-formed and scalable ISC by leveraging RAGs as its main specification and implementation language. Moreover, several composition systems based on SkAT are discussed, e.g., a well-formed composition system for Java and a C preprocessor-like macro language. In turn, those composition systems are used as composers in several example applications such as a library of parallel algorithmic skeletons.
|
| 3 |
Well-Formed and Scalable Invasive Software CompositionKarol, Sven 18 May 2015 (has links)
Software components provide essential means to structure and organize software effectively. However, frequently, required component abstractions are not available in a programming language or system, or are not adequately combinable with each other. Invasive software composition (ISC) is a general approach to software composition that unifies component-like abstractions such as templates, aspects and macros. ISC is based on fragment composition, and composes programs and other software artifacts at the level of syntax trees. Therefore, a unifying fragment component model is related to the context-free grammar of a language to identify extension and variation points in syntax trees as well as valid component types. By doing so, fragment components can be composed by transformations at respective extension and variation points so that always valid composition results regarding the underlying context-free grammar are yielded. However, given a language’s context-free grammar, the composition result may still be incorrect.
Context-sensitive constraints such as type constraints may be violated so that the program cannot be compiled and/or interpreted correctly. While a compiler can detect such errors after composition, it is difficult to relate them back to the original transformation step in the composition system, especially in the case of complex compositions with several hundreds of such steps. To tackle this problem, this thesis proposes well-formed ISC—an extension to ISC that uses reference attribute grammars (RAGs) to specify fragment component models and fragment contracts to guard compositions with context-sensitive constraints. Additionally, well-formed ISC provides composition strategies as a means to configure composition algorithms and handle interferences between composition steps.
Developing ISC systems for complex languages such as programming languages is a complex undertaking. Composition-system developers need to supply or develop adequate language and parser specifications that can be processed by an ISC composition engine. Moreover, the specifications may need to be extended with rules for the intended composition abstractions.
Current approaches to ISC require complete grammars to be able to compose fragments in the respective languages. Hence, the specifications need to be developed exhaustively before any component model can be supplied. To tackle this problem, this thesis introduces scalable ISC—a variant of ISC that uses island component models as a means to define component models for partially specified languages while still the whole language is supported. Additionally, a scalable workflow for agile composition-system development is proposed which supports a development of ISC systems in small increments using modular extensions.
All theoretical concepts introduced in this thesis are implemented in the Skeletons and Application Templates framework SkAT. It supports “classic”, well-formed and scalable ISC by leveraging RAGs as its main specification and implementation language. Moreover, several composition systems based on SkAT are discussed, e.g., a well-formed composition system for Java and a C preprocessor-like macro language. In turn, those composition systems are used as composers in several example applications such as a library of parallel algorithmic skeletons.
|
Page generated in 0.1062 seconds