 |
Automates et grammaires
|
Bibliographie succinte
- Concepts fondamentaux de l'informatique (Aho, Ullman)
- Compilers: principles, techniques and tools (Aho, Sethi, Ullman)
Plan de cours rapide
- Définition formelle d'un langage: alphabet, symboles, mot,
concaténation
- Expressions rationnelles classiques d'Unix
- Définition récursive des langages rationnels, exemple.
- L'analyse lexicale, un outil sous Unix: lex.
- Définition des automates: états, transitions.
- Langage reconnaissable, automates déterministes ou non
déterministes.
- Construction d'un automate non déterministe à partir d'un
langage rationnel.
- Un exemple de langage non rationnel: les mots bien parenthésés
(dits mots de Dyck).
A suivre:
- Utilisation des automates: l'algorithme de Knuth-Morris-Pratt.
- Construction d'un DFA à partir d'un NFA
- Construction d'une expression régulière à partir d'un automate.
- Grammaires et langages algébriques.
Exemples
- Le module d'analyse lexicale du programme Unix
bc,
un petit calculateur: scan.l
(on remarquera l'utilisation de la notation
<comment> pour noter explicitement des états
d'automate, allié à BEGIN(comment) pour forcer le passage
dans un état).
Retour page d'accueil
Copyright (C) 2003 Epita
$Id: index.html,v 1.1.1.1 2003/12/11 12:20:27 apache Exp $