Limbaje Formale Si are

1. Introducere Curs1 LFTLimbajele de nivel înalt au o serie de avantaje în raport cu limbajele de asamblare.

Pentru a putea însă folosi limbaje de nivel înalt, trebuie să existe posibilitatea de a converti programele scrise în aceste limbaje într-o formă binară. Această necesitate a dus la dezvoltarea translatoarelor sau compilatoarelor – programe care acceptă o reprezentare textuală a unui algoritm exprimat printr-un program sursă şi care produc o reprezentare a aceluiaşi algoritm exprimat într-un alt limbaj, limbajul obiect sau un limbaj echivalent.

Translatorul este deci un program care traduce programele scrise de utilizator (într-un limbaj) în programe echivalente (într-un alt limbaj). Dacă acestea din urmă sunt programe în cod maşină sau un limbaj apropiat de limbajul calculatorului, translatorul se numeşte compilator. Programul utilizatorului se numeşte program sursă, iar programul în cod maşină obţinut se numeşte program obiect. Între cele două programe trebuie să existe o relaţie de echivalenţă în ceea ce priveşte efectul lor asupra calculatorului.

Execuţia unui program în limbaj simbolic are loc în două faze:Faza 1. Compilarea: Program sursă Compilator Program obiectFaza 2. Execuţia propriu-zisă: Date iniţiale ale programului Program obiect Rezultate

În faza de translatare, calculatorul execută programul compilator, iar în faza de execuţie propriu-zisă, calculatorul execută programul obiect, adică citirea datelor iniţiale, prelucrarea lor şi memorarea sau tipărirea rezultatelor.

Pentru scrierea unui compilator, trebuiesc foarte bine definite atât limbajul sursă, cât şi limbajul ţintă. Aceasta înseamnă că ambele limbaje trebuie să fie formale.

Un limbaj are două aspecte: sintaxă şi semantică. Sintaxa stabileşte care text este corect din punct de vedere gramatical, iar semantica stabileşte modul în care se derivă semnificaţia unui text corect din punct de vedere gramatical.

Există numeroase formalisme şi instrumente software pentru descrierea sintaxei unui limbaj formal. Pentru descrierea semanticii însă, formalismele şi instrumentele existente nu sunt atât de simple şi uşor de utilizat ca şi specificaţiile de sintaxă.

2. Clasificarea şi structura translatoarelorUn translator poate fi definit formal ca o funcţie având domeniul de definiţie limbajul sursă

şi mulţimea valorilor funcţiei limbajul obiect sau un limbaj echivalent (destinaţie).

În dezvoltarea translatoarelor, sunt implicate cel puţin trei limbaje: limbajul sursă de translatat, limbajul obiect sau destinaţie şi limbajul gazdă folosit la implementarea translatorului. Dacă translatarea are loc în mai multe etape, pot exista şi alte limbaje intermediare. Desigur, limbajul gazdă şi limbajul obiect nu sunt cunoscute de utilizatorul limbajului sursă.

2.1. Diagrame TPentru descrierea programelor şi în particular a compilatoarelor, există o reprezentare

schematică consacrată, numită diagramă T, introdusă de Bratman în 1961.

O diagramă T pentru un program general este de forma:

1

O diagramă T pentru un translator general este de forma:

2.2. Clasificarea translatoarelor.- Asamblorul. Termenul de asamblor este asociat cu translatoarele care transformă

instrucţiuni scrise în limbaj de nivel coborât în cod maşină, care poate fi executat direct. De obicei liniile individuale ale programului sursă corespund cu o instrucţiune la nivel maşină. Rolul asamblorului este deci să convertească reprezentările simbolice ale instrucţiunilor în configuraţii de biţi, reprezentând echivalentele în cod-maşină ale instrucţiunilor.

- Macroasamblorul este un asamblor care permite utilizarea macrodefiniţiilor. El utilizează o primă trecere şi pentru colectarea macrodefiniţiilor.Rezultatul asamblării este un text în formă binară în care doar referinţele externe sunt

păstrate în formă simbolică în tabele asociate secţiunilor. Codul binar al secţiunilor este însoţit de informaţii ce indică locul referinţelor relocabile pentru ca, în momentul încărcării, valorile acestora să se poată transforma în referinţe absolute.

Combinarea acestor secţiuni într-un program executabil se face prin rezolvarea referinţelor externe (înlocuirea numelor simbolice cu adrese de memorie) şi adăugarea eventual a rutinelor din bibliotecile standard, şi ele păstrate sub formă relocabilă. Aceste operaţii sunt deobicei făcute de un editor de legături ( linkage editor). Programul furnizat de acesta este adus în memorie de încărcător (loader).- Compilatorul este de obicei un translator care traduce instrucţiuni de nivel înalt în cod

maşină, care poate fi executat direct. Liniile individuale din programul sursă corespund de obicei cu mai multe instrucţiuni la nivel maşină.

- Preprocesorul este un translator care traduce dintr-un superset al unui limbaj de nivel înalt în limbajul de nivel înalt original, sau care face simple substituiri de text înainea procesului de translatare propriu-zis. De exemplu, există numeroase preprocesoare de FORTRAN structurat care traduc din versiuni structurate ale FORTRAN-ului în FORTRAN obişnuit.

- Translatorul de nivel înalt este un translator care traduce un limbaj de nivel înalt într-un alt limbaj de nivel înalt, pentru care există deja compilatoare sofisticate pentru un număr mare de maşini.

- Interpretorul este un program care, primind un program sursă, îl prelucrează în prealabil pentru a-l aduce într-o formă mai simplă, după care îl execută simulând execuţia în limbaj sursă. Forma intermediară executată de de interpretor este de fapt un alt limbaj mai simplu, mai apropiat de limbajele de asamblare. Principalul avantaj al folosirii unui interpretor este portabilitatea foarte simplă a unui limbaj, prin implementarea maşinii virtuale pe un nou hardware. În plus, deoarece instrucţiunile sunt interpretate şi executate în timpul rulării, pot fi implementate limbaje foarte flexibile.

- Compilatoarele incrementale îmbină calităţile compilatoarelor cu cele ale interpretoarelor. Programul sursă este divizat de compilator în mici porţiuni numite incremente. Acestea prezintă o oarecare independenţă sintactică şi semantică faţă de restul programului. Incrementele sunt traduse de compilator. Execuţia are loc interpretativ, permiţându-se intervenţia utilizatorului atât în timpul compilării cât şi în timpul execuţiei.

- Decompilatorul sau dezasamblorul sunt tremeni care se referă la translatoare care au ca intrare un cod obiect şi regenerează codul sursă într-un limbaj de nivel mai înalt. În timp ce acest lucru se poate realiza destul de bine pentru limbaje de asamblare, este mult mai dificil de implementat pentru limbaje de nivel înalt cum ar fi C, Pascal.

Cele mai multe compilatoare nu produc cod maşină cu adrese fixe, ci o formă cunoscută sub numele de "semicompilat", "simbolic binar" sau formă relocatabilă. Rutinele astfel

2

compilate sunt legate cu ajutorul unor programe numite editoare de legături, linker, care pot fi privite ca ultima etapă în procesul de translatare. Limbajele care permit compilarea separată a părţilor unui program depind esenţial de existenţa acestor editoare de legături.

Diagramele T pot fi combinate pentru a arăta interdependenţa translatoarelor, editoarelor de legături etc.

Observaţie. Un compilator nu necesită un limbaj ţintă (de asamblare sau limbaj maşină) real. De exemplu, compilatoarele Java generează cod pentru o maşină virtuală numită "Java Virtual Machine" (JVM). Interpretorul JVM interpretează apoi instrucţiunile JVM fără nici o translatare ulterioară.

2.3. Fazele translaţiei.Translatoarele sunt programe complexe, care necesită o abordare sistematică. Imaginea

unui translator este cea a unui şir de transformări în cascadă a programului sursă în reprezentări din ce în ce mai apropiate de limbajul destinaţie.

Procesul de translaţie se divide într-o serie de faze. O fază este o operaţie unitară de transformare a programului sursă dintr-o reprezentare în alta.

Cea mai simplă descriere împarte procesul de translatare într-o fază analitică urmată de o fază sintetică.

- În faza analitică se analizează programul sursă pentru a determina dacă el corespunde cu restricţiile sintactice şi static semantice impuse de limbajul sursă.

- În faza sintetică se generează efectiv codul obiect în limbajul destinaţie.Componentele translatorului care îndeplinesc aceste faze majore se mai numesc "front end" şi "back end". Prima este total independentă de maşină, în timp ce a doua depinde puternic de maşina destinaţie.

În cadrul acestei structuri există componente mai mici sau faze, aşa cum se prezintă în figura următoare:

- Secţiunea de gestionare caractere este cea care comunică cu lumea exterioară, prin sistemul de operare, pentru citirea caracterelor care formează textul sursă. Cum setul de caractere şi gestiunea fişierelor variază de la sistem la sistem, această fază este de obicei dependentă de maşină sau de sistem de operare.

- Analizorul lexical (Scanner) preia textul sursă sub forma unei secvenţe de caractere şi le grupează în entităţi numite atomi (tokens). Aceştia sunt simboluri ca identificatori, şiruri, constante numerice, cuvinte cheie cum ar fi while şi if, operatori ca <= etc. Atomilor li se atribuie coduri lexicale, astfel că, la ieşirea acestei faze, programul sursă apare ca o secvenţă de asemenea coduri.

3

- Analizorul sintactic (Parser) are ca scop gruparea atomilor rezultaţi în urma analizei lexicale în structuri sintactice. O structură sintactică poate fi văzută ca un arbore ale cărui noduri terminale reprezintă atomi, în timp ce nodurile interioare reprezintă şiruri de atomi care formează o entitate logică. Exemple de structuri sintactice: expresii, instrucţiuni, declaraţii etc.

- Pe durata analizei sintactice, de obicei are loc şi o analiză semantică, adică efectuarea unor verificări legate de compatibilitatea tipurilor datelor cu operaţiile în care ele sunt implicate, de respectarea regulilor de vizibilitate impuse de limbajul sursă.

- Generatorul de cod intermediar este o fază sintetică care, în practică, poate fi integrată în faze anterioare ori poate fi omisă în cazul translatoarelor foarte simple. În această fază are loc transformarea arborelui sintactic într-o secvenţă de instrucţiuni simple, similare macroinstrucţiunilor unui limbaj de asamblare. Diferenţa dintre codul intermediar şi un limbaj de asamblare este în principal aceea că, în codul intermediar nu se specifică registrele utilizate în operaţii. Exemple de reprezentări pentru codul intermediar: notaţia postfix, instrucţiunile cu trei adrese etc. Codul intermediar prezintă avantajul de a fi mai uşor de optimizat decât codul maşină.

4

- Optimizatorul de cod este o fază opţională cu rolul de a modifica porţiuni din codul intermediar generat, astfel încât programul rezultat să satisfacă anumite criterii de performanţă vizând timpul de execuţie şi/sau spaţiul de memorie ocupat.

- Generatorul de cod final este faza cea mai importantă din secţiunea "back end" . În această fază se preia ieşirea de la faza precedentă şi se generează codul obiect, prin decizii privind locaţiile de memorie pentru date, generarea de coduri de acces pentru aceste date, selectarea registrelor pentru calcule intermediare şi indexare etc. Astfel, instrucţiunile din codul intermediar (eventual optimizat) sunt transformate în instrucţiuni maşină (sau de asamblare).

- Unele translatoare continuă cu o fază numită "peephole optimizer" în care se fac încercări de reducere a unor operaţii inutile prin examinarea în detaliu a unor secvenţe scurte din codul generat.

- Un translator foloseşte inevitabil o structură de date complexe, numită tabela de simboluri. Această tabelă memorează informaţii despre simbolurile folosite în programul sursă şi asociază proprietăţi acestor simboluri (tipul lor, spaţiul de memorie necesar pentru variabile sau valoarea lor pentru constante). Compilatorul face referire la această tabelă aproape în toate fazele compilării.

- Tratarea erorilor. Un compilator trebuie să fie capabil să recunoască anumite categorii de erori care apar în programul sursă. Tratarea unei erori presupune detectarea ei, emiterea unui mesaj corespunzător şi revenirea din eroare, adică, pe cât posibil, continuarea procesului de compilare până la epuizarea textului sursă, astfel încât numărul de compilări necesare eliminării tuturor erorilor dintr-un program să fie cât mai mic. Practic, există erori specifice fiecărei faze de compilare.

2.4. Translatoare cu mai multe treceriDeşi conceptual procesul de translatare este divizat în faze, deseori translatoarele sunt

divizate în treceri, în care fazele pot fi combinate ori întreţesute. Tradiţional, o trecere citeşte programul sursă, sau ieşirea unei treceri anterioare, face unele

transformări şi scrie ieşirea sa într-un fişier intermediar care va fi citit de o trecere ulterioară. Aceste treceri pot fi gestionate de diferite părţi integrate în acelaşi compilator, sau pot fi

gestionate prin rularea a două sau mai multe programe separate. Trecerile pot comunica folosind forme specializate ale propriului lor limbaj intermediar, sau

pot folosi structuri de date interne în loc de fişiere, dar se pot face şi mai multe treceri folosind acelaşi cod sursă original.

Numărul trecerilor depinde de o varietate de factori. Unele limbaje necesită cel puţin două treceri pentru a genera mai uşor codul obiect. Compilatoarele cu mai multe treceri folosesc de obicei mai puţină memorie şi sunt mai performante în optimizarea codului şi raportarea de erori, dar sunt mai lente decât cele cu o singură trecere.

În practică, cel mai des sunt folosite compilatoare cu două treceri, în care prima trecere este un translator de nivel înalt care converteşte programul sursă în limbaj de asamblare, sau chiar într-un alt limbaj de nivel înalt pentru care există deja un translator eficient.

2.5. Interpretoare, compilatoare incrementale, emulatoareCompilatoarele descrise mai sus au câteva proprietăţi comune:

- Produc cod obiect care poate rula cu viteza completă a maşinii ţintă.- Uzual compilează o secvenţă întreagă de cod înainte de orice execuţie.

În unele medii interactive, există necesitatea rulării unor părţi ale aplicaţiei fără a fi necesară pregătirea aplicaţiei în ansamblu, ori se permite utilizatorului modificarea din mers a acţiunii următoare.

Astfel de sisteme folosesc deseori un interpretor. Interpretorul este un translator care acceptă efectiv un program sursă şi îl execută direct, fără a produce aparent nici un cod obiect. Interpretorul preia din programul sursă instrucţiunile una câte una, le analizează şi le "execută" una câte una. Evident, pentru ca un astfel de scenariu să poată funcţiona, este necesară impunerea unor restricţii severe programului sursă. Nu pot fi folosite structuri complexe de program, cum ar fi de exemplu proceduri imbricate dar prezintă avantajul unor interogări on-line pentru baze de date etc.

5

Compilatoarele incrementale îmbină calităţile compilatoarelor cu cele ale interpretoarelor. Programul sursă este divizat de compilator în mici porţiuni numite incremente care prezintă o oarecare independenţă sintactică şi semantică faţă de restul programului. Compilatorul produce un cod incremental care este suficient de simplu pentru a satisface restricţiile impuse de un interpretor. Interpretorul "execută" algoritmul original prin simularea unei maşini virtuale pentru care codul intermediar numit şi pseudocod este efectiv codul maşină.

Distincţia dintre codul maşină şi pseudocod este ilustrată în figura următoare:

Dacă se parcurge numai etapa 1 de compilare, pseudocodul este intrare în interpretor. Dacă se parcurge şi etapa 2, rezultatul este un program obiect cu instrucţiuni în cod maşină care poate fi lansat în execuţie independent.

Desigur, orice maşină reală poate fi văzută ca un interpretor specializat care preia din programul sursă instrucţiunile una câte una, le analizează şi le "execută" una câte una. Într-o maşină reală această execuţie este realizată prin hardware, deci mult mai rapid. Se poate conclude că se pot scrie programe care permit unei maşini reale să emuleze orice altă maşină reală, cu dezavantajul vitezei reduse. Aceste programe sunt numite emulatoare şi sunt uzual folosite în proiectarea de noi maşini şi a software-ului care va rula pe acestea.

Una din cele mai cunoscute aplicaţii de compilator incremental portabil este "Pascal–P" (Zurich 1981) care constă din 3 componente:- Un compilator Pascal, scris într-un subset foarte complet al limbajului, numit Pascal-P. Scopul

acestui compilator este translatarea programelor sursă Pascal-P într-un limbaj intermediar foarte bine definit şi documentat, numit P-code, care este "codul maşină" pentru un calculator ipotetic bazat pe stivă, calculator numit P-machine.

- O versiune compilată a primului compilator, astfel încât primul obiectiv al compilatorului este compilarea lui însuşi.

- Un interpretor pentru limbajul P-code scris în Pascal. Interpretorul a servit în principal ca model pentru scrierea unor programe similare pentru alte maşini, în scopul emulării unei maşini ipotetice P-machine.

3. Analiza lexicală (scanner) C2

Este prima fază a procesului de compilare şi are rolul de a transforma programul sursă, văzut ca un şir de caractere într-un şir de simboluri numite atomi lexicali (tokens).

Mulţimea tuturori atomilori lexicali detectabili în programul sursă se împarte în clase de atomi: - clasa identificatorilor- clasa constantelor întregi (numerelor întregi)- clasa numerelor reale- clasa operatorilor - clasa cuvintelor cheie. În urma analizei lexicale, fiecare atom lexical identificat primeşte o codificare internă, iar

programul sursă se transformă într-un şir de coduri aranjate în ordinea detectării atomilor. Deşi rolul principal al analizei lexicale este detectarea atomilor lexicali, putem vorbi de operaţii

conexe analizei lexicale, cum sunt: eliminarea spaţiilor şi comentariilor, numărarea liniilor sursă (pentru raportarea de erori) etc.

3.1. Descriere3.1.1. Analiza lexicală ca etapă specifică a compilării

6

Analiza lexicală este o interfaţă între programul sursă şi analizorul sintactic (parser). Rolul analizorului lexical este asemănător cu cel al analizorului sintactic:

- identificarea conform anumitor reguli a unităţilor distincte în cadrul programului- semnalarea de erori în cazul abaterii de la aceste reguli- codificarea unităţilor identificate etc.

Funcţiile analizorului lexical ar putea fi preluate de analizorul sintactic. Cu toate acestea, în majoritatea cazurilor, se preferă separarea celor două activităţi în faze distincte

din următoarele motive: a) analizorul lexical este mare consumator de timp deoarece necesită preluarea înregistrare cu

înregistrare a textului de pe suportul extern, acesul la fiecare caracter, comparaţii ale atomilor lexicali cu mulţimi de caractere cunoscute în vederea clasificării, căutari în tabele etc. De aceea, pentru a obţine un analizor lexical mai eficient se recomandă implementarea analizorului în limbaj de asamblare, spre deosebire de celelalte faze în care implementarea se face în limbaje de nivel înalt.

b) textul rezultat în urma analizei lexicale, deci cel primit de analizorul sintactic este mai simplu, adică sunt eliminate spaţiile şi comentariile, numărul atomilor lexicali este mult mai mic decât numărul caracterelor din textul sursă.

Analizorul lexical preia astfel sarcina analizei unor construcţii dificile care ar complica şi mai mult procesul de analiză sintactică.

c) sintaxa atomilor lexicali este mai simplă decât a construcţiilor gramaticale de limbaj, se poate exprima prin gramatici regulate şi se poate analiza cu ajutorul automatelor finite, existând tehnici mai simple decât pentru analiza sintactică;

d) prin separarea fazelor, compilatorul poate fi scris modular, deci realizat în echipă;e) separarea creşte portabiliatatea compilatorului în sensul că pentru o versiune nouă a limbajului

va fi necesar să facem modificări doar la analiza lexicală, nu şi la analiza sintactică.

3.1.2. Modele de comunicare analizor lexical-analizor sintactic. Din punct de vedere al interacţiunii dintre analizorul lexical şi cel sintactic există 3 posibilităţi:1. Analizorul lexical procesează textul sursă într-o trecere separată, înainte de a începe analiza

sintactică; în acest caz, cuvintele sunt extrase din programul sursă şi depuse într-un fisier sau într-un tablou de mari dimensiuni în memorie.

2. Analizorul sintactic apelează analizorul lexical ori de câte ori acesta are nevoie de un nou cuvânt; este varianta preferată, deoarece nu este necesară construirea unei forme interne a programului sursă înainte de analiza sintactică. Un alt avantaj al metodei constă în faptul că pentru aceleaşi limbaj pot fi construite analizoare lexicale multiple, în funcţie de suportul de stocare a textului sursă.

3. Cele două analizoare funcţionează în regim de corutină, adică cele 2 faze sunt simultan active, transferând controlul una alteia atuci când este necesar.

Modelul ales în continuare este cel de analizor sintactic care apelează analizorul lexical (2).

3.2. Noţiuni specifice analizorului lexical. 3.2.1. Codificarea atomilor lexicaliMulţimea atomilor detectabili este organizată în clase de atomi. Fiecare atom detectat în

programul sursă primeşte o codificare internă (şir de informaţii) care descrie complet atomul respectiv: - clasa fiecarui atom- valoarea sa (dacă este un număr) sau adresa unde poate fi găsit dacă este un şir de caractere. Codul lexical este un număr întreg ce identifică atomul şi care este asociat în felul următor: dacă atomul lexical aparţine unei clase cu număr cunoscut de elemente (clasa operatorilor,

clasa cuvintelor cheie), fiecărui atom al clasei i se asociază un număr distinct. De exemplu: pentru "+"codul 16; pentru "-" codul 18; etc. Astfel, prin acest număr intern, atomul fi identificat complet.

clasei cu un număr nedeterminat de elemente (posibil infinit) i se asociază un unic cod intern; distincţia dintre atomii ce aparţin unei asemenea clase se face prin suplimentarea codului clasei cu alte informaţii. Astfel, la codul intern se adaugă adresa din tabela de simboluri, în timp ce în tabela de simboluri se memorează un identificator.

De exemplu:

7

- un simbol a va primi ca şi codificare codul clasei simbolurilor şi o adresă care pointează spre tabela de simboluri

-o constantă va primi ca şi codificare codul clasei constantelor şi valoarea constantei.

a clasa 1 tabela de simboluri 25 clasa 2 valoare adresa a valoare 25

identificator valoareInformaţiile suplimentare ataşate codului clasei atomului lexical se numesc atribute. În majoritatea

cazurilor, ca şi în cel de sus, este suficient un singur atribut: valoarea constantei (numere întregi, reale) sau valoarea adresei din tabela de simboluri.

