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

Introduction aux grammaires

Dans cours

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 into machine code using a popular backend called LLVM (htt ...

Description

Cette séance de cours couvre le pouvoir expressif des automates, les limites des langues régulières, le pompage du lemme et la transition des automates à états finis vers des grammaires sans contexte. Il présente des grammaires sans contexte, des arbres d'analyse, des dérivations grammaticales et fournit des exemples de grammaires équilibrées entre parenthèses.

Enseignant·e

Viktor Kuncak

Viktor Kunčak joined EPFL in 2007, after receiving a PhD degree from MIT. Since then has been leading the Laboratory for Automated Reasoning and Analysis and supervised at least 12 completed PhD theses. His works on languages, algorithms and systems for verification and automated reasoning. He served as an initiator and one of the coordinators of a European network (COST action) in the area of automated reasoning, verification, and synthesis. In 2012 he received a 5-year single-investigator European Research Council (ERC) grant of 1.5M EUR. His invited talks include those at Lambda Days, Scala Days, NFM, LOPSTR, SYNT, ICALP, CSL, RV, VMCAI, and SMT. A paper on test generation he co-authored received an ACM SIGSOFT distinguished paper award at ICSE. A PLDI paper he co-authored was published in the Communications of the ACM as a Research Highlight article. His Google Scholar profile reports an over-approximate H-index of 38. He was an associate editor of ACM Transactions on Programming Languages and Systems (TOPLAS) and served as a co-chair of conferences on Computer-Aided Verification (CAV), Formal Methods in Computer Aided Design (FMCAD), Workshop on Synthesis (SYNT), and Verification, Model Checking, and Abstract Interpretation (VMCAI). At EPFL he teaches courses on functional and parallel programming, compilers, and verification. He has co-taught the MOOC "Parallel Programming" that was visited by over 100'000 learners and completed by thousands of students from all over the world.

Source officielle

Proximité ontologique

Génie informatique

Programmation informatique: Compilateur

Concepts associés (32)

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.

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.

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

Arbre syntaxique

Un arbre syntaxique est un arbre permettant de représenter la syntaxe d'un objet. En linguistique, l'arbre syntaxique représente la structure syntaxique d'une phrase. Le nombre de catégories morphosyntaxiques correspondent à des classes distributionnelles, c'est-à-dire à la place qu'elles occupent dans la phrase, sur l'axe syntagmatique. En fonction de son voisinage, chaque élément peut commuter avec un autre élément de même catégorie.

Afficher plus

Séances de cours associées (32)

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.

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.

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.

Arbre syntaxique : Parse vs AST

Explique les arbres syntaxiques, l'analyse vs AST, tandis que la syntaxe du langage, les classes AST et les ambiguïtés grammaticales.

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.

Afficher plus

Concepts associés (32)

Grammaire non contextuelle

Grammaire ambigüe

Analyse syntaxique

Grammaire contextuelle

Arbre syntaxique

Afficher plus