luni, 30 martie 2020
LFA - (si IFR) Compilatoare - Cap 4 - Contextul [pg33]-[pg47]
Sper ca v-ati pregatit Linux-urile, Flex-ul si Bison-ul, editorul de texte si dosarul Lab4. In acest dosar Lab4 copiati toate fisierele din dosarul Lab3 si vom continua constructia compilatorului.
Nota: Comozii vor dori sa lucreze pe vechile fisiere. Pt a dovedi participarea regulata la aceste lucrari de laborator voi cere tot setul de dosare de laborator.
Voi incepe cu niste motivatii ale prezentei acestui capitol pe care nu le veti intelege,presupun, daca nu faceti urmatorul experiment:
Scrieti programul Simple:
let
integer x,x,y.
in
write (z);
end
Si sa dezbatem putin: Este el un program corect ?
1) Programatorii vor spune plini de siguranta, Nu , cel putin pentru doua motive: are o variabila dublu declarata, x-ul si o variabila nedeclarata dar folosita, z-ul.
Dar daca compilati programul de mai sus, salvat de ex sub numele p2bad.sim:
$ ./simple p2bad.sim
sau
$ ./simple.exe p2bad.sim
Ce spune compilatorul ?
Cum interpretati acest lucru ?
2) Programul este corect in masura in care respecta regulile de sintaxa.Si le respecta. Are tot ce trebuie sa aiba conform gramaticii limbajului Simple.
Forma generala let ... in ... end declaratia integer x,x,y. apoi instructiunea write cu expresia (z) corecta in paranteza si ; la sfarsit.
Unde este problema ? Pai sunt doua, de aceeasi natura. Lipsesc verificarile declaratiilor variabilelor in dictionarul de variabile. Va trebui sa implementam asa numita "symbol table" tabela de simboluri.
Deschideti manualul de constructia compilatoarelor (in limba romana) la pagina 33, capitolul al 4-lea.
Ce facem de fapt in capitolul al IV-lea ? Implementam o forma simpla de tabela de simboluri, reflectand faptul ca in limbajul Simple, variabilele trebuiesc declarate (si numai odata) inainte de a fi folosite. Vor trebui facute doua verificari: Sa evitam dubla declarare cautand variabila in context si sa verificam din instructiuni.
Exista o mica problema: Analizor lexical trimite numai niste raspunsuri generice: return(NUMBER); return(IDENTIFIER); nu transmite si care ESTE EXACT acel identificator sau numar. Vor trebui facute niste modificari in fisierul simple.lex
Tema: Lucrati va rog capitolul al IV-lea din cartea de compilatoare, incepind de la pagina 33 -> pg 47.
Cateva explicatii vor fi totusi necesare, in plus:
La modulul tabela de simboluri, cu numele ST.h
[pg 34] *sym_table este pointerul la tabela de simboluri implementata ca lista simplu inlantuita, de elemente symrec, observati ca este initializata cu (symrec*)0.
[pg34] putsym e functia care pune un record nou in lista, sym_table va arata noul element iar pointerul din acesta va arata restul listei.
Exercitiu: Descifrati codul functiei putsym desenand (ca la cursul de structuri de date) elementele listei inlantuite si pointerii. Noroc ca e in carte explicat rand cu rand :))
[pg38] Inainte de paragraful "Modificarile analizorului sintactic ..." Este un paragraf mai sus, care incepe cu "Observati .." si deasupra un return 0 in unele editii ale cartii.
Nu se poate ca o functie sa se termine cu:
return ptr;
return 0;}
Taiati-l pe return 0. Evident, functia de cautare getsym() returneaza pointer la elementul gasit, sau un zero rezultat din algoritm daca nu gaseste. Nu returneaza zero intotdeauna.
[pg 39] Paragraf 2 de jos: Fraza "Simple.lex va fi modificat astfel": se va citi
"Simple.y va fi modificat astfel:". Modificam parserul facut cu Bison si salvat in fisierul simple.y.
[pg39] Dupa:
%start program
asigurati-va ca toti acei %token sunt:
%token INTEGER SKIP IF THEN ELSE FI WHILE DO END ASSGNOP
(ca e INT sau INTEGER ca este ASSGNOP sau ASIGNOP de fapt nu conteza cum ii notati dar notati-i si folositi-i consecvent).
Erori ciudate veti obtine daca uitati asazisul record semantic !
%token <id> IDENTIFIER
Aici explicam Bisonului ca fiecare IDENTIFIER va avea undeva intr-o structura de date un camp numit .id care ii corespunde. De ce ?
Noi am vrea sa punem in tabela de simboluri id-ul, numele fiecarei variabile. Dar analizorul lexical spunde doar ca a gasit un IDENTIFIER nu ofera odata cu el si o "sacosa" pardon, camp dintr-o structura de date in care sa stocam acest identificator, de exemplu fie el "R2D2".
In regulile gramaticale pe care le manipuleaza Bison-ul aveti linga fiecare terminal sau neterminal din regula o variabila $i unde i este pozitia elementului terminal sau neterminal in partea dreapta a regulii.
Exemplu: Pt o regula:
<exp> -> <stanga> + <dreapta> Bison va producecand foloseste regula 3 variabile:
$$ $1 $2 $3
Daca de exemplu $1 este valoarea expresiei din stanga si $3 este valoarea expresiei din dreapta va trebui sa calculam pe $$ ca fiind suma valorilor lor.
Exemplul 2, [pg 40]. Daca intr- declaratie scrisa in codul Bison
declarations : /*empty*/
| INTEGER id_seq IDENTIFIER '.' {install($3);}
...inseamna ca i-am spus Bisonului ce sa faca dupa ce a parcurs declaratia si a trecut de '.'-ul ei final: Sa execute codul din acolada si sa apeleze functia install( $3) de instalare a valorii semantice asociate celui de-al treilea element din regula.... numaram ... acesta este IDENTIFIER.
Astfel punem in tabela de simboluri IDENTIFICATORUL care este valoarea semantica asociata unui atom IDENTIFIER.
Exemplul 3 [pg 40]: Daca atomii lexicali care sunt numerele in practica sunt numiti prin token-ul NUMBER este corecta regula:
exp: INT
| IDENTIFIER {context_check($2); } eroare la pg 40 , ultimul rand.
Corect:
exp : NUMBER
| IDENTIFIER {context_check($1); }
De ce ? In expresiile aritmetice intalnesti numere nu cuvantul "integer" care aparea in declaratii. Si daca o expresie este un identifier, regula are o parte stanga , exp, si o parte dreapta IDENTIFIER deci nu are sens sa vorbim de lementul al 2-lea din partea dreapta a regulii:
<exp> -> IDENTIFIER (ok, am scris-o cu alta notatie).
1 1 2-nu este.
Cititi pina la pg 41:
Modificarile scanner-ului [pg 41]:
Deoarece codul generat de Lex nu ofera si numele concret al identificatorilor ,
se declara intai locul unde este stocat [pg 42]:
%union {char * id; --- este acelasi id din linia %token <id> ...
}
si astfel variabila Yacc/Bison yylval va avea un camp .id in care vom putea scrie , din codul pentru Lex, numele variabilei asa cum e el in textul de intrare.
De data aceasta, cand codul generat de Lex/Flex gaseste un {ID} nu mai face doar {return(IDENTIFIER);} ci :
{ID } { yylval.id = (char *) strdup(yytext);
return(IDENTIFIER);}
Adica face o dup-licare de str-ing pe care il ia din variabila yytext de-a Bison-ului/Yacc-ului si il copie in yylval.id. Mda, de fapt copie pointeru.
Va rog cititi pe cont propriu despre reprezentarea intermediara. [pg 43 si urmatoarele] si sa terminati lucrarea din capitolul 4.
Validarea partii practice:
Refaceti compilatorul si compilati iar: p2bad.sim
let
integer x,x,y.
in
write (z);
end
Ar trebui sa obtineti doua mesaje de eroare:
x is already defined
z is an undeclared identifier.
Acum e in regula, nu-i asa ?
Final C4. Ne vedem miercuri la o reluare C4 cu cei de la zi, care nu au lucrat azi luni aceasta lucrare.
LFA (si pentru IFR) - Curs din saptamana a 7-a [pg 47] -Ora a II-a
AUTOMATE FINITE
Deschideti manualul de Limbaje formale si teoria automatelor la pagina 47 (49 pe pdf).
Ati intrebat care curs se leaga cu care capitol de la practica ? Ei bine acest capitol face legatura cu capitolul al III-lea din manualul de constructia compilatoarelor. Da, grupele care sunt cu laboratorul acela terminat vor incepe sa inteleaga cum ajungem la acele expresii regulare din fisierul simple.y.
Ele sunt de fapt notatii pentru niste automate. Acele automate sunt reprezentabile usor ca niste grafuri, dar trebuiesc scrise in limbajul de programare al Flex-ului sau in alte limbaje de programare. Cum scrii un automat in limbaj de programare... vom vedea, ca o expresie regulara.
Dar stop, sa explicam ce sunt acestea...
Incepem sa citim paragraful 2.1 AFD si AFN.
Ce ati inteles din prima jumatate a paginii 47 ?
Sa rezumam si sa mai explicam cate ceva:
Iararhia lui Chomsky va indica existenta unor gramatici foarte rapide la analiza sintactica, dele de tip 3. Ele au reguli atat de simple, de felul A->aB incat pot fi transformate in altfel de dispozitive, niste dispozitive cu stari care isi schimba starea (cam ca un caleidoscop care se roteste - comparatia e putin fortata) la fiecare citire a unui atom lexical din fluxul de intrare.
Dat fiind ca toate regulile unei astfel de gramatici sunt de forma A->aB (exceptie eventualele reguli A->a) rezulta ca o astfel de regula care se aplica la citirea literei a de la intrare ar pute duce sistemul dintr-o stare notata A intr-o stare notata B.
De aici ideea unui sistem care sare (cam ca o broasca care sare de pe o piatra pe alta) de la o stare la alta in momentul cand primeste un simbol terminal (un caracter) la intrare. Sa imi amintiti sa va spun povestea broastei montane !
Dupa ce parcurge TOT textul de la intrare, ceea ce inseamnan ca dupa cele n litere ale unu text ajunge in a n+1-a stare, daca aceasta e una dintre starile numit FINALE, cuvantul este acceptat, recunoscut, validat.
a
[A] -------------------> [B]
starea A starea B
Automatele de acceptare sunt niste dispozitive pentru recunoasterea textelor (pentru analiza lexicala ar spune compilatoristul). Ele sunt finite, altfel nu le-as putea implementa practic.
Pentru a le descrie avem doua modele (modelul fizic pg 47 [e-pdf pg49]) si modelul formal (pg 48, [e-pdf pg 50]) si o reprezentare - ati folosit-o la practica, expresia regulara.
a) modelul fizic
Imaginati-va automatul construit cam ca telegraful lui Samuel morse, insirat pe un sevalet, cu rola de banda pe care scrie si capul de scriere cu un electromagnet care perforeaza banda. Acum sa schimbam imaginea putin:
Imaginati-va un telegraf pe dos, cam ca un cititor de banda perforata de la computere, care are o rola de banda cu simboluri pe care le citeste un cap de citire.
Sa mai schimbam imaginea un pic: Va amintiti acele unitati de banda magnetica din filmele SF vechi, cu calculatoare. O banda magnetica cu simboluri inregistrate trece prin fata unui cap - dar sa fie la noi numia pentru citire. Ceea ce citeste capultrece apoi la prelucrat la unitatea centrala, pe care sclipesc in film beculete, semn ca ea isi schimba starea.
Vedeti poza de la pagina 47.
Acum cititi la pg 48 paragraful despre functionarea automatului, cel putin cea informala. In esenta , daca UC ii permite, sistemul:
1) citeste un nou caracter de la intrare
deplaseaza capul de citire la urmatorul
2) trece intr-o noua stare
samd
pina termina sirul d ela intrare si ajunge intr-o stare, s-o notam f.
Va fi important sa retineti ca:
- textul ramas la intrare si starea in care ajunge formeaza o noua configurati, ele fiind puse impreuna (chiar vor fi intr-o paranteza).
- dupa terminarea textului se verifica in ce stare a ajuns automatul, nu inainte.
b)modelul formal, matematic [pg 48 la mijloc]
Ca sa simulam, ca sa notam, functionarea automatului fizic de mai sus vom folosi modelul matematic. (Orice chestie cu reguli precise de functionare e matematizabila, ba chiar si unele cu reguli mai putin precise.
Ora 17:
Definitia 2.1
In definitia automatului finit:
Q - e multimea de stari (pot fi orice, chiar si alte multimi de stari de la alt automat, v-am prevenit!)
Σ - este tot alfabelul de intrare, (simbolurile de pe sageti din diagrame)
δ : Q x Σ -> P(Q) este functie de la o stare din q si un simbol din alfabet la o stare sau mai bine la o multime de stari [P(Q) - inseamna "partile lui Q" - adica multimea submultimilor lui Q.
q0 - este starea initiala din care automatul pleaca, 0 e indice inferior de obicei dar o puteti nota si altfel.
F e submultime a lui Q - sunt starile finale, acelea in care daca automatul ajunge EXACT la sfarsitul secventei citite, TAMAN cand aceasta se termina, atunci intelegem ca textul este acceptat.
Cititi Observatia de la pagina 48 [pg 50 in e-pdf]
Nota noastra: de fapt putem defini cu definitia de mai sus doua feluri de automate:
AFD - Automat finit determinist, in care se poate sti exact in ce stare se ajunge,
Cardinalul multimii |δ(q,a)| mai mic sau egal cu 1. Aici se stie exact daca pt o stare si un simbol rezulta ori multimea vida (blocaj) sau exact o alta stare.
AFN -Automat finit nedeterminist, aici de la o stare si un simbol se ajunge la o multime potentiala de stari (cam ca la sistemele cuantice unde particula ajunge undeva intr-un spatiu dar nu stii unde, stii doar probabilitatile - la noi nu am probabilitati, doar potentialitatea). Automatul e un AFN daca macar intr-o situatie intr-o stare q:
|δ(q,a)| > 1 deci am, cumva, "mai multe stari finale simultan".
Va rog cititi observatiile de l pg 48.
Urmeaza sa definim cum se schimba configuratia (perechea aceeea stare-string de intrare) unui automat.
La fel ca la gramatici, vom defini mai multe relatii de tranzitie :
tranzitia directa
k-tranzitia
+tranzitia
*tranzitia
Gasiti definitiile lor la pg 49 [pg 51 pe e-book]. Vom relua de aici...
Final de curs ... trecem la ora de seminar/laborator.
Continuam ...
LFA (si pentru IFR) - Curs din saptamana a 7-a [pg 37]
Buna ziua si bine ati venit
Va rog sa aveti iarasi manualul de Limbaje formale si teoria automatelor la indemana, deschis la pagina 37. (nr paginii tiparite).
Faptul ca exista o ierarhie a gramaticilor, ierarhia lui Chomsky, induce o ierarhie a limbajelor. De ce, manualul nu spune, dar fiecare limbaj are o gramatica cu numar maxim. Fireste, toate limbajele decidabile ar putea avea, fiecare, o gramatica generala de tip 0. Dar daca un limbaj are o gramatica de tip 3 il vom pune la categoria limbaje de tip 3.
Cititi definitia 1.12 pg 37
In unele manuale clasele limbajelor
- dependente de context
- independente de context
- regulare
se noteaza cu L indice 1, L indice 2, L indice 3, indici inferiori, iar L-ul este un L rond, rotunjit, ca R de la numere reale.
Cititi exemple si observatii pg 37 (pg 39 in pdf).
1) La o gramatica este dificil sa faci analiza ssintactica sau un parser pentru a gasi simbolul epsilon, adica sirul vid "". Cum il recunoastem in sirul de intrare ?
Ei bine, daca totusi limbajul contine si sirul vid (si sunt limbaje dde programare chiar la care puteti compila fisierul cu text vid si obtineti codul NOP;RETURN) ,
atunci vom inventa o regula ca el sa se obtina direct din simbolul de start,
S -> ε
si vom curata celelalte reguli de prezenta lui. Metoda e in paragraful 5.3 , sustine autorul cartii.
2)Se constata imediat ca limbajele regulare sunt si independente de context, vezi forma regulilor din gramatica, eda face ca regulile de la tipul 3 sa fie si reguli de la tipul 2 de gramatici. Deci L indice 3 inclus in L indice 2. Iar Limbajele monotone sunt limbaje generale deci L indice 1 inclus in L indice 0.
Dati pagina la pagina 38. (40 in pdf).
3) de ce genereaza gramaticacu regula S -> aS limbajul vid ? Fiindca singura sa regula nu poate sa scape de neterminalul S din sirul formt de oricate ori ai aplica-o, derivand:
S => aS => aaS => aaaS samd
din pacate textul final va fi format numai din terminali.
4) Gramatica de la acest puncyt genereaza limbajul cu un singur cuvant vid, fie ca il notam cu epsilon sau cu "".
Cum: Aplic regula S->"" si obtin L={ "" } , limbajul cu un singur cuvant, si acela vid.
5) Un limbaj finit are de asemenea o gramatica evidenta de tipul al treilea. E suficient sa scriu reguli rand pe rand care produc acele texte:
L = {x,y,z,t}
S-> x
S-> y
S-> z
S -> t
unde x y z t pot fi patru texte oarecare in caest exemplu.
6) Limbajul format cu toate cuvintele cu toate literele peste algfabetul sigma, notat cu sigma si *, este un limbj chiar de tip 3.
Este suficient sa luam toate literele acelui alfabet sigma, am sale notez a,b,c,d - e mai simplu - ca la alfabetul nostru si punem regulile:
S-> aS
S->bS
S->cS
...
S->zS
apoi un S-> "" (sau il notati cu epsilon pe "").
Exercitiu: Cu aceasta gramatica generati cuvantul "hello" !
S=> hS => heS => helS => hellS => helloS => hello
Ce regula am aplicat la fiecare pas ?
Aplicatie: (pg 38 carte, pg 40 pdf) Gramatica Identificatorilor.
Scrieti ogramatica ce genereaza identificatorii formati dintr-o litera si litere sau cifre in continuare.
I -> L
I -> C
I -> IC
I -> IL
Ce inseamna aceste reguli ?
C -> 0 | ... | 9
L -> A | ... | Z | a | ... | z.
Aplicati regulile pentru a obtine identificatorul r2d2.
I => IC => ILC => ICLC => LCLC => rCLC =>r2LC =>r2dC =>r2d2
Ce reguli am aplicat :
3,4,3,1, 6,5,6,5. Verificati.
Cititi va rog dumneavoastra 1.5 pg 39.
Inafara de reprezentarile propuse, pe care va rog sa le studiati, ce reprezentare am folosit pentru a reprezenta gramatica limbajului Simple pe intelesul bison-ului ?
Pauza s-a terminat, va rog sa trecem la alt capitol:
AUTOMATE FINITE
Voi incepe o postare noua pe blog. Manualul deschis la pg 47 (pg49 pe pdf).
Va rog sa aveti iarasi manualul de Limbaje formale si teoria automatelor la indemana, deschis la pagina 37. (nr paginii tiparite).
Faptul ca exista o ierarhie a gramaticilor, ierarhia lui Chomsky, induce o ierarhie a limbajelor. De ce, manualul nu spune, dar fiecare limbaj are o gramatica cu numar maxim. Fireste, toate limbajele decidabile ar putea avea, fiecare, o gramatica generala de tip 0. Dar daca un limbaj are o gramatica de tip 3 il vom pune la categoria limbaje de tip 3.
Cititi definitia 1.12 pg 37
In unele manuale clasele limbajelor
- dependente de context
- independente de context
- regulare
se noteaza cu L indice 1, L indice 2, L indice 3, indici inferiori, iar L-ul este un L rond, rotunjit, ca R de la numere reale.
Cititi exemple si observatii pg 37 (pg 39 in pdf).
1) La o gramatica este dificil sa faci analiza ssintactica sau un parser pentru a gasi simbolul epsilon, adica sirul vid "". Cum il recunoastem in sirul de intrare ?
Ei bine, daca totusi limbajul contine si sirul vid (si sunt limbaje dde programare chiar la care puteti compila fisierul cu text vid si obtineti codul NOP;RETURN) ,
atunci vom inventa o regula ca el sa se obtina direct din simbolul de start,
S -> ε
si vom curata celelalte reguli de prezenta lui. Metoda e in paragraful 5.3 , sustine autorul cartii.
2)Se constata imediat ca limbajele regulare sunt si independente de context, vezi forma regulilor din gramatica, eda face ca regulile de la tipul 3 sa fie si reguli de la tipul 2 de gramatici. Deci L indice 3 inclus in L indice 2. Iar Limbajele monotone sunt limbaje generale deci L indice 1 inclus in L indice 0.
Dati pagina la pagina 38. (40 in pdf).
3) de ce genereaza gramaticacu regula S -> aS limbajul vid ? Fiindca singura sa regula nu poate sa scape de neterminalul S din sirul formt de oricate ori ai aplica-o, derivand:
S => aS => aaS => aaaS samd
din pacate textul final va fi format numai din terminali.
4) Gramatica de la acest puncyt genereaza limbajul cu un singur cuvant vid, fie ca il notam cu epsilon sau cu "".
Cum: Aplic regula S->"" si obtin L={ "" } , limbajul cu un singur cuvant, si acela vid.
5) Un limbaj finit are de asemenea o gramatica evidenta de tipul al treilea. E suficient sa scriu reguli rand pe rand care produc acele texte:
L = {x,y,z,t}
S-> x
S-> y
S-> z
S -> t
unde x y z t pot fi patru texte oarecare in caest exemplu.
6) Limbajul format cu toate cuvintele cu toate literele peste algfabetul sigma, notat cu sigma si *, este un limbj chiar de tip 3.
Este suficient sa luam toate literele acelui alfabet sigma, am sale notez a,b,c,d - e mai simplu - ca la alfabetul nostru si punem regulile:
S-> aS
S->bS
S->cS
...
S->zS
apoi un S-> "" (sau il notati cu epsilon pe "").
Exercitiu: Cu aceasta gramatica generati cuvantul "hello" !
S=> hS => heS => helS => hellS => helloS => hello
Ce regula am aplicat la fiecare pas ?
Aplicatie: (pg 38 carte, pg 40 pdf) Gramatica Identificatorilor.
Scrieti ogramatica ce genereaza identificatorii formati dintr-o litera si litere sau cifre in continuare.
I -> L
I -> C
I -> IC
I -> IL
Ce inseamna aceste reguli ?
C -> 0 | ... | 9
L -> A | ... | Z | a | ... | z.
Aplicati regulile pentru a obtine identificatorul r2d2.
I => IC => ILC => ICLC => LCLC => rCLC =>r2LC =>r2dC =>r2d2
Ce reguli am aplicat :
3,4,3,1, 6,5,6,5. Verificati.
Cititi va rog dumneavoastra 1.5 pg 39.
Inafara de reprezentarile propuse, pe care va rog sa le studiati, ce reprezentare am folosit pentru a reprezenta gramatica limbajului Simple pe intelesul bison-ului ?
Pauza s-a terminat, va rog sa trecem la alt capitol:
AUTOMATE FINITE
Voi incepe o postare noua pe blog. Manualul deschis la pg 47 (pg49 pe pdf).
LFA (si pentru FR) Saptamana a 7-a - Intrebari
Întrebări cu privire la cursul de LFA - Ziua seminar din saptamana a 7-a
(sunt intrebari din urma)
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.
(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 .
sâmbătă, 28 martie 2020
Alerta de securitate
Alerta de securitate: Ca urmare a atacului care a dus la oprirea retelei UPC Vodafone venit de pe domeniul .tl linkurile wetransfer originale catre wetransfer.com au fost inlocuite cu link-uri catre un site din domeniul .tl. Nu dati click pe ele.
In orice caz, daca primiti alte link-uri pretinzand ca sunt link-uri wetransfer nu faceti click pe ele.
Link-urile de download wetransfer.com trebuie sa fie in domeniul wetransfer.com
De asemenea, adresele de e-mail din mesajele wetransfer au fost modificate, uneori le lipseste ultima litera astfel incat atunci cand dai click pe ele... va imaginati ca nu mai contactati expeditorul originar.
Unii posesori de Linux rulat pe procesoare mai vechi sunt rugati sa verifice si:
cat /sys/devices/system/cpu/vulnerabilities/mds
Iar in caz de vulnerabilitate MDS CPU BUG sa adauge la linia de comanda a nucleului din
/etc/grub/grub.cfg
...optiunea ...
mds=full,nosmt
Have fun !
In orice caz, daca primiti alte link-uri pretinzand ca sunt link-uri wetransfer nu faceti click pe ele.
Link-urile de download wetransfer.com trebuie sa fie in domeniul wetransfer.com
De asemenea, adresele de e-mail din mesajele wetransfer au fost modificate, uneori le lipseste ultima litera astfel incat atunci cand dai click pe ele... va imaginati ca nu mai contactati expeditorul originar.
Unii posesori de Linux rulat pe procesoare mai vechi sunt rugati sa verifice si:
cat /sys/devices/system/cpu/vulnerabilities/mds
Iar in caz de vulnerabilitate MDS CPU BUG sa adauge la linia de comanda a nucleului din
/etc/grub/grub.cfg
...optiunea ...
mds=full,nosmt
Have fun !
LFA IFR - Compilatoare, Cap al III-lea
Buna ziua tuturor,
Sper ca ati revenit din pauza.
Intrucat din cauza caderii de retea UPC - Vodafone am intarziat, trebuie sa ne miscam mai repede.
Deschideti manualele la Cap al III-lea, la pg 25.
Capitolul acesta este foarte asemanator cu precedentul. Veti lucra intr-un folder Lab3 care contine vechiul fisier simple.y. Vom scrie un set de specificatii pentru Lex, intr-un fisier simple.lex.
Fisierul are tot trei parti, cititi la pagina 29.
Atentie: simple.tab.h este un fisier creat de bison, care cuprinde o serie de informatii privind acei tokens, atomii lexicali de recunoscut de catre Flex/Lex. Cititi-l. Si nu uitati sa il includeti in fisierul pentru Flex asa cum se vede la pg. 26.
Descrierile atomilor lexicali se numesc Expresii regulare.
Aveti doua exemple : DIGIT este o cifra de la 0 la 9 si se noteaza [0-9]. ID este un identificator si se noteaza, se descrie ca fiind ceva ce incepe cu o litera , urmeaza litere sau cifre oricate.
Notatia: [a-z] adica orice litera de la a la z. Urmat de [a-z0-9] adica orice caracter a..z 0..9 si urmat de * care inseamna oricate chestii din paranteza anterioara.
Explicatii cum se formeaza expresiile regulare gasiti la pagina 28-29. De studiat, atentie, originalul cartii are cateva greseli de tipar (autorul american recunoaste ... mai gresesc si americanii).
Intrebare de control: Expresiile regulare inseamna multimi de stringuri asa cum expresiile aritmetice inseamna numere.
[] Adevarat ?
[] False ?
Ce ati alege !
Generati sursele si realizati compilatorul cu comenzile de la pagina 30. Toate se folosesc impreuna chiar si cand modificati doar un fisier !
Ultima o puteti modifica asa:
$ gcc -o simple.exe simple.tab.o lex.yy.o -lm -lfl
daca vreti ca binarul de Linux sa poarte numele simple.exe
Acum il puteti porni:
$ ./simple.exe p1.sim
....
$ ./simple.exe p10.sim
Checkpoint: Trimiteti pe e-mail cel putin cele 10 outputuri produse de rularea compilatorului nostru pe cele 10 fisiere cu extensia .sim.
Urmariti cum analizatorul sintactic verifica sintaxa si cum programul se conformeaza sau nu regulilor gramaticale.
Nou: Mai stati on line, incarc pe WeTransfer filme de ajutor pentru capitolul al treilea. Ora 16:30 Sambata. Plus inva vreo 1/2 ora.
Sper ca ati revenit din pauza.
Intrucat din cauza caderii de retea UPC - Vodafone am intarziat, trebuie sa ne miscam mai repede.
Deschideti manualele la Cap al III-lea, la pg 25.
Capitolul acesta este foarte asemanator cu precedentul. Veti lucra intr-un folder Lab3 care contine vechiul fisier simple.y. Vom scrie un set de specificatii pentru Lex, intr-un fisier simple.lex.
Fisierul are tot trei parti, cititi la pagina 29.
Atentie: simple.tab.h este un fisier creat de bison, care cuprinde o serie de informatii privind acei tokens, atomii lexicali de recunoscut de catre Flex/Lex. Cititi-l. Si nu uitati sa il includeti in fisierul pentru Flex asa cum se vede la pg. 26.
Descrierile atomilor lexicali se numesc Expresii regulare.
Aveti doua exemple : DIGIT este o cifra de la 0 la 9 si se noteaza [0-9]. ID este un identificator si se noteaza, se descrie ca fiind ceva ce incepe cu o litera , urmeaza litere sau cifre oricate.
Notatia: [a-z] adica orice litera de la a la z. Urmat de [a-z0-9] adica orice caracter a..z 0..9 si urmat de * care inseamna oricate chestii din paranteza anterioara.
Explicatii cum se formeaza expresiile regulare gasiti la pagina 28-29. De studiat, atentie, originalul cartii are cateva greseli de tipar (autorul american recunoaste ... mai gresesc si americanii).
Intrebare de control: Expresiile regulare inseamna multimi de stringuri asa cum expresiile aritmetice inseamna numere.
[] Adevarat ?
[] False ?
Ce ati alege !
Generati sursele si realizati compilatorul cu comenzile de la pagina 30. Toate se folosesc impreuna chiar si cand modificati doar un fisier !
Ultima o puteti modifica asa:
$ gcc -o simple.exe simple.tab.o lex.yy.o -lm -lfl
daca vreti ca binarul de Linux sa poarte numele simple.exe
Acum il puteti porni:
$ ./simple.exe p1.sim
....
$ ./simple.exe p10.sim
Checkpoint: Trimiteti pe e-mail cel putin cele 10 outputuri produse de rularea compilatorului nostru pe cele 10 fisiere cu extensia .sim.
Urmariti cum analizatorul sintactic verifica sintaxa si cum programul se conformeaza sau nu regulilor gramaticale.
Nou: Mai stati on line, incarc pe WeTransfer filme de ajutor pentru capitolul al treilea. Ora 16:30 Sambata. Plus inva vreo 1/2 ora.
LFA IFR - Compilatoare, Cap al II-lea
Bun venit inapoi din pauza,
Deschideti manualul la pagina 17, la capitolul al doilea.
Pregatiti un folder Lab2 pe sistemul dvs. Linux.
In el vom scrie cod intr-un fisier: simple.y
Analizorul sintactic (Parser-ul)
Cititi definitia de la pagina 17.
Fisierul de intrare pentru Yacc/Bison are urmatoarea structura:
declaratii C si declaratii parser
%%
Regulile gramaticii si actiunile semantice atasate (care vor opera cu a doua stive)
%%
Functii C (adesea aici se include si functia Main, care nu e generat automat)
Spre deosebire de manual, am sa va rog ca in prima parte a fisierului pt. Bison sa includeti urmatoarele declaratii:
%{
#include <stdio.h> /* For I/O */
#include <stdlib.h> /* For malloc here and in symbol table */
#include <string.h> /* For strcmp in symbol table */
#define YYDEBUG 1 /* For Debugging */
int errors; /* Error Count */
%}
Cititi explicatiile de la pg 18 sus ...
Si adaugati declaratiile pentru parserul facut cu Bison:
%start program
%token LET INTEGER IN
%token SKIP IF THEN ELSE END WHILE DO READ WRITE FI
%token NUMBER
%token IDENTIFIER ASSGNOP
%left '-' '+'
%left '*' '/'
%right '^'
%%
Sunt patru feluri de chestiuni explicate aici Bisonului :
1) Ca simbolul de start al gramaticii este chiar cuvantul program. El spune care este prima regula din gramatica (si ultima folosita la analiza) cand compilatorul recunoaste un program complet, corect scris.
2) Ca exista niste cuvinte cheie pe care le vom nota LET samd ... FI pentru uzul Bisonului. Dar se vor scrie cu minuscule ! De fapt Lex le va recunoaste si putem amana pt atunci decizia daca limbajul va fi case sensitive sau nu.
3) Sunt niste atomi lexicali a caror forma nu o stim exact dar ii numim NUMBER IDENTIFIER ASSGNOP. Lex va fi informat cum sa ii recunoasca si va spune Bisonului ca a gasit unul sau altul dintre ei.
4) Operatiile aritmetice , veti vedea, nu au definita o ordine a prioritatii operatiilor, ea poate fi definita aici. La fel si asociativitatea.
Adaugati regulile gramaticale care descriu limbajul:
program : LET declarations IN commands END ;
declarations : /* empty */
| INTEGER id seq IDENTIFIER '.'
;
id seq : /* empty */
| id seq IDENTIFIER ','
;
commands : /* empty */
| commands command ';'
;
command : SKIP
| READ IDENTIFIER
| WRITE exp
| IDENTIFIER ASSGNOP exp
| IF exp THEN commands ELSE commands FI
| WHILE exp DO commands END
;
exp : NUMBER
| IDENTIFIER
| exp '<' exp
| exp '=' exp
| exp '>' exp
| exp '+' exp
| exp '-' exp
| exp '*' exp
| exp '/' exp
| exp '^' exp
| '(' exp ')'
;
%%
Intrebare de control: Cateva grupuri de reguli sau reguli dintre regulile gramaticale de mai sus sunt descrieri inductive ale unor parti ale limbajuli , le puteti identifica ?
Astept pe e-mail raspunsuri la intrebare.
Intrebare de control: O gramatica e definita teoretic(vezi cursul teoretic) din terminali, neterminali, reguli gramaticale simbol de start. Identificati aceste elemente dintre cele de mai sus.
A treia sectiune cuprinde codul de la pagina 20.
Cateva explicatii:
In C , C++ (si alte cateva limbaje) argc si argv sunt parametri pentru transferul informatiei din linia de comanda catre executabil.
Cand scriu : c:/> compilator.exe p1.sim de fapt transmit un sir de stringuri. In C, stringurile sunt pointeri la caracter si un vector de stringuri este pointer la pointer la caracter.
argc este contorul de argumente , spune cate sunt, iar argv este vectorul de stringuri.
Corectura: La instructiunea care apeleaza fopen, al doilea argument este stringul "r" !!
Intrebare de control: Ce face functia main ?
Procesati fisierul conform indicatiilor de la pagina 21:
Va trebui sa obtineti un avertisment, doar care spune ca sunt un anumit numar de conflicte deplasare reducere, semn ca nu este optimala gramatica.
Sesiunea de lucru este explicata in Anexa 2. (pe la pg 87 depinzand de editie)
Checkpoint: Trimiteti captura de ecran cu rezultatul procesarii fisierului .y cu comanda Bison.
Pauza 10 minute
Adaos ulterior. Nu trimiteti programe in alte limbaje, deocamdata.
Adaos ulterior:
Deschideti manualul la pagina 17, la capitolul al doilea.
Pregatiti un folder Lab2 pe sistemul dvs. Linux.
In el vom scrie cod intr-un fisier: simple.y
Analizorul sintactic (Parser-ul)
Cititi definitia de la pagina 17.
Fisierul de intrare pentru Yacc/Bison are urmatoarea structura:
declaratii C si declaratii parser
%%
Regulile gramaticii si actiunile semantice atasate (care vor opera cu a doua stive)
%%
Functii C (adesea aici se include si functia Main, care nu e generat automat)
Spre deosebire de manual, am sa va rog ca in prima parte a fisierului pt. Bison sa includeti urmatoarele declaratii:
%{
#include <stdio.h> /* For I/O */
#include <stdlib.h> /* For malloc here and in symbol table */
#include <string.h> /* For strcmp in symbol table */
#define YYDEBUG 1 /* For Debugging */
int errors; /* Error Count */
%}
Cititi explicatiile de la pg 18 sus ...
Si adaugati declaratiile pentru parserul facut cu Bison:
%start program
%token LET INTEGER IN
%token SKIP IF THEN ELSE END WHILE DO READ WRITE FI
%token NUMBER
%token IDENTIFIER ASSGNOP
%left '-' '+'
%left '*' '/'
%right '^'
%%
Sunt patru feluri de chestiuni explicate aici Bisonului :
1) Ca simbolul de start al gramaticii este chiar cuvantul program. El spune care este prima regula din gramatica (si ultima folosita la analiza) cand compilatorul recunoaste un program complet, corect scris.
2) Ca exista niste cuvinte cheie pe care le vom nota LET samd ... FI pentru uzul Bisonului. Dar se vor scrie cu minuscule ! De fapt Lex le va recunoaste si putem amana pt atunci decizia daca limbajul va fi case sensitive sau nu.
3) Sunt niste atomi lexicali a caror forma nu o stim exact dar ii numim NUMBER IDENTIFIER ASSGNOP. Lex va fi informat cum sa ii recunoasca si va spune Bisonului ca a gasit unul sau altul dintre ei.
4) Operatiile aritmetice , veti vedea, nu au definita o ordine a prioritatii operatiilor, ea poate fi definita aici. La fel si asociativitatea.
Adaugati regulile gramaticale care descriu limbajul:
program : LET declarations IN commands END ;
declarations : /* empty */
| INTEGER id seq IDENTIFIER '.'
;
id seq : /* empty */
| id seq IDENTIFIER ','
;
commands : /* empty */
| commands command ';'
;
command : SKIP
| READ IDENTIFIER
| WRITE exp
| IDENTIFIER ASSGNOP exp
| IF exp THEN commands ELSE commands FI
| WHILE exp DO commands END
;
exp : NUMBER
| IDENTIFIER
| exp '<' exp
| exp '=' exp
| exp '>' exp
| exp '+' exp
| exp '-' exp
| exp '*' exp
| exp '/' exp
| exp '^' exp
| '(' exp ')'
;
%%
Intrebare de control: Cateva grupuri de reguli sau reguli dintre regulile gramaticale de mai sus sunt descrieri inductive ale unor parti ale limbajuli , le puteti identifica ?
Astept pe e-mail raspunsuri la intrebare.
Intrebare de control: O gramatica e definita teoretic(vezi cursul teoretic) din terminali, neterminali, reguli gramaticale simbol de start. Identificati aceste elemente dintre cele de mai sus.
A treia sectiune cuprinde codul de la pagina 20.
Cateva explicatii:
In C , C++ (si alte cateva limbaje) argc si argv sunt parametri pentru transferul informatiei din linia de comanda catre executabil.
Cand scriu : c:/> compilator.exe p1.sim de fapt transmit un sir de stringuri. In C, stringurile sunt pointeri la caracter si un vector de stringuri este pointer la pointer la caracter.
argc este contorul de argumente , spune cate sunt, iar argv este vectorul de stringuri.
Corectura: La instructiunea care apeleaza fopen, al doilea argument este stringul "r" !!
Intrebare de control: Ce face functia main ?
Procesati fisierul conform indicatiilor de la pagina 21:
Va trebui sa obtineti un avertisment, doar care spune ca sunt un anumit numar de conflicte deplasare reducere, semn ca nu este optimala gramatica.
Sesiunea de lucru este explicata in Anexa 2. (pe la pg 87 depinzand de editie)
Checkpoint: Trimiteti captura de ecran cu rezultatul procesarii fisierului .y cu comanda Bison.
Pauza 10 minute
Adaos ulterior. Nu trimiteti programe in alte limbaje, deocamdata.
Limbajul Simple nu are:
a) Atribuiri cu = ci cu :=.
b) Tipul boolean cu true si false. folositi 0 si 1.
c) Operatorul %.
d) secventa de comenzi nu se scrie in acolada. Vezi anexa A.7.
e) Operatorul && va trebui sa va descurcati cu aritmetica. Not se implementeaza asa: x, not x este 1-x.
f) # comentarii
g) Instructiunea display , se numeste write.
Adaos ulterior:
Limbajul Simple nu are:
a) Liste.
b) Atribuiri cu = ci cu :=
c) Operator %
d) Operator de indexare.
e) Secvente cu acolade.
Vezi exemplu de program in A.7
LFA IFR - Compilatoare - Capitolul I [pg 8+]
Salutare tuturor de la IFR
Cititi aceste note cu manualul de compilatoare la indemana. Deschideti-l la pagina 8.
Ca de obicei blog-ul va contine comentarii la manual si alte explicatii, dar nu tine loc de curs COMPLET !
In esenta, un compilator este un translator pentru o multime potential infinita de programe, scrise intr-un limbaj, pentru a obtine un cod obiect. Definitia completa o gasiti la pagina 8.
De ce este nevoie de un instrument atat de sofisticat: Deoarece trebuie sa ai posibilitatea de a procesa un numar infinit de programe, toate scrise in acelasi limbaj, dar limbajul trebuie descris printr-un set FINIT de reguli. Altfel nu poti face un compilator finit.
Modul ales de a stapani infinitatea de programe posibile este cu ajutorul inductiei.
Dar sunt mai multe feluri de inductii:
Inductia cu o baza si o regula:
Baza: P(0) - adevarat
Pasul inductiv: P(n)-> P(n+1)
Este instrument pentru a demonsta doar pe axa numerelor naturale ca e adevarata o propozitie.
Inductia cu doua baze si un pas inductiv:
Baza 1: P(0) - adevarat
Baza 2: P(1) - adevarat
Pasul inductiv : P(n)-> P(n+2)
Inductia cu o baza si doua reguli:
Pe cadranul din planul N+ x N+ al numerelor de doua coordonate intregi pozitive, ca varfurile
unor patratele de pe un caiet cu patratele (imaginati-va coordonatele lor) putem avea:
Baza 1: P(0,0) - adevarat
Pasul inductiv : P(x,y)-> P(x+1,y)
Pasul inductiv : P(x,y)-> P(x,y+1)
Exercitiu: Desenati pe o foaie de caiet cu patratele, prin sageti, cum se propaga proprietatea pe plan.
Trimiteti scanarea paginii pe e-mail la profesor.
Exercitiu de gandire: Cum este legat un limbaj de programare structurata de ideea de inductie matematica cu mai multe baze si cu mai multe reguli ?
Exercitiu: La pagina 9 din manual gasiti un exercitiu de traducere, rezolvat. Scrieti functia recursiva T(x) care spune cum se traduce sirul de numere ale lui Peano in descrierea sumei de unitati sub forma de text...
Cititi de la pg 10 ..
Fazele unei compilari:
Analiza lexicala : Cu scopul recunoasteri si clasificarii atomilor lexicali, fie ei cuvinte cheie, numere, identificatori, operatori din doua litere, semne de comparatie si alte semne de punctuatie si de elemente ale sintaxei. Acestea vor fi un fel de "litere chinezesti" - adica litere cu semnificatie de cuvant, care vor intra, intr-o anumita ordine si intercalate cu neterminali, in alcatuirea sintaxei:
De exemplu if x>=0 then write x fi se desparte in urmatorii atomi lexicali:
if
x
>=
0
then
write
x
fi
Analiza sintactica: Recunoaste structurile sintactice generice prezente in text in forme concrete si creaza ca efect suplimentar arborele sintactic (sau direct arborele operatorial) sau ramuri din el (cand il parcurge). Da acel mesaj "syntax error".
Verifica sintaxa conform regulilor gramaticale ale acesteia
Analiza semantica: face diverse verificari semantice, in esenta prin verificarea daca elemente folosite in text, variabile , functii etc sunt folosite asa cum au fost declarate. Pentru aceasta tine si un dictionar de declaratii, un dictionar de denumiri numit tabela de simboluri. E normal sa faca aceasta deoarece pe de o parte compilatorul nu stie ce denumiri de variabile a inventat autorul programului si nici daca sunt folosite corect.
Mai multe, in carte la pg 11-12. Cititi pg 11-12.
Optimizatorul arborelui: daca exista, optimizeaza arborele sintactic sau arborele operatorial.
Generatorul de cod: Ghiciti ce face ?
Optimizatorul de cod: Codul generat din bucatele poate crea portiuni de cod absurde la limita imbinarii bucatilor, de exemplu poate alatura un ultim PUSH AF dintr-o secventa de cod cu un POP AF sau un POP BC din inceputul altei secvente.
E clar ca
PUSH AF
POP AF
e totuna cu un
NOP
sau cu nici o instructiune, si codul se scurteaza.
Iar
PUSH AF
POP BC
ar putea fi inlocuit cu o incarcare directa
LD BC, AF (daca limbajul de Asamblare permite) sau cu doua partiale
LD B,A
LD C,F
sa zicem.
Definitia interpretorului este la pg 12-13.
La pagina 13 gasiti limbajul Simple.
Este momentul sa scriem programe in Simple, aceste programe le veti folosi la testarea compilatorului.
Sorin va da raspunsul pe e-mail.
Salvati fisierul rezultat in folderul Lab1 cu numele p1.sim.
Salvati fisierul rezultat in folderul Lab1 cu numele p2.sim.
Cititi aceste note cu manualul de compilatoare la indemana. Deschideti-l la pagina 8.
Ca de obicei blog-ul va contine comentarii la manual si alte explicatii, dar nu tine loc de curs COMPLET !
In esenta, un compilator este un translator pentru o multime potential infinita de programe, scrise intr-un limbaj, pentru a obtine un cod obiect. Definitia completa o gasiti la pagina 8.
De ce este nevoie de un instrument atat de sofisticat: Deoarece trebuie sa ai posibilitatea de a procesa un numar infinit de programe, toate scrise in acelasi limbaj, dar limbajul trebuie descris printr-un set FINIT de reguli. Altfel nu poti face un compilator finit.
Modul ales de a stapani infinitatea de programe posibile este cu ajutorul inductiei.
Dar sunt mai multe feluri de inductii:
Inductia cu o baza si o regula:
Baza: P(0) - adevarat
Pasul inductiv: P(n)-> P(n+1)
Este instrument pentru a demonsta doar pe axa numerelor naturale ca e adevarata o propozitie.
Inductia cu doua baze si un pas inductiv:
Baza 1: P(0) - adevarat
Baza 2: P(1) - adevarat
Pasul inductiv : P(n)-> P(n+2)
Inductia cu o baza si doua reguli:
Pe cadranul din planul N+ x N+ al numerelor de doua coordonate intregi pozitive, ca varfurile
unor patratele de pe un caiet cu patratele (imaginati-va coordonatele lor) putem avea:
Baza 1: P(0,0) - adevarat
Pasul inductiv : P(x,y)-> P(x+1,y)
Pasul inductiv : P(x,y)-> P(x,y+1)
Exercitiu: Desenati pe o foaie de caiet cu patratele, prin sageti, cum se propaga proprietatea pe plan.
Trimiteti scanarea paginii pe e-mail la profesor.
Exercitiu de gandire: Cum este legat un limbaj de programare structurata de ideea de inductie matematica cu mai multe baze si cu mai multe reguli ?
Exercitiu: La pagina 9 din manual gasiti un exercitiu de traducere, rezolvat. Scrieti functia recursiva T(x) care spune cum se traduce sirul de numere ale lui Peano in descrierea sumei de unitati sub forma de text...
Cititi de la pg 10 ..
Fazele unei compilari:
Analiza lexicala : Cu scopul recunoasteri si clasificarii atomilor lexicali, fie ei cuvinte cheie, numere, identificatori, operatori din doua litere, semne de comparatie si alte semne de punctuatie si de elemente ale sintaxei. Acestea vor fi un fel de "litere chinezesti" - adica litere cu semnificatie de cuvant, care vor intra, intr-o anumita ordine si intercalate cu neterminali, in alcatuirea sintaxei:
De exemplu if x>=0 then write x fi se desparte in urmatorii atomi lexicali:
if
x
>=
0
then
write
x
fi
Analiza sintactica: Recunoaste structurile sintactice generice prezente in text in forme concrete si creaza ca efect suplimentar arborele sintactic (sau direct arborele operatorial) sau ramuri din el (cand il parcurge). Da acel mesaj "syntax error".
Verifica sintaxa conform regulilor gramaticale ale acesteia
Analiza semantica: face diverse verificari semantice, in esenta prin verificarea daca elemente folosite in text, variabile , functii etc sunt folosite asa cum au fost declarate. Pentru aceasta tine si un dictionar de declaratii, un dictionar de denumiri numit tabela de simboluri. E normal sa faca aceasta deoarece pe de o parte compilatorul nu stie ce denumiri de variabile a inventat autorul programului si nici daca sunt folosite corect.
Mai multe, in carte la pg 11-12. Cititi pg 11-12.
Optimizatorul arborelui: daca exista, optimizeaza arborele sintactic sau arborele operatorial.
Generatorul de cod: Ghiciti ce face ?
Optimizatorul de cod: Codul generat din bucatele poate crea portiuni de cod absurde la limita imbinarii bucatilor, de exemplu poate alatura un ultim PUSH AF dintr-o secventa de cod cu un POP AF sau un POP BC din inceputul altei secvente.
E clar ca
PUSH AF
POP AF
e totuna cu un
NOP
sau cu nici o instructiune, si codul se scurteaza.
Iar
PUSH AF
POP BC
ar putea fi inlocuit cu o incarcare directa
LD BC, AF (daca limbajul de Asamblare permite) sau cu doua partiale
LD B,A
LD C,F
sa zicem.
Definitia interpretorului este la pg 12-13.
La pagina 13 gasiti limbajul Simple.
Este momentul sa scriem programe in Simple, aceste programe le veti folosi la testarea compilatorului.
Intrebare individuala pentru Sorin.P Care este cel mai simplu program Simple, conform regulii gramaticale care contine cuvantul program ? Inspiratie: Anexa 7.
Sorin va da raspunsul pe e-mail.
Salvati fisierul rezultat in folderul Lab1 cu numele p1.sim.
Intrebare individuala pentru O Alex: Cum arata conform paginii 13 un program Simple care are structura celui mai simplu program si o declaratie a unei variabile intregi pe nume X ?
Pg 13 si Anexa 7 !
Alex va da raspunsul pe e-mail.Salvati fisierul rezultat in folderul Lab1 cu numele p2.sim.
Intrebare individuala pt Cristiana:
O secventa de identificatori este scrisa conform acelei a treia reguli gramaticale, dar poate fi vida sau poate fi o alta secventa la care mai adaugam un identificator si o virgula.
Ca efect obtinem declaratii mai lungi .
Scrieti programul Simple care contine :Structura generala a unui program si
doua declaratii de variabile.
Salvati in dosarul Lab1 cu numele p3.sim
Intrebare individuala pentru Marius P.
Conform regulii 4 de la pagina 13 secventa de comenzi in limbajul Simple e formata dintr-o secventa de comenzi mai scurta care poate fi si vida si o alta comanda. Cum o comanda poate fi skip; cf. regulii a 5 -a adaugati la programul anterior, si doua comenzi skip.
Salvati programul in format .sim. Sub numele p4.sim
Raspundeti dupa pauza de la ora 13.
Intrebare individuala pt Alexandru A.
Intrebare individuala pt Alexandru A.
Conform ultimii reguli de la pagina 13 (regula cont. pe pg 14) o instructiune poate fi o atribuire formata din identificator := si o expresie.
Scrieti programul cu doua declaratii de variabile si doua atribuiri simple, de ex la dati val 10 si 20.
Scrieti programul cu doua declaratii de variabile si doua atribuiri complexe: Formulele vor avea toate operatiile aritmetice.
Salvati programele in folderul dvs Lab1 sub numele p4b.sim si p5.sim.
Intrebare individuala pt Alexandra S.
Limbajul Simple are o instructiune While (pg 14 sus). Scrieti un program care calculeaza suma numerelor dintr-un sir de numere terminat cu zero. O intrebare clasica de clasa incepatoare.
Salvati programul in folderul Lab1 cu numele P6.sim
Intrebare individuala pt. Daniel O
Limbajul Simple are un If si un While conform regulilotr de la pagina 14.
Scrieti in Simple micul program care face calculul sumei numerelor impare dintr-un sir terminat cu zero.
Intrebare suplimentara: Cum scrieti, intr-un limbaj care face calcule cu numere intregi, conditia ca un numar sa fie impar folosind doar cele patru operatii aritmetice ?
Salvati programul sub numele p7.sim in folderul Lab1.
Intrebare pentru B.Catalin
Scrieti programul Simple care primind un numar, afiseaza divizorii acestuia
de la 1 la numarul insusi.
Salvati programul sub numele p7b.sim
Intrebare pt I. Marius Dorin
Scrieti programul simple care calculeaza divizorul comun a doua numere prin scaderi repetate, unul din altul si invers.
Daca am obtinut 0, predentul scazator (sau descazutul) este divizorul comun.
Salvati programul sub numele p10.sim
Exercitii in continuare: Scrieti inca zece programe Simple cu grade diferite de complexitate sisalvati-le in folderul Lab1.
Veti avea nevoie de aceste programe pentru testarea compilatorului final. Fara ele si fara compilator nu participati la examen.
Pauza 20 minute. Intre timp voi incerca sa incarc video-urile ajutatoare pentru capitolul al doilea.
Nota : Participarea la laborator este obligatorie conform contractului incheiat, va rog sa recititi contractul.
Abonați-vă la:
Postări (Atom)