Cette thèse s'intéresse à la modélisation de la syntaxe et de l'interface syntaxe-sémantique de la phrase, et explore la possibilité de contrôler au niveau des structures de dérivation la surgénération que produit le traitement des dépendances à distance par des types d'ordre supérieur. À cet effet, nous étudions la possibilité d'étendre le système de typage des Grammaires Catégorielles Abstraites avec les constructions de la somme disjointe, du produit cartésien et du produit dépendant, permettant d'étiqueter les catégories syntaxiques par des structures de traits. Nous prouvons dans un premier temps que le calcul résultant de cette extension bénéficie des propriétés de confluence et de normalisation, permettant d'identifier les termes beta-équivalents dans le formalisme grammatical. Nous réduisons de plus le même problème pour la beta-eta-équivalence à un ensemble d'hypothèse de départ. Dans un second temps, nous montrons comment cette introduction de structures de traits peut être appliquée au contrôle des dépendances à distances, à travers les exemples des contraintes de cas, des îlots d'extraction pour les mouvements explicites et implicites, et des extractions interrogatives multiples, et nous discutons de la pertinence de placer ces contrôles sur les structures de dérivation / This thesis focuses on the modelisation of syntax and syntax-semantics interface of sentences, and investigate how the control of the surgeneration caused by the treatment of linguistics movements with higher order types can take place at the level of derivation structures. For this purpose, we look at the possibility to extend the type system of Abstract Categorial Grammars with the constructions of disjoint sum, cartesian product and dependent product, which enable syntactic categories to be labeled by feature structures. At first, we demonstrate that the calculus associated with this extension enjoy the properties of confluence and normalization, by which beta-equivalence can be computed in the grammatical formalism. We also reduce the same problem for beta-eta-equivalence to a few hypothesis. Then, we show how this feature structures can be used to control linguistics movements, through the examples of case constraints, extraction islands for overt and covert movements and multiples interrogative extractions, and we discuss the relevancy of operating these controls on the derivation structures

Ces travaux s’intéressent à la modélisation formelle de la sémantique des langues naturelles. Pour cela, nous suivons le principe de compositionnalité qui veut que le sens d’une expression complexe soit une fonction du sens de ses parties. Ces fonctions sont généralement formalisées à l’aide du [lambda]-calcul. Cependant, ce principe est remis en cause par certains usages de la langue, comme les pronoms anaphoriques ou les présuppositions. Ceci oblige à soit abandonner la compositionalité, soit modifier les structures du sens. Dans le premier cas, le sens n’est alors plus obtenu par un calcul qui correspond à des fonctions mathématiques, mais par un calcul dépendant du contexte, ce qui le rapproche des langages de programmation qui manipulent leur contexte avec des effets de bord. Dans le deuxième cas, lorsque les structures de sens sont ajustées, les nouveaux sens ont tendance à avoir une structure de monade. Ces dernières sont elles-mêmes largement utilisées en programmation fonctionnelle pour coder des effets de bord, que nous retrouvons à nouveau. Par ailleurs, s’il est souvent possible de proposer le traitement d’un unique phénomène, composer plusieurs traitements s’avère être une tâche complexe. Nos travaux proposent d’utiliser les résultats récents autour des langages de programmation pour parvenir à combiner ces modélisations par les effets de bord. Pour cela, nous étendons le [lambda]-calcul avec une monade qui implémente les effects et les handlers, une technique récente dans l’étude des effets de bord. Dans la première partie de la thèse, nous démontrons les propriétés fondamentales de ce calcul (préservation de type, confluence et terminaison). Dans la seconde partie, nous montrons comment utiliser le calcul pour le traitement de plusieurs phénomènes linguistiques : deixis, quantification, implicature conventionnelle, anaphore et présupposition. Enfin, nous construisons une unique grammaire qui gère ces phénomènes et leurs interactions. / In formal semantics, researchers assign meanings to sentences of a natural language. This work is guided by the principle of compositionality: the meaning of an expression is a function of the meanings of its parts. These functions are often formalized using the [lambda]-calculus. However, there are areas of language which challenge the notion of compositionality, e.g. anaphoric pronouns or presupposition triggers. These force researchers to either abandon compositionality or adjust the structure of meanings. In the first case, meanings are derived by processes that no longer correspond to pure mathematical functions but rather to context-sensitive procedures, much like the functions of a programming language that manipulate their context with side effects. In the second case, when the structure of meanings is adjusted, the new meanings tend to be instances of the same mathematical structure, the monad. Monads themselves being widely used in functional programming to encode side effects, the common theme that emerges in both approaches is the introduction of side effects. Furthermore, different problems in semantics lead to different theories which are challenging to unite. Our thesis claims that by looking at these theories as theories of side effects, we can reuse results from programming language research to combine them.This thesis extends [lambda]-calculus with a monad of computations. The monad implements effects and handlers, a recent technique in the study of programming language side effects. In the first part of the thesis, we prove some of the fundamental properties of this calculus: subject reduction, confluence and termination. Then in the second part, we demonstrate how to use the calculus to implement treatments of several linguistic phenomena: deixis, quantification, conventional implicature, anaphora and presupposition. In the end, we build a grammar that features all of these phenomena and their interactions.

