4/12/2017
Universitatea Transilvania din Braov
Facultatea de Inginerie Electric i tiina Calculatoarelor
Departamentul Electronic i Calculatoare
LIMBAJE FORMALE I COMPILATOARE
Curs
[Link]. Octavian Mihai MACHIDON
30.03.2017
Astzi
1 Introducere n analiza sintactic
Analiza sintactic LL
Recursivitate stng
2 Parser recursiv
Factorizare stnga
Eliminarea ambiguitilor
1
4/12/2017
Structura detaliat
Analiza sintactic
Verifica formarea corecta (cf. gramaticii) a
constructiilor din limbaj
Analiza lexical cuvinte
Analiza sintactica propozitii
Primeste un sir de atomi lexicali, construieste un
arbore de derivare
Structura utila in final este un arbore sintactic
Folosita in front-end-ul unui interpretor /
compilator
Dar si de catre IDE: syntax highlight, navigare prin
cod, refactoring
2
4/12/2017
Exemplu
Arbore de derivare / sintactic
3
4/12/2017
Tipuri de analiz sintactic
Descendenta (top-down, de sus in jos)
Inlocuieste cate un neterminal cu partea dreapta a unei
productii, pana ramane doar cu terminali
Ascendenta (bottom-up, de jos in sus)
Porneste de la sirul de atomi lexicali, abstractizeaza din sir
simbolul de start prin reduceri succesive
Analiza descendenta derivare stanga
Tot timpul inlocuim cel mai din stanga neterminal
Analiza ascendenta - derivarea dreapta
primul neterminal nlocuit este cel mai din dreapta din
forma propoziional curent
7
Derivare stnga, top down
LL: irul de tokeni se parcurge din stnga (L)
Se deriveaza non-terminalul cel mai din stnga (L)
Cum alegem producia folosit pentru derivare?
Backtracking dac alegem producia greit 8
4
4/12/2017
Derivare stnga, top down
Exemplu similar, dar trebuie alese alte producii
pentru o derivare corect fr backtracking
Este necesar o metod de predicie 9
Top down cu backtracking
SaAb|aBc
A bb | bc
Bb
Gramatica genereaz de fapt (abbb, abcb i abc).
Arborele de derivare pentru irul abc (abordare
descendenta):
10
5
4/12/2017
Derivare dreapta, bottom up
LR: irul de tokeni se
parcurge din stnga (L)
Tokenii sunt adugai pe
o stiv
Se compara partea
dreapt a stivei (R) cu
partea dreapt a unei
producii
De ce primul id nu a fost
transformat n Expr?
Decizie : SHIFT sau
REDUCE
11
Analiza LL, LR
Vrem sa evitam backtrackingul
O clas de gramatici independente de context care
permit o analiza determinist.
Alg. LL(k) analizeaza left-to-right, derivare stanga
Alg. LR(k) analizeaza left-to-right, derivare dreapta
K lookahead (cati tokeni sunt cititi)
LL(k) <LR(k)
Algoritmul folosit nu depinde de limbaj, gramatica
da.
12
6
4/12/2017
Alternativa la backtracking: analiza
predictiv (descendent recursiv)
Fiecare neterminal are o functie care il parseaza
Daca simbolul apare in partea dreapta a productiei
func a se va apela recursiv
Daca un neterminal apare in partea stanga a mai
multor produc i se alege una din ele in func e
de urmatorii atomi lexicali (lookahead)
13
Recursivitate stnga
14
7
4/12/2017
Recursivitate stnga
15
Gramatici de tip 2
recursivitate stng
16
8
4/12/2017
Exemplu
17
Eliminarea recursivitii stngi
18
9
4/12/2017
Exemplu
19
Eliminarea recursivitii stngi
20
10
4/12/2017
Exemplu de parser recursiv
21
Analiza descendent recursiv
22
11
4/12/2017
Cum punem condiiile?
Folosim doua seturi de terminali First si
Follow
Plus Nullable multime de neterminali ce pot
deriva in .
Setul de terminali-prefix ai neterminalului u -
notat First( u )
Setul de terminali care apar pe prima pozitie intr-
o derivare legala a lui u
Daca u=>* , atunci e in First(u)
Setul de terminali care pot urma dupa u
notat Follow(u) 23
Cum construim FIRST
24
12
4/12/2017
Cum construim FOLLOW
25
Cum construim FOLLOW
26
13
4/12/2017
Cum construim FOLLOW
27
Cum construim FOLLOW
28
14
4/12/2017
Cum construim FOLLOW
29
Algoritmul generic recursiv LL(1)
Pentru fiecare non-terminal A se creaza o functie de
parsare.
Pentru fiecare regula A se adauga un test
if (lookahead in FIRST(FOLLOW(A)) )
Pentru fiecare nonterminal din se apeleaza functia de
parsare.
Pentru fiecare terminal din , se verifica lookahead-ul
(match)
30
15
4/12/2017
Factorizare stnga
31
Factorizare stnga
32
16
4/12/2017
Eliminarea ambiguitilor
33
Eliminarea ambiguitilor
34
17
4/12/2017
Dangling else
35
Dangling else
36
18
4/12/2017
Automatizarea parsrii
Echivalenta cu un automat push-down
Parsarea se poate face cu un automat si o
tabela.
37
Data viitoare
Automate push-down
1 Parsere LL
2 Analiza sintactic LR
38
19
4/12/2017
NTREBRI?
20