Clasa VII/VIII lecția 28 - 20 mai 2014
Lecţie
Înainte de a vorbi despre temă, vom discuta un subiect care a fost mascota ONI 2014: parsing. Acest subiect a mai fost discutat în lecţia 8. Îl vom relua din cînd în cînd pentru cimentarea cunoştinţelor.
Destul de multe din problemele date la ONI 2014 fac parte dintr-o categorie numită parsing sau analiză sintactică din domeniul mai larg al compilatoarelor. Teoria din spatele analizei sintactice se studiază în facultate, dar bazele ei pot fi ințelese odată ce stăpîniți recursivitatea.
Pentru a implementa orice problemă de parsing avem nevoie să știm două lucruri: gramatici și implementarea analizorului recursiv cu proceduri pe baza acestor gramatici. Să le luăm pe rînd.
Gramatica expresiilor
Fără a intra în detalii deoarece depășește nivelul acestui cerc, putem descrie o expresie astfel:
Expr -> Term (('+'|'-')Term)*
Term -> Fact (('*'|'/')Fact)*
Fact -> Int | '('Expr')'
Int -> ('0'|'1'|'2'|...|'9')+
Unde parantezele pătrate semnifică o bucată opțională, steluța semnifică repetiție de oricîte ori, inclusiv zero, plus semnifică repetiţie de cel puţin o dată, iar bara verticală reprezintă operatorul sau (opțiune între mai multe opțiuni).
Ce semnifică această gramatică? Ea descrie toate expresiile corecte care conţin numai adunări, scăderi, înmulţiri, împărţiri şi paranteze. Cum descrie ea aşa ceva? Ea arată o succesiune de înlocuiri posibile. Astfel Expr se poate înlocui cu Term care la rîndul lui se poate înlocui cu Fact care se poate înlocui cu Int şi în final cu 2. Astfel știm că 2 este o expresie corectă. Să luăm un caz mai complicat, să generăm de exemplu expresia 2+3*4:
Expr -> Term + Term -> Fact + Term -> Int + Term -> 2 + Term -> 2 + Fact * Fact -> -> 2 + Int * Fact -> 2 + Int * Int -> 2 + 3 * Int -> 2 + 3 * 4
Analizorul recursiv cu proceduri
Bazat pe gramatica precedentă putem implementa un analizor recursiv. Fiecare simbol neterminal (care se mai poate expanda, cele care încep cu litere mari) se înlocuiește cu o funcție C care "înghite" de la intrare o expresie. Ea verifică în același timp corectitudinea și se oprește la caracterul incorect, dacă găsește o greșeală. Să luăm un exemplu: funcția expr().
Această funcție va chema mai întîi funcția term() care va înghiți la intrare un termen. Apoi va testa primul caracter la intrare. Dacă este plus sau minus înseamnă ca avem de "înghițit" în continuare un termen. Pe tot parcursul, dacă găsim o nepotrivire (nu e semnul corect, sau funcția term() returnează eroare) ne oprim returnînd eroare.
Ar mai fi de menționat că, deoarece vom avea mereu de luat decizii ce "înghițim" mai departe bazat pe primul caracter de la intrare, îl vom ține separat într-o variabilă numită first. Astfel, șirul de la intrare este reprezentat de primul caracter ținut în first și de fișierul de la intrare, ce urmează logic în secvență. De fiecare dată cînd citim un caracter din fișier îl trecem mai întîi în variabila first. Astfel putem "trage cu ochiul" la primul caracter din fișier fără a avea probleme cu faptul că l-am citit deja și că o altă funcție vrea să îl recitească. Toate funcțiile știu că primul caracter este în first.
Urmează discuţii atît despre problemele de la temă, cît şi despre problemele pe care le aveţi la tema următoare.
Întrebări despre jocul Flood Wars, eventuale discuţii despre unde a ajuns fiecare cu codarea.
Tema - rezolvări
Rezolvări aici [1]
Temă
Rezolvări aici [2]