Nesta tese, que se propôs a explorar as gramáticas brasileiras do português publicadas no século XIX, tivemos três objetivos. O primeiro foi realizar um mapeamento exaustivo da produção gramatical brasileira do português do século XIX, o qual foi feito por meio de fontes secundárias e catálogos de bibliotecas. Tivemos conhecimento de 127 títulos e 77 reedições, o que resulta em duzentas gramáticas. A partir dos dados coletados, que, em geral, eram título, subtítulo, autor, ano de publicação, local e casa impressora, formalizamos unidades de análise para, ao relacioná-las, por meio da metodologia da História Serial (Furet 1991, Barros 2005), realizar um mapeamento descritivo e interpretativo dessa produção. Nosso segundo objetivo, tendo selecionado, com base em quatro critérios combinados (prestígio, emergência, institucionalização e diálogo), dezoito exemplares (16 títulos, 2 reedições) dos duzentos e quatro de que tivemos conhecimento, foi de realizar uma análise orientada para os conteúdos dessas obras, organizada em torno de uma possível rede conceitual. A hipótese dessa análise, baseada em Auroux (2009[1992]) e Swiggers (2010), é de que alguns conceitos poderiam ser eixo de uma rede conceitual devido à sua influência técnica e, eventualmente teórica, em uma determinada tradição de descrição linguística. Essa hipótese surgiu nos resultados de nossa pesquisa de mestrado, em que, ao notar a complexidade da dimensão técnica (cf. Swiggers 2004) de algumas obras dessa tradição, pensamos ser necessário procurar meios de tornar sua análise mais homogênea (cf. Polachini 2013, Polachini 2016). Para testá-la, examinamos o conceito-chave de \'verbo substantivo\' apresentado nas obras selecionadas, que são amiúde influenciadas pela tradição da grammaire générale francesa, ao menos até 1880, quando passa a haver também influência do método histórico-comparativo (cf. Maciel 1910, Nascentes 1939, Elia 1975, Cavaliere 2001, Parreira 2011, Polachini 2013). Ademais, foi necessário formalizar uma metodologia a fim de reconhecer a rede conceitual em torno do verbo substantivo. Primeiramente, definimos conceitos gramaticais como sendo formados por meio de processos classificatórios da cadeia falada. Tais processos têm como produto, por um lado, termos, e, por outro, conceitos. Estes últimos podem ser analisados intensionalmente, por meio de sua definição e seu lugar numa determinada taxonomia, ou extensionalmente, considerando o inventário de dados linguísticos eleitos como exemplos e eventuais ilustrações desses dados em uso. Cada conceito é, portanto, analisado por meio das seguintes categorias: definição, taxonomia, exemplos, ilustrações e por seus termos. Consideramos rede conceitual as relações travadas entre o conceito-chave, verbo substantivo, e conceitos que, na tradição da grammaire générale teriam já alguma relação com o verbo substantivo (cf. Chevalier 1968; Colombat 1992; Raby 2000; Bouard 2007), a saber: gramática e linguagem, metaclasses e classes de palavras, modificadores do nome, verbo, oração (seus elementos e sua organização) apresentadas nas obras. Essas relações podem ser de quatro tipos: (1) equivalência; (2) intersecção (3) subordinação; (4) base teórica comum. Finalmente, distinguimos no texto gramatical a descrição linguística, que chamamos de texto, e as ampliações, reflexões ou críticas realizadas sobre essa descrição, que chamamos de metatexto. Tal metodologia nos permitiu uma visão mais clara e homogênea da dimensão técnica das obras (e de seu eventual ecletismo), além de proporcionar uma visão mais complexa de continuidades e descontinuidades dessa produção, que contrasta com aquelas das revisões históricas. Ademais, os resultados apontam também para: relações entre agendas dos autores ao publicarem suas gramáticas e seu ecletismo. Nossa terceira proposta foi de que esta tese fosse não apenas uma historiografia, mas também uma epihistoriografia dessa tradição. Assim, apresentamos dois apêndices: um com informações catalográficas das 204 gramáticas de que tivemos conhecimento, organizadas cronologicamente; e outro com os paratextos das dezoito obras analisadas. / In this thesis, which approached the Brazilian grammars of Portuguese published in the 19th century, we had three objectives. The first one was to conduct a comprehensive mapping of the Brazilian grammatical production on Portuguese in the 19th century, which we carried out through secondary sources and library catalogs. We have acknowledged 127 titles and 77 re-editions, which total two hundred grammars. From the data collected, which generally consisted of title, subtitle, author, year published, publisher city and publisher name, we built standardized units of analysis so that, when analyzing their relations among one another, we conducted a descriptive and interpretative mapping of this production, adopting the methodology of Serial History (Furet 1991, Barros 2005). By selecting eighteen grammars (16 titles, 2 re-editions) out of the acknowledged two hundred works, based on four combined criteria (prestige, emergence, institutionalization and dialog), our second object was to carry out an analysis oriented to the content of these selected works, organized under a possible conceptual network. The hypothesis of this analysis, based on Auroux (2009[1992]) and Swiggers (2010), is that some concepts could work as an axis of a conceptual network due to their technical, and sometimes theoretical, influence on a specific tradition of linguistic description. This hypothesis was raised in the results of our masters research, in which, by realizing the complexity of some of this traditions grammars technical dimension (cf. Swiggers 2004), we thought it to be necessary to find ways of turning the analysis more homogeneous (cf. Polachini 2013, Polachini 2016). In order to test its effectiveness, we examined the key concept of verbo substantivo (literally: substantive verb), presented in the selected works, which are frequently influenced by the tradition of the French grammaire générale, at least until 1880, when the influence of the historical-comparative method started to take place (cf. Maciel 1910, Nascentes 1939, Elia 1975, Cavaliere 2001, Parreira 2011, Polachini 2013). Moreover, it was necessary to formalize a methodology in order to recognize the conceptual network around the verbo substantivo. First, we defined the grammatical concepts as being formed through classifying processes of spoken speech. These processes have as products, on one side, terms and, on the other, concepts. The latter can be analyzed intentionally, through its definition and its places in a specific taxonomy, or extensionally, considering the inventory of linguistic data considered as examples and any illustrations of these data in use. Each concept is, therefore, analyzed through the following categories: definition, taxonomy, examples, illustrations and by its terms. We considered as conceptual network the relations between the key concept, verbo substantivo, and concepts that, in the grammaire génerales tradition would already have some relation to the verbo substantivo (cf. Chevalier 1968; Colombat 1992; Raby 2000; Bouard 2007), such as: grammar and language, metaclasses and parts of speech, noun modifiers, verb, clause (its elements and organization) presented in the grammars. These relations can be of three types: (1) identity; (2) intersection; (3) subordination; (4) shared theoretical background. Finally, in the grammatical text, we distinguished the linguistic description, which we called text, from its expansions, reflections and critical comments on this description, which we called metatext. Such methodology allowed a clearer and more homogeneous view of the technical dimension of the works analyzed (and their often eclecticism), in addition to providing a more complex view of continuities and discontinuities of this production, which contrasts with those of the historical reviews. Furthermore, the results also point to: relations between the authors schedules when publishing their grammars and their eclecticism; and the metatexts role between teaching and linguistic reflection. Our third objective was to make this thesis not only a historiography but also a epihistoriography of this tradition. Thus, we presented two appendices: one with cataloging information of the two hundred grammars which we acknowledged, organized chronologically; and another one with the paratexts of the eighteen works analyzed.

La linguistique informatique a pour objet de construire un modèle formel des connaissances linguistiques, et d’en tirer des algorithmes permettant le traitement automatique des langues. Pour ce faire, elle s’appuie fréquemment sur des grammaires dites génératives, construisant des phrases valides par l’application successive de règles de réécriture. Une approche alternative, basée sur la théorie des modèles, vise à décrire la grammaticalité comme une conjonction de contraintes de bonne formation, en s’appuyant sur des liens profonds entre logique et automates pour produire des analyseurs efficaces. Notre travail se situe dans ce dernier cadre. En s’appuyant sur plusieurs résultats existants en informatique théorique, nous proposons un outil de modélisation linguistique expressif, conçu pour faciliter l’ingénierie grammaticale. Celui-ci considère dans un premier temps la structure abstraite des énoncés, et fournit un langage logique s’appuyant sur les propriétés lexicales des mots pour caractériser avec concision l’ensemble des phrases grammaticalement correctes. Puis, dans un second temps, le lien entre ces structures abstraites et leurs représentations concrètes (en syntaxe et en sémantique) est établi par le biais de règles de linéarisation qui exploitent la logique et le lambda-calcul. Par suite, afin de valider cette approche, nous proposons un ensemble de modélisations portant sur des phénomènes linguistiques divers, avec un intérêt particulier pour le traitement des langages présentant des phénomènes d’ordre libre (c’est-à-dire qui autorisent la permutation de certains mots ou groupes de mots dans une phrase sans affecter sa signification), ainsi que pour leur complexité algorithmique. / The goal of computational linguistics is to provide a formal account linguistical knowledge, and to produce algorithmic tools for natural languageprocessing. Often, this is done in a so-called generative framework, where grammars describe sets of valid sentences by iteratively applying some set of rewrite rules. Another approach, based on model theory, describes instead grammaticality as a set of well-formedness logical constraints, relying on deep links between logic and automata in order to produce efficient parsers. This thesis favors the latter approach. Making use of several existing results in theoretical computer science, we propose a tool for linguistical description that is both expressive and designed to facilitate grammar engineering. It first tackles the abstract structure of sentences, providing a logical language based on lexical properties of words in order to concisely describe the set of grammaticaly valid sentences. It then draws the link between these abstract structures and their representations (both in syntax and semantics), through the use of linearization rules that rely on logic and lambda-calculus. Then in order to validate this proposal, we use it to model various linguistic phenomenas, ending with a specific focus on languages that include free word order phenomenas (that is, sentences which allow the free reordering of some of their words or syntagmas while keeping their meaning), and on their algorithmic complexity.

Cette thèse porte sur la classification et le traitement des invariants lexicaux arabes qui expriment un aspect temporel afin de créer un modèle qui présente chaque invariant sous la forme d’un schéma de grammaire (automates à états finis). Dans ce travail nous avons limité notre traitement seulement pour 20 invariants lexicaux. Notre hypothèse part du principe que les invariants lexicaux sont situés au même niveau structural (formel) que les schèmes dans le langage quotient (squelette) de la langue arabe. Ils cachent beaucoup d’informations et entraînent des attentes syntaxiques qui permettent de prédire la structure de la phrase.Au début de cette thèse, nous abordons la notion « invariant lexical » en exposant les différents niveaux d’invariance. Ensuite, nous classons les invariants étudiés dans cette thèse selon plusieurs critères.La deuxième partie de cette thèse fait l’objet de notre propre étude concernant les invariants lexicaux temporels dans laquelle nous commençons par une présentation de notre méthode d’étude linguistique ainsi que la modélisation par schémas de grammaires des invariants lexicaux temporels étudiés. Ensuite, nous abordons l’analyse proprement dite des invariants lexicaux simples comme « ḥattā, baʿda » et complexes comme « baʿdamā, baynamā ».Enfin, une application expérimentale « Kawâkib » a été employée pour détecter et identifier les invariants lexicaux en montrant leurs points forts aussi bien que leurs lacunes. Nous proposons également une nouvelle vision de la prochaine version de « Kawâkib » qui peut représenter une application pédagogique de l'arabe sans lexique. / This thesis focuses on the classification and the treatment of Arabic lexical invariants that express a temporal aspect. Our aim is to create a diagram of grammar (finite state machine) for each invariant. In this work, we limited our treatment to 20 lexical invariants. Our assumption is that the lexical invariants are located at the same structural level (formal) as the schemes in the language quotient (skeleton) of the Arabic language. They hide much information and involve syntactic expectations that make it possible to predict the structure of the sentence.In the first part of our research tasks, we present the concept of “invariant lexical” by exposing the various levels of invariance. Then, we classify the invariants according to several criteria.The second part is the object of our own study concerning the temporal lexical invariants. We present our linguistic method as well as our approach of modelling using diagrams of grammars. Then, we analyze the simple lexical invariants such “ḥattā, baʿda” and the complexes ones such “baʿdamā, baynamā”.Finally, an experimental application “Kawâkib” was used to detect and identify the lexical invariants by showing their strong points as well as their gaps. We also propose a new vision of the next version of “Kawâkib” that can represent a teaching application of Arabic without lexicon.

