Grammaire non contextuelle

Résumé

En linguistique et en informatique théorique, une grammaire algébrique, ou grammaire non contextuelle, aussi appelée grammaire hors-contexte ou grammaire « context-free » est une grammaire formelle dans laquelle chaque règle de production est de la forme :X\to \alpha où X est un symbole non terminal et \alpha est une chaîne composée de terminaux et/ou de non-terminaux. Le terme « non contextuel » provient du fait qu'un non terminal X peut être remplacé par \alpha, sans tenir compte du contexte où il apparaît. Un langage formel est non contextuel (ou hors contexte, ou encore algébrique) s'il existe une grammaire non contextuelle qui l'engendre. Par opposition est contextuelle une règle de la forme c~+X\to c+\alpha en raison de la partie gauche de la règle qui stipule un contexte pour X. Une telle règle signifie que X, dans le cas (contexte) où il est précédé du symbole terminal c et du littéra

Source officielle

https://fr.wikipedia.org/wiki/Grammaire_non_contextuelle

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (6)

Publications associées

Chargement

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés (48)

Concepts associés

Chargement

Cours associés (10)

Cours associés

Chargement

Séances de cours associées (26)

Séances de cours associées

Chargement

Grammar-based compression means to find a small grammar that generates a given object. Such a grammar reveals the structure of the object (according to the grammar formalism used); the main advantage of this compression method is that the resulting grammar can often be used in further computations without prior decompression. A linear time bottom-up algorithm is presented which transforms a tree into a particular context-free tree grammar. For common XML documents the algorithm performs well, compressing the tree structure to about 5 per cent of the original size. The validation of an XML document against an XML type can be done without decompression, in linear time w.r.t. the size of the grammar (for a fixed type). While the involved grammars can be double exponentially smaller than the represented trees, testing them for equivalence can be done in polynomial space w.r.t. the sum of their sizes.

2004

Chargement

This document gives information on parsing experiments applied to the standard Wall Street Journal corpus (``Standard'' means that this corpus has been widely used for exhibiting parsing tests of various models). The tested syntactic models are : standard Stochastic Context-Free Grammars, standard Tree Substitution Grammars, Gibbsian Context-Free Grammars and Gibbsian Tree Substitution Grammars. The parsing experiments are described with deep details so as to enable reader to easily redo the experiments from scratch (i.e. preparing the database, training and evaluating the models). The programs developped for these experiments are also described.

2004

Chargement

Modèles syntaxiques probabilistes non-génératifs

Antoine Rozenknop

This work deals with models used, or usable in the domain of Automatic Natural Language Processing, when one seeks a syntactic interpretation of a statement. This interpretation can be used as additional information for subsequent treatments, that can aim for instance at producing a semantic representation of the statement. It can also be used as a filter to select utterances belonging to a specific language, among several hypotheses, as done in Automatic Speech Recognition. As the syntactic interpretation of a statement is generally ambiguous with natural languages, the probabilisation of the space of syntactic trees can help in the analysis task : when several analyses are competing, one can then extract the most probable interpretation, or classify interpretations according to their probabilities. We are interested here in the probabilistic versions of Context-Free Grammars (PCFGs) and Substitution Tree Grammar (PTSGs). Syntactic treebanks, which as much as possible account for the language we wish to model, serve as the basis for defining the probabilistic parameters of such grammars. First, we exhibit in this thesis some drawbacks of the usual learning paradigms, due to the use of arbitrary heuristics (STSG DOP model), or to the use of learning criteria that consider these grammars as generative ones (creation of sentences from the grammar) rather than dedicated to analysis (creation of analyses from the sentence). In a second time, we propose new methods for training grammars, based on the traditional Maximum Entropy and Maximum Likelihood criteria. These criteria are instanciated so that they correspond to a syntactic analysis task rather than a language generation task. Specific training algorithms are necessary for their implementation, but traditional algorithms can cope with those models for the task of syntactic analysis. Lastly, we invest the problem of time complexity of syntactic analysis, which is a real issue for the effective use of PTSGs. We describe classes of PTSGs that allow the analysis of a sentence in polynomial complexity. We finally describe a method that enable the extraction of such a PTSG from the set of subtrees of a treebank. The PTSG produced by this method allows us to test our non-generative learning criterium on "realistic" data, and to give a statistical comparison between this criterium and the usual heuristic criterium in term of analysis performance.

EPFL2003

Chargement

Modèles syntaxiques probabilistes non-génératifs

Antoine Rozenknop

EPFL2003