Grammaire non contextuelle déterministe

En 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. Les DCFG sont d'un grand intérêt pratique, car ils peuvent être analysés en temps linéaire et en fait un analyseur peut être généré automatiquement à partir de la grammaire par un générateur d'analyseurs. Ils sont donc largement utilisés en informatique. Diverses formes restreintes des DCFG peuvent être analysées par des analyseurs plus simples et moins gourmands en ressources, et sont donc souvent utilisées. Ces classes de grammaires sont désignées par le type d'analyseur qui les analyse, et les exemples paradigmatiques sont LALR, SLR et LL. Dans les années 1960, des recherches théoriques en informatique sur les expressions régulières et les automates finis ont conduit à établir que les grammaires non contextuelles sont équivalentes aux automates à pile. Les premiers langages de programmation étaient en cours de développement à l'époque (voir histoire des langages de programmation ) et l'écriture de compilateurs était difficile. L'utilisation de grammaires non contextuelles a permis d'automatiser la partie d'analyse du compilateur. Les grammaires non contextuelles déterministes étaient particulièrement utiles car elles pouvaient être analysées séquentiellement par un automate à pile déterministe, ce qui était une exigence en raison des contraintes de mémoire de l'ordinateur. En 1965, Donald Knuth a conçu les analyseurs LR (k) et a prouvé qu'il existe une grammaire LR (k) pour chaque langage déterministe non contextuel.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés (7)

Cours associés (5)

Séances de cours associées (18)

CS-320: Computer language processing

We teach the fundamental aspects of analyzing and interpreting computer languages, including the techniques to build compilers. You will build a working compiler from an elegant functional language in

BIO-468: Scientific literature analysis in computational molecular biology

The goal of this course is to learn to analyze a scientific paper critically, asking whether the data presented support the conclusions that are drawn. The analysis is presented in the form of a summa

BIOENG-451: Scientific literature analysis in neuroscience

The goal of this course is to learn to analyze a scientific paper critically, question if the data support the conclusions, and produce constructive referee reports in written or oral form. The papers

Grammaire non contextuelle déterministe

Grammaire formelle

Une 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).

Analyse Earley

En 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).

Grammaires sans contexte: Partie 2

Couvre les grammaires sans contexte, y compris la définition des symboles non terminaux et terminaux, les règles pour générer des chaînes, et le concept de dérivations.

Analyseur: CYK Algorithm

Explore les grammaires formelles, les algorithmes d'analyse, l'efficacité de l'algorithme CYK et la correction syntaxique dans le traitement du langage naturel.

Sémantique opérationnelle : Amyli Language CS-320: Computer language processing

Explore la sémantique opérationnelle et les relations inductives dans le langage Amyli.