Nesta tese, que se propôs a explorar as gramáticas brasileiras do português publicadas no século XIX, tivemos três objetivos. O primeiro foi realizar um mapeamento exaustivo da produção gramatical brasileira do português do século XIX, o qual foi feito por meio de fontes secundárias e catálogos de bibliotecas. Tivemos conhecimento de 127 títulos e 77 reedições, o que resulta em duzentas gramáticas. A partir dos dados coletados, que, em geral, eram título, subtítulo, autor, ano de publicação, local e casa impressora, formalizamos unidades de análise para, ao relacioná-las, por meio da metodologia da História Serial (Furet 1991, Barros 2005), realizar um mapeamento descritivo e interpretativo dessa produção. Nosso segundo objetivo, tendo selecionado, com base em quatro critérios combinados (prestígio, emergência, institucionalização e diálogo), dezoito exemplares (16 títulos, 2 reedições) dos duzentos e quatro de que tivemos conhecimento, foi de realizar uma análise orientada para os conteúdos dessas obras, organizada em torno de uma possível rede conceitual. A hipótese dessa análise, baseada em Auroux (2009[1992]) e Swiggers (2010), é de que alguns conceitos poderiam ser eixo de uma rede conceitual devido à sua influência técnica e, eventualmente teórica, em uma determinada tradição de descrição linguística. Essa hipótese surgiu nos resultados de nossa pesquisa de mestrado, em que, ao notar a complexidade da dimensão técnica (cf. Swiggers 2004) de algumas obras dessa tradição, pensamos ser necessário procurar meios de tornar sua análise mais homogênea (cf. Polachini 2013, Polachini 2016). Para testá-la, examinamos o conceito-chave de \'verbo substantivo\' apresentado nas obras selecionadas, que são amiúde influenciadas pela tradição da grammaire générale francesa, ao menos até 1880, quando passa a haver também influência do método histórico-comparativo (cf. Maciel 1910, Nascentes 1939, Elia 1975, Cavaliere 2001, Parreira 2011, Polachini 2013). Ademais, foi necessário formalizar uma metodologia a fim de reconhecer a rede conceitual em torno do verbo substantivo. Primeiramente, definimos conceitos gramaticais como sendo formados por meio de processos classificatórios da cadeia falada. Tais processos têm como produto, por um lado, termos, e, por outro, conceitos. Estes últimos podem ser analisados intensionalmente, por meio de sua definição e seu lugar numa determinada taxonomia, ou extensionalmente, considerando o inventário de dados linguísticos eleitos como exemplos e eventuais ilustrações desses dados em uso. Cada conceito é, portanto, analisado por meio das seguintes categorias: definição, taxonomia, exemplos, ilustrações e por seus termos. Consideramos rede conceitual as relações travadas entre o conceito-chave, verbo substantivo, e conceitos que, na tradição da grammaire générale teriam já alguma relação com o verbo substantivo (cf. Chevalier 1968; Colombat 1992; Raby 2000; Bouard 2007), a saber: gramática e linguagem, metaclasses e classes de palavras, modificadores do nome, verbo, oração (seus elementos e sua organização) apresentadas nas obras. Essas relações podem ser de quatro tipos: (1) equivalência; (2) intersecção (3) subordinação; (4) base teórica comum. Finalmente, distinguimos no texto gramatical a descrição linguística, que chamamos de texto, e as ampliações, reflexões ou críticas realizadas sobre essa descrição, que chamamos de metatexto. Tal metodologia nos permitiu uma visão mais clara e homogênea da dimensão técnica das obras (e de seu eventual ecletismo), além de proporcionar uma visão mais complexa de continuidades e descontinuidades dessa produção, que contrasta com aquelas das revisões históricas. Ademais, os resultados apontam também para: relações entre agendas dos autores ao publicarem suas gramáticas e seu ecletismo. Nossa terceira proposta foi de que esta tese fosse não apenas uma historiografia, mas também uma epihistoriografia dessa tradição. Assim, apresentamos dois apêndices: um com informações catalográficas das 204 gramáticas de que tivemos conhecimento, organizadas cronologicamente; e outro com os paratextos das dezoito obras analisadas. / In this thesis, which approached the Brazilian grammars of Portuguese published in the 19th century, we had three objectives. The first one was to conduct a comprehensive mapping of the Brazilian grammatical production on Portuguese in the 19th century, which we carried out through secondary sources and library catalogs. We have acknowledged 127 titles and 77 re-editions, which total two hundred grammars. From the data collected, which generally consisted of title, subtitle, author, year published, publisher city and publisher name, we built standardized units of analysis so that, when analyzing their relations among one another, we conducted a descriptive and interpretative mapping of this production, adopting the methodology of Serial History (Furet 1991, Barros 2005). By selecting eighteen grammars (16 titles, 2 re-editions) out of the acknowledged two hundred works, based on four combined criteria (prestige, emergence, institutionalization and dialog), our second object was to carry out an analysis oriented to the content of these selected works, organized under a possible conceptual network. The hypothesis of this analysis, based on Auroux (2009[1992]) and Swiggers (2010), is that some concepts could work as an axis of a conceptual network due to their technical, and sometimes theoretical, influence on a specific tradition of linguistic description. This hypothesis was raised in the results of our masters research, in which, by realizing the complexity of some of this traditions grammars technical dimension (cf. Swiggers 2004), we thought it to be necessary to find ways of turning the analysis more homogeneous (cf. Polachini 2013, Polachini 2016). In order to test its effectiveness, we examined the key concept of verbo substantivo (literally: substantive verb), presented in the selected works, which are frequently influenced by the tradition of the French grammaire générale, at least until 1880, when the influence of the historical-comparative method started to take place (cf. Maciel 1910, Nascentes 1939, Elia 1975, Cavaliere 2001, Parreira 2011, Polachini 2013). Moreover, it was necessary to formalize a methodology in order to recognize the conceptual network around the verbo substantivo. First, we defined the grammatical concepts as being formed through classifying processes of spoken speech. These processes have as products, on one side, terms and, on the other, concepts. The latter can be analyzed intentionally, through its definition and its places in a specific taxonomy, or extensionally, considering the inventory of linguistic data considered as examples and any illustrations of these data in use. Each concept is, therefore, analyzed through the following categories: definition, taxonomy, examples, illustrations and by its terms. We considered as conceptual network the relations between the key concept, verbo substantivo, and concepts that, in the grammaire génerales tradition would already have some relation to the verbo substantivo (cf. Chevalier 1968; Colombat 1992; Raby 2000; Bouard 2007), such as: grammar and language, metaclasses and parts of speech, noun modifiers, verb, clause (its elements and organization) presented in the grammars. These relations can be of three types: (1) identity; (2) intersection; (3) subordination; (4) shared theoretical background. Finally, in the grammatical text, we distinguished the linguistic description, which we called text, from its expansions, reflections and critical comments on this description, which we called metatext. Such methodology allowed a clearer and more homogeneous view of the technical dimension of the works analyzed (and their often eclecticism), in addition to providing a more complex view of continuities and discontinuities of this production, which contrasts with those of the historical reviews. Furthermore, the results also point to: relations between the authors schedules when publishing their grammars and their eclecticism; and the metatexts role between teaching and linguistic reflection. Our third objective was to make this thesis not only a historiography but also a epihistoriography of this tradition. Thus, we presented two appendices: one with cataloging information of the two hundred grammars which we acknowledged, organized chronologically; and another one with the paratexts of the eighteen works analyzed.

