[pt] Expressões regulares são um formalismo utilizado para descrever linguagens regulares e compõem a base de diversas bibliotecas de casamento de padrão. No entanto, existem determinados padrões úteis que são complexos ou impossíveis de serem descritos com expressões regulares puras. Devido a essas limitações, linguagens de script modernas disponibilizam bibliotecas de casamento de padrões baseadas em regexes, isto é, extensões de expressões regulares compostas, principalmente, por construções ad-hoc que focam em problemas específicos. Apesar de serem muito úteis na prática, os regexes possuem implementações complexas e distantes do formalismo original de expressões regulares. Parsing Expression Grammars (PEG) são uma alternativa formal para reconhecer padrões e possuem mais expressividade que expressões regulares sem necessitar de contruções ad-hoc. O objetivo deste trabalho é estudar formas de conversão de regexes para PEGs. Para isso, estudamos as implementações atuais de regexes e mostramos a conversão de algumas construções para PEGs. Por fim, apresentamos uma implementação da conversão de regexes para PEGs para a linguagem Lua. / [en] Regular expressions are a formalism used to describe regular languages and form the basis of several pattern-matching libraries. However, many interesting patterns either are difficult to describe or cannot be described by pure regular expressions. Because of these limitations, modern scripting languages have pattern matching libraries based on regexes, ie, extensions of regular expressions mainly composed by a set of ad-hoc constructions that focus on specific problems. Although very useful in practice, these implementations are complex and distant from the original formalism of regular expressions. Parsing Expression Grammars (PEG) are a formal alternative to recognize patterns and it is much more expressive than pure regular expressions and does not need use ad-hoc constructions. The goal of this work is to study the convertion of regexes to PEGs. To accomplish this task, we studied the current implementations of regexes and show how to convert some constructions to PEGs. Finally, we present an implementation that convert regexes to PEGs for the Lua language.

[pt] Um cenário comum atualmente é o de aplicações desenvolvidas usando duas linguagens de programação a fim de otimizar partes onde o desempenho é crítico e permitir extensibilidade através de scripts escritos pelo usuário. Há várias formas de se obter esse tipo de interoperabilidade; idealmente, entretanto, uma linguagem deve prover uma interface de acesso externo (foreign language interface, FLI) que permita ao programador receber e enviar tanto chamadas como dados para outra linguagem. Este trabalho discute as principais questões envolvendo o projeto de APIs para integração de ambientes de execução de linguagens em aplicações C. Apresentamos os principais problemas enfrentados na interação entre código executando em um ambiente com características inerentemente dinâmicas como o de uma linguagem de script com código C. Comparamos aqui as abordagens empregadas por cinco linguagens no tratamento da comunicação entre os espaços de dados de C e do ambiente de execução embutido e as conseqüências destas abordagens no gerenciamento de memória, bem como no compartilhamento de código entre a aplicação C e o da linguagem de script. Ilustramos as diferenças das APIs destas linguagens e o impacto destas no código resultante de uma aplicação C através de um estudo de caso. Diferentes linguagens de script são embutidas como plugins de uma mesma biblioteca, que por sua vez expõe a aplicações clientes uma API genérica de scripting. Assim, o código de cada plugin permite observar de forma clara e isolada os procedimentos adotados em cada linguagem para chamada de funções, registro de funçoes C e conversão de dados entre os ambientes. / [en] Applications written in two programming languages, in order to optimize parts where performance is critical or to obtain extensibility through userwritten scripts, are commonplace nowadays. There are several ways to obtain this kind of interoperability; ideally, however, a language should provide a foreign language interface (FLI), allowing the programmer to send and receive both data and function calls to the external language. This work discusses the main issues involving the design of APIs for the integration of language environments within C applications. We present the main problems faced in the interaction between code executed in an environment with inherently dynamic characteristics such as a scripting language and C code. We compare the approaches employed by five languages when handling communication between the data spaces of C and the embedded runtime environment and the consequences of these approaches in memory management, as well as sharing of code between the C application and that from the scripting language. We illustrate the differences of the APIs of those languages and their impact in the resulting code of a C application through a case study. Different scripting languages were embedded as plugins for a library, which on its turn exposes to client applications a generic scripting API. This way, the code of each plugin allows us to observe in a clear and isolated way the procedures adopted by each language for function calls, registration of C functions and conversion of data between the environments.

