La thèse s'intéresse au problème de l'analyse syntaxique pour les langages de programmation. Si ce sujet a déjà été traité à maintes reprises, et bien que des outils performants pour la génération d'analyseurs syntaxiques existent et soient largement employés, l'implémentation de la partie frontale d'un compilateur reste encore extrêmement complexe.<br /><br />Ainsi, si le texte d'un programme informatique se doit de n'avoir qu'une seule interprétation possible, l'analyse des langages de programmation, fondée sur une grammaire algébrique, est, pour sa part, le plus souvent non déterministe, voire ambiguë. Confrontés aux insuffisances des analyseurs déterministes traditionnels, les développeurs de parties frontales se sont tournés massivement vers des techniques d'analyse générale, à même d'explorer des choix non déterministes, mais aussi au prix de la garantie d'avoir bien traité toutes les ambiguïtés grammaticales. Une difficulté majeure dans l'implémentation d'un compilateur réside alors dans l'identification (non décidable en général) et le traitement de ces ambiguïtés.<br /><br />Les techniques décrites dans la thèse s'articulent autour d'approximations des grammaires à deux fins. L'une est la génération d'a\-na\-ly\-seurs syntaxiques non canoniques, qui sont moins sensibles aux dif\-fi\-cultés grammaticales, en particulier parce qu'ils peuvent exploiter un langage algébrique non fini en guise de contexte droit pour résoudre un choix non déterministe. Ces analyseurs rétablissent la garantie de non ambiguïté de la grammaire, et en sus assurent un traitement en temps linéaire du texte à analyser. L'autre est la détection d'ambiguïté en tant que telle, avec l'assurance qu'une grammaire acceptée est bien non ambiguë quel que soit le degré d'approximation employé.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.

Notre travail porte sur le développement d'algorithmes performants d'application de grammaires locales, en prenant comme référence ceux des logiciels libres existants : l'analyseur syntaxique descendant d'Unitex et l'analyseur syntaxique à la Earley d'Outilex. Les grammaires locales sont un formalisme de représentation de la syntaxe des langues naturelles basé sur les automates finis. Les grammaires locales sont un modèle de construction de descriptions précises et à grande échelle de la syntaxe des langues naturelles par le biais de l'observation systématique et l'accumulation méthodique de données. L'adéquation des grammaires locales pour cette tâche a été testée à l'occasion de nombreux travaux. À cause de la nature ambiguë des langues naturelles et des propriétés des grammaires locales, les algorithmes classiques d'analyse syntaxique tels que LR, CYK et ne peuvent pas être utilisés dans le contexte de ce travail. Les analyseurs top-down et Earley sont des alternatives possibles ; cependant, ils ont des coûts asymptotiques exponentiels pour le cas des grammaires locales. Nous avons d'abord conçu un algorithme d'application de grammaires locales avec un coût polynomial dans le pire des cas. Ensuite, nous avons conçu des structures de donnés performantes pour la représentation d'ensembles d'éléments et de séquences. Elles ont permis d'améliorer la vitesse de notre algorithme dans le cas général. Nous avons mis en œuvre notre algorithme et ceux des systèmes Unitex et Outilex avec les mêmes outils afin de les tester dans les mêmes conditions. En outre, nous avons mis en œuvre différents versions de chaque algorithme en utilisant nos structures de données et algorithmes pour la représentation d'ensembles et ceux fournis par la Standard Template Library (STL) de GNU. Nous avons comparé les performances des différents algorithmes et de leurs variantes dans le cadre d'un projet industriel proposé par l'entreprise Telefónica I+D : augmenter la capacité de compréhension d'un agent conversationnel qui fournit des services en ligne, voire l'envoi de SMS à des téléphones portables ainsi que des jeux et d'autres contenus numériques. Les conversations avec l'agent sont en espagnol et passent par Windows Live Messenger. En dépit du domaine limité et de la simplicité des grammaires appliquées, les temps d'exécution de notre algorithme, couplé avec nos structures de données et algorithmes pour la représentation d'ensembles, ont été plus courts. Grâce au coût asymptotique amélioré, on peut s'attendre à des temps d'exécution significativement inférieurs par rapport aux algorithmes utilisés dans les systèmes Unitex et Outilex, pour le cas des grammaires complexes et à large couverture / This work focuses on the research and development of efficient algorithms of application of local grammars, taking as reference those of the currently existent open-source systems : Unitex's top-down parser and Outilex's Earley-like parser. Local grammars are a finite-state based formalism for the representation of natural language grammars. Moreover, local grammars are a model for the construction of fully scaled and accurated descriptions of the syntax of natural languages by means of systematic observation and methodical accumulation of data. The adequacy of local grammars for this task has been proved by multiple works. Due to the ambiguous nature of natural languages, and the particular properties of local grammars, classic parsing algorithms such as LR, CYK's and Tomita's cannot be used in the context of this work. Top-down and Earley parsers are possible alternatives, though they have an exponential worst-case cost for the case of local grammars. We have first conceived an algorithm of application of local grammars having a polynomial worst-case cost. Furthermore, we have conceived other optimizations which increase the efficiency of the algorithm for general cases, namely the efficient management of sets of elements and sequences. We have implemented our algorithm and those of the Unitex and Outilex systems with the same tools in order to test them under the same conditions. Moreover, we have implemented different versions of each algorithm, either using our custom set data structures or those included in GNU's implementation of the C++ Standard Template Library (STL). We have compared the performances of the different algorithms and algorithm versions in the context of an industrial natural language application provided by the enterprise Telefónica I+D : extending the understanding capabilities of a chatterbot that provides mobile services, such as sending SMSs to mobile phones as well as games and other digital contents. Conversation with the chatterbot is held in Spanish by means of Microsoft's Windows Live Messenger. In spite of the limited domain and the simplicity of the applied grammars, execution times of our parsing algorithm coupled with our custom implementation of sets were lower. Thanks to the improved asymptotic cost of our algorithm, execution times for the case of complex and large coverage grammars can be expected to be considerably lower than those of the Unitex and Outilex algorithms

