Condiţii examen Este permis cu documentaţie. Documentaţie înseamnă carte, caiet sau foi legate cu numele şi prenumele scris pe prima pagină. Foile volante sunt considerate fiţuici nu documentaţie. Documentaţia este individuală. Nu se acceptă 2 studenţi cu aceeaşi documentaţie. 01 Curs – 05.10.2015 ************************** Importanţa domeniului – Error: Reference source not found – pag. 7 Ce este un compilator – Error: Reference source not found – pag. 11 Limbajele de programare – Error: Reference source not found – pag. 3 ************************** 02 Curs – 12.10.2015 ************************** Descrierea sintaxei şi semanticii unui limbaj – Error: Reference source not found – pag. 3 Tipuri de gramatici folosite: gramatici regulare ( expresiilor regulare) în analiza lexicală ,
Transcript
Condiţii examen Este permis cu documentaţie. Documentaţie înseamnă carte, caiet sau foi legate cu numele şi
prenumele scris pe prima pagină. Foile volante sunt considerate fiţuici nu documentaţie.
Documentaţia este individuală. Nu se acceptă 2 studenţi cu aceeaşi documentaţie.
01 Curs – 05.10.2015
**************************
Importanţa domeniului – Error: Reference source not found – pag. 7
Ce este un compilator – Error: Reference source not found – pag. 11
Limbajele de programare – Error: Reference source not found – pag. 3
**************************
02 Curs – 12.10.2015
**************************
Descrierea sintaxei şi semanticii unui limbaj – Error: Reference source not found – pag. 3
Tipuri de gramatici folosite: gramatici regulare (expresiilor regulare) în analiza lexicală,
respectiv a gramaticilor independente de context în analiza sintactică.
Gramatică BNF
Exemplu de gramatică (BNF) ce descrie un minilimbaj de programare:
<program> —> begin <lista_de_instructiuni> end
<lista de instructiuni> —> <instructiune> | <lista_de_instructiuni> <instructiune>
Aici apar două tokenuri: LITERA şi NUMĂR. Acestea pot la rândul lor să fie descrise prin
acelaşi mecanism:
LITERA —> a | b | c | d | e | f | g | h | i | j | k | 1 | m | n | o | p | q | r | s | t | u | v | w | x | y | z
NUMĂR —> < cifra > | NUMĂR < cifra >
<cifra> —> 0|1|2|3|4|5|6|7|8|9
**************************
03 Curs – 19.10.2015
**************************
1.3. Specificarea unui limbaj de programare 18
2. ANALIZA LEXICALĂ22
2.1. Detectare şi clasificare 22
if (x==z) {x = y;}
Etapa de clasificare necesită ca fiecărui atom lexical să i se asocieze o singură clasă de
apartenenţă. În cazul în care un atom nu poate fi asociat nici unei clase, adică nu respectă condiţiile
de apartenenţă la clasa respectivă, atunci analiza lexicală se termină cu insucces: a fost detectată o
eroare lexicală.
Algoritmul 2.1 Analiza lexicală - versiunea 1
while (mai există caractere necitite în sursă) do
detectare (atom);
clasificare(atom);
codificare(atom)
end while
Clasele de atomiClasele de atomi corespunzătoare oricărui limbaj de programare au menirea de a descrie toate
entităţile importante dintr-un limbaj:
identificatori;
constante;
cuvinte rezervate (cuvinte cheie);
operatori;
separatori (delimitatori).
Pentru clasele cuvintelor rezervate, separatorilor şi operatorilor se testează apartenenţa la
mulţimea respectivă. Pentru clasele identificatorilor şi constantelor este necesar să se verifice
respectarea criteriilor corespunzătoare, care sunt descrise prin:
expresii regulare;
automate finite.
2.2. Codificare
Tabelul următor prezintă o astfel de codificare parţială. în realitate, fiecare atom lexical are un
cod ataşat.
Tabel de coduri
Atom Cod
Identificator 1
Constantă 2
+ 3
– 4
== 10
( 11
) 12
{ 13
} 14
= 15
; 16
if 17
else 18
for 19
while 20
do 21
... ...
Astfel rezultatul analizei lexicale, numit Forma Internă a
Programului (FIP), reprezintă o secvenţă de perechi, în care primul
element este codul corespunzător, iar al doilea element al perechii îl
reprezintă poziţia
if (x==z) {x = y;}
Cod Atom Poziţie în TS
17 011 01 110 01 312 013 01 115 01 216 014 0
SUBIECT DE EXAMEN nr. 1
Se va da altă instrucţiune if (x==z) {x = y;}
Să se intocmească forma internă a programului (FIP)
2.3. Modelul analizorului lexical 27
Algoritmul 2.2 Analiza lexicală - versiunea 2
INPUT: program sursă., codificare
OUTPUT: FIP, TS, erori
while (mai există caractere necitite în program sursă) do detectare(atom);
if este cuvânt rezervat sau operator sau separator then genFIP(cod,0)
else
if este identificator then
indice := poz(atom,TS);
genFIP(codidentificator, indice);
else
if este constantă then
indice := poz(atom,TS);
gcnFir(cod.constanta, indicc),
else
mesaj:”Eroare lexicala la atomul:’1, atom
end if
end if
end if
end while
**************************
04 Curs – 26.10.2015
**************************
4. Expresii regulare Error: Reference source not found
Notaţii utilizate în gramatici:a, b, c – elemente terminale;
= {a, b, c} – alfabet, mulţime de elemente terminale,
u, v, x, y, z – secvenţă de elemnte terminale
w = secvenţă de elemente terminale,
* = {… u, v, x, y, z} – mulţimea secvenţelor peste , secvenţe de simboluri terminale. O secvenţă de elemente terminale se numeşte propoziţie (cuvânt).
N = {A, B, C} – mulţime de elemente neterminale;
{ β,α, } – secvenţă de elemente terminale şi neterminale;
(N )* = { β,α, } – mulţimea secvenţelor peste mulţimea elementelor terminale reunite cu mulţimea elementelor neterminale. Secvenţele de elemente terminale şi neterminale se numesc forme propoziţionale.
A a, producţie. Exemplu: număr binar 01101. O producţie βα se mai notează
β,α P, şi se înţelege că α dintr-o anumită secvenţă se înlocuieşte cu β .
Gramatică
Definiţie:
Ansamblul G = ( N, , P, S ) unde:
N este un alfabet de simboluri neterminale; este un alfabet de simboluri terminale; P este o mulţime de finită de producţii, P (N )* N (N )* (N )*; S N – simbolul iniţial de start;
se numeşte gramatică.
Clasificarea gramaticilor. Ierarhia lui Chomsky 1
4. Expresii regulare Error: Reference source not found 2
Teoremă: 3
Soluţia ecuaţiei de forma X = X.a + b este X = b.a*
Se dă automatul finit următor, care reprezintă o gramatică regulară. Să se calculeze expresia regulară corespunzătoare.
Expresiile regulare ataşate vârfurilor A, B şi C sunt următoarele:o A = ε + Cbo B = Aao C = Ab + Bb + Ca
Valoarea ε defineşte starea A ca şi stare iniţială a automatului. Starea C este stare finală a automatului.
1 Error: Reference source not found. Error: Reference source not found2 Error: Reference source not found. Error: Reference source not found3 Error: Reference source not found. Error: Reference source not found
Rezolvarea sistemului de ecuaţii regulare: 4
C = Ab + Bb + Ca = (ε + Cb)b + Aab + Ca == (ε + Cb)b + (ε + Cb)ab + Ca == εb + Cbb + εab + Cbab + Ca =
= b + ab + C(bb + bab + a) =
Rezultă C = (b + ab)(bb + bab + a)*
Exemplu: 5
SUBIECT DE EXAMEN nr. 2.
Se va da un alt automat finit, care reprezintă o gramatică regulară. Să se calculeze expresia regulară corespunzătoare.
**************************
05 Curs – 02.11.2015
**************************SUBIECT DE EXAMEN – Să se explice forma regulară a constantei
întregi fără semn.
2. Constantă: şir de caractere care conţine doar cifre, cu următoarele excepţii:
• primul caracter poate fi ”+“ sau ” –“ în cazul constantelor cu semn;
• poate conţine caracterul ”.” cel mult o dată, în cazul constan¬telor reale.
Prima cifră este nenulă, exceptând constanta 0 sau numerele subunitare, de exemplu 0.56.
6 Error: Reference source not found. Error: Reference source not found – pag. 30.
Subiecte de exmen
Tabele de dispersie cu înlănţuire
Tabele de dispersie cu înlănţuire
Exemplul 2.2. Presupunem că într-un program se întâlnesc următoarele nume simbolice
(în această ordine) iar valoarea funcţiei de dispersie asociate este cea din paranteză:
Forma Internă a Programului (FIP) – Se dă şi lungimea Tabelei de dispersie.
NODE (1), AN (3), FUNCTION (9), STORE (2), B (9), ADD (3), BRAN (9),
PARAMETER (9).
SUBIECT DE EXAMEN, nr. 4.
Se va da o altă Formă Internă a Programului şi lungimea Tabelei de dispersie.
Să se întocmească cele două tabele de dispersie.
**************************
07 Curs – 16.11.2015
**************************
3.1. Analizor sintactic descendent cu reveniri 46
**************************
08 Curs – 23.11.2015
**************************
3. Automate finite7
Mulţimea configuraţiilor
(q, w) este o configuraţie
tranziţia(p, aw) (q, w)
Configuraţia (q0, w) se numeşte configuraţie iniţială, iar (q, ), q F se numeşte configuraţie finală.
3.1.1. Modelul analizorului sintactic descendent cu reveniri498
Automatul push-down corespunzător analizorului sintactic descendent cu
reveniri poate fi caracterizat de următoarea configuraţie [Şer87):
(s, i, α, β)
Expandare
Avans
Revenire
Altă încercare
Succes
7 Error: Reference source not found. Error: Reference source not found8 Error: Reference source not found. Error: Reference source not found – pag. 49.
