Forme normale de ChomskyEn informatique théorique, et notamment en théorie des langages, une grammaire non contextuelle est en forme normale de Chomsky si et seulement si toutes ses règles de production sont de la forme : ou ; ou où sont des symboles non terminaux, est un symbole terminal, est l'axiome de la grammaire, et est le mot vide. Si la dernière règle est présente, il est demandé que l'axiome n'apparaisse jamais dans le membre droit d'une règle.
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.
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).
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.
Grammaire attribuéeUne grammaire attribuée est une manière formelle de définir des attributs pour les productions d'une grammaire, associant ces attributs à des valeurs. L'évaluation a lieu dans les nœuds de l'arbre syntaxique abstrait quand le langage est traité par un analyseur syntaxique ou un compilateur. Les attributs sont divisés en deux groupes : les attributs synthétisés et les attributs hérités. Les attributs synthétisés sont le résultat des règles d'évaluation des attributs ; ils peuvent aussi utiliser les valeurs d'attributs hérités.
Arbre de la syntaxe abstraiteEn informatique, un arbre de la syntaxe abstraite ou ASA (abstract syntax tree, ou AST, en anglais) est un arbre dont les nœuds internes sont marqués par des opérateurs et dont les feuilles (ou nœuds externes) représentent les opérandes de ces opérateurs. Autrement dit, généralement, une feuille est une variable ou une constante. Un arbre de la syntaxe abstraite est utilisé par un analyseur syntaxique comme un intermédiaire entre un arbre d'analyse et une structure de données.
PalindromeLe palindrome (adjectif et substantif masculin), du grec / pálin (« en arrière ») et / drómos (« chemin, voie »), aussi appelé palindrome de lettres est une figure de style désignant un mot ou une phrase dont l'ordre des lettres reste le même qu'on les lise de gauche à droite ou de droite à gauche, comme dans la phrase ou encore à un accent près. Le palindrome est un cas particulier d'anacyclique (lequel est lui-même un cas particulier d'anagramme) comme « suce|écus », pour lequel la signification est la même dans les deux sens de lecture.
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.
Generalized phrase structure grammarGeneralized phrase structure grammar (GPSG) is a framework for describing the syntax and semantics of natural languages. It is a type of constraint-based phrase structure grammar. Constraint based grammars are based around defining certain syntactic processes as ungrammatical for a given language and assuming everything not thus dismissed is grammatical within that language. Phrase structure grammars base their framework on constituency relationships, seeing the words in a sentence as ranked, with some words dominating the others.
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.
