INFO416 - Compilation 2017-2018
INFO416 - Compilation 2017-2018
INFO416 - Compilation 2017-2018
1 Généralités
2 Grammaires formelles
3 Automates à pile
Objectif
Comprendre le fonctionnement des langages (formel), vus comme
moyen de communication, d’un point de vue mathématique.
Algorithmes, Programmes, etc.
Exemples
Alphabet Mots Langages
Σ = {0, 1}, , 0, 1, 00, 01 {, 0, 1, 00, 01}, {}, ∅
{a, b, c, . . . , z}, salut, patron {salut, patron, }
{α, β, γ, δ, µ, ν, π, σ, η}, ηγαµ {, ηγαµ}
Notation
Nous utiliserons habituellement des notations conventionnelles :
Notation Exemple
Alphabet : Σ Σ = {0, 1}
Mot : a, b, c, . . . x = 00011
Langage : L, L1 , . . . L = {, 00, 11, µ}
Quelques concepts
La notion de grammaire (formelle) qui définit la syntaxe d’un
langage,
La notion d’automate permettant de déterminer si un mot fait
partie d’un langage (et donc permettant également de définir un
langage (l’ensemble des mots acceptés)), constituant ainsi son
lexique,
La notion d’expression régulière qui permet de dénoter un
langage.
Motivations théoriques
Liées aux théories de
la calculabilité (qui détermine en particulier quels problèmes sont
solubles par un ordinateur)
la complexité qui étudie les ressources (principalement temps et
espace mémoire) requises pour résoudre un problème donné
Pour C = f (LC , LS → LO )
LC LS LO
C Assembleur RISC Assembleur RISC
C C Assembleur P7
C Java C
Java LateX HTML
C XML PDF
Compilateur Vs Interprète
Interpréteur = outil qui analyse, traduit, mais aussi exécute un
programme écrit dans un langage informatique.
L’interpréteur se charge donc également de l’exécution au fur et à
mesure de son interprétation.
Compilateur monolithique
les premiers compilateurs étaient monolitiques : ils pouvaient
travailler en 1 seule passe (les langages étaient encore simples)
autant de compilateurs que de couples (langage, machine cible),
soit m × n
Efficacité
Robustesse
Portabilité
Fiabilité
Code debuggable
A une passe
A n passes (70 pour un compilateur PL/I !)
Optimisant
Natif
Cross-compilation
Exemple
Analyse lexicale (Scanning)
Définition (Unité lexicale (ou token))
Type générique d’éléments lexicaux (correspond à un ensemble de
strings ayant une sémantique proche).
Exemple : identificateur, opérateur relationnel, mot clé "begin"...
Phase de synthèse
Pour un langage impératif, la synthèse comporte les 3 phases
1 Génération de code intermédiaire sous forme de langage
universel qui
utilise un adressage symbolique
utilise des opérations standard
effectue l’allocation mémoire (résultat dans des variables
temporaires...)
2 Optimisation du code
supprime le code "mort"
met certaines instructions hors des boucles
supprime certaines instructions et optimise les accès à la mémoire
3 Production du code final
Allocation de mémoire physique
gestion des registres
temp1 ← 15.5
temp2 ← Int2Real(id3)
temp2 ← temp1 ∗ temp2
temp3 ← id2
temp3 ← temp3 + temp2
id1 ← temp3
2 Optimisation du code
temp1 ← Int2Real(id3)
temp1 ← 15.15 ∗ temp1
id1 ← id2 + temp1
3 Production du code final
temp1 ← Int2Real(id3)
temp1 ← 15.15 ∗ temp1
id1 ← id2 + temp1
3 Production du code final
MOVF id3, R1
ITOR R1
MULF 15.15, R1, R1
ADDF id2, R1, R1
STO R1, id1
1 Généralités
2 Grammaires formelles
3 Automates à pile
Dérivation
Les ensembles de symboles Vt et Vn doivent être disjoints
Seuls les symboles terminaux formes les mots du langage
Les symboles non-terminaux sont là juste pour aider à générer le
langage
a génération du langage commence toujours par le symbole de
départ S
Remarque
Souvent, les lettres grecques sont utilisées pour désigner les chaînes
construites d’éléments terminaux ou non terminaux comme dans la
production précédente.
Dérivation
La grammaire G permet de dériver v de u en une étape (notation
u ⇒ v ) si et seulement si :
u = xu 0 y (u peut être décomposé en trois parties x, u’ et y ; les
parties x et y peuvent éventuellement être vides),
v = xv 0 y (v peut être décomposé en trois parties x, v’ et y),
u 0 → v 0 (la règle (u’, v’) est dans P).
−→+ désigne la fermeture transitive de −→
Une grammaire G défini un langage L(G) sur l’alphabet Σ dont les
éléments sont les mots engendrés par dérivation à partir du symbole
de départ S.
L(G) = {w ∈ Σ∗ |S −→+ w}
Hiérarchie de Chomsky
On détermine la classe et la complexité des langages (et des
grammaires) en fonction d’un certain nombre de contraintes sur la
forme des règles de production. 4 ou 5 types de grammaire.
Types de grammaire
Type 0
Type 1
Type 2
Type 3
(Type 4)
S → $S 0 $ Aa → aA
$a → a$
S 0 → aAS 0 Ab → bA
$b → b$
G2 S 0 → bBS 0 Ba → aB A$ → $a
S0 → Bb → bB B$ → $b
$$ → #
Exemple
P = {S −→ aSb, S −→ ab}
=⇒ L(G) = {an bn | n > 0}
Exemple
P = {A → aB, A → a, B → b}
Grammaire de type 4
Les parties droites de toutes les règles sont des terminaux.
Les règles sont de la forme X → α où X ∈ Vn et α ∈ Vt∗
Théorème : Chomsky
1 Les langages réguliers (type 3) sont strictement contenus dans
les langages algébriques (type 2).
2 Les langages algébriques propres (type 2) sont strictement
contenus dans les langages contextuels (type 1).
3 les langages contextuels (type 1) sont strictement contenus dans
les langages récursifs.
4 les langages récursifs sont strictement contenus dans les
langages récursivement énumérables (type 0).
Basée sur les grammaires, l’analyse syntaxique peut vouloir dire deux
choses
Décision (le programme est correct ou non)
Décomposition syntaxique ou "Parsing" (une représentation de la
structure syntaxique est construite pour les programmes corrects).
Composante essentielle de l’implémentation d’un langage de
programmation, l’analyse syntaxique a pour rôle de :
Exemple
Considérons l’instruction "If A=1 then . . . fi"
Anal. Lexicale : MotReservé(If) + Variable(A) + OpRel(=)+ entier(1) +
MotRéservé(then) + . . . + MotRéservé(fi)
Anal. Syntaxique : Si(MotReservé(If)) + Expression(Variable(A)) +
OpRel(=)+ entier(1)) + Alors(MotRéservé(then)) +
BlocInstruction(. . . + MotRéservé(fi))
Les grammaires
Symboles terminaux (= unités lexicales) alphabet A
Symboles intermédiaires ou variables (= catégories
grammaticales) alphabet X
Règles de grammaire x → w où x ∈ X et w ∈ (A ∪ X )∗ . w est
donc un mot quelconque, même vide
Exemples
instr → si expr alors instr sinon instr
phrase → sujet verbe complément
Axiome (= programme)
Langage engendrés
Langage engendré = mots terminaux dérivant de l’axiome.
Analyse syntaxique
Étant donné un mot terminal, déterminer s’il est ou non engendré par
la grammaire ; si oui, en donner un arbre d’analyse.
En général, il existe 3 méthodes bien connues pour ce faire
Méthode universelle : essayer toutes les dérivations à partir de
l’axiome, jusqu’à trouver le mot. Des règles de longueur
(après modifications) permettent d’éliminer les impasses
Méthode descendante (descente récursive) : une procédure par
variable, les terminaux servant à choisir la dérivation
(prévision) et à la validation.
Méthode ascendante : on lit le mot (décalage) jusqu’à identifier des
dérivation, qu’on réduit et empile (réduction).
Remarque
Les deux premières dérivations correspondent à la même façon de
comprendre le mot, en voyant + reconnu plus haut que ∗, ce qui n’est
pas le cas pour la dernière.
Quelques remarques
1 L’ambiguïté est une propriété des grammaires et non des
langages.
2 Idéalement, pour permettre le parsing, une grammaire ne doit pas
être ambiguë. En effet, l’arbre de dérivation détermine le code
généré par le compilateur.
3 On essayera donc de modifier la grammaire pour supprimer ses
ambiguïtés.
4 Il n’existe pas d’algorithme pour supprimer les ambiguïtés d’une
grammaire context-free.
5 Pour un même langage, certaines grammaires peuvent être
ambiguës, d’autres non.
S → AB |C
A → aAb | ab
P= B → cBd | cd (4)
C → aCd | aDd
D → bDc| bc
E → E + E|T mais E → E + T |T
E → E + E|T mais E → E + T |T
E → T +E |T
Mais plutôt P = T → F ∗T |F (8)
F → id | (E)
Associativité de l’instruction If
instr → if expr instr |if expr instr else instr |other est ambigüe
Exemple :
Grammaire G2 = (Vn , Vt , S, P) définie par :
S → AB | CA, A → a, B → AB |EA,
P= (10)
C → aB |b, D → aC, E → BA
Qu’obtient-on à l’étape 1 ? ? ?
Il reste donc :
S → CA, A → a, C → b, D → aC
Qu’obtient-on à l’étape 2 ? ? ?
Que reste-t-il finalement ? ? ?
Exemple :
Grammaire G2 = (Vn , Vt , S, P) définie par :
S → AB | CA, A → a, B → AB |EA,
P= (11)
C → aB |b, D → aC, E → BA
S → CA, A → a, C → b, D → aC
S → CA, A → a, C → b
Exemple :
La grammaire suivante engendre les mots bien parenthésés :
S → S(S) |
Celle qui suit engendre les mêmes mots, sauf le mot vide.
Pour obtenir le mot vide, on tolère une seule production vide, sur
l’axiome, et sans autoriser celui-ci à apparaître en partie droite de
production. On rajoute donc un nouvel axiome, ici T :
P 0 = ??? (14)
expression → terme fin_expression
fin_expression → ” + ” terme fin_expression |
P0 = terme → facteur fin_terme (1
fin_terme → ” ∗ ” facteur fin_terme|
facteur → nombre|identificateur |”(”expression”)”
instr _si → si expr alors instr |si expr alors instr sinon instr
Théorème
Pour toute grammaire hors-contexte, il existe une grammaire
hors-contexte équivalente sous forme normale.
Théorème
Définition
Deux grammaires sont dites équivalentes si elles peuvent
produire les mêmes chaînes de symboles terminaux.
Grammaires de type 2 : passage d’un arbre syntaxique à un arbre
équivalent sous CNF = facile
Exemple
P → SN SV , SN → Det N,
SN → Det N SP, SP → Prep SN,
R= (21)
SV → V, SV → V SN,
SV → V SN SP, SV → mange
Exemple
Règle Forme initiale Règle Forme Normale de Chomsky
R1 : P → SN SV R1 : P → SN SV
R2 : SN → Det N R2 : SN → Det N
Exemple
Règle Forme initiale Règle Forme Normale de Chomsky
R1 : P → SN SV R1 : P → SN SV
R2 : SN → Det N R2 : SN → Det N
R3 : SN → Det N SP R3.1 : X1 → N SP
R3.2 : SN → Det X1
Exemple
Règle Forme initiale Règle Forme Normale de Chomsky
R1 : P → SN SV R1 : P → SN SV
R2 : SN → Det N R2 : SN → Det N
R3 : SN → Det N SP R3.1 : X1 → N SP
R3.2 : SN → Det X1
R4 : SP → Prep SN R4 : SP → Prep SN
Exemple
Règle Forme initiale Règle Forme Normale de Chomsky
R1 : P → SN SV R1 : P → SN SV
R2 : SN → Det N R2 : SN → Det N
R3 : SN → Det N SP R3.1 : X1 → N SP
R3.2 : SN → Det X1
R4 : SP → Prep SN R4 : SP → Prep SN
R5 : SV → V R1.2 P → SN V
Exemple
Règle Forme initiale Règle Forme Normale de Chomsky
R1 : P → SN SV R1 : P → SN SV
R2 : SN → Det N R2 : SN → Det N
R3 : SN → Det N SP R3.1 : X1 → N SP
R3.2 : SN → Det X1
R4 : SP → Prep SN R4 : SP → Prep SN
R5 : SV → SV R1.2 P → SN V
R6 : SV → V SN R6 : SV → V SN
Exemple
Règle Forme initiale Règle Forme Normale de Chomsky
R1 : P → SN SV R1 : P → SN SV
R2 : SN → Det N R2 : SN → Det N
R3 : SN → Det N SP R3.1 : X1 → N SP
R3.2 : SN → Det X1
R4 : SP → Prep SN R4 : SP → Prep SN
R5 : SV → SV R1.2 P → SN V
R6 : SV → V SN R6 : SV → V SN
R7 : SV → V SN SP R3.1 : X2 → SN SP
R3.2 : SV → V X2
Exemple
Règle Forme initiale Règle Forme Normale de Chomsky
R1 : P → SN SV R1 : P → SN SV
R2 : SN → Det N R2 : SN → Det N
R3 : SN → Det N SP R3.1 : X1 → N SP
R3.2 : SN → Det X1
R4 : SP → Prep SN R4 : SP → Prep SN
R5 : SV → SV R1.2 P → SN V
R6 : SV → V SN R6 : SV → V SN
R7 : SV → V SN SP R3.1 : X2 → SN SP
R3.2 : SV → V X2
R8 : SV → mange R8 : SV → mange
X → aα avec a ∈ Vt et α ∈ Vn∗
Remarques :
Cela accroît le nombre de productions de façon exponentielle.
Dans la pratique, il n’est pas indispensable que la grammaire soit
sous forme normale de Chomsky, mais le déroulement de
l’algorithme peut en être perturbé.
Exemple : On considère la grammaire initiale :
A1 → A2 A3 , A2 → A3 A1 | b, A3 → A1 A2 | a
Théorème
Un langage est engendré par une grammaire linéaire droite si et
seulement s’il est régulier sans le mot vide.
1 Généralités
2 Grammaires formelles
3 Automates à pile
a
[i, P] [j, Q]
Table de transitions
Un automate à pile peut se décrire aussi à l’aide d’une table de
transitions dans laquelle les transitions sont spécifiées.
Les lignes correspondent aux états,
Les colonnes correspondent aux étiquettes possibles.
Dans les cases, figurent les triplets (état d’arrivée ; symbole
dépilé ; symbole empilé) ; il peut y en avoir plusieurs par case, ou
aucun. Les états particuliers sont signalés dans les dernières
colonnes.
Exemple 2 : Le palindrome
a b accept
S0 (S0 , , P) (S0 , , Q) (1, , )
(1, , ) (1, , ) (1, , )
1 (1, , u) (2, u, )
2 (2, u, ) x
Définition
Configuration = triplet (q, m, α) ∈ Q × Σ∗ × Γ∗ , où :
q est l’état courant de l’unité de contrôle
m représente la partie du mot à reconnaître non encore lue. Le
symbole le plus à gauche de m est le caractère sous la tête de
lecture.
α représente le contenu de la pile. Le symbole le plus à gauche
de α est le sommet de la pile.
Il existe des variantes qui ne portent pas sur la forme des transitions,
mais sur l’état dans lequel doit être la pile pour qu’une chaîne soit
acceptée.
Remarque
Pour un PDA P, 2 langages (à priori différents) sont définis :
N(P) (acceptation par pile vide) et
L(P) (acceptation par état final) .
N(P) n’utilise pas F et n’est donc pas modifié si l’on définit F = ∅ ;
Remarque
L(P) = {w | w ∈ Σ∗ ∧ ∃q ∈ F , γ ∈ Γ∗ (q0 , w, Z0 ) `∗P (q, , γ)}
N(P) = {w | w ∈ Σ∗ ∧ ∃q ∈ Q, (q0 , w, Z0 ) `∗P (q, , )}
a(, u) b(u, )
Preuve
On peut montrer que le langage Lww r défini au slide 124 ne peut être
défini par un PDA déterministe
Théorème
Les trois classes de langages suivants sont équivalentes :
Les langages définis par une grammaire hors contexte (i.e les
langages hors contexte)
Les langages définis par un PDA avec acceptation par pile vide
Les langages définis par un PDA avec acceptation par état final
Construction
Théorème
Pour tout PDA PF = (Q, Σ, Γ, δF , q0 , Z0 , F ) on peut définir un PDA PN
avec N(PN ) = L(PF )
Construction
Théorème
Pour tout PDA P on peut définir une CFG G avec L(G) = N(P)
L est-il context-free ?
Pour quels opérateurs les langages context-free sont-ils fermés ?
w ∈ L?
L est-il vide, fini, infini ?
L1 ⊆ L2, L1 = L2 ?
Astuces
Pour montrer que L est context-free, il faut :
Trouver une CFG (ou un PDA) G et
montrer que L = L(G) (ou L = N(G) si G est un PDA avec
acceptation par pile vide i.e
L ⊆ L(M), et donc tout mot de L est accepté par M
L(M) ⊆ L, et donc tout mot accepté par M est dans L
Exemple : L = {0i 1j | i ∈ N}
Pour montrer que L est context-free, on définit par exemple le PDA P
et on démontre (par induction) que L = L(P).
Preuve
Soit L un langage algébrique.
L (ou L \ {}) est reconnu par une CFG en forme normale de
Chomsky G
Soit k le nombre de variables de G
Prenons p = 2k k et | z |≥ p
Prenons un des plus longs chemins de l’arbre de dérivation de z :
plusieurs noeuds du chemin ont le même label (une variable)
Dénotons v1 et v2 2 sommets sur ce chemin labellés par la même
variable avec v1 ancêtre de v2 et on choisi v1 "le plus bas possible"
Découpons z comme indiqué sur la figure
Et donc ∀i : uv i wx i y ∈ L
Exemple
Σ = {a, b, c}. Montrer que L = {an bn c n | n ∈ N} n’est pas algébrique.
Soit k l’entier dont le lemme de pompage garantit l’existence.
Considérons le mot t = ak bk c k . il doit alors exister une factorisation
t = uvwxy pour laquelle on a (i) | vx |≥ 1, (ii) | vxx |≤ k et (iii) ∀i ≥ 0,
uv i wx i y ∈ L. La propriété (ii) assure que le facteur vwx ne peut pas
contenir simultanément les lettres a et c : en effet, tout facteur de t
comportant un a et un c doit avoir aussi le facteur bk , et donc être de
longueur ≥ k + 2. Supposons que vwx ne contienne pas la lettre c
(l’autre cas étant complètement analogue) : en particulier, ni v ni x ne
la contient, donc le mot uv i wx i y , qui est dans L d’après (iii), a le même
nombre de c que le mot t initial ; mais comme son nombre de a ou bien
de b est différent (d’après (i)), on a une contradiction.
Théorème
L1 et L2 algébriques ⇒L1 ∪ L2 , L1 .L2 et L∗ algébriques.
Preuve
Soit G1 = (V1 , T1 , P1 , S1 ) et G2 = (V2 , T2 , P2 , S2 ) 2 grammaires
n’ayant aucune variable en commun et S ∈ / V1 ∪ V2 :
Union : Pour G∪ = (V1 ∪ V2 ∪ S, T1 ∪ T2 , P, S) avec
P = P1 ∪ P2 ∪ {S → S1 | S2 }, on a L(G∪ )) = L(G1) ∪ L(G2)
Concaténation : Pour Gconcat = (V1 ∪ V2 ∪ {S}, T1 ∪ T2 , P, S) avec
P = P1 ∪ P2 ∪ {S → S1 | S2 }, on a : L(Gconcat ) = L(G1).L(G2)
Fermeture de Kleene : Pour G∗ = (V1 ∪ {S}, T1 , P, S) avec
P = P1 ∪ {S → S1 S2 | }, on a : L(G∗ ) = L(G1 )∗
Théorème
Si L est un langage algébrique alors LR l’est aussi.
Preuve
L est reconnu par une CFG G = (V , T , P, S).
À partir de G on peut construire une CFG GR = (V , T , P R , S) avec
P R = {A → αR |→ α ∈ P}
On peut prouver que
L(GR ) = LR
Théorème
Si L et M sont algébriques alors L ∩ M peut ne pas être algébrique.
Preuve
Il suffit de donner un contre exemple !
L1 {al bl c m | l, m ∈ N} est un langage algébrique (démontrer)
L2 {al bm c m | l, m ∈ N} est un langage algébrique (démontrer)
Mais L1 ∩ L2 n’est pas un langage algébrique
Théorème
Si L est algébrique et R est régulier alors L ∩ R est algébrique.
Preuve
Ayant le PDA AL avec L(AL ) = L : AL = (QL , Σ, Γ, γL , qL , Z0 , FL )
Et l’AFD AR avec L(AR ) = R, AR = (Σ, QR , qR , δR , FR )
On définit le PDA AL∩R par AQL ∩QR , Σ, Γ, δL∩R , (qL , qR ), Z0 , FL × FR
avec δL∩R (p, q, a) = {(p0 , q 0 ) | p0 ∈ δL (p, a) ∧ q 0 ∈ δR (q, a)}
a ∈ Σ ∪ {}. On peut démontrer que L(AL∩R ) = L ∩ R
Théorème
Si L est un langage algébrique alors L ne peut être algébrique
Preuve
Une des lois de De Morgan est :
L1 ∩ L2 = L1 ∪ L2
Théorème
Si L et M sont des langages algébriques alors L \ M peut ne pas être
algébrique
Preuve
(L) = Σ∗ \ M
Et Σ∗ est régulier.
Astuce
Pour tester que :
w ∈ L voir si une CFG en forme normale de Chomsky génère w Il
existe un algorithme en O(n3 ) où n est la longueur de w
L vide (L=∅), voir si dans G avec L(G) = L, le symbole de départ
produit quelque chose
L infini ? voir si une CFG en forme normale de Chomsky qui définit
L est récursive
1 Généralités
2 Grammaires formelles
3 Automates à pile
Questions posées
En supposant qu’on ait une phrase ω, Les différentes questions que
l’on peut se poser par rapport aux phrases engendrées par une
grammaire sont :
comment analyser ω ?
ω appartient-elle au langage L(G) ?
si ω ∈ L(G), donner une dérivation
Critères de classification
Il existe 2 critères de classification pour distinguer les différentes
méthodes d’analyse syntaxique :
le sens X de parcours de la chaîne analysée :
gauche → droite (L) ou droite → gauche (R). X : {L, R}
le sens Y d’application des productions : dérivation ou réduction
(Leftmost ou Rightmost). Y : {L, R}
On distingue donc 4 méthodes d’analyse désignées par un couple XY
On dit qu’un langage L est LL(k) s’il existe une grammaire LL(k)
qui engendre L.
Un langage est LL(k) s’il est LL(1).
On parlera de la classe des langages LL.
Définition
C’est une analyse avec une inspection d’un symbole terminal en
avance sur le symbole courant traité.
Dans la pratique ce sont les grammaires les plus utilisées.
Le but de l’analyse LL(1) est de pouvoir (toujours) connaître la
règle de production à appliquer et ceci en se basant sur le terminal
suivant non encore traité de la phrase en cours d’examen.
Deux concepts nouveaux se révèlent nécessaires pour faciliter
l’analyse LL(1) :
PREMIER (FIRST)
SUIVANT (FOLLOW)
L’ensemble SUIVANT
Nous appliquons les règles suivantes jusqu’à ce qu’aucun terminal ne
puisse être ajouté aux ensembles SUIVANT.
mettre $ dans SUIVANT de l’axiome.
s’il y a une production : A → αBβ, le contenu de PREMIER(β),
excepté la chaîne vide est ajouté à SUIVANT(B)
s’il y a une production : A → αB ou A → αBβ tq β ⇒∗ , les
éléments de SUIVANT(A) sont ajoutés à SUIVANT(B)
Il est constitué de :
un tampon qui contient la chaîne du programme à analyser, suivie
par le symbole $.
une pile qui contient une séquence de symboles grammaticaux,
avec $ au fond de la pile.
une table d’analyse à deux dimensions qui permet de choisir la
règle de production à utiliser.
DEPILER si a=b
M[a, b] = ACCEPTE si a=b=$
Erreur sinon
? ? ? ? ? ?
? ? ? ? ? ? ?
? ? ? ? ? ? ?
? ? ? ? ? ? ?
? ? ? ? ? ? ?
a b e i t $
S S→a Erreur Erreur S → iEtSS 0 Erreur Erreur
S’ Erreur Erreur S 0 → eS Erreur Erreur S0 →
S0 →
E Erreur E →b Erreur Erreur Erreur Erreur
E → TE 0
E 0 → +TE 0 | E E’ T T’ F
PREMIER (, nb +, (, nb ∗, (, nb
T → FT 0
SUIVANT $, ) $, ) +, , $, ) +, , $, ) ∗, , +, $
T 0 → ∗FT 0 |
F → (E)|nb
nb + * ( ) $
E E → TE 0 E → TE 0
E’ E 0 → +TE 0 E0 → E0 →
0 0
T T → FT T → FT
T’ T0 → T 0 → ∗FT 0 T0 → T0 →
F F → nb F → (E)
Remarque
La classe des langages LL est strictement incluse dans la classe des
langages LR :