Abstract FR:

Le but est de proposer des algorithmes de calcul de forêts d'analyse décorées par des attributs vérifiant la structure algébrique de demi-anneau et applicables à différents formalismes de la linguistique calculatoire. Le point de départ est l'analyse syntaxique non-contextuelle générale (incluant donc les grammaires ambiguës). Une stratégie d'analyse est présentée sous la forme d'un automate à pile non-déterministe, qui est ensuite interprété par programmation dynamique. Cette technique s'applique sur des calculs récursifs à condition que chaque sous-calcul puisse être identifié par un indice. Le mécanisme consiste à tabuler les résultats, en n'effectuant chaque sous-calcul qu'une fois. Il en résulte une complexité (en temps et en espace) cubique pour les algorithmes de reconnaissance syntaxique. Cette méthode est étendue à l'analyse stochastique, pour laquelle nous proposons une généralisation des théorèmes d'adéquation entre les calculs opérationnels de probabilités et leur définition par la grammaire probabiliste. Les quantités calculées sont les probabilités de préfixe, de sous-chaîne, et le calcul du meilleur arbre. Quatre stratégies sont présentées : earley, left corner, lr et extended lr. La théorie des séries de puissance algébriques est utilisée pour formaliser la décoration d'une grammaire dans un demi-anneau abstrait. L’analyse s'exprime alors comme le calcul du coefficient d'un mot pour la série formelle définie par la grammaire décorée, ce qui revient à résoudre un système d'équations au point fixe. Nous donnons des conditions qui assurent la solvabilité du système, et montrons qu'on peut le résoudre en utilisant la programmation dynamique. Les quatre algorithmes stochastiques sont alors reformulés pour calculer une décoration dans un demi-anneau abstrait. Enfin nous montrons que les grammaires de clauses définies et les grammaires à structure de traits peuvent être décrites comme des grammaires non-contextuelles décorées dans un demi-anneau.