Avec les espaces de finitude, Ehrhard a exhibé une sémantique de la logique linéaire contenant une opération de différentiation. Dans ce cadre, l'interprétation des formules est décomposable en séries de Taylor. Cette étude a engendré des syntaxes différentielles. Cette thèse de sémantique dénotationnelle prolonge ce travail par une exploration de sémantiques vectorielles de la logique linéaire, et contribue à l'étude sémantique et syntaxique de la formule de Taylor. La première partie aborde la sémantique. Nous présentons l'interprétation des constructions de la logique linéaire dans les espaces vectoriels munis d'une topologie linéarisée, les espaces de Lefschetz. Nous définissons une notion intrinsèque d'espaces de finitude, les espaces de Lefschetz finitaires. Nous caractérisons les espaces de Lefschetz réflexifs complets à l'aide de bornologies linéaires. Enfin, nous montrons que la décomposition de Taylor reste valide dans ces espaces. La seconde partie porte sur les syntaxes différentielles. La formule de Taylor syntaxique traduit un terme en une superposition de termes différentiels qui sont autant de possibilités d'exécutions. Comme l'ont montré Ehrhard et Regnier, les termes issus de cette traduction vérifient une relation de cohérence. Nous introduisons une sémantique totale qui capture cette relation. Puis, nous construisons une extension vectorielle du lambda-calcul, le calcul barycentrique, interprété par cette sémantique totale. Enfin, dans le cadre des réseaux différentiels, nous présentons un algorithme non déterministe qui permet de décider si un ensemble fini de réseaux différentiels provient de la traduction d'un réseau de la logique linéaire par la formule de Taylor syntaxique.

Étude de la représentation de programmes dans un atelier de génie logiciel et des principaux concepts de l'édition syntaxique. Justification de l'utilité de la manipulation structurée des programmes, avant de présenter les spécifications externes d'un éditeur dirigé par la syntaxique. Étude des diverses techniques permettant d'effectuer une analyse contextuelle incrémentale d'un programme, mise en œuvre après chacune de ses modifications. Les différents concepts étudiés ont fait l'objet d'un prototype, réalisé dans le cadre du projet d'atelierADELE.

Approche pour la réalisation d'outils de vérification des masques de circuit intégrés. Le système Comfor est un extracteur de schéma électrique paramétrable par la technologie. Il analyse des images de C.I. pour reconnaitre les composants électriques et calculer leurs caractéristiques. Comfor base à la fois sur des notions de programmation logique et des techniques de reconnaissance syntaxique de formes

.

.

