Phrase structure rulesPhrase structure rules are a type of rewrite rule used to describe a given language's syntax and are closely associated with the early stages of transformational grammar, proposed by Noam Chomsky in 1957. They are used to break down a natural language sentence into its constituent parts, also known as , including both lexical categories (parts of speech) and phrasal categories. A grammar that uses phrase structure rules is a type of phrase structure grammar.
Langage formelUn langage formel, en mathématiques, en informatique et en linguistique, est un ensemble de mots. L'alphabet d'un langage formel est l'ensemble des symboles, lettres ou lexèmes qui servent à construire les mots du langage ; souvent, on suppose que cet alphabet est fini. La théorie des langages formels a pour objectif de décrire les langages formels. Les mots sont des suites d'éléments de cet alphabet ; les mots qui appartiennent à un langage formel particulier sont parfois appelés mots bien formés ou formules bien formées.
Recursive descent parserIn computer science, a recursive descent parser is a kind of top-down parser built from a set of mutually recursive procedures (or a non-recursive equivalent) where each such procedure implements one of the nonterminals of the grammar. Thus the structure of the resulting program closely mirrors that of the grammar it recognizes. A predictive parser is a recursive descent parser that does not require backtracking.
Noncontracting grammarIn formal language theory, a grammar is noncontracting (or monotonic) if for all of its production rules, α → β (where α and β are strings of nonterminal and terminal symbols), it holds that |α| ≤ |β|, that is β has at least as many symbols as α. A grammar is essentially noncontracting if there may be one exception, namely, a rule S → ε where S is the start symbol and ε the empty string, and furthermore, S never occurs in the right-hand side of any rule.
Forme de Backus-NaurLa forme de Backus-Naur (souvent abrégée en BNF, de l'anglais Backus-Naur Form) est une notation qui permet d'écrire les règles des langages informatiques (notamment des langages de programmation). C’est donc un métalangage employé pour définir inductivement un langage. Elle est utilisée dans certains livres pour décrire le langage étudié, mais également par de nombreux logiciels d’analyse syntaxique pour travailler sur des fichiers sources de plusieurs langages différents.
Grammaire régulièreEn informatique théorique, en théorie des langages, une grammaire régulière, rationnelle ou à états finis est une grammaire hors-contexte particulière qui décrit un langage régulier. Les grammaires régulières donnent donc une autre possibilité que les expressions rationnelles et les automates finis pour décrire un langage régulier. Une grammaire régulière peut être « à gauche » ou « à droite ». Une grammaire régulière à gauche est un ensemble de règles de la forme : où , sont des symboles non-terminaux et un symbole terminal.
Lemme d'itération pour les langages algébriquesLe lemme d'itération pour les langages algébriques, aussi connu sous le vocable lemme de Bar-Hillel, Perles et Shamir, donne une condition de répétition nécessaire pour les langages algébriques. Sa version simplifiée pour les langages rationnels est le lemme de l'étoile. Une version plus élaborée du lemme d'itération est le lemme d'Ogden. Le lemme indique donc que, dans un langage algébrique, certains facteurs de mots assez longs peuvent être itérés de concert.
Traitement automatique du langage naturelLe traitement automatique du langage naturel (TALN), en anglais natural language processing ou NLP, est un domaine multidisciplinaire impliquant la linguistique, l'informatique et l'intelligence artificielle, qui vise à créer des outils de traitement du langage naturel pour diverses applications. Il ne doit pas être confondu avec la linguistique informatique, qui vise à comprendre les langues au moyen d'outils informatiques.
Top-down parsingTop-down parsing in computer science is a parsing strategy where one first looks at the highest level of the parse tree and works down the parse tree by using the rewriting rules of a formal grammar. LL parsers are a type of parser that uses a top-down parsing strategy. Top-down parsing is a strategy of analyzing unknown data relationships by hypothesizing general parse tree structures and then considering whether the known fundamental structures are compatible with the hypothesis.
Phrase structure grammarThe term phrase structure grammar was originally introduced by Noam Chomsky as the term for grammar studied previously by Emil Post and Axel Thue (Post canonical systems). Some authors, however, reserve the term for more restricted grammars in the Chomsky hierarchy: context-sensitive grammars or context-free grammars. In a broader sense, phrase structure grammars are also known as constituency grammars. The defining trait of phrase structure grammars is thus their adherence to the constituency relation, as opposed to the dependency relation of dependency grammars.
Complexité en tempsEn algorithmique, la complexité en temps est une mesure du temps utilisé par un algorithme, exprimé comme fonction de la taille de l'entrée. Le temps compte le nombre d'étapes de calcul avant d'arriver à un résultat. Habituellement, le temps correspondant à des entrées de taille n est le temps le plus long parmi les temps d’exécution des entrées de cette taille ; on parle de complexité dans le pire cas. Les études de complexité portent dans la majorité des cas sur le comportement asymptotique, lorsque la taille des entrées tend vers l'infini, et l'on utilise couramment les notations grand O de Landau.
Forme normale de GreibachEn informatique théorique, et notamment en théorie des langages formels, une grammaire algébrique est en forme normale de Greibach (en anglais, Greibach normal form ou GNF) si les membres droits de ses règles commencent tous par un symbole terminal, suivi éventuellement d'une ou plusieurs variables. Une variante permet une règle additionnelle pour engendrer le mot vide s'il fait partie du langage. Cette forme normale porte le nom de Sheila Greibach qui l'a introduite et a prouvé son existence.
