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.
Grammaire non contextuelleEn 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 où est un symbole non terminal et est une chaîne composée de terminaux et/ou de non-terminaux. Le terme « non contextuel » provient du fait qu'un non terminal peut être remplacé par , sans tenir compte du contexte où il apparaît.
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.
Grammaire formelleUne grammaire formelle est un formalisme permettant de définir une syntaxe et donc un langage formel, c'est-à-dire un ensemble de mots admissibles sur un alphabet donné. La notion de grammaire formelle est particulièrement utilisée en programmation logique, compilation (analyse syntaxique), en théorie de la calculabilité et dans le traitement des langues naturelles (tout particulièrement en ce qui concerne leur morphologie et leur syntaxe).
Parsing expression grammarIn computer science, a parsing expression grammar (PEG) is a type of analytic formal grammar, i.e. it describes a formal language in terms of a set of rules for recognizing strings in the language. The formalism was introduced by Bryan Ford in 2004 and is closely related to the family of top-down parsing languages introduced in the early 1970s. Syntactically, PEGs also look similar to context-free grammars (CFGs), but they have a different interpretation: the choice operator selects the first match in PEG, while it is ambiguous in CFG.
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).
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.
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.
Grammaire ambigüeEn informatique théorique et en théorie des langages, une grammaire ambiguë ou ambigüe est une grammaire algébrique qui admet un mot avec deux dérivations gauches distinctes ou — de manière équivalente — deux arbres de dérivation distincts. L'ambiguïté ou l'inambiguïté est une propriété des grammaires, et non des langages. De nombreux langages admettent à la fois des grammaires ambiguës et inambigües, alors que d'autres ne possèdent que des grammaires ambiguës.
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.
Grammaire contextuelleUne grammaire contextuelle est une grammaire formelle dans laquelle les substitutions d'un symbole non terminal sont soumises à la présence d'un contexte gauche et d'un contexte droit. Elles sont plus générales que les grammaires algébriques. Les langages formels engendrés par les grammaires contextuelles sont les langages contextuels. Ils sont reconnus par les automates linéairement bornés. Les grammaires contextuelles ont été décrites par Noam Chomsky. Ce sont les grammaires de type 1 dans la hiérarchie de Chomsky.
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.
Arbre syntaxiqueUn arbre syntaxique est un arbre permettant de représenter la syntaxe d'un objet. En linguistique, l'arbre syntaxique représente la structure syntaxique d'une phrase. Le nombre de catégories morphosyntaxiques correspondent à des classes distributionnelles, c'est-à-dire à la place qu'elles occupent dans la phrase, sur l'axe syntagmatique. En fonction de son voisinage, chaque élément peut commuter avec un autre élément de même catégorie.
Analyse syntaxique ascendanteEn informatique, l'analyse syntaxique révèle la structure grammaticale d'un texte. C'est la première étape dans l'étude de son sens. À l'inverse de l'analyse descendante, l'analyse ascendante reconnaît d'abord les plus petites unités du texte (les unités lexicales) analysé avant d'en reconnaître la structure grammaticale en le confrontant à des règles de syntaxe.
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).
Hiérarchie de Chomskyvignette|Hiérarchie de Chomsky. En informatique théorique, en théorie des langages, et en calculabilité, la hiérarchie de Chomsky (parfois appelée hiérarchie de Chomsky-Schützenberger) est une classification des grammaires formelles (et par extension, des langages formels respectifs engendrés par les grammaires), esquissée par Noam Chomsky en 1956, et décrite de façon formelle en 1959. La hiérarchie introduite par Noam Chomsky repose sur le modèle de grammaire formelle.
Chart parserIn computer science, a chart parser is a type of parser suitable for ambiguous grammars (including grammars of natural languages). It uses the dynamic programming approach—partial hypothesized results are stored in a structure called a chart and can be re-used. This eliminates backtracking and prevents a combinatorial explosion. Chart parsing is generally credited to Martin Kay. A common approach is to use a variant of the Viterbi algorithm. The Earley parser is a type of chart parser mainly used for parsing in computational linguistics, named for its inventor.
Langage algébriqueEn théorie des langages formels, un langage algébrique ou langage non contextuel est un langage qui est engendré par une grammaire algébrique. De manière équivalente, un langage algébrique est un langage reconnu par un automate à pile. Les langages algébriques forment les langages de dans la hiérarchie de Chomsky. Ils ont des applications importantes dans la description des langages de programmation et en linguistique. Ils interviennent également dans la description des langages XML.
Expression régulièrevignette|Stephen Cole Kleene, dont les travaux ont fondé le concept d'expression régulière. En informatique, une expression régulière ou expression rationnelle ou expression normale ou motif est une chaîne de caractères qui décrit, selon une syntaxe précise, un ensemble de chaînes de caractères possibles. Les expressions régulières sont également appelées regex (un mot-valise formé depuis l'anglais regular expression). Les expressions rationnelles sont issues des théories mathématiques des langages formels des années 1940.
Probabilistic context-free grammarGrammar theory to model symbol strings originated from work in computational linguistics aiming to understand the structure of natural languages. Probabilistic context free grammars (PCFGs) have been applied in probabilistic modeling of RNA structures almost 40 years after they were introduced in computational linguistics. PCFGs extend context-free grammars similar to how hidden Markov models extend regular grammars. Each production is assigned a probability.
