. Algoritmi de Performanta Pentru Analizoare Sintactice de Tip Lr

. Algoritmi de Performanta Pentru Analizoare Sintactice de Tip Lr

Byadmin ianuarie 1, 2024

CAPITOLUL I

Noțiuni generale

O specificare completă a unui limbaj de programare trebuie să îndeplinească cel puțin două funcții. În primul rând trebuie specificată sintaxa limbajului; adică care sunt simbolurile care vor construi programe corecte. În al doilea rând, trebuie specificată semantica limbajului; adică, ce semnificație trebuie atribuită fiecărui program corect din punct de vedere sintactic.

Un compilator pentru un limbaj de programare trebuie să verifice dacă programul se supune convențiilor sintactice ale specificațiilor limbajului. De asemenea, trebuie să traducă fișierul de intrare într-un fișier scris într-un cod obiect, într-un mod consistent în raport cu semantica limbajului. În plus, dacă programul conține erori sintactice, compilatorul ar trebui să anunțe prezența lor și să încerce să indice poziția lor în codul sursă. Pentru a putea efectua aceste lucruri fiecare compilator are un dispozitiv încorporat, numit analizor.

Pentru a specifica sintaxa unui limbaj de programare se poate folosi o gramatică independentă de context. În plus, dacă gramatica este construită cu grijă, mare parte din semantica limbajului poate fi exprimată prin regulile gramaticii.

Există multe tipuri de analizoare pentru gramatici independente de context. În această lucrare vom vorbi doar despre analizoarele LR. Aceste analizoare sunt eficiente și foarte potrivite pentru compilatoare de limbaje de programare. Poate mai important este faptul că putem genera automat analizoare LR pentru o gamă largă și folositoare de gramatici independente de context. Un aspect important al algoritmului pentru generarea unui analizor este detectarea automată a ambiguităților și a “bucăților” dificil de analizat din specificația limbajului.

Mai întâi vom arăta cum poate o gramatică independentă de context să definească un limbaj. Apoi vom discuta analiza LR și vom evidenția algoritmul de generare al analizorului. Încheiem prin a arăta cum poate fi îmbunătățită performanța analizoarelor LR prin câteva transformări simple și cum poate fi încorporată recuperarea erorilor în analiza LR.

În continuare, o secvență de simboluri terminale o vom numi propoziție. Propozițiile sunt scrise între apostroafe (‘). De exemplu ‘a’, ‘ab’, ‘,’ sunt propoziții. Propoziția vidă este ‘’. Două propoziții scrise una lângă alta vor fi concatenate, astfel ‘a’’b’ este sinonim cu ‘ab’. Termenul de limbaj va însemna aici o mulțime de propoziții.

CAPITOLUL II

Gramatici și arbori de derivare

II.1. Gramatici

O gramatică este folosită pentru a defini un limbaj și pentru a impune o structură pentru fiecare propoziție din limbaj. Ne vom ocupa doar de gramaticile independente de context, denumite uneori specificații BNF(Backus-Naur form).

Într-o gramatică independentă de context specificăm două 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 secvență de una sau mai multe litere mari. De exemplu, LIST reprezintă un neterminal, la fel ca și litera A. În gramatică, se distinge în mod special un simbol – simbolul de start (sau propoziția de start).

Al doilea set de simboluri dintr-o gramatică independentă de context este setul de simboluri terminale. Propozițiile limbajului generat de o gramatică vor conține doar simboluri terminale. Un simbol, terminal sau neterminal, se va numi simbol al gramaticii.

O gramatică independentă de context mai conține și un set finit de reguli, numite producții. O producție are forma

parte_stângă -> parte_dreaptă,

unde “parte_stângă” este un singur neterminal (uneori numit categorie sintactică) și “parte_dreaptă” este o secvență de zero sau mai multe simboluri ale gramaticii. Săgeata este doar un simbol special care separă cele două părți. De exemplu,

LIST -> LIST’,’ELEMENT

este o producție în care LIST și ELEMENT sunt neterminale și virgula dintre apostroafe reprezintă un terminal. O gramatică reprezintă un sistem de rescriere. Dacă A este o secvență de simboluri ale gramaticii și A -> este o producție, atunci vom scrie A => și vom spune că derivă direct din A. Un șir de secvențe 0, 1, … n , astfel încât i-1 => i pentru 1 i n se numește derivare a lui n din 0. Uneori vom spune și că n este derivabil din 0.

Simbolul de start al unei gramatici se numește formă propozițională. O secvență derivabilă din simbolul de start este de asemenea o formă propozițională a gramaticii. O formă propozițională formată doar din terminale se numește propoziție generată de gramatică. Limbajul generat de o gramatică G, adesea notat prin L(G), este mulțimea de propoziții generate de G.

Exemplul 1)

Următoarea gramatică, numită G1, are LIST ca simbol de start :

LIST -> LIST ’,’ ELEMENT

LIST -> ELEMENT

ELEMENT -> ’a’

ELEMENT -> ‘b’

Secvența :

LIST => LIST ‘,’ ELEMENT

=> LIST ‘,a’

=> LIST ‘,’ ELEMENT ‘,a’

=> LIST ‘,b,a’

=> ELEMENT ‘,b,a’

=> ‘a,b,a’

este o derivare a propoziției ‘a,b,a’. L(G1) constă din secvențe nevide de a-uri și b-uri, separate prin virgulă.

Să observăm că în derivarea din exemplul de mai sus, cel mai din dreapta neterminal din fiecare formă propozițională este rescris pentru a obține următoarea formă propozițională. O astfel de derivare este denumită derivare de dreapta și fiecare formă propozițională dintr-o astfel de derivare se numește formă propozițională de dreapta. De exemplu,

LIST ’,b,a’

este o formă propozițională de dreapta din G1.

Dacă Aw este o formă propozițională de dreapta în care w este o secvență de terminale și Aw=>w, atunci se numește manipulator pentru w. De exemplu. ‘b’ este manipulator pentru forma propozițională de dreapta LIST‘,b,a’ din ex. 1).

Un prefix din forma propozițională de dreapta w se numește prefix viabil al gramaticii. De exemplu, LIST ‘,’ este un prefix viabil al lui G1 pentru că este prefix pentru forma propozițională de dreapta LIST ‘,’ ELEMENT ( si w sunt nuli aici).

Reformulând această definiție, un prefix viabil al unei gramatici este orice prefix al unei forme propoziționale de dreapta care nu trece peste capătul din dreapta al unui manipulator din acea formă propozițională. Astfel știm că există întotdeauna o secvență de simboluri ale gramaticii care poate fi adăugată la capătul unui prefix viabil pentru a obține o formă propozițională de dreapta. Prefixele viabile sunt importante în construcția compilatoarelor cu posibilități mari de detectare a erorilor; atâta timp cât partea de intrare văzută poate fi derivată dintr-un prefix viabil, putem fi siguri că nu există erori care să apară din acea parte de intrare.

II.2. Arbori de derivare

Adesea, interesul nostru pentru o gramatică nu constă doar în limbajul pe care-l generează, ci și în structura pe care o impune propozițiilor limbajului. Aceasta pentru că analiza gramaticală este strâns legată de alte procese, cum ar fi compilarea și translatarea, iar translatările sau acțiunile celorlalte procese sunt adesea definite cu ajutorul producțiilor gramaticii. Acestea fiind spuse, ne îndreptăm atenția înspre reprezentarea unei derivări printr-un arbore de derivare.

Pentru fiecare derivare dintr-o gramatică putem construi un arbore de derivare corespunzător. Să considerăm derivarea din exemplul 1). Pentru a modela primul pas în derivare, în care LIST este rescris ca LIST ‘,’ ELEMENT folosind producția 1, creăm mai întâi o rădăcină etichetată cu simbolul de start LIST, iar apoi creăm trei descendenți direcți ai ei, etichetați LIST, ‘,’ și ELEMENT

În cel de-al doilea pas al derivării, ELEMENT este rescris ca 'a'. Pentru a modela acest pas, creăm un descendent direct etichetat cu 'a' pentru nodul etichetat cu ELEMENT :

Continuând în această manieră, obținem următorul arbore de derivare :

Să observăm că dacă un nod dintr-un arbore de derivare este etichetat cu un neterminal A și descendenții săi direcți sunt etichetați X1, X2, …Xn , atunci producția

A -> X1, X2, …Xn

trebuie să existe în gramatică.

Dacă a1, …am sunt etichetele tuturor frunzelor arborelui de derivare, în ordine de la stânga la dreapta, atunci secvența a1, …am este numită frontiera arborelui. De exemplu 'a,b,a' este frontiera arborelui precedent. Evident, pentru fiecare propoziție din limbaj există cel puțin un arbore de derivare cu acea propoziție ca frontieră. O gramatică care admite doi sau mai mulți arbori de derivare distincți cu aceeași frontieră se spune că este ambiguă.

Exemplul 2)

Gramatica G2 cu producțiile :

LIST -> LIST ',' LIST

LIST -> 'a'

LIST -> 'b'

este ambiguă pentru că următorii doi arbori de derivare au aceeași frontieră :

În anumite situații gramaticile ambigue se pot folosi pentru a reprezenta limbaje de programare într-un mod mai economic decât ar putea-o face gramaticile neambigue echivalente. Oricum, dacă este folosită o gramatică ambiguă, atunci trebuie specificate alte reguli pe lângă cele existente pentru a determina care din arborii de derivare posibili să fie asociat cu intrarea. Asupra gramaticilor ambigue vom reveni mai târziu.

CAPITOLUL III

Analiza LR

III.1. Analizoare

Putem considera un analizor pentru o gramatică ca fiind un dispozitiv care, atunci când îi este dat o secvență de intrare, încearcă să construiască un arbore de derivare a cărui frontieră să se potrivească cu această secvență. Dacă analizorul poate construi un astfel de arbore de derivare, atunci el va fi verificat că secvența de intrare este o propoziție a limbajului generat de gramatică. Dacă intrarea este incorectă din punct de vedere sintactic, atunci procesul de construcție nu va reuși și pozițiile la care procesul eșuează pot fi folosite pentru a indica posibile locații ale erorilor.

Un analizor poate opera în multe moduri diferite. Aici ne vom referi doar la analizoare care examinează secvența de intrare de la stânga la dreapta, câte un simbol odată. Aceste analizoare vor încerca să cobnstruiască arborele de derivare de jos în sus, adică de la frunze înspre rădăcină. Din motive istorice aceste analizoare se numesc LR. "L" vine de la "left-to-right" (de la stânga la dreapta); "R" vine de la "rightmost derivation" (derivare de dreapta). Vom vedea că un analizor LR construiește inversa unei derivări de dreapta pentru intrare. Aici vom descrie într-un mod neformal modul cum operează o anumită clasă de analizoare LR, numite LR(1).

Un analizor LR operează, în timpul construcției arborelui de derivare, cu o mulțime de arbori parțial construiți. Vom numi această mulțime de arbori pădure. Aici, pădurea este construită de la stânga la dreapta pe măsură ce este citită intrarea. La o anumită etapă din procesul de construcție, am citit o anumită cantitate din intrare și avem un arbore parțial construit. De exemplu, să presupunem că analizăm intrarea 'a,b' pentru gramatica G1. După ce am citit 'a' construim arbore ele . Apoi construim :

folosind producția ELEMENT -> 'a'. Pentru a reflecta această acțiune a analizei, spunem că 'a' este redus la ELEMENT. Apoi folosim producția LIST -> ELEMENT pentru a obține arborele :

Aici ELEMENT este redus la LIST. Apoi citim din intrare următorul simbol, ',' și îl adăugăm la pădure ca un arbore cu un singur nod, . Acum avem doi arbori. Acești arbori vor deveni eventual subarbori în arborele final de derivare. Apoi citim următorul simbol din intrare, 'b' și creăm arbore cu un singur nod și pentru el :

Folosind producția ELEMENT -> 'b' reducem 'b' la ELEMENT , iar în final, folosind producția LIST -> LIST ',' ELEMENT combinăm acești trei arbori în arborele final :

În acest moment analizorul detectează că am citit toată intrarea și anunță ca analiza este completă. Derivarea de dreapta a lui 'a,b' în G1 este :

LIST => LIST ',' ELEMENT

=> LIST ',b'

=> ELEMENT ',b'

=> 'a,b'

Analizând 'a,b' în modul arătat mai sus, tot ce trebuie să facem este să reconstruim derivarea de dreapta în sens invers. Secvența de producții găsite parcurgând o derivare de dreapta în sens invers se numește analiză de dreapta.

Existparcurgând o derivare de dreapta în sens invers se numește analiză de dreapta.

Există patru tipuri de acțiuni de analiză pe care le poate face un analizor LR : shift (deplasare), reduce (reducere), accept (acceptare, anunță terminarea analizei) și error (eroare).

Într-o acțiune de deplasare următorul simbol este luat de la intrare. Un nou nod etichetat cu acest simbol este adăugat la pădure, la dreapta, ca un nou arbore.

Într-o acțiune de reducere este specificată o producție, cum ar fi

A -> X1, X2, …Xn

fiecare Xi reprezentând un terminal sau un neterminal. O reducere prin această producție cauzează următoarele operații :

1) Este creat un nod etichetat cu A;

2) Cele mai din dreapta n rădăcini din pădure (care au fost deja etichetate cu X1, X2, …Xn) sunt făcute descendenți direcți ai noului nod, care devine astfel cea mai din dreapta rădăcină a pădurii.

Dacă reducerea se face printr-o producție de forma A -> '' (adică atunci când partea dreaptă este secvența vidă) analizorul crează doar o rădăcină etichetată cu A, fără nici un descendent.

Un analizor operează făcând în mod repetat acțiuni de analiză până când apare acțiunea de acceptare sau de eroare. Următoarea secvență de acțiuni de analiză construiește arborele de analiză pentru 'a,b' în G1 :

(1) Shift 'a'

(2) Reduce by ELEMENT -> 'a'

(3) Reduce by LIST -> ELEMENT

(4) Shift ','

(5) Shift 'b'

(6) Reduce by ELEMENT -> 'b'

(7) Reduce by LIST -> LIST ',' ELEMENT

(8) Accept

Ne întrebăm acum cum decide un analizor LR ce acțiuni de analiză să facă. Evident, o acțiune de analiză poate depinde de ce acțiuni s-au făcut deja și care sunt următoarele simboluri din intrare. Un analizor LR care "vede" doar următorul simbol din intrare, pentru a decide ce acțiune să facă, se numește analizor LR(1). Dacă "vede" următoarele k simboluri din intrare, cu k 0, se numește analizor LR(k). Ca un ajutor pentru luarea deciziilor, un analizor LR atașează rădăcinii fiecărui arbore din pădure un număr numit stare. Numărul rădăcinii arborelui celui mai din dreapta se numește stare curentă. Mai există și o stare inițială în stânga pădurii care ajută la determinarea primei acțiuni de analiză. Vom scrie stările în paranteze, deasupra rădăcinilor asociate. De exemplu,

(1)

(5)

(0)

reprezintă o pădure cu stări. Starea (5) este starea curentă și starea (0) este starea inițială. Starea curentă și următorul simbol din intrare determină acțiunea de analiză a unui analizor LR(1).

Următorul tabel arată stările unui analizor LR(1) pentru G1 și acțiunile de analiză asociate. În acest tabel există o coloană etichetată cu '$' cu o semnificație specială. '$' are rolul de delimitator de dreapta, care se presupune a fi adăugat la sfârșitul tuturor secvențelor de intrare. Alt mod de a privi acest lucru este să ne gândim la '$' ca reprezentând condiția de a fi citit și deplasat toate caracterele "reale" din secvența de intrare.

Următorul simbol de la intrare

Acțiunile de reducere sunt reprezentate sub forma "Red. n", întregul n referindu-se pa producții după cum urmează :

(1) LIST -> LIST ',' ELEMENT

(2) LIST -> ELEMENT

(3) ELEMENT -> 'a'

(4) ELEMENT -> 'b'

Ne vom referi la celul pentru linia s și coloana c ca action(s,c). După ce am făcut ori o deplasare, ori o reducere analizorul trebuie să determine ce stare să atașeze rădăcinii arborelui ce tocmai a fost adăugat la pădure. Într-o mișcare de deplasare această stare este determinată de starea curentă și de simbolul de intrare care tocmai a fost deplasat în pădure.

De exemplu, dacă tocmai am deplasat ',' în pădure :

(1)

(0) (5)

atunci starea (1) și ',' determină starea care să fie atașată noii rădăcini ce se află cel mai în dreapta, adică ','.

Într-o mișcare de reducere, să presupunem că reducem prin producția :

A -> X1, X2, …Xn

Când facem ca nodurile X1, X2, …Xn sa fie descendenți direcți ai rădăcinii A, ștergem stările atașate la X1, X2, …Xn. Starea care trebuie atașată nodului A este determinată de starea care este acum cel mai în dreapta în pădure și de neterminalul A. De exemplu, dacă tocmai am redus prin producția :

LIST -> LIST ',' ELEMENT

și am creat pădurea :

(0)

atunci starea (0) și neterminalul LIST determină starea ce urmează a fi atașată rădăcinii LIST. Să observăm că stările atașate anterior descendenților direcți ai noii rădăcini au dispărut și nu mai joacă nici un rol în calculul noii stări.

Tabelul următor determină aceste noi stări pentru G1. Vom numi acest tabel tabela goto pentru G1 :

Ne vom referi la celula pentru linia s și coloana c ca goto(s,c). Reiese de aici că celulele din tabela goto care sunt goale nu vor fi consultate niciodată.

Un analizor LR pentru o gramatică este specificat complet când am dat tabela acțiunilor de analiză și tabela goto. Putem să ne imaginăm un analizor LR(1) ca în figura de mai jos :

INTRARE

CURSOR LA INTRARE

Algoritmul analizei LR(1) poate fi rezumat după cum urmează :

Inițializare : Punem starea inițială într-o pădure goală; starea inițială este starea curentă la începutul analizei.

Acțiunea de analiză : Examinăm tabela de acțiuni de analiză și determinăm valoarea corespunzătoare stării curente și simbolului de intrare curent. Pe baza acestei valori (shift, reduce, error sau accept) executăm una din următoarele patru acțiuni :

Deplasare : Adăugăm un nou nod la pădure, etichetat cu simbolul de intrare curent. Îi asociem starea goto (stare_curentă, intrare) și facem ca această stare să fie noua stare curentă. Avansăm cursorul de intrare pentru a citi următorul caracter. Repetăm pasul Acțiunea de analiză.

Reduce : Dacă producția indicată este A -> X1, X2, …Xn adăugăm un nou nod etichetat cu A la pădure ș facem ca cele mai din dreapta n rădăcini (n 0) să fie descendenți direcți ai acestui nod. Eliminăm stările asociate acestor rădăcini. Dacă s este starea care se află cel mai în dreapta în pădure (pe rădăcina imediat din stânga noului nod) atunci asociem starea goto (s,A) noului nod. Facem ca această stare să fie noua stare curentă. (Să observăm că la intrare caracterul nu se schimbă). Repetăm pasul Acțiunea de analiză.

Accept : Stop. A fost construit un arbore de derivare complet.

Error : A apărut o eroare în secvența de intrare. Anunțăm eroarea și apoi încercăm să terminăm analiza recuperând eroarea (cum facem acest lucru vom discuta mai târziu).

Pentru a vedea cum lucrează un analizor LR, să analizăm din nou secvența de intrare 'a,b' folosind funcția acțiune de analiză action și funcția goto exprimate în tabelele date mai sus.

Inițializare : Punem starea (0) în pădure; (0) devine stare curentă.

Acțiunea de analiză 1 : action (0,'a') = shift. Creăm o nouă rădăcină etichetată cu 'a' și îi atașăm starea (3) (pentru că goto (0,'a')=3). Avem :

(3)

(0)

Acțiunea de analiză 2 : action (3, ',') = reduce 3. Reducem prin producția 3 : ELEMENT -> 'a'. Examinăm starea imediat din stânga; această stare este (0). Deoarece goto (0, ELEMENT) = 2 etichetăm noua rădăcină cu (2). Avem acum :

(2)

(0)

Acțiunea de analiză 3 : action (2, ',') = reduce 2. Reducem prin producția 2 : LIST -> ELEMENT. goto (0, LIST) = 1, deci noua stare este (1).

Acțiunea de analiză 4 : action (1, ',') = shift. Ne deplasăm și atașăm starea (5).

Acțiunea de analiză 5 : action (5, 'b') = shift. Ne deplasăm și atașăm starea (4). Avem acum :

(1)

