Clasa VII/VIII lecția 13 - 16 dec 2014: Difference between revisions

From Algopedia
Jump to navigationJump to search
No edit summary
 
(No difference)

Latest revision as of 14:31, 3 May 2022

Tema - rezolvări

Rezolvări aici [1]

Lecţie

Introducere în analiza sintactică

În această lecţie vom discuta un subiect care a fost mascota ONIgim 2014: analiza sintactică, denumită şi parsing. Ea face parte din domeniul mai larg al teoriei compilatoarelor. Teoria din spatele analizei sintactice se studiază în facultate, dar bazele ei pot fi ințelese odată ce stăpîniți recursivitatea.

Dacă se studiază abia în facultate, de întîlnim subiecte de gimnaziu care necesită parsing? Răspunsul este unul foarte interesant, în opinia mea. Este vorba de un fenomen întîlnit şi la olimpiadele de matematică şi de fizică. Unele subiecte de olimpiadă sînt fabricate în modul următor: creatorul problemei preia o problemă existentă de la clase mai mari, care foloseşte cunoştinţe de nivel superior. Apoi o modifică uşor şi, cunoscînd metoda avansată de rezolvare, găseşte o metodă "băbească" de rezolvare cu cunoştinţe de nivel mic. Apoi declară problema de clasa a 7a. Creatorului problemei îi este uşor să "găsească" acea demonstraţie, deoarece el sau ea este ghidat de soluţia de nivel superior, care este, de obicei, banală. Dar vouă, celor mici, nu vă este deloc uşor, căci problema este în fapt aproape imposibilă fără cunoştinţe avansate. De aceea consider că aceste probleme nu sînt corecte. Viaţa nu este întotdeauna corectă, se pare că nici măcar la vîrsta voastră.

Mai departe: de ce se întîmplă acest lucru? Dacă aceste probleme sînt de fapt banale odată ce ai cunoştinţe de nivel superior şi aproape imposibile dacă nu ai acele cunoştinţe, de ce creatorii de probleme simt nevoia să creeze astfel de probleme? Răspunsul, cred, constă în faptul că este greu să creezi probleme frumoase, bune, grele şi inedite folosind doar cunoştinţe de nivelul dorit. Este mult mai uşor să iei ceva clasic, pe care copilul nu îl ştie, şi să i-l pui în faţă.

Concluzia? Olimpicii de vîrf sînt siliţi să înveţe teorie în avans, iar eu sînt silit să o predau. Şi iată-mă predînd această lecţie :-)

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.

Gramatici

Aşa cum gramatica limbii române descrie structura, organizarea limbii, o gramatică din teoria compilatoarelor descrie structura unui limbaj. Acel limbaj poate fi limbajul C, sau Pascal, dar poate fi şi mult mai simplu, ca limbajul parantezelor corect închise, sau limbajul tuturor expresiilor aritmetice. Analogia funcţionează mai departe: gramatica limbii române identifică părţile de propoziţie: subiect, predicat, atribut, complement. În informatică propoziţia este un şir din limbaj, de exemplu o expresie corectă, iar gramatica identifică structuri în acea expresie, cum ar fi operatori, operanzi, paranteze.

O gramatică constă din producţii de forma:

S ⇾ aAb

cu semnificaţia că S poate fi înlocuit cu grupul aAb.

Să luăm un exemplu:

Exemplul 1

Să considerăm limbajul:

Lab = { ab, aabb, aaabbb, aaaabbbb, ... }

respectiv limbajul tuturor şirurilor care au litere a la început şi litere b la final, în număr egal. O gramatică care descrie acest limbaj este:

S ⇾ aSb
S ⇾ λ

cu semnificaţia că λ este şirul vid. Cum putem produce un şir din limbaj folosind această gramatică? Prin înlocuiri succesive ale lui S cu una din părţile din dreapta ale producţiilor pînă ce obţinem şirul dorit. Să presupunem că vrem să generăm şirul aabb. Vom porni cu S şi vom înlocui succesiv astfel:

S ⇾ aSb ⇾ aaSbb ⇾ aabb

Literele mari din gramatică se numesc simboli neterminali, deoarece ele nu fac parte din şirurile generate. Înlocuirile se fac pînă ce şirul nu mai conţine nici un simbol neterminal. Să luăm un exemplu similar:

Exemplul 2

Fie limbajul şirurilor care conţin întîi litere a, apoi litere b în număr egal cu a, apoi litere c, apoi litere d în număr egal cu c:

Labcd = { ab, cd, abcd, aabb, aabbcd, abccdd, aaabbb, cccddd, ... }

O gramatică posibilă este:

S ⇾ XY
X ⇾ aXb | λ
Y ⇾ cYd | λ

Am introdus aici o prescurtare în notaţie: dacă X are două producţii, le vom grupa separînd părţile din dreapta cu bare verticale. Să exemplificăm producţia lui abccdd:

S ⇾ XY ⇾ aXbY ⇾ abY ⇾ abcYd ⇾ abccYdd ⇾ abccdd

Deoarece avem mai multe simboluri neterminale trebuie să specificăm cu ce simbol pornim în înlocuiri: simbolul S va fi denumit simbol de start.

Analizorul recursiv cu proceduri

Ne propunem, în primă fază, să răspundem la întrebarea "este şirul nostru corect?". Cu alte cuvinte, şirul de la intrare face parte din limbaj? Sau, mai concret, este o expresie corectă? Bazat pe gramatici 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ă.

Exemplul 1

Să luăm ca exemplu gramatica din Exemplul 1. Ne propunem să scriem o funcţie S() care verifică dacă şirul de la intrare se potriveşte cu ceea ce poate produce simbolul de start S. După verificare, cursorul din fişier va rămîne la primul caracter după şirul verificat. Funcţia va arăta astfel:

char first, eroare;

void S() {
  if ( first == 'a' ) {
    first = fgetc( fin );
    S();
    if ( first == 'b' )
      first = fgetc( fin );
    else
      eroare = 1;
  }
}

Funcţia S() decide care din cele două producţii trebuie urmate analizînd primul caracter de la intrare, memorat în variabila globală first. Dacă are caracterul a, îl consumă, apoi reapelează S(), urmărind producţia din gramatică. În final verifică existenţa literei b, caz în care o consumă. Dacă litera b nu apare, se setează variabila globală de eroare.

Iată programul complet, care afişează 1 dacă şirul este corect, sau 0 în caz contrar:

#include <stdio.h>

FILE *fin, *fout;
int first, eroare;

void S() {
  if ( first == 'a' ) {
    first = fgetc( fin );
    S();
    if ( first == 'b' )
      first = fgetc( fin );
    else
      eroare = 1;
  }
}

int main() {
  fin = fopen( "ab.in", "r" );
  first = fgetc( fin );
  S();
  fclose( fin );

  if ( first != '\n' )
    eroare = 1;
  fout = fopen( "ab.out", "w" );
  fputc( '1'-eroare, stdout );
  fclose( fout );

  return 0;
}

Exemplul 2

Să considerăm gramatica din Exemplul 2. Ne propunem să scriem o funcţiile S(), X() şi Y() care verifică dacă şirul de la intrare se potriveşte cu ceea ce poate produce simbolul de start S. După verificare, cursorul din fişier va rămîne la primul caracter după şirul verificat. Programul arăta astfel:

#include <stdio.h>

FILE *fin, *fout;
int first, eroare;

void X();
void Y();

void S() {
  X();
  Y();
}

void X() {
  if ( first == 'a' ) {
    first = fgetc( fin );
    X();
    if ( first == 'b' )
      first = fgetc( fin );
    else
      eroare = 1;
  }
}

void Y() {
  if ( first == 'c' ) {
    first = fgetc( fin );
    Y();
    if ( first == 'd' )
      first = fgetc( fin );
    else
      eroare = 1;
  }
}

int main() {
  fin = fopen( "abcd.in", "r" );
  first = fgetc( fin );
  S();
  fclose( fin );

  if ( first != '\n' )
    eroare = 1;
  fout = fopen( "abcd.out", "w" );
  fputc( '1'-eroare, stdout );
  fclose( fout );

  return 0;
}

Primul caracter este special

Deoarece vom avea mereu de luat decizii ce "înghițim" mai departe bazat pe primul caracter de la intrare, îl vom ține separat în variabila 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.

Dincolo de corectitudine

Pînă acum am văzut cum scriem un analizor recursiv cu proceduri care ne spune dacă un şir la intrare este corect. Dar dacă am dori să aflăm mai multe? Pentru gramaticile anterioare ne-am putea dori să aflăm factorul maxim de imbricare (numărul maxim de litere 'a' sau 'c'), de exemplu. Sau, pentru o expresie aritmetică, ne-am dori să o evaluăm. De obicei programul analizorului se poate adapta uşor pentru aceste calcule extra. De exemplu, pentru factorul maxim de imbricare am putea să modificăm funcţiile X() şi Y() să returneze acest factor, iar funcţia S() să calculeze maximul:

#include <stdio.h>

FILE *fin, *fout;
int first, eroare;

int X();
int Y();

int S() {
  int x, y;
  x = X();
  y = Y();
  return x > y ? x : y;
}

int X() {
  int x = 0;
  if ( first == 'a' ) {
    first = fgetc( fin );
    x = X() + 1;
    if ( first == 'b' )
      first = fgetc( fin );
    else
      eroare = 1;
  }
  return x;
}

int Y() {
  int y = 0;
  if ( first == 'c' ) {
    first = fgetc( fin );
    y = Y() + 1;
    if ( first == 'd' )
      first = fgetc( fin );
    else
      eroare = 1;
  }
  return y;
}

