Accueil
Equipe
Recherche
Logiciels
Démos
Publications
Projets
Collaborations
Rejoindre ATOLL
Actualités
Glossaire
Liens
Privé
Nous contacter

Les RCG («Range Concatenation Grammars»), introduites par Pierre Boullier, forment une très vaste hiérarchie de grammaires couvrant de manière uniforme la classe PTIME des formalismes grammaticaux analysables en temps et place polynomiaux. D'un point de vue linguistique, cette classe englobe les formalismes faiblement dépendants du contexte [MCS] dont les grammaires d'arbres adjoints [TAG] sont les plus illustres représentants et qui sont de plus en plus importants dans le traitement des langues. L'étude des RCG se poursuit suivant deux axes :

• Le premier axe est un travail formel qui porte d'une part sur ses propriétés intrinsèques et d'autre part sur la traduction d'autres formalismes grammaticaux vers une RCG équivalente. À notre avis, les RCG vont occuper une place essentielle dans la nébuleuse des formalismes linguistiques.
• Le second axe est la réalisation d'un système traitant les RCG. La version actuelle possède des performances extrêmement encourageantes. Nous avons par exemple comparé la vitesse de l'analyseur de l'anglais du système XTAG, référence mondiale pour le traitement des TAG, avec l'analyseur RCG produit à partir de la même grammaire. Nous avons noté des gains très importants, correspondant à priori à des gains de plusieurs ordres en complexité. Ce résultat reste cependant à analyser plus en détail.

Nous mettons en avant que l'analyse syntaxique peut être rendue plus simple en s'appuyant sur

1. des automates permettant le codage de diverses stratégies d'analyse
2. des interprétation en Programmation Dynamique des ces automates pour construire des analyseurs syntaxiques tabulaires.

Par tabulation, nous voulons dire que des traces de calculs sont stockées dans des tables afin de mieux gérer les ambiguités des langues (partage de calculs), de détecter les boucles (récursions) et d'extraire des forêts partagées de dérivation ou d'analyse.

L'introduction d'automates et d'interprétations facilite les preuves, facilite la compréhension des algorithmes et permet la conception de nouvelles stratégies d'analyse et de nouveaux systèmes d'évaluation tabulaire.

Cette approche a été formalisée pour les CFG avec les Push Down Automata [PDA], les grammaires d'unification (DCG) avec les Logical Push Down Automata [LPDA], et les Feature TAGs avec les 2-stack Automata [2SA].

Une implantation existe au travers du système DyALog.

Tree Adjoining Grammars are a very interesting class of linguistically motivated grammars introduced by Joshi. They are natural extensions of Context-Free Grammars and belong also to a larger class of formalisms parsable in polynomial space and time: Mildly Context Sensitive Grammars. They are also equivalent to Linear Indexed Grammars (LIG).

Tabular algorithms exist for TAGs and LIGs but are usually designed for a specific parsing strategy and have varying complexities. There also exist different kinds of automata useful for TAGs and LIGs, such as 2-stack automata [2SA] and Embedded Push-Down Automata [EPDA].

In a recent joint work, Miguel Alonso Pardo and Eric de la Clergerie have proposed a restricted class of 2-SA that may be used to describe a wide range of parsing strategies for TAGs and LIGs. A Dynamic Programming interpretation of these 2-SA exists that gives the best known time and space general complexity. A more specialized version has also been proposed for bottom-up strategies that reduce the space complexity (but not the time complexity).