(5) (4)

(0)

Acțiunea de analiză 6 : action (4, '$') = reduce 4. Reducem prin producția 4, ELEMENT -> 'b', goto (5, ELEMENT) = 6, deci noua stare este (6). Avem acum :

(1)

(6)

(5)

(0)

Acțiunea de analiză 7 : action (6, '$') = reduce 1. Reducem prin producția 1, LIST -> LIST ',' ELEMENT. Starea din stânga arborelui nou creat este (0) deci noua stare este goto (0, LIST) = 1.

Acțiunea de analiză 8 : action (1, '$') = accept. Ne oprim și terminăm analiza.

Analizoarele LR(1) bine construite pot analiza o clasă largă de limbaje folositoare numite limbaje deterministe indepentente de context. Aceste analizoare au câteva propietăți importante :

(1) Raportează erorile cât mai curând posibil (scanâd intrarea de la stănga spre dreapta);

(2) Analizează o secvență într-un timp proporțional cu lungimea ei;

(3) Nu necesită recitirea a ceea ce a citit anterior;

(4) Analizoarele pot fi generate mecanic pentru o clasă largă de gramatici, inclusiv toate gramaticile care pot fi analizate prin coborâre recursivă, fără backtracking și acele gramatici analizabile cu tehnici de precedența operatorilor.

Se poate observa că stările pot fi memorate într-o stivă deoarece cea mai din dreapta stare este folosită, în orice etapă din procesul de analiză. Într-o acțiune de deplasare înlocuim un șir de stări din vârful stivei cu o nouă stare. De exemplu, analizând secvența de intrare 'a,b' stiva va arăta după cum urmează în cadrul fiecărei acțiuni prezentate mai sus. (Vârful stivei este în dreapta.)

Astfel, controlul analizei este independent de arbori, și depinde doar de o stivă de stări. În practică, s-ar putea să nu fie nevoie să construim explicit arborele de derivare, dacă translatarea de efectuat este suficient de simplă. De exemplu, mai tărziu vom menționa o gamă de translatări folositoare care pot fi efectuate de un analizor LR fără a crea pădurea.

Dacă dorim să construim arborele de derivare, o putem face cu ușurință punând în stivă, împreună cu fiecare stare, rădăcina arborelui asociat cu acea stare.

III.2. Reprezentarea tabelei de acțiuni și a tabelei goto

Memorând tabela de acțiuni și tabela goto liniar, ca matrici, facem o risipă mare de spațiu pentru analizoare mari. De exemplu, tabela goto este aproape în întregime goală. Acum vom discuta unele modalități simple de a comprima aceste tabele, economisind astfel mult spațiu; de fapt reprezentăm o matrice rară mai compact, folosind o codificare specială.

Să începem cu acțiunile de deplasare. Daca x este un simbol terminal și s este o stare, acțiunea de analiză asupra lui x în starea s este de deplasare dacă și numai dacă goto (s,x) nu este vidă. Vom codifica goto în acțiunea de deplasare folosind shift 17 ca o prescurtare pentru "deplasează și atașează starea (17) noului nod". Codificând goto-urile pentru simbolurile terminale în tabela de acțiuni, vom avea în vedere numai goto-urile pentru neterminale. Le vom codifica pe coloane, adică după numele terminalului. Dacă pentru un neterminal A există valori goto nevide corespunzător stărilor s1, s2, …sn și avem si' = goto (si,A) pentru i = 1, …, n atunci vom codifica coloana pentru A într-un pseudo-limbaj de programare :

A : if (stare = s1) goto = s1'

.

if (stare = sn) goto = sn'

Tabela goto pentru G1 va fi reprezentată astfel :

LIST : if (stare = 0) goto = 1

ELEMENT : if (stare = 0) goto = 2

if (stare = 5) goto = 6

Reiese de aici că, de fiecare dată când facem un goto pe A, starea va fi una din stările s1, s2, …sn chiar dacă avem o eroare în secvența de intrare. Astfel, se va alege întotdeauna una din aceste ramuri.

Vom codifica acțiunile de analiză în același fel, dar după liniile din tabelă. Acțiunile de analiză pentru o stare s vor fi de asemenea reprezentate printr-o mulțime de instrucțiuni într-un pseudo-limbaj de programare. Dacă simbolurile de la intrare a1, a2, …an au asociate acțiunile ac1, ac2, …acn , atunci vom scrie :

s : if (intrare = a1) ac1

.

if (intrare = an) acn

Cum am menționat mai devreme vom atașa goto (s, ai) acțiunii dacă aci este deplasare. La fel, dacă avem o reducere prin producția A -> vom scrie de obicei reduce by A -> ca fiind acțiunea.

De exemplu, acțiunile de analiză pentru starea (1) din analizorul pentru G1 sunt reprezentate prin :

1 : if (intrare = 'a') error

if (intrare = 'b') error

if (intrare = ',') shift 5

if (intrare = '$') accept

La prima privire aceasta nu reprezintă o economie din moment ce tabela de acțiuni e aproape plină. Putem face o mare economie, totuși, introducând noțiunea de acțiune obișnuită (defalut action) în instrucțiuni. O acțiune obișnuită este pur și simplu o acțiune de analiză care este executată indiferent de caracterul de intrare; poate exista cel mult o astfel de acțiune pentru fiecare stare și va fi scrisă la sfârșit. Astfel, în starea (1) avem două acțiuni de eroare ca fiind acțiune obișnuită. Vom scrie:

1 : if (intrare = ',') shift 5

if (intrare = '$') accept

error

Se poate face o economie în plus. Să presupunem că o stare are și intrări de eroare și de reducere. Atunci putem înlocui toate intrările de eroare pentru acea stare cu una din intrările de reucere. Analizorul obținut face o serie de reduceri în locurile unde analizorul inițial ar fi anunțat eroare dar cel nou va anunța eroarea înainte de a se deplasa la următorul simbol din intrare. Ambele analizoare anunță eroarea în aceeași poziție din intrare, dar noului analizor i-ar putea lua puțin mai mult timp pentru a face acest lucru.

Există un avantaj care apare datorită acestei modificări : noua tabelă de acțiuni va cere mai puțin spațiu decât cea inițială. De exemplu, starea (2) din tabela de acțiuni pentru G1 ar fi fost reprezentată inițial prin :

2 : if (intrare = 'a') error

if (intrare = 'b') error

if (intrare = ','') reduce 2

if (intrare = '$') reduce 2

Aplicând această transformare, starea (2) va fi reprezentată doar prin :

2 : reduce 2

Astfel, într-o stare cu acțiuni de reducere, vom avea întotdeauna acțiunile de deplasare și acceptare înaintea celor de reducere. Una din acțiunile de reducere va deveni acțiunea obișnuită și vom ignora intrările de eroare. Într-o stare fără acțiuni de reducere, acțiunea obișnuită va fi cea de eroare. Vom mai vorbi despre reducerea dimensiunilor unui analizor mai târziu.

III.3. Construcția unui analizor dintr-o gramatică

Vom sublinia o metodă care funcționează pentru o gamă de gramatici numite gramatici LR(1) cu predicții (lookahead LR(1) – LALR(1)).

Comportarea unui analizor LR, cuma fosy descrisă în ultima secțiune, este dată de starea curentă. Această stare reflectă progresul analizorului, adică rezumă informația despre secvența de la intrare citită pană la un moment dat astfel încât să poată fi luate decizii de analiză.

Alt mod de a vedea o stare este de a o considera o reprezentare a unei clase de echivalență pentru prefixe viabile. La fiecare etapă a procesului de analiză, secvența formată prin concatenarea simbolurilor gramaticii de pe rădăcinile subarborilor existenți trebuie să fie un prefix viabil; starea curentă este reprezentarea clasei de echivalență ce conține acel prefix viabil.

III.3.1. Mulțimi de configurații

La fel cum trebuie să discutăm despre arborii parțial construiți când vorbim despre analiză, trebuie să discutăm și despre "producții parțial recunoscute" când vorbim despre construcția analizoarelor. Pentru aceasta introducem noțiunea de configurație. O configurație este pur și simplu o producție cu un punct (.) plasat undeva în partea dreaptă (chiar și la sfârșit). De exemplu :

[LIST -> LIST . ',' ELEMENT]

[ELEMENT -> . 'a']

sunt configurații ale lui G1 .

Punem configurațiile între paranteze drepte pentru a face diferență între ele și producții.

Intuitiv, o mulțime de configurații poate fi folosită pentru a reprezenta o etapă în procesul de analiză; de exemplu, configurația [A -> .] indică faptul că secvența de intrare derivabilă din a fost citită și, dacă vom citi în continuare o secvență de intrare derivabilă din , vom putea reduce prin producția A -> .

Să presupunem că bucata de intrare pe care am citit-o până în acest moment a fost redusă la prefixul viabil . Atunci, configurația [A -> .] este validă pentru dacă A este de asemenea un prefix viabil. În general, mai multe configurații sunt valide pentru un prefix viabil; mulțimea tuturor configurațiilor valide la o anumită etapă a analizei corespunde stării curente a analizorului.

Ca exemplu, să verificăm prefixul viabil LIST ',' din G1 . Configurația

[LIST -> LIST ',' . ELEMENT]

este validă pentru acest prefix deoarece, luând ca secvența vidă și ca LIST ',' în definiția de mai sus, vedem că LIST (care este doar LIST) este un prefix viabil. Cu alte cuvinte, când această configurație este validă am citit o parte din intrare care poate fi redusă la prefixul viabil și vom citi în continuare o bucată din intrare care va putea fi redusă la ELEMENT.

Configurația [LIST -> . ELEMENT] nu este validă pentru LIST ',' totuși, deoarece luând la LIST ',' și ca secvența vidă vom obține LIST ',' LIST care nu este un prefix viabil.

Vom asocia o stare a analizorului cu fiecare mulțime de configurații valide și vom calcula valorile din tabela cu acțiuni de analiză pentru acea stare, din mulțimea de configurații. Există un număr finit de producții, deci există un număr finit de configurații și un număr finit de stări posibile asociate fiecărei gramatici G.

III.3.2. Construcția colecției canonice

Vom descrie acum o procedură pentru generarea tuturor stărilor și în același timp pentru generarea tabelei de acțiuni și a tabelei goto. Ca un exemplu vom construi tabela de acțiuni și tabela got pentru G1 .

Mai întâi vom îmbogăți gramatica cu producția

ACCEPT -> LIST

unde LIST va fi în general simbolul de start pentru gramatică (aici G1). O reducere prin această producție corespunde acțiunii de acceptare a analizorului.

Apoi construim I0 = V (' '), mulțimea de configurații valide pentru prefixul viabil reprezentat de secvența vidă. Prin definiție, pentru G1 această mulțime trebuie să conțină configurația [ACCEPT -> . LIST]. Punctul din fața neterminalului LIST înseamnă că, în acest moment, ne așteptăm să găsim la intrare orice propoziție derivabilă din LIST. Astfel, I0 mai trebuie să conțină configurațiile :

[LIST -> . LIST ',' ELEMENT]

[LIST -> . ELEMENT]

obținute din cele două producții pentru neterminalul LIST. A doua configurație are punct în fața neterminalului ELEMENT, deci va trebui să adăugăm la starea inițială și configurațiile :

[ELEMENT -> . 'a']

[ELEMENT -> . 'b']

corespunzătoare celor două producții pentru ELEMENT. Aceste cinci configurații constituie I0 . Vom asocia starea 0 cu I0 .

Acum să presupunem că am calculat V(), mulțimea de configurații valide pentru prefixul viabil . Fie X un terminal sau neterminal. Calculăm V(X) din V() după cum urmează :

(1) Pentru fiecare configurație de forma [A -> . X] din V() adăugăm în V(X) configurația [A -> X . ]

(2) Calculăm închiderea mulțimii de configurații din V(X); adică, pentru fiecare configurație de forma [B -> . C] din V(X) unde C este neterminal, adăugăm la V(X) configurațiile :

[C -> . 1]

[C -> . 2]

.

[C -> . n]

unde C -> 1 , … C -> n sunt toate producțiile din G cu C în partea stângă. Dacă una dinaceste configurații există deja în V(X) nu o mai adăugăm. Continuăm acest proces până nu mai pot fi adăugate noi configurații la V(X).

Se poate arăta că pașii (1) și (2) calculează exact configurațiile valide pentru X. De exemplu, să calculăm I1 = V(LIST), mulțimea de configurații valide pentru prefixul viabil LIST. Aplicăm algoritmul de mai sus cu = ' ' și X = LIST și folosim cele cinci configurații din I0 .

În pasul (1) al algoritmului de mai sus adăugăm configurațiile :

[ACCEPT -> LIST . ]

[LIST -> LIST . ',' ELEMENT]

la I1. Deoarece nici o configurație din I1 nu are un neterminal imediat în dreapta punctului, operația de închidere nu adaugă nici o configurație la I1 . Vom asocia starea (1) cu I1 .

Observați că algoritmul de mai sus este total independent de ; avem nevoie doar de configurațiile din V() ș de X. Pentru fiecare mulțime de configurații I și fiecare simbol al gramaticii, algoritmul construiește o nouă mulțime de configurații pe care o vom numi GOTO (I,X); aceasta este aceeași funcție goto întâlnită în ultimele două secțiuni. Astfel, în exemplul nostru, am calculat GOTO (I0, LIST)= I1 .

Putem extinde această funcție GOTO la secvențe de simboluri ale gramaticii după cum urmează :

GOTO (I, ' ') = I

GOTO (I, X) = GOTO (GOTO (I, ), X)

unde este o secvență de simboluri din gramatică și X este un neterminal sau terminal. Dacă I = V() atunci I = GOTO (I0, ). Astfel, GOTO (I0, ) dacă și numai dacă este un prefix viabil, unde I0 = V (' ').

Mulțimile de configurații ce pot fi obținute din I0 cu funcția GOTO se numesc mulțimi accesibile de configurații (stări accesibile). Construim mulțimea de stări accesibile calculând GOTO (I, X) pentru toate stările accesibile I și simbolurile X din gramatică; de fiecare dată când GOTO produce o nouă stare nevidă, aceasta este adăugată la mulțimea de stări accesibile și procesul continuă. Deoarece numărul de stări este finit, procesul se termină la un moment dat.

Ordinea în care sunt calculate aceste stări nu contează și nici denumirea pe care o dăm fiecăreia. Vom denumi stările I0 , I1 , … în ordinea în care le creăm. Apoi vom asocia starea (i) cu Ii .

Să revenim la G1 . Am calculat I0 care conține configurațiile :

[ACCEPT -> . LIST]

[LIST -> . LIST ',' ELEMENT]

[LIST -> . ELEMENT]

[ELEMENT -> . 'a']

[ELEMENT -> . 'b']

Acum dorim să calculăm GOTO (I0, X) pentru toate simbolurile X din gramatică. Am calculat deja GOTO (I0, LIST) = I1 .Pentru a determina GOTO (I0, ELEMENT) ne uităm la toate configurațiile din I0 care au punctul imediat înainte de ELEMENT. Luăm aceste configurații și mutăm punctul în dreapta lui ELEMENT. Obținem o singură configurație, [LIST -> ELEMENT .]. Operația de închidere nu aduce nici o configurație nouă din moment ce această configurație nu are nici un neterminal în dreapta punctului. Vom numi mulțimea formată din această configurație I2 . Continuând în acest mod aflăm că :

GOTO (I0, 'a') conține doar pe

[ELEMENT -> 'a' .]

GOTO (I0, 'b') conține doar pe

[ELEMENT -> 'b' .]

și GOTO (I0, ',') și GOTO (I0, '$') sunt vide. Să denumim cele două mulțimi nevide I3 și I4 . Am calculat acum toate mulțimile de configurații accesibile direct din I0 .

Calculăm acum toate mulțimile de configurații accesibile din mulțimile de configurații pe care tocmai le-am calculat. Continuăm să calculăm mulțimi accesibile de configurații până când nu se mai găsesc unele noi. Tabela următoare arată colecția de mulțimi accesibile de configurații pentru G1 :

I0 : [ACCEPT -> . LIST]

[LIST -> . LIST ',' ELEMENT]

[LIST -> . ELEMENT]

[ELEMENT -> . 'a']

[ELEMENT -> . 'b']

I1 : [ACCEPT -> LIST .]

[LIST -> LIST . ',' ELEMENT]

I2 : [LIST -> ELEMENT .]

I3 : [ELEMENT -> 'a' .]

I4 : [ELEMENT -> 'b' .]

I5 : [LIST -> LIST ',' . ELEMENT]

[ELEMENT -> . 'a']

[ELEMENT -> . 'b']

I6 : [LIST -> LIST ',' ELEMENT .]

Funcția GOTO pentru această colecție poate fi schematizată ca un graf orientat în care nodurile sund etichetate cu mulțimi de configurații și arcele cu simboluri ale gramaticii, după cum urmează :

LIST ',' ELEMENT

ELEMENT

'a' 'a'

'b' 'b'

Aici am folosit i în loc de Ii . De exemplu, observăm că :

GOTO (0, ' ') = 0

GOTO (0, LIST ',') = 5

GOTO (0, LIST ',' ELEMENT) = 6

Observăm că există o cale de la intrarea 0 la un nod dat dacă și numai dacă acea cale construiește un prefix viabil. Astfel, GOTO (0, 'ab') este vidă deoarece 'ab' nu este un prefix viabil.

III.3.3. Construcția tabelei de acțiuni și a tabelei goto din colecția de mulțimi de configurație

Tabela cu acțiunile de analiză se construiește din colecția de mulțimi accesibile de configurații. Pentru configurațiile din fiecare mulțime Ii generăm acțiunile de analiză. O configurație de forma [A -> . 'a'] din Ii generează acțiunea de analiză :

if (intrare = 'a') shift t

unde GOTO (Ii, 'a') = It .

O configurație cu punctul la sfârșit, în dreapta producției se numește configurație finală. O configurație finală [A -> .] indică faptul că putem reduce prin producția A -> . Totuși, la un analizor LR(1) trebuie să determinăm pe ce simbol de intrare este posibilă această reducere. Dacă 'a1', 'a2', … 'an', sunt aceste simboluri și ele nu sunt asociate cu vreo acțiune de deplasare sau de acceptare, atunci vom genera secvența de acțiuni :

(intrare = 'a1') reduce by A ->

(intrare = 'a2') reduce by A ->

.

(intrare = 'an') reduce by A ->

Așa cum am spus în ultima secțiune, dacă mulțimea de configurații conține doar configurații finale, puetm înlocui această secvență de acțiuni prin acțiunea generală reduce by A -> . Această acțiune este plasată după toate acțiunile de deplasare și acceptare generate de această mulțime de configurații.

Dacă o mulțime de configurații conține mai mult de o configurație finală, atunci trebuie să generăm acțiuni de reducere condiționale pentru toate configurațiile finale cu excepția uneia.

Dacă o configurație finală este de forma [ACCEPT -> S .] atunci generăm acțiunea de acceptare :

if (intrare = '$') accept

unde '$' este indicatorul de afârșit pentru secvența de intrare.

În final, dacă o mulțime de configurații nu generează nici o acțiune de reducere vom genera eroare. Acest mesaj este plasat după toate acțiunile de deplasare și acceptare generate din mulțimea de configurații.

Întorcându-ne la exemplul nostru pentru G1 , din I0 am genera acțiunile :

if (intrare = 'a') shift 3

if (intrare = 'b') shift 4

error

Observați că acestea sunt exact acțiunile pentru starea (0) din analizorul din secțiunea III.1. În mod similar, I3 generează acțiunea

reduce by : ELEMENT -> 'a'

Tabela goto este folosită pentru a calcula noua stare după ce a avut loc o reducere. De exemplu, când reducerea din starea (3) este făcută, întotdeauna avem starea (0) în dreapta lui 'a'. Noua stare este determinată din :

GOTO (I0, ELEMENT) = I2

Aceasta determină execuția codului :

if (stare = 0) goto 2

pentru ELEMENT din tabela goto.

În general, dacă neterminalul A are exact următoarele acțiuni GOTO în graful GOTO :

GOTO (Ii1,A) = It1

GOTO (Ii2,A) = It2

.

GOTO (Iin,A) = Itn

atunci vom genera următoarea reprezentare pentru coloana A a tabelei goto :

A : if (stare = s1) goto = t1

if (stare = s2) goto = t2

.

if (stare = sn) goto = tn

Astfel, tabela goto este pur și simplu o reprezentare a funcției GOTO din ultima secțiune, aplicată simbolurilor neterminale.

Acum trebuie să determinăm simbolurile de intrare asupra cărora este aplicată reducerea. Acest lucru ne va permite să detectăm ambiguitățile și construcțiile dificil de analizat din gramatici și să alegem între reduceri dacă sunt posibile mai multe pentru o stare dată. În general, aceasta este o sarcină complexă; soluția cea mai generală pentru această problemă a fost dată de Knuth în 1965, dar algoritmul său cere timp mult și spațiu mare de memorie. Au fost propuse câteva simplificări de către DeRemer (1969 și 1971) cărora le lipsește generalitatea completă a tehnicii lui Knuth, dar care pot construi analizoare practice ce lucrează într-un timp rezonabil pentru o gamă largă de limbaje. Vom descrie un algoritm care rezolvă toate conflictele ce pot fi rezolvate când analizorul are stările date mai sus.

III.3.4. Calculul mulțimilor de predicții

Să presupunem că [A -> . ] este o configurație validă pentru un prefix viabil . Spunem că simbolul de intrare 'a' este aplicabil pentru [A -> . ] dacă, pentru o secvență de terminale 'w', atât 'aw' cât și A'aw' sunt forme propoziționale de dreapta. Marcatorul de sfârșit '$' este aplicabil pentru [A -> . ] dacă și și A sunt forme propoziționale de dreapta.

Această definiție are o explicație simplă când avem în vedere configurații finale. Să presupunem că simbolul 'a' este aplicabil pentru configurația finală [A->]. Dacă un analizor LR(1) face reducerea specificată de această configurație pe simbolul de intrare aplicabil 'a', atunci analizorul va putea face cel puțin încă o acțiune de deplasare fără să întâlnească o eroare.

Mulțimea de simboluri aplicabile pentru fiecare configurație va fi numită mulțime de predicții pentru acea configurație. De acum înainte vom include mulțimea de predicții ca parte a unei configurații. Producția cu punctul undeva în partea dreaptă se va numi nucleu al configurației. De exemplu,

([ELEMENT -> 'a' .], {',', '$'})

este o configurație în G1 cu nucleul [ELEMENT -> 'a' .] și preducția {',', '$'}.

Vom descrie acum un algoritm care va calcula mulțimile de configurații valide pentru o gramatică în care configurațiile includ și predicțiile. Într-o mulțime, configurațiile apar în două moduri : prin calculul funcției GOTO și prin operația de închidere. Primul tip de calcul este foarte simplu : dacă avem o configurație de forma

([A -> . X], L),

unde X este un simbol al gramaticii și L este o mulțime de predicții, atunci, când vom face o operație GOTO cu X pentru această configurație, vom obține configurația

([A -> X . ], L)

(observăm că predicția este neschimbată).

Este oarecum mai greu de calculat predicțiile în operația de închidere. Să presupunem că există o configurație de forma ([A -> . B], L) într-o mulțime de configurații, unde B este un neterminal. Trebuie să adăugăm configurațiile de forma ([B -> . ], L') unde B -> este o producție din gramatică. Noua predicție L' va conține toate terminalele care reprezintă primul simbol al unei propoziții derivabile din orice secvență de forma B'a', unde 'a' este un simbol din L.

Dacă în timpul efectuării acestei construcții se observă că o mulțime conține configurații cu același nucleu, de exemplu ([A -> . ], L1) și ([A -> . ], L2) atunci aceste configurații sunt fuzionate și creează o singură configurație, de exemplu ([A -> . ], L1U L2).

Vom descrie acum un algoritm pentru construcția colecției canonice mai în detaliu, construind mulțimile valide de configurații pentru gramatica G1 . La început construim I0 începând cu configurația ([ACCEPT -> .LIST], {'$'}). Calculăm apoi închiderea acestei mulțimi. Cele două producții pentru LIST aduc două configurații :

([LIST -> . LIST ',' ELEMENT], {'$'})

([LIST -> . ELEMENT], {'$'})

Prima aduce, prin operația de închidere, încă două configurații :

([LIST -> . LIST ',' ELEMENT], {','})

([LIST -> . ELEMENT], {','})

deoarece primul terminal din orice secvență derivabilă din ',' ELEMENT'$' este întotdeauna ','. Deoarece configurațiile cu același nucleu fuzionează avem acum următoarele configurații în I0 :

([ACCEPT -> . LIST], {'$'})

([LIST -> . LIST ',' ELEMENT], {',', '$'})

([LIST -> . ELEMENT], {',', '$'})

Primele două dintre acestea nu mai aduc noi configurații când este aplicată operația de închidere. A treia aduce următoarele configurații :

([ELEMENT -> . 'a'], {',', '$'})

([ELEMENT -> . 'b'], {',', '$'})

aceste cinci configurații constituie I0 .

Acum vom calcula I2 = GOTO (I0, 'a'). Mai întâi adăugăm la I2 configurația :

([ELEMENT -> 'a' .], {',', '$'})

deoarece 'a' apare în dreapta punctului unei configurații din I0 . Operația de închidere nu mai adaugă alte configurații în I2 .

I2 conține o configurație finală. Predicția {',', '$'} ne spune pe ce simboluri de intrare este aplicabilă reducerea.

Întreaga colecție canonică va fi :

I0 : [ACCEPT -> . LIST], {'$'}

[LIST -> . LIST ',' ELEMENT], {',', '$'}

[LIST -> . ELEMENT], {',', '$'}

[ELEMENT -> . 'a'], {',', '$'}

[ELEMENT -> . 'b'], {',', '$'}

I1 : [ACCEPT -> LIST .], {'$'}

[LIST -> LIST . ',' ELEMENT], {',', '$'}

I2 : [LIST -> ELEMENT .], {',', '$'}

I3 : [ELEMENT -> 'a' .], {',', '$'}

I4 : [ELEMENT -> 'b' .], {',', '$'}

I5 : [LIST -> LIST ',' . ELEMENT], {',', '$'}

[ELEMENT -> . 'a'], {',', '$'}

[ELEMENT -> . 'b'], {',', '$'}

I6 : [LIST -> LIST ',' ELEMENT .], {',', '$'}

Cu toate că situația nu apare aici, dacă generăm o mulțime de configurații It astfel încât It acre aceeași mulțime de nuclee ca și o altă mulțime Iu generată deja, dar It Iu , atunci fuzionăm aceste două mulțimi formând o nouă mulțime I prin uniunea predicțiilor configurațiilor cu același nucleu. Apoi trebuie să calculăm GOTO (I, X) pentru toate simbolurile X ale gramaticii.

Predicțiile configurațiilor finale dau terminalele cu care se efectuează reducerile. Există probabilitatea să apară ambiguități în gramatică sau că gramatica să fie prea complexă pentru a permite construcția analizorului prin această tehnică; acest lucru cauzează apariția conflictelor în acțiunile analizorului. De exemplu, să presupunem că există o mulțime de configurații It în care 'a' produce o deplasare deoarece există GOTO (It, 'a'). De asemenea să mai presupunem că există o configurație finală ([A -> .], L) în It și că terminalul 'a' este în mulțimea de predicții L. Atunci nu avem de unde ști care acțiune este corectă în starea (t) când avem un 'a'; putem să ne deplasăm peste 'a' sau putem reduce prin producția A -> . Singura soluție este să raportăm un conflict shift-reduce (deplasare-reducere).

La fel, dacă există două reduceri posibile într-o anumită stare deoarece două configurații finale conîntr-o anumită stare deoarece două configurații finale coține același terminal în predicțiile lor, atunci nu putem spune care reducere trebuie să o facem; trebuie să raportăm un conflict reducere-reducere.

În loc să raportăm un conflict putem încerca să rezolvăm toate acțiunile conflictuale fie prin simulare paralelă fie prin backtracking.

O mulțime de configurații este consistentă sau adecvată dacă nu generează conflicte. O colecție de mulțimi de configurații este validă dacă toate mulțimile sale sunt consistente; de exemplu colecția construită anterior pentru G1 este validă.

Rezumăm acum procesul de construcție a tabelei de acțiuni și a tabelei goto :

(1) Fiind dată o gramatică G o îmbogățim cu o nouă producție de start, ACCEPT -> S, unde S este simbolul de start pentru G.

(2) Fie I mulțimea cu o configurație, ([ACCEPT -> . S], {'$'}). Fie I0 închiderea lui I.

(3) Fie C colecția curentă de mulțimi accesibile de configurații, conținând inițial doar pe I0 .

(4) Pentru fiecare I din C și pentru fiecare simbol X din gramatică calculăm I'=GOTO (I, X). Pot apărea trei cazuri :

a) I' = I'' pentru I'' existent în C. În acest caz nu facem nimic.

b) Dacă mulțimea de nuclee din I' este diferită de cele ale mulțimilor de congigurații existente deja în C, atunci adăugăm pe I' la C.

