Buna ziua tuturor !
Astazi, in saptamana a 8-a ne ocupam de a patra etapa din constructia compilatorului, cu cei care acum o saptamana nu si-au terminat proiectele, adica semigrupa a II-a.
Nu uitati sa faceti refresh din cand in cand !
Daca v-ati terminat capitolul Contextul din cartea de compilatoare, atunci puteti trece la:
1) Vizionarea unui film de ajutor, despre Clasificarea gramaticilor. (S6301359.AVI si S6301360.AVI) dintr-un curs anterior.
Voi incarca aceste filme pe Wetransfer si veti avea link-urile disponibile pe e-mail.
Acest lucru va mai dura ...
Intre timp, haideti sa incercam niste mici exercitii cu gramatici, considerati-le recapitulari din capitolul anterior:
Exercitiul 1: Gasiti limbajul generat de o gramatica G, precizand si tipul gramaticii:
N = {S} T = {0,1,2}
P = { S -> 0S0 | 1S1 | 2S2| 0}
Este ca si cum ar fi setul de productii:
P = { S -> 0S0, (regula 1)
S -> 1S1, ( 2)
S -> 2S2, ( 3)
S -> 0} ( 4)
Intrebare de control: Fiecare S , cand se transforma , ce fel de simboluri produce in jurul lui ?
Notati multimea aceast cu M: M = {....}
Intrebare de control: La ultimul pas in ce se transforma S-ul ?
Raspuns: Limbajul final este multimea sirurilor (stringurilor) care incep cu orice secventa de 0,1,2 , urmeaza un zero, urmeaza tot o secventa de 0,1,2. Ambele secvent sunt si vide. Ambele secvente au acceasi lungime, secventele sunt una imaginea in oglinda a celeilalte.
Exercitiu: Care dintre elementele de mai jos nu fac parte din limbaj ?
0, 000, 001, 002, 100, 101, 102, 200, 201, 202 ?
Verificati: 0, 000, 001, 002, 100, 101, 102, 200, 201, 202 ?
Exercitiu: Scieti o derivare in gramatica, aplicand regulile de productie 1,2,3,4, in aceasta ordine:
Sa incercam impreuna:
S => 0S0 => 01S10
am aplicat regulile 1 si 2 deja...
S => 0S0 => 01S10 =>012S210 =>0120210
am aplicat si regulile 3 si 4, am obtinut doar terminali.
Intrebare de control: Daca in loc de zero , unu si doi am avea urari de an nou,
0 = La multi ani !
1 = Sanatate !
2 = Bucurie !
ce fel de scrisori de felicitare ar genera gramatica ?
Rapuns:
Daca am avea regulile:
S-> La multi ani ! S La multi ani !
S -> Sanatate ! S Sanatate !
S -> Bucurie ! S Bucurie !
S -> La multi ani !
(Am boldit neterminalul S, vedti ca el dispare pina la urma din textul final.)
Prin aplicarea in ordine a rgulilor 0,1,2,3,4 (desi se pot aplica si altfel)
ar duce la textul:
La multi ani ! Sanatate ! Bucurie ! La multi ani ! Bucurie ! Sanatate ! La multi ani !
... in care am evidentiat terminalul provenit din aplicarea regulii 4.
Exercitiu: Dati exemplu de o astfel de scrisoare de felicitare, si scrieti pasii prin care se obtine ea, prin procesul de derivare.
Hei, nu e greu, este doar un joc de simboluri in care unele simboluri se inlocuiesc cu alte secvente de simboluri !
Raspuns la intrebarea initiala : De ce tip este aceasta gramatica ?
Uitati-va la forma regulilor si mai ales la NUMARUL de terminali si neterminali din dreapta si din stanga regulilor.
O fi gramatica de tip trei ?
Pai acelea au toate regulile doar de forma: A -> aB si A ->b (A,B neterminalii, cei ce se transforma, a,b, terminalii).
Numaram si noi: S->0S0 .... 3 simboluri in dreapta, prea multe, nu e de tip trei!
O fi gramatica de tip doi ?
Pai aceea are reguli cu un neterminal in stanga regulii, si secventa de simboluri in dreapta (Exceptie doar regula S - > "" scrisa , "S trece in epsilon").
Sa vedem, au regulile noastre exact un neterminal in stanga regulii ?
S -> 0S0, (regula 1)
S -> 1S1, ( 2)
S -> 2S2, ( 3)
S -> 0} ( 4)
Ne uitam in stanga semnului -> care desparte partile regulii.
Si gasim doar un singur neterminal, la noi, in acest caz, pe S. Puteau fi si altii, dar tot singuri.
Acest lucru inseamna ca gramatica este independenta de context, adica in orice context ar apre S, oriunde se foloseste un S care se va transforma, nu depinde de ce este pe linga el, ca sa aplic regula.
(nu e o regula ca: aSb -> acccb care s-ar aplica doar cu S intre a si b).
Nota: Cuvantul context este folosit cu doua sensuri in acest curs:
1) In cartea de compilatoare prin context se intelege tabela de simboluri. Intr-adevar, folosirea unei variabile, functii si a orice mai declaram se face conform cu declaratia scrisa mai inainte, in textul inconjurator instructiunii, adica e un context.
2) In cartea de LFA: Se foloseste la gramatici independente de context, numite si gramatici de tip 2. Acestea sunt gramaticile limbajelor de programare uzuale. V-ar conveni ca intr-un limbaj, ceva, o instructiune sa zicem, sa se scrie asa ... intr-un loc si altfel ... in altul. Nu.
Deci oriunde apare o instructiune , de exemplu incrementarea x++ (sau oricare alta, sau orice declaratie, sau orice provine dintr-un neterminal) ea sa se scrie la fel ! Pare banal, o cerinta banala. Dar matematica, algebra LFA o cere explicata.
O fi gramatica monotona de tip 1 ?
Acelea erau gramatici monotone, dreapta regulii sa fie mai lunga ca stanga,
da se confirma si la gramatica noastra...
In stanga reguliilor e un simbol, in dreapta sunt 1 sau 3.
Da , este si o gramatica de tip 1 dar stii de ce ?
Fiindca tipurile de limbaje (generate de gramatici) sunt incluse unul in altul:Tipul 0 include Tipul 1 include tipul 2(mai greu de demonstrat) care include Tipul 3.
O fi gramatica de tip 0 ?
Pai acestea sunt cele mai generale ... sigur este, deoarece clasa lor le include pe toate celelalte.
Adevarat, dar nerelevant.
Raspuns: Era gramatica de tip 2, independenta de context.
S-a incarcat filmul 1/3-4 , vine mail cu link....mergeti pe e-mail.
S-a incarcat filmul 2. 100% , hai pe e-mail.
O veste proasta, nu va pot trimite film despre tabela de simboluri, are 2.2 GB si Wetransfer accepta doar 2GB. Sa vad poate il pot recoda... si asa avea defecte.
Partea practica, independenta de teoria de mai sus:
In dosarul Lab4 de pe stick-ul dvs, continuati lucrul la compilator, conform capitolului 4 al cartii de compilatoare. [pg 33-47], cu mici variatii depinzand de editie]
Punct de control:
La compilarea fisierului simple p2bad.sim:
let
integer x,y,y.
in
write (z);
end
va trebui sa obtineti mesajele date de functiile:
install() : care va zice
"y is already defined"
si
context_check(): ... care va zice:
"z is an undeclared identifier".
Tema: Trimiteti pe e-mail o captura de ecran cu mesajele obtinute la compilarea micului program.
Niciun comentariu:
Trimiteți un comentariu