Haideti sa citim impreuna si sa notam cateva comentarii la aceste pagini:
pg 33(pagina 35 din pdf) :
Paragraf 1.2 Exemple de gramatici si limbaje generate de gramatici.
Iata ce ar fi de spus:
1. Observati mica gramatica de aici. S->AB deci cuvintele au o parte derivata din A si una derivata din B. A->a sau A-> b, deci prima parte nu poate fi decat "a" sau "b". Din regulile B -> c si B-> d deducem ca partea a doua poate sa fie ori "c" ori "d". Ca urmare sunt doar patru cuvinte posibile L(G) = {ac,ad, bc, bd}.
2. Aceasta este celebra gramatica a expresiilor aritmetice, dar reduse la cele care folosesc plus si inmultit nu minus, nu impartit: Observati ca din E->E+T (citeste Expresia poate fi O alta Expresie - mai scurta - urmata de plus si de un alt Term) impreuna cu E->T permit sa demonstarm ca E -> T + ... +T (sau doar un T). Deci expresia este o suma de termi.
La fel termul este un produs de oricati factori.
Aici factorul F-> a deci este un "a" ("a" este un fel de NUMBER, de numar)
sau factorul este F->(E) deci poate fi o expresie in paranteza. Sa fie o functie este exclus.
Exercitii: Derivati expresii din ce in ce mai complicate, in aceasta gramatica. Cum le alegeti ca sa va faceti exercitiile: le scrieti ca niste expresii aritmetice cu a in loc de numere, semnele + si * si paranteze.
Dati pagina la pagina 36.
Derivarea este acolo, scrisa pas cu pas.
Teorema 1.1. Este de fapt un exemplu de exercitia de matematica, de algebra a limbajelor formale. Exercitiul cere sa demonstaram ca L(G) = { .... } vezi manualul. Demonstartia se face prin dubla incluziune.
Puteti face in generat astfel de demonstratii ?
Definitia 1.10. Spunem despre un limbaj ca este decidabil daca putem preciza (eu as spune decide algoritmic ) daca un cuvant w apartine sau nu limbajului L.
Nota: Este exact ce are de facut in prima faza un compilator, sa spuna daca textul programului este corect sintactic sau nu.
Observatia 1: BNF -ul este pina la urma o notatie similara cu aceea a regulilor gramaticale. Incercati sa intelegeti o regula gramaticala, cumva, independent de notatii: Ca scriem S -> aBc sau ca scriem <S> :: a <B> c este in esenta acelasi lucru, o regula care spune ca un S se scrie incepand cu a si urmat de o scriere posibila a lui B si urmeaza un c.
pg 35 jos:
<cifra > ::= 0 | 1| 2| 3|4|5|6|7|8|9
ne spune ce poate fi o cifra.
Dati pagina ... trecem la pagina 36 din carte (38 din pdf).
Gasim o definitie similara pentru <litera> si apoi din ele facem o definitie pentru <identificator>.
Va imaginati cum ar fi ? Un identificator este ceva care incepe cu o litera, iar daca e mai lung continua cu o litera sau o cifra !
Cum se scrie regula gramaticala ?
Raspunsul: la pg 36 (pg 38 din pdf).
Acum inca o intrebare ? Cum ati scrie aceste reguli gramaticale folosind Majuscule pentru Neterminali, minuscule pentru terminali si -> pt a separa stanga de dreapta regulii (in loc de ::= din BNF ?).
Observatia 2). As comenta: Descrierea unui limbaj trebuie sa fie finita dar multimea programelor posibile ar fi bine sa fie cat mai mare, de preferat infinita. Acest fel de infinit (numarabil, ca numerele naturale) se poate stapani cu o tehnica pe care o cunoasteti de la algebra: inductia. Din acest motiv, un limbaj de programare are sintaxa definita ca o definitie prin inductie a instructiunilor combinata cu o definitie prin inductie a expresiilor (pot fi mai multe feluri de expresii). Se pot defini asa si declaratiile.
Exercitiu: Extrageti din lectia despre sintaxa limbajului Simple, grupurile de reguli gramaticale care definesc prin inductie:
1) sirul id_seq de identificatori.
2) secventa de comenzi, notata commands.
1.4 Clasificarea gramaticilor, Ierarhia lui Chomsky
Ei, aici este un mare mister. Lucrarile de algebra a limbajelor afirma doar: iata cat de importante sunt, ati vazut, gramaticile pentru definirea limbajelor. Afirmam ca forma regulilor joaca un rol esential in considerentele legate de gramatici !?! Hm. Si apoi urmeaza calsificarea gramaticilor.
Ei bine, problema practica este alta. In practica viteza analizatorului sintactic este aceea care conteaza (atat de mult incat s-a ajuns sa se studieze clase particulare de gramatici). Clasificarea numita Ierarhia lui Chomsky este de fapt o ierarhie a vitezei analizatoarelor sintactice care se pot face pe baza diferitelor feluri de gramatici.
De exemplu, as putea determina prin backtracking ce reguli gramaticale s-au aplicat pentru a obtine textul. Dr ar rezulta un analizator sintactic cu timp de calcul exonential , brr. Ce ma fac daca ii dau sa analizeze codul unei aplicatii de sa zicem 500 000 de linii. (Un Office Modern ar putea avea asa un cod, de exemplu. Sau un nucleu de SO cu o anume colectie de drivere.) ce ma fac cu 10 la puterea 80 x 500 000 de pasi de analiza ? Imbatranesc linga compilator ?
Este clar ca aceste gramatici la care analiza sintactica s-ar face doar prin backtracking nu sunt tocmai cele mai bune.
Iar de gramaticile generale ce sa mai zic ? Circula o gluma pe seama lor. Sa presupunem ca am descrie modul de transformare a formulelor matematice cu o gramatica (deendenta de context sau generala) apoi as vrea sa demonstrez o teorema cautand o derivare pentru concluzia ei in acea gramatica. Ce-ar fi, ar fi jale mare, am avea un analizor sintactic care ar tine locul matematicienilor si matematica ar disparea. Totusi acest lucru nu se intampla. Semn ca nu toate gramaticile au algoritmi de ananliza sintactica sau nu toate au algoritmi de analiza sintactica cu timp rezonabil de calcul.
La capatul celalalt al spectrului sunt niste gramatici echivalente cu automatele din capitolul urmator (demonstratia va urma). Aceste automate sunt niste dispozitive care citesc un caracter, trec in alta starea (au mai multe stari) si asa mai departe pina ajung sa consume tot textul. Starea in care ajung ne spune daca textul e corect scris sau nu.
Asemenea gramatici sau asemenea automate au incredibila calitate ca functioneaza cu viteza maxima, dupa n pasi de analiza, un text de lungime n (masurat in atomi lexicali) este gata analizat. O(n) - se citeste - "ordinul lui n".
Mai repede de atat nu se poate. Trebuie sa citesc macar o data fiecare litera sau atom lexical.
Dar aceste gramatici sau automate au niste limite, ele nu ar putea valida, de exemplu, expresii cu oricate paranteze. (Ca sa poti valida expresii cu oricate paranteze ai nevoie de o memorie ca o stiva ca sa tii minte care paranteze au fost deschise si care inchise... ceea ce automatele nu au.)
Asa ca in practica autmatele, gramaticile de tip 3 si expresiile regulare (vezi cap 3 din cartea despre compilatoare) se folosesc doar la recunoasterea unor fragmente de program: acei atomi lexicali de care am vorbit in lectia din cap 3 din cartea despre compilatoare).
Si mai exista o categorie de gramatici, undeva la mijloc: timp polinomial de analiza (s-a demonstrat ca permit) si reguli fara context , in stanga regulii e doar un simbol neterminal. Acestea sunt de fapt gramaticile limbajelor de programare (exceptie e Fortran-ul, creat inaintea acestei teoretizari).
Intr-adevar, forma regulilor conteaza, dar conteaza prin viteza pe care o vor avea analizoarele/analizatoarele sintactice.
Acum puteti citi mai departe de definitia 1.1. de la pagina 36 (pg 38 din pdf).
0. Numim gramatici de tip 0 gramaticile care nu au nici o restrictie referitoare la forma regulilor. Notam: Nu li se impune sa aiba doar un neterminal in partea stanga, nici ca regulile sa fie monotone, crescand numarul de simboluri prin derivare. Toate gramaticile intra in aceasta multime.
1. Numim gramatici de tip 1, gramaticile pentru care orice productie (diferita de productia care duce pe S, simbolul de start, in epsilon - cuvantul vid) are o inegalitate intre lungimile partilor regulii: partea stanga e mai scurta strict decat cea dreapta. ( Se adauga aici: "Daca productia S trece in epsilo apartine gramaticii, atunci S nu apare in membrul drept al unei alte productii." Nota: chestia aceasta este scrisa deoarece orice gramatica poate fi adusa la o astfel de forma in care epsilon, cuvantul vid, sa apara doar in regula "S trece in epsilon"). Demonsratia ultimei afirmatii se gaseste intr-un capitol ulterior, la eliminarea simbolului epsilon. (un test de rabdare: cautati demonstratia in carte, acum si inainte de sesiune !!)
Nota: Daca regulile sunt monotone si nu stim ce reguli de derivare se aplica putem pleca de la S si sa le incercm pe toate cele posibile la fiecare pas. E un backtracking. Cum ne oprim: deoarce regulile noastre lungesc secventa (de terminali si neterminali) obtinuta, ne oprim cand depasim lungimea textului/programului de ananlizat. dar timpul va fi EXPONENTIAL ! :((
2. Gramaticile de tip doi sunt gramaticile in care regulile au exact un neterminal in partea stanga si o secvent de terminali si neterminali in partea dreapta. Se numesc "independente de context" deoarece orice din limbaj: variabila , expresie etc se poate scrie dupa aceleasi reguli in indiferent ce context apare.
Punct de control: Cum e legat acest lucru de forma regulii ?? Puteti observa !
Acestea, de tip doi, sunt gramaticile cu viteza adecvata nevoilor practice.
3. Gramaticile de tip trei sunt gramaticile in care orice productie (diferita de aceea care il duce pe S in cuvantul vid epsilon) are una din urmatoarele DOUA forme:
Un neterminal devine o secventa de 2 atomi, primul terminal al doilea neterminal. Ex: A-> aB . Sau , a doua forma:
A -> b adica un neterminal trece intr-un terminal. (Iar derivarea va inceta aici).
Acum puteti citi definitia 1.12 (tipuri de limbaje).
Vom continua cu exemplele si observatiile de la pagina 37. (pg 39 in pdf).
Nota:
...
Continuam dupa pauza ...
Niciun comentariu:
Trimiteți un comentariu