Grammaire d'arbres adjointsLa grammaire d'arbres adjoints, grammaire TAG, ou légèrement sensible au contexte, est un formalisme d'analyse grammaticale introduit par Aravind K. Joshi et ses collègues en 1975. Ce formalisme a été utilisé à différentes fins, et particulièrement en linguistique formelle et informatique pour le traitement de la syntaxe des langues naturelles. Historiquement, il a d'abord permis de représenter de manière directe des dépendances à longue distance et il permet également de représenter les dépendances croisées du suisse allemand et du flamand occidental, phénomène qui ne peut se traiter avec une grammaire de réécriture hors contexte, comme l'a montré S.
Analyse syntaxiqueL' consiste à mettre en évidence la structure d'un texte, généralement une phrase écrite dans une langue naturelle, mais on utilise également cette terminologie pour l'analyse d'un programme informatique. L' (parser, en anglais) est le programme informatique qui réalise cette tâche. Cette opération suppose une formalisation du texte, qui est vue le plus souvent comme un élément d'un langage formel, défini par un ensemble de règles de syntaxe formant une grammaire formelle.
Analyseur LRComme tout analyseur grammatical (ou analyseur syntaxique), un analyseur LR vise à vérifier si une chaîne de caractères (typiquement contenue dans un fichier) possède bien la structure d'une grammaire spécifiée à l'avance. Cette vérification s'accompagne généralement d'actions. Une action typique est la génération d'une autre chaîne de caractères ou encore d'un arbre d'analyse. Ainsi l'analyse grammaticale est généralement utilisée pour la compilation (transformation d'un code source en code machine).
Analyse EarleyEn théorie des langages, l'algorithme d'Earley est un algorithme d'analyse syntaxique pour les grammaires non contextuelles décrit pour la première fois par Jay Earley. À l'instar des algorithmes CYK et GLR, l'algorithme d'Earley calcule toutes les analyses possibles d'une phrase (et pas seulement une de ces analyses). Il repose sur de la programmation dynamique. On peut construire un analyseur Earley pour toute grammaire non contextuelle. Il s'exécute en temps cubique (O (n3), où n est la longueur de la chaîne d'entrée).
Shift-reduce parserA shift-reduce parser is a class of efficient, table-driven bottom-up parsing methods for computer languages and other notations formally defined by a grammar. The parsing methods most commonly used for parsing programming languages, LR parsing and its variations, are shift-reduce methods. The precedence parsers used before the invention of LR parsing are also shift-reduce methods. All shift-reduce parsers have similar outward effects, in the incremental order in which they build a parse tree or call specific output actions.
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.
Combinateur d'analyseursEn programmation informatique, un combinateur d'analyseurs est une fonction d'ordre supérieur qui accepte plusieurs analyseurs en entrée et renvoie un nouvel analyseur en sortie. Dans ce contexte, un analyseur est une fonction acceptant des chaînes en entrée et renvoyant une structure en sortie, généralement un arbre d'analyse ou un ensemble d'indices représentant les emplacements dans la chaîne où l'analyse s'est arrêtée avec succès.
Definite clause grammarA definite clause grammar (DCG) is a way of expressing grammar, either for natural or formal languages, in a logic programming language such as Prolog. It is closely related to the concept of attribute grammars / affix grammars from which Prolog was originally developed. DCGs are usually associated with Prolog, but similar languages such as Mercury also include DCGs. They are called definite clause grammars because they represent a grammar as a set of definite clauses in first-order logic.
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.