Avantajul codificării atomilor lexicali constă în preluarea unitară de către analizorul sintactic a datelor furnizate de analizorul lexical, în sensul că analizorul sintactic nu va prelua atomii lexicali (şiruri de caractere de lungime variabilă), ci numere, codificări ale atomilor.

Exemplu: Deseori, un atom (token) are structura din secvenţa următoare:

#ifndef LEX_H #define LEX_H typedef enum { NAME, NUMBER, LBRACE, RBRACE, LPAREN, RPAREN, ASSIGN, SEMICOLON, PLUS, MINUS, ERROR } TOKENT; typedef struct

{ TOKENT type; union {int value; /* type == NUMBER */ char far* name; /* type == NAME */

}info; } TOKEN;

extern TOKEN lex(); /*functial lex() e definita altundeva)*/#endif LEX_H

Funcţia lex() este cea care returnează următorul atom din textul sursă.

3.2.2 ObservaţiiUnele limbaje de programare , îndeosebi cele vechi, conţin unele particularităţi care îngreunează

procesul de analiză lexicală. De exemplu FORTRAN şi COBOL impun o anumită structură a programului sursă pe mediul de intrare. Limbajele moderne au în exclusivitate formatul liber pe fişierul de intrare, aranjarea instrucţiunilor pe linii fiind făcută pe criterii de claritate şi lizibilitate. În ALGOL 68, spaţiile sunt nesemnificative, ceea ce duce la îngreunarea identificării atomilor în anumite instrucţiuni.

Există limbaje de programare în care cuvintele cheie nu sunt rezervate (PL/I), urmând ca analizorul lexical să deosebească din context cuvintele cheie de cele rezervate.

3.3. Construirea unui analizor lexical.Pentru construirea analizorului lexical se au în vedere următoarele aspecte: recunoaşterea atomilor

lexicali (cu genererarea codurilor de eroare în caz de eşec), furnizarea către analizorul sintactic a unei ieşiri ce codifică atomii lexicali şi introducerea în tablele compilatorului a datelor obţinute în această fază (identificatori , constante).

Un analizor lexical poate fi construit manual sau cu ajutorul unui generator de analizoare lexicale. - Construirea manuală a analizorului lexical înseamnă scrierea programului propriu zis pe baza

unor diagrame realizate în prealabil, care precizează structura atomilor din textul sursă. Tehnica manuală asigură creerea unor analizoare lexicale eficiente, dar scrierea programului e monotonă, prezintă riscul unor erori, mai ales dacă există un număr mare de stări.

8

Secvenţa următoare prezintă o implementare manuală simplă a unui scanner:

#include <stdio.h> #include <ctype.h> #include <stdlib.h>#include <string.h> / #include "lex.h"

static int state = 0;#define MAXBUF 256 static char buf[MAXBUF]; static char *pbuf; static char *token_name[] ={ "NAME", "NUMBER", "LBRACE", "RBRACE", "LPAREN", "RPAREN", "ASSIGN", "SEMICOLON", "PLUS", "MINUS", "ERROR" }; static TOKEN token; char far* dup_str ;/* Acest cod nu e complet. Nu se testeaza depasirea bufferului, etc*/TOKEN *lex(){char c;while (1)switch(state)

{case 0: /* pentru unul din 1,4,6,8,10,13,15,17,19,21,23 */pbuf = buf;c = getchar();if (isspace(c))

state = 11;else if (isdigit(c))

{*pbuf++ = c; state = 2;}

else if (isalpha(c)){*pbuf++ = c; state = 24;}

else switch(c){case '{': state = 5; break;case '}': state = 7; break;case '(': state = 9; break;case ')': state = 14; break;case '+': state = 16; break;case '-': state = 18; break;case '=': state = 20; break;case ';': state = 22; break;default:state = 99; break;}

break;case 2:c = getchar();if (isdigit(c))

9

*pbuf++ = c;else

state = 3;break;

case 3:token.info.value= atoi(buf);token.type = NUMBER;ungetc(c,stdin);state = 0; return &token;break;case 5:token.type = LBRACE;state = 0; return &token;break;case 7:token.type = RBRACE;state = 0; return &token;break;case 9:token.type = LPAREN;state = 0; return &token;break;case 11:c = getchar();if (isspace(c));elsestate = 12;break;case 12:ungetc(c,stdin);state = 0;break;case 14:token.type = RPAREN;state = 0; return &token;break;case 16:token.type = PLUS;state = 0; return &token;break;case 18:token.type = MINUS;state = 0; return &token;break;case 20:token.type = ASSIGN;state = 0; return &token;break;case 22:token.type = SEMICOLON;state = 0; return &token;break;case 24:c = getchar();if (isalpha(c)||isdigit(c))*pbuf++ = c;

10

elsestate = 25;break;case 25:*pbuf = (char)0;dup_str= strdup(buf); /*aloca spatiu*/token.info.name =dup_str;token.type = NAME; ungetc(c,stdin); state = 0; return &token; break; case 99: if (c==EOF) return 0; fprintf(stderr,"Caracter ilegal: \'%c\'\n",c); token.type = ERROR;

state = 0; return &token; break;

default: break; /* Nu se poate intampla */ } } int main() { TOKEN *t; while (((t=lex())!=0))

{ printf("%s",token_name[t->type]); switch(t->type){case NAME:

printf(":%s\n",t ->info.name); break;

case NUMBER:printf(":%d\n",t ->info.value); break;

default:printf("\n"); break;

} }

return 0; }

Fluxul procedurii lex() se poate reprezenta prin diagramele de tranziţii din figura următoare.

11

1. La preluarea unui nou atom (de exemplu la intrarea în lex() ) folosim starea specială state 0 pentru a reprezenta faptul că nu am decis încă ce diagramă să urmăm. Alegerea e făcută pe baza următorului caracter de intrare Uneori, de exemplu pentru atomul LBRACE atomul e recunoscut imediat prin scanarea ultimului caracter din atom. Pentru alţi atomi însă, de exemplu pentru NUMBER, cunoaştem lungimea atomului numai după citirea unui extracaracter care nu aparţine numărului (stări notate cu *). În acest caz, caracterul în plus trebuie returnat la intrare.

2. Dacă citim un caracter care nu corespunde cu o secvenţă acceptată, se returnează atomul special ERROR.

Diagramele de tranziţie sunt grafuri orientate şi etichetate în care nodurile simbolizează stările, iar arcele trecerea (tranziţia) dintr-o stare în alta.

- Generarea automată a analizorului lexical presupune conceperea unui program de traducere (un fel de compilator) care primeşte la intrare într-un limbaj de specificare, atât structura atomilor lexicali, cât şi eventualele acţiuni semantice care trebuiesc realizate împreună cu analiza lexicală. Ieşirea unui astfel de compilator va fi un program de analiză lexicală. Un astfel de compilator poate fi aplicat unei clase mai largi de limbaje.

4. Noţiuni generale de limbaje formale.C3

Limbajele de programare sunt modelate matematic în cadrul limbajelor formale. Studiul modelării limbajelor de programare are în vedere în primul rând, structurile finite care permit dezvoltarea de limbaje cu un număr infinit de fraze.

Calea uzuală de descriere formală a unui limbaj este de a folosi o gramatică pentru acel limbaj.

O gramatică G este definită de 4 componente:- O mulţime finită T de simboluri care pot apare în frazele limbajului, numite

simboluri terminale, sau primitivele limbajului.- O mulţime infinită N de simboluri neterminale, sau categorii sintactice, care sunt

utilizate pentru descrierea limbajului, dar nu apar în frazele acestuia. Deci, mulţimile T şi N sunt disjuncte.

- O mulţime P de reguli de generare sau producţii care descriu aspectele constructive ale acestuia

12

- Un simbol neterminal special S care apare doar într-o singură producţie din mulţimea P şi care se numeşte simbol iniţial, simbol de start sau axioma gramaticii. Producţiile sau regulile de generare din P arată cum pot fi construite toate frazele limbajului pornind de la simbolul neterminal S.

Deci, cvadruplul: G={N, T, P, S}, unde N, T, P, S au semnificaţiile menţionate,

constituie o gramatică.

Un alfabet A reprezintă o mulţime finită şi nevidă de simboluri. Un simbol din A este reprezentat printr-o literă, cifră sau semn, uneori printr-un şir finit de litere, cifre sau semne.

Se notează cu A* mulţimea aranjamentelor cu repetiţie ale simbolurilor din A, în care unele pot apărea de mai multe ori.

