Analiza sintactică

Ierarhia lui Chomsky. Gramatici IDC

Simplificarea gramaticilor IDC
Exerciţii diverse

Curs Limbaje formale şi compilatoare

Analiza sintactică. Gramatici IDC. Simplificarea gramaticilor
IDC

Universitatea Transilvania din Braşov

Facultatea de Matematică şi Informatică

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Obiective

1 Analiza sintactică

2 Ierarhia lui Chomsky. Gramatici IDC

3 Simplificarea gramaticilor IDC

4 Exerciţii diverse

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Faza de analiză sintactică

Analiza sintactică
Program sursă

Analizor lexical (scanner/lexer)

pe baza tokenilor şi a regulilor gramaticale ale

Șir de tokeni limbajului sursă se ı̂ncearcă construirea
arborelui sintactic (syntactic parse tree)

Analizor sintactic (parser)

Arbore sintactic (abstract syntax tree)

Analizor semantic

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Faza de analiză sintactică

Analiza sintactică
Program sursă

Analizor lexical (scanner/lexer)

pe baza tokenilor şi a regulilor gramaticale ale

Șir de tokeni limbajului sursă se ı̂ncearcă construirea
arborelui sintactic (syntactic parse tree)
se simplifică arborele sintactic la un AST
Analizor sintactic (parser) (abstract syntax tree)

Arbore sintactic (abstract syntax tree)

Analizor semantic

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Faza de analiză sintactică

Analiza sintactică
Program sursă

Analizor lexical (scanner/lexer)

pe baza tokenilor şi a regulilor gramaticale ale

Șir de tokeni limbajului sursă se ı̂ncearcă construirea
arborelui sintactic (syntactic parse tree)
se simplifică arborele sintactic la un AST
Analizor sintactic (parser) (abstract syntax tree)
se tratează erorile sintactice (cele mai
frecvente)
Arbore sintactic (abstract syntax tree)

Analizor semantic

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Faza de analiză sintactică

Analiza sintactică
Program sursă

Analizor lexical (scanner/lexer) pe baza tokenilor şi a regulilor gramaticale ale

limbajului sursă se ı̂ncearcă construirea
Șir de tokeni
arborelui sintactic (syntactic parse tree)
se simplifică arborele sintactic la un AST
(abstract syntax tree)
Analizor sintactic (parser) se tratează erorile sintactice (cele mai
frecvente)

Noţiuni de LF necesare: gramatici IDC, arbore

Arbore sintactic (abstract syntax tree)
sintactic de derivare, automate push-down

Analizor semantic

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Faza de analiză sintactică - Exemplu

Pentru şirul de tokeni obţinut la exemplul de analiză sintactică
Intrare: < id, 1 ><:=, >< id, 2 >< +, >< id, 3 >< ∗, >< num, 40 >

se obţine arborele sintactic:

Instrucțiune atribuire

Identificator := Expr aritm

valoareinit Expr aritm + Expr aritm

*
Identificator Expr aritm Expr aritm

valoareinit Identificator număr

cant
valoareinit 40
valoareinit

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Faza de analiză sintactică - Exemplu

Pentru şirul de tokeni obţinut la exemplul de analiză sintactică
Intrare: < id, 1 ><:=, >< id, 2 >< +, >< id, 3 >< ∗, >< num, 40 >

Ieşire: AST (Abstract Syntax Tree) corespunzător:

:=

<id, 1> +

<id, 2> *

<id, 3> <num, 40>

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Ierarhia lui Chomsky

Ierarhia lui Chomsky

(0) Gramatică de tip 0 care nu are nici o restricţie asupra regulilor

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Ierarhia lui Chomsky

Ierarhia lui Chomsky

(0) Gramatică de tip 0 care nu are nici o restricţie asupra regulilor

(1) Gramatică de tip 1 (DC) ı̂n care fiecare regulă din P este de forma
u1 Au2 → u1 wu2 , unde u1 , u2 ∈ (VN VT )∗ , A ∈ VN şi w ∈ (VN VT )+
S S
cu o singură excepţie posibilă S → λ, care poate să apară dacă S nu apare
ı̂n dreapta nici unei reguli din P

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Ierarhia lui Chomsky

Ierarhia lui Chomsky

(0) Gramatică de tip 0 care nu are nici o restricţie asupra regulilor

