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.
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.
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).
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.
Grammaire non contextuelle déterministeEn informatique théorique, et particulièrement dans la théorie des grammaires formelles, les grammaires context-free déterministes ( DCFG ) ou grammaires non contextuelles déterministes sont un sous-ensemble des grammaires non contextuelles. Ce sont les grammaires non contextuelles qui peuvent être dérivées d'automates à pile déterministes, et ils engendrent les langages non contextuels déterministes. Les DCFG sont toujours inambigües et ils constituent une sous-classe importante des grammaires non contextuelles ; il existe cependant des CFG inambigües qui ne sont pas déterministes.
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.
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.
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.
S-expressionUne S-expression (ou expression symbolique) est une convention pour la représentation de données ou d'expressions d'un programme sous forme textuelle. Les S-expressions sont utilisées dans la famille de langages Lisp, incluant Scheme et , ainsi que comme métalangage dans des protocoles de communication tels IMAP ou le langage CBCL (Common Business Communication Language) de John McCarthy.
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).
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.
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).
Expression (mathématiques)In mathematics, an expression or mathematical expression is a finite combination of symbols that is well-formed according to rules that depend on the context. Mathematical symbols can designate numbers (constants), variables, operations, functions, brackets, punctuation, and grouping to help determine order of operations and other aspects of logical syntax. Many authors distinguish an expression from a formula, the former denoting a mathematical object, and the latter denoting a statement about mathematical objects.
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.
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.
Sémantique formelleEn linguistique, la sémantique formelle cherche à comprendre le sens (linguistique) en construisant des modèles mathématiques précis des principes utilisés par le locuteur pour définir la relation entre des expressions en langage naturel et l’environnement supportant un discours faisant sens. Les outils mathématiques utilisés sont une combinaison de logique mathématique et de langage formel théorique, plus particulièrement de lambda-calcul typé.
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.
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.
Equivalence (formal languages)In formal language theory, weak equivalence of two grammars means they generate the same set of strings, i.e. that the formal language they generate is the same. In compiler theory the notion is distinguished from strong (or structural) equivalence, which additionally means that the two parse trees are reasonably similar in that the same semantic interpretation can be assigned to both. Vijay-Shanker and Weir (1994) demonstrates that Linear Indexed Grammars, Combinatory Categorial Grammars, Tree-adjoining Grammars, and Head Grammars are weakly equivalent formalisms, in that they all define the same string languages.
Méthode formelle (informatique)En informatique, les méthodes formelles sont des techniques permettant de raisonner rigoureusement, à l'aide de logique mathématique, sur un programme informatique ou du matériel électronique numérique, afin de démontrer leur validité par rapport à une certaine spécification. Elles reposent sur les sémantiques des programmes, c'est-à-dire sur des descriptions mathématiques formelles du sens d'un programme donné par son code source (ou, parfois, son code objet).