Exemplu: Pentru A1={(,)}, următoarele şiruri sunt elemente din A1*:( , ) (( ((( (()) () etc.

În A* există un şir care nu conţine nici un simbol din A. Acest simbol, numit şir vid îl notăm cu .

Un limbaj L peste alfabetul A este o submulţime a lui A*. Orice şir din A* care aparţine şi lui L este un simbol sau cuvânt al limbajului L.

Evident, mulţimea A* este infinită, deci şi limbajul L poate reprezenta o mulţime infinită. Acest lucru înlătură orice abordare de tip enumerativ în definirea limbajului, fiind necesară o reprezentare finită a mulţimii infinite.

Se disting două categorii de astfel de reprezentări:- reprezentarea (finită) sintetică care generează toate cuvintele limbajului şi

corespunde noţiunii de gramatică.- reprezentarea (finită) analitică care permite recunoaşterea apartenenţei sau

nonapartenenţei unei construcţii la limbajul considerat, reprezentare care corespunde noţiunii de automat sau analizor.

Cu notaţile definite se construiesc mulţimile: A = N T şi A+ = A* - {}. Reuniunea A = N T reprezintă alfabetul sau vocabularul gramaticii.

O producţie p P din gramatica G reprezintă o transformare de forma:

unde A+ şi A* .Fiind date şi două şiruri oarecare din A* se poate defini relaţia :

care specifică transformarea şirului concaternat în şirul pe baza regulii de generare existentă în mulţimea P a producţiilor.

Relaţia notată cu "" exprimă doar o singură transformare de la un şir la altul în cadrul gramaticii G, dar ea poate fi extinsă pentru a exprima o întreagă succesiune de transformări, sub una din formele:

1 * k k sau 1 +k k

Astfel se specifică că şirul k

este derivat (dedus) succesiv din şirul 1 prin aplicarea unei serii de transformări, (derivare în k paşi) prin utilizarea şirului nul (relaţia * k) sau prin neutilizarea acestui şir (relaţia + k).

Se poate defini un limbaj L generat de gramatica G ca fiind alcătuit din acele simboluri terminale din G, numite propoziţii, care derivă din simbolul iniţial S:

L(G) = { s | s T* şi S s}

O propoziţie, notată mai sus cu s conţine în exclusivitate simboluri terminale.

13

Orice şir de simboluri terminale şi neterminale derivat din axioma S este numit formă propoziţională.

-derivarea canonică stânga - este un şir de transformări în care neterminalul care se expandează este întotdeauna cel mai din stânga neterminal al formei propoziţionale

-derivarea canonică dreapta - este un şir de transformări în care neterminalul care se expandează este întotdeauna cel mai din dreapta neterminal al formei propoziţionale

Operaţia inversă derivării se numeşte reducere.

Un limbaj se poate descrie prin mai multe gramatici diferite.

Două gramatici se spune că sunt echivalente dacă şi numai dacă limbajele generate de fiecare din acestea sunt identice.

O gramatică se numeşte recursivă dacă permite derivări de forma:u + u , unde u N iar , A*

O gramatică este: - recursivă la stânga dacă: u + u w- recursivă la dreapta dacă: u + w u

Exemplu: Considerăm o gramatică care descrie un set restrâns de operaţii algebrice G = {N, T, P, S}

N = {S, <expr>, <term>, <fact>}T = {a, b, c, -, * }P = {S <expr>

<expr> < term> | <expr> - <term><term> <factor> | <term>*<factor> <factor> a | b | c }Să încercăm să vedem dacă expresia a-b*c aparţine sau nu gramaticii.S <expr> <expr>-<term> <fact> - <term> a - <term> a- <term>*<factor> a - <factor>* <factor> a - b* <fact> a - b * c

Se observă că propoziţia a - b * c s-a obţinut în urma a 11 derivări, substituind la fiecare pas câte un simbol în forma propoziţională curentă.

4.1. Tipuri de gramatici şi limbaje

După forma producţiilor, N. Chomsky a împărţit gramaticile în 4 mari clase: gramatici de tip 0 - este forma cea mai generală de gramatică, făra restricţii, de tipul

celei prezentate mai sus. gramatici de tip 1 - sunt gramatici dependente de context (sensibile la context); ele au

producţii de forma u , adică producţia u se poate aplică doar dacă u apare în contextul u . Gramaticile dependente de context generează limbaje dependente de context.

gramatici de tipul 2 - sunt gramatici independente de context de forma u , adică derivarea are loc independent de contextul în care se află u.

gramatici de tipul 3 - se numesc gramatici regulate, în care părţile drepte ale producţiilor încep cu un terminal. Clasa mulţimilor regulate peste alfabetul A reprezintă clasa limbajelor regulate L3(A).

Notând cu Gi clasa gramaticilor de tipul i, N. Chomsky a ademonstrat că există următoarele relaţii de incluziune între gramatici:

14

G0 G1 G2 G3 iar pentru limbaje incluziunile sunt stricte : L0 L1 L2 L3.

Dintre cele 4 tipuri de gramatici, doar gramaticile regulate şi cele independente de context şi-au găsit o aplicabilitate practică în construirea limbajelor de programare. Celelalte două tipuri de gramatici prezintă un interes pur teoretic.

Gramaticile regulate sunt un caz particular al gramaticilor independente de context. De aceea se spune că limbajele formale independente de context modelează limbaje de programare.

Un limbaj poate fi generat de o gramatică regulată dacă el poate fi recunoscut de un automat finit.

Dacă în producţiile gramaticii independente de context se foloseşte un singur tip de recursivitate la

stânga sau la dreapta, ea devine o gramatică regulată.

Sintaxa unei propoziţii într-un limbaj independent de context se poate reprezenta printr-o structură de arbore, numit arbore de derivare (sau deducţie). Pentru recunoaşterea unei propoziţii dintr-un limbaj, este necesar ca arborele asociat să fie unic. În caz contrar, gramatica care generează limbajul se numeşte ambiguu.

Un limbaj este inerent ambiguu dacă nu poate fi generat decât de o gramatică ambiguă.Există posibilitatea ca prin modificarea setului de producţii ale unei gramatici ambigue să

se poată elimina ambiguităţile existente, fără ca limbajul generat să sufere vreo modificare.

Producţii vide

Partea dreaptă a unei producţii conţine un şir de terminale sau neterminale. Uneori este util să se genereze un şir vid, adică un şir ce nu conţine nici un simbol. Acest şir este notat cu e.De exemplu, gramatica

<unsigned integer> <digit> <rest of integer><rest of integer> <digit><rest of integer> | <digit> 0 | 1 | …|9

defineşte <rest of integer> ca o secvenţă de 0 sau mai multe cifre.Producţia <rest of integer> e se numeşte producţie vidă. În general, dacă pentru un şir este valabilă o derivare de forma *, atunci se numeşte simbol anulabil. Un neterminal este anulabil dacă există o producţie a cărei definiţie (parte dreaptă) este anulabilă.

4.2. Aspecte privind definirea limbajelor de programare

Pentru descrierea unui limbaj de programare este necesară adoptarea unui limbaj de descriere corespunzător, numit metalimbaj. Această idee aparţine lui John Backus şi notaţia introdusă de el este cunoscută sub numele de BNF (Backus Naur Form).

O producţie defineşte o clasă sintactică (simbol neterminal) sub forma generală:

< nume clasă sintactică> :: = definiţie

- Notaţia :: = are semnificaţia : "definit prin"- clasa sintactică, denumită şi partea stângă, corespunde unui simbol neterminal şi este

inclusă între paranteze unghiulare.- partea de definiţie este denumită şi partea dreaptă

15

Simbolurile terminale nu sunt incluse în perechea de paranteze unghiulare şi ele apar în propoziţiile limbajului.

BNF utilizează un set restrâns de metasimboluri ( | < > :: =) şi un set (specific limbajului) de

simboluri terminale.

Formalismul BNF impune nişte restricţii asupra regulilor de generare:

- fiecare clasă sintactică (simbol neterminal) trebuie să apară în partea stângă a unei singure producţii;

- simbolul de start nu trebuie să apară în partea stângă a nici unei producţii;

Ulterior s-au utilizat variante şi completări la notaţia BNF pentru a se descrie diferite limbaje de programare.

Pentru a creşte lizibilitatea notaţiilor, s-au adoptat prescurtări inspirate de metasimbolurile folosite pentru expresii regulate.

Aceste notaţii extinse au denumirea de forma Backus Naur extinsă EBNF.

De exemplu pentru următoarea gramatică de descriere a întregilor cu semn:<integer> <sign> <unsigned integer><unsigned integer> <digit> <unsigned integer><sign> + | - |

folosind EBNF se va rescrie:<unsigned integer> <digit> (<digit>)*sau mai restrans:<integer> (+ | - | )<digit> (<digit>)*

Extensii introduse de Wirth

În definirea limabjelor Pascal şi Modula-2, 1977, Wirth a introdus câteva extensii la forma originală de notaţie, obtinând o formă extinsă care a devenit larg utilizată:

neterminale - sunt scrise cu litere italice instructiuneterminale - litere drepte şi între apostrofuri ‘begin’| () - au semnificaţia din notaţia originală[] - semnifică aparitia opţională a şirului dintre paranteze{} - denotă repetiţia de 0 sau mai multe ori a şirului. - marchează sfârşitul fiecărei producţii(* *) - simboluri pentru comentarii - se înlocuieşte cu []

Exemplu: unsigned integer ::= digit {digit} digit ::= ‘0’ | ‘1’ | ‘2’ | …| ‘9’.

4.3. Automate de recunoaştere. Diagrame de tranziţie.

Pe baza gramaticii limbajului stabilit pentru atomi, analizorul lexical are sarcina să decidă apartenenţa la limbaj a atomilor detectaţi în fişierul de intrare. Pentru gramatici regulate, problema apartenenţei la limbaj este decidabilă.

Problema deciziei trebuie completată cu sarcina codificării atomilor lexicali, cu cea a semnalării şi tratării erorilor.

16

Gramaticile de descriere a atomilor lexicali oferă analizorului lexical tiparele pentru identificarea atomilor. Pe baza acestor gramatici, implementarea procesului de recunoaştere a atomilor se face folosind un model matematic, numit automat de recunoaştere sau automat finit.

Modelul fizic al unui automat finit este o "maşină" cu operaţii foarte simple care are un cap de citire, o unitate de comandă şi opţional o memorie. Maşina citeşte câte un caracter de pe banda de intrare şi unitatea de comandă decide în ce stare trece automatul pe baza caracterului citit. Automatul se poate afla într-un număr finit de stări.

În momentul în care automatul începe citirea unui caracter, acesta se află în starea numită starea de start. Automatul are un număr de stări numite, stări finale. Un şir x este acceptat de automat dacă pornind din starea de start, după citirea tuturor caracterelor din şirul de intrare, automatul ajunge într-o stare finală. Cu alte cuvinte, şirul aparţine limbajului acceptat de automat.

Modelul matematic de reprezentare a automatului finit este acela al diagramelor de tranziţii.

- Simbolurile care etichetează arcele indică caracterul la citirea căruia automatul va trece din starea de la care porneşte arcul în starea în care ajunge arcul respectiv.

- Săgeata etichetată cu cuvântul "start" indică nodul de start al diagramei de tranziţii, ori poate fi o săgeată de intrare neetichetată.

- Pentru a indica orice alt caracter care poate urma la ieşirea unei stări, în afara celor deja trecute pe arcele care ies din starea respectivă, se va utiliza o etichetă specială "altceva".

- Diagramele de tranziţii sunt deterministe, adică acelaşi simbol nu poate eticheta două sau mai multe tranziţii care ies din aceeaşi stare.

- Unei tranziţii, pe lângă simbol i se pot asocia şi anumite acţiuni care se vor executa în momentul când fluxul de comandă trece prin tranziţia respectivă.

Exemplu:

În general analizorul lexical este format din mai multe astfel de diagrame de tranziţii care pornesc

din aceeaşi stare de start şi recunosc grupe de atomi. Dacă parcurgând o anumită diagramă se semnalează

eşec, se revine în starea de start şi se trece la următoarea diagramă. Revenirea în starea de start presupune şi

revenirea capului de citire în poziţia anterioară încercării nereuşite. Readucerea capului de citire se poate

face memorând adresa locaţiei cu citirea căreia a început ultima recunoaştere. Dacă prin parcuregerea

secvenţială a tuturor diagramelor de tranziţii. se va semnala eşec la toate, înseamnă că s-a gasit o eroare

lexicală şi se va apela rutina de tratare a erorii.

Un alt aspect al analizei lexicale îl constituie comunicarea datelor detectate de analizorul lexical analizorului sintactic, generearea erorilor lexicale şi, dacă este necesar, introducerea datelor în tabelă. Pentru realizarea acestor sarcinci, diagramele de tranziţii se completează cu proceduri semantice asociate cu tranziţiile din diagramă. Aceste proceduri semnatice fie

17

generează ieşiri către analizorul sintactic, realizând şi gestionarea tabelelor, fie tratează erorile lexicale.

4.4. Exemplu de gramatică a atomilor lexicali şi diagrame de tranziţii

În cele ce urmează, dăm notaţia BNF a unei gramatici a atomilor lexicali, reprezentative pentru majoritatea limbajelor de programare. Notam G0 această gramatică.

1. < şir atomi>::=<atom> | <şir atomi> < atom>2. < atom>::= <id> | <const> | <op> | <del> | <com>3. <id> ::=<lit> | <id> <lit> | <id><cif>4. <const>::= <cif> | <const> | <cif>5. <op>::= + | * | < | <= | > | >= | = | <> 6.<del>::= ; |blanc7. <com>::= (* < orice şir de caractere ce nu conţine grupul '*)'> *)8. <lit>::= A | ... | Z 9. <cif>::= 0 | ... | 9Gramatica G0 nu este regulată dar poate fi transformată uşor într-o gramatică

regulată mărind numărul producţiilor şi al neterminalelor. Procedând astfel însă, gramatica se complică şi procesul de proiectare al analizorului se poate lungi.

De exemplu, producţiile 4 se pot scrie: <const>::= 0 | ... | 9| <const>0 | | <const>1| …| <const>9 Se preferă o simplificare a gramaticii prin "stratificarea" gramaticii G0 într-o ierarhie de

gramatici mai simple, care fiecare în parte este regulată, sau se transformă în gramatică regulată. Pentru fiecare din aceste gramatici se va construi diagrama de tranziţie, iar în final se asamblează diagramele astfel încât limbajul în ansamblu rămâne acelaşi.

Se partţionează mulţimea de neterminale şi se stabileşte o ierarhie între elementele partiţiei. În exemplul dat, o asemenea partiţionare este:

N1={<sir atomi>, <atom>}N2={<id>, <const>, <op>, <del>, <com>}N3={<lit>, <cif>}Formăm, în jurul celor trei mulţimi, gramatici plecând de la producţiile lui G0. Pentru fiecare gramatică vom considera ca terminale, pe lângă terminalele lui G0 şi

neterminalele din grupul imediat inferior din ierarhie. Noile gramatici sunt:(G1) :< şir atomi>::=<atom> | <şir atomi> < atom> < atom>::= id | const | op | del | com

(G21) :<id> ::=lit | <id> lit | <id>cif(G22) :<const>::= cif | <const> | cif(G23) :<op>::= + | * | < | <= | > | >= | = | <> (G24) :<del>::= ; |blanc(G25): <com>::= (* < orice şir de caractere ce nu conţine grupul '*)'> *)

(G31) :<lit>::= A | ... | Z (G32): <cif>::= 0 | ... | 9

Gramaticile sunt regulate cu excepţia lui G1 şi G25. Gramatica G1 se poate rescrie într-o formă EBNF:(G1) :< şir atomi>::=(id | const| op| del| com) | (id | const| op| del| com)*

18

G25 s-ar putea şi ea rescrie într-un mod asemănător, dar se preferă construirea automatului direct din această formă intuitivă.

În figura următoare se prezintă diagramele de tranziţii ale automatelor finite echivalente cu gramaticile G1, G2i ( i = 1, …, 5) G3j (j = 1,2):

19

Din analiza diagramelor, observăm că efectul stratificării constă în existenţa unor tranziţii condiţionate de terminale care pe nivelul inferior reprezintă diagrame de tranziţii. Acest lucru înseamnă că nu putem activa o asemenea tranziţie pe nivelul superior decât dacă diagrama de tranziţie respectivă de pe nivelul inferior a fost parcursă din starea iniţială într-o stare finală.

Deci, un automat aflat pe un nivel inferior trebuie să transmită nivelului superior informaţia de acceptare a şirului inspectat.

Vom avea deci o asamblare a automatelor ca în figura următoare:

20

Cuplarea automatelor A1, A2, A3 se face în serie, ieşirea unuia fiind intrarea celuilalt.Pentru a putea descrie funcţionarea automatului A0 printr-un limbaj de programare, trebuiesc îndeplinite două condiţii:

- Automatele rezultate din diferite cuplări trebuie să fie deterministe- Orice simbol primit la intrarea unui automat şi care nu activează nici o tranziţie

trebuie să ducă la o situaţie de neacceptare sau de eroare.Observaţie:

Există situaţii în care, pentru identificarea unui simbol, un automat consumă un simbol care aparţine atomului următor. Soluţiile de implementare constau fie în revenirea în şirul de intrare cu un simbol, fie în generalizarea avansului pentru toate stările finale.

Completarea diagramei de tranziţii cu proceduri semantice.

În proiectarea analizorului lexical, automatul de recunoaştere are un rol orientativ. El arată care sunt sarcinile analizorului în identificarea atomilor lexicali.

Pentru semnalarea erorilor şi emiterea unor ieşiri, se folosesc proceduri semantice asociate tranziţiilor automatului de recunoaştere.

Procedurile semantice lucrează cu cu structuri de date pe care le utilizează în luarea deciziilor şi pe care, eventual, le modifică. Aceste structuri de date alcătuiesc baza de date a analizorului lexical şi controlul contextului activităţii lui.

Controlul contextului are ca scop restabilirea – la sfârşitul analizei unui atom lexical – a unui context adecvat căutării următorului atom, emiterea unei ieşiri corecte care să reprezinte atomul analizat şi semnalarea erorilor.

4.5. Probleme specifice implementarii unui analizor lexical

4.5.1. Gestionarea tampoanelor de intrare

Textul sursă parcurs şi analizat de analizorul lexical este citit de pe suportul de intrare. Pentru efectuarea acestei operaţii se recomandă utilizarea a 2 zone tampon din următoarele motive:

- Poate creşte viteza prin umplerea unui tampon când analizorul lucreaza cu celălalt- Se poate trata simplu cazul în care un atom se continuă dintr-un tampon în altul.

21

Soluţiile concrete de gestiune ale tampoanelor depind de modul de implementare al analizorului:

1. Utilizarea unui generator de analizoare lexicale: rutinele pentru gestiune sunt incluse in generator, şi nu se află sub controlul programatorului.

2. Analizorul se scrie intr-un limbaj de nivel inalt. Posibilităţile de gestionarea tampoanelor sunt cele specifice limbajului.

3. Analizorul se scrie în limbaj de asamblare. Tampoanele se pot gestiona în modul explicit la cel mai scăzut nivel.

Eficienţa şi efectul cresc de la 1 la 3 Notăm cu n dimensiunea tamponului; ea corespunde lungimii dimensiunii fizice (linie, articol) pe mediul de intrare. Fiecare tampon se umple printr-o singură comandă de citire iar sfârşitul textului este marcat de EOF

Pentu localizarea atomului lexical (lexemei curente) în tampoane se utilizează pointeri numiţi pointeri de inceput pi şi pointeri de anticipare pa.

La început, ambii pointeri indică primul caracter al lexemei curente, apoi p a avanseaza până când analizorul găseşte corespondenţa cu un tipar. Şirul de caractere dintre cei doi pointeri reprezintă următorul atom lexical.

După detectarea unui atom lexical, pointerul de anticipare poate sa rămână ori pe ultimul caracter al lexemei curente ori pe primul caracter al lexemei următoare. Din motive de uniformitate se preferă a doua situaţie.

După prelucrarea lexemei curente, pi este adus în aceeaşi poziţie cu pointerul de anticipare, situaţie în care se poate trece la analiza unui nou atom.

Trecerea pointerului pi din primul tampon în al doilea trebuie precedată de umplerea (citirea) celui de-al doilea tampon, operaţie care se poate desfasura în paralel cu analiza propriu zisă când sistemul de calcul şi limbajul permite acest lucru. Analog, trecerea pointerului pa din al doilea tampon în primul în mod circular, trebuie precedată de umplerea (citirea) tamponului 1. Această tehnică poate fi aplicată atunci când lungimea maximă a unei lexeme nu poate depăşi 2n, ceea ce este o limitare rezonabilă.

Algoritmul de avans al lui pa pentru situaţia de mai sus este următorul:if * pa este la sfirsitul tamponului 1 then

begin * incarca tamponul 2; pa:= pa +1;end

else if * pa este la sfirsitul tamponului 2 thenbegin * incarca tamponul1; pa:=1;end

else pa:= pa +1 Principalul dezavantaj al acestui algoritm îl reprezintă faptul că pentru fiecare caracter

(exceptând sfârşitul tamponului 1, avansul pointerului de anticipare este precedat de 2 teste.Cele două teste se pot reduce la unul singur dacă se marchează sfârşitul fiecărui tampon

cu un caracter special numit santinelă, care să fie acelaşi cu cel de sfârşit EOF .

Algoritmul se modifică astfel:pa = pa +1;if pa = EOF then if* pa este la sfirsitul tamponului 1 then begin *incarca tapon2

22

pa:= pa +1 end

else if * pa este la sfirsitul tamponului 2 then begin

*incarca tampon 1 pa :=1 end

else *termină analiza lexicală.Se mai remarcă şi faptul că acelaşi unic test de sfârşit de tanpon rezolvă şi testul de

sfârşit al textului sursă necesar pentru încheierea analizei lexicale.

4.5.2. Scrierea codului pentru diagramele de tranziţii

Din punct de vedere al programării, o secvenţă de diagrame de tranziţii poate fi implementată fie prin case fie prin succesiune de if. Pentru aceasta fiecărei stari i se asociază o porţiune de program distinctă. - Dacă starea nu este finală, adică există arce care ies din acea stare, atunci porţiunea de program se încheie cu citirea unui caracter pe baza căruia se pot selecta tranziţii spre stare următoare, dacă există arc de ieşire etichetat cu acel caracter. Citirea unui caracter se poate face cu o procedură care gestionează tamponul de intrare, avansează pointerul de anticipare şi returnează următorul caracter.

- Dacă există arc pornind din starea curentă etichetat cu caracterul citit se va transfera controlul la secvenţa de program pentru noua stare.

- Dacă nu există un astfel de arc şi starea curentă nu este finală, se va apela o procedură eşec care returnează pointerul de început al atomului lexical şi asigură saltul la următoarea diagramă. În cazul când s-au epuizat toate posibilităţile, se va apela procedura de eroare.

Dacă limbajul nu are case, acesta poate fi simulat printr-un tablou (indexat prin codul caracterului

de la intrare). Fiecare element al tabloului corespunde unei stări noi şi reprezintă un pointer spre o secvenţă

de cod ce trebuie executată atunci când caracterul curent corespunde indicelui. Porţiunea de

corespunzătoare fiecărei stări se va încheia fie cu luarea în considerare a stării următoare, fie cu salt la

tabloul corespunzător următoarei diagrame.

5. Construirea automată a analizoarelor lexicale C4Un generator de analizoare lexicale porneşte de la expresiile regulate care descriu toţi atomii

limbajului sursă şi obţine diagrama de tranziţie corespunzătoare, sub forma unei tabele de analiză. Această tabelă, împreună cu procedura de analiză alcătuiesc analizorul lexical.5.1.Obţinerea tabelei de analiză pe baza expresiilor regulate

Există două metode de transformare a expresiilor regulate în automate finite deterministe.Metoda I Această metodă presupune parcurgerea următoarelor etape:

a.Construirea unui automat finit nedeterminist (AFN) pornind de la expresiile regulate (ER).

23

b.Transformarea automatului nedeterminist (AFN) în automat finit determinist (AFD).

c.Minimizarea numărului de stări ale automatului determinist.

Metoda II Această metodă presupune parcurgerea următoarelor etape:a.Construirea arborelui binar corespunzător ER.b.Construirea AFD pe baza arborelui.

5.1.1. Construirea unui automat finit nedeterminist din expresii regulateÎn diagramele de tranziţii folosite până acum, am implementat automate finite deterministe,

(AFD)de genul celui din figura următoare:

Din fiecare stare iese o singură săgeată etichetată cu un simbol de intrare. Matricea de tranziţii

pentru acest automat este:

Dacă renunţăm la unele restricţii şi permitem ca dintr-un nod să iasă mai multe săgeţi etichetate cu

acelaşi simbol de intrare, precum şi săgeţi etichetate cu - care vor reprezenta tranziţii independente de

intrare – obţinem un automat finit nedeterminist. (AFN), prezentat în Figura 2.

Unei stări şi unui simbol de intrare nu îi mai corespunde o stare ci o mulţime, eventual vidă de stări.

Matricea de tranziţii pentru acest automat este:

24

Evident, AFD este un caz particular al AFN. Pornind de la expresii regulate, se pot construi automate finite nedeterministe.Fie o expresie regulată R peste un alfabet . Algoritmul de mai jos va genera un automat

finit nedeterminist N, care va accepta limbajul definit de R.Se descompune expresia R în componentele sale elementare (simboluri şi operatori). Se

vor construi automate elementare pentru fiecare simbol, după care, folosind aceste automate, se vor construi automatele pentru expresiile compuse. Automatele pentru expresiile compuse se construiesc inductiv, pentru fiecare operaţie : reuniune, concatenare, inchidere. Algoritmul de construcţie introduce la fiecare pas cel mult 2 stări noi, prin urmare, automatul rezultat va avea cel mult de 2 ori atâtea stari câte simboluri si operaţii are expresia regulată.

Algoritmul lui Thomson prezentat în continuare, nu este cel mai eficient (un algoritm mai performant ar genera un AFN cu mai puţine stări pentru aceeaşi expresie regulată). Are însă avantajul simplităţii, iar după transformarea din automat nedeterminist în automat determinist, există posibilitatea reducerii numărului de stări ale automatului finit determinist obţinut.

Folosim următoarele notaţii: i - stare iniţialăf - stare finalăN(Ri) - automatul corespunzător expresiei regulate Ri.

- Pentru (simbolul vid notat şi ) se generează:

- Pentru a ( un simbol oarecare al alfabetului sursă):

Pentru fiecare AFN elementar construit, stările vor fi notate cu nume (numere) distincte; dacă un

acelaşi simbol al alfabetului apare de mai multe ori în ER, se va construi pentru fiecare apariţie a sa câte un

AFN separat, cu stări notate distinct.

În continuare, se conectează între ele AFN elementare construite, corespunzător operatorilor aplicaţi asupra primitivelor din ER, compunându-se astfel, din aproape în aproape (prin inducţie) AFN final.

Descompunerea ER în componente elementare, respectiv compunerea acestora se face aducând ER la forma postfix, tinând cont că operatorii se evaluează în ordinea următoare: parantezele, închiderea ( * ), concatenarea si selecţia (|).- Pentru R1|R2

25

Automatul corespunzător expresiei R1 | R2, este N(R1 |R2), obţinut prin creerea a 2 stări noi: o stare iniţială, diferită de stările iniţiale ale automatelor N(R1) şi N(R2) şi o stare finală diferită de stările finale din N(R1) şi N(R2), care îşi pierd proprietatea de satre iniţială şi finală.

Limbajul corespunzător expresiei regulate R1 |R2 este: L(R1) L(R2).- Pentru R1R2

Automatul corespunzător expresiei R1R2 este N( R1R2) pentru care starea iniţială este starea se start a automatului N(R1) iar starea finală este cea a automatului N(R2). Starea finală a automatului N(R1) se identifică cu starea se start a automatului N(R2).

Un drum între i şi f va traversa mai întâi automatul N(R1), după care va trece prin automatul N(R2). Prin urmare, şirul de simboluri recunoscut va fi un şir din limbajul expresiei R 1

urmat de un şir al limbajului expresiei R2. În consecinţă, limbajul modelat de automat este: L(R1)L(R2).- Pentru R1*

Automatul are 2 stări noi şi ne putem deplasa din starea iniţială i în starea finală f, fie direct prin tranziţia , fie prin automatul N(R1), de un număr oarecare de ori.

Un automat obţinut pe baza algoritmului lui Thomson are următoarele proprietăţi:

-AFN final va avea o singură stare de start şi o singură stare finală.- Fiecare stare a automatului are cel mult o tranziţie etichetată cu un simbol din alfabet sau cel mult 2 tranziţii etichetate cu .

Aplicaţie: Se consideră expresia regulată R = (aba)*aa . Automatul construit pas cu pas, pornind de la această expresie este:

26

5.1.2. Transformarea AFN în AFDUn AFN se poate transforma într-un automat finit determinist (AFD) care să accepte acelaşi

limbaj ca şi AFN. Notăm cu s0 starea iniţială a AFN. O stare a AFD va fi compusă dintr-o mulţime de stări {s1, s2,..., sn

} ale AFN. Noţiunea de -închidere se defineşte pentru fiecare mulţime de stări T ale unui automat:

este mulţimea stărilor în care se poate trece din stările mulţimii T pentru un simbol de intrare.Exemplu: Pentru automatul din Figura 2, prin tranziţii vide, -închidere(0) = {0,2}, -

închidere(1) = {1}, -închidere(0, 3) = {0,2,3} etc.Notăm: alfabetul limbajului sursă

Dstări mulţimea stărilor AFDDtranz mulţimea tranziţiilor

Pentru implementarea algoritmului putem folosi ca structuri de date două stive şi un şir de cifre binare indexat de stările automatului. Într-una din stive se ţine evidenţa mulţimii curente a stărilor nedeterministe iar a doua stivă se utilizează pentru calculul mulţimii de stări următoare. Vectorul de cifre binare înregistrează dacă o stare este prezentă în stivă, pentru a se evita dublarea ei. Organizarea acestei structuri ca vector are avantajul timpului de căutare constant al unei stări. După încheierea procesului de calcul a mulţimii de stări următoare, rolul stivelor se inversează.

Se iniţializează stările AFD căutat Dstări cu un singur element (o stare), şi anume cu mulţimea stărilor în care se poate ajunge din starea s0 a AFN numai prin tranziţii vide (de fapt -închidere({s0}), care va fi notată cu -închidere({s0}).

La început această stare e nemarcată. Totodată, mulţimea tranziţiilor este vidă.Pentru fiecare stare nemarcată din Dstări şi pentru fiecare simbol din alfabet se caută stările în

care se poate ajunge în AFN pentru simbolul respectiv. Adaugă aceste stări la Dstări dacă ele nu sunt deja incluse în această mulţime, adaugă tranziţia la Ditranz şi marchează starea testată din Dstări. Algoritmul de obţinere a AFD este:

procedura AFN2AFD este *iniţializează Dstări cu -închidere({s0}) *la început stările din Dstări sunt nemarcate Dtranz = cât timp mai există în Dstări o stare x = {s1, s2,. . ., sn } nemarcată execut ă

*marchează xpentru fiecare a execut ă *fie T = mulţimea stărilor din AFN pentru care o tranziţie etichetată cu a de la o

stare si x; y = -închidere(T);

27

dac ă y Dstări atunci *adaugă y la Dstări, y - nemarcată*adaugă tranziţia x y la Dtranz, dacă nu există deja

€€

€sfâr ş it AFN2AFD

Algoritmul de calcul pentru funcţia -închidere este:func ţ ia -închidere( T ) este *pune toate stările din T într-o stivă *iniţializează -închidere( T ) cu T cât timp stiva nu e vidă execut ă

*extrage starea s din vârful stiveipentru fiecare stare t pentru care s t pentru simbolul execut ă dac ă t -închidere( T ) atunci *adaugă t la -închidere( T )

*pune t în stivă €€

€sf â r ş it -închidere( T )

Exemplu: Fie AFN din figura 7. Limbajul acceptat este: {a, b, ab, abab, …}.

Aplicăm algoritmul AFN2AFD pe diagrama de tranziţii.

Dstări = {(0,1,4)} Dtranz =

Se marchează cu * starea (0,1, 4)- Pentru simbolul a construim mulţimea {2, 5} şi calculăm -închidere ({2, 5}) = {2, 5, 7}

Dstări = {(0,1,4)* , (2, 5, 7)} Dtranz = {(0,1,4)(2, 5, 7) cu simbolul a}

28

- Pentru simbolul b construim mulţimea {6}şi calculăm -închidere ({6}) = {6, 7}

Dstări = {(0,1,4)* , (2, 5, 7), (6, 7)} Dtranz = {(0,1,4)(2, 5, 7) cu a; (0,1,4)(6,7) cu b }

Se marchează cu * starea (2, 5, 7)- Pentru simbolul a nu avem tranziţii

- Pentru simbolul b construim mulţimea {3}şi calculăm -închidere ({3}) = {1, 3, 7}

Dstări = {(0,1,4)* , (2, 5, 7)*, (6, 7), (1, 3, 7)}

Dtranz = {(0,1,4)(2, 5, 7) cu a; (0,1,4)(6,7) cu b ; (2, 5, 7) (1, 3, 7) cu b}

Se marchează cu * starea (6,7)- Pentru simbolul a nu avem tranzitii

- Pentru simbolul b nu avem tranziţii

Dstări = {(0,1,4)* , (2, 5, 7)*, (6, 7)*, (1, 3, 7)}

Dtranz = {(0,1,4)(2, 5, 7) cu a; (0,1,4)(6,7) cu b ; (2, 5, 7) (1, 3, 7) cu b}

Se marchează cu * starea (1, 3, 7)- Pentru simbolul a construim mulţimea {2}şi calculăm -închidere ({2}) = {2}

Dstări = {(0,1,4)* , (2, 5, 7)*, (6, 7)*, (1, 3, 7)*, (2)}

Dtranz = {(0,1,4)(2, 5, 7) cu a; (0,1,4)(6,7) cu b ; (2, 5, 7) (1, 3, 7) cu b; (1, 3, 7) (2) cu a }

- Pentru simbolul b nu avem tranziţii

Se marchează cu * starea (2)- Pentru simbolul a nu avem tranziţii

- Pentru simbolul b construim mulţimea {3}şi calculăm -închidere ({3}) = {1, 3, 7}, dar ea există.

Dstări = {(0,1,4)* , (2, 5, 7)*, (6, 7)*, (1, 3, 7)*, (2)*}

Stările pot fi redenumite, de exemplu:

(0,1,4) = A

(2, 5, 7) = B

(6, 7) = C

29

(1, 3, 7) = D

(2) = E

Matricea şi diagrama de tranziţii pentru AFD parţial definit sunt cele din Figura 8.Se observă că AFD obţinut acceptă exact limbajul {a, b, ab, abab, …} acceptat de AFN

iniţial.Stările acceptoare (finale) ale AFD obţinut vor fi acele stări x care vor conţine cel puţin o

stare acceptoare a AFN. Starea de start a AFD este cea formată din s0 împreună cu toate stările la care se poate ajunge din s0 doar prin simbolul .

Algoritmul de mai sus este important pentru că dă soluţia pentru simularea unui AFN. Simularea directă este dificilă, deoarece trebuie simulat calculul "în paralel" al diferitelor traiectorii ce pot fi urmate în AFN. Folosind algoritmul, se determină mai întâi AFD echivalent şi apoi se simulează AFD. Această simulare este echivalentă cu construirea analizorului limbajului generat de gramatică.

5.1.3. Algoritm pentru simularea comportării unui automat finit nedeterministSe consideră un automat N construit dintr-o expresie regulată prin metoda Thomson. Se

prezintă algoritmul de simulare care va decide dacă automatul N recunoaşte sau nu un şir de intrare x. Răspunsul automatului va fi “da” în cazul recunoaşterii şi “nu” altfel.

- Algoritmul citeşte intrarea simbol cu simbol (carurm)- Calculează pentru fiecare mulţime de stări T mulţimea stărilor în care se poate trece din

stările din T numai prin tranziţii vide. ( închidere).- Verifică dacă se poate ajunge într-o stare acceptoare.

S:= - închidere(S0);a:= carurm;while a eof dobegin

S:= - închidere(S,a);a := carurm;

end;if SF then generează(“da”)

else generează(“nu”);Pentru implementarea algoritmului putem folosi ca structuri de date două stive şi un şir

de cifre binare indexat de stările automatului. Într-una din stive se ţine evidenţa mulţimii stărilor curente, iar a doua stivă se utilizează pentru calculul mulţimii de stări următoare. Vectorul de cifre binare înregistrează dacă o stare este prezentă în stivă, pentru a se evita dublarea ei.

30

Organizarea acestei structuri ca vector are avantajul timpului de căutare constant al unei stări. După încheierea procesului de calcul a mulţimii de stări următoare, rolul stivelor se inversează.

5.1.4. Minimizarea numărului de stări ale unui AFDAutomatul finit determinist obţinut din automatul finit nedeterminist nu este întotdeauna

cel mai simplu posibil pentru şirul de intrare dat. Uneori este posibilă reducerea numărului de stări ale AFD astfel obţinut.

Se prezintă un algoritm care, în caz că este posibil, reduce numărul de stări ale unui AFD.O stare s a unui AFN este o stare importantă dacă are cel puţin o tranziţie etichetată cu un

simbol diferit de . De exemplu, în algoritmul de conversie AFN-AFD, stările importante au fost cele care au determinat creerea unei noi stări în AFD.

Considerând mulţimile de stări din AFN corespunzătoare la 2 stări din AFD, 2 submulţimi sunt identice dacă:

1. ele au aceleaşi stări importante2. ambele fie includ, fie exclud stări acceptoare

Algoritmul de minimizare :Considerăm că avem un AFD notat M, având mulţimea stărilor notată cu S, iar

reprezintă mulţimea de simboluri de intrare. Presupunem că fiecare stare are o tranziţie pentru fiecare simbol de intrare. Dacă AFD nu îndeplineşte această condiţie, vom crea o stare fictivă, numită “stare de blocaj”, m din care vom trasa arce spre el însuşi pentru fiecare simbol de intrare. Pentru toate stările care nu au tranziţii pentru toate simbolurile, tranziţiile lipsă se vor completa cu arce spre starea m.

Iniţial divizăm mulţimea stărilor AFN în 2 submulţimi, una conţinând stările care nu sunt finale, celalată conţinând mulţimea stărilor finale. Algoritmul va partiţiona aceste mulţimi astfel încât două stări din aceeaşi mulţime vor trece în aceeaşi mulţime de stări pentru orice simbol de intrare.

Considerăm P o partiţie obţinută la un moment dat în procesul de partiţionare, S=s1,s2,…,sk una din mulţimile partiţiei şi un simbol de intrare a. Căutăm pentru fiecare stare s i starea în care trece pentru simbolul a. Dacă stările următoare obţinute aparţin la mulţimi diferite din P, mulţimea S se va împărţi în submulţimi ale căror elemente duc în aceeaşi submulţime din P. Procesul de divizare se repetă până când nu mai găsim grupuri ce trebuiesc divizate.

i) Se realizează o partiţionare P a multimii Dstari în două grupuri de stări: F=setul de stări acceptoare şi Dstari - F = setul de stări non-acceptoare. Printr-o procedură, care se va da mai jos, se încearcă efectuarea unei noi partiţionări, Pnou, prin descompunerea grupurilor lui P în subgrupuri. Dacă Pnou P, se înlocuieşte P cu Pnou şi se repetă procedura de descompunere. Dacă Pnou P, înseamnă că partiţionarea nu se mai poate face.

procedura partiţionare este pentru fiecare grup G P execută

* descompune G în subgrupuri a.î. 2 stări s şi t din G să se afle în acelaşi subgrup dacă şi numai dacă, pentru toate simbolurile a , s si t tranzitează în stări aparţinând aceluiaşi subgrup

* subgrupurile obţinute se pun în Pnou

sfâr s it partitionareii) Din fiecare grup al partiţiei obţinute în pasul anterior, se alege câte o stare oarecare (stare

reprezentantă). Acestea vor fi stările AFD minimizat. Starea iniţială va fi starea reprezentantă a grupului ce conţine starea initială s0, iar stările finale vor fi reprezentantele subgrupurilor provenite din F.

iii) Toate tranziţiile dintre stările automatului iniţial se transformă în tranziţii între reprezentanţii grupelor respective. Dacă AFD minimizat conţine o stare de blocaj m, adică o stare care nu este finală şi care tranzitează în ea însăşi pentru toate simbolurile a această stare se

31

elimină. Se vor elimina, de asemenea, stările care nu pot fi atinse plecând din starea iniţială. Tranziţiile spre stările de blocaj dinspre alte stări devin nedefinite.Exemplu: fie automatul din figura 9:

S=A,B,C,D,EPrima partiţie: = A,B,C,D EPentru a construi nou, considerăm mulţimea E; această mulţime nu se mai poate diviza,

deci o includem in noua partiţie. Considerăm acum A,B,C,Dşi căutăm tranziţiile pentru simbolul a: A -a- B, B -a- B, C

-a- B, D -a- B, prin urmare simbolul a nu divizează mulţimea. Considerăm acum b: A -b- C, B -b- D, C -b- C, D -b- E, aceste tranziţii vor partiţiona

mulţimea în A, B, C şi în D.nou = (A, B, C D E)A, B, C -a- B, B, B A, B, C -b- C, D, CDeoarece D este în altă partiţie, obţinem:nou = (A, C B D E)A, C -a- B, B A, C -b- C, Cnou = (A, C B D E)În acest moment nou = , deci automatul minimizat va avea stările A, C B D E.

Din mulţimea A, C alegem satrea A ca stare reprezentativă. Toate tranziţiile spre C vor deveni tranziţii spre A, iar celelalte tranziţii le copiem din automatul iniţial. Deci, în acest caz s-a reuşit minimizarea numărului de stări cu o stare.5.1.5. Construirea arborelui binar corespunzător ER

C5

a. Un arbore de derivare (parse tree) într-o gramatică G={N, T, P, S} este un arbore orientat, etichetat, cu următoarele proprietăţi:- rădăcina arborelui este etichetată cu S;- nodurile interioare sunt etichetate cu neterminalele gramaticii, iar frunzele cu neterminale sau

terminale;- pentru orice nod interior etichetat cu A având descendenţi direcţi etichetaţi în ordine de la stânga

la dreapta cu simbolurile din A: X1, X2, … Xk (k 1) există în P o producţie: A X1 X2 … Xk . Şirul simbolurilor care etichetează frunzele arborelui scrise în ordine de la stânga la dreapta

se numeşte frontiera arborelui. Se poate arăta că oricărei forme propoziţionale din G îi corespunde cel puţin un arbore de

derivare în G care are ca frontieră pe . El se numeşte arborele de derivare în G al lui . .Fie gramatica: G={{E}, {i, +, *}, P, E} cu P = { E E + E

E E * E

32

E (E)E i }.

Propoziţia: i*(i+i) are următoarea derivare canonică stânga:E E * E i * E i * (E) i * ( E + E) i * ( i + E ) i * ( i + i )În figura următoare se prezintă arborele de derivare al acestei propoziţii. Construcţia urmăreşte derivarea canonică stângă: frontierele arborilor construiţi reproduc formele propoziţionale din derivarea canonică stângă.

b. Arborele corespunzător ER este un arbore binar care are câte un nod terminal pentru fiecare simbol ce apare în ER şi câte un nod interior pentru fiecare operator aplicat (concatenare, închidere, sau). În prealabil ER va fi modificată, în sensul că la sfârşitul ei va fi concatenat un simbol special, notat cu #, care va servi drept marcator de sfârşit al ER. O asemenea ER modificată se numeşte ER augmentată.

În funcţie de operatorul înmagazinat într-un nod, nodul se va numi nod-cat dacă operatorul este concatenare, nod-sau dacă operatorul este sau, nod-stea.

În automatul AFD corespunzător ER augmentate, orice stare de la care va exista o tranziţie etichetată cu '#' va fi stare acceptoare.

Fiecare simbol din ER va fi numerotat, în ordinea textuală a apariţiei sale în ER. Dacă acelaşi simbol apare de mai multe ori, fiecare apariţie va avea un număr distinct. Deci, unui simbol din alfabet îi pot corespunde mai multe numere de poziţie dacă el este repetat în cadrul expresiei.

Numerele atribuite în acest mod se numesc pozi ţ ii .. Arborele se obţine aducând ER la forma postfix .

Exemplu:

Fie ER : ( a | b )* a b b

ER augmentată este: ( a | b )* a b b #

a b a b b #

poz. 1 2 3 4 5 6

33

Fiecare nod al arborelui primeşte câte un identificator unic, pentru a putea fi localizat. În figura următoare, identificatorii nodurilor au fost notaţi cu Ni, i=1. .13. Arborele corespunzător va fi cel din figura următoare.

5.1.5. Obţinerea AFD din arborele binarSe foloseşte ER augmentată, se construieşte arborele sintactic (ca în exemplul anterior) şi se

aplică o metodă de analiză sintactică. Se poate demonstra că stările importante din AFN echivalent ER sunt echivalente cu poziţia frunzelor din arborele sintactic corespunzător ER. De aceea, metoda obţine direct un AFD, iar stările lui vor fi mulţimi de poziţii din arborele sintactic.

Prin traversări peste arborele construit, pentru fiecare nod n din arbore, se vor determina 4 funcţii notate: Anulabil (n), Primapoz(n) , Ultimapoz(n), Pozurm(i), unde n este identificatorul nodului. AFD se va obţine din funcţia Pozurm(i), Primele 3 funcţii sunt definite de nodurile arborelui sintactic şi se folosesc în calculul lui Pozurm(i), care este definit numai de poziţia din arbore.

Funcţia Pozurm(i) - unde i este o poziţie din arborele ER- reprezintă mulţimea poziţiilor j care pot urma poziţiei i în arbore.

Pentru expresia regulată din exemplul precedent, Pozurm(1) = {1, 2, 3}.Poziţia 1 corespunde primului a din ER. După acesta poate să urmeze:- un nou a din aceeaşi poziţie datorită aplicării operatorului *- un b din poziţia 2 din acelaşi motiv, considerând şi faptul că operatorul este sau- un a de pe poziţia 3 cu care începe şirul final abb

Pentru a calcula Pozurm(i) trebuie să se cunoască ce poziţii pot fi puse în corespondenţă cu primul sau cu ultimul simbol al unui şir generat de o anumită subexpresie din ER.

Dacă expresia este r* atunci fiecare poziţie care poate fi prima în r poate urma după fiecare poziţie care poate fi ultima în r.

Dacă expresia este rs atunci fiecare poziţie care poate fi prima în s poate urma după fiecare poziţie care poate fi ultima în r.

Funcţia Primapoz(n) este mulţimea poziţiilor corespunzătoare cu primul simbol al tuturor şirurilor generate de subexpresiile cu rădăcina în n. Analog, Ultimapoz(n) este mulţimea poziţiilor corespunzătoare cu ultimul simbol dintr-un astfel de şir.

Pentru expresia regulată din exemplul precedent, dacă n este rădăcina arborelui, Primapoz(n) = {1, 2, 3}, Ultimapoz(n) = {6}.

34

Pentru calculul acestor funcţii este necesar să se determine acele noduri care sunt rădăcini ale unor subarbori ce pot genera şirul vid. Asemenea noduri se numesc anulabile. Vom defini o funcţie Anulabil(n) care va returna valoarea logică true dacă n este un nod anulabil, şi false în caz contrar.

Există 2 reguli de bază şi 3 reguli inductive pentru cei 3 operatori. Pe baza acestor reguli, parcurgând arborele de la frunze spre rădăcină, se pot determina valorile celor 3 funcţii.

Regulile de calcul sunt următoarele:

Nr. Nodul n Anulabil (n) Primapoz (n) Ultimapoz (n)

1. Frunză cu eticheta true

2. Frunză eti-chetată cu i false {i} {i}

3. Anulabil(c1) Primapoz(c1) Ultimapoz(c1)

sau Anulabil(c2) Primapoz(c2) Ultimapoz(c2)

4. Anulabil(c1) dacă Anulabil(c1) dacă Anulabil(c2)

şi Anulabil(c2) atunci Primapoz(c1) atunci Ultimapoz(c2)

Primapoz(c2) Ultimapoz(c1)

altfel Primapoz(c1) altfel

Ultimapoz(c2)

35

n |

c1 c2

c1 c2

n

5. true Primapoz (c1) Ultimapoz (c1)

Observaţii:- Pentru Ultimapoz regulile sunt similare cu cele de la Primapoz, doar că se înlocuieşte Primapoz

cu Ultimapoz şi se interschimbă c1 cu c2 (unde este cazul).- Regula 5 pentru Anulabil (n) arată că dacă nodul n este închiderea expresiei prin * atunci

Anulabil (n) este true, deoarece închiderea expresiei prin * generează un limbaj care include cu certitudine pe .

- Regula 4 pentru Primapoz arată că dacă în expresia rs, r generează pe (adică Anulabil(c1) = true) atunci Primapoz (s) "se vede" prin r şi se include în Primapoz (n). În caz contrar, Primapoz (n) va conţine Primapoz (r).

Funcţiile Primapoz (n) şi Ultimapoz(n), calculate pentru exemplul precedent sunt:

Regulile pentru calculul lui Pozurm(i) sunt:i) Dacă n este un nod-concatenare (•), cu fiul stâng c1 şi cu fiul drept c2 şi

iUltimapoz(c1), atunci se include Primapoz(c2) în Pozurm(i).ii) Dacă n este un nod-închidere (*) şi iUltimapoz(n), atunci se include

Primapoz(n) în Pozurm(i).

36

c1

*n

În exemplul dat, având funcţiile Primapoz (n) şi Ultimapoz(n) calculate, se determină Pozurm(i).

Nod Poziţie Anulabil Primapoz Ultimapoz Pozurm

N13 2 false { 2 } { 2 } { 1,2,3 }

N12 1 false { 1 } { 1 } { 1,2,3 }

N11 - false { 1,2 } {1,2 }

N10 * true {1,2 } { 1,2 } -

N9 3 false { 3 } { 3 } { 4 }

N8 • true { 1,2 } { 1,2 } -

N7 4 false { 4 } { 4 } { 5 }

N6 • false { 1,2,3 } { 3 } -

N5 5 false { 5 } { 5 } { 6 }

N4 • false { 1,2,3 } { 4 } -

N3 6 false { 6 } { 6 }

N2 • false { 1,2,3 } { 5 } -

N1 • false { 1,2,3 } { 6 } -

Se parcurge arborele, luând în considerare numai nod-cat şi nod-stea:N2 este fiu stânga , N3 este dreapta, deci includem 6 în Pozurm pentru 5.N4 este fiu stânga , N5 este dreapta, deci includem 5 în Pozurm pentru 4.N6 este fiu stânga , N7 este dreapta, deci includem 4 în Pozurm pentru 3.N8 este fiu stânga , N9 este dreapta, deci includem 3 în Pozurm pentru 1 şi 2.N10 este nod-stea, deci includem { 1,2 } în Pozurm pentru 1 şi 2.

Deci:Poz.

Pozurm

1 {1,2,3}2 {1,2,3}3 {4}4 {5}5 {6}6 -

37

Funcţia Pozurm se poate reprezenta ca un graf orientat, având câte un nod pentru fiecare poziţie şi un arc orientat de la i la j, dacă j este în Pozurm(i).

Acest graf este un AFN fără pentru ER dată, dacă sunt îndeplinite condiţiile:- Toate poziţiile din Primapoz (rad) devin stări de start {1,2,3} - Fiecare arc orientat (i,j) este etichetat cu simbolul din poziţia j- Starea asociată cu # este singura stare acceptoare

Notând cu rad nodul rădăcină al arborelui şi preluând notaţiile Dtranz şi Dstări de la cursul anterior, algoritmul de transformare a arborelui ER în AFD este:

procedura ER2AFD este *iniţializează Dstări cu Primapoz (rad) *la început stările din Dstări sunt nemarcate cât timp există stare nemarcată T în Dstări execut ă

*marchează Tpentru fiecare a execut ă *fie U=Pozurm (p), unde p T şi simbolul din poziţia p este a dac ă U şi U Dstări atunci

*adaugă U ca stare nemarcată la Dstări

€ *adaugă tranziţia T U la Dtranz

€ €sfâr ş it ER2AFD

Etapele care se parcurg pentru obţinerea AFD pe baza arborelui unei ER sunt:I.Se determină Primapoz şi Ultimapoz pentru fiecare nod al arborelui.II.Se calculează Pozurm pentru fiecare poziţie, parcurgând arborele de sus în jos.III.Se execută procedura ER2AFD.

5.2. Implementarea generatorului automat de analizor lexical

Specificarea de intrare pentru un generator o reprezintă expresiile regulate care descriu atomii lexicali, însoţite de specificaţii semantice. Acţiunile semantice sunt secvenţe de program care se execută atunci când în şirul de intrare se identifică o lexemă corespunzătoare tiparului cu care este asociată acţiunea.

r1 acţiune 1 r2 acţiune 2 r3 acţiune 3 …rn acţiune n

38

a

Generatorul este un program care pe baza specificaţiilor de intrare produce tabela de tranziţii a automatului. Analizorul lexical va fi format dintr-un simulator pentru automat, împreună cu tabela de tranziţii generată.

Simulatorul citeşte tamponul de intrare şi pe baza tabelei de tranziţie identifică lexemele.

Automatul generat la ieşire poate fi nedeterminist sau determinist, în funcţie de implementarea dorită.

În continuare vom analiza câteva probleme de proiectare specifice pentru cele 2 variante de automate.

a. Generator care implementează AFNConsiderăm tiparele reprezentate prin ri, i=1,n pentru care se vor construi automatele

nedeterministe N(ri). Automatele parţiale obţinute se combină într-un automat general, , numit AFN combinat astfel: se introduce o nouă stare de start de la care pleacă tranziţii spre toate cele n automate.

Simularea automatului combinat se bazează pe o variantă a algoritmului iniţial, care recunoaşte cel mai lung cuvânt din intrare. Aceasta înseamnă că de fiecare dată când automatul ajunge la o mulţime de stări care conţine o stare acceptoare, va reţine poziţia din intrare şi tiparul ri asociat cu acea stare, dar simularea continuă până în momentul în care se ajunge în situaţia de terminare, adică din mulţimea de stări curentă nu există nici o tranziţie pentru simbolul din intrare. La atingerea condiţiei de terminare, pointerul de avans al intrării se va retrage la poziţia corespunzătoare ultimei stări acceptoare marcate. Tiparul memorat pentru această poziţie identifică atomul găsit, iar lexema recunoscută se găseşte între cei doi pointeri. Dacă nu există stare acceptoare, se poate genera un mesaj de eroare.

Exemplu:Se consideră următoarele tipare:

39

a abb a*b+

Automatele parţiale corespunzătoare celor 3 expresii sunt:

Combinarea automatelor parţiale în automatul general este:

Se va analiza şirul de intrare aaba

Mulţimea stărilor de start: 0,1,3,7

Mulţimea de stări iniţială este 0,1,3,7. La intrare avem simbolul a, deci se va trece în mulţimea 2,4,7. Întrucât starea 2 este stare finală, se reţine poziţia 2 în şirul de intrare şi tiparul 1 asociat cu cuvântul recunsocut. Se continuă simularea şi pe baza celui de-al doilea a din intrare se trece în starea 7, apoi în starea 8 care este stare finală. Pointerul este acum pe simbolul b din intrare deci se va memora poziţia lui b şi tiparul 3 asociat cu şirul aab. Se continuă simularea pentru ultimul a la care s-a ajuns şi din acest punct nu mai avem tranziţii, În consecinţă, se revine la ultima corespondenţă recunoscând lexema aab corespunzătoare celui de-al treilea tipar.

Dacă expresiile regulate ar avea asociate acţiuni semantice, acestea s-ar executa în momentul recunoaşterii unui tipar. Această operaţie nu se va face în mod automat de fiecare dată

40

când analizorul ajunge într-o stare acceptoare corespunzătoare unui tipar, ci numai atunci când tiparul se dovedeşte a fi tiparul care realizează cea mai lungă corespondenţă.

b. Generator care implementează AFDDacă generatorul furnizează la ieşire un AFD, programul de simulare este asemănător cu

cel pentru AFN din capitolul anterior, adică se va căuta lexema de lungime maximă. Problema care apare este că s-ar putea ca prin transformarea AFN- AFD, mulţimea de

stări din AFN corespunzătoare unei stări din AFD să conţină mai multe stări acceptoare. Trebuie să decidem care stare din cele acceptoare se va alege pentru a determina tiparul asociat. Regula este că se va alege acea stare care corespunde expresiei regulate aflate mai în faţă, în ordinea introducerii expresiilor.

Exemplu: Aplicăm algoritmul de conversie automatului generalizat de mai sus:

stare a b tiparul anunţat

0,1,3,7 2,4,7 8 nimic2,4,7 7 5,8 a8 - 8 a*b+7 7 8 nimic5,8 - 6,8 a*b+6,8 - 8 abb

În mulţimea de stări 6,8 ambele stări sunt finale. Deoarece starea 6 este stare terminală pentru o expresie regulată care apare înaintea expresiei regulate pentru starea finală 8 (ordinea de introducere a fost a, abb, a*b+), se va alege starea 6 ca stare acceptoare.

Pentru şirul de intrare aaba, algoritmul de simulare va genera aceleaşi puncte de marcare ca şi la simularea AFN.

6. Analiza sintactică C6

Este etapa din construcţia compilatorului în care se recunosc construcţiile sintactice ale programului. Regulile care descriu structura sintactică a programelor corecte pentru un anumit limbaj de programare se exprimă în mod uzual prin gramatici independente de context scrise de exemplu în notaţia BNF. Utilizarea gramaticilor pentru descrierea limbajelor de programare are urmatoarele avantaje:

a. gramatica reprezintă o notaţie precisă a unui limbaj, relativ uşor de reţinut;b. s-au elaborat metode de construcţie manuală sau automată de analizoare sintactice

eficiente pentru limbaje descrise prin gramatici; aceste metode permit şi punerea în evidenţă a unor ambiguităţi sintactice care ar trece neobservate în faza de definiţie a limbajului sau la începutul proiectării compilatorului

c. descrierea limbajului printr-o gramatică corectă favorizează procesul de detectare a erorilor şi de traducere a programului sursă în cod obiect

d. dacă limbajul evoluează în timp, şi apar construcţii de limbaj noi (completări la sintaxă) care trebuie să efectueze sarcini noi (completari la semantică), construcţiile noi se pot adăuga mai uşor limbajului iniţial, iar modificările implicate în compilator sunt mai simple

În cele ce urmează, se vor prezenta principalele metode de analiză sintactică utilizate în compilatoare. Se vor studia conceptele generale –operaţii cu gramatici, transformări aplicate gramaticilor-, tehnici de implementare manuală a analizoarelor sintactice precum şi tehnici de generare automată a analizoarelor sintactice. Metodele prezentate se vor completa cu tehnici specifice de revenire în caz de eroare.

6.1. Rolul analizei sintactice

41

Analizorul sintactic primeşte ca intrare de la analizorul lexical un şir de atomi lexicali şi are sarcina de a verifica dacă şirul respectiv poate fi generat de gramatică. În caz de eroare va trebui să semnaleze cât mai clar atât poziţia cât şi cauza erorii şi să apeleze rutine de tratare şi revenire din erori pentru a putea continua analiza.

atomProgram arbore cod cod sursă citire atom

Ieşirea analizorului sintactic este o reprezentare a arborelui sintactic corespunzător şirului de atomi furnizat de analizorul lexical. În diferite cazuri practice, arborele sintactic poate să nu fie construit efectiv ca o structură de date reală, chiar dacă el apare implicit în timpul analizei. În afara construirii arborelui sintactic, analiza sintactică are şi alte sarcini: colectarea de informaţii despre atomi şi depunerea lor în tabela de simboluri, executarea verificărilor de tip, analiza de domeniu, alte verificări semantice mergând până la generare de cod intermediar.

Există 3 tipuri de analizoare sintacice bazate pe gramatici:-universale: pot analiza orice gramatică dar sunt practic ineficiente-analizoare sintactice descendente (top-down parsing denumite şi analizoare LL)-analizoare sintactice ascendente (bottom-up parsing denumite şi analizoare LR)Cele mai eficiente analizoare sintactice ascendente respectiv descendente funcţionează pentru

subclase de gramatici, aceste subclase conţin însă majoritatea construcţiilor de limbaj uzuale. Metodele bazate pe clasele de gramatici analizabile LL sunt utilizate în analizoare sintactice implementate manual, iar cele pentru gramatici LR sunt mai generale şi utilizate în metodele de generare automată.

6.1.1. Tratarea erorilor sintactice

Un compilator trebuie să localizeze cu precizie o eroare, să identifice natura erorii şi să asigure continuarea analizei. O primă dificultate provine din faptul că definiţiile limbajelor de programare nu cuprind şi tratarea erorilor, reacţia fiind lăsată în totalitate în sarcina proiectantului compilatorului.

Planificarea erorilor de la începutul proiectării compilatorului poate să simplifice structura acestuia şi să îmbunătaţească reacţia compilatorului la erori. Programele pot conţine erori la diferite nivele: lexical, sintactic, semantic şi logic. Cele mai multe erori detectabile în faza de compilare sunt erorile sintactice, iar metodele de analiză sintactică dispun de tehnici performante de detectare de erori care în anumite situatii garantează cu certitudine detecţia tuturor erorilor. Pentru erorile semantice şi logice nu există metode de detecţie atât de precise.

La întâlnirea unei erori, analizorul sintactic trebuie să raporteze clar şi precis eroarea şi să aplice o metodă de revenire din eroare. Toate aceste sarcini trebuie astfel implementate încât să nu reducă semnificativ viteza de prelucrare a programelor corecte. O tratare completă şi detaliată a tuturor acestor probleme este dificil de realizat în practică. De obicei se preferă mecanisme mai simple de tratare a erorii care se bazează pe ideea că majoritatea erorilor de compilare care apar sunt simple şi uşor de detectat.

Metodele de analiză sintactica LL şi LR au proprietatea de prefix viabil, adică sesizează apariţia unei erori imediat ce apare la intrare un prefix care nu corespunde nici unui şir din limbaj, motiv pentru care sunt considerate metode rapide din punct de vedere al detecţiei erorilor. La raportarea unei erori se indică de obicei locul în care s-a detectat eroarea, fără a exista certitudinea că

42

Analizor lexical

Analizor sintactic

Restul prg. de front-end

Tabela de simboluri

acela este locul erorii. Există totuşi probabilitatea ca eroarea să fie chiar în acel loc sau în imediata lui vecinatate, cel mult câtiva atomi mai în faţă. Natura erorii se precizează prin mesaje de eroare, dacă există o probabilitate mare de estimare corectă se genereaza un mesaj exact, de exemplu “lipseşte;”, dacă nu, este de preferat un mesaj mai vag: ”sintax error”.

În ceea ce priveşte metodele de revenire din eroare, există câteva metode generale. În principiu, compilarea nu poate fi abandonată decât la erori grave, iar analiza trebuie reluată dintr-un punct cât mai apropiat de locul erorii cu condiţia ca prin revenire să nu se introducă erori noi.

6.1.2. Strategii de revenire din eroriExistă 3 strategii acceptate:a. modul de panică – este metoda cel mai frecvent folosită şi cel mai uşor de implementat.

În momentul detectării unei erori se elimină din intrare unul sau mai multe simboluri până când se ajunge la un atom special de sincronizare, iar din acest punct al intrării analiza se poate relua. Metoda are avantajul că se ajunge întotdeauna la sfârşitul sirului de intrare şi nu pot apărea cicluri infinite în analiză. Ca şi atomi de sincronizare se aleg diferiţi delimitatori specifici limbajului.

b. revenirea la nivel de propoziţie – la detectarea unei erori, analizorul încearcă să facă corecţii locale în şirul de intrare, de genul: înlocuirea unui simbol cu altul, ştergerea sau inserarea unui simbol. Prin aceste modificări urmăreşte să construiască un prefix corect al intrării în locul celui eronat. La această metodă există pericolul ciclului infinit (de exemplu la inserarea repetată a unuia şi aceluiaşi simbol, fără a se putea continua analiza). Dezavantajul principal al metodei este că nu permite corecţii adecvate în cazul în care eroarea este înainte de punctul de detecţie.

c. utilizarea producţiilor de eroare – este o metoda care impune cunoaşterea precisă a tipurilor de eroare ce se pot întâlni şi practic, numărul erorilor posibile nu este foarte mare. Pentru această metodă se suplimentează gramatica limbajului cu producţii care să genereze şi construcţii eronate, iar analizorul sintactic se construieşte pe baza acestei gramatici extinse. Dacă pe parcursul analizei se utilizează o producţie de eroare, acţiunile asociate cu acea producţie nu vor conduce la traducere ci la un mesaj de eroare.

d. efectuarea de corecţii globale – este o metodă teoretică care compară programul x cu un program y obţinut printr-un număr minim de transformări, presupus a fi cel “intenţionat de programator”.

6.2. Proiectarea unei gramatici Pentru a fi analizat sintactic, un limbaj va fi descris în continuare printr-o gramatică independentă de context.

O gramatică independentă de context nu poate descrie însă complet sintaxa unui limbaj de programare, deoarece există şi constructii dependente de context şi acestea vor trebui tratate în fazele următoare de analiză (de exemplu cerinţa ca un identificator să fie declarat înainte de utilizare). O altă problemă care se pune este faptul că fiecare metodă de analiză poate trata numai gramatici de o anumită formă şi de aceea este uneori necesar ca gramatica iniţială să fie transformată pentru a o face analizabilă prin metoda aleasă. În acest subcapitol se vor trata acele transformări care fac o gramatică potrivită pentru metode descendente de analiză: eliminarea ambiguităţii din gramatică, eliminarea simbolurilor inutile, eliminarea recursivităţii de stânga, factorizarea la stânga).

6.2.1. Comparaţie: expresii regulate-gramatici independente de contextPână acum, pentru descrierea atomilor lexicali, s-au folosit în principal expresiile regulate.

Regulile lexicale sunt simple şi descrierea lor nu necesită un formalism atât de puternic ca şi cel oferit de gramatici.Expresiile regulate, faţă de gramatici oferă următoarele avantaje:

a. pentru structuri simple de limbaj reprezintă notaţii mai precise şi mai clare decât gramaticile

b. analizorul lexical realizat pe baza expresiilor regulate are structura mai simplă şi poate fi mai uşor generat automat.

43

Observaţie: Fiecare construcţie exprimabilă printr-o expresie regulată se poate descrie şi printr-o gramatică independentă de context, respectiv orice automat finit nedeterminist se poate transforma într-o gramatică care generază acelaşi limbaj.

Exemplu. Fie expresia regulată: (a|b)*abb. Ei îi corespunde un AFN di figura următoare:

Pe baza acestui AFN se poate construi gramatica:G: A0 aA0 | bA0 | aA1

A1 bA2 A2 bA3 A3

Metoda de transformare este:- Pentru fiecare stare i din automat se crează un neterminal Ai - Pentru fiecare tranziţie se crează în gramatică o construcţie de forma Ai aAj - Pentru fiecare tranziţie se include în gramatică o construcţie de forma Ai Aj - Pentru fiecare stare finală i se include în gramatică câte o producţie Ai - Simbolul corespunzător stării de start devine simbol de start al gramaticii.

Nu există reguli fixe de divizare a unui limbaj în parte lexicală şi nelexicală. De obicei se descriu prin expresii regulate şi se tratează la expresii regulate construcţiile simple ale unui limbaj: identificatori, numere, şiruri de caractere, iar în faza de analiză sintactică se tratează construcţiile mai complexe care se exprimă prin relaţii recursive: instrucţiuni, declaraţii, expresii etc.

6.2.3. Gramatici ambigue. Exemplu de transformare a unei gramatici ambigue într-o gramatică neambiguă echivalentă

Analizorul sintactic pentru un limbaj generează implicit sau explicit arborele sintactic pentru şirul de intrare dat. Din această cauză este important ca arborele care se asociază să fie unic. Considerăm următoarea gramatică :S AB|BCA DB EC DD a|bE a|bDacă şirul din intrare este ‘ab’, atunci pentru această propoziţie se pot forma doi arbori:

44

Definiţie: O GIC se numeste ambiguă dacă în limbajul generat există o propoziţie care admite mai mult decât un arbore sintactic, obţinut prin derivări dinstincte; în caz contrar gramatica este neambiguă. Cu toate că gramaticile ambigue reprezintă o descriere mai compactă şi mai clară a unui limbaj, ele sunt în general o piedică, un inconvenient în plus. Pentru acelaţi limbaj, pot exista atât gramatici ambigue cât şi gramatici neambigue care să-l genereze.Exemplu: G1: S i5 | SS G2: S i5 | i5S

L(G1)=L(G2)={i5k | k>=1}G1 este ambiguă deoarece de exemplu pentru i15 avem două derivări stânga:S SS SSS i5SS i10S i15

S SS i5S i5SS i10S i15

în timp ce G2 este neambiguă.Definiţie: Un limbaj se numeşte inerent ambiguu dacă orice gramatică care-l generează este ambiguă.

Exemplu de transformare a unei gramatici ambigue într-o gramatică echivalentă neambiguă. Considerăm următoarea gramatică a expresiilor matematice:G1= < {E}, {+,*,(,),id}, P1, E >P1: E E+E | E*E | (E) | id

Aplicând producţiile gramaticii, expresiei id+id*id îi corespund următorii arbori sintactici:

Ambiguitatea se poate rezolva dacă stabilim care dintre operatorii ‘*’ şi ‘+’ este mai prioritar. Pentru primul arbore operatorul mai prioritar este ‘*’ iar pentru al doilea este ‘+’. Modificând gramatica astfel:G2= < {E,T,F}, {+,*,(,),id}, P2, E >P2: E E+T|T T T*F | F F (E) | idObţinem pentru expresie un arbore unic:

45

Ambiguitatea s-a eliminat prin fixarea priorităţii mai mari pentru operatorul de ‘*’ faţă de operatorul ‘+’. În general eliminarea ambiguităţii implică mărirea numărului de neterminale.

În teoria limbajelor formale se demomstrează urmatoarele teoreme:1. Limbajele regulate din clasa L3 sunt neambigue.2. O reuniune a unui număr finit de limbaje neambigue disjuncte 2 câte 2 reprezintă de

asemenea un limbaj neambiguu.Teorema 2 permite ca studierea ambiguităţii să se facă pentru părţi ale limbajului, chiar pentru un set mic de producţii.

S-a demonstrat faptul că nu există un algoritm care acceptând orice GIC să determine în timp finit dacă aceasta este sau nu ambiguă. Există doar un set de condiţii care dacă sunt satisfacute de gramatică atunci este cert că gramatica nu este ambiguă. Aceste condiţii sunt suficiente dar nu şi necesare, adică o gramatică poate fi neambiguă şi fără să respecte aceste condiţii.

6.2.4. Eliminarea simbolurilor inutile dintr-o gramaticăFie gramatica G = < N,T,P,S>, unde VG =N U T este vocabularul gramaticii. Un simbol VG este inutil dacă nu există nici o derivare de forma:

S =*> u v =*> u x v unde u,x,v T*

Relaţia de mai sus descrie două tipuri de simboluri inutile:a. simboluri inaccesibile : sunt acele simboluri care nu pot fi generate prin nici o derivare pornind

de la simbolul de start – nu apar în nici o propoziţie generată de gramatică; este simbol inaccesibil

b. simboluri nefinalizate : sunt acele simboluri care nu se pot transforma într-un şir exclusiv de simboluri terminale, oricâte derivări s-ar aplica

În timp ce simbolurile inaccesibile pot fi atât terminale cât şi neterminale, cele nefinalizate pot fi doar neterminalele gramaticii.

Se poate demonstra că pentru orice GIC cu limbajul generat L(G) există o gramatică echivalentă cu ea (deci generează acelaşi limbaj) care nu are simboluri inutile.

Eliminarea simbolurilor inutile din gramatică se poate face în doi paşi:1. se caută şi se elimină toate simbolurile nefinalizate precum şi relaţiile care le conţin2. se determină şi se elimină toate simbolurile inaccesibile şi relaţiile corespunzătoare lorGramaticile care descriu limbajele de programare sunt obligatoriu fără simboluri inutile.

6.2.5. Eliminarea recursivităţii de stânga dintr-o gramaticăO gramatică este recursivă la stânga dacă are cel puţin un neterminal A pentru care există o

derivare de forma: A =+> A unde este un şir oarecare. În mod similar se defineşte recursivitatea la dreapta a unei gramatici .

Metodele de analiză sintactică descendentă nu pot trata gramaticile recursive la stânga (analizorul intră în ciclu infinit) rezultând deci că pentru a face o gramatică analizabilă prin această metodă este necesar să se elimine acest tip de recursivitate. Cazul cel mai simplu îl constituie acela în care gramatica are producţii de forma: AA, ceea ce înseamnă recursivitate de stânga imediată. Acest tip de recursivitate se rezolvă simplu în felul următor:Având producţiile A A | unde nu începe cu neterminalul A, se introduce un nou neterminal A’ iar producţiile se modifică în felul următor:A A’A’ A’ | Se poate arăta uşor că limbajul generat de noua gramatică nu s-a schimbat.Exemplu:

46

E E + T | TT T * F | FF (E) | id

Producţiile recursive sunt cele pentru E şi T.=> E T E’ E’ + T E’ | T F T’ T’ * F T’ |

F (E) | id

Algoritm de eliminare a recursivităţii stânga imediateLa modul general, recursivitatea stânga imediată pentru un simbol A se poate elimina prin

următoarea metodă:- se grupează producţiile pentru A

A A 1 | A 2 | …| A m | 1 | …| n

astfel încât nici un i nu începe cu A-se înlocuiesc producţiile pentru A prin următoarele producţii echivalente:

A 1 A’ | 2 A’ |…| n A’A’ 1 A’| 2 A’| …| m A’ |

Metoda elimină orice caz de recursivitate imediată cu condiţia ca nici un i să nu fie . Eliminarea recursivitatii de stânga s-a obţinut prin transformarea ei în recursivitate de dreapta care însă nu deranjează în procesul de analiză descendentă.

Recursivitatea de stânga poate să nu fie imediată. De exemplu pentru gramatica:S A a | bA A c | S d |

Atât pentru S cât şi pentru A există producţii recursive, pentru S recursivitatea nefiind imediată.Se prezintă un algoritm care elimină complet recursivitatea stânga cu condiţia ca gramatica să

nu aibă cicluri ( A=+> A) şi să nu aibă producţii vide (A). Problema ciclului şi a producţiilor vide poate fi rezolvată anterior aplicării algoritmului de mai jos, prin transformări specifice.

Algoritm de eliminare a recursivităţii stânga1. se aranjează neterminalele gramaticii într-o anumită ordine şi se numerotează A1, A2, …An

2. for i:=1 to n do beginfor j:=1 to i-1 do begin * inlocuieşte fiecare producţie de forma Ai Aj prin producţia

Ai 1 | … | k unde Aj 1 | … | k reprezintă toate producţiile corespunzătoare lui Aj

* elimină recursivitatea stânga imediată pentru Ai, dacă este cazulend;

end;Algoritmul funcţionează corect deoarece înainte de iteraţia i oarecare orice producţie de

forma Ak Al cu k< i are în mod obligatoriu l >k. Ca rezultat, la următoarea iteraţie (i), ciclul interior (cu j) va ridica progresiv limita inferioară m în orice producţie A i Am până când m i. Eliminând acum recursivitatea imediată pentru Ai, rămâne m > i, adică poate începe următoarea iteraţie.

Trasarea algoritmului pentru gramatica anterioară: (chiar dacă există producţie vidă pentru A, pentru gramatica dată nu deranjează)1. ordonăm producţiile pentru S şi A2. pentru i=1 bucla pentru j nu are efect (neterminalul S)

pentru i=2 adică neterminalul AA Ac | Aad | bd | Introducem un neterminal nou A’ şi obţinemA bdA’ | A’

47

A’ cA’ | adA’ | s-a obţinut gramatica

S Aa | bA bdA’ | A’A’ cA’ | adA’ |

6.2.6. Factorizarea la stângaDacă pentru un neterminal A există mai multe alternative care încep cu acelaşi simbol sau

acelaşi grup de simboluri, în procesul de analiză top-down nu se poate decide care alternativă să fie aleasă. Factorizarea întârzie luarea deciziei până în momentul în care parcurgând suficiente simboluri din intrare există suficientă informaţie pentru a lua o decizie de expandare corectă. Din acest motiv este necesară introducerea unei etape intermediare de factorizare a producţiilor de acest gen.

<instr> if <expresie> then <instr> else <instr> if <expresie> then <instr> | altceva

<expresie> bDacă în intrare apare if, nu se poate şti care din variante să se utilizeze pentru expandarea

neterminalului <instr>. În general se poate nota A 1 | 2 cu . Factorizarea constă în introducerea unui neterminal A’ şi transformarea gramaticilor astfel: A A’, A’ 1 | 2.

Algoritmul de transformare:* pentru fiecare neterminal A se caută cel mai lung prefix comun la două sau mai multe

alternative ale lui A. Dacă atunci toate producţiile de forma A 1 | 2 | … | k | , unde reprezintă producţiile care nu au pe ca prefix) se vor