Aujourd'hui, dans un monde globalisé, la conception des produits est en train de basculer vers la conceptiondistribuée multi-sites. En effet, la complexité des produits avec des contraintes économiques et d'ingénierie ontaccéléré la transformation et l'organisation des activités de conception en service-orientés dans un réseau distribué.Alors, la conception pour la configuration des produits émerge comme un outil efficace pour résoudre les nouveauxdéfis de la conception des produits. Beaucoup de recherches sur la conception pour la configuration considèrent leproblème de la conception pour la configuration uniquement comme un problème d'arrangement des composants.En effet, le processus de conception implique de multiple-métiers, la distribution des métiers et des acteurs, etl'interaction dans un environnement dynamique et incertain. De plus, nous pensons que la structure interne duprocessus de conception est une image homomorphe des discontinuités du produit perçu. En considérant l'espacede la conception pour la configuration comme multi vues, multi dimensionnels et incertain, cette thèse porte surl'étude de la conception pour la configuration comme un problème holistique.Nous avons proposé à étudier : (1) appréhender et modéliser la conception pour la configuration comme unproblème de recherche de consensus entre différents métiers ; (2) appréhender et modéliser les relations intra etinter domaines considérant la conception pour la configuration comme un problème holistique ; (3) formaliser lesgrammaires génératives pour la modélisation de produit dans les deux principaux espaces : fonctionnel et structurelet (4) modéliser les liens entre ces deux espaces à l'aide du concept d'holon de conception. A partir de cesconsidérations, nous établissons les hypothèses les plus importantes de notre recherche : (a) Hypothèse de multivues; (b) Hypothèse de flou ; (c) Hypothèse de dérivation ; (d) Hypothèse holistique et (e) Hypothèse d'attracteur.Nous avons décrit un modèle de conception pour la configuration dans lequel les aspects d'optimisation desconfigurations et la recherche des noyaux des configurations sont intégrés. D'ailleurs, nous avons proposé desgrammaires fonctionnelles floues graphes et des grammaires fonctionnelles floues formelles pour représentergraphiquement et formellement les structures fonctionnelles de produit. Nous avons aussi proposé une approche demodélisation holonique des configurations. Les concepts d'Holon Conception Floue et de l'Attracteur Flou sontproposés pour comprendre la coévolution dans la conception pour la configuration. Nous avons étudié un casindustriel de la conception pour la configuration à l'aide des modules pour un groupe motopropulseur / Product design is switching to the multi-site distributed design. Indeed, the complexity of products with engineeringand economic constraints have accelerated the transformation and organization of design activities into serviceorientedin a distributed network. So, design for product configuration emerges as an effective tool to address thenew challenges of product design. Many researches on design for configuration consider the design problem only asa problem of arrangement of components. Indeed, the design process involves multi-trades, distribution of tradesand actors, and interaction in a dynamic and uncertain environment. Moreover, we believe that the internal structureof the design process is a homomorphic image of the product perceived discontinuities. Considering the space ofthe design for the configuration as multi-views, multi-dimensional and uncertain, this thesis focuses on the study ofdesign for the configuration as a holistic problem.We proposed to study: (1) understand and model design for configuration as a consensus-building problem betweendifferent trades; (2) understand and model the relationships within and between domains considering the design forconfiguration as a holistic problem; (3) formalize the generative grammars for product modeling in two main spaces:functional and structural and (4) model the links between these two spaces with the concept of design holon. Fromthese considerations, we establish the most important assumptions of our research: (a) Assumption of multi-view;(b) Assumption of fuzzy; (c) Assumption of derivation; (d) Holistic assumption and (e) Assumption of attractor.We have described a design model for configuration wherein the optimization aspects of configurations andsearching of configurations cores are integrated. Moreover, we proposed fuzzy graphs functional grammars andformal fuzzy functional grammars to represent formally and graphically the functional structures of product. We alsoproposed an approach of holonic modeling for configurations. The concepts of Fuzzy Design Holon and FuzzyAttractor are proposed to understand the co-evolution in design for configuration. We studied an industrial case ofdesign for configuration using modules of a power train.

