Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Séance de cours

Grammaires sans contexte: Partie 2

Description

Cette séance de cours 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. Il explore également l'utilisation d'automates et d'opérations de pile dans le contexte des grammaires.

Source officielle

Concepts associés (13)

Grammaire non contextuelle

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

Langage algébrique

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

Grammaire contextuelle

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

Grammaire ambigüe

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

Afficher plus

Séances de cours associées (32)

Grammaires sans contexte

Couvre les grammaires sans contexte, leur équivalence avec les automates pushdown et la hiérarchie des types de grammaire.

Grammaires sans contexte: Partie 1

Couvre les grammaires sans contexte, les règles de production, les automates, l'analyse syntaxique et les techniques d'analyse.

CYK Algorithme pour l'analyse des grammaires générales

Explore l'analyse des grammaires générales à l'aide de l'algorithme CYK et de Chomsky Normal Form.

Introduction aux grammaires

Introduit des automates, des limitations de langues régulières, des grammaires sans contexte et des grammaires équilibrées entre parenthèses.

CYK Parsing Algorithme pour les grammaires générales

Introduit l'algorithme d'analyse CYK pour les grammaires sans contexte, expliquant sa gestion de l'ambiguïté et de l'importance dans l'analyse des grammaires générales.

Afficher plus

Concepts associés (13)

Grammaire non contextuelle

Langage algébrique

Grammaire contextuelle

Grammaire ambigüe

Grammaire non contextuelle déterministe

Afficher plus