înlocui cu A A’ | , A’ 1 | 2 | … | k

* se repetă acest procedeu până nu mai există neterminale cu alternative având prefix comun

<instr> if <expresie> then <instr> <instrprim> | altceva<instrprim> else <instr> | <expresie> b

Exemplu de eliminarea recursivităţii stânga dintr-o gramatică

Fie gramatica: S CB | a; B Sa | b; C Bb | Cba

Algoritmul se bazează pe ordonarea neterminalelor urmată de prelucrarea producţiilor astfel încât să nu apară producţii de forma Ai Aj cu j i.Ordonăm neterminalele:A1 = S, A2 = B, A3 = CGramatica cu producţii numerotate devine:1. A1 A3 A2 2. A1 a3. A2 A1 a 4. A2 b5. A3 A2 b 6. A1 A3 baProducţia 3 este înlocuită cu:3', 3" A2 A3A2 a| aaProducţia 5 este înlocuită cu:5', 5", 5"' A3 A3A2 ab| aab | bb Producţiile 5', 5", 5"' şi 6 se înlocuiesc datorită recursivităţii stângi imediate a lui A3 cu:A3 aab A' | bb A' şi A' A2 ab A'| ba A' | Renumerotând producţiile, gramatica devine:0. A' A2 ab A' 1. A' ba A' 2. A' 3. A1 A3 A2 4. A1 a5. A2 A3A2 a 6. A2 aa 7. A2 b8. A3 aab A' 9. A3 bb A'