Context-free grammars are the most suitable and most widely used method for describing the syntax of programming languages. They can be used to generate parsers, which transform a piece of source code into a tree-shaped representation of the code's syntactic structure. These parse trees can then be used for further processing or analysis of the source text. In this sense, grammars form the basis of many engineering and reverse engineering applications, like compilers, interpreters and tools for software analysis and transformation. Unfortunately, context-free grammars have the undesirable property that they can be ambiguous, which can seriously hamper their applicability. A grammar is ambiguous if at least one sentence in its language has more than one valid parse tree. Since the parse tree of a sentence is often used to infer its semantics, an ambiguous sentence can have multiple meanings. For programming languages this is almost always unintended. Ambiguity can therefore be seen as a grammar bug. A specific category of context-free grammars that is particularly sensitive to ambiguity are character-level grammars, which are used to generate scannerless parsers. Unlike traditional token-based grammars, character-level grammars include the full lexical definition of their language. This has the advantage that a language can be specified in a single formalism, and that no separate lexer or scanner phase is necessary in the parser. However, the absence of a scanner does require some additional lexical disambiguation. Character-level grammars can therefore be annotated with special disambiguation declarations to specify which parse trees to discard in case of ambiguity. Unfortunately, it is very hard to determine whether all ambiguities have been covered. The task of searching for ambiguities in a grammar is very complex and time consuming, and is therefore best automated. Since the invention of context-free grammars, several ambiguity detection methods have been developed to this end. However, the ambiguity problem for context-free grammars is undecidable in general, so the perfect detection method cannot exist. This implies a trade-off between accuracy and termination. Methods that apply exhaustive searching are able to correctly find all ambiguities, but they might never terminate. On the other hand, approximative search techniques do always produce an ambiguity report, but these might contain false positives or false negatives. Nevertheless, the fact that every method has flaws does not mean that ambiguity detection cannot be useful in practice. This thesis investigates ambiguity detection with the aim of checking grammars for programming languages. The challenge is to improve upon the state-of-the-art, by finding accurate enough methods that scale to realistic grammars. First we evaluate existing methods with a set of criteria for practical usability. Then we present various improvements to ambiguity detection in the areas of accuracy, performance and report quality. The main contributions of this thesis are two novel techniques. The first is an ambi- guity detection method that applies both exhaustive and approximative searching, called AMBIDEXTER. The key ingredient of AMBIDEXTER is a grammar filtering technique that can remove harmless production rules from a grammar. A production rule is harmless if it does not contribute to any ambiguity in the grammar. Any found harmless rules can therefore safely be removed. This results in a smaller grammar that still contains the same ambiguities as the original one. However, it can now be searched with exhaustive techniques in less time. The grammar filtering technique is formally proven correct, and experimentally validated. A prototype implementation is applied to a series of programming language grammars, and the performance of exhaustive detection methods are measured before and after filtering. The results show that a small investment in filtering time can substantially reduce the run-time of exhaustive searching, sometimes with several orders of magnitude. After this evaluation on token-based grammars, the grammar filtering technique is extended for use with character-level grammars. The extensions deal with the increased complexity of these grammars, as well as their disambiguation declarations. This enables the detection of productions that are harmless due to disambiguation. The extentions are experimentally validated on another set of programming language grammars from practice, with similar results as before. Measurements show that, even though character-level grammars are more expensive to filter, the investment is still very worthwhile. Exhaustive search times were again reduced substantially. The second main contribution of this thesis is DR. AMBIGUITY, an expert system to help grammar developers to understand and solve found ambiguities. If applied to an ambiguous sentence, DR. AMBIGUITY analyzes the causes of the ambiguity and proposes a number of applicable solutions. A prototype implementation is presented and evaluated with a mature Java grammar. After removing disambiguation declarations from the grammar we analyze sentences that have become ambiguous by this removal. The results show that in all cases the removed filter is proposed by DR. AMBIGUITY as a possible cure for the ambiguity. Concluding, this thesis improves ambiguity detection with two novel methods. The first is the ambiguity detection method AMBIDEXTER that applies grammar filtering to substantially speed up exhaustive searching. The second is the expert system DR. AMBIGUITY that automatically analyzes found ambiguities and proposes applicable cures. The results obtained with both methods show that automatic ambiguity detection is now ready for realistic programming language grammars.

Model-driven software development requires techniques to consistently propagate modifications between different related models to realize its full potential. For large-scale models, efficiency is essential in this respect. In this paper, we present an improved model synchronization algorithm based on triple graph grammars that is highly efficient and, therefore, can also synchronize large-scale models sufficiently fast. We can show, that the overall algorithm has optimal complexity if it is dominating the rule matching and further present extensive measurements that show the efficiency of the presented model transformation and synchronization technique. / Die Model-getriebene Softwareentwicklung benötigt Techniken zur Übertragung von Änderungen zwischen verschiedenen zusammenhängenden Modellen, um vollständig nutzbar zu sein. Bei großen Modellen spielt hier die Effizienz eine entscheidende Rolle. In diesem Bericht stellen wir einen verbesserten Modellsynchronisationsalgorithmus vor, der auf Tripel-Graph-Grammatiken basiert. Dieser arbeitet sehr effizient und kann auch sehr große Modelle schnell synchronisieren. Wir können zeigen, dass der Gesamtalgortihmus eine optimale Komplexität aufweist, sofern er die Ausführung dominiert. Die Effizient des Algorithmus' wird durch einige Benchmarkergebnisse belegt.

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.