CAP. 3 ANALISI SINTATTICA • • • • 3.1 Il ruolo dell'analizzatore sintattico 3.2 Le grammatiche 3.3 L’analisi discendente 3.4 L’analisi ascendante Traduzione cap3 1 3.1 Il ruolo dell'analizzatore sintattico unità lessicale programma iniziale analizzatore lessicale analizzatore sintattico albero di analisi (sintattico) richiesta tabella dei simboli Ruolo centrale della parte frontale: attiva l'analizzatore lessicale con richieste verifica la correzzione sintattica costruisce l'albero di analisi prepara e anticipa la traduzione gestisce gli errori comuni di sintassi. Traduzione cap3 2 Tipi di analizzatori sintattici: • metodi universali (Cocke-Younger-Kasami), permettono un'analisi di qualsiasi grammatica algebrica, ma complessità in O(n3); • metodi lineari in O(n), su certe grammatiche: analisi discendente, più intuitiva, ben adatta a grammatiche simplici; analisi ascendente, più sofisticata, più utilizzata dai generatori automatici di analizzatori sintattici, poichè necessita poche adattazioni della grammatica. Trattamento degli errori: • diagnosi (messagi); • continuazione dell'analisi: "modo panico", fino a risincronizzazione; correzione (difficile se l’errore è avvenuta molto prima della detezione; regole di errori, integrate alla sintassi (grammatica). Traduzione cap3 3 3.2 Le grammatiche Sintassi specificata da regole grammaticali. • Simboli terminali (= unità lessicali) alfabeto A; • Simboli intermedi o variabili (= categorie grammaticali) alfabeto X; • Regole grammaticali x w , dove x X e w (AX)* w è una parole, anche vuota. Esempi : instr if expr then instr else instr frase soggetto verbo complemento • Assioma (= programma) Linguaggio generato = parole terminali derivate dall'assioma. Traduzione cap3 4 Esempio: Espressioni aritmetiche E number E(E) EE+E EE–E EE*E EE/E Albero d'analisi di 3*(6+2) E E * E ( E ) + E 3 number E 6 number 2 number I valori espliciti sono attributi delle unità lessicali. L’associazione alle unità lessicali è realizzata dall’analizzatore lessicale. Traduzione cap3 5 Grammatica precedente ambigua Grammatica non ambigua per espressioni aritmetiche (operatori suffissi): E EE + | EE – | EE * | EE / | number Grammatica non ambigua per expressioni aritmetiche: E E +T | E –T | T T T *F | T /F | F F ( E ) | number Scelta: associatività a sinistra precedenza di * e / su + et – Traduzione cap3 6 Analisi sintattica: Data una parola terminale, determinare se è, sì o no, generata dalla grammatica; in caso di sì, produrre un albero d'analisi. • Metodo universale: provare tutte le derivazioni partendo dall’assioma, fino a trovare la parola. Regole di lunghezza (dopo modificazioni) permettono di eliminare le derivazioni che non possono convenire. • Metodo discendente (descesa recursiva): una procedura per variabile, i terminali servono a scegliere la regola (previsione) e alla validazione. • Metodo ascendante: la parola è letta (spostamento) fino ad identificare regole, che vengono ridotte (riduzione). Traduzione cap3 7 3.3 L’analisi discendente Una procedura per variabile. Problema: ricorsività diretta a sinistra; necessità di una trasformazione per eliminarla. Grammatica iniziale E E +T | T T T *F | F F (E ) | number Grammatica modificata A E$ (produzione aumentata) E TG G +TG | T FU U *FU | F (E ) | number Procedure corrispondenti: supponiamo che due procedure sono già scritte: • prevision ritorna l’unità lessicale seguente senza rimuoverla; • match(x) legge l’unità lessicale seguente, la rimuove e segnala un errore se non vale x. Traduzione cap3 8 procedure expression ; begin writeln(‘E->TG’) ; term ; moreterm end ; procedure moreterm ; begin if prevision = plus then begin writeln(‘G->+TG’) ; match(plus) ; term ; moreterm end else writeln(‘G->epsilon’) end ; procedure expression ; begin writeln(‘E->TG’) ; term ; while prevision = plus do begin writeln(‘G->+TG’) ; match(plus) ; term end ; writeln(‘G->epsilon’) end ; Raggruppando e eliminando la ricorsività terminale Traduzione cap3 9 procedure term ; begin writeln(‘T->FU’); factor ; while prevision = mult do begin writeln(‘U->*FU’) ; match(mult) ; factor end ; writeln(‘U->epsilon’) end ; procedure factor ; begin if prevision = open then begin writeln(‘F->(E)’) ; match(open) ; expression ; match(close) end else if prevision = number then begin writeln(‘F->number’); match(number) end else writeln(‘error’) procedure analysis ; end ; begin writeln(‘A->E$’) ; expression ; match(dollar) ; writeln(‘success’) end ; Il fallimento dell’analisi è trattato da match(x). Traduzione cap3 10 Funzioni FIRST e NEXT x FIRST(x) NEXT(x) FIRST(x) = insieme dei terminali che possono cominciare una derivazione da x. NEXT(x) = insieme dei terminali che possono seguire x in una derivazione Traduzione cap3 11 Calcolo di FIRST: Un grafo è costruito fra tutti i simboli grammaticali. Freccia da x verso y ssi x y , e è annullabile. Qui, contiene solo variabili, senza restrizione (anche ). FIRST(x) = { a terminale | esiste un cammino da x fino a a } ; se x è annulabile, si aggiunge a FIRST(x). Esempio con la grammatica precedente: Annulabili: G e U Grafo: A E T F ( G number + U * FIRST(A) = FIRST(E) = FIRST(T) = FIRST(F) = { (, number } FIRST(G) = {+, } FIRST(U) = { *, } La funzione FIRST è estesa a tutte le parole: FIRST(xu) = FIRST(x) se x non è annullabile {}FIRST(x) \ } FIRST(u) se x è annullabile Traduzione cap3 12 Calcolo di NEXT: Un grafo è costruito fra tutti i simboli grammaticali. Freccia da x verso y sse • esiste z x , y è terminale e y FIRST() ; • esiste y x e è annullabile. Qui, e sono parole qualsiasi (anche ). NEXT(x) = { a terminale | esiste un cammino da x fino a a }. Esempio con la grammatica precedente: F * Grafo: NEXT non è definito per l'assioma della produzione aumentata (qui A). U T + G E $ ) NEXT(G) = NEXT(E) = { $, ) } NEXT(U) = NEXT(T) = { +, $, ) } NEXT(F) = { *, +, $, ) } Traduzione cap3 13 Con FIRST e NEXT si possono caratterizzare le grammatiche analizzabili in modo discendente, usando un solo simbolo di previsione a: a parte già analizzata simbolo di previsione parte ancora da analizzare Grammatiche LL(1). Sia a il simbolo di previsione e x la variabile da riscrivere. Utilizzare la regola x se a FIRST(); Se è annullabile, utilizzare la regola x se a NEXT(x). La grammatica è LL(1) quando, per ogni x, una sola regola soddisfa una delle condizioni sopraddette. Traduzione cap3 14 Tabella di analisi LL(1): n $ 1 2 3 3 4 4 6 5 6 6 7 8 + * E G T U F ( 1 ) 0 A E$ 1 E TG 2 G +TG 3G 4 T FU 5 U *FU 6U 7F(E) 8 F number I vuoti nella tabella corrispondono a errori sintattici. La tabella specifica i collegamenti nelle procedure del programma di analisi per discesa ricorsiva. Può anche essere usato come il dato di un programma universale di analisi discendente non ricorsiva. Traduzione cap3 15 3.4 L’analisi ascendante Si utilizza uno pila e un automa. Le transizioni di esso dipendono dal simbolo seguente: oppure • si mette uno stato sulla pila (push) e si rimuove il simbolo di previsione (spostamento); o • si rimuove dalla pila un numero di stati uguale alla lunghezza della regola riconosciuta (pop) e si mette sulla pila un nuovo stato (riduzione). pila parte analizzata parte non analizzata Traduzione cap3 16 Esempio: espressioni aritmetiche 0 A E$ FIRST: 1 E E +T A E T F 2ET 3 T T *F NEXT: 4TF 5 F (E ) F T E $ 6Fn + * ) ( n Calcolo degli stati: regole marcate (items); Lo stato iniziale contiene la produzione aumentata con il marchio in posizione iniziale; Se uno stato contiene l'item x u •yv, contiene anche tutti gli items y •w (chiusura di un item) ; Se uno stato contiene l'item x u •yv, c'è una transizione con il simbolo y sullo stato che contiene x uy •v. Traduzione cap3 17 stato 0 stato 1 A •E$ E •E +T E •T T •T *F T •F F •(E ) F •n E A E •$ E E • +T $ + stato 2 T ET• T T • *F F stato 3 * stato 4 Fn• n ( F (•E ) E •E +T E •T T •T *F T •F F •(E ) F •n E E + •T T •T *F T •F F •( E ) F •n T T * •F F •(E ) F •n ( stato 5 stato 6 stato 7 TF• n ACCETTATA E T F stato 8 F (E •) E E • +T T F ( n F ( n ) + stato 9 E E +T • T T • *F 3 4 5 * 7 stato 10 T T *F • 4 5 stato 11 F (E )• 6 2 3 Automa costruito dalla grammatica precedente Traduzione cap3 18 Fonzionamento del automa: All'inizio, la pila contiene lo stato 0. Si legge il simbolo seguente del testo da analizzare; l'ultimo stato sulla pila e questo simbolo indicano al automa il numero dello stato da mettere sulla pila (spostamento). Quando uno stato contiene un item di tipo x u •, si possono rimuovere dalla pila gli ultimi |u| stati; si legge il nuovo stato sulla pila; questo, con x, indica al automa un nuovo stato, che si sostituisce sulla pila a quelli rimossi (riduzione). In certi casi, più di una possibilità esiste: si dice che c'è un conflitto spostamento-riduzione o riduzione–riduzione; Il caso più generale è quando lo stesso stato contiene x u •, y v •, z r •st, dove s è un simbolo terminale. Il conflitto può essere tolto se NEXT(x), NEXT(y) e {s} sono disgiunti. Se è il caso, si dice che la grammatica è SLR(1). Traduzione cap3 19 La sequenza delle reduzioni costituisce una derivazione della parola da analizzare, a partire dalla fine, dalla destra verso la sinistra. Esempio: L'unico conflitto si trova nello stato 9. È tolto dal esame di NEXT(E). 0 1 2 3 4 5 6 7 8 9 10 11 n d5 d5 d5 d5 + * d6 r2 r4 d7 r4 r6 r6 d6 r1 r3 r5 d7 r3 r5 ( d4 d4 d4 d4 ) $ r2 r4 A r2 r4 r6 r6 d11 r1 r3 r5 r1 r3 r5 E d1 T d2 F d3 d8 d2 d3 d9 d3 d10 Tabella di analisi SLR(1) delle espressioni aritmetiche Traduzione cap3 20 Esempio: (3 + 2) * 4 $ pila 0 04 045 043 042 048 0486 04865 04863 04869 048 0 4 8 11 03 02 parte non analizzata (3 + 2) * 4 $ 3 + 2) * 4 $ + 2) * 4 $ + 2) * 4 $ + 2) * 4 $ + 2) * 4 $ 2) * 4 $ )*4$ )*4$ )*4$ )*4$ *4$ *4$ *4$ regola Fn TF ET pila 027 0275 0 2 7 10 02 01 parte non analizzata 4$ $ $ $ $ regola Fn T T *F ET ACCET. Derivazione ottenuta: Fn TF E E +T F (E ) TF E T T *F T * 4 F * 4 (E) * 4 (E + T) * 4 (E + F) * 4 (E + 2) * 4 (T + 2) * 4 (F + 2) * 4 (3 + 2) * 4 Traduzione cap3 21 Certe volte, i conflitti non possono essere tolti dall'esame degli insiemi NEXT. Si può allora tenere conto dei caratteri che possono seguire una variabile durante la costruzione. Se l’automa costruito così non ha più conflitti, si dice che la grammatica è LR(1). Maggiore problema: il numero degli stati può diventare troppo grande. Compromesso: sull'automa simplice costruito precedentemente, si può definire dinamicamente l'insieme dei caratteri che possono seguire una variabile. Nei casi di reduzioni, questi insiemi si sostituiscono agli insiemi NEXT del caso SLR(1). Se allora i conflitti sono tolti, si dice che la grammatica è LALR(1). Questo metodo è usato da YACC. LR(1) LALR(1) SLR(1) Traduzione cap3 22 Regola di propagazione della previsione: item x u •yv (z) da per chiusura y •w (FIRST(vz)) per transizione x uy •v (z) Si costruisce il grafo di dipendenza degli items. I caratteri di previsione ammissibili sono calcolati seguendo quel grafo. stato 0 A •E$ E •E +T E •T T •T *F T •F F •(E ) F •n ( ) ($, +) ($, +) ($, +, *) ($, +, *) ($, +, *) ($, +, *) T stato 2 ET• ($, +) T T • *F ($, +, *) conflitto tolto Per questa grammatica, stesso risultato con LALR(1) o con SLR(1). Traduzione cap3 23 Uso dell'ambiguità: 0 A E$ 1 E E +E 2 E E *E 3 E (E ) 4En Grammatica ambigua per espressioni aritmetiche NEXT(E ) = {$, +, *, )} L'ambiguità impedisce un'analisi sia discendente che ascendente. Le tecniche precedenti non possono togliere i conflitti. Traduzione cap3 24 stato 0 stato 1 E A •E$ E •E +E E •E *E E •(E ) ( E •n n ( stato 9 En• n A E •$ E E •+E E E •*E stato 2 E (•E ) E •E +E E •E *E E •(E ) E •n $ stato 3 + E E + •E E •E +E E •E *E E •(E ) E •n * stato 4 E E * •E E •E +E E •E *E E •(E ) E •n E stato 5 E (E •) E E •+E E E •*E stato 6 ACCETTATA E E +E • E E •+E E E •*E E ( n + * 3 4 2 9 stato 7 E E *E • E E •+E E E •*E E ( n + * 3 4 2 9 stato 8 E (E ) • ) + * 3 4 Traduzione cap3 25 stato 6 E E +E • E E •+E E E •*E Conflitti spostamento-riduzione Con $, ), niente conflitto, si riduce Con +, si riduce poichè + associativo a sinistra Con *, si sposta poichè * ha precedenza su + stato 7 E E *E • E E •+E E E •*E Con $, ), niente conflitto, si riduce Con +, si riduce poichè * ha precedenza su + Con *, si riduce poichè * associativo a sinistra Regole di precedenza per togliere i conflitti spostamento-riduzione Se conflitto tra x u op1y • e x u •op2y 1) op1 ha precedenza su op2, si riduce; 2) op2 ha precedenza su op1, si sposta; 3) op1 e op2 hanno stessa precedenza: 3.1) associatività a sinistra, si riduce; 3.2) associatività a destra, si sposta; 3.3) niente associatività, segnalare un errore. Traduzione cap3 26 Gestione degli errori: Grammatica ambigua precedente Esempi di correzione possibile. Correzioni in corsivo 0 1 2 3 4 5 6 7 8 9 n d9 3 d9 d9 d9 3 r1 r2 r3 r4 + 1 d3 1 1 1 d3 r1 r2 r3 r4 * 1 d4 1 1 1 d4 d4 r2 r3 r4 ( d2 3 d2 d2 d2 3 r1 r2 r3 r4 ) 2 2 2 2 2 d8 r1 r2 r3 r4 $ 1 A 1 1 1 4 r1 r2 r3 r4 E d1 d5 d6 d7 Azioni correttrici: 1 Inserire un n fittivo (e dunque porre 9 sulla pila) e segnalare "missing number" 2 Togliere ) dal testo e segnalare "extra closing parenthesis" 3 Inserire un + fittivo (e dunque porre 3 sulla pila) e segnalare "missing operator" 4 Inserire un ) fittivo (e dunque porre 8 sulla pila) e segnalare "missing closing parenthesis". Traduzione cap3 27