48

C7Exemplu de eliminarea recursivităţii stânga dintr-o gramatică

Fie gramatica: S CB | a; B Sa | b; C Bb | Cba

Algoritmul se bazează pe ordonarea neterminalelor urmată de prelucrarea producţiilor astfel încât să nu apară producţii de forma Ai Aj cu j i.Ordonăm neterminalele:A1 = S, A2 = B, A3 = CGramatica cu producţii numerotate devine:1. A1 A3 A2 2. A1 a3. A2 A1 a 4. A2 b5. A3 A2 b 6. A1 A3 baProducţia 3 este înlocuită cu:3', 3" A2 A3A2 a| aaProducţia 5 este înlocuită cu:5', 5", 5"' A3 A3A2 ab| aab | bb Producţiile 5', 5", 5"' şi 6 se înlocuiesc datorită recursivităţii stângi imediate a lui A3 cu:A3 aab A' | bb A' şi A' A2 ab A'| ba A' | Renumerotând producţiile, gramatica devine:0. A' A2 ab A' 1. A' ba A' 2. A' 3. A1 A3 A2 4. A1 a5. A2 A3A2 a 6. A2 aa 7. A2 b8. A3 aab A' 9. A3 bb A'

Tipuri de analizoare sintactice

Rolul analizei sintactice este transformarea şirului de atomi lexicali într-o descriere structurală a şirului în cazul în care acesta e corect, sau într-un mesaj de eroare, în cazul în care şirul nu e corect. Descrierea structurală este de obicei un echivalent al arborelui de derivare.

a. În principiu, există două strategii de construire a arborelui de derivare: strategia descendentă, în care arborele este construit de la rădăcină spre frunze şi strategia ascendentă, în care arborele este construit de la frunze spre rădăcină.

În ambele cazuri, construcţia e ghidată de şirul de la intrare. Corespunzător acestor strategii, există analizoare sintactice descendente şi, respectiv,

analizoare sintactice ascendente. Metodele de analiză sintactică descendentă sunt simple comparativ cu cele ascendente şi permit construirea manuală uşoară de analizoare sintactice destul de eficiente. Analizoarele sintactice ascendente sunt mai generale, adică permit tratarea unor clase mai largi de limbaje.

b. O altă clasificare a analizoarelor sintactice este dată de existenţa revenirilor. Un analizor sintactic cu reveniri permite prin program posibilitatea încercării tuturor

alternativelor de continuare a analizei, în situaţia în care unui neterminal îi corespund mai multe alternative dintre care nu se poate alege în mod univoc una exactă la un moment dat al analizei. Abandonarea unei alternative necesită revenirea la situaţia anterioară încercării ei.

Dacă se asigură în orice moment o singură posibilitate de continuare a analizei sintactice se pot realiza analizoare sintactice fără reveniri, care sunt mai eficiente.

7. Analiza sintactică descendentă

49

