Lucrare de curs lfpc - Limbaje Formale si Proiectarea Compilatoarelor

Extras din document

Analiza sintactică descendentă. Gramatici LL(1). I. Partea teoretică - Strategia de analiză descendentă - Mașina de Analiză Predictivă (MAP) - Mulțimile FIRST, FOLLOW - Simboluri Directoare - Gramatici LL(1) - Construirea MAP pentru gramatici LL(1) - Exemplu II. Partea practică - Să se programeze MAP. Să se testeze exemplul propus. Strategia de analiză descendentă Implementarea unui asemenea proces necesita pentru eventualele reveniri, memorarea drumului parcurs în arbore, precum si a punctelor din sirul de intrare în care s-a început expandarea neterminalelor. Deoarece revenirile se fac strict în ordine inversa fata de cea a expandarilor si avansurilor, mecanismul de baza în implementare va fi cel de stiva. Stiva poate fi implementata explicit, caz în care fiecare element memoreaza starea analizei la momentul actiunii respective, sau implementata implicit, folosind mecanismul de implementare a recursivitatii procedurilor, existent în multe limbaje de programare.În cel de al doilea caz, prin mecanismul recursivitatii se memoreaza ordinea expandarii neterminalelor, deci cu aproximatie drumul parcurs în arbore, în schimb trebuie prevazuta în mod explicit salvarea starii çirului de intrare (referinta curenta spre textul de intrare) pentru fiecare neterminal ce urmeaza a fi expandat.În cazul în care gramatica este recursiva la stânga, exista posibilitatea intrarii intr-un ciclu infinit pentru o anumita clasa de çiruri de intrare. Fenomenul acesta are loc pentru orice solutie de implementare a analizorului sintactic descendent, daca gramatica folosita conduce la derivari de forma A c× A þ, adica pentru orice gramatica recursiva la stânga.În concluzie, pentru implementarea unui analizor sintactic descendent,trebuie eliminata recursivitatea la stânga a gramaticii. Pe lânga eliminarea recursivitatii la stânga, pentru a se putea construi un analizor sintactic descendent recursiv, este necesar sa se realizeze çi factorizarea la stânga a gramaticii, daca este cazul.Factorizarea la stânga reprezinta o transformare care se opereaza asupra unei gramatici. Ideea de baza consta în rescrierea A-productiilor, în cazul în care nu este evident care productie se foloseçte, astfel încât sa se amâne decizia de alegere a unei productii pâna în momentul în care se poate face corect. Mașina de Analiză Predictivă (MAP) Structura maşinii de analiză predictive: