(sunt intrebari din urma)
Q1.Cand vine vorba de gramatici:
G=(N,Σ,P,S)
| | | |
| | | ----simbolul de start, capul primei reguli
| | --------multimea de reguli gramaticale/reguli de sintaxa
| -----------alfabetul limbajului = terminalii gramatici, ei apar in text
--------------denumirele acelor parti variabile din text, sunt categoriile gramaticale (ar spune lingvistii).
| | | |
| | | ----simbolul de start, capul primei reguli
| | --------multimea de reguli gramaticale/reguli de sintaxa
| -----------alfabetul limbajului = terminalii gramatici, ei apar in text
--------------denumirele acelor parti variabile din text, sunt categoriile gramaticale (ar spune lingvistii).
Se poate să ne detaliati ce anume face fiecare parametru (N,Σ,P,S )?
pentru a înțelege cum funcționează o gramatică .
R1:
Neterminalii: Sunt denumiri pentru categorii de part de text inclusiv categoria generala a programelor, acesta e un neterminal special, notat mai sus cu S.
Sa luam de exemplu un text cu forma aproape fixa, sa zicem prognoza meteo:
"Azi sunt 4 grade Celsius si vantul bate cu 3 metri pe secunda."
daca de exemplu am avea de generat aceste texte, este evident ca am citi datele de pe niste senzori si ar putea fi orice numar si orice viteza a vantului.
Textul nostru sablon este format din restul cuvintelor ( se vor numi terminali aceste parti de text care se regasesc in textul final) si niste "sabloane" , niste jockeri daca vreti care vor fi inlocuiti de altceva.
Imaginati-va textul scris evidentiind aceste parti variabile, acestea sunt neterminalii:
"Azi sunt <temperatura_grade> grade Celsius si vantul bate cu <viteza_vant> metri pe secunda." unde < si > nu fac decat sa delimiteze portiunile care trebuiesc adaugate conform altor reguli.
Observati ca ne vor trebui niste reguli ca sa spunem ca temperatura poate fi intre anumite valori sau macar ca este formata din cifre.
<temperatura_grade> -> <cifra>
<temperatura_grade> -> <temperatura_grade> <cifra>
Iar
<cifra> -> 0 |1 |2 |3 |4| 5| 6| 7| 8| 9
Evident, 0 ,1 ,2 ... 9 sunt terminali care apar in sirul din dreapta regulii.
Exercitiu: Cautati in fisierul Bison simple.y de la laborator niste reguli similare ca mod de functionare (genereaza un sir de .... ceva) dar scrise cu alta notatie, cea de la Bison.
Observati ca ne vor trebui niste reguli ca sa spunem ca temperatura poate fi intre anumite valori sau macar ca este formata din cifre.
<temperatura_grade> -> <cifra>
<temperatura_grade> -> <temperatura_grade> <cifra>
Iar
<cifra> -> 0 |1 |2 |3 |4| 5| 6| 7| 8| 9
Evident, 0 ,1 ,2 ... 9 sunt terminali care apar in sirul din dreapta regulii.
Exercitiu: Cautati in fisierul Bison simple.y de la laborator niste reguli similare ca mod de functionare (genereaza un sir de .... ceva) dar scrise cu alta notatie, cea de la Bison.
Terminalii: Sunt acele simboluri care se gasesc in sirul final, in textul final, dupa ce prin aplicarea regulilor, toti neterminalii se transforma in terminali.
Observatie: Si la texte putem lucra cu tipul Char sau cu tipul String. Si aici sunt posibile doua abordari. La unele probleme si aplicatii Σ este o multime de caractere iar la altele Σ este o multime de stringuri.
In exemplul de mai sus am putea considera:
Σ = {'a','b','c', 'd', ... 'z', ' ', 'A', ....'Z', '.' } reunit cu {0,1,2,...9}
ceea ce ne permite sa formulam texte cum e cel de mai sus, fiindca avem litere, cifre, spatiu si punct.
Exercitiu: Puteti reduce multimea Σ la o submultime a ei, tot din caractere.
Varianta: Putem reduce multimea sigma si la o multime de cuviunte.
Care ar fi multimea ?
Σ = { "Azi", "sunt" , "grade" , "Celsius" , "si ,"vantul" , "bate", "cu" ,"metri" ,"pe" ,"secunda" ,"." }
Regulile gramaticale: Pentru fiecare neterminal exista una sau mai multe reguli (nedeterminism aici) care spun cum se expandeaza neterminalul respectiv (sau secventa de neterminali si terminali din din stanga regulii)
Exemplu de regula de expansiune a neterminalului <cifra>:
<cifra> -> 0 |1 |2 |3 |4| 5| 6| 7| 8| 9
Aceasta e de fapt o notatie pentru mai multe reguli:
<cifra> -> 0
<cifra> -> 1,
....
samd
<cifra> -> 2
Regulile pot fi mai complicate:
<comanda> -> Skip ;
<comanda> -> If <Exp> then <comenzi> else <comenzi> fi.
Intrebare: Ce are in stanga si in dreapta fiecare din regulile de mai sus ?
Simbolul de start: Totusi exista si o categorie , cea mai vasta, de texte. In exemplul nostru ar fi <prognoza_meteo>.
Avem deci intre regulile gramaticii si :
<prognoza_meteo> -> Azi sunt <temperatura_grade> grade Celsius si vantul bate cu <viteza_vant> metri pe secunda.
De ce este el important:
1) Pentru a genera texte complete, avem nevoie sa pornim de la el. Daca as porni de la <cifra> as genera doar o cifra, nu frazele complete de mai sus.
2) La gramaticile limbajelor de programare trebuie indicat conform carei sau caror reguli se scriu programele. Simbolul de start va fi program sau unul similar, capul regulii care da forma programelor.
Exercitiu: Cautati in fisierul bison simple.y locul unde este declarat neterminalul de start al gramaticii limbajului Simple.
Indicatie: E un cuvant start acolo...
Continuam ...pls wait and refresh!
Cum functioneaza o gramatica ?
Aici sunt de fapt doua intrebari deoarece gramaticile pot fi privite in doua moduri:
R1) Ca niste gramatici generative, deci ca un set de reguli care genereaza texte!
Exercitiu: Scrieti programul care produce textele de mai sus, scriind pentru fiecare neterminal o functie (sau procedura) care scrie ce are de scris si cand da de un neterminal apeleaza alta functie/procedura, corespunzatoare acestuia.
Ce ati observat facand implementarea ?
Acest mod de a genera texte este surprins de acele reguli de derivare din curs !
Derivare, k-derivare, + derivare , * derivare.
R2) Gramatica poate fi inteleasa ca un set de specificatii dupa care functioneaza un parser = analizator sintactic. El face operatia inversa generarii, el analizeaza un text gata primit.
Este ceea ce facem la laborator, cand dam bison-ului sau altui generator de parsere o gramatica.
Nu sunt independente, mai curand se completeza insa folosesc alte notatii.
Legaturile
nu sunt evidente iar la practica se folosesc doar ... elemente la care
ajungem din loc in loc pe parcursul cursului teoretic, aceasta si din cauza ca nu
facem un compilator atat de mare ca la un limbaj real.
Sfarsit .
Observatie: Si la texte putem lucra cu tipul Char sau cu tipul String. Si aici sunt posibile doua abordari. La unele probleme si aplicatii Σ este o multime de caractere iar la altele Σ este o multime de stringuri.
In exemplul de mai sus am putea considera:
Σ = {'a','b','c', 'd', ... 'z', ' ', 'A', ....'Z', '.' } reunit cu {0,1,2,...9}
ceea ce ne permite sa formulam texte cum e cel de mai sus, fiindca avem litere, cifre, spatiu si punct.
Exercitiu: Puteti reduce multimea Σ la o submultime a ei, tot din caractere.
Varianta: Putem reduce multimea sigma si la o multime de cuviunte.
Care ar fi multimea ?
Σ = { "Azi", "sunt" , "grade" , "Celsius" , "si ,"vantul" , "bate", "cu" ,"metri" ,"pe" ,"secunda" ,"." }
Regulile gramaticale: Pentru fiecare neterminal exista una sau mai multe reguli (nedeterminism aici) care spun cum se expandeaza neterminalul respectiv (sau secventa de neterminali si terminali din din stanga regulii)
Exemplu de regula de expansiune a neterminalului <cifra>:
<cifra> -> 0 |1 |2 |3 |4| 5| 6| 7| 8| 9
Aceasta e de fapt o notatie pentru mai multe reguli:
<cifra> -> 0
<cifra> -> 1,
....
samd
<cifra> -> 2
Regulile pot fi mai complicate:
<comanda> -> Skip ;
<comanda> -> If <Exp> then <comenzi> else <comenzi> fi.
Intrebare: Ce are in stanga si in dreapta fiecare din regulile de mai sus ?
Simbolul de start: Totusi exista si o categorie , cea mai vasta, de texte. In exemplul nostru ar fi <prognoza_meteo>.
Avem deci intre regulile gramaticii si :
<prognoza_meteo> -> Azi sunt <temperatura_grade> grade Celsius si vantul bate cu <viteza_vant> metri pe secunda.
De ce este el important:
1) Pentru a genera texte complete, avem nevoie sa pornim de la el. Daca as porni de la <cifra> as genera doar o cifra, nu frazele complete de mai sus.
2) La gramaticile limbajelor de programare trebuie indicat conform carei sau caror reguli se scriu programele. Simbolul de start va fi program sau unul similar, capul regulii care da forma programelor.
Exercitiu: Cautati in fisierul bison simple.y locul unde este declarat neterminalul de start al gramaticii limbajului Simple.
Indicatie: E un cuvant start acolo...
Continuam ...pls wait and refresh!
Cum functioneaza o gramatica ?
Aici sunt de fapt doua intrebari deoarece gramaticile pot fi privite in doua moduri:
R1) Ca niste gramatici generative, deci ca un set de reguli care genereaza texte!
Exercitiu: Scrieti programul care produce textele de mai sus, scriind pentru fiecare neterminal o functie (sau procedura) care scrie ce are de scris si cand da de un neterminal apeleaza alta functie/procedura, corespunzatoare acestuia.
Ce ati observat facand implementarea ?
Acest mod de a genera texte este surprins de acele reguli de derivare din curs !
Derivare, k-derivare, + derivare , * derivare.
R2) Gramatica poate fi inteleasa ca un set de specificatii dupa care functioneaza un parser = analizator sintactic. El face operatia inversa generarii, el analizeaza un text gata primit.
Este ceea ce facem la laborator, cand dam bison-ului sau altui generator de parsere o gramatica.
Q2.
De asemenea se poate să explicati ce puncte comune au cursul si
laboratorul pt a stii dacă se pot completa una pe alta sau dacă acestea
sunt independente una de cealaltă ?
Nu sunt independente, mai curand se completeza insa folosesc alte notatii.
Da, de ex C2 gramatici <-> C2 folosire Bison.
Da, un curs care va urma , Automate si expresii regulare <-> C3 - Flex
Da, un curs care va urma Arbori de sintaxa <-> Optimizare de arbore C4
....
veti gasi si alte potriviri, dar rolul teoriei este sa furnizeze dupa un anumit demers anumite elemente pentru practica, a caror teorie ramane ascunsa practicienilor, de aici senzatia ca teoria nu se foloseste toata la practica.
Nici cand tai painea cu cutitul nu ma intereseaza din ce Otel OLE ... bla bla este facut cutitul, la ce tratamente termice a fost supus, ci doar sa inteleg cum duritatea lui e afectata de tratamentele termice, de exemplu ca sa nu il stric expunandu-l la fierbinte si rece (decalire).
Daca insa dau examen la specialitate va trebui sa stiu si detaliile teoretice si cele practice.
Sfarsit .
Niciun comentariu:
Trimiteți un comentariu