Analiza sintactică descendentă constă în încercarea de a găsi o succesiune de derivări stânga, pornind de la simbolul de start, până se obtine şirul dat la intrare. Ea este echivalentă cu încercarea de a construi arborele sintactic pentru şirul respectiv, pornind de la rădăcină spre frunze, construind nodurile în preordine.

7.1. Analiza sintactică descendentă cu reveniri

Construcţia arborelui sintactic începe de la rădăcină, principalele operaţii ale analizorului sintactic fiind:

- Înlocuirea unui neterminal A din vârful stivei cu un şir ce reprezintă o parte dreaptă a producţiilor gramaticii pentru simbolul neterminal respectiv, operaţie ce se numeşte expandare. La nodul curent etichetat cu A se selectează una din producţiile pentru A şi se construiesc fiii nodului etichetaţi cu simbolurile din partea dreaptă a producţiei, iar apoi se caută următorul nod pentru care se va construi subarborele.

- Ştergerea unui terminal din vârful stivei în cazul în care el coincide cu terminalul curent de la intrare, operaţie numită avans.

Astfel, analizorul sintactic propune diverse alternative de rescriere pentru fiecare neterminal (expandare). Fiecare alternativă se constituie într-un obiectiv care trebuie demonstrat şi reprezintă o structură posibilă pentru următorul simbol de la intrare. Dacă structura nu e regăsită în şirul de la intrare, analizorul va propune o altă alternativă ş.a.m.d.

Dacă următorul obiectiv este un simbol terminal şi el e acelaşi cu simbolul de la intrare, analizorul efectuează o operaţie de avans considerând obiectivul îndeplinit.

Arborele sintactic se construieşte prin baleierea şirului din intrare şi căutarea producţiei a cărei parte dreaptă începe cu simbolul curent din intrare sau poate fi dezvoltată astfel încât să corespundă cu acesta. Atomul curent baleiat la intrare se numeşte simbol de anticipare.

Iniţial, simbolul de anticipare este cel mai din stânga atom din şirul de intrare.

Exemplul 1. Fie gramatica G1 cu producţiile:S bAeA d | dAşi cuvântul de intrare: bdde din limbajul generat de gramatică.

Baleierea şirului de intrare, concomitent cu construcţia arborelui decurge în felul următor:Deoarece obiectivul iniţial al analizorului este S, în primul pas al analizei se propune ca

obiectiv singura structură posibilă, bAe, care conduce la arborele de derivare din fig.1. Operaţia este de expandare. Obiectivul iniţial, S, este astfel înlocuit de structura formată din trei obiective succesive: b, A, e, care sunt etichetele descendenţilor imediaţi pentru nodul etichetat cu S.

Obiectivul imediat următor este dat de frunza cea mai din stânga, etichetată cu terminalul b. Deoarece este un terminal, el trebuie regăsit ca simbol curent în şirul de intrare. Pentru exemplul dat este adevărat şi analizorul sintactic face o operaţie de avans şi se propune recunoaşterea unei structuri a lui A din şirul de intrare încă neanalizat. Se încearcă o expandare cu prima alternativă a lui A: d şi se obţine arborele din figura 2.

50

Obiectivul A este înlocuit cu obiectivul d, terminal care trebuie găsit în şirul de intrare. Deoarece următorul simbol de intrare este d, analizorul face un avans la obiectivul e. În acest moment nu se mai poate avansa, deoarece primul caracter al şirului neanalizat este d (nu e), analizorul sintactic sesizează o eroare în luarea deciziilor şi se întoarce la cel mai recent obiectiv propus şi depăşit, adică A şi propune o altă alternativă: dA.

Datorită acestei întoarceri, are loc o revenire în şirul de la intrare până la punctul în care se afla analizorul când a propus prima alternativă de expandare pentru A, adică dde.

Expandarea lui A cu dA conduce la arborele din fig. 3. Se înlocuieşte astfel obiectivul A cu două obiective d şi A. Următorul obiectiv imediat este regăsirea lui d în şirul dde, ceea ce permite avansul şi trecerea la obiectivul A. Din nou analizorul propune expandarea cu prima alternativă d, urmată de avansul cu d, conducând la arborele din fig. 4.

Astfel, ultimul obiectiv A este rezolvat şi se raportează succes obiectivului de pe nivelul superior, care este tot A şi care în acest moment este rezolvat. Următorul obiectiv devine e. Deoarece şirul de la intrare este chiar e, se face un avans raportându-se succes pentru e şi apoi pentru S.

Coincidenţa dintre raportarea succesului pentru S şi epuizarea şirului de intrare este echivalentă cu acceptarea.

Se observă că derivarea stânga a lui S în bdde este echivalentă cu construirea arborelui de derivare a şirului.

S bAe bdAe bdde

Dacă şirul de intrare ar fi fost bddb, la încercarea de avans cu e s-ar fi înregistrat eşec, ceea ce ar fi dus la reveniri succesive astfel: întâi o încercare cu o altă alternativă pentru neterminalul A. Deoarece nu mai există o astfel de alternativă, se revine la obiectivul b, care este cel mai din stânga descendent a lui S. Dar acesta este un terminal, se raportează eşec pentru întreaga alternativă bAe. Deoarece aceasta este singura alternativă pentru S, se raportează eşec pentru S, iar acesta fiind nodul rădăcină, situaţia este echivalentă cu neacceptarea şirului bddb.

51

Implementarea unui asemenea proces necesită, pentru eventualele reveniri, memorarea drumului parcurs în arbore, precum şi a punctelor din şirul de la intrare în care s-a început expandarea neterminalelor.

Deoarece revenirile se fac strict în ordine inversă faţă de cea a axpandărilor şi avansurilor, mecanismul de implementare va fi cel de stivă.

Stiva poate fi implementată explicit sau implicit, folosind mecanismul de implementare al recursivităţii existent în multe limbaje de programare.

Observaţie. Dacă producţiile gramaticii ar fi de forma: A Ad | d, analizorul sintactic ar executa - pentru orice şir de intrare – un ciclu infinit. Într-adevăr, după avansul peste b, obiectivul următor devine A, care se expandează în prima sa alternativă, adică Ad, ceea ce fixează ca obiectiv tot pe A ş.a.m.d. O soluţie ar fi să lăsăm analiza lui Ad ultima şi să încercăm mai întâi cu d, dar atunci ciclul infinit ar apare pentru şiruri incorecte, de exemplu be. Deci o gramatică recursivă la stânga poate determina ca un analizor sintactic descendent recursiv, chiar şi pentru varianta cu reveniri să intre într-un ciclu infinit. Această situaţie apare atunci când expandând un neterminal recursiv ajungem din nou la expandarea sa, fără să avansăm în şirul de intrare.

Exemplu de implementare. Fie gramatica:G = <{S,A}, {a,b,c,d} , P,S>, unde P conţine producţiile:S cAdA ab | a

şi fie w = cad şirul de intrare.Se dă un exemplu de implementare prin scrierea unei funcţii pentru fiecare neterminal,

analizând pe rând alternativele de expandare ale neterminalului. Trecerea la o nouă alternativă are loc dacă încercarea alternativei precedente a eşuat. Această trecere trebuie să restabilească indicatorul şirului de la intrare. Dacă toate alternativele au eşuat, se întoarce valoarea logică fals. Dacă o alternativă e satisfăcătoare, se întoarce valoarea logică adevărat.

Analiza unei alternative înseamnă propunerea pe rând ca obiective a simbolurilor succesive ce formează alternativa. Dacă este vorba de terminal, se verifică faptul că el coincide cu simbolul de intrare, iar dacă e neterminal se verifică dacă apelul funcţiei asociate întoarce valoarea logică adevărat.

typedef ENUM {false, true} BOOL;TOKEN *tokens; /*iesire de la scanner*/TOKEN* token ; /*atomul curent */

BOOL sintax_S()/*analiza sintactica derivata din S */{ /*incearca alternativa S -> cAd */if (*token =='c'){

++token;if (sintax_A())

if (*token =='d'){++token;return true;}

}return false;}BOOL sintax_A()/*analiza sintactica derivata din A */TOKEN save; /pentru backtracking */

52

save = token;{ /*incearca alternativa A -> ab */

if (*token =='a'){++token;if (*token =='b'){

++token;return true;}

}token = save; /*esec, backtracking */{ /*incearca alternativa A -> a */

if (*token =='a'){++token;return true;}

token = save; /*esec, backtracking *//* nu mai sunt alternative, esec */return false;}

Metoda prezentată are două dezavantaje:- Nu se poate aplica unei gramatici recursive la stânga- Backtracking este dificil de implementat, deoarece toate acţiunile compilatorului

până în punctul de revenire (de exemplu actualizarea tabelei de simboluri) trebuiesc şterse. Soluţia ar fi aplicarea analizorului sintactic asupra unor gramatici pentru care nu mai este necesar procedeul de backtracking.

Eliminarea recursivităţii stânga se poate face cu algoritmul prezentat la 6.2.5. Examinând exemplul dat, se observă că, pentru evitarea procedeului de backtracking, ar trebui ca decizia asupra alternativei corecte să poată fi luată doar pe baza următorului simbol de la intrare.

Exemplu de factorizare stânga a unei gramatici.Revenind la exemplul 1, un şir de intrare bdde este respins pentru ordinea de

încercare d urmată de dA. Astfel, după avansul lui b şi expandarea cu d a lui A, se avansează cu d şi se verifică existenţa lui e la intrare, ceea ce conduce la eşec (următorul simbol este d, nu e). Acest lucru se datorează faptului că d este un prefix al lui dA şi se raportează succes la expandarea cu d a lui A atât în cazul în care alternativa d este corectă, cât şi în cazul în care structura intrării este dA.

Soluţia pentru această problemă este ordonarea alternativelor de tip şi astfel încât să îl preceadă pe . Această ordonare permite o optimizare: Dacă pentru analiza conform cu se obţine succes, se memorează starea intrării şi se analizează conform cu . Dacă se raportează eşec, se revine la situaţia intrării de la sfârşitul lui şi se raportează succes.

Mai general, problema se pune pentru alternativele care încep la fel. De exemplu, A 1 | 2 . Implementarea prezentată ar fi încercat 1 şi apoi 2 . Se observă că s-ar fi încercat de două ori.

Pentru evitarea acestei situaţii se recurge la factorizare stânga:A A'A' 1 | 2

53

Folosind această metodă, pentru A există o singură posibilitate, iar alternativele lui A' diferă cu primul simbol, deci este uşor de recunoscut alternativa corectă faţă de şirul curent de la intrare. Această idee stă la baza analizei sintactice descendente fără reveniri. Aceasta însă nu se poate implementa pentru orice tip de gramatică independentă de context. Se pune problema determinării unei astfel de gramatici.

7.2. Analiza sintactică descendentă fără reveniri

7.2.1. Analizor sintactic descendent recursiv de tip predictiv

Analizoarele sintactice cu reveniri se caracterizează printr-un timp mare de analiză, din acest motiv în practică sunt rar întâlnite. Dacă dintr-o gramatică se elimină recursivitatea de stânga şi se aplica factorizare la stânga, gramatica devine analizabilă prin metode de analiză sintactică descendentă, fără să fie necesare reveniri. Un astfel de analizor sintactic de numeşte analizor sintactic descendent recursiv de tip predictiv.

În cazul unui analizor sintactic predictiv, pentru un simbol de intrare ‘a ‘ şi un neterminal A care urmează să fie expandat, trebuie să se poată decide care din alternativele A->1| 2 |…| n

este unica alternativă din care pot deriva şiruri care să înceapă cu ‘a’. Cu alte cuvinte, trebuie să se aleagă alternativa corectă cercetând doar simbolul curent din intrare (un singur simbol din intrare) şi având acces la un singur simbol în arbore.

În majoritatea limbajelor de programare construcţiile sintactice (instrucţiuni, declaraţii, etc.) încep cu un cuvânt cheie tocmai în scopul de a facilita analiza. Cuvintele cheie fiind distincte de la o construcţie la alta, pe baza lor se poate alege producţia corectă pe parcursul analizei sintactice.

Un analizor sintactic de tip recursiv se compune tot din proceduri recursive, câte una pentru fiecare neterminal al gramaticii. Spre deosebire de cazul analizorului cu reveniri, unde, dacă alegerea unei alternative se dovedeşte a fi greşită se selectează următoarea alternativă, în acest caz alegerea alternativei se face exclusiv pe baza simbolului de intrare. Odată aleasă o alternativă, eşuarea analizei este echivalentă cu neacceptarea intrării.

Simbolului de anticipare selectează univoc procedura care trebuie apelată la un moment dat. Secvenţa de apeluri pentru prelucarea unui şir de intrare dat defineşte implicit arborele sintactic corespunzător intrării.

Exemplu. Fie producţiile unei gramatici:tip -> simplu | ^id | array [simplu] of tipsimplu -> integer | char | num pp numAnalizorul sintactic se va compune din 2 proceduri corespunzătoare neterminalelor tip şi

simplu precum şi dintr-o procedură suplimentară notată coresp care va avansa simbolul de anticipare la următorul caracter din intrare după ce verifică corespondenţa dintre simbolul de anticipare şi argument.

Procedure coresp(t:atom);Begin

If sa=t then sa:=urmatorulElse eroare();

End;

Procedure tip;Begin

If sa în [integer,char,num] then simpluElse if sa = ´^´ then begin

54

Coresp(‘^’); coresp(id); End Else

If sa=array then beginCoresp(array); coresp(‘[‘);Simplu; (* trateaza tipul indicelui *)Coresp(‘]’); coresp(of);Tip;EndElse eroare();

End; {tip}

Procedure simplu;Begin If sa=integer then coresp(integer) Else if sa=char then coresp(char) Else if sa=num then begin

Coresp(num); coresp(pp); coresp(num);Else eroare();

End;

Analiza sintactică propriu-zisă (programul principal) începe cu un apel la procedura pentru neterminalul de start al gramaticii (în acest caz tip).

Considerând analiza şirului de intrare array [ num pp num] of integer, vom avea iniţial sa = array (simbolul de anticipare). În procedura tip se va executa a treia ramură corespunzătoare celei de-a treia alternative din producţiile pentru tip.

În principiu fiecare neterminal din partea dreaptă a producţiei care se regăseşte în construcţia procedurii respective va determina un apel la procedura pentru acel neterminal iar fiecare terminal va fi pus în corespondenţă cu simbolul de anticipare. Sa ghidează (decide) selecţionarea producţiei ce trebuie aplicată. Dacă partea drepată a producţiei începe chiar cu un terminal, acea productie se va aplica dacă sa coincide cu terminalul. Dacă partea dreaptă a producţiei începe cu un neterminal (ex: tip -> simplu) atunci va fi selectată acea producţie dacă din neterminalul respectiv pot să deriveze şiruri care să înceapă cu simbolul de anticipare.

Rezultă că analiza sintactică predictivă se bazează pe informaţii despre simbolurile care pot să fie primele în şirul derivat din partea dreaptă a producţiei. Notând cu partea dreaptă a unei producţii, se defineşte ca PRIM() mulţimea tuturor simbolurilor terminale care pot să apară pe prima poziţie în cel puţin un şir derivat din . Dacă = sau poate genera , atunci se include şi în PRIM().

Exemplu: PRIM(^id)={^}PRIM(simplu)={integer, char, num}

Dacă părţile drepte încep cu un terminal (de exemplu cuvânt cheie) acel terminal este singurul element al mulţimii PRIM şi determinarea se face într-un singur pas.

Considerăm producţia A -> | cu două alternative pentru neterminalul A. Analiza sintactică descendent recursivă de tip predictiv cere ca PRIM() şi PRIM() să fie disjuncte. Dacă această cerinţă nu este îndeplinită se poate încerca rezolvarea ei prin factorizare la stânga.

Utilizarea producţiilor vide ()

55

Producţiile cu în partea dreaptă impun o tratare specială în sensul că analizorul sintactic

descendent recursiv utilizează implicit o producţie vidă atunci când nu se poate utiliza nici o altă

producţie.

Instr -> begin corp_instr end.Corp_instr -> lista_instr | Atunci când se tratează corpul instrucţiunii, dacă sa nu este în PRIM (lista_instr ) nu se

va efectua nici o activitate ( dar nici nu se dă eroare) presupunându-se că s-a selectat producţia . Acestă alternativă este corectă numai dacă sa este end, în caz contrar se va ajunge totuşi la eroare, dar în procedura care trateaza instr.

7.2.2. Proiectarea unui analizorul sintactic predictiv C8Analizorul sintactic predictiv este un program ce constă dintr-o procedură pentru fiecare

neterminal. Fiecare procedură va executa două acţiuni:a. pe baza simbolului de anticipare decide care producţie se va utiliza;

- dacă sa este în PRIM() se va utiliza producţia cu partea dreaptă - dacă există un conflict (ambiguitate) între 2 părţi drepte pentru acelaşi sa, atunci

gramatica nu poate fi analizată prin această metodă. - dacă sa(PRIM()) pentru nici o parte dreaptă, se va selecta producţia cu în partea

dreaptă (dacă există o astfel de producţie).b. activitatea procedurii va urmări partea dreaptă a producţiei alese. Un neterminal în partea

dreaptă va determina apelul procedurii corespunzatoare acelui neterminal, iar un neterminal care corespunde simbolului de anticipare determină citirea următorului atom. În cazul în care atomul din partea dreaptă a producţiei nu corespunde cu sa se va semnala eroare de sintaxă.

7.2.3. Exemplu de analizor sintactic complet realizat prin metoda de analiza cu descendenţi recursivi

Gramatica limbajului este următoarea:

program .

bloc CONST id = nr ;

,

VAR id ;

,

PROCEDURE ; ;

56

bloc

id bloc

factor identificator

expresie

numar

instructiune :=

CALL

BEGIN END

;

IF THEN

WHILE DO

conditie ODD

=

expresie +

- + -

termen factor

* /

( )

57

id expresie

id

instructiune

expresie

expresie

conditie instructiune

conditie

instructiune

instructiune

expresie

termen

Observaţie: * Numerele se consideră a fi de un singur fel iar felul identificatorilor nu interesează

Program anal_sintactic;Label 99; {abandonarea compilarii}Const nrcuvcheie=11; Txmax=100; {lungimea tabelei de simboluri} idlung=10;Type codlex =(nedef, ident, numar, plus, minus, inm, impr, oddcl, eq, ne, ge, gt, le, lt, pr_stg, pr_dr,

virgula, punct, punct_virg, atrib, begincl, endcl, ifcl, thencl, whilecl, docl, callcl, constcl,varcl, proccl);Obiect=(constanta,variabila,procedura);

Var cl:codlex; Id:string[10]; {ultimul identif citit de ALEX}

Num:integer; {se considera doar nunere intregi}ch:char;cc,ll:integer;linie: {tamponul de intrare}cheie: array[1..nrcuvcheie] of codlex;clsing:array[char] of codlex;ts: array[0..tmax] of recordnume:string[10];fel:obiect;End;

Procedure init_an_lex……Procedure eroare….Procedure eroaregrava…..Procedure carurm….Procedure anlex…..

Procedure bloc(tx:integer); Procedure intrare(f:obiect); //obiect:constante,proceduri, variabile Begin

tx:=tx+1; //eventual se poate verifica depasirea indicelui TSwith ts[tx] do

begin num:=id; fel:=f;end;

end;//cauta id in tab de simb function pozitie(id:string[10]):integer;

var i:integer;begin

ts[0].nume:=id; i:=tx;while(ts[i].nume<>id) do dec(i);pozitie:=i;

end; procedure declconst;

beginif cl=ident then

beginanlex;if cl=eq then

beginanlex;

58

if cl=numar then beginintrare(constanta);anlex;end;

else eroare(8); (*lipseste valoare pentru decl de constante*)end;

else eroare(9); (*lipseste ‘=’ in decl. de const *)end;

else eroare(10); (*lipseste nume constanta *) end;

procedure declvar;begin

if cl=ident then begin

intrare(variabila);anlex;

end;else eroare(11); (* lipseste nume simbolic *)

end;

procedure instructiune;var i:integer;

procedure expresie;procedure termen;

procedure factor;var i:integer;begin

if cl=ident thenbegin

i:=pozitie(id);if i=0 then eroare(12)else if ts[i].fel=procedura then eroare(13);anlex;

end;else if cl=numar then anlex

else if cl=prstinga then beginanlex;expresie;if cl=prdreapta then anlex;else eroare(14);endelse eroare(15); (* eroare de factor *)

end; (* factor *)begin (* termen *)

factor;while cl in [inm,impr] do

beginanlex;factor;

end;end;begin (*expresie*)

if cl in [plus,minus] then anlex;

59

termen;while cl in [plus,minus] do begin

anlex;termen;

end;end; (*expresie*)

procedure conditie;beginif cl=oddcl then begin

anlex;expresie;

endelse begin

expresie;if not(cl in [eq,ne,lt,le,gt,ge])then eroare(16);else begin

anlex;expresie;

end;end;

end;begin (*instructiune*)

if cl=ident then begin i:=pozitie(id);if i=0 then eroare(12); (*id nedeclarat*)if ts[i].fel <>variabila then eroare(17);anlex;if cl=atrib then anlex else eroare(18);expresie;

endelse if cl=callcl then begin

anlex;if cl<>ident then aroare(19) else begin

i:=pozitie(id);if i=0 then eroare(12)

else if ts[i].fel<>procedura then eroare(20);anlex;

end;endelse (*not callcl*)

if cl=begincl then beginanlex;instructiune;while cl=punctvirg do begin

anlex;instructiune; (* descendenta recursiva*)

end;if cl=endcl then anlex else eroare(21);

endelse if cl=ifcl then begin

anlex;conditie;if cl=thencl then anlex else eroare(22);instructiune; (* descendenta recursiva*)if cl=elsecl then begin

anlex;

60

instructiune;end;

endelse if cl=whilecl then begin

anlex;conditie;if cl=docl then anlex else eroare(23);instructiune;

endelse eroare(24);

end; (* instructiune *)

begin (* bloc *)if cl=constcl then

beginanlex;declconst;while (cl=virgula) do

beginanlex;declconst;

end;if cl=punctvirg then anlex else eroare(25);

end;if cl=varcl then

beginanlex;declvar;while (cl=virgula) do

beginanlex;declvar;

end;if cl=punctvirg then anlex else eroare(25);

end;while cl=procedurecl do

beginanlex;if cl=ident then

beginintrare(procedura);anlex;

endelse eroare(26);if cl=punctvirg then anlex else eroare(25);bloc(tx);if cl=punctvirg then anlex else eroare(25);

end (*while*)instructiune;

end; (*bloc*)

begin (*program main*)initalex;anlex;bloc(0);if cl<>punct then eroare(27);

61

99: writeln(‘fatal error’);end.

7.2. 4. Analizor sintactic predictiv nerecursiv C9Un algoritm recursiv poate fi transformat într-unul nerecursiv prin gestiunea explicită a unei

stive de lucru. Problema esenţială de rezolvat pentru un analizor sintactiv predictiv nerecursiv (ASPN) este de a alege în mod unic producţia pentru expandarea unui neterminal.

În varianta nerecursivă aceasta se realizează prin căutarea într-o tabelă de analiză sintactică. Din acest punct de vedere metoda este dirijată de tabele.

tampon de intrare

stiva ieşire

M

- Tamponul de intrare conţine şiruri care se încheie cu $- Stiva conţine simboluri gramaticale (terminale şi neterminale). Iniţial conţine simbolul

de start al gramaticii, urmat de simbolul $.- Tabela de ASPN are liniile etichetate cu neterminalele gramaticii şi coloanele etichetate

cu simbolurile terminale. O intrare în tabela este de forma: M[A,a], unde A este neterminal, a este terminal, iar M[A,a] poate fi o producţie sau poate fi intrare vidă.

- ‘Ieşire’ reprezintă acţiunile ce se execută la recunoaşterea unei producţii, iar aceste acţiuni pot fi mesaje de eroare în cazul intrărilor vide, arbori sintactici, cod virtual, etc. Analizorul va semnala la ieşire recunoaşterea şirului din intrare.

7.2.5. Funcţionarea unui ASPNNotând cu ‘X’ simbolul din vârful stivei şi cu ‘a’ simbolul din intrare, funcţionarea unui

ASPN poate fi formulată astfel: * dacă X=a=$, analiza se încheie cu succes* dacă X=a<>$ se extrage X din stivă şi se avansează pointerul din intrare; în acest caz s-a analizat cu succes simbolul din intrare* dacă X este neterminal, se analizează elementul M[X,a] şi în funcţie de valoarea lui, se execută următoarele acţiuni:

a. M[X,a] = X->UVW se elimină X din stivă şi în locul lui se introduce WVU astfel încât U sa apară în vârf

b. M[X,a] = vid, se apelează procedura pentru tratarea şi revenirea din erori

Algoritmul de analiză sintactică predictiv nerecursivă:intrare : şirul w şi tabela de analiză M corespunzătoare unei gramatici Gieşire : dacă w L(G) atunci şirul de derivări stânga pentru w, în caz contrar un mesaj de eroare

62

$

w $

ASPN

tabela de ASPN

stiva : iniţial conţine simbolul $ iar în vârf simbolul de start al gramaticii S

S$

tamponul de intrare : conţine şirul din intrare terminat de simbolul $

w $

* se poziţionează pointerul în intrare pe primul simbol din wrepeat * fie X simbolul din vârful stivei şi a simbolul curent din intrare * if X este un terminal sau $ then * if X =a then extrage X din stivă şi avansează pointerul în intrare else eroare()

else if M[X,a]={X->Y1 Y2 ... Yk} then

begin* extrage X din stiva* introdu în stiva Yk,...Y2,Y1

* tipareste producţia X->Y1 Y2 ... Yk

end else

eroare();until X=$;if simbolul de intrare<>$ then eroare().

Exemplu: Fie gramatica:G=({E, E', T, T', F}, {id, +, *, (,)}, P, E), unde producţiile P sunt:

E -> T E' E’ -> +T E’ | T -> F T’ T’ -> * F T’ | F -> (E) | id

Presupunem cunoscută tabela de analiză sintactică predictiv nerecursivă pentru gramatica dată:

Simbol de intrareNeterm./Term id + * ( ) $E E->TE' - - E->TE' - -E' - E'->+TE' - - E'-> E'->T T->FT' - - T->FT' - -T' - T'-> T'->*FT' - T'-> T'->F F->id - - F->(E) - -

Trasarea algoritmului pentru şirul de intrare: id + id * id

Stiva intrare iesire$E id+id*id$$E’ T id+id*id$ E->TE’$E’ T’ F id+id*id$ T->FT’$E’ T’ id id+id*id$ F->id$E’ T’ +id*id$ T’->$E’ +id*id$ E’ ->+TE’$E’ T+ +id*id$

63

$E’ T id*id$ T->FT’$E’ T’ F id*id$ F->id$E’ T’ id id*id$$E’ T’ *id$ T’ ->*FT’$E’ T’ F* *id$$E’ T’ F Id$ F->id$E’ T’ id id$$E’ T’ $ T’ ->$E’ $ E’->$ $ succes

Acţiunile analizorului materializate prin producţii tipărite urmăresc o derivare stânga a şirului de intrare. Simbolurile de intrare care au fost deja baleiate, urmate de simbolurile gramaticale din stivă (de la vârf spre bază) sunt forme propoziţionale stânga din derivare.

7.2.6. Funcţiile prim şi urmDupă cum rezultă din paragraful anterior, algoritmul de ASPN nu este dificil. Problema

dificilă este construirea tabelului M, în conformitate cu o gramatică G. Un pas intermediar în această construcţie o constituie calculul mulţimilor prim şi urm. În plus mulţimile urm sunt folosite la stabilirea erorilor de sincronizare la modul panică.

Mulţimea prim() conţine mulţimea simbolurilor terminale care pot apare la începutul unui şir terminal derivat din , inclusiv dacă poate fi derivat în şirul vid. ( poate fi terminal sau neterminal).

Mulţimea urm(A) conţine mulţimea simbolurilor terminale care pot urma după un şir derivat din neterminalul A în terminal. Un terminal aurm(A) dacă şi numai dacă există o derivare S=>* Aa unde şi sunt şiruri oarecare de simboluri. Dacă A este simbolul cel mai din dreapta al unei forme propoziţionale atunci urm (A).

Calculul funcţiei prim():* calculul este precedat de calculul prim(X) unde X este terminal sau neterminal al gramaticii* calculul se realizează prin aplicarea în mod repetat a următoarelor reguli până când nu se mai pot adăuga terminale noi sau la nici o multime prim

1. dacă X este terminal atunci prim(X)={X} (iniţializare)2. dacă X poate fi derivat în atunci prim(X)=3. dacă X este un neterminal şi X->Y1Y2.. Yk, atunci, prim(Y1) se include cu certitudine în

prim(X) mai puţin eventual . Dacă prim(Y1) atunci se include în prim(X) şi prim(Y2),etc., altfel calculul se opreşte.

Mulţimile prim pentru neterminalele gramaticii pe baza regulilor de mai sus sunt:prim(E)={ id , ( }prim(E’ ) ={ + , }prim(T) = { id , ( }prim(T’ ) = { * , }prim(F) = { id, ( }Etapele construirii acestei mulţimi sunt:

E E’ T T’ F+ * (, id iniţializare

(, id

regula E’-> regula T->FT’ regula T’->

(, id regula E->TE’

Se poate construi apoi următorul tabel:id + * ( )

prim (E) true false false true false falseprim (E’) false true false false false true

64

prim (T) true false false true false falseprim (T’) false false true false false trueprim (F) true false false true false false

Calculul mulţimii urm pentru neterminalele gramaticii se realizează prin aplicarea repetată a următoarelor reguli până când nu se mai pot adauga noi simboluri.1 Marcajul $ al sirului de intrare se adauga la urm(S). (iniţializare)2 Dacă în gramatica există o producţie de forma A -> B, atunci simbolurile din prim() mai putin aparţin lui urm(B) 3.Dacă în gramatica există o producţie de forma A -> B sau o producţie A -> B cu prim(), atunci adaugă urm(A) la urm(B).

Pentru exemplul dat avem următoarele etape ale construirii acestei mulţimi:E E’ T T’ F$ iniţializare

)+

*

regula E’ -> +T E’ regula F->(E)regula T’ -> * F T’

$ , )$ , )

$,),+$,),+

regula E->TE’ regula E’ -> +T E’ regula T->FT’ regula T->FT’

$ , ) $ , ) +,$,) $,),+ *,$ , ),+ Final

