[THL] Theorie des langages (1)

Compilateur

2 phases :

Etapes du compilateur

  1. Analyseur lexical : coupe le texte en token
  2. Verification syntaxique : verifie si la sequence est correcte
  3. Analyse semantique : analyse la sequence dans son contexte

THLR

Langage : ensemble de symboles (non ordonne)
(langage vide) {ε} (langage contenant le mot vide)

Mot : suite finie de symboles (eventuellement vide)

Alphabet Σ : caracterise par son cardinal (Nombre de symboles dans l’alphabet)
Σ* : ensemble de tous les mots possibles generes sur l’alphabet Σ

Operations sur des mots

Concatenation (Loi de composition interne)

u = abc
v = bcd
u.v = abcbcd
|u| + |v| = |uv|
element neutre : ε

Operations sur des langages

Concatenation

L1.L2 = prefixes dans L1, suffixes dans L2

Exemple
L1 = {ab, bc}, L2 = {bc, cd}
L1.L2 = {abbc, abcd, bcbc, bccd}





Prefixe

pref(abcaab) = {ε, a, ab, abc, abca, abcaa, abcaab}

Langage rationnel

Un langage rationnel est defini par les elements suivants

Et les operateurs suivants

Expressions rationnelles

Exemple L’expression devient