Un analyseur syntaxique performant adapt\'e aux grammaires $S$-attribu\'ees ambigu\"es

Notre motivation pour la cr\'eation d'un analyseur syntaxique performant vient d'un probl\`eme pos\'e par les biologistes~: la d\'etermination de structure secondaire d'un ARN. En cherchant \`a traiter ce probl\`eme en utilisant le formalisme des grammaires $S$-attribu\'ees (une extension simple des grammaires non-contextuelles), nous avons d\^u faire face \`a de nombreuses difficult\'es~: la n\'ecessit\'e de g\'erer un nombre d'arbres augmentant exponentiellement avec la taille des ARNs, l'inad\'equation des algorithmes classiques d'analyse syntaxique et la n\'ecessit\'e de rester comp\'etitifs avec les algorithmes actuels d'analyse d'ARNs dans certains cas particuliers. Nous avons donc \'et\'e conduits \`a d\'evelopper un algorithme plus performant que ce qui avait \'et\'e r\'ealis\'e auparavant dans ce domaine. Les r\'esultats obtenus sont encourageants puisque nous sommes plus rapides que les anciens algorithmes dans tous les cas de figure, avec parfois des \'ecarts importants en notre faveur, que ce soit en vitesse ou en taille m\'emoire.