- Adaug $ la urm(E) deoarece E este simbolul de start - Deooarece E’ -> +T E’ , prim(E’ ) mai puţin se include în urm(T), adică +- Deoarece F -> (E) , se include ) în urm(E)- Deoarece T’ -> * F T’ , se include prim(T’) mai puţin în urm(F), adică * - Deoarece E -> T E' se adaugă urm(E) la urm(E'), adică $ şi )- Deoarece prim(E') şi E’ -> +T E’ se adaugă urm(E') la urm(T), adică ) şi $- Deoarece T -> F T’ , se adaugă urm(T) la urm T', adică $,),+ - Deoarece prim(T') şi T’ -> * F T’ se adaugă urm(T') la urm F, adică $,),+

Se poate construi apoi următorul tabel:

id + * ( ) $urm (E) false false false false true trueurm (E’) false false false false true trueurm (T) false true false false true trueurm (T’) false true false false true trueurm (F) false true true false true true

urm(E ) = { $ , ) } urm(T’ ) = { + , ) , $ }urm(E’) = { $ , ) } urm(F ) = { * , +, ) , $ }urm(T ) = { + , ) , $ }

7.2.7. Construirea tabelului ASPN

După cum s-a aratat deja, tabelul de analiză, M[A,a] va conţine:- fie o producţie care este folosită pentru expandarea neterminalului A din vârful stivei atunci când

în intrare apare simbolul a - fie M[A,a] este vidă, adică starea (A,a) nu poate apare pentru un şir de intrare corect.

Algoritm pentru construirea tabelului ASPN.*la intrare avem o gramatică G, iar la ieşire se obţine tabela M pentru ASPN

65

1. Pentru fiecare producţie a gramaticii de forma A-> se aplică paşii 2 şi 32. Pentru simbolul a prim(), intrările M[A,a] devin A -> 3. Dacă prim(), atunci pentru b urm(A) se completează M[A,b] cu producţia A-> . Dacă prim() şi $ urm(A) atunci M[A,$] va conţine A-> 4. Intrările rămase necompletate în urma paşilor 2 şi 3 reprezintă intrări de eroare (vor fi

vide).

Adică:Pentru fiecare A-> execută:

Pentru fiecare a prim(A) adaugă A-> la M[A,a]if prim() then

Pentru fiecare b urm(A) adaugă A-> la M[A,b]Intrările rămase necompletate vor fi vide şi reprezintă intrări de eroare.

Ideea de bază a algoritmului este : se va expanda neterminalul A în şirul dacă a prim() sau dacă = (eventual =*> ) şi a urm(A) sau dacă a = $ urm(A).

Folosind funcţiile prim şi urm deja teterminate:

prim(E)={ id , ( }prim(E’) ={ + , }prim(T) = { id , (}prim(T’ ) = { *, }prim(F) = { id, ( }

urm(E ) = { $ , ) }urm(E’ ) = { $ , ) }urm(T ) = { + , ) , $ }urm(T’ ) = { + , ) , $ }urm(F ) = { * , +, ) , $ }

E -> T E' E’ -> +T E’ | T-> F T’ T’ ->*FT’|F -> (E) | id

Vom obţine abela de ASPN construită pe baza regulilor enunţate:

Simbol de intrareNeterminal id + * ( ) $E E->TE' - - E->TE' - -E' - E'->+TE' - - E'-> E'->T T->FT' - - T->FT' - -T' - T'-> T'->*FT' - T'-> T'->F F->id - - F->(E) - -

M[E,id] = E->TE’ , M[E,(] = E->TE’ prin urmare ‘id’ şi ‘(‘ aparţin lui prim(T)

7.2.8. Gramatici LL(1) (independente de context) analizabile cu ASPNÎn principiu, algoritmul de construire a tabelei se poate aplica pentru orice gramatică. Pentru

unele gramatici însă, tabela M poate avea intrări multiplu definite (mai multe producţii pentru acelaşi element al gramaticii).

Dacă gramatica este recursivă la stânga sau este ambiguă, atunci tabela va conţine cel puţin o intrare multiplu definită.

De exemplu, pentru instructiunea if:<instr> -> if <expresie> then <instr> <altern> | a<altern> -> else < instr> | <expr> -> b

Tabela de ASPN:

simbol terminal

Neterminal a b else if then $<instr> <instr>->a 1<altern> 2 <altern>-><expr> <expr>->b

66

unde:1= <instr> -> if <expr> then <instr> <altern>2=<altern> -> else <instr> <altern> ->

Elementul M[<altern>, else] este dublu definit deoarece Urm(<altern>)={else,$}. Cauza este ambiguitatea gramaticii manifestată la alegerea producţiei ce trebuie aplicată în momentul apariţiei lui else în intrare, cunoscută ca problema ataşării lui else. Pentru a ataşa else cu cel mai apropiat then care îl precede alegem producţia <altern> -> else <instr>.

Definiţie: Gramaticile independente de context care permit o analiză descendentă fără reveniri folosindu-se eventual de următoarele k simboluri din intrare se numesc gramatici LL(k).

Primul L semnifică faptul că preluarea simbolului din intrare se face de la stânga la dreapta, iar al doilea L faptul că la analiză se doreşte reconstituirea unei derivări stânga. În practică se utilizează de obicei cazul când k=1, caz în care pentru analiză se foloseşte un singur simbol din intrare, cel curent. Observaţie: Aplicând algoritmul de ASPN prezentat pentru o gramatică LL(1), nu rezultă intrări multiplu definite.

Aplicând algoritmul de construire a tabelei pentru ASPN în cadrul gramaticii LL(1) rezultă o singură tabelă care va recunoaşte forme propoziţionale corecte din gramatica L(G) şi doar pe acestea, deci metoda este corectă şi completă. Nici o gramatică ambiguă sau recursivă la stânga nu poate fi LL(1).

Considerăm producţiile A -> 1 | 2 | . |n dintr-o gramatică.Definiţie: O gramatică independentă de context este LL(1) dacă pentru orice neterminal al gramaticii sunt îndeplinite următoarele două condiţii:

prim(i) prim(j) = mulţimea vidă, oricare ar fi i,j în intervalul [1,n] cu i<>j; adică: luând în considerare oricare două părţi drepte, nu se pot deriva din ambele şiruri care încep cu acelaşi terminal, sau eventual

dacă prim(i) oricare ar fi i în intervalul[1,n], atunci urm(A)prim(j) este mulţimea vidă, unde 1<=j=<=n, i<>j; cu alte cuvinte: dacă dintr-o anumită parte dreaptă se poate deriva şirul vid, atunci din oricare din celelalte părţi drepte nu se pot deriva şiruri care să înceapă cu un terminal.

Dacă gramatica respectă cele două condiţii, atunci este LL(1). Se pune întrebarea: cum trebuie procedat dacă la construirea tabelei de analiză apar intrări

multiplu definite. Prima soluţie este de a transforma gramatica prin eliminarea recursivităţii de stânga şi a ambiguităţii. Există însă gramatici neambigue şi nerecursive la stânga (if) care nu sunt LL(1). În astfel de cazuri se pot introduce reguli euristice pentru alegerea producţiilor corecte în cazul intrărilor multiplu definite. În exemplul anterior s-a ales în mod arbitrar varianta M[<altern>, else] = <altern> -> else <instr>.

În general nu există reguli universale prin care intrările multiplu definite din tabela M se pot reduce la o singură valoare fără a afecta limbajul recunsocut de analiză. În concluzie, principala dificultate în utilizarea ASPN constă în scrierea gramaticii pentru limbajul sursă astfel încât să se poată construi tabela de analiză.

Deşi eliminarea recursivităţii de stânga şi factorizarea la stânga sunt uşor de realizat, aceste operaţii complică atât gramatica cât şi aplicarea gramaticii în traducere. De asemenea gramatica recunoscută pierde din acurateţe. Din punct de vedere practic, instrucţiunile sunt analizate prin metoda ASPN iar expresiile vor fi analizate prin alte metode, de obicei cele bazate pe precedenţa operatorilor.

7.2.9. Revenirea din erori în cazul ASPNAnaliza sintactică încearcă o punere în corespondenţă a simbolurilor (terminale şi

neterminale) din stivă cu simbolurile din intrare. O eroare sintactică poate apare în următoarele două cazuri:

67

- simbolul terminal din vârful stivei nu coincide cu simbolul din intrare- simbolul neterminal din vârful stivei împreună cu simbolul din intrare selectează în tabela

de ASPN o intrare vidăRevenirea din eroare în modul panică:

Principial, metoda se bazează pe eliminarea de simboluri din intrare până la apariţia unui atom dintr-o mulţime de atomi de sincronizare. Calitatea tratării erorilor depinde de alegerea mulţimii de sincronizare.

Regulile pentru construirea mulţimii atomilor de sincronizare sunt:

1. Mulţimea atomilor de sincronizare pentru A este iniţializată cu urm(A), aceasta înseamnă că se vor elimina succesiv din intrare simboluri până la apariţia unui simbol din urm(A), în continuare se elimină A din vârful stivei şi există posibilitatea de a continua în mod normal analiza

2. Fixarea mulţimii atomilor de sincronizare pe urm(A) nu este suficientă în cazul limbajelor în care ‘;’ este terminator (C,Pascal). În acest caz, la atomii de sincronizare pentru neterminalele corespunzatoare expresiilor, se adaugă mulţimea cuvintelor cheie cu care încep instrucţiunile. Altfel, absenţa lui ‘;’ poate duce la omiterea cuvintelor cheie cu care începe instrucţiunea următoare, ceea ce înseamnă că o posibilă revenire din erori va fi tardivă.

Fiecare limbaj are o structură ierarhică a construcţiilor potrivit căreia se includ expresiile în instrucţiuni, etc. De aceea, o soluţie este ca la mulţimea atomilor de sincronizare pentru construcţiile inferioare să se adauge simbolurile cu care încep construcţiile superioare (de exemplu pentru expresii se adaugă terminalele cu care încep instrucţiunile).

3. În situaţia în care în mulţimea atomilor de sincronizare pentru neterminalul A se includ simbolurile din prim(A), analiza s-ar putea relua chiar cu A în vârful stivei ( nu se mai extrage A din stivă).

4. dacă neterminalul din vârful stivei poate genera şirul vid atunci producţia din care derivă se poate aplica implicit în caz de eroare iar prin expandarea neterminalului respectiv la şirul vid el va fi extras din stivă. Procedând astfel se va întârzia detectarea erorilor fără a se omite cuvintele cheie. Prin această regulă se va reduce numărul de neterminale care trebuie considerate la tratarea erorilor.

5. dacă terminalul din vârful stivei nu coincide cu terminalul din intrare se elimină terminalul din vârful stivei şi se afişează un mesaj de eroare. Prin urmare, mulţimea atomilor de sincronizare pentru terminale este formată din toate celelalte terminale.

simbol de intrareNetermi-nale

id + * ( ) $

E E’->TE’ - - E->TE’ - SincE’ - E’->e TE’ - - E’ -> E’ ->T T->FT’ sinc - T->FT’ sinc SincT’ - T’ -> T’->*FT’ - T’ -> T’ ->F F->Id sinc sinc F->(E) sinc Sinc

Intrările de sincronizare au fost completate aplicând regula 1 pe baza simbolurilor din mulţimea următoare.

Analiza sintactică în caz de eroare decurge astfel:1. în vârful stivei se află neterminalul A:* se va căuta dacă M[A,a] este vid, atunci se va omite simbolul curent din intrare, a*dacă M[A,a] conţine atom de sincronizare atunci se va extrage A din vârful stivei şi avansăm

în intrare până când simbolul curent este prezent în mulţimea sinc2. dacă în vârful stivei este un terminal care nu coincide cu simbolul de intrare curent, atunci

se va omite simbolul din vârful stivei, conform regulii 5

În toate situaţiile, după efectuarea operaţiilor de mai sus se va relua analiza. Fie şirul de intrare ) id * + id

68

Stiva Intrare concluzii$E )id*+id$ M[E,)]=vid =>error!$E id*+id$$E’ T id*+id$$E’ T’F id*+id$$E’ T’ id id*+id$$E’ T’ *+id$$E’ T’ F* *+id$$E’ T’ F +id$ M[F,+] => sinc => error!$E’ T’ +id$ intrarea îl conţine pe +, rămâne intrare cu +$E’ +id$$E’ T+... +id$

Analiza de mai sus a neglijat problema mesajelor de eroare, care rămâne totuşi importantă pentru proiectarea compilatorului şi trebuie şi ea tratată.

Un alt mod de tratare a erorilor care se poate aplica este revenirea la nivel de propoziţie. În acest caz intrările vide din tabela de analiză se completează cu pointeri spre rutine de

tratare a erorilor. Aceste rutine acţionează de obicei asupra simbolului curent din intrare şi în principiu pot schimba simbolul curent din intrare cu altul, îl şterg sau inserează un simbol nou (cerut de situaţia din stivă) şi emit în paralel şi un mesaj de eroare. Se pot concepe rutine de tratare care să acţioneze şi asupra stivei, cu precizarea că eliminarea sau inserarea unui simbol în stivă strică procesul de derivare şi poate să conducă la situaţii în care şirul final nu corespunde nici unei porpoziţii sau derivări din limbaj. De asemenea, există pericolul de a intra în ciclu infinit. Acesta se poate evita cu certitudine dacă se adoptă măsura ca în urma oricărei acţiuni de revenire să se avanseze cel puţin un simbol în intrare, iar dacă intrarea s-a epuizat, atunci să se avanseze în stivă.

8. Analiza sintactică ascendentă. Prezentare generalăC10

Se va prezenta un tip general de analizor numit “cu deplasare şi reducere”. Acesta încearcă să construiască arborele sintactic pentru şirul de intrare începând de la frunze spre rădăcină (ascendent).

- Procesul poate fi privit ca o reducere a unui şir de terminale la simbolul de start al gramaticii. - În fiecare pas al reducerii se caută în forma propoziţională curentă localizarea unui subşir

care să corespundă părţii drepte a unei producţii. Acest subşir se înlocuieşte cu partea stângă a producţiei respective. Dacă subşirul este corect ales, la fiecare pas se va parcurge în sens invers o derivare dreapta.

Exemplu : fie gramatica:S ->aABeA->Abc|bB->d

Pentru şirul de intrare abbcde avem următoarea parcurgere în sens invers a unei derivări dreapta: abbcde -> aAbcde -> aAde -> aABe -> SReducerile corespund parcurgerii în sens invers a următoarei derivări drepte:

S -> aABe -> aAde -> aAbcde -> abbcde

8.1. Capete

Un capăt al unui şir este un subşir care corespunde părţii drepte a unei producţii şi a cărui înlocuire cu neterminalele din partea stângă a producţiei reprezintă un pas în parcurgerea în sens invers a unei derivări dreapta.

Nu toate subşirurile care sunt părţi drepte ale unei producţii A-> şi care pot fi localizate ca subşiruri ale unei forme propoziţionale sunt în acelasi timp şi capete pentru că este posibil ca prin

69