int main() {
  int max;

  fin = fopen( "abcd.in", "r" );
  first = fgetc( fin );
  max = S();
  fclose( fin );

  if ( first != '\n' )
    eroare = 1;
  fout = fopen( "abcd.out", "w" );
  if ( eroare == 1 )
    fprintf( fout, "-1\n" );
  else
    fprintf( fout, "%d\n", max );
  fclose( fout );

  return 0;
}

Studiu de caz: paranteze 3

Problema paranteze 3 este o modificare a exemplului 2. Ea cere să se spună dacă o expresie de paranteze deschise şi închise este corectă şi să se calculeze gradul de imbricare. Parantezele pot fi rotunde, sau acolade. Ele se pot închide şi acolade în interiorul parantezelor, nu ca la matematică.

Vom folosi următoarea gramatică:

E ⇾ ('('E')'|'{'E'}')*

Remarcaţi că am pus parantezele şi acoladele între apostrofuri, pentru a le distinge de parantezele din descrierea gramaticii. Steluţa de la final înseamnă că expresia dintre paranteze poate să apară de oricîte ori, inclusiv de zero ori. Nu uitaţi că bara verticală înseamna sau, putînd alege oricare din producţii.

Această gramatică spune că o expresie este formată dintr-un şir de oricîte subexpresii, inclusiv niciuna, ceea ce înseamnă că expresia vidă este corectă. O subexpresie este formată dintr-o pereche de paranteze rotunde sau acolade între care se află o expresie. Precum vedeţi gramaticile sînt definiţii recursive.

Studiu de caz: expr

Problema expr cere să evaluăm o expresie. Pentru aceasta să găsim mai întîi gramatica care descrie limbajul expresiilor aritmetice din problemă. Pentru aceasta să definim următorii termeni:

  • Termen: Un termen este o subexpresie care nu conţine adunări sau scăderi. Astfel, o expresie este formată dintr-o înşiruire de termeni care sînt despărţiţi de operatori plus sau minus. Un termen va fi format din factori care se înmulţesc sau împart.
  • Factor: Un factor este o subexpresie care nu conţine adunări, scăderi, înmulţiri sau împărţiri. El este, în principiu, un număr, în faţa căruia putem avea semne, operatori unari plus sau minus. Tot un factor este şi o expresie între paranteze.

Putem acum introduce gramatica:

Expr -> Term (('+'|'-')Term)*
Term -> Fact (('*'|'/')Fact)*
Fact -> Int | ('+'|'-')Fact|'('Expr')' 
Int -> ('0'|'1'|'2'|...|'9')+

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

În continuare vom scrie analizorul recursiv cu proceduri, cu o mică adăugire: fiecare funcţie asociată lui Expr, Term şi Fact va returna valoarea subexpresiei analizate de acel neterminal. Astfel, în final, vom avea valoarea întregii expresii.

Notaţia postfix

Notaţia postfix a unei expresii aritmetice, denumită şi notaţie poloneză inversă, scrie mai întîi operanzii şi apoi operatorii. De exemplu:

  • 3 + 4: notație infixată
  • 4 3 +: notație postfixată sau notație poloneză inversă

Notația postfixată are două mari avantaje:

  1. Nu necesită paranteze. (3 + 4) * 5 se transcrie în notație postfixată ca 3 4 + 5 *
  2. Se poate evalua ușor folosind doar o stivă de operanzi: de câte ori apare un operator se scot elemente de pe stivă (două, sau cîte necesită operatorul), se evaluează operaţia executînd operatorul și se pune rezultatul înapoi pe stivă.

Când întâlnim o sumă de mai mulți termeni sau un produs de mai mulți factori, cel din stânga are prioritate. Cu alte cuvinte, 3 + 4 + 5 se scrie în notație postfixată ca 3 4 + 5 +, nu 3 4 5 + +. Aceasta din urmă ar fi echivalentă cu 3 + (4 + 5). Devine evident de ce avem nevoie de această prioritate dacă ne gândim la expresia 3 - 4 + 5. Dacă o reprezentăm ca 3 4 - 5 +, atunci valoarea ei este 4. Dacă însă o reprezentăm ca 3 4 5 + -, atunci valoarea ei este -6.

Conversia expresiilor la notaţia postfix

Unele probleme, cum ar fi problema pom, nu cer evaluarea unei expresii, ci transformarea ei în notaţie postfix. Cum realizăm acest lucru?

Vom modifica fiecare funcţie corespunzătoare unui simbol neterminal N să scrie la ieşire notaţia postfix a subexpresiei analizate de N. De exemplu, pentru gramatica de la studiul de caz 2, o expresie Expr va chema pe rînd funcţiile neterminalului Term (care vor scrie subexpresiile postfix pentru fiecare termen), iar, începînd cu al doilea termen, va afişa semnul găsit imediat după apelul termenului.

Precum am menţionat mai devreme, modificarea este relativ uşoară.

Temă

La temă vă rămîn problemele de la studiile de caz:

Tema 13 clasele 7/8

Rezolvări aici [2]