Pagina documente » Informatica, Matematica » Algoritmi de performanta pentru analizoare sintactice de tip LR

Despre lucrare

lucrare-licenta-algoritmi-de-performanta-pentru-analizoare-sintactice-de-tip-lr
Aceasta lucrare poate fi descarcata doar daca ai statut PREMIUM si are scop consultativ. Pentru a descarca aceasta lucrare trebuie sa fii utilizator inregistrat.
lucrare-licenta-algoritmi-de-performanta-pentru-analizoare-sintactice-de-tip-lr


Cuprins

Cuprins
CAPITOLUL I Notiuni generale ..............3
CAPITOLUL II Gramatici si arbori de derivare ..3
II.1. Gramatici ..........3
II.2. Arbori de derivare ...........3
CAPITOLUL III Analiza LR ..3
III.1. Analizoare ......3
III.2. Reprezentarea tabelei de actiuni si a tabelei goto ..3
III.3. Constructia unui analizor dintr-o gramatica .........3
III.3.1. Multimi de configuratii ............3
III.3.2. Constructia colectiei canonice .3
III.3.3. Constructia tabelei de actiuni si a tabelei goto din colectia de multimi de configuratie ..........3
III.3.4. Calculul multimilor de predictii .............3
III.4. Analiza gramaticilor ambigue ...3
III.5. Optimizarea analizoarelor LR ...3
III.5.1 Fuziunea starilor identice .........3
III.5.2. Eliminarea starilor care sunt in plus .....3
III.5.3. Eliminarea reducerilor prin productii de tipul A ->X (rescrieri) ....3
III.6. Recuperarea in urma erorilor ...3
CAPITOLUL IV Concluzii .....3
CAPTIOLUL V Un analizor LALR(1) .3
V.1.Specificatii ........3
V.2. Structura analizorului ...3
V.3. Date de test ......3

EXTRAS DIN DOCUMENT

?{p}

{p}

?CAPITOLUL I

Notiuni generale

O specificare completa a unui limbaj de programare trebuie sa indeplineasca cel putin doua functii. În primul rand trebuie specificata sintaxa limbajului; adica care sunt simbolurile care vor construi programe corecte. În al doilea rand, trebuie specificata semantica limbajului; adica, ce semnificatie trebuie atribuita fiecarui program corect din punct de vedere sintactic.

Un compilator pentru un limbaj de programare trebuie sa verifice daca programul se supune conventiilor sintactice ale specificatiilor limbajului. De asemenea, trebuie sa traduca fisierul de intrare intr-un fisier scris intr-un cod obiect, intr-un mod consistent in raport cu semantica limbajului. În plus, daca programul contine erori sintactice, compilatorul ar trebui sa anunte prezenta lor si sa incerce sa indice pozitia lor in codul sursa. Pentru a putea efectua aceste lucruri fiecare compilator are un dispozitiv incorporat, numit analizor.

Pentru a specifica sintaxa unui limbaj de programare se poate folosi o gramatica independenta de context. În plus, daca gramatica este construita cu grija, mare parte din semantica limbajului poate fi exprimata prin regulile gramaticii.

Exista multe tipuri de analizoare pentru gramatici independente de context. În aceasta lucrare vom vorbi doar despre analizoarele LR. Aceste analizoare sunt eficiente si foarte potrivite pentru compilatoare de limbaje de programare. Poate mai important este faptul ca putem genera automat analizoare LR pentru o gama larga si folositoare de gramatici independente de context. Un aspect important al algoritmului pentru generarea unui analizor este detectarea automata a ambiguitatilor si a “bucatilor” dificil de analizat din specificatia limbajului.

Mai intai vom arata cum poate o gramatica independenta de context sa defineasca un limbaj. Apoi vom discuta analiza LR si vom evidentia algoritmul de generare al analizorului. Încheiem prin a arata cum poate fi imbunatatita performanta analizoarelor LR prin cateva transformari simple si cum poate fi incorporata recuperarea erorilor in analiza LR.

În continuare, o secventa de simboluri terminale o vom numi propozitie. Propozitiile sunt scrise intre apostroafe (‘). De exemplu ‘a’, ‘ab’, ‘,’ sunt propozitii. Propozitia vida este ‘’. Doua propozitii scrise una langa alta vor fi concatenate, astfel ‘a’’b’ este sinonim cu ‘ab’. Termenul de limbaj va insemna aici o multime de propozitii.

CAPITOLUL II

Gramatici si arbori de derivare

II.1. Gramatici

O gramatica este folosita pentru a defini un limbaj si pentru a impune o structura pentru fiecare propozitie din limbaj. Ne vom ocupa doar de gramaticile independente de context, denumite uneori specificatii BNF(Backus-Naur form).

Într-o gramatica independenta de context specificam doua seturi disjuncte de simboluri pentru a ajuta la definirea unui limbaj. Unul este un set de simboluri neterminale. Un simbol neterminal va fi reprezentat de o secventa de una sau mai multe litere mari. De exemplu, LIST reprezinta un neterminal, la fel ca si litera A. În gramatica, se distinge in mod special un simbol – simbolul de start (sau propozitia de start).

Al doilea set de simboluri dintr-o gramatica independenta de context este setul de simboluri terminale. Propozitiile limbajului generat de o gramatica vor contine doar simboluri terminale. Un simbol, terminal sau neterminal, se va numi simbol al gramaticii.

O gramatica independenta de context mai contine si un set finit de reguli, numite productii. O productie are forma

parte_stanga -> parte_dreapta,

unde “parte_stanga” este un singur neterminal (uneori numit categorie sintactica) si “parte_dreapta” este o secventa de zero sau mai multe simboluri ale gramaticii. Sageata este doar un simbol special care separa cele doua parti. De exemplu,

LIST -> LIST’,’ELEMENT

este o productie in care LIST si ELEMENT sunt neterminale si virgula dintre apostroafe reprezinta un terminal. O gramatica reprezinta un sistem de rescriere. Daca ?A? este o secventa de simboluri ale gramaticii si A -> ? este o productie, atunci vom scrie ?A? => ??? si vom spune ca ??? deriva direct din ?A?. Un sir de secvente ?0, ?1, ... ?n , astfel incat ?i-1 => ?i pentru 1 ? i ? n se numeste derivare a lui ?n din ?0. Uneori vom spune si ca ?n este derivabil din ?0.

Simbolul de start al unei gramatici se numeste forma propozitionala. O secventa derivabila din simbolul de start este de asemenea o forma propozitionala a gramaticii. O forma propozitionala formata doar din terminale se numeste propozitie generata de gramatica. Limbajul generat de o gramatica G, adesea notat prin L(G), este multimea de propozitii generate de G.