reducerea lui la A procesul de reducere să se blocheze fără să se poată face reducerea la simbolul de start al gramaticii.

Exemplu: dacă se aplică reducerea aAbcde -> aAAcde procesul se va bloca.

Rezultă că trebuie dată o definiţie mai riguroasă noţiunii de capăt: Fiind dată o formă propoziţională ,, un capăt al său constă:- dintr-o producţie A-> şi - dintr-o propoziţie în în care poate fi localizat şirul astfel încât prin înlocuirea cu A se

obţine forma propoziţională anterioară a unei derivări dreapta a lui .

Exemplu: S=*> A => ; capătul este format din producţia A-> şi din propoziţia care urmează lui .

Observaţie: şirul , situat în dreapta capătului conţine numai terminale. În cazul în care gramatica este ambiguă, şirul s-ar putea obţine prin mai multe derivări

dreapta. Rezultă că el ar putea să conţină mai multe capete (deci ambiguitatea e o problemă). Dacă gramatica nu este ambiguă, capătul corespunzător unei anumite forme propoziţionale este

unic. Grafic, procesul de reducere al unui capăt se poate reprezenta astfel:

S

a A B e

A B c

Capătul reprezintă cel mai din stângă subarbore complet, format dintr-un nod şi toţi fiii săi. Părintele (în cazul nostru A) este nodul cel mai de jos şi cel mai din stânga având toţi fiii prezenţi în arbore sub formă de frunze. Reducerea unui capăt la partea stângă a producţiei respective se numeşte fasonarea capătului şi constă din îndepărtarea fiilor lui A din arborele sintactic.

Exemplu: fie gramatica ambiguăE -> E + EE -> E * EE -> (E)E -> id

pentru şirul de intrare: id+ id * id(1) E =d> E + E =d> E + E * E =d> E + E * id3 =d> E + id2 * id3 =d> id1 + id2 * id3

Se observă că şirurile situate în dreapta unui capăt conţin exclusiv simboluri terminale. Gramatica dată fiind ambiguă există şi următoara derivare dreapta distinctă de prima:

(2) E =d> E * E =d> E * id3 =d> E + E * id3 =d> E + id2 * id3 =d> id1 + id2 * id3În exemplul dat există 2 capete, corespunzătoare primei şi respectiv celei de-a doua derivări

dreapta prezentate. Existenţa celor 2 derivări dreapta semnifică priorităţi relative diferite ale operatorilor ‘*’ şi ‘+’. La primul model de derivare este mai prioritar ‘*’.

8.2. Fasonarea capetelor

Fasonarea capetelor se poate considera şi ca procesul de parcurgere în sens invers a unei derivări dreapta. Se porneşte de la un şir de analizat. Dacă aparţine limbajului descris de gramatica dată, atunci el se poate obţine dintr-un pas oarecare n al unei derivări dreapta încă necunsocute, dar care are următoarea formă:

S =d> 0 =d> 1 =d> … =d> n =d> Reconstituirea în sens invers a acestei derivări constă în localizarea în forma propoziţională n a

unui capăt n şi înlocuirea lui cu partea stângă a producţiei. An -> n, obţinându-se astfel forma propoziţională n-1. Apoi se continuă procedeul cu n-1 etc. Dacă în final s-a ajuns la simbolul de start al gramaticii, înseamnă că procesul de analiză s-a încheiat cu succes.

70

Exemplu: Considerăm din nou gramatica din exemplul precedent:E -> E + E | E -> E * E | E -> (E) | E -> idcu şirul de intrare: id1 + id2 * id3Secvenţa de reduceri prezentată în continuare reprezintă inversul secvenţei din prima derivare

(unde * este mai prioritară: E =d> E + E =d> E + E * E =d> E + E * id3 =d> E + id2 * id3 =d> id1 + id2 * id3)

forma propoziţională dreapta capăt producţie pentru reducereid1 + id2 * id3 id1 E -> idE + id2 * id3 id2 E -> idE + E * id3 id3 E -> idE + E * E E * E E -> E * EE + E E + E E -> E + E

8.3. Implementarea cu stivă a analizei sintactice de tip deplasare-reducere

Pentru implementarea analizei sintactice bazată pe fasonarea capetelor trebuiesc rezolvate două probleme:1. Localizarea subşirului care urmează să fie redus în forma propoziţională curentă2. În cazul în care gramatica are mai multe producţii cu aceeaşi parte dreaptă, trebuie să decidem care

este producţia ce se va aplica.

Ca structură de date de bază se poate utiliza o stivă în care se vor deplasa simbolurile gramaticale din tamponul de intrare şi se vor localiza capetele.

- Tamponul de intrare conţine şirul de analizat . - Baza stivei şi respectiv extremitatea dreaptă a şirului de intrare vor fi marcate printr-un simbol

special ‘$’.- La început stiva este goală, conţine doar simbolul ‘$’ iar la intrare şirul este $. - La fiecare pas al analizei, analizorul deplasează în stivă 0 sau mai multe simboluri de intrare,

până în momentul în care în vârful stivei apare un capăt , apoi se reduce la partea stângă a producţiei respective şi se continuă ciclic aceste operaţii, fie până când stiva conţine doar simbolul de start şi intrarea este goală, fie până când se detectează o eroare.

- În configuraţia finală, stiva va conţine ‘$S’ iar în intrare vom avea simbolul ‘$’. Dacă se ajunge în această configuraţie fără eroare, se va semnala terminarea cu succes a analizei.

Exemplu:stiva intrare actiune$ id1 + id2 * id3 $ deplasare$ id1 + id2 * id3 $ reducere E->id$ E + id2 * id3 $ deplasare$ E + id2 * id3 $ deplasare$ E + id2 * id3 $ reducere E -> id$ E + E * id3 $ deplasare$ E + E * id3 $ deplasare$ E + E * id3 $ reducere E -> id$ E + E * E $ reducere E -> E * E$ E + E $ reducere E -> E + E$ E $ succes

Din acest exemplu rezultă că analizorul execută următoarele 4 acţiuni 1 Deplasare: simbolul de intrare curent este introdus în stivă

71

2 Reducere: se realizează în situaţia în care extremitatea dreaptă a unui capăt se află în vârful stivei; analizorul trebuie să localizeze extremitatea să stângă, să stabilească neterminalul cu care trebuie înlocuit capătul şi să realizeze efectiv reducerea lui.

3 Acceptare: analizorul semnalează terminarea cu succes a analizei4 Eroare: se apelează o rutină de eroare dacă s-a detectat un caz de eroare

Observaţie: utilizarea stivei ajută la localizarea capătului pentru că el va fi situat întotdeauna în varful stivei.

Modalitatea concretă a alegerii uneia dintre acţiuni depinde de tipul concret de analiză, care poate fi de mai multe feluri:

- bazată pe precedenţa operatorilor- de tipul left-right

8.4. Prefixe viabile

Mulţimea prefixelor formelor propoziţionale dreapta care pot să apară în stiva unui analizor sintactic cu deplasare şi reducere se numesc prefixe viabile.

Altfel spus, un prefix viabil este un prefix al unei forme propoziţionale dreapta care nu continuă dincolo de extremitatea dreaptă a celui mai din dreapta capăt al acelei forme propoziţionale.

Consecinţa acestei definiţii este aceea că întotdeauna este posibil să se adauge simboluri terminale la extremitatea unui prefix viabil pentru a obţine o formă propoziţională dreapta.

Pe parcursul analizei sintactice nu va apare nici o eroare atâta timp cât porţiunea de intrare văzută până la un anumit punct poate fi redusă la un prefix viabil.

8.5. Conflicte în timpul analizei sintactice cu deplasare şi reducere

- Există gramatici independente de context la care nu se poate aplica analiza sintactică cu deplasare şi reducere. Pentru o astfel de gramatică, analizorul poate ajunge într-o configuraţie în care, cunoscând întreg conţinutul stivei şi următoarele simboluri din intrare, nu se poate decide dacă trebuie efectuată o deplasare sau o reducere. Acest tip de conflict se numeşte conflict deplasare-reducere.

- În alte situaţii analizorul nu poate decide ce reducere să efectueze dintre mai multe posibile. Este cazul conflictelor reducere-reducere.

Observaţie: - Gramaticile în care nu pot apare astfel de conflicte se numesc gramatici LR.- Clasa gramaticilor pentru care pot să apară astfel de conflicte nu se incadrează în clasa

LR. Exemplu:Gramatica instrucţiunii if , care este ambiguă nu este LR.<instructiune> -> if <expr> then <instr> |

if <expr> then <instr> altceva

stiva intrareif <expr> then <instr> else … $

Pentru configuraţia dată, nu se poate decide dacă vârful stivei este un capăt sau nu. Avem deci un conflict deplasare-reducere, întrucât în funcţie de ceea ce urmează în intare, poate fi corect să se reducă if <expr> then <instr> la <instr> sau ar putea fi corect să se deplaseze else din intrare în stivă , urmat de căutarea unei alte <instr>, pentru ramura de else.

Deoarece nu se poate lua decizia pe baza unui singur simbol de anticipare, se spune că gramatica nu este LR1.

În general, nici o gramatică ambiguă (ca cea de sus) nu poate să fie LRk, oricare ar fi k N*. Analizorul sintactic cu deplasare-reducere poate fi uşor adaptat pentru a analiza şi gramatici

ambigue ca cea de mai sus prin decizia ca orice conflict de tipul deplasare-reducere să se rezolve în favoarea deplasării. Se observă că luând această decizie în situaţia de mai sus, analiza decurge corect.

72

O altă situaţie pentru gramaticile non LR este atunci când se localizează cu certitudine un capăt, dar conţinutul stivei şi simbolul curent din intrare nu sunt suficiente pentru a determina care producţie trebuie utilizată pentru reducere (conflict reducere-reducere).

Exemplu: dispunem de un analizor lexical care furnizează atomul lexical id pentru orice identificator, indiferent de utilizarea acestuia (cazul normal). Presupunem că în limbajul ales apelurile de proceduri pe de o parte şi referirea elementelor de tablou pe de altă parte, au aceeaşi formă sintactică, adică un nume şi argumentele între paranteze. Deoarece din punct de vedere semantic traducerea indicilor în referinţe de tablou diferă substanţial de traducerea argumentelor la apelurile de proceduri şi funcţii, trebuie să utilizăm producţii diferite pentru a genera listele de indici şi respectiv listele de argumente, ca în gramatica următoare:

(1) <instr> -> id (<lista_param>)(2) <instr> -> <expresie> :=<expresie>(3) <lista_param> -> <lista_param>,<parametru>(4) <lista_param> -> <parametru>(5) <parametru> -> id(6) <expresie> -> id (<lista_expr>)(7) <expresie> -> id(8) <lista_expr> -> <lista_expr>,<expresie>(9) <lista_expr> -> <expresie>

Considerăm o instrucţiune care începe cu a(i,j) şi presupunem că am ajuns în situaţia în care primii trei atomi au fost transferaţi în stivă.

stiva intrare… ( id id )… $Este evident că id din vârful stivei trebuie redus, dar nu se ştie care dintre producţii trebuie

utilizată. Dacă ‘a’ este procedura, ar trebui aleasă pentru reducere producţia (5), iar dacă a este element de

tablou, trebuie aplicată producţia (7). Pentru a lua o decizie, ar trebui consultată tabela de simboluri (dacă acolo informaţiile sunt

completate). O soluţie pur sintactică la această situaţie constă în modificarea analizorului lexical astfel încât să

furnizeze un atom distinct (procid) când ‘a’ este un nume de procedură.Cu modificarea propusă, pentru cazul când în situaţia de mai sus este un apel de procedură,

conţinutul stivei şi al intrării este următorul:

stiva intrareprocid ( id , id ) … $

Astfel, devine clar că reducerea lui id se face prin (5).Observaţie:

- Decizia privind reducerea este luată pe baza simbolului al treilea de sub vârful stivei (procid) care nici măcar nu participă la reducere.- Rezolvarea conflictelor reducere-reducere pe baza modificărilor de gramatică este metoda generală de rezolvare a acestei situaţii

(1) <instr> -> procid ( <lista_param>)

8.6. Analiza sintactică bazată pe precedenţa operatorilor

Acest tip de analiză sintactică se poate aplica doar la o clasă redusă de gramatici, dar este importantă datorită răspândirii ei şi are avantajul că analizorul se poate construi uşor manual.

Printre alte cerinţe esenţiale, gramatica la care se aplică acest tip de analiză, trebuie să aibă urmatoarele două proprietaţi:1. Să nu aibă producţii vide2. În nici o producţie să nu existe o parte dreaptă care să conţină două neterminale adiacente.

73

Gramaticile care respectă condiţia 2 se numesc gramatici de operatoriE -> EAE | (E) | -E | idunde A poate fi:A -> + | - | * | / | ^

Dacă se substituie A atunci se obţine E -> E + E | E – E | E * E | E / E | E ^ E | (E) | -E | id

Acest mod de transformare este general şi se va urmări cu precădere. O gramatică de operatori nu trebuie neapărat să fie o gramatică de expresii.

Metoda are şi importante dezavantaje- sunt dificil de prelucrat atomi care au 2 precedenţe diferite (de ex. semnul ‘-‘)- Relaţia dintre analizor şi gramatică nu este întotdeauna biunivocă; este posibil ca analizorul să

accepte şiruri (considerându-le corecte), care nu fac parte din limbajul gramaticii (deci nu se semnalează toate erorile).

- Clasa de gramatici acceptate este redusăDatorită simplităţii ei, această tehnică s-a utilizat în multe compilatoare existente pentru analiza

expresiilor, în timp ce instrucţiunile limbajului şi celelalte construcţii de nivel înalt sunt analizate prin alte metode (de exemplu cu descendenţi recursivi). Există totuşi şi compilatoare bazate complet pe această tehnică.

8.6.1. Definirea relaţiei de precedenţă

În analiza sintactica bazată pe precedenţa operatorilor se definesc 3 relaţii de precedenţă disjuncte: <, =, > care se stabilesc între anumite perechi de terminale ale gramaticii. Pe baza acestor relaţii se selectează capătul formei propoziţionale în stiva analizorului. Semnificaţia lor este următoarea:

relatia semnificaţiaa < b a cedează precedenţa lui ba = b a are aceeaşi precedenţă cu ba > b a are precedenţă faţă de b

Aceste relaţii se deosebesc în esenţă faţă de relaţiile similare din algebră:- au cu totul altă semantică decât precedenţa algebrică- este posibil ca între 2 terminale să nu existe nici o relaţie de precedenţă- este posibil ca între 2 terminale să existe 2 relaţii de precedenţă

Stabilirea relaţiei de precedenţă între terminale se poate face pe 2 căi:1. Intuitiv, pornind de la semnificaţia algebrică a operatorilor şi ţinând cont de asociativitatea lor:

*> +, + < *Prin introducerea acestor două relaţii se rezolvă şi ambiguitatea gramaticii expresiilor, fără să mai fie necesară transformarea ei2. În mod automat, aplicând un algoritm adecvat; pentru această variantă trebuie eliminată în prealabil ambiguitatea din gramatică astfel încât ea să reflecte corect asociativitatea şi precedenţa operatorilor.

8.6.2. Utilizarea relaţiilor de precedenţă a operatorilor

Scopul introducerii relaţiilor de precedenţă este acela de a determina capătul în forma propoziţională dreapta curentă. Astfel, simbolul < marchează extremitatea stângă a capătului, = interiorul unui capăt, iar > marchează extremitatea dreaptă a capătului.

Pentru detalii, considerăm o formă propoziţională dreapta a unei gramatici de operatori. Deoarece părţile drepte ale producţiilor nu conţin două neterminale adiacente, rezultă că în nici o formă propoziţională dreaptă nu pot apare 2 neterminale adiacente.

La modul general, o formă propoziţională dreapta de acest fel poate fi notată astfel: 0 a1 1 an n

unde fiecare i este fie , fie un singur neterminal şi fiecare ai este un singur terminal.

74

Într-o astfel de formă propoziţională dreapta, se caută relaţia de precedenţă între perechi de terminale vecine, presupunându-se că între ele există o unică relaţie de precedenţă.

Extremităţile şirului de analizat, se marchează cu $ şi se introduc relaţiile de precedenţă: $ <a şi a>$.

În continuare, se elimină neterminalele din şir iar în şirul rămas (conţinând numai terminale şi $) se introduc relaţiile de precedenţă corecte, <,=,>.

Capătul se determină prin următorul procedeu:1. Se baleiază şirul cu relaţia de precedenţă introdusă din extremitatea să stângă până la întâlnirea

primului >; acesta va reprezenta marginea dreaptă a capătului.2. Se baleiază şirul înapoi, omiţând eventualele simboluri = până se întâlneşte primul marcaj <, acesta

va fi marginea stângă a capătului.3. Se consideră ca fiind capăt, şirul de simboluri gramaticale dintre cele 2 marcaje, inclusiv neterminalele

care apar ca incluse, sau înconjoară terminalele dintre marcaje. Considerarea neterminalelor înconjurătoare este necesară pentru a asigura că nu vor apare două neterminale adiacente în forma propoziţională următoare.

Exemplu: se consideră şirul de intrare $ id + id * id $ şi matricea de relaţii de precedenţă redusă de mai jos:

id + * $id > > >+ < > < >* < > > >$ < < <

În tabelă, operatorul de adunare este asociativ la stânga, în timp ce operatorul de înmulţire asociativ la dreapta

Şirul iniţial, cu relaţiile de precedenţă introduse este următorul:

$ < d > + < id > * < id > $ $ E + E * E $ capăt $ < + < * > $ E -> E * E$ E + id * id $ $ E + E $$ < + < id > * < id > $ $ < + > $$ E + E * id $ $ E $ => sfarsit$ < + < * < id > $

Observaţie: deoarece neterminalele nu influienţează analiza, nu trebuie făcută distincţie între ele.

În stiva analizorului este suficient să se ţină un singur marcaj reprezentativ pentru orice fel de terminal pentru a marca doar locul din stivă corespunzator acelui neterminal, folosit pentru a înregistra atributele semantice corespunzătoare neterminalului respectiv.

Aparent, din exemplul de mai sus s-ar putea deduce că pentru determinarea capătului ar fi necesară baleierea întregii forme propoziţionale sau, în orice caz, a unei mari porţiuni din ea. Acest lucru nu este însă necesar, deoarece implementarea concretă se face tot pe baza mecanismului de analiză sintactică cu deplasare şi reducere, iar relaţiile de precedenţă sunt utile doar pentru a dirija acţiunile analizorului (deplasare sau reducere). Acţiunile analizorului sunt cele cunoscute :1. Deplasare: cât timp nu s-a găsit extremitatea dreaptă a capătului, adică, între simbolul terminal cel mai

apropiat de vârful stivei şi simbolul curent din intrare este valabilă una din realaţiile: < sau =.2. Reducere: când s-a găsit extremitatea dreaptă a capătului, adică între terminalul cel mai propiat din

vârful stivei şi simbolul de intrare există relaţia >, se baleiază în sens invers stiva până la întâlnirea primului marcaj <, după care se face reducere.

3. Acceptare: când ambele simboluri care se compară ( adică vârful stivei şi simbolul curent din intrare) sunt ‘$’

4. Eroare: dacă se compară 2 simboluri între care nu există relaţie de precedenţă.

75

Aceste idei privind mecanismul de analiză sintactică bazată pe precedenţa operatorilor sunt cuprinse în următorul algoritm:

Algoritmul primeşte la intrare şirul w de analizat şi matricea relaţiilor de precedenţă. Dacă w este corect, se va obţine la ieşire un schelet al arborelui său sintactic, în caz contrar un mesaj de eroare, datorită substituirii intermediare a neterminalului, motiv pentru care nodurile interioare vor fi uniforme.stiva intrare $ w$(1) * se poziţionează pointerul de intrare pe primul simbol din w(2) repeat forever

if *atât simbolul din vârful stivei cât şi simb. curent de intrare sunt $ then returnelse begin *fie ‘a’ simbolul terminal cel mai apropiat de vârful stivei,

‘b‘ simbolul curent din intrare if (a < b) or ( a=b) then

begin {deplasare} * introdu b în stivă * avansează cu o poziţie pointerul de intrareendelse if (a >b) then {reducere}

repeat* extrage din stivăuntil *terminalul din vârful stivei este în relaţie < cu terminalul cel mai recent extras

else *eroareend;

8.6.3. Deducerea intuitivă a relaţiei de precedenţă din asociativitatea şi prioritatea algebrică a operatorilor

Singura cerinţă care trebuie avută în vedere este aceea ca relaţia de precedenţă să conducă la analiza corectă a limbajului defninit de gramatică.

Ţinând cont de faptul că analiza sintactică bazată pe precedenţa operatorilor se aplică la gramatici pentru expresii, sau gramatici similare cu acestea, iar între operatorii din expresii există reguli de prioritate şi asociativitate riguroase care rezolvă eventualele ambiguităţi, aceste reguli pot reprezenta baza pentru stabilirea relaţiei de precedenţă.

Pentru cazul operatorilor binari, notaţi cu , 1, 2 relaţiile de precedenţă pot fi deduse astfel:

1. dacă 1 este mai prioritar algebric decât 2, se introduc în tabelă relaţiile 1 > 2 şi 2 < 1.

2. dacă 1 şi 2 au prioritate algebrică egală (inclusiv când reprezintă acelaşi operator) apar următoarele 2 situaţii:

a. 1 şi 2 sunt asociativi la stânga1 > 2 şi 2 > 1

b. 1 şi 2 sunt asociativi la dreapta1 < 2 şi 2 < 1

3. pentru orice operator există următoarele relaţii de precedenţă cu celelalte terminale:

id ( şi ) < id > )

76

id > ) > < ( > $( < $ > $

Pentru a asigura reducerea la E a lui id şi a lui (E), între terminalele care nu sunt operatori se introduc următoarele relaţii:

( = ) $ < ( $ id( < ( id > $ ) < $( < id id > ) ) > )

Exemplu: Se consideră gramatica:E -> E + E | E – E | E * E | E / E | E ^ E | ( E ) | id

Operatorii au următoarele proprietăţi:

^ cel mai prioritar, asociativ la stânga*,/ asociativi la stânga+.- cea mai mică prioritate, asociativi la stânga

Pe baza relaţiilor de precedenţă de mai sus, rezultă următoarea matrice de precedenţe:

+ - * / ^ id ( ) $+ > > < < < < < > >- > > < < < < < > >* > > > > < < < > >/ > > > > < < < > >^ > > > > < < < > >id > > > > > > >( < < < < < < < =) > > > > > > >$ < < < < < < <

-

77

Limbaje Formale Si are

Documents

Transcript of Limbaje Formale Si are