(1) Gramatică de tip 1 (DC) ı̂n care fiecare regulă din P este de forma
u1 Au2 → u1 wu2 , unde u1 , u2 ∈ (VN VT )∗ , A ∈ VN şi w ∈ (VN VT )+
S S
cu o singură excepţie posibilă S → λ, care poate să apară dacă S nu apare
ı̂n dreapta nici unei reguli din P
(2) Gramatică de tip 2 (IDC) ı̂n care
S fiecare regulă din P este de forma
A → w cu A ∈ VN şi w ∈ (VN VT )+

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Ierarhia lui Chomsky

Ierarhia lui Chomsky

(0) Gramatică de tip 0 care nu are nici o restricţie asupra regulilor

(1) Gramatică de tip 1 (DC) ı̂n care fiecare regulă din P este de forma
u1 Au2 → u1 wu2 , unde u1 , u2 ∈ (VN VT )∗ , A ∈ VN şi w ∈ (VN VT )+
S S
cu o singură excepţie posibilă S → λ, care poate să apară dacă S nu apare
ı̂n dreapta nici unei reguli din P
(2) Gramatică de tip 2 (IDC) ı̂n care
S fiecare regulă din P este de forma
A → w cu A ∈ VN şi w ∈ (VN VT )+
(3) Gramatică de tip 3 (R) ı̂n care fiecare regulă are una dintre următoarele
două forme: A → aB sau A → a, unde A, B ∈ VN şi a ∈ VT .

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Gramatici independente de context

Limbajele independente de context sunt generate de gramaticile de tip 2 din

ierarhia lui Chomsky.

Gramatică independentă de context: O gramatică IDC este o gramatică

G = (VN , VT , S, P),Sı̂n care mulţimea regulior P este de forma A → α, cu
A ∈ VN şi α ∈ (VN VT )∗ .

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Gramatici independente de context

Să se construiască gramatici IDC pentru limbajele:

L1 = {an b n+2 |n > 3}

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Gramatici independente de context

Să se construiască gramatici IDC pentru limbajele:

L1 = {an b n+2 |n > 3}
L2 = {an b n+2 c m d m+1 |n > 3, m > 0}

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Gramatici independente de context

Să se construiască gramatici IDC pentru limbajele:

L1 = {an b n+2 |n > 3}
L2 = {an b n+2 c m d m+1 |n > 3, m > 0}
L3 = {an b m+2 c m d n+1 |n > 0, m > 0}

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Arbore de derivaţie (I)

Vom prezenta o metodă vizuală de descriere a oricărei derivaţii ı̂ntr-o gramatică

IDC sub forma unui arbore de derivaţie.
Ce este un graf de tip arbore?
Arbore de derivaţie: Un arbore de derivaţie ı̂ntr-o gramatică IDC G este un
arbore ı̂n care:
S
a) Fiecare nod este etichetat cu un simbol din VN VT .

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Arbore de derivaţie (I)

Vom prezenta o metodă vizuală de descriere a oricărei derivaţii ı̂ntr-o gramatică

IDC sub forma unui arbore de derivaţie.
Ce este un graf de tip arbore?
Arbore de derivaţie: Un arbore de derivaţie ı̂ntr-o gramatică IDC G este un
arbore ı̂n care:
S
a) Fiecare nod este etichetat cu un simbol din VN VT .
b) Eticheta rădăcinii este S.

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Arbore de derivaţie (I)

Vom prezenta o metodă vizuală de descriere a oricărei derivaţii ı̂ntr-o gramatică

IDC sub forma unui arbore de derivaţie.
Ce este un graf de tip arbore?
Arbore de derivaţie: Un arbore de derivaţie ı̂ntr-o gramatică IDC G este un
arbore ı̂n care:
S
a) Fiecare nod este etichetat cu un simbol din VN VT .
b) Eticheta rădăcinii este S.
c) Dacă nodul A are cel puţin un descendent, atunci are o etichetă din VN .

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Arbore de derivaţie (I)

Vom prezenta o metodă vizuală de descriere a oricărei derivaţii ı̂ntr-o gramatică

IDC sub forma unui arbore de derivaţie.
Ce este un graf de tip arbore?
Arbore de derivaţie: Un arbore de derivaţie ı̂ntr-o gramatică IDC G este un
arbore ı̂n care:
S
a) Fiecare nod este etichetat cu un simbol din VN VT .
b) Eticheta rădăcinii este S.
c) Dacă nodul A are cel puţin un descendent, atunci are o etichetă din VN .
d) Dacă A1 , A2 , A3 , ..., Ak sunt toţi descendenţii direcţi ai lui A ı̂n ordine de la
stânga spre dreapta, atunci: A → A1 A2 A3 ...Ak este o regulă din P.

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Arbore de derivaţie (II)

G = ({S, A, B}, {a, b}, S, P) cu P
S → aAB
S→a
S → bBA
S→b
A → aS
B → bS
Pentru această gramatică, un arbore de derivaţie având frunzele a, a, b, b şi a
este cel din figura de mai jos.

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Arbore de derivaţie (III)

Se numeşte rezultat al unui arbore cuvântul format din etichetele frunzelor

citite de la stânga spre dreapta.
Conform acestei definiţii rezultatul arborelui de derivaţie din figura slide
anterior este cuvântul aabba.

Se numeşte subarbore al unui arbore, graful format dintr-un nod ı̂mpreună cu

toţi descendenţii săi.

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Simplificarea gramaticilor IDC (I)

Algoritm pentru a determina dacă un limbaj este vid

Considerăm o gramatică G cu m neterminale (variabile). Se construieşte o

mulţime M de arbori de derivaţie ı̂n G ı̂n modul următor:
se adaugă iniţial arborele format din nodul S;

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Simplificarea gramaticilor IDC (I)

Algoritm pentru a determina dacă un limbaj este vid

Considerăm o gramatică G cu m neterminale (variabile). Se construieşte o

mulţime M de arbori de derivaţie ı̂n G ı̂n modul următor:
se adaugă iniţial arborele format din nodul S;
dacă arborele A ∈ M se adaugă fiecare arbore obţinut din A prin aplicarea
unei singure reguli şi care respectă următoarele condiţii:

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Simplificarea gramaticilor IDC (I)

Algoritm pentru a determina dacă un limbaj este vid

Considerăm o gramatică G cu m neterminale (variabile). Se construieşte o

mulţime M de arbori de derivaţie ı̂n G ı̂n modul următor:
se adaugă iniţial arborele format din nodul S;
dacă arborele A ∈ M se adaugă fiecare arbore obţinut din A prin aplicarea
unei singure reguli şi care respectă următoarele condiţii:
(i) arborele obţinut nu este deja ı̂n M;

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Simplificarea gramaticilor IDC (I)

Algoritm pentru a determina dacă un limbaj este vid

Considerăm o gramatică G cu m neterminale (variabile). Se construieşte o

mulţime M de arbori de derivaţie ı̂n G ı̂n modul următor:
se adaugă iniţial arborele format din nodul S;
dacă arborele A ∈ M se adaugă fiecare arbore obţinut din A prin aplicarea
unei singure reguli şi care respectă următoarele condiţii:
(i) arborele obţinut nu este deja ı̂n M;
(ii) arborele obţinut nu are drumuri de lungime mai mare decât m.

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Simplificarea gramaticilor IDC (II)

Algoritm pentru a determina dacă un limbaj este vid

Algoritmul se opreşte ı̂n momentul ı̂n care nu mai au loc modificări ı̂n
mulţimea M.

Dacă ı̂n final există ı̂n M un arbore al cărui rezultat este din VT∗ , atunci
L(G) 6= ∅. Atfel L(G) = ∅.

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Simplificarea gramaticilor IDC (III)

Simbol inaccesibil: Simbolul A ∈ VN se numeşte inaccesbil dacă NU există

∗
S ⇒ α1 Aα2 .

Simbol neutilizabil: Simbolul A ∈ VN se numeşte neutilizabil dacă NU există

∗ ∗
nici o derivaţie de forma: S ⇒ α1 Aα2 ⇒ w , unde w ∈ VT∗ .

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Simplificarea gramaticilor IDC (IV)

Pentru orice gramatică IDC G, există o gramatică IDC G1 echivalentă

∗
astfel ı̂ncât, ∀A ∈ VN ∃w ∈ VT∗ cu A ⇒ w

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Simplificarea gramaticilor IDC (IV)

Pentru orice gramatică IDC G, există o gramatică IDC G1 echivalentă

∗
astfel ı̂ncât, ∀A ∈ VN ∃w ∈ VT∗ cu A ⇒ w
Pentru orice gramatică IDC G, există o gramatică IDC G2 echivalentă şi
fără simboluri inaccesibile.

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Simplificarea gramaticilor IDC (IV)

Pentru orice gramatică IDC G, există o gramatică IDC G1 echivalentă