[pt] Muitas aplicações são tornadas programáveis para usuários finais avançados adicionando recursos como scripting e macros. Outras aplicações dão a uma linguagem de programação um papel central na sua interface com o usuário. Esse é o caso, por exemplo, da linguagem de fórmulas de planilhas de cálculo. Enquanto a área de scripting se beneficiou dos avanços das pesquisas em linguagens de programação, produzindo linguagens maduras e reusáveis, o estado das linguagens em nível de interface não teve o mesmo grau de desenvolvimento. Argumentamos que um melhor entendimento desta classe de linguagens se faz necessário. Neste trabalho, modelamos semânticas de linguagens de usuário final existentes, em três diferentes domínios: multimídia, planilhas e engenharia. Nosso foco é em linguagens de dataflow, um paradigma representativo em aplicações programáveis por usuários finais. Com base nessa análise, temos como objetivo prover um melhor entendimento do design de linguagens de dataflow no contexto de programação de usuários finais e propor linhas-guia para o projeto de linguagens de nível de interface baseadas neste paradigma para aplicações programáveis. / [en] Many applications are made programmable for advanced end-users by adding facilities such as scripting and macros. Other applications take a programming language to the center stage of its UI. That is the case, for example, of the spreadsheet formula language. While scripting has benefited from the advances of programming language research, producing mature and reusable languages, the state of UI-level languages lags behind. We claim that a better understanding of such languages is necessary. In this work, we model the semantics of existing end-user programming languages in three different domains: multimedia, spreadsheets and engineering. Our focus is on dataflow languages, a representative paradigm for end-user programmable applications. Based on this analysis, we aim to provide a better understanding of dataflow semantics as used in the context of end-user programming and propose guidelines for the design of UI-level languages for end-user programmable applications.

[pt] Ambientes de Execução Gerenciada tornaram-se alvos populares para compiladores de linguagens de programação de alto nível. Eles provêem um sistema tipos de alto nível com segurança de memória garantida, assim como facilidades como coleta de lixo, acesso a serviços da plataforma subjacente (possivelmente através de uma sandbox), multithreading, e uma rica biblioteca de estruturas de dados e algorithmos, mas não possuem um modelo de desempenho claro, o que atrapalha as tentativas de otimização de qualquer linguagem que não tenha um mapeamento direto na semântica do ambiente de execução, especialmente se a linguagem é dinamicamente tipada. Nós afirmamos que é possível construir um compilador para uma linguagem dinâmica que tem como alvo um ambiente de execução gerenciada que rivaliza um compilador que tem como alvo linguagem de máquina na eficiência do código que ele gera. Essa tese apresenta um compilador com tal característica, descrevendo as otimizações necessárias para sua construção, e testes de desempenho que validam essas otimizações. Nossas otimizações não dependem de geração de código em tempo de execução, apenas em informação estaticamente disponível no código fonte. Nós usamos uma nova análise de inferência de tipos para aumentar a quantidade de informação disponível. / [en] Managed runtime environments have become popular targets for compilers of high-level programming languages. They provide a high-level type system with enforced runtime safety, as well as facilities such as garbage collection, possibility sandboxed access to services of the underlying platform, multithreadng, and a rich library of data structures and algorithms. But managed runtime environments lack a clear performance model, which hinders attempts ar optimizing the compilation of any language that does nor have a direct mapping to the runtime environments semantics. This is aggravated if the language is dynamically typed. We assert that it is possible to build a compiler for a dynamic language that targets a managed runtime environment so that it rivals a compiler that targets machine code directly in efficiency of the code it generates. This dissertation presents such a compiler, describing the optimizations that were needed to build it, and benchmarks that validate these optimizations. Our optimizations do not depend on runtime code generation, only on information that is statically available from the source program. We use a novel type inference analysis to increase the amount of information available.

[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.

[pt] Inúmeras linguagens de programação oferecem suporte a finalizadores e referências fracas. Não obstante, de maneira geral esses mecanismos são relativamente pouco conhecidos e pouco usados por programadores. Mesmo entre pesquisadores e desenvolvedores de linguagens não existe muito consenso quanto à sua semântica, que varia consideravelmente entre diferentes implementações. Neste trabalho buscamos explorar os conceitos de finalizadores e de referências fracas, suprindo a ausência de uma especificação clara e abrangente, e permitindo uma melhor compreensão, implementação e uso dos mecanismos correspondentes. Como ponto de partida realizamos um amplo levantamento sobre como é feito o suporte a finalizadores e referências fracas em diferentes linguagens de programação, identificando as características comuns, os problemas, e as questões semânticas mais relevantes associadas às implementações consideradas. Para garantir uma maior precisão em nossa análise, utilizamos um modelo abstrato de uma linguagem de programação com gerenciamento automático de memória. Através deste modelo especificamos formalmente a semântica de finalizadores e referências fracas, incluindo descrições das suas principais variantes e mecanismos relacionados. Além disso, provamos certas propriedades inerentes a linguagens de programação com gerenciamento automático de memória, indicando como estas são afetadas pela introdução de finalizadores e referências fracas. Por fim, consideramos possíveis estratégias de implementação desses mecanismos em diferentes tipos de sistemas. Algumas das opções semânticas investigadas impõe um custo de processamento expressivo, o que frequentemente inviabiliza a sua adoção na prática. / [en] Most mainstream programming languages support finalizers and weak references. In spite of that, these abstractions are still modestly known by programmers in general. Even among language designers there seems to be no common view on how to define their semantics, and language implementations certainly reflect that. In this thesis we explore the concepts of finalizer and weak reference by discussing several important issues that, as far as we know, have not been explored by other authors. After presenting a survey on how finalizers and weak references are supported by actual programming languages, we thoroughly examine their semantics and discuss alternative implementation strategies. We also use an operational approach to develop a formal model for reasoning about garbage collection and its interaction with client programs. By explicitly representing low-level details, such as heap memory and its addresses, we were able to clearly specify memory management actions, and prove several important memory-related language invariants. Using this model we describe a formal semantics for finalizers and weak references, exploring some of its many subtleties. We believe that the topics covered here can serve as a relevant reference for further investigations, and also help to guide actual implementations.

[pt] Produzir tecnologia tem se mostrado uma habilidade cada vez mais indispensável na sociedade moderna. Os usuários estão deixando de ser simples consumidores e passando a ser produtores, usando a tecnologia para expressarem suas ideias. Nesse contexto, o aprendizado do chamado raciocínio computacional deve ser tão importante quanto o de disciplinas básicas, como a leitura, a escrita e a aritmética. Ao desenvolver tal habilidade o aluno vai conseguir se expressar através do software. Diversos projetos ao redor do mundo têm suas tecnologias e didáticas próprias a fim de auxiliar o aluno a desenvolver tal capacidade. Porém, sabemos que em um contexto que está em constante evolução como é o caso da informática, não podemos deixar que o aluno fique preso a uma única ferramenta ou meio de se expressar. Ferramentas podem ficar obsoletas e ele perderia seu poder de produtor de tecnologia. Pensando nisso, foi elaborado um modelo de transferência do aprendizado do raciocínio computacional a ser incorporado a sistemas de documentação ativa que apoiam o ensino-aprendizado desta habilidade. O modelo auxiliará o designer na criação de um artefato tecnológico que seja capaz de ajudar alunos e professores a aprenderem uma nova linguagem de programação. O modelo, que é baseado na Engenharia Semiótica, é a principal contribuição científica dessa dissertação de mestrado. / [en] Producing technology has been an increasingly essential ability in modern society. The users are no longer simple consumers but actually, also, technology producers, using technology to express their ideas. In this context, the learning of the so-called computational thinking should be as important as learning basic disciplines such as reading, writing and arithmetic. As long as the student can develop this ability, he will be able to express himself or herself through the software. Many projects around the world have their own technologies and pedagogy to help the student develop such capacity. However, we know that in a context that is constantly evolving as is the case of informatics, we cannot allow the student to be attached to a single tool or means. Tools may become obsolete and students would lose their technology producer status. With this in mind, we designed a learning transfer model of computational thinking, which will assist the designer in the creation of a technological artifact to help students and teachers learn a new programming language. The model, which is based on the Semiotic Engineering, is the main scientific contribution of this master s dissertation.

[pt] A maioria das linguagens de programação modernas fornece ferramentas para programação concorrente sem restringir seu uso. Assim, fica a cargo do programador evitar a ocorrência de condições de corrida. Nessa dissertação, revisitamos o modelo de monitores, projetados para prevenir condições de corrida ao limitar o acesso à variáveis compartilhadas, e mostramos que monitores podem ser implementados em linguagens de programação com semântica referencial, dadas as regras de tipagem apropriadas. Nós descrevemos a linguagem de programação Aria, projetada com monitores nativos seguindo a proposta original do modelo. Através da resolução de problemas clássicos de concorrência, nós avaliamos o uso de monitores em Aria para sincronização em diferentes níveis de granularidade, e extendemos a linguagem com novos recursos a fim de contemplar as limitações do modelo envolvendo desempenho e expressividade. / [en] Most current programming languages do not restrict the use of the concurrency primitives they provide, leaving it to the programmer to detect data races. In this dissertation, we revisit the monitor model, which guards against data races by guaranteeing that accesses to shared variables occur only inside monitors, and show that this concept can be implemented in a programming language with referential semantics, given appropriate typing rules. We describe the Aria programming language, designed with native monitors according to these rules. Through the discussion of classic concurrency problems, we evaluate the use of Aria monitors for synchronization at different levels of granularity and extend the language with new features to address the limitations of monitors regarding performance and expressiveness.