Akim Demaille

A set of tools to teach compiler construction

By Akim Demaille, Roland Levillain, Benoît Perrot

2008-03-29

In Proceedings of the thirteenth annual conference on innovation and technology in computer science education (ITICSE’08)

Abstract

Compiler construction is a widely used software engineering exercise, but because most students will not be compiler writers, care must be taken to make it relevant in a core curriculum. Auxiliary tools, such as generators and interpreters, often hinder the learning: students have to fight tool idiosyncrasies, mysterious errors, and other poorly educative issues. We introduce a set of tools especially designed or improved for compiler construction educative projects in . We also provide suggestions about new approaches to compiler construction. We draw guidelines from our experience to make tools suitable for education purposes.

Continue reading

Semantics driven disambiguation: A comparison of different approaches

By Akim Demaille, Renaud Durlin, Nicolas Pierron, Benoît Sigoure

2008-02-08

In Proceedings of the 8th workshop on language descriptions, tools and applications (LDTA’08)

Abstract

Context-sensitive languages such as or can be parsed using a context-free but ambiguous grammar, which requires another stage, disambiguation, in order to select the single parse tree that complies with the language’s semantical rules. Naturally, large and complex languages induce large and complex disambiguation stages. If, in addition, the parser should be extensible, for instance to enable the embedding of domain specific languages, the disambiguation techniques should feature traditional software-engineering qualities: modularity, extensibility, scalability and expressiveness. We evaluate three approaches to write disambiguation filters for sdf grammars: algebraic equations with asf, rewrite-rules with programmable traversals for , and attribute grammars with , our system. To this end we introduce , a highly ambiguous language. Its “standard” grammar exhibits ambiguities inspired by those found in the and standard grammars. To evaluate modularity, the grammar is layered: it starts with a small core language, and several layers add new features, new production rules, and new ambiguities.

Continue reading

Towards the world-wide quantum network

By Cuong Le Quoc, Patrick Bellot, Akim Demaille

2008-01-25

In Proceedings of the 4th information security practice and experience conference (ISPEC’08)

Abstract

Quantum Key Distribution (QKD) networks are of much interest due to their capacity of providing extremely high security keys to network participants. Most QKD network studies so far focus on trusted models where all the network nodes are assumed to be perfectly secured. This restricts QKD networks to be small. In this paper, we first develop a novel model dedicated to large-scale QKD networks, some of whose nodes could be eavesdropped secretly. Then, we investigate the key transmission problem in the new model by an approach based on percolation theory and stochastic routing. Analyses show that under computable conditions large-scale QKD networks could protect secret keys with an extremely high probability. Simulations validate our results.

Continue reading

On the security of quantum networks: A proposal framework and its capacity

By Cuong Le Quoc, Patrick Bellot, Akim Demaille

2007-03-10

In Proceedings of the 2007 international conference on new technologies, mobility and security (NTMS’07)

Abstract

In large Quantum Key Distribution (QKD)-based networks, intermediate nodes are necessary because of the short length of QKD links. They have tendency to be used more than classical networks. A realistic assumption is that there are eavesdropping operations in these nodes without knowledge of legitimate network participants. We develop a QKD-based network framework. We present a percolation-based approach to discuss about conditions of extremely high secret key transmission. We propose also an adaptive stochastic routing algorithm that helps on protecting keys from reasonable eavesdroppers in a dense QKD network. We show that under some assumptions, one could prevent eavesdroppers from sniffing the secrets with an arbitrarily large probability.

Continue reading

Stochastic routing in large grid-shaped quantum networks

By Cuong Le Quoc, Patrick Bellot, Akim Demaille

2006-12-04

In Proceedings of the fifth international conference on computer sciences, research, innovation and vision for the future (RIVF’07)

Abstract