c) Dacă mulțimea de nuclee din I' este egală cu cea a unei mulțimi de configurații I'' deja existente în C dar I' I'' atunci fie I''' mulțimea de configurații de forma ([A->.],L1UL2) astfel încât ([A->.],L1) I' și ([A->.],L2)I''.

(5) Repetăm pasul (4) până când nu se mai adaugă mulțimi noi la C. C se numește colecția LALR(1) de mulțimi de configurații pentru G.

(6) Din C încercăm să construim tabela de acțiuni și tabela goto ca în secț. 6.3.

Dacă această tehnică reușește să producă o colecție canonică pentru o gramatică dată în care toate mulțimile de configurații sun consistente, atunci gramatică este numită gramatică LALR(1). Astfel de gramatici includ multe clase importante de gramatici, inclusiv gramatici LL(1), gramatici de precedență simplă și gramatici de precedența operatorilor.

Pasul (4) poate fi un destul de mare consumator de timp pentru a fi implementat. O abordare mai simplă dar mai puțin generală va funcționa după cum urmează. Fie FOLLOW (A) mulțimea de terminale care pot urma după neterminalul A într-o formă propozițională. Dacă A poate fi cel mai din dreapta simbo, al unei forme propoziționale, atunci '$' este inclus în FOLLOW (A). Putem calcula mulțimile de configurații fără predicții ca în secțiunea III.3.2. Atunci pentru fiecare configurație finală [A -> .] putem aprecia mulțimea de predicții L cu FOLLOW(A). (În general L este o submulțime a lui FOLLOW(A)). Colecția rezultată se numește simple LR(1). Cu toate că nu orice gramatică LALR(1) este simple LR(1), fiecare limbaj generat de o gramatică LALR(1) este generat și de o gramatică simple LR(1).

III.4. Analiza gramaticilor ambigue

Nu este de dorit să avem ambiguități nedectate în definiția unui limbaj de programare. Totuși, o gramatică ambiguă poate fi adesea folosită penrtu a specifica unele construcții ale limbajului mai ușor decât una neambiguă echivalentă. Vom vedea că putem construi analizoare mai eficiente direct din gramatici ambigue decât din gramatici echivalente neambigue. Dacă încercăm să construim un analizor pentru o gramatică ambiguă, tehnica de construire a analizorului LALR(1) va genera cel puțin o mulțime de configurații inconsistentă. Astfel, tehnica de generare a analizorului poate fi folosită pentru a detecta dacă o gramatică este neambiguă. Adică, dacă nu este generată nici o mulțime inconsistentă de configurații gramatica este în mod sigur neambiguă. Totuși, dacă apare o mulțime inconsistentă de configurații, atunci tot ce putem spune este că gramatica nu este LALR(1). Gramatica poate fi sau nu ambiguă.

Mulțimile inconsistente de configurații sunt folositoare în specificarea construcțiilor ambigue sau dificil de analizat dintr-o gramatică dată. De exemplu, o producție de forma A -> AA existentă într-o gramatică va face ca acea gramatică să fie ambiguă și va cauza apariția unui conflict între mulțimi conținând configurații cu nucleele [A -> AA .] și [A -> A . A]. Construcțiile care sunt destul de complexe încât să fie nevoie de mai multe simboluri în predicție duc de asemenea la conflicte în analiză. De exemplu, gramatica :

S -> A 'a'

A -> 'a' | ' '

este o gramatică LALR(2) dar nu este LALR(1).

Experimentele pe un generator de analizoare LALR(1) numit YACC la Bell Laboratories au arătat că câteva iterații cu generatorul sunt de obicei suficiente pentru a rezolva conflictele într-o colecție LALR(1) de mulțimi de configurații pentru un limbaj de programare rezonabil.

Exemplu 1) :

Fie gramatica ambiguă :

S -> 'if b then ' S

S -> 'if b then' S 'else' S

S -> 'a'

în care fiecare "else" va fi asociat cu ultimul "then" fără "else". Colecția LALR(1) de mulțimi de configurații pentru această gramatică este :

I0 : [ACCEPT -> . S], {'$'}

[S -> . 'if b then' S], {'$'}

[S -> . 'if b then' S 'else' S], {'$'}

[S -> . 'a'], {'$'}

I1 : [ACCEPT -> S .], {'$'}

I2 : [S -> 'if b then' . S], {'else', '$'}

[S -> 'if b then' . S 'else' S], {'else', '$'}

[S -> . 'if b then' S], {'else', '$'}

[S -> . 'if b then' S 'else' S], {'else', '$'}

[S -> . 'a'], {'else', '$'}

I3 : [S -> 'a' .], {'else', '$'}

I4 : [S -> 'if b then' S .], {'else', '$'}

[S -> 'if b then' S . 'else' S], {'else', '$'}

I5 : [S -> 'if b then' S 'else' . S], {'else', '$'}

[S -> . 'if b then' S], {'else', '$'}

[S -> . if b then' S 'else' S], {'else', '$'}

[S -> . 'a'], {'else', '$'}

I6 : [S -> 'if b then' S 'else' S .], {'else', '$'}

I4 conține un conflict deplasare-reducere. Pe intrarea "else", I4 spune că se poate face fie o deplasare în I5 fie o reducere prin producția S -> 'if b then' S. Dacă alegem deplasarea vom asocia "else" de la intrare cu ultimul "then" fără "else". Acest lucru este evident deoarece configurația cu nucleul [S -> 'if b then' S . 'else' S] din I4 provoacă o acțiune de deplasare.

Tabela de acțiuni completă, cu conflictul rezolvat, și tabela goto construită din această colecție de mulțimi de configurații sunt date mai jos :

Tabela cu acțiuni de analiză

0 : if (intrare = 'if b then') shift 2

if (intrare = 'a') shift 3

error

1 : if (intrare = '$') accept

error

2 : if (intrare = 'if b then') shift 2

if (intrare = 'a') shidt 3

error

3 : reduce by : S -> 'a'

4 : if (intrare = 'else') shift 5

reduce by : S -> 'if b then' S

5 : if (intrare = 'if b then') shift 2

if (intrare = 'a') shift 3

error

6 : reduce by : S -> 'if b then' S 'else' S

Tabela Goto

S : if (stare = 0) goto = 1

if (stare = 2) goto = 4

goto = 6

Fiind dată o gramatică ambiguă, cu regulile adecvate pentru rezolvarea ambiguităților, putem adesea obține un analizor mai mic din gramatica ambiguă decât din gramatica neambiguă echivalentă. Totuși, unele optimizări discutate în secțiunea următoare vor face analizorul pentru gramatica neambiguă la fel de mic cu cel pentru gramatica ambiguă.

Exemplul 2)

Fie gramatica G2 pentru expresii aritmetice :

E -> E '+' E

E -> E '*' E

E -> '(' E ')'

E -> 'a'

unde 'a' este simbolul dat oricărui identificator. Presupunând că '+' și '*' sunt ambele asociative de stânga ș '*' are o precedență mai mare decât '+', sunt două lucruri în neregulă cu această gramatică. Mai întâi, este ambiguă deoarece operanzii operatorilor binari '+' și '*' pot fi asociați în orice mod. De exemplu, 'a+a+a' poate fi analizată astfel :

sau astfel :

Prima analiză dă asociativitatea obișnuită, de la stânga la dreapta, iar cea de-a doua dă o asociativitate de la dreapta la stânga. Dacă rescriem gramatica ca G3 :

E -> E '+' T

E -> E '*' T

E -> T

T -> '(' E ')'

T -> 'a'

atunci eliminăm această ambiguitate impunând asociativitatea normală, de la stânga la dreapta, pentru '+' și '*'. Totuși, această nouă gramatică are încă un defect : '+' și '*' au aceeași precedență, deci o expresie de forma 'a+a*a' va fi evaluată ca (a+a)*a. Pentru a elimina acest lucru, trebuie ca mai departe să rescriem gramatica ca G4 :

E -> E '+' T

E -> T

T -> T '*' F

T -> F

F -> '(' E ')'

F -> 'a'

Acum putem să construim un analizor pentru G4 destul de ușor și să aflăm că avem 12 stări; dacă numărăm acțiunile de analiză din analizor (adică suma numărului de acțiuni de deplasare și de reducere din toate stările împreună cu acțiunile goto) observăm că analizorul pentru G4 are 35 de acțiuni.

În contrast, analizorul pentru G2 are doar 10 stări și 29 de acțiuni. O mare parte din avantaj vine din eliminarea neterminalelor T și F din G4 cât și din eliminarea producțiilor E -> T și T -> F.

Să discutăm rezoluția conflictelor din acțiunile de analiză din G2 mai în detaliu. Există două mulțimi de configurații în colecția LALR(1) de mulțimi de configurații pentru G2 care generează conflicte în analiză :

[E -> E . '+' E], {'+', '*', '(', ')', '$'}

[E -> E . '*' E], {'+', '*', '(', ')', '$'}

[E -> E '+' E .], {'+', '*', '(', ')', '$'}

și

[E -> E . '+' E], {'+', '*', '(', ')', '$'}

[E -> E . '*' E], {'+', '*', '(', ')', '$'}

[E -> E '*' E .], {'+', '*', '(', ')', '$'}

În ambele mulțimi conflictele deplasare-reducere apar pe cele două terminale '+' și '*'. De exemplu, în prima mulțime, pentru o intrare '+' putem genera fie o acțiune de deplasare fie una de reducere. Deoarece vrem ca '+' să fie asociativ de stânga, vom alege reducerea pe această intrare; o deplasare ar avea efectul întârzierii reducerii până când va fi citit mai mul din secvența de intrare și ar implica asociativitatea de dreapta. Pentru simbolul de intrare '*', totuși, dacă am face reducerea a ajunge să analizăm 'a+a*a' ca (a+a)*a; adică nu i-am dat lui '*' o precedență mai mare ca lui '+'. Astfel, este corect să ne deplasăm peste această intrare. Folosind raționamente similare, observăm că întotdeauna este corect să generăm o acțiune de reducere din a doua mulțime de configurații; pentru intrarea '*' acesta este rezultatul asociativității de stânga a lui '*', în timp ce pe intrarea '+' aceasta reflectă relația de precedență dintre '+' și '*'.

Încheiem această secțiune cu un exemplu despre cum poate fi aplicat acest raționament gramaticii noastre G1 . Am observat mai sus că gramatica :

LIST -> LIST ',' LIST

LIST -> 'a'

LIST -> 'b'

este ambiguă, dar această ambiguitate nu ar mai trebui să ne îngrijoreze. Presupunând că proiectantul limbajului vrea să trateze ',' ca un operator asociativ de stânga, putem genera un analizor care este mai mic și mai rapid decât analizorul pentru G1 generat în ultima secțiune. Acesta arată astfel :

Tabela de acțiuni de analiză

0 : if (intrare = 'a') shift 2

if (intrare = 'b') shift 3

error

1 : if (intrare = '$') accept

if (intrare = ',') shift 4

error

2 : reduce by : LIST -> 'a'

3 : reduce by : LIST -> 'b'

4 : if (intrare = 'a') shift 2

if (intrare = 'b') shift 3

error

5 : reduce by : LIST -> LIST ',' LIST

Tabela Goto

LIST : if (stare = 0) goto = 1

goto = 5

Să observăm că avem doar 14 acțiuni de analiză în loc de 16 câte aveam în celălalt analizor pentru G1 . În plus, arborii de derivare produși de acest analizor sunt mai mici deoarece nodurile corespunzătoare neterminalului ELEMENT nu mai există. Aceasta înseamnă că analizorul face mai puține acțiuni când analizează o secvență de intrare. Analiza gramaticilor ambigue este discutată mai în detaliu de Aho, Johnson și Ullman în "Deterministic parsing of ambiguous grammars".

III.5. Optimizarea analizoarelor LR

Există câteva moduri de a reduce dimensiunea și scăderea vitezei unui analizor LR(1) fără a afecta capacitatea sa de detectare a erorilor. În această secțiune vom da câteva transformări care pot fi aplicate tabelei de acțiuni și tabelei goto ale unui analizor LR(1) pentru a realiza acest lucru. Aceste transformări sunt simple dar eficiente în practică.

III.5.1 Fuziunea stărilor identice

Cea mai simplă și evidentă optimizare este să fuzionăm stările cu acțiuni de analiză comune. De exemplu, tabela de acțiuni pentru G1 dată în secțiunea III.2 conține acțiuni identice în stările (0) și (5). Astfel, este normal să reprezentăm acest lucru în analizor ca :

0 : 5 : if (intrare = 'a') shift 2

if (intrare = 'b') shift 3

error

În mod clar, comportarea analizorului LR(1) folosind această nouă tabelă de acțiuni este aceeași cu a analizorului folosind vechea tabelă.

III.5.2. Eliminarea stărilor care sunt în plus

O ușoară generalizare a transformării din secțiunea III.5.1. este de a elimina o stare ale cărei acțiuni de analiză sunt sufixe ale acțiunilor altor stări. În acest caz etichetăm începutul sufixului cu starea eliminată; de exemplu, dacă avem :

n : if (intrare = 'x') shift p

if (intrare = 'y') shift q

error

și

m : if (intrare = 'y') shift q

error

atunci putem elimina starea (m) adăugând eticheta în interiorul stării (n) :

n : if (intrare = 'x') shift p

m : if (intrare = 'y') shift q

error

Inversarea ordinii acestor instrucțiuni poate crește aplicabilitatea acestei optimizări.

III.5.3. Eliminarea reducerilor prin producții de tipul A ->X (rescrieri)

O rescriere este o producție de tipul A ->X unde A este un neterminal și X este un simbol din gramatică. Dacă această producție nu are vreo importanță în traducere, atunci spunem că producția este nesemnificativă din punct de vedere sintactic. O situație frecventă în care apar rescrieri apare când o gramatică este folosită pentru a descrie nivelele de precedență i asociativitatea operatorilor (vezi G4 din exemplul 2). Putem întotdeauna să facem un analizor LR să evite să facă aceste reduceri; făcând asta analizorul devine mai rapid și se reduce numărul de stări.

Vom da un exemplu pentru G1 care conține rescrierea LIST ->ELEMENT . Vom elimina reducerile prin această producție din analizorul pentru G1 din secț. III.2. Singura stare care cere o reducere prin această producție este starea (2). Mai mult, singura cale prin care putem ajunge în starea (2) este prin acțiunea goto :

ELEMENT : if (stare = 0) goto = 2

După ce analizorul face reducerea în starea (2) trece imediat la acțiunea goto :

LIST : goto = 1

moment în care starea curentă devine (1). Astfel, arborele cel mai din dreapta este etichetat cu starea (2) doar pentru o scurtă perioadă de timp; starea (2) reprezintă doar un pas în drumul spre starea (1). Putem elimina această reducere printr-o rescriere schimbând acțiunea goto pentru ELEMENT în :

ELEMENT : if (stare = 0) goto = 1

astefl încât trecem peste starea (2) direct în starea (1). Aflăm acum că nu putem ajunge niciodată în starea (2), prin nici o acțiune de analiză, astfel încât ea poate fi eliminată. Se dovedește că acțiunile goto pentru LIST și ELEMENT devin compatibile în acest moment; adică acțiunile nu diferă pentru această stare. Întotdeauna pot fuziona acțiuni goto compatibile pentru neterminale; analizorul rezultat are cu o stare mai puțin și cu o acțiune goto mai puțin.

Exemplul 3)

În continuare avem o reprezentare pentru tabela de acțiuni și pentru tabela goto pentru un analizor LR(1) al gramaticii G1 . Ele rezultă din tabelele din secțiunea III.2. aplicând fuziunea stărilor (secțiunea III.3.1.) și eliminând reducerile prin rescrieri.

Tabela de acțiuni

0 : 5 : if (intrare = 'a') shift 3

if (intrare = 'b') shift 4

error

1 : if (intrare = ',') shift 5

if (intrare = '$) accept

error

3 : reduce by : ELEMENT -> 'a'

4 : reduce by : ELEMENT -> 'b'

6 : reduce by : LIST -> LIST ',' ELEMENT

Tabela Goto

LIST : ELEMENT : if (stare = 0) goto = 1

goto = 6

Aceste tabele sunt identice cu acelea pentru versiunea ambiguă a lui G1 după ce au fost identificate stările egale. Ele diferă doar prin aceea că neterminalele LIST și ELEMENT au fuzionat în gramatica ambiguă în timp ce distincția este făcută nominal în tabelele de mai sus.

În general, pot exista un număr de stări care cer reduceri prin aceeași producție și pot exista alte acțiuni de analiză în stări care cer aceste reduceri. Nu este întotdeauna posibil să facem aceste modificări fără a mări numărul de stări; condițiile ce trebuie satisfăcute pentru a realiza acest lucru în mod profitabil sunt date în "A techinque for speeding up LR(k) parsers" , Aho & Ullman. Pentru scopurile noastre este destul să observăm că dacă o reducere printr-o rescriere A -> X este eliminată și dacă această reducere este generată de o singură mulțime de configurații ce con și dacă această reducere este generată de o singură mulțime de configurații ce conține o configurație cu nucleul [A -> X .] atunci această rescriere poate fi eliminată. Reiese că rescrierile care apar în reprezentarea precedenței operatorilor sau a asociativității pot fi întotdeauna eliminate; rezultatul este același ca și când am avea o gramatică ambiguă și am rezolva conflictele așa cum am spus în secțiunea III.3. Totuși, gramatica ambiguă generează analizorul imediat, fără a avea nevoie de acest algoritm de optimizare.

III.6. Recuperarea în urma erorilor

Un analizor LR bine făcut va anunța că a apărut o eroare din momentul în care nu se mai poate continua în mod corect cu intrarea deja citită. Din nefericire, nu este întotdeauna ușor să decidem ce ar trebui să facă analizorul când este detectată o eroare; în general, aceasta depinde de mediul în care operează analizorul. Orice schemă de recuperare în urma erorilor trebuie să fie realizată cu grijă, în concordanță cu analiza lexicală și fazele generării de cod ale compilării, din moment ce aceste operații au, în mod obișnuit, efecte secundare care trebuie să fie anulate înainte ca eroarea să poată fi considerată corectată. În plus, un compilator ar trebui să-și revină "frumos" în urma oricărei erori întâlnite astfel încât erorile următoare să fie și ele detectate.

Analizoarele LR pot adapta o gamă largă de strategii de recuperare în urma erorilor. În loc de fiecare intrare de eroare din fiecare stare, putem insera o rutină de corectare a erorii care este gata să facă niște acțiuni extraordinare pentru a corecta eroarea. Descrierea stării, așa cum este dată de mulțimea de configurații, de obicei oferă destule informații de context pentru a permite construcția unor rutine sofisticate de recuperare.

Vom exemplifica printr-o metodă simplă prin care recuperarea în urma erorilor poate fi introdusă în procesul de analiză. Această metodă este doar una din multe tehnici posibile. Introducem producții de recuperare de forma A -> error în gramatică pentru anumite neterminale. Aici, "error" este un terminal special. Aceste producții de recuperare vor introduce configurații cu nuclee de forma [A -> . error] în anumite stări. Când analizorul LR întâlnește o eroare, o poate anunța și poate înlocui simbolul curent de la intrare cu terminalul special "error". Atunci analizorul poate parcurge arbori din pădurea de analiză, câte unul odată, de la dreapta la stânga, până când starea curentă (starea corespunzătoare celui mai din dreapta arbore din pădurea de analiză) are o acțiune de deplasare pentru intrarea "error". Analizorul a ajuns acum într-o stare cu cel puțin o configurație de forma [A -> . error]. Analizorul poate efectua acțiunea de deplasare și să facă reducerea prin una din producțiile de recuperare, A ->error. (Dacă există mai multe astfel de producții, va trebui specificat un mod de alegere.) La reducere, analizorul poate efectua o acțiune "de mână" (hand-tailored) asociată cu această acțiune de eroare. O astfel de acțiune ar putea fi să se sară peste simbolurile de intrare până când se găsește un simbol 'a' astfel încât 'a' poate apărea fie ca ultimul simbol al unei secvențe generate de A fie ca primul simbol al unei secvențe ce poate urma lui A.

Mai sunt posibile și anumite acțiuni automate de recuperare în urma erorilor. De exemplu, producțiile de recuperare pot fi generate mecanic pentru orice set de neterminale dat. Analiza și recuperarea pot decurge ca mai sus doar că la reducerea printr-o astfel de producție analizorul poate trece automat peste simboluri de intrare până când găsește un simbol, să zicem 'a', asupra căruia poate face o acțiune valabilă de analiză, moment în care analiza normală continuă. Acest lucru corespunde presupunerii că s-a întâlnit o eroare în timp ce analizorul căuta o frază care să poată fi redusă la neterminalul A. Analizorul va presupune că trecând peste intrări până la 'a' va găsi o instanță a neterminalului A.

Anumite modele de recuperare în urma erorilor pot produce o avalanșă de mesaje de eroare. Pentru a evita succesiunea de astfel de mesaje dintr-o recuperare neadecvată, un analizor ar putea opri anunțarea erorilor consecință până când a apărut un anumit număr de acțiuni de deplasare de succes.

În prezent, nu există nici o soluție generală eficientă pentru problema recuperării în urma erorilor în compilare. Se văd greșeli în orice abordare uniformă, chiar și în cea de mai sus. Mai mult, succesul oricărei abordări poate varia considerabil de la aplicație la aplicație. Dacă un limbaj este proiectat logic și este bine specificat va fi bună și recuperarea automată.

CAPTIOLUL IV

Un analizor LALR(1)

IV.1.Specificații

Pnetru a exemplifica cele discutate în capitolele precedente am realizat un analizor LALR(1). Un analizor LALR(1) este un tot un analizor din clasa analizoarelor LR(k), cu k = 1, dar el aduce unele îmbunătățiri în ceea ce privește spațiul de memorie și timpul necesare în analiză. Acest lucru se datorează faptului că, la construcția unui astfel de analizor, stările care conțin configurații cu aceleași nuclee fuzionează și astfel numărul de stări va fi mai mic.

Analizorul care va fi prezentat în continuare funcționează pentru o gramatică LALR(1) (a cărei definiție am dat-o în secțiunea III.3.4.), care are următoarele producții :

<CompilationUnit> -> ";"

<ClassDeclaration> -> <Modifiers> "class" <Identifier> <ClassBody>

<ClassDeclaration> -> "class" <Identifier> <ClassBody>

<ClassBody> -> "{" <ClassBodyDeclarations> "}"

<ClassBody> -> "{" "}"

<MethodDeclarator> -> <Identifier> "(" ")"

<MethodDeclarator> -> <MethodDeclarator> "[" "]"

<MethodBody> -> "{" "}"

<MethodBody> -> ";"

<InterfaceDeclaration> -> <Modifiers> "interface" <Identifier> <InterfaceBody>

<InterfaceDeclaration> -> "interface" <Identifier> <InterfaceBody>

<InterfaceBody> -> "{" <InterfaceMemberDeclaration> "}"

<InterfaceBody> -> "{" "}"

<InterfaceMemberDeclaration> -> <MethodHeader> ";"

<Modifier> -> "public"

<Type> -> "boolean"

<IntegralType> -> "byte"

<FloatingPointType> -> "float"

După cum poate s-a observat este vorba despre o "mini-gramatică" pentru limbajul java. Așadar, dacă avem un fișier care conține un mic program scris în acest subset de java, analizorul nostru va putea spune dacă programul este corect. Dacă da, va pune într-un fișier cu numele "rexlex.txt" rezultatele analizei lexicale, adică codificarea atomilor lexicali întâlniți în program, tabela de simboluri și forma internă a programului, iar într-un fisier cu numele "iesire.txt" va pune rezultatele analizei lexicale. Ce înseamnă toate acestea? Fiecare atom lexical întâlnit în fișierul de analizat, și dacă este constantă i se atribuie codul 1, dacă este identificator i se atribuie codul 2, iar dacă este cuvânt rezervat java, separator sau operator i se va atribui un cod unic. Identificatorii sunt trecuți în tabela de simboluri și i se atribuie fiecăruia un index aleator in tabela de simboluri. Dacă pentru un identificator se generează un index care a mai fost generat pentru un alt identificator se caută următorul index la care tabela nu conține nimic. Forma internă a programului este o tabelă care conține toti atomii ce apar în program, în ordinea apariției lor și reprezentați prin codurile lor din tabela de codificare, dacă sunt cuvinte rezervate, separatori sau identificatori, sau prin indecșii lor din tabela de simboluri dacă sunt identificatori.

Rezultatele analizei sintactice constă în următoarele : se specifică dacă programul a fost corect, dacă da se dau producțiile folosite în derivare, apoi se dă colecția canonică, tabela cu acțiunile de analiză și tabela cu acțiunile goto.

IV.2. Structura analizorului

Pentru a analiza din punct de vedere sintactic un fisier dat avem nevoie mai întâi de un analizor lexical. Acesta împarte în tokeni fisierul de analizat și determină natura fiecărui token (constantă numerică sau șir de caractere, cuvânt rezervat, identificator, separator sau operator). Pentru aceasta am construit o clasa "Analizor" care are următoarea structură :

import java.io.*;

import java.util.*;

public class Analizor

{

String mToken; //atomul curent

String mType; //tipul atomului curent

BufferedInputStream mIn; //stream-ul de intrare

LinkedList mErrors; //lista cu erorile lexicale

LinkedList mST; //tabela de simboluri

LinkedList mIFT; //forma internă a programului

public LexicalAnalyzeResult mResult; // rez. analizei lexicale

//constructorul

public Analizor();

// funcția care face analiza lexicală

public void analyze(String fisIn, String fisOut);

// funcția care obține tabela cu codificarea atomilor

LinkedList GetCodeMappingTable();

// funcție care obține codul unui atom din tabela de mai sus

long GetTokenCode(String token);

// funcția care obține tabela de simboluri

LinkedList GetSTIndex(String token);

// Funcția care adaugă un atom în forma internă a programului

void AddToIFT(long tokenCode,long stI1,long stI2);

// funcția care tipărește rezultatele

void tipResults(BufferedOutputStream ost);

// funcția care se execută când apare o eroare

void Error(String token,int nr);

}

Mai sus nu am prezentat toate funcțiile ce apar în clasa “Analizor” deoarece restul sunt funcții care sunt folosite de cele rămase, și nu sunt foarte relevante. Se poate observa ca există câteva tipuri definite care ne ajută la mai buna reprezentare a informației. Acestea ar fi, până în acest moment următoarele :

CodeMappingRecord care reprezintă o înregistrare din tabela de codificare a atomilor, cu următoarele date :

– mToken – atomul ca String

– mCode – codul asociat

LexicalAnalyzeResult care este o clasă cu următorii membrii :

– mIntForm – care reține forma internă a programului

– mSymbols – care reține tabela de simboluri

– mCodemapping – care reține codificarea atomilor

– mErrors – care reține erorile apărute

Deci, prin apelul metodei “analyze()” al acestei clase, “Analizor” se va efectua analiza lexicală al cărei rezultat, memorat în membrul mResult, va fi folosit de analizorul sintactic.

Deoarece gramatica pe care urmează să o folosească analizorul sintactic este dată într-un fișier text, într-o formă specială, trebuie să avem o modalitate de a citi acest fișier și de a pune gramatica într-o formă adecvată, ușor de accesat și de folosit. De aceea am implementat o clasă “Grammar” care face tocmai acest lucru; adică citește fișierul respectiv și de acolo construiește mulțimea de producții, mulțimea de neterminale și mulțimea de terminale. Structura ei este următoarea (cu aceeași mențiune ca mai sus, că nu am dat chiar toate funcțiile prezente ci doar cele importante) :

import java.io.*;

import java.util.*;

public class Grammar implements Serializable

{

//lista cu producțiile gramaticii

LinkedList mProd;

//obiectul format din fișierul de unde se citește gramatica

transient BufferedReader mInGram;

// lista de netermianle din gramatică

TreeSet mNeterm;

// lista de terminale din gramatică

TreeSet mTerm;

//constructorul implicit

Grammar();

// alt constructor

Grammar(String numeFisGram,LexicalAnalyzeResult res);

}

Observăm că această clasă este foarte simplă, neconținând decât patru membri și doi constructori. Acest lucru se datorează faptului că tot ce este de făcut se face în constructori. Clasa "Grammar" implementează interfața Serializable deoarece, dacă folosim aceeași gramatică pentru a analiza mai multe fișiere, este inutil să citim și să construim de fiecare dată gramatica din fișierul text. Ar fi o mare pierdere de timp. O clasă care implementează această interfață poate fi salvată ca obiect într-un fișier deschis ca ObjectOutputStream, prin apelul metodei writeObject de unde poate fi citită foarte ușor mai târziu, prin apelul metodei readObject. Din cauză ca construcția se poate face în două moduri (prin citire dintr-un fișier text sau dintr-un ObjectInputStream) am implementat doi constructori pentru clasa "Grammar". Constructorul cu parametrii numeFisGram și res construiește gramatica citind-o din fișierul text cu numele numeFisGram și folosindu-se de rezultatul analizei lexicale, res. După ce s-a construit gramatica se va salva o formă serializată a ei.Constructorul fără parametri se apelează doar atunci când se constată că fișierul care conține gramatica nu s-a modificat de la ultima execuție a programului pe acea gramatică și singurul lucru pe care-l face este să citească forma serializată a gramaticii.

Iarăși am folosit câteva tipuri pentru a structura mai bine programul. Acestea sunt după cum urmează :

Element – clasă care reprezintă un simbol al gramaticii, terminal sau neterminal și are următorii membrii:

– mType – tipul simbolului (terminal sau neterminal)

– mCode – codul asociat

Neterm – clasă care reprezintă un neterminal, cu următorii membri :

– mToken – numele neterminalului

– mCode – codul asociat neterminalului

Productie – clasă care reprezintă o producție, ce are membrii:

// partea stângă a producției

Element mLeftSide;

// partea dreaptă a producției

LinkedList mRightSide;

// o referință la gramatica construită mai sus

transient Grammar mGram;

Productie(); // constructorul implicit

// construiește o producție dintr-un string, bazându-se // pe rezultatele analizei lexicale și pe informațiile // deja existente în gramatică

Productie(LinkedList pr, LexicalAnalyzeResult res,Grammar gr);

// verifică dacă producția nu are parte dreaptă

boolean HasNoRightSide();

// verifică dacă producția are parte stângă

boolean HasLeftSide(Element el);

// tipărește o producție într-un fișier

void tiparire(BufferedOutputStream out);

După ce am construit și gramatica putem trece la analiza sintactică propriu-zisă. Aceasta se realizează cu ajutorul clasei "SyntAnalyzer" care arată în felul următor :

import java.io.*;

import java.util.*;

public class SyntAnalyzer

{

Grammar mGram; // referință la gramatica construită

BufferedOutputStream mOut; //stream-ul de ieșire

LexicalAnalyzeResult mResLex; //rezultatele analizei lexicale

LinkedList mColCan; // colecția canonică

LinkedList mColMerged; // colecția canonică cu stări fuzionate

LinkedList mActionTable; // tabela de acțiuni de analiză

LinkedList mGotoTable; //tabela goto

LinkedList mFuziuni; //schemă cu fuziunile dintre stări

// constructorul implicit

SyntAnalyzer();

// alt constructor

SyntAnalyzer(String numeFisGram, String numeFisIes, LexicalAnalyzeResult reslex);

// funcție care determină acțiunea care se poate realiza din //starea (s) având la intrare elementul el

Action action(long s,Element el);

// funcție care determină acțiunea goto realizată din starea //(s) cu elementul el

Goto GetGoto(long s, Element el);

// obține starea asociată mulțimii de configurații s

long GetStateInd(TreeSet s);

// obține mulțimea de configurații pentru care s-a asociat //starea s

TreeSet GetState(long st);

// funcția care construiește tabela goto

void GoToTableConstruction();

// funcția care constriește tabela cu acțiunile de analiză

void ActionTableConstruction();

// funcția care fuzionează două stări

boolean Merge(TreeSet I1, TreeSet I2);

// funcția care realizează fuziunea tuturor stărilor

void MergeStates();

// funcția care ne spune ce mulțime de configurații obținem //dacă efectuăm o acțiune goto pe mulțimea I cu elementul X

TreeSet GoToFunction(TreeSet I, Element X);

// funcție care realizează închiderea tranzitivă a mulțimii de // configurații I

TreeSet closure(TreeSet I);

// funcție care determină primul terminal care apare prin //derivarea mulțimii de elemente mul

LinkedList first(LinkedList mul);

// funcția care scrie în stream-ul mOut o parte din //rezultatele analizei lexicale, adică tabela de acțiuni și //tabela goto

void WriteToStream();

// funcția care construiește colecția cononică

void collection();

// funcția care realizează analiza sintactică proppriu-zisă

void analyze();

}

În continuare vom descrie modul în care este realizat acest analizor, explicând ce fac funcțiile mai importante. În constructorul cu parametrii numeFisGram, numeFisIes și reslex se fac unele inițializări și se constriește gramatica după cum este cazul : direct din fișierul text cu numele numeFisGram sau din fișierul care conține forma serializată (având numele numeFistGram și extensia ".ser").

Prin apelul funcției "analyze()" va începe analiza sintactică. Primul pas este construcția colecției canonice, cu ajutorul funcției "collection()" care va construi o primă variantă a acestei colecții ce va fi memorată în variabila membră mColCan. Am mai explicat în secțiunea III.3.2. cum se construiește colecția canonică așa că nu mai intrăm în detalii aici, doar vom face câteva precizări. Mulțimea de la care se pornește în construcție este cea formată din configurația

([SPrim -> . CompilationUnit], {'$'})

unde CompilationUnit este simbolul unde start pentru gramatica noastră iar SPrim este neterminalul cu care am îmbogățit gramatica. Acestei mulțimi i se aplică funcția closure() care am explicat-o de asemenea în explicațiile din capitolele anterioare. Implementările tuturor funcțiilor de care am pomenit și vom pomeni de acum înainte le găsim în anexele de la finalul acestei lucrări. În final vom avea în colecția canonică 80 de mulțimi de configurații.

Datorită optimizărilor care se vor face în continuare numărul de stări se va reduce considerabil și deci spațiul de memorie necesar se va micșora. Una din optimizări este fuziunea stărilor ale căror configurații au aceleași nuclee, optimizare caracteristică analizoarelor LALR(1). Fuziunea se realizează aici cu ajutorul funcției MergeStates(), care pentru fiecare pereche de stări din colecția canonică mColCan va apela funcția Merge care primește ca parametri aceste două stări, și care va realiza fuziunea dacă este cazul și va adăuga noua stare în colecția canonică cu stări fuzionate mColMerged, iar dacă nu nu va modifica cu nimic aceste stări și le va adăuga în mColMerged. După ce s-a executat și funcția MergeStates(), noua colecție canonică, mColMerged va avea doar 61 de mulțimi de configurații.

Acum putem trece la construcția tabelei cu acțiunile de analiză, care se va realiza prin funcția ActionTableConstruction(), care pentru fiecare mulțime de configurații din mColMerged și pentru fiecare terminal din mulțimea simbolurilor gramaticii determină acțiunea coerspunzătoare (shift, reduce, accept sau error) în maniera descrisă în secțiunea III.2.. și pune rezultatele în mActionTable.

Apoi se construiește tabela goto cu ajutorul funcției GotoTableConstruction() care, pentru fiecare mulțime de configurații (având asociată o stare) din mColMerged și pentru fiecare simbol din gramatică (terminal sau neterminal) determină starea în care se trece din acea stare și cu simbolul respectiv (acest lucru se realizează cu ajutorul funcției GotoFunction ( care are ca parametri o mulțime de configurații și un simbol al gramaticii). Rezultatele vor fi puse în mGotoTable.

Având aceste construcții putem înainta încă un pas în analiză, adică să începem să citim intrarea. Simbolurile de la intrare le punem într-o stivă, pe care o vom numi stiva de intrare iar configurațiile cu care lucrăm le vom pune în altă stivă pe care o vom numi stiva de lucru. Punem ca delimitator de sfârșit al secvenței de intrare terminalul special '$'. Acesta va fi cel mai de jos element din stiva de intrare. De asemenea vom folosi '$' pentru a determina când s-a golit stiva de lucru, deci el va fi și în această stivă cel mai de jos element.

Pentru configurația de lucru am implementat o clasă WorkItem care are membrii : mElem și mState care reprezintă, pentru configurația de lucru curentă, ultimul element citit de la intrare și starea curentă în care se află analizorul.

Acum se va porni din starea inițială :

I0 = { [ <SPrim> -> . <CompilationUnit> , $ ]

[ <CompilationUnit> -> . <ClassDeclaration> , $ ]

[ <CompilationUnit> -> . <InterfaceDeclaration> , $ ]

[ <CompilationUnit> -> . ; , $ ]

[ <ClassDeclaration> -> . <Modifiers> class <identifier> <ClassBody> , $ ]

[ <ClassDeclaration> -> . class <identifier> <ClassBody> , $ ]

[ <InterfaceDeclaration> -> . <Modifiers> interface <identifier> <InterfaceBody> , $ ]

[ <InterfaceDeclaration> -> . interface <identifier> <InterfaceBody> , $ ]

[ <Modifiers> -> . <Modifier> , class byte float boolean ]

[ <Modifiers> -> . <Modifier> <Modifiers> , class byte float boolean ]

[ <Modifier> -> . public , class byte ] }

se va citi un simbol din stiva de intrare și se va determina acțiunea de analiză corespunzătoare. Procesul se va derula în mainera descrisă în secțiunea III.1. până când atât stiva de intrare cât și stiva de lucru vor conține doar terminalul special '$' sau intervine o eroare. În primul caz programul va fi corect și analizorul va anunța acest lucru, dând și producțiile folosite în derivare, iar în al doilea caz analizorul va anunța eroarea cu câteva informații referitoare la natura ei.

Pentru a vedea mai bine cum funcționează acest analizor vom da în continuare două exemple de teste, unul cu un program corect și un altul cu un program incorect. Incorectitudinea unui program scris într-un limbaj generat de o gramatică dată poate consta fie in prezența unor erori lexicale, care de cele mai multe ori vor atrage după ele erori sintactice, fie in prezența doar a unor erori sintactice.

IV.3. Date de test

Programul care reprezintă analizorul nostru se lansează în execuție în felul următor. Fiindcă este un program java trebuie să avem instalat jdk1.3. Din linia de comandă se rulează programul prin execuția comenzii "java princ" ("princ" fiind numele gramului principal). Mai întâi ne va apărea o fereastră de genul :

După cum se vede fereastra conține o bară de meniuri din care ne putem alege acțiunea pe care dorim să o executăm. Pentru început avem nevoie de un fișier de intrare, pe care să-l analizăm. Îl putem crea, alegând opțiunea "New" din meniul "File" sau putem deschide unul deja existent. Pentru aceasta alegem opțiunea "Open" din meniul "File" :

Astfel, în jumătatea de sus a ferestrei ne va apărea conțiunutul fișierului selectat. De exemplu,dacă dorim să analizăm fișierul "intrare.txt" vom alege din caseta de dialog apărută în urma alegerii opțiunii "Open" fișierul cu acest nume și ni se va deschide fișierul cu următorul conținut :

public class a {

public void main (){

}

Acesta reprezintă programul de analizat. De această dată este vorba despre un program corect, lucru pe care îl vom vedea mai departe. Din acest moment putem face modificări la acest fișier, modificări care pot fi salvate alegând opțiunea "Save" din același meniu "File". După ce am decis care este forma fișierului de intrare putem alege gramatica pe care o vom folosi în analiză, alegând din meniul "Analyze" opțiunea "Choose Grammar". Implicit aceasta este "Gram2.txt" și are următorul conținut :

<CompilationUnit> ::= ";"

<ClassDeclaration> ::= <Modifiers> "class" <Identifier> <ClassBody>

<ClassDeclaration> ::= "class" <Identifier> <ClassBody>

<ClassBody> ::= "{" <ClassBodyDeclarations> "}"

<ClassBody> ::= "{" "}"

<MethodDeclarator> ::= <Identifier> "(" ")"

<MethodDeclarator> ::= <MethodDeclarator> "[" "]"

<MethodBody> ::= "{" "}"

<MethodBody> ::= ";"

<InterfaceDeclaration> ::= <Modifiers> "interface" <Identifier> <InterfaceBody>

<InterfaceDeclaration> ::= "interface" <Identifier> <InterfaceBody>

<InterfaceBody> ::= "{" <InterfaceMemberDeclaration> "}"

<InterfaceBody> ::= "{" "}"

<InterfaceMemberDeclaration> ::= <MethodHeader> ";"

<Modifier> ::= "public"

<Type> ::= "boolean"

<IntegralType> ::= "byte"

<FloatingPointType> ::= "float"

După ce am ales și gramatica putem trece la analiza propriu zisă, alegând opțiunea "Analyze" din același meniu. În acest moment începe analiza fișierului cu gramatica aleasă (în cazul nostru, fisierul de intrare este "intrare.txt" iar gramatica folosită în analiză este "Gram2.txt"). Cand s-a terminat de analizat fișierul, apare un mesaj de înștiințare iar în partea de jos a ferestrei apar erorile lexicale și sintactice survenite :

Dacă dorim să vedem mai în detaliu rezultatele analizei sintactice putem alege din meniul "Results" una din opțiunile "Lexical Results" sau "Syntactical Results". Dacă facem acest lucru fișierul ales (cel cu rezultatele analizei lexicale sau, respectiv, cel cu rezultatele analizei sintactice) va fi deschis și afișat în partea de sus a ferestrei aplicației. În exemplul pe care l-am ales rezultatele ar fi cele date în anexa ???? iar ferestrele aplicației ar arăta în felul următor:

După ce am văzut aceste rezultate putem să ne întoarcem dacă dorim la fișierul pe care l-am analizat dacă alegem opțiunea "Back to file" din meniul "Go".

Dacă dorim, acum putem crea un nou fișier de intrare sau sa-l modificăm pe cel curent. De exemplu să modificăm fișierul curent după cum urmează :

public class a {

public void void main (){

}

Acum, acest fișier conține o eroare. Dacă lăsăm aceeași gramatică și pornim acțiunea de analiză, erorile care apar vor fi arătate în partea de jos a ferestrei :

iar rezultatele analizei lexicale, respectiv sintactice vor fi cele din anexa ????. Deci în acest caz, programul nu va fi acceptat ca fiind corect.

Dacă nu mai avem alte fișiere de analizat, putem părăsi aplicația selectând opțiunea "Exit" din meniul "File".

CAPITOLUL V

Concluzii

Analizoarele LR aparțin clasei de algoritmi de analiză de tip deplasează-reduce (shift-reduce). Acestea sunt analizoare ce operează citind intrarea de la stânga la dreapta, deplasând simbolurile de la intrare într-o stivă push-down până când forma propozițională de dreapta curentă este în vârful stivei; în acest moment manipulatorul este redus. Acest proces se continuă fie până când a fost citită toată intrarea și stiva conține doar simbolul de start, fie până s-a întâlnit o eroare.

În anii 1960 s-au găsit câțiva algoritmi de tip deplasare-reducere pentru subclase variate de gramatici independente de context. Gramaticile de precedența operatorilor, gramaticile de precedență simplă și gramaticile de precedență slabă sunt unele din aceste subclase. Definițiile acestor clase de gramatici și algoritmii asociați sunt discutate în detaliu în "The Theory of Parsing, Translation and Compiling", volumul I, "Parsing" de Aho and Ullman.

În 1965 Knuth a definit o clasă de gramatici pe care le-am numit gramatici LR(k). Acestea sunt gramatici independente de context care pot fi analizate de jos în sus folosind un automat push-down determinist cu k simboluri în predicție pentru a determina acțiunile de analiză de deplasare-reducere. Această clasă de gramatici include toate celelalte gramatici analizabile prin deplasare-reducere și admite o procedură de analiză cel puțin la fel de eficientă ca și algoritmii de analiză dați pentru acestea.

În această lucrare Knuth a evidențiat o metodă pentru construirea unui analizor LR pentru o gramatică LR. Totuși, acest algoritm construiește analizoare prea mari pentru uz practic. Câțiva ani mai târziu, după 1969, Korenjak și în special DeRemer au reușit să modifice substanțial algoritmul original al lui Knuth, construind o procedură pentru a realiza analizoare de dimensiune practică. Un progres substanțial a fost făcut datorită îmbunătățirii dimensiunilor și performanței analizoarelor LR.

Poate cel mai mare avantaj al analizei LR este că analizoarele mici și rapide pot fi generate mecanic pentru o gamă largă de gramatici independente de context, care include to, care include toți algoritmii de analiză prin backtracking. În plus, analizoarele LR sunt capabile să detecteze erori de sintaxă la prima apariție într-o citire de la stânga la dreapta a secvenței de intrare, proprietate care nu caracterizează mulți alți algoritmi.

La fel cum putem analiza construind un arbore de derivare pentru o secvență de intrare de jos în sus (de la frunze spre rădăcină) putem analiza și de sus în jos, construind arborele de derivare de la rădăcină înspre frunze. O sublclasă adecvată a gramaticilor LR poate fi analizată deterministic de sus în jos. Acestea sunt gramaticile LL studiate pentru prima dată de Lewis și Stearns. Analizoarele LL sunt și ele eficiente și au o capacitate mare de detectare a erorilor. În plus, un analizor LL necesită mai puțină optimizare inițială pentru a fi de dimensiune practică. Totuși, cel mai serios dezavantaj al tehnicii LL este că gramaticile LL tind să fie nenaturale și greu de construit. Mai mult, există limbaje LR care nu au o gramatică LL.

Aceste considerații, împreună cu experiența practică cu un sistem automat pentru generarea analizoarelor bazat pe principiile expuse în această lucrare, ne face să credem că analiza LR este o unealtă importantă și practică pentru realizarea unui compilator.

Anexa 1

Clasele ajutătoare

import java.util.*;

import java.io.*;

// reprezintă o înregistare din tabela de codificare a atomilor

class CodeMappingRecord

{

String mToken;

long mCode;

public CodeMappingRecord(String token, long code){

mToken=token;

mCode=code;

}

};

// reprezintă o înregistrare din forma internă a programului

class InternalFormRecord{

long mTokenCode;

long mSymbolIndex1;

long mSymbolIndex2;

public InternalFormRecord(){

}

InternalFormRecord(long t, long s1, long s2){

mTokenCode=t;

mSymbolIndex1=s1;

mSymbolIndex2=s2;

}

};

// reprezintă o înregistrare din tabela de simboluri

class SymbolTableRecord{

boolean mUsed;

String mSymbol;

String mType;

SymbolTableRecord mNext;

public SymbolTableRecord(){

mUsed=false;

mSymbol=new String("");

mType= new String("");

mNext=null;

}

};

// reprezintă rezultatele analizei lexicale

class LexicalAnalyzeResult{

LinkedList mIntForm; //InternalFormRecord

LinkedList mSymbols; //SymbolTableRecord

LinkedList mCodemapping; //CodeMappingRecord

LinkedList mErrors;

public LexicalAnalyzeResult(){

mIntForm=new LinkedList();

mSymbols=new LinkedList();

mCodemapping=new LinkedList();

mErrors=new LinkedList();

}

public String getTermByCode(long cod){

ListIterator it = mCodemapping.listIterator(0);

while(it.hasNext()){

CodeMappingRecord rec=(CodeMappingRecord)it.next();

if (rec.mCode==cod)

return rec.mToken;

}

return "";

}

};

// reprezintă un element

class Element implements Comparable, Serializable{

char mType;

long mCode;

Element(){

}

public boolean isEqual(Element e){

if (e.mType==mType && e.mCode==mCode)

return true;

return false;

}

public boolean equals(Object obj){

Element e=(Element)obj;

if (e.mType==mType && e.mCode==mCode)

return true;

return false;

}

public int compareTo(Object obj) throws ClassCastException{

Element e1=(Element)obj;

if (mType=='T' && e1.mType=='N')

return -1;

if (mType=='N' && e1.mType=='T')

return 1;

if (mCode<e1.mCode)

return -1;

if (mCode>e1.mCode)

return 1;

return 0;

}

};

// reprezintă un neterminal

class Neterm implements Comparable, Serializable

{

String mToken;

long mCode;

Neterm(){

mToken="";

mCode=-1;

}

public int compareTo(Object n) throws ClassCastException{

return mToken.compareTo(((Neterm)n).mToken);

}

};

// reprezintă un element de analiză

class ElementOfAnalyze implements Comparable{

long mNrProd; // indicele productiei in sirul de productii

long mIndPoint; // pozitia punctului la un moment dat

LinkedList mPrediction; // predictii; lista de Element

public ElementOfAnalyze(){

mPrediction=new LinkedList();

}

public int compareTo(Object obj) throws ClassCastException{

ElementOfAnalyze e=(ElementOfAnalyze)obj;

if (mNrProd<e.mNrProd)

return -1;

if (mNrProd>e.mNrProd)

return 1;

if (mIndPoint<e.mIndPoint)

return -1;

if (mIndPoint>e.mIndPoint)

return 1;

if (mPrediction.size()<e.mPrediction.size())

return -1;

if (mPrediction.size()>e.mPrediction.size())

return 1;

ListIterator i=mPrediction.listIterator(0);

while(i.hasNext()){

Element el=(Element)i.next();

if (!e.mPrediction.contains(el))

return -1;

}

return 0;

}

boolean hasSameCore(ElementOfAnalyze eoa){

if(mNrProd==eoa.mNrProd && mIndPoint==eoa.mIndPoint)

return true;

return false;

}

public boolean isEqual(ElementOfAnalyze e){

if (mNrProd!=e.mNrProd || mIndPoint!=e.mIndPoint || mPrediction.size()!=e.mPrediction.size())

return false;

ListIterator i=mPrediction.listIterator(0);

while(i.hasNext()){

Element el=(Element)i.next();

if (!e.mPrediction.contains(el))

return false;

}

i=e.mPrediction.listIterator(0);

while(i.hasNext()){

Element el=(Element)i.next();

if (!mPrediction.contains(el))

return false;

}

return true;

}

};

// reprezintă o acțiune de analiză

class Action{

long mState;

Element mTerminal;

String mAction;

long mProdRed;

public Action(){

mTerminal=new Element();

}

};

// reprezintă o acțiune goto

class Goto{

long mState;

Element mElem;

long mGoto;

public Goto(){

mElem=new Element();

}

};

// reprezintă o configurație de lucru

class WorkItem{

Element mElem;

long mState;

public WorkItem(){

mElem=new Element();

}

};

// reprezintă o configurație

class Configuration{

LinkedList mWorkStack; //WorkItem

LinkedList mInputStack; //InternalFormRecord

LinkedList mUsedProductions; //long

public Configuration(){

mWorkStack=new LinkedList();

mInputStack=new LinkedList();

mUsedProductions=new LinkedList();

}

};

Anexa 2

Clasa "Analizor" (lexical)

import java.io.*;

import java.util.*;

public class Analizor

{

String mToken;

String mType;

BufferedInputStream mIn;

LinkedList mErrors; //String

LinkedList mST; //SymbolTableRecord

LinkedList mIFT; //InternalFormRecord

public LexicalAnalyzeResult mResult;

// constructorul implicit

public Analizor(){

mErrors=new LinkedList();

mST=new LinkedList();

mIFT=new LinkedList();

mResult=new LexicalAnalyzeResult();

}

void reset(){

mToken="";

}

public void analyze(String fisIn, String fisOut){

for (int i=0; i<100; i++){

mST.add(new SymbolTableRecord());

}

try{

mIn=new BufferedInputStream(new FileInputStream(fisIn),1000);//IStream(fisIn);

while(mIn.available()>0){

reset();

readToken();

}

} catch(IOException e){

String t="";

Error(t,2);

}

mResult.mCodemapping=GetCodeMappingTable();

mResult.mSymbols=mST;

mResult.mIntForm=mIFT;

mResult.mErrors=mErrors;

try{

BufferedOutputStream mOut=new BufferedOutputStream(new FileOutputStream(fisOut));

tipResults(mOut);

mOut.close();

mIn.close();

}

catch(IOException e){

System.out.println(e.toString());

}

void readToken(){

try{

char c=(char)mIn.read();

if (c=='/'){

char c1=(char)mIn.read();

if (c1=='/'){

readLineComment();

return;

}

else

if (c1=='*'){

readBlockComment();

return;

}

if (c=='\''){

readChar();

return;

}

if(c=='\"'){

readString();

return;

}

if (isAlpha(c) || c=='_'){

readIdentifierOrKeyword(c);

return;

}

if (isDigit(c)){ //isDigitN–daca este cifra diferita de zero

System.out.println("Se incearca citirea unui numar!");

readNumeric(c);

return;

}

String str="";

str+=c;

if (isOperator(str)){

readOperator(c);

return;

}

str="";

str+=c;

if (isSeparator(str)){

readSeparator(c);

return;

}

if(mToken != ""){

while((c!=' ') || (c!='\n') || (c!='\t')){

mToken+=c;

c=(char)mIn.read();

}

Error(mToken,0);

}

}catch(IOException e){

System.out.println(e.toString());

}

void readLineComment(){

mType="LineComment";

mToken="//";

try{

char car=(char)mIn.read();

do{

mToken=mToken+car;

car=(char)mIn.read();

}

while(car!='\n');

}

catch(IOException e){

System.out.println(e.toString());

}

return;

}

void readBlockComment(){

mType="BlockComment";

try{

mToken="/*";

char car1=(char)mIn.read();

char car2=(char)mIn.read();

while(car1!='*' && car2!='/'){

mToken+=car1;

car1=car2;

car2=(char)mIn.read();

}

mToken+=(char)mIn.read();

}catch(IOException e){

System.out.println(e.toString());

}

return;

}

void readChar(){

mType="Character";

try{

mToken+="\'";

char c=(char)mIn.read();

while(c!='\''){

mToken+=c;

c=(char)mIn.read();

if (c=='\\'){

mToken+=c;

if (mToken.length()>3){

c=(char)mIn.read();

while( (c!=' ') &&

(c!='\t')&&

(c!='\n')){

mToken+=c;

c=(char)mIn.read();

}

Error(mToken,1);

return;

}

if (mToken.length()>2){

c=(char)mIn.read();

while( (c!=' ') &&

(c!='\t')&&

(c!='\n')){

mToken+=c;

c=(char)mIn.read();

}

Error(mToken,1);

return;

}

mToken+=c;

long code=GetConstCode();

LinkedList STInd=GetSTIndex(mToken);

AddToIFT(code,((Long)STInd.get(0)).longValue(),((Long)STInd.get(1)).longValue());

}

System.out.println(mErrors.size()+" E nr de erori");

}catch(IOException e){

System.out.println(e.toString());

}

return;

}

void readString(){

mType="String";

try{

mToken+="\"";

char c=(char)mIn.read();

while(c!='\"'){

mToken+=c;

char c1=(char)mIn.read();

if (c=='\\' && c1=='\"'){

mToken+=c1;

c=(char)mIn.read();

}

else

c=c1;

mToken+=c;

}

}catch(IOException e){

System.out.println(e.toString());

}

long code=GetConstCode();

LinkedList STInd=GetSTIndex(mToken);

AddToIFT(code,((Long)STInd.get(0)).longValue(),((Long)STInd.get(1)).longValue());

return;

}

void readIdentifierOrKeyword(char c1){

try{

mToken+=c1;

char c=(char)mIn.read();

while(isAlpha(c) || isDigit(c) || (c=='_')){

mToken+=c;

c=(char)mIn.read();

}

}catch(IOException e){

System.out.println(e.toString());

}

if (isInKeywordTable(mToken)){

mType="Keyword";

long code=GetTokenCode(mToken);

long STIndex=0;

AddToIFT(code,STIndex,0);

return;

}

mType="Identifier";

long code=GetIdentifierCode();

LinkedList STInd=GetSTIndex(mToken);

AddToIFT(code, ((Long)STInd.get(0)).longValue(),((Long)STInd.get(1)).longValue());

return;

}

void readNumeric(char c1){

try{

mToken+=c1;

char c=(char)mIn.read();

if (mToken=="0"){

if (isDigit(c) || isAlpha(c)){

String str="";

str+=c;

while( (c!=' ') &&

(c!='\t')&&

(c!='\n')&&

!(isOperator(str))&&

!(isSeparator(str))){

mToken+=c;

c=(char)mIn.read();

str="";

str+=c;

}

Error(mToken,0);

return;

}

while (isDigit(c)){

mToken+=c;

c=(char)mIn.read();

}

if (c=='.'){

readFloat();

return;

}

if (isAlpha(c)){

System.out.println("S-a gasit o litera intr-un numar!");

while( (c!=' ') &&

(c!='\t') &&

(c!='\n') &&

!isOperator(""+c) &&

!isSeparator(""+c)){

mToken+=c;

c=(char)mIn.read();

}

Error(mToken,0);

return;

}

}catch(IOException e){

System.out.println(e.toString());

}

mType="Integer";

long code=GetConstCode();

LinkedList STInd=GetSTIndex(mToken);

AddToIFT(code,((Long)STInd.get(0)).longValue(),((Long)STInd.get(1)).longValue());

return;

}

void readFloat(){

mType="Real";

try{

mToken+=(char)mIn.read();

char c=(char)mIn.read();

while(isDigit(c)){

mToken+=c;

c=(char)mIn.read();

}

if (isAlpha(c)){

while( (c!=' ') ||

(c!='\t')||

(c!='\n')){

mToken+=c;

c=(char)mIn.read();

}

Error(mToken,0);

return;

}

}catch(IOException e){

System.out.println(e.toString());

}

long code=GetConstCode();

LinkedList STInd=GetSTIndex(mToken);

AddToIFT(code,((Long)STInd.get(0)).longValue(),((Long)STInd.get(1)).longValue());

return;

}

void readOperator(char cc){

try{

mToken+=cc;

String t=mToken;

char c=(char)mIn.read();

t+=c;

while(isOperator(t)){

mToken+=c;

c=(char)mIn.read();

t+=c;

}

}catch(IOException e){

System.out.println(e.toString());

}

mType="Operator";

long code=GetTokenCode(mToken);

LinkedList STInd=GetSTIndex(mToken);

AddToIFT(code,((Long)STInd.get(0)).longValue(),((Long)STInd.get(1)).longValue());

return;

}

void readSeparator(char c){

mToken+=c;

mType="Separator";

long code=GetTokenCode(mToken);

LinkedList STInd=GetSTIndex(mToken);

AddToIFT(code,((Long)STInd.get(0)).longValue(),((Long)STInd.get(1)).longValue());

return;

}

LinkedList GetCodeMappingTable(){//CodeMappingRecord

CodeMappingRecord codes[]={

new CodeMappingRecord("<identifier>", 1),

new CodeMappingRecord("<constant>", 2),

new CodeMappingRecord("abstract", 3),

new CodeMappingRecord("boolean", 4),

new CodeMappingRecord("break", 5),

new CodeMappingRecord("byte", 6),

new CodeMappingRecord("byvalue", 7),

new CodeMappingRecord("case", 8),

new CodeMappingRecord("cast", 9),

new CodeMappingRecord("catch", 10),

new CodeMappingRecord("char", 11),

new CodeMappingRecord("class", 12),

new CodeMappingRecord("const", 13),

new CodeMappingRecord("continue", 14),

new CodeMappingRecord("default", 15),

new CodeMappingRecord("do", 16),

new CodeMappingRecord("double", 17),

new CodeMappingRecord("else", 18),

new CodeMappingRecord("extends", 19),

new CodeMappingRecord("false", 20),

new CodeMappingRecord("final", 21),

new CodeMappingRecord("finally", 22),

new CodeMappingRecord("float", 23),

new CodeMappingRecord("for", 24),

new CodeMappingRecord("future", 25),

new CodeMappingRecord("generic", 26),

new CodeMappingRecord("goto", 27),

new CodeMappingRecord("if", 28),

new CodeMappingRecord("inner", 29),

new CodeMappingRecord("implements", 30),

new CodeMappingRecord("import", 31),

new CodeMappingRecord("instanceof", 32),

new CodeMappingRecord("int", 33),

new CodeMappingRecord("interface", 34),

new CodeMappingRecord("long", 35),

new CodeMappingRecord("native", 36),

new CodeMappingRecord("new", 37),

new CodeMappingRecord("null", 38),

new CodeMappingRecord("operator", 39),

new CodeMappingRecord("outer", 40),

new CodeMappingRecord("package", 41),

new CodeMappingRecord("private", 42),

new CodeMappingRecord("protected", 43),

new CodeMappingRecord("public", 44),

new CodeMappingRecord("rest", 45),

new CodeMappingRecord("return", 46),

new CodeMappingRecord("short", 47),

new CodeMappingRecord("static", 48),

new CodeMappingRecord("super", 49),

new CodeMappingRecord("switch", 50),

new CodeMappingRecord("synchronized", 51),

new CodeMappingRecord("this", 52),

new CodeMappingRecord("threadsafe", 53),

new CodeMappingRecord("throw", 54),

new CodeMappingRecord("throws", 55),

new CodeMappingRecord("transient", 56),

new CodeMappingRecord("true", 57),

new CodeMappingRecord("try", 58),

new CodeMappingRecord("var", 59),

new CodeMappingRecord("void", 60),

new CodeMappingRecord("while", 61),

new CodeMappingRecord( "+", 62),

new CodeMappingRecord( "-", 63),

new CodeMappingRecord( "!", 64),

new CodeMappingRecord( "%", 65),

new CodeMappingRecord( "^", 66),

new CodeMappingRecord( "&", 67),

new CodeMappingRecord( "*", 68),

new CodeMappingRecord( "|", 69),

new CodeMappingRecord( "~", 70),

new CodeMappingRecord( "/", 71),

new CodeMappingRecord( ">", 72),

new CodeMappingRecord( "<", 73),

new CodeMappingRecord( "?", 74),

new CodeMappingRecord( ":", 75),

new CodeMappingRecord( "=", 76),

new CodeMappingRecord( "++", 77),

new CodeMappingRecord( "–", 78),

new CodeMappingRecord( "==", 79),

new CodeMappingRecord( "<=", 80),

new CodeMappingRecord( ">=", 81),

new CodeMappingRecord( "!=", 82),

new CodeMappingRecord( "<<", 83),

new CodeMappingRecord( ">>", 84),

new CodeMappingRecord( ">>>", 85),

new CodeMappingRecord( "+=", 86),

new CodeMappingRecord( "-=", 87),

new CodeMappingRecord( "*=", 88),

new CodeMappingRecord( "/=", 89),

new CodeMappingRecord( "&=", 90),

new CodeMappingRecord( "|=", 91),

new CodeMappingRecord( "^=", 92),

new CodeMappingRecord( "%=", 93),

new CodeMappingRecord( "<<=", 94),

new CodeMappingRecord( ">>=", 95),

new CodeMappingRecord( ">>>=", 96),

new CodeMappingRecord( "||", 97),

new CodeMappingRecord( "&&", 98),

new CodeMappingRecord( ")", 99),

new CodeMappingRecord( "(", 100),

new CodeMappingRecord( "{", 101),

new CodeMappingRecord( "}", 102),

new CodeMappingRecord( "[", 103),

new CodeMappingRecord( "]", 104),

new CodeMappingRecord( ";", 105),

new CodeMappingRecord( ",", 106),

new CodeMappingRecord( ".", 107),

new CodeMappingRecord( "$", 108),

new CodeMappingRecord( "volatile",109)

};

LinkedList lst=new LinkedList();

for(int i=0; i<codes.length; i++){

lst.add(codes[i]);

}

return lst;

}

long GetTokenCode(String token){

LinkedList codes=new LinkedList();

codes=GetCodeMappingTable();

ListIterator i=codes.listIterator(0);

while(i.hasNext()){

CodeMappingRecord rec=(CodeMappingRecord)i.next();

if (token.equals(rec.mToken))

return rec.mCode;

}

return -1;

}

long GetConstCode(){

return 2;

}

long GetIdentifierCode(){

return 1;

}

LinkedList GetSTIndex(String token){

LinkedList rez=new LinkedList();

long i1=0;

long i2=0;

ListIterator i=mST.listIterator(0);

while(i.hasNext()){

SymbolTableRecord rec=(SymbolTableRecord)i.next();

if (rec.mSymbol.equals(token)){

rez.add(new Long(i1));

rez.add(new Long(i2));

return rez;

}

i1++;

}

i1=hash(token,0,100);

if (((SymbolTableRecord)mST.get((int)i1)).mUsed==false){

SymbolTableRecord rec=new SymbolTableRecord();

rec.mUsed=true;

rec.mSymbol=mToken;

rec.mType=mType;

rec.mNext=null;

mST.set((int)i1,rec);

rez.add(new Long(i1));

rez.add(new Long(i2));

return rez;

}

SymbolTableRecord rec=((SymbolTableRecord)mST.get((int)i1)).mNext;

i2++;

while(rec.mNext!= null){

rec=rec.mNext;

i2++;

}

rec.mNext.mUsed=true;

rec.mNext.mSymbol=mToken;

rec.mNext.mType=mType;

rec.mNext.mNext=null;

((SymbolTableRecord)mST.get((int)i1)).mNext=rec;

i2++;

rez.add(new Long(i1));

rez.add(new Long(i2));

return rez;

}

long hash(String token, long inf, long sup){

long rez=0;

for (int i=0; i<token.length(); i++){

rez=rez+(int)(token.charAt(i));

}

return (rez-inf)%(sup-inf) + inf;

}

void AddToIFT(long tokenCode,long stI1,long stI2){

InternalFormRecord rec=new InternalFormRecord(tokenCode, stI1, stI2);

mIFT.add(rec);

}

void tipResults(BufferedOutputStream ost){

try{

ost.write((new String("\n–––––––––––––––")).getBytes());

ost.write((new String("\nCodificarea atomilor\n")).getBytes());

ost.write((new String("\n–––––––––––––––")).getBytes());

LinkedList it=GetCodeMappingTable();

ost.write((new String("\nAtom")).getBytes());

for (int j=0; j<20-4; j++) ost.write(' ');

ost.write( (new String("| Cod\n")).getBytes());

ost.write( (new String("–––––––––––––––\n")).getBytes());

ListIterator i=it.listIterator(0);

while(i.hasNext()){

CodeMappingRecord rec=(CodeMappingRecord)i.next();

ost.write( rec.mToken.getBytes() );

String t=rec.mToken;

for (int j=0; j<20-t.length(); j++) ost.write(' ');

ost.write((new String( "| "+rec.mCode +"\n")).getBytes());

}

ost.write((new String("\n–––––––––––––––––––")).getBytes());

ost.write((new String("\nTabela de simboluri\n")).getBytes());

ost.write((new String("\n–––––––––––––––––––\n")).getBytes());

int ind=0;

ost.write((new String( "nr \t| Folosit\t| Simbol")).getBytes());

for (int j=0; j<11; j++) ost.write(' ');

ost.write((new String("| Tip")).getBytes());

for (int j=0; j<12; j++) ost.write(' ');

ost.write((new String("| Urmatorul\n")).getBytes());

ost.write((new String("–––––––––––––––––––––\n")).getBytes());

ListIterator ii=mST.listIterator(0);

while(ii.hasNext()){

SymbolTableRecord rec=(SymbolTableRecord)ii.next();

ost.write((new String( ind +"\t\t| "+ rec.mUsed +"\t| "+rec.mSymbol)).getBytes());

String s=rec.mSymbol;

for (int j=0; j<15-s.length(); j++) ost.write(' ');

ost.write((new String("| "+rec.mType)).getBytes());

String tip=rec.mType;

for (int j=0; j<=20-tip.length(); j++) ost.write(' ');

if ( rec.mNext==null) {

ost.write((new String( "| NULL")).getBytes());

}

SymbolTableRecord recc=rec.mNext;

while(recc!=null){

ost.write((new String("||\t"+recc.mUsed+"\t"+recc.mSymbol+"\t"+recc.mType+"\t")).getBytes());

recc=recc.mNext;

}

ost.write('\n');

ind++;

}

ost.write((new String("\n–––––––––––––––")).getBytes());

ost.write((new String("\nForma interna a programului\n")).getBytes());

ost.write((new String("\n–––––––––––––––\n")).getBytes());

ost.write((new String("Index1\t\t| Index2\t\t| Cod\n")).getBytes());

ost.write((new String("–––––––––––––––\n")).getBytes());

ListIterator i1=mIFT.listIterator(0);

while(i1.hasNext()){

InternalFormRecord rec=(InternalFormRecord)i1.next();

ost.write((new String(rec.mSymbolIndex1 +"\t\t| "+rec.mSymbolIndex2+"\t\t| "+rec.mTokenCode+"\n")).getBytes());

}

ost.write((new String("\n–––––––––––––––")).getBytes());

ost.write((new String("\nErori\n")).getBytes());

ost.write((new String("\n–––––––––––––––\n")).getBytes());

System.out.println("Exista erori: "+mErrors.size());

ListIterator i2=mErrors.listIterator(0);

while(i2.hasNext()){

String er=(String)i2.next();

ost.write((new String( er+"\n" )).getBytes());

}

}catch(IOException e){

System.out.println(e.toString());

}

void Error(String token,int nr){

switch(nr){

case 0:

mErrors.add("Unknown construction: "+token);

break;

case 1:

mErrors.add("This is not a character constant: "+token);

break;

}

boolean isAlpha(char c){

return ((('a'<=c) &&(c<='z')) || (('A'<=c) && (c<='Z')));

}

boolean isDigitN(char c){

return (('0'<c) && (c<='9'));

}

boolean isDigit(char c){

return (('0'<=c) && (c<='9'));

}

boolean isSeparator(String str){

String separators[]={

")",

"(",

"{",

"}",

"[",

"]",

";",

",",

"."

};

for (int i=0; i<separators.length; i++){

if (separators[i].equals(str))

return true;

}

return false;

}

boolean isOperator(String str){

String operators[]={

"+",

"-",

"!",

"%",

"^",

"&",

"*",

"|",

"~",

"/",

">",

"<",

"?",

":",

"=",

"++",

"–",

"==",

"<=",

">=",

"!=",

"<<",

">>",

">>>",

"+=",

"-=",

"*=",

"/=",

"&=",

"|=",

"^=",

"%=",

"<<=",

">>=",

">>>=",

"||",

"&&"

};

for (int i=0; i<operators.length; i++){

if (operators[i].equals(str))

return true;

}

return false;

}

boolean isInKeywordTable(String str){

String keywords[]={

"abstract", "boolean", "break", "byte",

"byvalue", "case", "cast", "catch",

"char", "class", "const", "continue",

"default", "do", "double", "else",

"extends", "false", "final", "finally",

"float", "for", "future", "generic",

"goto", "if", "inner", "implements",

"import", "instanceof", "int", "interface",

"long", "native", "new", "null",

"operator", "outer", "package", "private",

"protected", "public", "rest", "return",

"short", "static", "super", "switch",

"synchronized", "this", "threadsafe", "throw",

"throws", "transient", "true", "try",

"var", "void", "while" };

for (int i=0; i<keywords.length; i++){

if (keywords[i].equals(str))

return true;

}

return false;

}

};

Anexa 3

Clasa "Producție"

import java.util.*;

import java.io.*;

public class Productie implements Serializable

{

Element mLeftSide;

LinkedList mRightSide;

transient Grammar mGram;

Productie(){

mRightSide=new LinkedList();

mLeftSide=new Element();

mGram=new Grammar();

}

Productie(LinkedList pr, LexicalAnalyzeResult res,Grammar gr){

mRightSide=new LinkedList();

mLeftSide=new Element();

mGram=gr;

char c=((String)pr.get(0)).charAt(0);

if (c=='\"'){

mLeftSide.mType='T';

mLeftSide.mCode=Find(res.mCodemapping,((String)pr.get(0)).substring(1,((String)pr.get(0)).length()-2));

}

else{

if (c=='<'){

String el=(String)pr.get(0);

if (el.equals("<Identifier>")){

mLeftSide.mCode=1;

mLeftSide.mType='N';

}

else{

if (el.equals("<Literal>")){

mLeftSide.mCode=2;

mLeftSide.mType='N';

}

else{

mLeftSide.mType='N';

Iterator net=mGram.mNeterm.iterator();

while (net.hasNext()){

Neterm n=(Neterm)net.next();

if (el.equals(n.mToken)){

mLeftSide.mCode=n.mCode;

break;

}

ListIterator i=pr.listIterator(1);

while(i.hasNext()){

String el=(String)i.next();

if (el.charAt(0)=='\"'){

Element temp=new Element();

temp.mType='T';

temp.mCode=Find(res.mCodemapping,el.substring(1,el.length()-1));

mRightSide.add(temp);

}

else

if (el.charAt(0)=='<'){

Element temp=new Element();

if (el.equals("<Identifier>")){

temp.mCode=1;

temp.mType='T';

}

else

if (el.equals("<Literal>")){

temp.mCode=2;

temp.mType='T';

}

else{

temp.mType='N';

Iterator j=mGram.mNeterm.iterator();

while (j.hasNext()){

Neterm net=(Neterm)j.next();

if (el.equals(net.mToken)){

temp.mCode=net.mCode;

break;

}

mRightSide.add(temp);

}

long Find(LinkedList table, String str){

ListIterator i=table.listIterator(0);

while(i.hasNext()){

CodeMappingRecord rec=(CodeMappingRecord)i.next();

if (rec.mToken.equals(str))

return rec.mCode;

}

return -1;

}

boolean HasNoRightSide(){

if (mRightSide.size()==0)

return true;

return false;

}

boolean HasLeftSide(Element el){

if (mLeftSide.isEqual(el))

return true;

return false;

}

boolean isEqual(Productie p1){

if (mLeftSide.isEqual(p1.mLeftSide)){

if (mRightSide.size() == p1.mRightSide.size()){

ListIterator i=mRightSide.listIterator(0);

ListIterator i1=p1.mRightSide.listIterator(0);

while(i.hasNext() && i1.hasNext()){

Element el=(Element)i.next();

Element el1=(Element)i1.next();

if (!(el.isEqual( el1)))

return false;

}

return true;

}

return false;

}

return false;

}

void tiparire(BufferedOutputStream out) throws IOException{

out.write((new String(mLeftSide.mCode+" "+mLeftSide.mType+" ")).getBytes());

ListIterator i=mRightSide.listIterator(0);

while(i.hasNext()){

Element el=(Element)i.next();

out.write( (new String(el.mCode+" "+el.mType+" ")).getBytes());

}

Anexa 4

Clasa "Grammar"

import java.io.*;

import java.util.*;

public class Grammar implements Serializable

{

LinkedList mProd;

transient BufferedReader mInGram;

TreeSet mNeterm;

TreeSet mTerm;

Grammar(){

mProd=new LinkedList();

mNeterm=new TreeSet();

mTerm=new TreeSet();

}

Grammar(String numeFisGram,LexicalAnalyzeResult res){

mProd=new LinkedList();

mNeterm=new TreeSet();

mTerm=new TreeSet();

try{

mInGram=new BufferedReader(new FileReader(numeFisGram));

boolean unu=true;

long nrNeterm=0;

Long cd=new Long(Find(res.mCodemapping,"$"));

mTerm.add(cd);

rel:

while( true ){

String line = mInGram.readLine();

if (line==null)

break;

if( line.equals(""))

continue rel;

StringTokenizer strTok=new StringTokenizer(line," ");

LinkedList pr=new LinkedList();

pr.clear();

reluare:

while(strTok.hasMoreTokens()){

String tok=strTok.nextToken();

if (unu){

Neterm net=new Neterm();

net.mToken="<SPrim>";

net.mCode=0;

mNeterm.add(net);

Neterm net1=new Neterm();

net1.mCode=1;

net1.mToken=tok;

mNeterm.add(net1);

nrNeterm=nrNeterm+1;

pr.add(new String("<SPrim>"));

pr.add(tok);

Productie prod=new Productie(pr,res,this);

mProd.add(prod);

pr.clear();

unu=false;

}

if (tok.equals("::="))

continue reluare;

pr.add(tok);

if (tok.charAt(0)=='<' && !tok.equals("<Identifier>") && !tok.equals("<Literal>")){

if (nrNeterm>0){

Neterm net=new Neterm();

net.mToken=tok;

nrNeterm++;

net.mCode=nrNeterm;

mNeterm.add(net);

}

else{

if (tok.charAt(0)=='\"'){

long cc=Find(res.mCodemapping,tok.substring(1,tok.length()-1));

Long cod=new Long(cc);

mTerm.add(cod);

}

if (tok.equals("<Identifier>")){

long cod=Find(res.mCodemapping,"<identifier>");

mTerm.add(new Long(cod));

}

if (tok.equals("<Literal>")){

long cod=Find(res.mCodemapping,"<constant>");

mTerm.add(new Long(cod));

}

mProd.add(new Productie(pr,res,this));

}

}catch(IOException e){

e.printStackTrace();

}

long Find(LinkedList table, String str){

ListIterator i=table.listIterator(0);

while(i.hasNext()){

CodeMappingRecord rec=(CodeMappingRecord)i.next();

if (rec.mToken.equals(str))

return rec.mCode;

}

return -1;

}

void tipGram(BufferedOutputStream out) throws IOException{

out.write((new String("Neterminale\n")).getBytes());

Iterator it=mNeterm.iterator();

while(it.hasNext()){

Neterm net=(Neterm)it.next();

out.write((new String(net.mToken+" "+net.mCode+"\n")).getBytes());

}

out.write((new String("Terminale\n")).getBytes());

Iterator it1=mTerm.iterator();

while(it1.hasNext()){

out.write((new String(it1.next()+"\n")).getBytes());

}

out.write((new String("Productii")).getBytes());

ListIterator i=mProd.listIterator(0);

while(i.hasNext()){

Productie prod=(Productie)i.next();

out.write('\n');

prod.tiparire(out);

}

out.close();

}

long GetProdInd(Productie pr){

ListIterator i=mProd.listIterator(0);

long j=0;

while(i.hasNext()){

Productie prod=(Productie)i.next();

if (prod.isEqual(pr))

return j;

j++;

}

return -1;

}

Anexa 5

Clasa "SyntAnalyzer"

import java.io.*;

import java.util.*;

public class SyntAnalyzer

{

Grammar mGram;

BufferedOutputStream mOut;

LexicalAnalyzeResult mResLex;

LinkedList mColCan;

LinkedList mColMerged;

LinkedList mActionTable;

LinkedList mGotoTable;

LinkedList mFuziuni;

LinkedList mErrors;

Action action(long s,Element el){

ListIterator i=mActionTable.listIterator(0);

while(i.hasNext()){

Action action=(Action)i.next();

if (action.mState == s && action.mTerminal.isEqual(el)){

return action;

}

Action act=new Action();

act.mState=s;

act.mTerminal=el;

act.mAction="eroare";

mErrors.add("Unexpected identifier : "+mResLex.getTermByCode(el.mCode));

return act;

}

Goto GetGoto(long s, Element el){

ListIterator i=mGotoTable.listIterator(0);

while (i.hasNext()){

Goto got=(Goto)i.next();

if (got.mState == s && got.mElem.isEqual(el))

return got;

}

Goto g=new Goto();

g.mState=s;

g.mElem=el;

g.mGoto=-1;

mErrors.add("Unexpected identifier : "+mResLex.getTermByCode(el.mCode));

return g;

}

long GetStateInd(TreeSet s){

ListIterator i=mColMerged.listIterator(0);

long j =0;

while (i.hasNext()){

TreeSet state=(TreeSet)i.next();

if (areEqual(state,s))

return j;

j++;

}

return -1;

}

TreeSet GetState(long st){

ListIterator i=mColMerged.listIterator(0);

TreeSet s=new TreeSet();

while( st>=0 )

{

s=(TreeSet)i.next();

st–;

}

return s;

}

boolean areEqual(TreeSet s1, TreeSet s2){

if (s1.size()!=s2.size())

return false;

Iterator i=s1.iterator();

while(i.hasNext()){

ElementOfAnalyze eoa=(ElementOfAnalyze)i.next();

Iterator i2=s2.iterator();

boolean are=false;

while(i2.hasNext()){

ElementOfAnalyze eoa2=(ElementOfAnalyze)i2.next();

if (eoa2.mNrProd==eoa.mNrProd && eoa2.mIndPoint==eoa.mIndPoint)

are=true;

}

if (! are)

return false;

}

Iterator ii=s2.iterator();

while(ii.hasNext()){

ElementOfAnalyze eoa=(ElementOfAnalyze)ii.next();

Iterator ii2=s1.iterator();

boolean are=false;

while(ii2.hasNext()){

ElementOfAnalyze eoa2=(ElementOfAnalyze)ii2.next();

if (eoa2.mNrProd==eoa.mNrProd && eoa2.mIndPoint==eoa.mIndPoint)

are=true;

}

if (! are )

return false;

}

return true;

}

void GoToTableConstruction(){

ListIterator it1=mColMerged.listIterator(0);

while (it1.hasNext()){

TreeSet state=(TreeSet)it1.next();

Iterator it2=mGram.mNeterm.iterator();

while (it2.hasNext()){

Neterm net=(Neterm)it2.next();

Goto el=new Goto();

el.mState=GetStateInd(state);

Element elem=new Element();

elem.mType='N';

elem.mCode=net.mCode;

el.mElem=elem;

el.mGoto=GetStateInd(GoToFunction(state,elem));

if (el.mGoto != -1)

mGotoTable.add(el);

}

ListIterator itt1=mColMerged.listIterator(0);

while (itt1.hasNext()){

TreeSet state=(TreeSet)itt1.next();

Iterator it2=mGram.mTerm.iterator();

while (it2.hasNext()){

Long term=(Long)it2.next();

Goto el=new Goto();

el.mState=GetStateInd(state);

Element elem=new Element();

elem.mType='T';

elem.mCode=term.longValue();

el.mElem=elem;

el.mGoto=GetStateInd(GoToFunction(state,elem));

if (el.mGoto != -1)

mGotoTable.add(el);

}

void TA(Action act){

Element e=new Element();

e.mType='T';

e.mCode=Find(mResLex.mCodemapping,"$");

act.mAction="";

TreeSet I=GetState(act.mState);

Iterator it=I.iterator();

if (act.mTerminal.isEqual(e)){

while (it.hasNext()){

ElementOfAnalyze eoa=(ElementOfAnalyze)it.next();

if ( (eoa.mNrProd==0) && (eoa.mIndPoint==1) && (eoa.mPrediction.size() == 1) && ((Element)eoa.mPrediction.getFirst()).isEqual(e)){

act.mAction="acc";

return;

}

Iterator it1=I.iterator();

while (it1.hasNext()){

ElementOfAnalyze eoa=(ElementOfAnalyze)it1.next();

Productie pr1=(Productie)mGram.mProd.get((int)eoa.mNrProd);

if (pr1.mRightSide.size()>eoa.mIndPoint){

if (((Element)pr1.mRightSide.get((int)eoa.mIndPoint)).isEqual(act.mTerminal))

if (act.mAction == "" || act.mAction == "s") {

act.mAction="s";

}

else

act.mAction="conflict";

}

else

if (eoa.mIndPoint == pr1.mRightSide.size()){

long k=mGram.GetProdInd(pr1);

if (act.mAction == "" || (act.mAction == "r" && act.mProdRed == k)){

act.mAction="r";

act.mProdRed=k;

}

else

act.mAction="conflict";

}

void ActionTableConstruction(){

ListIterator it1=mColMerged.listIterator(0);

while (it1.hasNext()){

TreeSet state=(TreeSet)it1.next();

Iterator it2=mGram.mTerm.iterator();

while (it2.hasNext()){

Long term=(Long)it2.next();

Element el=new Element();

el.mType='T';

el.mCode=term.longValue();

Action act=new Action();

act.mState=GetStateInd(state);

act.mTerminal=el;

TA(act);

if (!act.mAction.equals(""))

mActionTable.add(act);

}

boolean Merge(TreeSet I1, TreeSet I2){

if (I1.size()!=I2.size())

return false;

TreeSet stMerged=new TreeSet();

Iterator it1=I1.iterator();

while(it1.hasNext()){

boolean has=false;

ElementOfAnalyze eoa1=(ElementOfAnalyze)it1.next();

Iterator it2=I2.iterator();

while(it2.hasNext()){

ElementOfAnalyze eoa2=(ElementOfAnalyze)it2.next();

if (eoa1.hasSameCore(eoa2)){

has=true;

ElementOfAnalyze enew=new ElementOfAnalyze();

enew.mNrProd=eoa1.mNrProd;

enew.mIndPoint=eoa1.mIndPoint;

enew.mPrediction=eoa1.mPrediction;

ListIterator it3=eoa2.mPrediction.listIterator(0);

while(it3.hasNext()){

Element e1=(Element)it3.next();

if (!enew.mPrediction.contains(e1))

enew.mPrediction.add(e1);

}

stMerged.add(enew);

}

if (!has)

return false;

}

mColMerged.remove(I1);

mColMerged.remove(I2);

if (!mColMerged.contains(stMerged))

mColMerged.add(stMerged);

return true;

}

void MergeStates(){

boolean modify;

for (int k=0; k<mColCan.size(); k++)

mFuziuni.add(new Long(0));

doReduceStates();

LinkedList col=mColCan;

do{

int n1=0;

modify=false;

ListIterator i=col.listIterator(0);

reluare:

while (i.hasNext()){

TreeSet st1=(TreeSet)i.next();

int n2=0;

if (((Long)mFuziuni.get(n1)).longValue() != 0){

n1++;

continue reluare;

}

ListIterator j=col.listIterator(0);

for (long k=0; k<=n1; k++){

TreeSet st=(TreeSet)j.next();

}

n2=n1+1;

while (j.hasNext()){

TreeSet st2=(TreeSet)j.next();

if (Merge(st1,st2)){

mFuziuni.set((int)n1, new Long(n1+1));

mFuziuni.set((int)n2, new Long(n1+1));

modify=true;

break;

}

n2++;

}

n1++;

}

while (modify);

ListIterator i=col.listIterator(0);

int n=0;

while (i.hasNext()){

TreeSet st =(TreeSet)i.next();

if (((Long)mFuziuni.get(n)).longValue() == 0)

if (!mColMerged.contains(st))

mColMerged.add(st);

n++;

}

void doReduceStates(){

LinkedList coll=new LinkedList();

ListIterator i=mColCan.listIterator(0);

while(i.hasNext()){

TreeSet state=(TreeSet)i.next();

Iterator it1=state.iterator();

TreeSet st=state;

while (it1.hasNext()){

ElementOfAnalyze eoa=(ElementOfAnalyze)it1.next();

Iterator it=state.iterator();

ElementOfAnalyze e=(ElementOfAnalyze)it.next();

while(!e.isEqual(eoa)){

e=(ElementOfAnalyze)it.next();

}

while (it.hasNext()){

e=(ElementOfAnalyze)it.next();

if (eoa.hasSameCore(e)){

st.remove(eoa);

st.remove(e);

ListIterator i1=e.mPrediction.listIterator(0);

while (i1.hasNext()){

Element el=(Element)i1.next();

if (!eoa.mPrediction.contains(el)){

eoa.mPrediction.add(el);

}

st.add(eoa);

}

if (!coll.contains(st))

coll.add(st);

}

mColCan=coll;

}

TreeSet GoToFunction(TreeSet I, Element X){

TreeSet param=new TreeSet();

Iterator it1=I.iterator();

while (it1.hasNext()){

ElementOfAnalyze e=(ElementOfAnalyze)it1.next();

Productie p=(Productie)mGram.mProd.get((int)e.mNrProd);

if (p.mRightSide.size()>e.mIndPoint)

if (((Element)p.mRightSide.get((int)e.mIndPoint)).isEqual(X)){

ElementOfAnalyze eoa=new ElementOfAnalyze();

eoa.mNrProd=e.mNrProd;

eoa.mIndPoint=e.mIndPoint+1;

eoa.mPrediction=e.mPrediction;

param.add(eoa);

}

return closure(param);

}

LinkedList PR(Element el, TreeSet net){

LinkedList prim=new LinkedList();

ListIterator it1=mGram.mProd.listIterator(0);

rell:

while(it1.hasNext()){

Productie pr=(Productie)it1.next();

Element e1=new Element();

if (pr.HasLeftSide(el)){

net.add(el);

e1=(Element)pr.mRightSide.getFirst();

if (e1.mType=='T'){

if (!prim.contains(e1))

prim.add(e1);

}

else{

if (net.contains(e1))

continue rell;

LinkedList temp=new LinkedList();

temp.addAll(PR(e1,net));

ListIterator it2=temp.listIterator(0);

while(it2.hasNext()){

Element e2=(Element)it2.next();

if (!prim.contains(e2))

prim.add(e2);

}

return prim;

}

TreeSet closure(TreeSet I){

TreeSet Cl=(TreeSet)I.clone();

boolean modify=false;

TreeSet usedNet=new TreeSet();

do{

modify=false;

TreeSet J=new TreeSet();

J.addAll(Cl);

Iterator it1=J.iterator();

while(it1.hasNext()){

ElementOfAnalyze eoa=(ElementOfAnalyze)it1.next();

Productie pOld=(Productie)mGram.mProd.get((int)eoa.mNrProd);

if (pOld.mRightSide.size()>eoa.mIndPoint){

Element el=(Element)pOld.mRightSide.get((int)eoa.mIndPoint);

if (el.mType=='N' && !usedNet.contains(el)){

usedNet.add(el);

ListIterator it2=mGram.mProd.listIterator(0);

while(it2.hasNext()){

Productie p=(Productie)it2.next();

if (p.HasLeftSide(el)){

ElementOfAnalyze eoa1=new ElementOfAnalyze();

eoa1.mNrProd=mGram.GetProdInd(p);

eoa1.mIndPoint=0;

LinkedList pred=new LinkedList();

ListIterator it3=pOld.mRightSide.listIterator((int)eoa.mIndPoint+1);

while (it3.hasNext()){

pred.add((Element)it3.next());

}

ListIterator it4=eoa.mPrediction.listIterator(0);

while(it4.hasNext()){

Element e1=(Element)it4.next();

LinkedList predi=pred;

predi.add(e1);

LinkedList first=first(predi);

ListIterator it5=first.listIterator(0);

while(it5.hasNext()){

Element e2=(Element)it5.next();

if (!eoa1.mPrediction.contains(e2))

eoa1.mPrediction.add(e2);

}

modify=Cl.add(eoa1);

}

while(modify);

return Cl;

}

LinkedList first(LinkedList mul){

LinkedList fst=new LinkedList();

ListIterator it1=mul.listIterator(0);

Element e1=(Element)it1.next();

if (e1.mType=='T'){

fst.add(e1);

return fst;

}

TreeSet net=new TreeSet();

fst=PR(e1,net);

return fst;

}

String ElementToString( Element e){

switch( e.mType )

{

case 'T':

{

LinkedList cmap = mResLex.mCodemapping;

ListIterator i=cmap.listIterator(0);

while( i.hasNext())

{

CodeMappingRecord rec=(CodeMappingRecord)i.next();

if(rec.mCode == e.mCode)

return rec.mToken;

}

case 'N':

{

Iterator i=mGram.mNeterm.iterator();

while(i.hasNext())

{

Neterm net=(Neterm)i.next();

if(net.mCode==e.mCode)

return net.mToken;

}

return "?";

}

long Find(LinkedList table, String str){

ListIterator i=table.listIterator(0);

while(i.hasNext()){

CodeMappingRecord rec=(CodeMappingRecord)i.next();

if (rec.mToken.equals(str))

return rec.mCode;

}

return -1;

}

SyntAnalyzer(){

mColCan=new LinkedList();

mColMerged=new LinkedList();

mActionTable=new LinkedList();

mGotoTable=new LinkedList();

mFuziuni=new LinkedList();

mErrors=new LinkedList();

mResLex=null;

}

SyntAnalyzer(String numeFisGram, String numeFisIes, LexicalAnalyzeResult reslex){

if (reslex.mErrors.size()>0){

}

else{

mResLex=reslex;

mColCan=new LinkedList();

mColMerged=new LinkedList();

mActionTable=new LinkedList();

mGotoTable=new LinkedList();

mErrors=new LinkedList();

mFuziuni=new LinkedList();

try{

String numeGram=numeFisGram+".txt";

String numeSer=numeFisGram+".ser";

File f1=new File(numeGram);

File f2=new File(numeSer);

if (!f2.exists() || f1.lastModified()>f2.lastModified()){

mGram=new Grammar(numeGram, mResLex);

FileOutputStream fis=new FileOutputStream(numeSer);

ObjectOutputStream grSerial=new ObjectOutputStream(fis);

grSerial.writeObject(mGram);

fis.close();

mOut=new BufferedOutputStream(new FileOutputStream(numeFisIes));

}

else{

System.out.println("Se ia forma serializata!");

FileInputStream fis =new FileInputStream(numeSer);

ObjectInputStream grDeserial=new ObjectInputStream(fis);

mGram=(Grammar)grDeserial.readObject();

fis.close();

mOut=new BufferedOutputStream(new FileOutputStream(numeFisIes));

}

catch(Exception e){

e.printStackTrace();

}

void WriteToStream(){

try{

mOut.write((new String("Rezultatele analizei sintactice\n\n")).getBytes());

Iterator q=mGram.mNeterm.iterator();

while( q.hasNext())

{

Neterm net=(Neterm)q.next();

mOut.write((new String(net.mToken +" – " +net.mCode +"\n")).getBytes());

}

mOut.write('\n');

// Colectia canonica

mOut.write((new String("––––––\n")).getBytes());

mOut.write((new String("Colectia canonica\n")).getBytes());

mOut.write((new String("––––––\n")).getBytes());

mOut.write('\n');

ListIterator i=mColMerged.listIterator(0);

while(i.hasNext())

{

TreeSet state=(TreeSet)i.next();

mOut.write((new String(GetStateInd(state) + " = {")).getBytes());

Iterator j=state.iterator();

while(j.hasNext())

{

ElementOfAnalyze eoa=(ElementOfAnalyze)j.next();

mOut.write((new String(" [ ")).getBytes());

Productie p = (Productie)mGram.mProd.get((int)eoa.mNrProd);

mOut.write((new String(ElementToString(p.mLeftSide) + " -> ")).getBytes());

for(int k=0; k<eoa.mIndPoint; k++)

mOut.write((new String(ElementToString((Element)p.mRightSide.get(k))+" ")).getBytes());

mOut.write((new String(". ")).getBytes());

for(int k=(int)eoa.mIndPoint; k<p.mRightSide.size(); k++)

mOut.write((new String(ElementToString((Element)p.mRightSide.get(k))+" ")).getBytes());

mOut.write((new String(" , ")).getBytes());

ListIterator it=eoa.mPrediction.listIterator(0);

while(it.hasNext()){

Element elem=(Element)it.next();

mOut.write((new String(ElementToString(elem) + " ")).getBytes());

}

mOut.write((new String(" ] \n")).getBytes());

}

mOut.write((new String(" } \n")).getBytes());

}

// Tabela Goto

mOut.write((new String("––––––\n")).getBytes());

mOut.write((new String("Tabela Goto\n")).getBytes());

mOut.write((new String("––––––\n\n")).getBytes());

ListIterator k=mGotoTable.listIterator(0);

while (k.hasNext()){

Goto got=(Goto)k.next();

mOut.write((new String( "\ngoto ( " + got.mState + " , " + ElementToString(got.mElem) + " ) = " + got.mGoto)).getBytes());

}

// Tabela Action

mOut.write((new String("\n––––––\n")).getBytes());

mOut.write((new String("Tabela Action\n")).getBytes());

mOut.write((new String("––––––\n\n")).getBytes());

ListIterator jj=mActionTable.listIterator(0);

while (jj.hasNext()){

Action act=(Action)jj.next();

mOut.write((new String("\naction ( "+act.mState+" , "+ElementToString(act.mTerminal)+" ) = "+act.mAction)).getBytes());

if (act.mAction=="r")

mOut.write((new String(""+act.mProdRed)).getBytes());

}

mOut.close();

}catch(IOException e){

e.printStackTrace();

}

void collection(){

LinkedList C=new LinkedList();

Element e=new Element();

e.mType='T';

e.mCode=Find(mResLex.mCodemapping,"$");

ElementOfAnalyze eoa=new ElementOfAnalyze();

eoa.mIndPoint=0;

eoa.mNrProd=0;

eoa.mPrediction.add(e);

TreeSet I0=new TreeSet();

I0.add(eoa);

TreeSet clos=closure(I0);

C.add(clos);

boolean modify;

do{

modify=false;

LinkedList Tmp=new LinkedList();

ListIterator it1=C.listIterator(0);

while(it1.hasNext()){

TreeSet state=(TreeSet)it1.next();

TreeSet I=GoToFunction(state,e);

if (I.size()>0 && !C.contains(I)){

Tmp.add(I);

modify=true;

}

Iterator it2=mGram.mNeterm.iterator();

while(it2.hasNext()){

Neterm net=(Neterm)it2.next();

if (net.mCode!=0){

Element el=new Element();

el.mType='N';

el.mCode=net.mCode;

TreeSet I1=GoToFunction(state,el);

if (I1.size()>0 && !C.contains(I1)){

Tmp.add(I1);

modify=true;

}

Iterator it3=mGram.mTerm.iterator();

while(it3.hasNext()){

Long term=(Long)it3.next();

Element el=new Element();

el.mType='T';

el.mCode=term.longValue();

I=GoToFunction(state,el);

if (I.size()>0 && !C.contains(I)){

Tmp.add(I);

modify=true;

}

if(modify)

{

ListIterator i=Tmp.listIterator(0);

while(i.hasNext())

{

TreeSet stt=(TreeSet)i.next();

if (!C.contains(stt))

C.add(stt);

}

break;

}

while(modify);

mColCan.clear();

ListIterator itt=C.listIterator(0);

while(itt.hasNext()){

TreeSet st=(TreeSet)itt.next();

mColCan.add(st);

}

void analyze(){

Element e=new Element();

e.mType='T';

e.mCode=Find(mResLex.mCodemapping,"$");

collection();

System.out.println("S-a construit colectia!");

MergeStates();

ActionTableConstruction();

GoToTableConstruction();

Configuration config=new Configuration();

WorkItem item=new WorkItem();

item.mElem=e;

ListIterator li=mColMerged.listIterator(0);

while(li.hasNext()){

TreeSet state=(TreeSet)li.next();

Iterator si=state.iterator();

while(si.hasNext()){

ElementOfAnalyze eoa=(ElementOfAnalyze)si.next();

if (eoa.mNrProd==0 && eoa.mIndPoint==0){

item.mState=GetStateInd(state);

break;

}

if (si.hasNext())

break;

}

config.mWorkStack.add(item);

config.mInputStack=mResLex.mIntForm;

InternalFormRecord el=new InternalFormRecord();

el.mTokenCode=e.mCode;

config.mInputStack.add(el);

boolean acceptat=false,erori=false;

while (!acceptat && !erori){

Element elem=new Element();

elem.mCode=((InternalFormRecord)config.mInputStack.getFirst()).mTokenCode;

elem.mType='T';

Action act=action(((WorkItem)config.mWorkStack.getLast()).mState,elem);

WorkItem it=new WorkItem();

if (act.mAction == "s"){

it.mElem=elem;

it.mState=GetGoto(((WorkItem)config.mWorkStack.getLast()).mState,elem).mGoto;

if (it.mState == -1){

erori=true;

}

else{

config.mWorkStack.add(it);

config.mInputStack.remove(config.mInputStack.getFirst());

}

else

if (act.mAction == "r"){

Productie pr=(Productie)mGram.mProd.get((int)act.mProdRed);

for (int i=0; i<pr.mRightSide.size(); i++)

config.mWorkStack.removeLast();

WorkItem itt=new WorkItem();

itt.mElem=pr.mLeftSide;

if (config.mWorkStack.size()>0)

itt.mState=GetGoto(((WorkItem)config.mWorkStack.getLast()).mState,pr.mLeftSide).mGoto;

if (itt.mState == -1){

erori=true;

}

else{

config.mWorkStack.add(itt);

config.mUsedProductions.add(new Long(act.mProdRed));

}

else

if (act.mAction == "acc"){

acceptat=true;

}

else{

erori=true;

}

try{

if (acceptat){

mOut.write((new String("\nSecventa a fost acceptata\n")).getBytes());

mOut.write((new String("\nProductiile folosite: \n")).getBytes());

ListIterator i=config.mUsedProductions.listIterator(0);

while (i.hasNext()){

Long p=(Long)i.next();

Productie prod=(Productie)mGram.mProd.get(p.intValue());

mOut.write((ElementToString(prod.mLeftSide)+" -> ").getBytes());

ListIterator j=prod.mRightSide.listIterator(0);

while (j.hasNext()){

Element ell=(Element)j.next();

mOut.write((" "+ElementToString(ell)).getBytes());

}

mOut.write('\n');

}

else

mOut.write((new String("\nSecventa nu a fost acceptata\n")).getBytes());

}catch(IOException ex){

ex.printStackTrace();

}

Anexa 6

Programul principal

(princ.java)

import javax.swing.*;

import java.awt.*;

import java.awt.event.*;

import javax.swing.event.*;

import java.io.*;

import javax.swing.filechooser.*;

import java.util.*;

class AlertDialog extends JDialog{

JLabel mLabMessage;

JButton mButOk;

AcListener mListener;

public class AcListener implements ActionListener{

public void actionPerformed(ActionEvent e){

String command=e.getActionCommand();

if (command.equals("OK")){

dispose();

return;

}

public AlertDialog(Frame owner, String title, boolean modal, String message){

super(owner, title, modal);

getContentPane().setLayout(new GridBagLayout());

getContentPane().add(mLabMessage=new JLabel(message));

getContentPane().add(mButOk=new JButton("OK"));

mListener=new AcListener();

mButOk.addActionListener(mListener);

Insets i=getInsets();

this.setBounds(100,100,200,200);

mLabMessage.setBounds(i.left,50, 150,30);

mButOk.setBounds(25,150, 100,30);

((GridBagLayout)getContentPane().getLayout()).setConstraints(mButOk, new GridBagConstraints(10,10,1,1,0,0,GridBagConstraints.CENTER, GridBagConstraints.NONE, new Insets(10,10,10,10), 0,0));

}

public class princ extends JFrame

{

JMenuBar mMenuBar;

JTextArea mTextAreaFile;

JTextArea mTextAreaErrors;

EvListener mListen;

WinListener mWinListen;

File mInputFile;

String mGramName;

public JFrame getFrame(){

return this;

}

public class WinListener extends WindowAdapter{

public void windowClosing(WindowEvent ev){

dispose();

System.exit(0);

}

public class EvListener implements ActionListener{

public void actionPerformed(ActionEvent e){

String command=e.getActionCommand();

if (command.equals("Open")){

JFileChooser dopen=new JFileChooser();

dopen.setCurrentDirectory(new File("c:\\home\\ina\\an4\\lucrare\\esswing\\"));

if (dopen.showOpenDialog(getFrame())==JFileChooser.APPROVE_OPTION){

try{

mInputFile=dopen.getSelectedFile();

getFrame().setTitle(mInputFile.getName());

BufferedReader in=new BufferedReader(new FileReader(mInputFile));

mTextAreaFile.setText("");

String line=in.readLine();

while(line!=null){

mTextAreaFile.append(line+"\n");

line=in.readLine();

}

in.close();

for (int i=0; i<mMenuBar.getMenuCount(); i++){

if (i!=2)

for (int j=0; j<mMenuBar.getMenu(i).getItemCount(); j++){

mMenuBar.getMenu(i).getItem(j).setEnabled(true);

}

}catch(IOException ex){

ex.printStackTrace();

}

return;

}

if (command.equals("Save")){

JFileChooser dSave=new JFileChooser();

dSave.setCurrentDirectory(new File("c:\\home\\ina\\an4\\lucrare\\esswing\\"));

if (dSave.showSaveDialog(getFrame())==JFileChooser.APPROVE_OPTION){

try{

String fText=mTextAreaFile.getText();

BufferedWriter f=new BufferedWriter(new FileWriter(dSave.getSelectedFile()));

getFrame().setTitle(dSave.getSelectedFile().getName());

f.write(fText,0,fText.length());

f.close();

}

catch(IOException ex){

ex.printStackTrace();

}

return;

}

if (command.equals("Close")){

mTextAreaFile.setText("");

getFrame().setTitle("Analyzer");

mMenuBar.getMenu(0).getItem(1).setEnabled(false);

mMenuBar.getMenu(0).getItem(2).setEnabled(false);

mMenuBar.getMenu(1).getItem(0).setEnabled(false);

mMenuBar.getMenu(2).getItem(0).setEnabled(false);

mMenuBar.getMenu(2).getItem(1).setEnabled(false);

mMenuBar.getMenu(3).getItem(0).setEnabled(false);

return;

}

if (command.equals("Exit")){

getFrame().dispose();

System.exit(0);

return;

}

if (command.equals("Choose Grammar")){

JFileChooser cGram=new JFileChooser();

cGram.setCurrentDirectory(new File("c:\\home\\ina\\an4\\lucrare\\esswing\\"));

if (cGram.showDialog(getFrame(), "CHOOSE")==JFileChooser.APPROVE_OPTION){

String gr=cGram.getSelectedFile().getName();

mGramName=gr.substring(0,gr.length()-4);

}

return;

}

if (command.equals("Analyze")){

String numeFisGram="Gram2";

String numeFisRezlex="rexlex.txt";

String numeFisIes="iesire.txt";

Analizor analex=new Analizor();

analex.analyze(getFrame().getTitle(), numeFisRezlex);

mTextAreaErrors.setText("Lexical Errors :\n");

if (analex.mErrors.size() >0){

ListIterator it =analex.mErrors.listIterator(0);

while (it.hasNext()){

String error=it.next()+"\n";

mTextAreaErrors.append(error);

}

}else{

mTextAreaErrors.append("0 errors\n");

SyntAnalyzer analizor=new SyntAnalyzer(numeFisGram, numeFisIes,analex.mResult);

analizor.analyze();

mTextAreaErrors.append("Syntactical errors:\n");

if (analizor.mErrors.size()>0){

ListIterator it =analizor.mErrors.listIterator(0);

while (it.hasNext()){

String error=it.next()+"\n";

mTextAreaErrors.append(error);

}

else{

mTextAreaErrors.append("0 errors\n");

}

analizor.WriteToStream();

}

AlertDialog al=new AlertDialog(getFrame(), "Gata!!!", true, "Analyze finished!");

al.show();

mMenuBar.getMenu(2).getItem(0).setEnabled(true);

mMenuBar.getMenu(2).getItem(1).setEnabled(true);

return;

}

if (command.equals("Lexical Results")){

try{

getFrame().setTitle("rexlex.txt");

BufferedReader in=new BufferedReader(new FileReader("rexlex.txt"));

mTextAreaFile.setText("");

String line=in.readLine();

while(line!=null){

mTextAreaFile.append(line+"\n");

line=in.readLine();

}

in.close();

}catch(IOException ex){

ex.printStackTrace();

}

return;

}

if (command.equals("Syntactical Results")){

try{

getFrame().setTitle("iesire.txt");

BufferedReader in=new BufferedReader(new FileReader("iesire.txt"));

mTextAreaFile.setText("");

String line=in.readLine();

while(line!=null){

mTextAreaFile.append(line+"\n");

line=in.readLine();

}

in.close();

}catch(IOException ex){

ex.printStackTrace();

}

return;

}

if (command.equals("Back to file")){

try{

getFrame().setTitle(mInputFile.getName());

BufferedReader in=new BufferedReader(new FileReader(mInputFile));

mTextAreaFile.setText("");

String line=in.readLine();

while(line!=null){

mTextAreaFile.append(line+"\n");

line=in.readLine();

}

in.close();

}catch(IOException ex){

ex.printStackTrace();

}

return;

}

public princ(){

getContentPane().setLayout(new GridLayout(2,1,20,20));

setTitle("Analyzer");

JScrollPane scroll1=new JScrollPane(mTextAreaFile=new JTextArea());

getContentPane().add(scroll1);

JScrollPane scroll2=new JScrollPane(mTextAreaErrors=new JTextArea());

getContentPane().add(scroll2);

mListen=new EvListener();

mWinListen=new WinListener();

this.addWindowListener(mWinListen);

mMenuBar=new JMenuBar();

JMenuItem item;

JMenu menFile=new JMenu("File");

menFile.addActionListener(mListen);

menFile.add(item = new JMenuItem("Open"));

item.addActionListener( mListen );

menFile.add(item=new JMenuItem("Save"));

item.addActionListener(mListen);

menFile.add(item=new JMenuItem("Close"));

item.addActionListener(mListen);

menFile.add(item=new JMenuItem("Exit"));

item.addActionListener(mListen);

menFile.getItem(1).setEnabled(false);

menFile.getItem(2).setEnabled(false);

mMenuBar.add(menFile);

JMenu menAnalyze=new JMenu("Analyze");

menAnalyze.add(item=new JMenuItem("Choose Grammar"));

item.addActionListener(mListen);

menAnalyze.add(item=new JMenuItem("Analyze"));

item.addActionListener(mListen);

menAnalyze.addActionListener(mListen);

menAnalyze.getItem(0).setEnabled(false);

menAnalyze.getItem(1).setEnabled(false);

mMenuBar.add(menAnalyze);

JMenu menResults=new JMenu("Results");

menResults.add(item=new JMenuItem("Lexical Results"));

item.addActionListener(mListen);

menResults.add(item=new JMenuItem("Syntactical Results"));

item.addActionListener(mListen);

menResults.addActionListener(mListen);

menResults.getItem(0).setEnabled(false);

menResults.getItem(1).setEnabled(false);

mMenuBar.add(menResults);

JMenu go=new JMenu("Go");

go.add(item=new JMenuItem("Back to file"));

item.addActionListener(mListen);

go.getItem(0).setEnabled(false);

mMenuBar.add(go);

setJMenuBar( mMenuBar );

this.setBounds(0,0,500,500);

Insets i=getInsets();

mTextAreaFile.setBounds(0,i.top,this.getBounds().width-i.left-i.right,400);

}

public static void main(String args[]){

princ p=new princ();

p.show();

}

BIBLIOGRAFIE

Aho, A.V., Denning, P.J. și Ullman, J.D. – "Weak and mixed strategy precedence parsing", J. ACM 19, 2 (1972), pag. 225-243

Aho, A.V., Johnson, S.C. și Ullman, J.D. – "Deterministic parsing of ambiguous grammars" Conference Record of ACM Symposium on Principles of Programming Languages (Oct. 1973), pag. 1-21

Aho, A.V. și Peterson, T.G. – "A minimum distance error-correcting parser for context-free languages", SIAM J. Computing 1, 4 (1972), pag. 305-312

Aho, A.V. și Ullman, J.D. – "The Theory of Parsing,Translation and Compiling", Vol.I, "Parsing", Prentice-Hall, Englewood Cliffs, N.J., 1972a

Aho A.V., și Ullman, J.D. – "Optimization of LR(k) parsers" J. Cmputer and System Sciences 6, 6 (1972b), pag. 573-602

Aho, A.V. și Ullman, J.D. – "The Theory of Parsing,Translation and Compiling", Vol.II, "Compiling", Prentice-Hall, Englewood Cliffs, N.J., 1973a

Aho, A.V. și Ullman, J.D. – "A technique for speeding up LR(k) parsers" SIAM J. Computing 2, 2 (1973b) pag. 106-127

Anderson, T. – "Syntactic analysis of LR(k) languages" PhD Thesis, Univ. Newcastle-upon-Tyne, Northumberland, England (1972)

Anderson, T., Eve, J. și Horning, J.J. – "Efficient LR(1) parsers" Acta Informatica 2 (1973), pag. 12-39

DeRemer, F.L. – "Practical translators for LR(k) languages" Project MAC Report MAC TR-65, MIT, Cambridge, Mass, 1969

Earley, J. – "An efficient context-free parsing algorithm", Comm. ACM 13, 2 (1970), 94-102

Floyd, R.W. – "Syntactic analysis and operator precedence", J. ACM 10, 3 (1963), pag. 316-333

Knuth, D.E. – "On the translation of languages from left to right" Information and Control 8, 6 (1965), pag. 607-639

Knuth, D.E. – "Top down syntax analysis", Acta Informatica 1, 2 (1971), pag. 97-110

Lalonde, W.R., Lee, E.S. și Horning, J.J. – "An LALR(k) parser generator" Proc. IFIP Congress 71. TA-3, North-Holland Publishing Co., Amsterdam, the Netherlands (1971), pag. 153-157

Lewis, P.M. and Stearns, R.E. – "Syntax directed transduction", J. ACM 15, 3 (1968), pag. 464-488

McKeeman, W.M., Horning, J.J. and Wortman, D.B. – "A Compiler Generator", Prentice-Hall, Englewood Cliffs, N.J., 1970

Pager, D. – "A fast left-to-right parser for context-free grammars", Technical Report PE 240, Information Sciences Program, Univ. Hawaii, Honolulu, Hawaii, 1972b

Copyright Notice

© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.

Acest articol: . Algoritmi de Performanta Pentru Analizoare Sintactice de Tip Lr (ID: 148945)

Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.

. Algoritmi de Performanta Pentru Analizoare Sintactice de Tip Lr

Copyright Notice

Validarea Si Verificarea Sistemelor Critice

Principalele Componente ale Unui Document X.m.l

Dispozitivele Periferice ale Unui Sistem de Calcul

Asigurarea Securitatii In Comertul Electronic

Generarea Desenelor de Montaj Si Instalare

Aplicatii pe Android

Copyright Notice

Similar Posts