• Langue : Anglais
• Discipline : Informatique
• Identifiant : 2019LILUI077
• Type de thèse : Doctorat
• Date de soutenance : 26/11/2019

Résumé en langue originale

Les transformations automatiques de code apparaissent dans diverses situations, les refactorings, les migrations inter-langages ou encore la spécialisation de code. Les moteurs supportant ces transformations cherchent dans le code source les occurrences de motifs spécifiés par l’utilisateur, puis les réécrivent grâce à une transformation. Cette transformation peut soit modifier les occurrences elles-mêmes, des éléments de la représentation intermédiaire (IR) du langage, en nouveaux éléments ou réécrire leur code source. Nous nous concentrons sur la réécriture de code source qui offre une meilleure flexibilité grâce à des transformations arbitraires particulièrement utiles à la migration et à la spécialisation de code. Les motifs sont divisés en deux catégories : les motifs explicites et syntaxiques. Les premiers demandent que l’utilisateur connaisse l’IR du langage, un effort d’apprentissage non négligeable. Les seconds demandent seulement de connaître la syntaxe du langage et non son IR, mais requièrent un effort d’implémentation supplémentaire pour les back-ends de langage du moteur. Tandis que les experts en langage connaissent l’IR et la syntaxe du langage, les autres utilisateurs connaissent seulement la syntaxe. Nous proposons un moteur de reconnaissance de motifs offrant une représentation hybride des motifs : les motifs peuvent être à la fois explicites et syntaxiques. Par défaut, le moteur se rabat sur un fonctionnement syntaxique, car la barrière à l’entrée est plus basse. Pour pallier au coup d’implémentation des back-ends de langage pour la reconnaissance syntaxique, nous prenons une approche générative. Le moteur de reconnaissance hybride est couplé avec un moteur de génération d’analyseurs syntaxiques. Ce dernier génère des analyseurs syntaxiques LR généralisés (GLR) capables d’analyser non seulement le code source à réécrire, mais également le motif à reconnaitre. L’implémenteur du back-end de langage n’a alors qu’à ajouter une ligne à la grammaire pour avoir accès au moteur de reconnaissance de motifs pour ce langage. L’approche est basée sur des analyseurs syntaxiques GLR pouvant se dupliquer et traquant ses sous-analyseurs. Ces implémentations particulières de GLR ne passent pas à l’échelle quand trop de duplications sont nécessaires pour gérer les ambiguïtés et notre approche ajoute de la duplication. Pour éviter une explosion du temps d’exécution, nos analyseurs syntaxiques FGLR fusionnent plus régulièrement et permettent une désambiguïsation à la volée pendant l’analyse via des effets de bord.

Résumé traduit

Code transformations are needed in various cases: refactorings, migrations, code specialization, and so on. Code transformation engines work by finding a pattern in the source code and rewriting its occurrences according to the transformation. The transformation either rewrites the occurrences, elements of the intermediate representation (IR) of the language, into new elements or directly rewrites the source code. In this work, we focused on source rewriting since it offers more flexibility through arbitrary transformations, especially for migrations and specializations. Matching patterns come in two different flavors, explicit and syntactic. The former requires the user to know the IR of the language, a heavy knowledge burden. The latter only relies on the syntax of the matched language and not its IR, but requires significantly more work to implement the language back-ends. Language experts tend to know the IR and the syntax of a language, while other users know only the syntax. We propose a pattern matching engine offering a hybrid pattern representation: both explicit and syntactic matching are available in the same pattern. The engine always defaults to syntactic as it is the lowest barrier to entry for patterns. To counterbalance the implementation cost of language back-ends for syntactic pattern matching, we take a generative approach. We combine the hybrid pattern matching engine with a parser generator. The parser generator generates generalized LR (GLR) parsers capable of not only parsing the source but also the hybrid pattern. The back-end implementer only needs to add one line to the grammar of the language to activate the pattern matching engine. This approach to pattern matching requires GLR parsers capable of forking and keeping track of each individual fork. These GLR implementations suffer the more forking is done to handle ambiguities and patterns require even more forking. To prevent an explosion, our Fibered-GLR parsers merge more often and allow for classic disambiguation during the parse through side-effects.