This paper investigates the problem of secret key transmissions for an arbitrary Alice-Bob pair in Quantum Key Distribution-based networks. We develop a realistic QKD-based network framework and we show that the key transmission problem on such a framework can be considered as a variant of the classical percolation problem. We also present an adaptive stochastic routing algorithm protect from inevitable eavesdroppers. Simulations were carried out not only to validate our approach, but also to compute critical parameters ensuring security. These results show that large quantum networks with eavesdroppers do provide security.

Continue reading

Modeling of sensor networks using XRM

By Akim Demaille, Sylvain Peyronnet, Benoît Sigoure

2006-09-14

In Proceedings of the 2nd international symposium on leveraging applications of formal methods, verification and validation (ISoLA’06)

Abstract

Sensor networks are composed of small electronic devices that embed processors, sensors, batteries, memory and communication capabilities. One of the main goal in the design of such systems is the handling of the inherent complexity of the nodes, strengthened by the huge number of nodes in the network. For these reasons, it becomes very difficult to model and verify such systems. In this paper, we investigate the main characteristics of sensor nodes, discuss about the use of a language derived from Reactive Modules for their modeling and propose a language (and a tool set) that ease the modeling of this kind of systems.

Continue reading

Attribute grammars for modular disambiguation

By Valentin David, Akim Demaille, Olivier Gournet

2006-07-12

In Proceedings of the IEEE 2nd international conference on intelligent computer communication and processing (ICCP’06)

Abstract

To face the challenges to tomorrow’s software engineering tools, powerful language-generic program-transformation components are needed. We propose the use of attribute grammars (AGs) to generate language specific disambiguation filters. In this paper, a complete implementation of a language-independent AGs system is presented. As a full scale experiment, we present an implementation of a flexible C front-end. Its specifications are concise, modular, and the result is efficient. On top of it, transformations such as software renovation, code metrics, domain specific language embedding can be implemented.

Continue reading

Probabilistic verification of sensor networks

By Akim Demaille, Sylvain Peyronnet, Thomas Hérault

2006-02-01

In Proceedings of the fourth international conference on computer sciences, research, innovation and vision for the future (RIVF’06)

Abstract

Sensor networks are networks consisting of miniature and low-cost systems with limited computation power and energy. Thanks to the low cost of the devices, one can spread a huge number of sensors into a given area to monitor, for example, physical change of the environment. Typical applications are in defense, environment, and design of ad-hoc networks areas. In this paper, we address the problem of verifying the correctness of such networks through a case study. We modelize a simple sensor network whose aim is to detect the apparition of an event in a bounded area (such as a fire in a forest). The behaviour of the network is probabilistic, so we use APMC, a tool that allows to approximately check the correctness of extremely large probabilistic systems, to verify it.

Continue reading

C-Transformers — A framework to write C program transformations

By Alexandre Borghi, Valentin David, Akim Demaille

2005-10-16

In ACM Crossroads

Abstract

Program transformation techniques have reached a maturity level that allows processing high-level language sources in new ways. Not only do they revolutionize the implementation of compilers and interpreters, but with modularity as a design philosophy, they also permit the seamless extension of the syntax and semantics of existing programming languages. The C-Transformers project provides a transformation environment for C, a language that proves to be hard to transform. We demonstrate the effectiveness of C-Transformers by extending C’s instructions and control flow to support Design by Contract. C-Transformers is developed by members of the LRDE: EPITA undergraduate students.

Continue reading

C/C++ disambiguation using attribute grammars

By Valentin David, Akim Demaille, Renaud Durlin, Olivier Gournet

2005-05-01

In

Abstract

We propose a novel approach to semantics driven disambiguation based on Attribute Grammars (AGs). AGs share the same modularity model as its host grammar language, here Syntax Definition Formalism (SDF), what makes them particularly attractive for working on unstable grammars, or grammar extensions. The framework we propose is effective, since a full ISO-C99 disambiguation chain already works, and the core of the hardest ambiguities of C++ is solved. This requires specific techniques, and some extensions to the stock AG model.

Continue reading

Search

Tags