∗
astfel ı̂ncât, ∀A ∈ VN ∃w ∈ VT∗ cu A ⇒ w
Pentru orice gramatică IDC G, există o gramatică IDC G2 echivalentă şi
fără simboluri inaccesibile.
Rezultă: Pentru orice gramatică IDC G, există o gramatică IDC G 0
echivalentă şi fără simboluri neutilizabile.

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Simplificarea gramaticilor IDC (V)

Algoritm pentru eliminarea simbolurilor care nu generează cuvinte din VT∗

Intrare: Gramatica G = (VN , VT , S, P) independentă de context

Ieşire: Gramatica G1 = (VN1 , VT , S, P1 ) fără simboluri care nu pot genera

cuvinte din VT∗ .

Construim mulţimea VN1 pas cu pas.

Pas 1 : V0 = ∅, i = 1

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Simplificarea gramaticilor IDC (V)

Algoritm pentru eliminarea simbolurilor care nu generează cuvinte din VT∗

Intrare: Gramatica G = (VN , VT , S, P) independentă de context

Ieşire: Gramatica G1 = (VN1 , VT , S, P1 ) fără simboluri care nu pot genera

cuvinte din VT∗ .

Construim mulţimea VN1 pas cu pas.

Pas 1 : V0 = ∅, i = 1
V T }∗ }
S S
Pas 2 : Vi = Vi−1 {A|A → α ∈ P, α ∈ {Vi−1

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Simplificarea gramaticilor IDC (V)

Algoritm pentru eliminarea simbolurilor care nu generează cuvinte din VT∗

Intrare: Gramatica G = (VN , VT , S, P) independentă de context

Ieşire: Gramatica G1 = (VN1 , VT , S, P1 ) fără simboluri care nu pot genera

cuvinte din VT∗ .

Construim mulţimea VN1 pas cu pas.

Pas 1 : V0 = ∅, i = 1
V T }∗ }
S S
Pas 2 : Vi = Vi−1 {A|A → α ∈ P, α ∈ {Vi−1
Pas 3 : Dacă Vi 6= Vi−1 atunci i = i + 1, salt la Pas2;
altfel VN1 = Vi , P1 = {A → α|A ∈ VN1 }

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Simplificarea gramaticilor IDC (VI)

Algoritm pentru eliminarea simbolurilor inaccesibile

Intrare: Gramatica G = (VN , VT , S, P).

Ieşire: Gramatica G2 = (VN1 , VT , S, P2 ) fără simboluri inaccesibile.

Construim mulţimea VN2 pas cu pas.

Pas 1 : V0 = {S}, i = 1

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Simplificarea gramaticilor IDC (VI)

Algoritm pentru eliminarea simbolurilor inaccesibile

Intrare: Gramatica G = (VN , VT , S, P).

Ieşire: Gramatica G2 = (VN1 , VT , S, P2 ) fără simboluri inaccesibile.

Construim mulţimea VN2 pas cu pas.

Pas 1 : V0 = {S}, i = 1
S
Pas 2 : Vi = Vi−1 {A ∈ VN |∃B → αAβ ∈ P, B ∈ Vi−1 }

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Simplificarea gramaticilor IDC (VI)

Algoritm pentru eliminarea simbolurilor inaccesibile

Intrare: Gramatica G = (VN , VT , S, P).

Ieşire: Gramatica G2 = (VN1 , VT , S, P2 ) fără simboluri inaccesibile.

Construim mulţimea VN2 pas cu pas.

Pas 1 : V0 = {S}, i = 1
S
Pas 2 : Vi = Vi−1 {A ∈ VN |∃B → αAβ ∈ P, B ∈ Vi−1 }
Pas 3 : Dacă Vi 6= Vi−1 atunci i = i + 1, salt la Pas 2;
altfel VN2 = Vi , P2 = {A → α|A ∈ VN1 }.

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Gramatici independente de context

Să se simplifice următoarea gramatică: G = ({S, A, B, C }, {a, b}, S, P) cu P

S→A
S→B
B → AB
B → Ba
A → aB
A → bS
A→b
C → AS
C →b
Eliminăm stări inaccesibile:
V0 = {S}, i = 1
V1 = {S} ∪ {A, B}, i = 2
V2 = {S, A, B} ∪ {} ⇒ V1 = V2 ⇒ VN1 = {S, A, B}

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Gramatici independente de context

Astfel, P devine P1
S → A|B
B → AB|Ba
A → aB|bS|b
Eliminăm stări neutilizabile:

V0 = {}, i = 1

V1 = {} ∪ {A}, i = 2
V2 = {A} ∪ {S}, i = 3
V3 = {A, S} ∪ {} ⇒ V3 = V1 ⇒ VN2 = {A, S}
Astfel, P2 devine
S→A
A → bS|b

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Simplificarea gramaticilor IDC

Derivaţie la stânga: O derivaţie ı̂ntr-o gramatică G se numeşte derivaţie la

stânga dacă la fiecare pas al derivaţiei se ı̂nlocuieşte cel mai din stânga
neterminal.

Redenumire: O regulă a unei gramatici G se numeşte redenumire dacă este de

forma A → B, A, B ∈ VN .

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Simplificarea gramaticilor IDC

Algoritm pentru eliminarea redenumirilor

Intrare: Gramatica G = (VN , VT , S, P) IDC.

Ieşire: Gramatica G1 = (VN1 , VT , S, P 1 ) IDC.

Construim mulţimea P 1 pas cu pas.

Pas 1 : P0 = {A → α ∈ P nu este redenumire }

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Simplificarea gramaticilor IDC

Algoritm pentru eliminarea redenumirilor

Intrare: Gramatica G = (VN , VT , S, P) IDC.

Ieşire: Gramatica G1 = (VN1 , VT , S, P 1 ) IDC.

Construim mulţimea P 1 pas cu pas.

Pas 1 : P0 = {A → α ∈ P nu este redenumire }
S ∗
Pas 2 :Pi = Pi−1 {A → αj |∃A ⇒ B ∈ P ∧ B → αj ∈ Pi−1 }

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Simplificarea gramaticilor IDC

Algoritm pentru eliminarea redenumirilor

Intrare: Gramatica G = (VN , VT , S, P) IDC.

Ieşire: Gramatica G1 = (VN1 , VT , S, P 1 ) IDC.

Construim mulţimea P 1 pas cu pas.

Pas 1 : P0 = {A → α ∈ P nu este redenumire }
S ∗
Pas 2 :Pi = Pi−1 {A → αj |∃A ⇒ B ∈ P ∧ B → αj ∈ Pi−1 }
Pas 3 : Dacă Pi 6= Pi−1 atunci i = i + 1, salt la Pas2;
altfel P 1 = Pi , VN1 = {A ∈ VN |∃A → α ∈ P 1 }

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Simplificarea gramaticilor IDC

Să se elimine redenumirile din următoarea gramatică:

G = ({S, T , L}, {a, b, +, ∗, [, ]}, S, P) cu P
S →T +S
S→T
T →L∗T
T →L
L → [S]
L→a
L→b

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Simplificarea gramaticilor IDC

Redenumiri: S → T , T → L
S →T +S
T →L∗T
L → [S]
L→a
L→b
...
S →L∗T
T → [S]
T →a
T →b
...
S → [S]
S→a
S→b

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Exerciţii

Se consideră arborele din figura următoare. Să se construiască o gramatică IDC

G, astfel ı̂ncât arborele să fie arbore de derivaţie ı̂n G.

Soluţie: O gramatică pentru care arborele de mai sus să fie arbore de derivaţie
este: G = ({S}, {a, b}, S, {S → aSSb, S → a, S → λ})

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Exerciţii

Eliminaţi neterminalele neutilizabile din gramatica:

G = ({S, A, B}, {a, b}, S, P) cu regulile:
S → aS, S → AB, S → abB, A → bA, B → AA, B → b Eliminăm stări
neutilizabile:
VN1 = {}
VN2 = {} ∪ {B}
VN3 = {B} ∪ {S}
VN4 = VN3 = {B, S}
Rezultă gramatica:

G 0 = ({S, B}, {a, b}, S, {S → aS, S → abB, B → b})

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl
 Analiza sintactică
Ierarhia lui Chomsky. Gramatici IDC
Simplificarea gramaticilor IDC
Exerciţii diverse

Exerciţii

Fie gramatica G = ({S, A, B}, {a, b}, S, {S → aB, S → bA, A → a, A →

aS, A → bAA, B → b, B → bS, B → aBB}). Găsiţi o derivare şi un arbore de
derivaţie pentru cuvântul w = aaabbabbbba
O derivaţie pentru w = aaabbabbbba:
S → aB → aaBB → aaaBBB → aaabSBB → aaabbABB → aaabbaBB →
aaabbabbB → aaabbabbbS → aaabbabbbbA → aaabbabbbba.
Arborele de derivare este:

Curs Limbaje formale şi compilatoare Analiza sintactică. Gramatici IDC. Simpl