Séance de cours

Grammaires sans contexte: Partie 1

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Description

Cette séance de cours introduit des grammaires sans contexte, mettant l'accent sur les symboles non terminaux, les règles de production et les automates. Il couvre la définition formelle des grammaires sans contexte et leur rapport à la théorie des automates, en mettant l'accent sur la génération des langues. La séance de cours traite également de l'analyse syntaxique des grammaires sans contexte, y compris les techniques d'analyse et la hiérarchie Chomsky.

Source officielle

Proximité ontologique

Génie informatique

Programmation informatique: Compilateur

Concepts associés (32)

Analyse syntaxique

L' 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 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.

Probabilistic context-free grammar

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

Afficher plus

Séances de cours associées (49)

Sémantique opérationnelle : Amyli Language

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

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.

Fondements du logiciel: Modélisation des langages de programmation

Couvre l'étude mathématique des comportements de programme, l'analyse, les langages spécifiques à un domaine et les outils puissants de conception de langage.

Grammaires et analyseurs: un aperçu du traitement du langage

Fournit une vue d'ensemble des grammaires et des analyseurs dans le traitement du langage informatique.

Compilateurs : défis avec les processeurs de signaux numériques

Couvre les défis de la compilation pour les processeurs de signaux numériques en raison de leurs caractéristiques architecturales uniques et des irrégularités.

Afficher plus

Concepts associés (32)

Analyse syntaxique

Grammaire non contextuelle

Langage algébrique

Grammaire contextuelle

Probabilistic context-free grammar

Afficher plus