Notre travail porte sur le développement d'algorithmes performants d'application de grammaires locales, en prenant comme référence ceux des logiciels libres existants : l'analyseur syntaxique descendant d'Unitex et l'analyseur syntaxique à la Earley d'Outilex. Les grammaires locales sont un formalisme de représentation de la syntaxe des langues naturelles basé sur les automates finis. Les grammaires locales sont un modèle de construction de descriptions précises et à grande échelle de la syntaxe des langues naturelles par le biais de l'observation systématique et l'accumulation méthodique de données. L'adéquation des grammaires locales pour cette tâche a été testée à l'occasion de nombreux travaux. À cause de la nature ambiguë des langues naturelles et des propriétés des grammaires locales, les algorithmes classiques d'analyse syntaxique tels que LR, CYK et ne peuvent pas être utilisés dans le contexte de ce travail. Les analyseurs top-down et Earley sont des alternatives possibles ; cependant, ils ont des coûts asymptotiques exponentiels pour le cas des grammaires locales. Nous avons d'abord conçu un algorithme d'application de grammaires locales avec un coût polynomial dans le pire des cas. Ensuite, nous avons conçu des structures de donnés performantes pour la représentation d'ensembles d'éléments et de séquences. Elles ont permis d'améliorer la vitesse de notre algorithme dans le cas général. Nous avons mis en œuvre notre algorithme et ceux des systèmes Unitex et Outilex avec les mêmes outils afin de les tester dans les mêmes conditions. En outre, nous avons mis en œuvre différents versions de chaque algorithme en utilisant nos structures de données et algorithmes pour la représentation d'ensembles et ceux fournis par la Standard Template Library (STL) de GNU. Nous avons comparé les performances des différents algorithmes et de leurs variantes dans le cadre d'un projet industriel proposé par l'entreprise Telefónica I+D : augmenter la capacité de compréhension d'un agent conversationnel qui fournit des services en ligne, voire l'envoi de SMS à des téléphones portables ainsi que des jeux et d'autres contenus numériques. Les conversations avec l'agent sont en espagnol et passent par Windows Live Messenger. En dépit du domaine limité et de la simplicité des grammaires appliquées, les temps d'exécution de notre algorithme, couplé avec nos structures de données et algorithmes pour la représentation d'ensembles, ont été plus courts. Grâce au coût asymptotique amélioré, on peut s'attendre à des temps d'exécution significativement inférieurs par rapport aux algorithmes utilisés dans les systèmes Unitex et Outilex, pour le cas des grammaires complexes et à large couverture

La thèse présentée ici a pour but de proposer des systèmes de détection, de composition de constituants sémantiques et d'interprétation dans la compréhension de la langue naturelle parlée. Cette compréhension se base sur un système de reconnaissance automatique de la parole qui traduit les signaux oraux en énoncés utilisables par la machine. Le signal de la parole, ainsi transcrit, comporte un ensemble d'erreurs liées aux erreurs de reconnaissance (bruits, parasites, mauvaise prononciation...). L'interprétation de cet énoncé est d'autant plus difficile qu'il est issu d'un discours parlé, soumis à la disfluence du discours, aux auto-corrections... L'énoncé est de plus agrammatical, car le discours parlé lui-même est agrammatical. L'application de méthodes d'analyses grammaticales ne produit pas de bons résultats d'interprétation, sur des textes issus de transcriptions de la parole. L'utilisation de méthodes d'analyses syntaxiques profondes est à éviter. De ce fait, une analyse superficielle est envisagée. Un des premiers objectifs est de proposer une représentation du sens. Il s'agit de considérer des ontologies afin de conceptualiser le monde que l'on décrit. On peut exprimer les composants sémantiques en logique du premier ordre avec des prédicats. Dans les travaux décrits ici, nous représentons les éléments sémantiques par des frames (FrameNet ). Les structures de frames sont hiérarchisées, et sont des fragments de connaissances auxquels on peut insérer, fusionner ou inférer d'autres fragments de connaissances. Les structures de frames sont dérivables en formules logiques. Nous proposons un système de compréhension de la parole à partir de règles logiques avec le support d'une ontologie, afin de pouvoir créer des liens à partir de composants sémantiques. Puis, nous avons mené une étude sur la découverte des supports syntaxiques des relations sémantiques. Nous proposons une expérience de composition sémantique afin d'enrichir les composants sémantiques de base. Enfin, nous présentons un système de détection de lambda-expression pour mettre en hypothèse les relations à trouver à travers le discours