Durante la nostra attività di programmatori quante volte ci siamo posti la domanda: come si fa un compilatore? Certamente, in modo intuitivo, sappiamo agevolmente comprendere il risultato finale ed i meccanismi che il compilatore va ad implementare. Nonostante questa approfondita conoscenza dei comportamenti sappiamo bene che realizzane un compilatore è un lavoro estremamente complesso. Un compilatore è composto in linea di massima di cinque componenti: analizzatore lessicale, parser, il generatore di pseudo codice, ottimizzatore, generatore di codice. Nell'articolo qui presentato analizzeremo come lavora un parser realizzato mediante Bison(che è un generatore di parser, cioè "genera" il codice che realizza il parser).
I parser verificano la validità di un flusso dati o per dirla in altri termini, verificano che una struttura dati rispetta una grammatica. Questi strumenti sono importantissimi nella programmazione in genere, non solo quanto bisogna realizzare dei compilatori. Nel presente articolo cercheremo di capire come se ne può realizzarne uno mediante Bison. Andremo ad analizzare come questi realizza l'attività di parsing in dettaglio.
Si prega di comunicarci eventuali errori di traduzione/punti non chiari rilevati nel presente articolo. Grazie.
Indice dei contenuti
Introduzione
Prerequisiti
Il Parser LR
Un esempio di grammatica
Le tabelle nello stile Dragon Book
- La grammatica Aumentata di Bison
- Riduzioni di Default
- Tabelle Tradizionali Modificate
- Simboli numerici
Compressione della tabella di parsing
Descrizione tabelle
Altre tabelle di supporto
Riepilogo tabelle
La Routine di Parsing Generata da Bison - yyparse ()
Un Esempio di Parsing
Storia del documento/story of the document
Riferimenti
Copia di questo documento
Licenza GNU
Introduzione
Bison è un generatore di parser che converte una grammatica di tipo context-free in un parser di tipo LALR(1) o GLR in codice C o C ++. Tra le funzioni generate abbiamo la funzione di parsing che può essere chiamata esternamente dall'applicazione.
Come viene realizzato un parser mediante bison può essere utile per capire quali sono le differenze rispetto ai parser che vengono descritti nei molti testi specifici. Conoscere il codice di parsing ottenuto inoltre, ci consente di poterlo modificare al fine di ottimizzarne la performace: in alcuni casi ad esempio può essere più conveniente avere diverse funzioni di parsing (yyparse, più piccole) piuttusto che una che le comprenda tutte.
In questo documento tenteremo di descrivere l'implementazione di un parser LALR(1) in linguaggio C come generato da Bison 2.3. Per comprendere in dettaglio il funzionamento e le tabelle di parsing utilizzeremo una grammatica piuttosto semplice. Si potrà inoltre confrontare le tabelle di parsing ottenure con quelle che si trovano nel libro "Compilatori - Principi, tecniche e strumenti" di Aho, Sethi e Ullman, conosciuto anche come il "Dragon Book".
Prerequisiti
Si parte dal presupposto che il lettore abbia familiarità con le grammatiche context-free e tecniche di parsing LR e che abbia un minimo di esperienza con il parser Bison. È inoltre necessario avere familiarità con la teoria e la terminologia usuale come: shift (spostamento), reduction (riduzioni), stack di parsing e gestione degli errori. Se non si ha familiarità con Bison, si raccomanda vivamente di leggere il manuale d'uso di Bison prima di proseguire con la lettura di questo documento.
Il parser LR
Un parser LR è essenzialmente un algoritmo shift/reduction (bottom up) guidato da tabelle di parsing ed uno stack. Per una panoramica dell'algoritmo di parsing LR, è possibile fare riferimento al Dragon Book oppure a questa eccellente voce di Wikipedia .
L'algoritmo di analisi è lo stesso (almeno in teoria) per tutti i parser LR. Tra loro differiscono solo per le tabelle prodotte dal generatore di parser. Nel nostro caso, Bison genera tabelle di parsing LALR(1) in codice di C/C++. La funzione di parsing generata (yyparse), per svolgere il proprio compito, implementa una routine di analisi che fa riferimento a queste tabelle ed uno stack.
Un esempio di grammatica
Adotteremo la seguente grammatica come esempio per mostrare i meccanismi interni al parser generato da Bison. La stessa grammatica sarà anche utilizzata per la creazione delle tabelle e cercheremo di evidenziare quale relazione esiste tra le tabelle teoriche e quelle ottenute mediante Bison.
(1) L → L;E
(2) L → E
(3) E → E,P
(4) E → P
(5) P → a
(6) P → (M)
(7) M → ε
(8) M → L
La grammatica equivalente per Bison è la seguente:
%%
L : L ';' E
| E
;
E : E ',' P
| P
;
P : 'a'
| (M)
;
M : /* nothing */
| L
;
%%
Le tabelle nello stile Dragon Book
Lo schema di parsing in formato tabellare (non compresso), lo troviamo sia del Dragon Book che in altri testi specifici sulla teoria dei compilatori, questo schema, è estremamente utile alla comprensione teorica del funzionamento di un parser LR. Esaminiamo lo schema relativo alla grammatica della sezione precedente.
L'azione(action) ed il salto(goto) della tabella sono riportati di seguito allo stato, la tabella seguente LALR(1) è stata realizzata manualmente:
| action | goto | ||||||||||
| state | ; | , | a | ( | ) | $ | L | E | P | M | |
| 0 | s12 | s6 | 1 | 8 | 9 | ||||||
| 1 | s2 | acc | |||||||||
| 2 | s12 | s6 | 3 | 9 | |||||||
| 3 | r1 | s4 | r1 | r1 | |||||||
| 4 | s12 | s6 | 5 | ||||||||
| 5 | r3 | r3 | r3 | r3 | |||||||
| 6 | s12 | s6 | r7 | 7 | 8 | 9 | 10 | ||||
| 7 | s2 | r8 | |||||||||
| 8 | r2 | s4 | r2 | r2 | |||||||
| 9 | r4 | r4 | r4 | r4 | |||||||
| 10 | s11 | ||||||||||
| 11 | r6 | r6 | r6 | ||||||||
| 12 | r5 | r5 | r5 | r5 | |||||||
L'automa ottenuto consiste quindi di 13 stati. Una stringa appartiene a questa grammatica se al termine del parsing l'automa viene atrovarsi nello stato 1. Il funzionamento di un algoritmo di parsing LR basato su questo tipo di tabella è abbastanza semplice ed è spiegato con chiarezza nella voce di wikipedia segnalata nonché nei libri concernenti la teoria dei compilatori.
Possiamo vedere che la maggior parte delle caselle della tabella sono vuote oppure risultano in esse delle voci già presenti in altre righe. Le caselle vuote nella parte relativa all'azione (action) sono errori;
La parte relativa ai salti (goto) contiene solo 4 voci valide, le celle vuote, a differenza del caso precedente non risultano essere degli errori, sono semplicemente posizioni non raggiungibili; è impossibile rilevare un errore su un simbolo non terminale a causa della correttezza dell'algoritmo LR.
Una grammatica di questo genere se venisse impiegata in comuni compilatori finirebbe con l'avere una enorme quantità di stati le cui caselle sarebbero in gran parte vuote. Esistono numerosi metodi per ottimizzare un generatore di parser. Lo stesso Dragon Book suggerisce qualche metodologia per la compressione di tabelle di parsing. Bison, come vedremo, ha un approccio diverso per risolvere questo problema.
Le tabelle generate da Bison
Bison, invece di generare una matrice come quella indicata, genera più tabelle mono-dimensionali. Non tutte queste tabelle sono utilizzate direttamente nella routine di analisi - alcune vengono utilizzate per stampare informazioni di debug altre per la gestione degli errori. Prima di addentrarci nella spiegazione di ciascuna tabella, è necessario approfondire alcuni aspetti che Bison implementa e che in qualche modo differiscono dalle metodologie teoriche classiche.
La grammatica Aumentata di Bison
Bison aumenta la grammatica iniziale con la seguente regola:
$accept : $end
$accept e $end sono simboli fittizi. Questo metodo è in qualche modo simile ai metodi descritti nei molti testi specifici su questo argomento. Rispetto ai metodi classici, oltre al simbolo $accept, Bison inserisce il simbolo $end utile a generare lo stato finale del parser. Questo stato finale generalmente ha una produzione singola:
$accept : $end .
si noti il punto come ultimo carattere di fine regola. Questo consente alla routine di parsing a riconoscere quando accettare la stringa di input solamente osservando la situazione attuale e rende non necessario il dover rappresentare "$accept" come una voce nelle tabelle LALR. Non vi è alcun concetto di "stato finale" nel parsing LALR teorico (nonostante questa sia una caratteristica invece nelle FSM relative ai parser LR (0)), ma Bison utilizza uno Stato come lo stato finale, introducendo il simbolo di fine $.
Una conseguenza importante di questo aumento è che la "numerazione Regola" cambia per le tabelle generate da Bison. La regola $accept viene numerata regola#1, quindi nelle tabelle prodotte da Bison, la nostra regola r6 assumerà il valore R7 e così via.
Riduzioni di Default
Negli stati dove è presente una riduzione, l’azione per molti simboli sarà la stessa. Si consideri ad esempio gli stati 5-8-9-11 della tabella sopra indicata: si può notare che ripetono la stessa azione di riduzione per molti dei simboli terminali. Notiamo quindi che si può evitare di sprecare spazio di memoria creando un’azione di default per i simboli terminali. Per esempio lo stato 5 può avere come azione di default la r3. Il parser generato da Bison eseguirà una riduzione utilizzando la regola #3 se lo stato dell’automa si troverà nello stato 5 a prescindere da quale simbolo si troverà ad analizzare nella tabella di look-ahead! Possiamo facilmente comprendere questo comportamento applicato in ogni stato potrebbe far compiere delle azioni non corrette. Come vedremo questo non ci deve far preoccupare in quanto prima di procedere con l'azione verrà eseguita un ulteriore verifica.
Tabelle Tradizionali Modificate
Applicando le modifiche esposte, la nostra tabella, secondo lo stile Dragon Book, cambierà notevolmente. Nella nuova tabella abbiamo ora 14 stati a causa del simbolo terminale di $fine. Inoltre non vi è più alcuna voce "accept" nella tabella. Stato 8 viene quindi considerato come lo stato di accept.
La prima tabella che viene mostrata qui sotto, viene ottenuta eseguendo Bison attivando l’opzione oppurtuna (--report=all). Tale tabella in ogni caso non verrà utilizzata da Bison, viene solo ad essere utile per fini documentativi.
| Table realizzata partendo dal report di Bison | Tabella calcolata manualmente - riordinata | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
La tabella realizzata mediante il file di report Bison vediamo che trova corrispondenze con la tabella da noi calcolata. Lo stato 1 generato da Bison corrisponde con lo stato 12 con quella manuale e così via. Ovviamente non troviamo corrispondenze con lo stato 8 in quanto nella grammatica iniziale noi non avevamo il simbolo di fine($end).
Simboli numerici
Bison assegna un identificativo numerico ad ogni simbolo della grammatica (sia terminale che non terminale). Ovviamente Bison ha una sua tabella simboli come qualunque altro compilatore. Come regola generale, Bison assegna sempre prima gli identificativi dei simboli terminali per poi procedere con i non-terminali. Cioè: i simboli non terminali hanno sempre un valore numerico maggiore dei terminali. Inoltre Bison crea 4 nuovi simboli:
$accept : il nuovo simbolo di start(non-terminal)della grammatica;
$end : a cui viene riservato il numero 0 (un simbolo fittizio);
error : il simbolo di errore a cui viene riservato il numero 1;
$undefined : a cui viene riservato il numero 2, identifica un simbolo che sta ad indicare che è stato trovato un token che non può essere riconosciuto (viene dato in input un simbolo non facente parte della grammatica, non definto usando la parola chiave %token).
I valori numerici per i terminali cominciano dal 3 in poi. È possibile controllare gli identificativi numerici assegnato ai vari simboli guardando la matrice yytname generata in output da parser. Per la nostra grammatica di esempio, l’associazione appare quindi:
| Symbol | Number |
| $end | 0 |
| error | 1 |
| $undefined | 2 |
| ';' | 3 |
| ',' | 4 |
| 'a' | 5 |
| '(' | 6 |
| ')' | 7 |
| $accept | 8 |
| L | 9 |
| E | 10 |
| P | 11 |
| M | 12 |
Abbiamo quindi da 0 a 7 i valori relativi ai terminali dal 9 in poi i successivi (non terminali). Tra breve vedremo come questi simboli verranno utilizzati per indicizzare ulteriori tabelle create da Bison.
Compressione della tabella di parsing
Vediamo come possiamo rappresentare in maniera ottimale la nostra 'tabella tradizionale modificata'. Iniziamo a considerare un fatto: la tabella iniziale contiene ancora molti spazi vuoti e caselle ripetute, possiamo pensare di unire le azioni comuni in un unico punto. Le riduzioni ripetute saranno il nostro primo target. Tutte le riduzioni possono quindi essere elencate in un array indicizzato in base allo stato:
default_reductions[] = {none,r5,r7,none,r2,r4,r8,none,none,none,none,r6,r1,r3}
In questo vettore viene sprecato un po’ di spazio (i valori 'none') tuttavia, tale spazio, è comunque di gran lunga inferiore a quello che veniva sprecato in precedenza per elencare tutte le azioni di riduzione in quanto ripetuto per ogni riga. Alcuni stati contemplano solo un azione di riduzione e niente altro. Si osservi che abbiamo elencato la riduzione di default per lo stato 2 (R7) pur avendo le azioni di shift su un paio di simboli. Quindi, questa matrice può essere utilizzato solo dopo essersi assicurati che non vi siano azioni di shift per lo stato attuale del corrente simbolo di look-ahead.
Il prossimo obiettivo di riduzione non può che essere relativo alla parte dei goto che molto spesso contiene delle caselle vuote. Poiché la maggior parte degli Stati non possiede un’istruzione di salto (goto), la migliore ottimizzazione di spazio si ha mediante un array indicizzato da ogni simbolo non terminale (sulla colonna) anzichè basandosi sullo (quindi sulla riga). Del resto ogni simbolo non terminale può avere un diverso salto (goto) a seconda dello stato attuale dell'automa. Così, abbiamo scelto di elencare i salti (goto) più comuni di ogni simbolo non-terminale in un array di questo tipo:
default_gotos[] = { 3, 4, 5, 7 }
Abbiamo quindi un valore di default per ogni simbolo non-terminale. Rimangono dunque da considerare le alternative istruzioni di salto(goto) differenti da quelli di default per i simboli non terminali L, E e P che sono presenti in alcuni stati. Prima di procedere oltre possiamo comunque col dire che la tabella creata ci ha consentito di risparmiare una notevole quantità di spazio di memoria dovuto agli spazi nulli relativi alle istruzioni di salto.
Rimane dunque da risolvere il problema di rappresentare in forma compatta alcuni shift ed alcuni salti(goto) sopra menzionati. Nelle tabelle che seguono riassumiamo in forma compatta le azioni ed i salti eliminando le riduzioni di default e gli stati che contengono solo riduzioni di default. Inoltre nella tabella dei salti abbiamo sostituito ai simboli il relativo simbolo numerico. Abbiamo quindi:
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Per comprimere questa parte delle tabelle Bison si segue un algoritmo descritto da Tarjan e Yao [3]. Si tratta di un algoritmo applicato ad una struttura dati TRIE combinata ad "un doppio spostamento" in cui vengono applicati i metodi ideati degli autori per migliorare i tempi di ricerca.
Il doppio spostamento consiste di un idea estremamente semplice. La prima azione da compiere consiste nel riscrivere le informazioni tabellari in formato vettoriale eliminando gli spazi vuoti. Manteniamo l'ordine degli elementi di ogni riga intatta e spostiamo ogni riga da una certa quantità di posizioni tale che non ci siano due voci, non nulle presenti in ogni, riga tali che queste occupino la stessa posizione nella matrice unidimensionale. La nostra mappatura sarà definita da una serie di spostamenti D (i) per ogni riga i e la posizione (i, j), nella tabella qui sopra, si associa alla posizione D (i) + j nel nostro array monodimensionale. Si consideri ad esempio la tabella spostamento e la corrispondente di una tabella dimensionale:
D = { 4, 6, 0, 0, 12, 9, 8, 0, 13} e
T = { 9, 10, 1, 2, 11, 8, 1, 2, 1, 2, 1, 2, 9, 11, 10}La tabella spostamento D ha il compito di definire l’offset da cui partire nella tabella T(che contiene gli elementi veri e propri) in un dato stato; L’indice in T per l’elemento (i,j) è calcolato mediante la formula: D[i] + j. Per esempio, per trovare il dato nella posizione (3,1) (cioè consideriamo l’azione sul simbolo 4 nello stato 4) nella tabella 2-D sopra indicata, dobbiamo calcolare D[3] + 1 = 0+1 = 1 e quindi T[1] = 10 è il dato desiderato.
Anche nella tabella del nostro esempio abbiamo molte voci ricorrenti presenti negli stessi stati(es. stati 1 e 2). Abbiamo quindi combinato le nostre colonne di simboli con la struttura TRIE al fine di aumentare il fattore di compressione della nostra tabella originale (se questi argomenti hanno suscitato in voi un interesse particolare chi interessato può approfondire con qualche testo specifico[3] per maggiori dettagli).
Proseguiamo il nostro ragionamento ponendo l’attenzione sul fatto che Bison ha come target la costruzione di un vettore in cui deve essere specificato che cosa si deve fare in ogni stato. Tale tabella verrà indicizzata mediante un vettore directory che denomineremo D. Nella precedente analisi, gli spostamenti in T, venivano indicizzati mediante un array 2-d (i,j). Nel caso di T invece noi si vuole indircizzamento mediante il numero di stato e l'identificativo del simbolo (in quanto le righe e le colonne della tabella 2D sono state intestate mediante stati e simboli rispettivamente). Bison indicizza D mediante l'identificativo (numerico) dello stato e lo spostamento in T attraverso l'identificativo del simbolo. Se il prossimo simbolo da parserizzare (il look-ahead symbol) è costituito dal numero k la voce della tabella, per lo stato corrente, viene ottenuta nel seguente modo:
Azione per lo stato n sul simbolo y = T[ D[n] + k ]
Consideriamo ad esempio l’azione per lo stato 0 (s1) sul simbolo numero 5(‘a’). Quindi se T[0] = 1 allora D[0] = -5; pertanto, per avere l’azione s2 sul simbolo numero 6, dovremmo avere T[ D[0] +6 ] = T[1] = 2 e così via.
A questa procedura c’è tuttavia un caso speciale di cui dobbiamo avere cura. Esistono alcuni errori ‘espliciti’ nell’azione delle tabelle che non devono essere sovrascritti dalle riduzioni di default. Tali errori sono dovuti alle dichiarazioni %nonassoc presenti nella grammatica. In tal caso avremmo delle riduzioni nelle azioni “non considerare” mediante il vettore default_reductions[]. Per rappresentare queste particolari riduzioni nella stesse tabella T, Bison genera un numero di regola negativo in T. Il segno negativo serve a differenziare le riduzioni(negative) dalle azioni(positive). Gli errori invece vengono esplicitati da un valore negativo che rappresenta l’out of range dei numeri regola e definita in modo esplicito mediante una macro (si veda YYTABLE_NINF più avanti). Nella nostra grammatica di esempio, non abbiamo questo caso.
Si noti che Bison anche in D assegna un valore negativo con uno speciale significato che sta ad indica che si deve applicare la riduzione di default(si veda lo stato 1 del nostro esempio).
Similmente immaginiamo di creare una tabella che potremmo denominare ND per indicare i simboli non-terminali che non seguono un goto di default contenente una voce di riferimento per ogni simbolo non-terminale in cui ciascuna voce nella tabella rappresenta uno spostamento nella tabella T le cui voci verranno indicizzate dalla stato (numerico). Se ND[‘P’] = 2 e lo stato corrente è 10, ci riferiremo a T[12] per acquisire l’informazione di goto nello stato 10 con il simbolo ‘P’.
Rimane da chiarire il metodo per discriminare quando è necessario prelevare l'istruzione di salto dalla tabella di default oppure dalla tabella T. Una possibile strategia può essere quella di rendere ND[S] con un valore al di fuori delle dimensioni della tabella e quindi forzare il parser ad andare a prelevare il dato sui goto di default.
Bison, tra le tabelle che genera, ha anche una tabella di guardia che serve a verificare se i salti ottenuti risultano nei limiti consentiti oppure no. Le tabelle che seguono dovrebbero chiarire ulteriormente i concetti fin qui espressi.
Descrizione tabelle
Bison, come si è visto nelle sezioni precedenti, genera le tabelle di parsing in un formato vettoriale. Tutti i nomi delle variabili create del parser iniziano con 'aa' per evitare conflitti di denominazione con i programmi utente. Quello che segue è una breve descrizione di ogni tabella con alcuni esempi relativi alla grammatica campione.
yytranslate
Questa tabella mappa i token di input in symboli numerici. Se si hanno dichiarazioni %token nella grammatica, Bison assegna un token number per ciascuno di essi; Se semplicemente utilizzate una rappresentazione a caratteri (come fatto nel nostro caso), Bison mappa la tabella ASCII in simboli numerici. Pertanto, nel nostro caso, yytranslate[97] = 5 che è una 'a' (si veda la tabella sopra). La tabella completa la troviamo qui sotto.
/* YYTRANSLATE[YYLEX] -- Bison symbol number corresponding to YYLEX. */
static const yytype_uint8 yytranslate[] =
{
0, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
6, 7, 2, 2, 4, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 3,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 5, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 1, 2
};
Notiamo come la maggior parte delle voci consistano del simbolo # 2, cioè $indefinito. Solo ai simboli effettivamente presenti nella nostra grammatica è stato assegnato un numero di simbolo valido. Ogni volta che yyparse () richiede un token, viene chiamato yylex e quindi viene tradotto e restituito il token di input nel corrispettivo symbol number tramite questa tabella.
yydefact
Questa tabella contiene le riduzioni di deafult da appllicare in ogni stato. yydefact[state] = numero regola di default da usare nel presente stato. Qui abbiamo la tabella defact realizzata per la nostra grammatica di esempio:
/* YYDEFACT[STATE-NAME] -- Default rule to reduce with in state
STATE-NUM when YYTABLE doesn't specify something else to do. Zero
means the default is an error. */
static const yytype_uint8 yydefact[] =
{
0, 6, 8, 0, 3, 5, 9, 0, 1, 0,
0, 7, 2, 4
};
Nei commenti si può notare che viene menzionata la yytable(tra breve approfondiremo anche questa tabella). Si noti come la regola con numero 0 in questo vettore significa error. La regola 0 non è usata internamente da Bison a causa di alcune limitazioni relative alla rappresentazione della grammatica di ingresso
Se si da uno sguardo al modo con cui viene scritta la tabella modificata secondo lo style dragon book, si può facilmente comprendere a che cosa ci dice yydefact. Un importante osservazione è la seguente - le regole hanno un identificativo incrementato di 1 a causa della grammatica aumentata dalla regola: ‘$accept → L $end’. Quindi, la riduzione r5 nello stato 1 della tabella iniziale e diventato r6 in yydefact.
yydefgoto
Questa è la tabella compressa relativa ai salto(goto) della tabella tradizionale. Il numero di voci presenti è identico al numero di simboli non terminali presenti nella grammatica. Ogni voce indica qual’è il nuovo stato in cui si deve entrare in funzione di un nuovo simbolo non terminale. Quindi nel nostro caso abbiamo:
static const yytype_int8 yydefgoto [] = { -1, 3, 4, 5, 7 };
yydefgoto[n-esimo simbolo non-terminale] = il goto più comune a fronte dell’n-esimo simbolo non terminale. Si noti che n inizia da zero. L’indice in questo array viene ottenuto sottraendo al numero del simbolo non-terminale il numero di simboli terminali presenti nella grammatica. Per esempio, il numero simbolo per ‘E’ vale 10 ed il numero di simbolo treminale vale 8, quindi:
Così yydefgoto [E] = yydefgoto [10-8] = Stato 4.
yydefgoto viene consultato ogniquqlvolta il parser riduce il contenuto della stack usando una regola. Successivamente vedremo che yydefgoto viene consultata solo dopo aver compiuto un’analisi di un’altra tabella di salto e che, come vedremo, sarà chiarito come si possa gestire il salto nello stato 6 dallo stato 2 con il simbolo ‘L’ invece di procedere con il salto nello stato 3 come invece specificato da questa tabella.
Come nota finale osserviamo che la voce per il non-terminale 0 ($accept) valga -1. Lo stack non verrà mai ridotto con la regola $accecpt.
yyr1 e yyr2
yyr1 specifica l'identificativo numerico relativo alla parte sinistra di ogni regola (LHS, left hand side). Si ricordi che 0 non viene mai usato come numero di regola, quindi questa tabella ha NREGOLE + 1 voci, dove NREGOLE è il numero di regole presenti nella grammatica (che nel nostro caso in esempio vale 9). Qui abbiamo la lista di esempio:
/ * YYR1 [YYN] - l'identificativo numerico del simbolo relativo alla regola YYN. * /
static const yytype_uint8 yyr1 [] = { 0, 8, 9, 9, 10, 10, 11, 11, 12, 12 };
Dunque abbiamo che la regola #1 ha $accept come parte sinistra, pertanto yyr1[1] = 8 (si veda la tabella dei simboli data in precedenza) e così via. Quando avviene una riduzione, è necessario sapere qual’è il simbolo LHS della regola usata per ridurre ad una transizione allo stato appropriato. Diciamo cioè che è in questo abito che viene ad essere utilizzata la presente tabella.
yyr2 specifica la lunghezza (cioè il numero di simboli) di cui è composta la parte destra della regola. Qui abbiamo nuovamente il nostro esempio creato da Bison:
/ * YYR2 [YYN] - Numero di simboli che compongono lato destro della regola YYN. * /
static const yytype_uint8 yyr2 [] = {0, 2, 3, 1, 3, 1, 1, 3, 0, 1};
La Regola #2 (L → L;E) ha tre simboli nella parte destra(RHS), e quindi yyr2[2] = 3. Questa tabella viene anche utilizzata durante la fase di riduzione. Il numero degli stati che devono essere spuntati dallo stack equivale al numero di simboli della parte destra di ogni regola di riduzione.
yytable
Questa tabella è un contenitore al cui interno possiamo trovare numeri di stato e numeri di regola inseriti in un ordine pre-calcolato. Questa sarebbe la tabella T di cui si è parlato in precedenza. yytable serve ad indicare al parser sia lo stato successivo che deve essere inserito nello stack sia la regola da usare per la riduzione. yytable viene utilizzata in modo congiunto alle tabelle yycheck, yypact and yypgoto (si veda più avanti). Qui di seguito abbiamo elencato yytable nel caso in esempio. Le voci non avranno alcun senso fino a quando non si darà spiegazione di yypact and yypgoto.
/* YYTABLE[YYPACT[STATE-NUM]]. What to do in state STATE-NUM. If
positive, shift that token. If negative, reduce the rule which
number is the opposite. If zero, do what YYDEFACT says.
If YYTABLE_NINF, syntax error. */
#define YYTABLE_NINF -1
static const yytype_uint8 yytable[] =
{
8, 1, 2, 9, 11, 10, 9, 6, 12, 0,
0, 0, 13
};
Una cosa importante da notare è la definizione di YYTABLE_NINF - il valore di "infinito negativo" per la tabella yytable tale valore rappresenta il valore negativo più elevato possibile per la tabella (nel nostro caso è -1 in quanto non esistono valori negativi in yytable). Tale valore è utile al fine di capire particolari situazioni di errore.
yypgoto
Questa tabella concerne le voci di goto GOTO per i simboli non-terminali che fanno avvenire una transizione dell’automa in modo tale da portarlo in un altro stato basandosi sullo stato attuale. Per esempio, il simbolo ‘L’ può portare nello stato 3 se si è nello stato 0, ma se tale simbolo venisse ad essere inputato nello stato 2 lo stato successivo sarebbe il 6. Similmente per il simbolo ‘E’ e ‘P’ ci sono differenti goto in base allo stato attuale. I goto più comuni sono già stati definiti in YYDEFGOTO. Il compito di YYPGOTO è quello di indicare le gestire i casi alternativi. Diami uno sgaurdo alla tabella relativa al nostro esempio:
/* YYPGOTO[NTERM-NUM]. */
static const yytype_int8 yypgoto[] =
{
-5, 5, -1, 2, -5
};
Questa è la nostra tabella ND di cui si è accennato nella sezione relativa alla compressione delle tabelle. Viene ad essere indicizzata dai simboli non-terminali: ogni voce (eccetto $accept) L, E, P, M.
Diciamo che lo stato corrente sulla cima dello stack dopo la riduzione con la Regola #5 (P → a) sia 10 (vedere l’esempio in appendice). Ora, la transizione dovuta al goto per lo stato 10 con il simbolo P è lo stato 13 (secondo la tabella tradizionale), che non è la voce presente in yydefgoto per il simbolo P.
Il parser somma yypgoto[P] allo stato corrente. Nel nostro esempio yypgoto[3] sommato allo stato corrente (stato 10) dà come risultato 12 (in quanto yypgoto[3]=2). Quindi abbiamo che yytable[12] vale 13, che è il nuovo stato che deve essere immesso nello stack.
Ma come fa il parser a comprendere che deve prelevare lo stato da yytable (via yypgoto) e non da yydefgoto? Questo compito viene ad essere svolto da yycheck, una tabella di guardia, che da istruzioni in tal senso. Solamente dopo aver effettuato oppurtuni controlli viene effettuato l’indirizzamento. Descriveremo in dettaglio tale questione nella sezione concernente la routine di parsing yyparse().
yypact
La presente tabella specifica la porzione di yytable che descrive cosa fare nello stato S. Essa viene indicizzata dal simbolo(numerico) relativo alla token symbols. Questa tabella equivale alla tabella di directory D già descritta in precedenza(compressing parsing tables).
#define YYPACT_NINF -5
static const yytype_int8 yypact[] =
{
-4, -5, -4, 0, 1, -5, 3, -3, -5, -4,
-4, -5, 1, -5
};
Questa è la prima tabella ad essere consultata dal loop di parsing. Se yypact[cur-state] = YYPACT_NINF, si è nella condizione di dover applicare una riduzione di default (quindi mediante yydefact). Ciò significa che lo stato ha solo riduzioni come nello stato1(r5); altrimenti la voce in yypact[cur-state] viene sommata al symbol number del corrente look-ahead token ed il risultato usato come indice in yytable per ottenere la prossima azione da compiere (si vedano i commenti relatici al codice di yytable dell’esempio).
Ecco un esempio: supponiamo di trovarci nello stato 0 ed il look-ahead token sia 'a'(symbol number 5). Quindi yypact[0] vale -4, pertanto l’indice in yytable vale 5-4 = 1. yytable[1] vale 1 che significa "esegui uno shift su questo simbolo e vai allo stato 1". Si veda yycheck nei paragrafi successivi per ulteriori informazioni concernenti il checking. Se le voci in tabella yytable risultano negative(-n) (differenti da YYPACT_NINF) significa che si deve eseguire la riduzione secondo la regola #n.
yycheck
Questa è come una tabella di guardia e viene utilizzata in numerose situazioni. Ancora abbiamo a che fare con una tabella che contiene: simboli(numerici) e stati(numerici). Si può trovare un’ottima spiegazione di questa tabella nel codice sorgente di Bison (src/tables.h). Quindi la riportiamo esattamente così come la troviamo sul manuale(tradotta):
YYCHECK = un vettore indicizzato in parallelo con YYTABLE. Esso indica, in modo indiretto,
i limiti della porzione che si sta provando ad esaminare. Supponiamo che la porzione di
YYTABLE inizia all’index P e che l’indice in esame relativo a tale porzione sia I. Allora se
YYCHECK[P+I] != I, I è al di fuori dei limiti di quanto attualmente allocato, e devono
essere usati i parametri di defaulta(YYDEFACT oppure YYDEFGOTO). Viceversa si deve
utilizzare YYTABLE[P+I].
Questo è il vettore ottenuto nel caso del nostro esempio:
static const yytype_int8 yycheck[] =
{
0, 5, 6, 3, 7, 4, 3, 2, 9, -1,
-1, -1, 10
};
Esempio di utilizzo:
Supponiamo di essere nello stato 0 e che il look-ahead token sia 'a', quindi: yypact[0] = -4. Tale numero sommato al simbolo(numerico) of 'a' (5), come visto in precedenza, ci dà l’index in yytable. Prima di accedere ad yytable[1] e di procedere con lo shift del token, il parser deve verificare che yycheck[1] abbia un symbol number relativo al token corrente. Se il test fallisce, viene eseguita una riduzione di default! Tuttavia, nel nostro caso, yycheck[1] contiene 5 che è in effetti il simbolo(numerico) di 'a', in tal caso si procede ad analizzare yytable per sapere cosa si dovrà fare successivamente.
yycheck inoltre risulta utile nei casi in cui è necessario applicare istruzioni di salto stato(goto) in casi speciali relativi a simboli non-terminali, non presenti in yydefgoto; Consideriamo lo stesso esempio dato nella sezione relativa alla tabella yypgoto: si condierava lo stato #10 e la regola di riduzione era la #5 (P → a). Dopo aver sommato yypgoto[P]=2 allo stato corrente number (10) siamo arrivati a 12. Prima di procedere con analizzare yytable il parser verifica yycheck[12]: se il valore contenuto vale 10 (cioè riconosciamo #10 come stato speciale), altrinementi, si utilizza yydefgoto per decidere la transizione.
Altre tabelle di supporto
Ci sono altre tabelle che Bison produce in output utili allo scopo di debug, error recovery e output in formato verbose. Quella che segue ne è la lista unitamente ad una breve descrizione.
yyrhs - A -1 lista separata dei simboli relativi alla parte destra(RHS) di tutte le regole. yyrhs[n] = il primo simbolo della Regola #n.
yyprhs[n] - indice in yyrhs del primo simbolo RHS relativo alla regola #n.
yyrline[n] - linea # del codice sorgente della grammatica .y dove la regola n viene definita.
yytname[n] - una stringa che specifica il simbolo relativo al numero di simbolo n. ytoknum[n] - numero di token n relativo all’ennesimo Token.
Riepilogo tabelle
Quindi abbiamo descritto le seguenti tabelle:
yytranslate: mappa i token numbers restituiti da yylex() con i symbol number di Bison.
yydefact: elenca le regole di riduzione di default per ogni stato, 0 rappresenta un errore.
yydefgoto: elenca i parametri di salto(goto) per ogni simbolo non terminale. Viene utilizzata solo dopo aver eseguito opportune verifiche su yypgoto.
yyr1: symbol number di ogni regola(lhs, parte sinistra). Utilizzata ogniqualvolta si applichi una riduzione, utile per trovare il prossimo stato.
yyr2: lunghezza di ogni regola (rhs, parte destra). Utilizzata durante la riduzione per eliminare dalla parte superiore dello stack i simboli relativi alla regola.
yytable: una rappresentazione estremamente complessa che definisce le azioni da eseguire in ogni stato. I valori negativi rappresentano le riduzioni. Esiste un parametro negativo per discriminare gli errori.
yypgoto: elenco dei salti non-default per i simboli non-terminali.
yypact: directory into yytable indexed by state number. The displacements in yytable are indexed by symbol number.
yycheck: guard table used to check legal bounds within portions of yytable.
La Routine di Parsing Generata da Bison - yyparse ()
Passiamo quindi ad analizzare il funzionamento dell'yyparse() - la routine di parsing LR in base alle tabelle appena descritte. Per semplificare la lettura, abbiamo qui di seguito elencato alcuni frammenti di codice tratti dal file generato da Bison apportando alcune modifiche non funzionali. In particolare abbiamo: eliminato la gestione degli errori, molti controlli e chiamate MACRO. Tali modifcihe sono state necessarie al fine di rendere comprensibile il funzionamento di base dell'algoritmo di analisi. La spiegazione del codice è stat inserita nei commenti del codice.
/*queste che seguono sono variabili globali*/
/* il simbolo di look-ahead */
int yychar;
/* il valore semantico del simbolo look-ahead */
YYSTYPE yylval;
int
yyparse()
{
int yystate; /* lo stato corrente */
int yyn; /* questa è una variabile general purpose! Talvolta può servire a
rappresentare uno stato, in altri casi una regola! */
int yyresult; /* risultato di parsing restituito al chiamante */
int yytoken=0; /* token corrente*/
/* lo stack di stato: Questo parser non shifta simboli nello stack. Solo uno stack di
stati viene gestito */
int yyssa[YYINITDEPTH]; /* YYINITDEPTH vale 200 */
int *yyss = yyssa /* creazione e set del puntatore al fondo dello stack */
int *yyssp; /* Top dello stack */
/*
* Lo stack dei valori semantici: questo stack cresce parallelamente allo stack degli
* stati: ad ogni riduzione, i valori semantici vengono spuntati dal presente stack e
* viene eseguita l'azione.
*/
YYSTYPE yyvsa[YYINITDEPTH];
YYSTYPE *yyvs = yyvsa; /* puntatore all'elemento inferire dello stack */
YYSTYPE *yyvsp; /* puntatore all'elemento superiore dello stack */
/* POP, spunta dagli stack {stati/valori semantici } N simboli - utile per
azioni di riduzione */
#define YYPOPSTACK(N) (yyvsp -= (N), yyssp -= (N))
int yylen = 0; /* questa variabile viene usata nelle azioni di riduzione per
memorizzare la lunghezza RHS di una regola; */
/* Ok, le variabili sono stae dichiarate. Tiriamo la palla...*/
yystate = 0; /* Stato iniziale */
yychar = YYEMPTY /* YYEMPTY vale -2 */
yyssp = yyss; /* Top = puntiamo alla parte bassa dello stack */
yyvsp = yyvs; /* stessa cosa per i valori semantici */
goto yysetstate; /* bene, i goto sono utilizzati per ottenere la massima performance */
/* Ogni etichetta può essere pensata come una funzione */
yynewstate: /* inserisci un nuovo stato nello stack */
yyssp ++; /* Semplicemente incrementa la cima dello stack;
l'azione di 'push' avviene nelo stato che segue (yysetstate) */
yysetstate:
*yyssp = yystate; /* Ok, inserito lo stato sulla cima dello stack */
goto yybackup; /* in questo punto vengono eleborate le azioni */
yybackup: /* il punto principale del parser inizia qui */
yyn = yypact[yystate]; /* riferimento, a cosa punta indica yypact nello stato corrente */
if ( yyn == YYPACT_NINF) /* se è negatico è il momento di eseguire una riduzione */
goto yydefault; /* salto quindi alla riduzione di default; si veda in seguito */
/* verifichiamo se abbiamo un nuovo token da analizzare secondo l'algoritmo
look-ahead. Questo è un parser LALR(1) */
if (yychar == YYEMPTY)
yychar = YYLEX; /* la macro YYLEX viene definita come yylex() */
if (yychar <= YYEOF) /* YYEOF vale 0 - il token restituito dal
lexer al termine dell'input */
yychar = yytoken = YYEOF; /* setta tutto a EOF */
else
yytoken = yytranslate[yychar]; /* convertiamo il lexer-token in un
symbol-number interno*/
/* Ora il primo token look-ahead. Inizia l'analisi ! */
yyn = yyn + yytoken; /* questo equivale a yypact[yystate] + yytoken */
/* Si osservi questo check con attenzione. Stiamo verificando che yyn si trovi
* nei limiti di yytable e anche se yycheck contiene il token number corrente.
*/
if ( yyn < 0 || YYLAST < yyn || yycheck[yyn] != yytoken )
/* YYLAST è l'index più alto in yytable */
goto yydefault; /* è giunto il momento di compiere una riduzione */
/* Ok, yyn è all'interno di yytable */
yyn = yytable[yyn]; /* Questo equivale a yytable[ yypact[yystate] + yytoken ] */
if (yyn <= 0) /* Se yytable contiene un valore negativo o nullo,
non è uno shift - è una riduzione */
{
if (yyn == 0 || yyn == YYTABLE_NINF) /* Verifica la condizione di fuori estremo */
goto yyerrlab; /* in tal caso emette un errore */
/* Se non siamo in una casistica di errore procede con la riduzione
relativa alla regola # -yyn */
yyn = -yyn;
goto yyreduce; /* label in cui viene implementate le riduzioni */
}
/* L'ultimo check: siamo nello stato finale? */
if (yyn == YYFINAL) /* YYFINAL (vale 8 nel nostro caso) */
YYACCEPT; /* macro dfinita come 'goto acceptlab - una label per terminare */
/* I check sono tutti terminato; Se siamo in questo punto, non ci sono altre
opzioni, deve essere eseguito uno shift */
yystate = yyn; /* quindi, yyn (= yytable[ yypact[yystate] + yytoken ])
è lo stato che viene immesso nello stack */
*++yyvsp = yylval; /* Inserische il valore semantico del simbolo nello
stack (dei simboli) */
goto yynewstate; /* Questo incrementerà lo stack degli stati
ed il successivo yysetstate eseguirà l'inserimento */
yydefault: /* Questa label concerne la parte di codice che implementerà
la riduzione di default */
yyn = yydefact[yystate]; /* prende la riduzione di default per questo stato */
if ( yyn == 0 ) /* Questo stato non ha riduzioni di default.
Abbiamo un errore */
goto yyerrlab;
goto yyreduce; /* Ok, abbiamo la riduzione di default della regola # in yyn;
andiamo avanti e riduciamo lo stack */
yyreduce: /* Questa label concerne la parte di codice che implementerà
la riduzione dello stack. */
/* yyn contiene la regola# da usare per ridurre lo stack. */
/* Passi per compiere la riduzione:
* 1. Trovare il numero NSP di simboli destri(RHS), relativi ad una data regola #yyn;
* 2. Eseguire le azioni semantiche prelevando i valori dallo stack dei valori semantici;
* 3. Spuntare NSP simboli dallo stack degli stati ed NSP valori dallo stack della semantica;
* 4. Trovare l'LHS della regola #yyn;
* 5. Trovare il GOTO relativo all'ultimo simbolo dello stato corrente
* relativo al simbolo LHS;
* 6. Inserisci lo stato nello stack;
*/
yylen = yyr2[yyn]; /* Preleva il numero di simboli NSP relativi ad
una data regola (RHS) */
/* Azione semantica di default - $$=$1 */
yyval = yyvsp[1-yylen];
/* Esegue l'azione semantica */
switch ( yyn ) /* ogni regola ha la sua azione semantica */
{
default: break; /* Nella grammatica presentata non esistono azioni.
questo switch pertanto contiene solo il default.*/
}
YYPOPSTACK (yylen); /* Questo spunta gli stack degli stati e dei valori semantici.
Si veda in precedenza la definizione di questa macro */
yylen = 0; /* re-inizializza yylen */
*++yyvsp = yyval; /* Inserisce il risultato dell'azione semantica
in cima allo stack dei valori semantici */
/* Si procede quindi con la riduzione dei risultati (passi 4 - 6) */
yyn = yyr1[yyn]; /* Riutilizzo di yyn. Nei passi successivi yyn equivale
al simbolo (numerico) della regola LHS */
/*
* La prima cosa che deve essere verificata sono i GOTO anomali,
* altrimenti adotta i goto di default (YYDEFGOTO)
* Si osservi che se sottraiamo un dato numero di terminale (YYNTOKENS)
* da un simbolo numerico, otteniamo un index in yypgoto o yydefgoto
* per quel simbolo non-terminale.
*
*/
yystate = yypgoto[yyn - YYNTOKENS] + *yyssp;
/*
* Sono necessari ancora un paio di check prima di sapere se questo
* NON è un goto di default
* 1. yystate deve rimanere negli estremi di ytable ( 0 fino a YYLAST );
* 2. yycheck deve contenere lo stato corrente presente sulla cima
* dello stack;
*/
if ( 0 <= yystate && yystate <= YYLAST && yycheck[yystate] = *yyssp)
yystate = yytable[yystate]; /* preleva il GOTO da yytable */
else
yystate = yydefgoto[yyn - YYNTOKENS]; /* altrimenti adotta il GOTO di default */
goto yynewstate; /* Semplicemente inserisce il nuovo stato trovato
sulla cima dello stack e continua */
} /* Fine di yyparse() */
Questo spiega in maniera basilare e semplificata come vengono utilizzate le tabelle generate da Bison. La routine completa oltre a quanto descritto compie altre operazioni quali:
- check dello stack overflow;
- riposizionamento dello stack quando necessario;
- veriche di errore di vario genere (il parser, deve poter tornare in uno stato valido precedente tralasciando il token errato);
- produrre l'output testuale e gestione della yyerror();
- procedure di cleanup per i simboli e valori che vengono spuntati dai relativi stack per evitare lo spreco di memoria;
Nella descrizione sono state ignorate tutte le parti di codice che non erano strettamente legate all'algoritmo qui in analisi.
Un Esempio di Parsing
Bison ha delle opzioni per abilitare il tracciato di parsing. Settando yydebug = 1 prima di chiamare yyparse(), il parser produrrà un output in cui verranno avidenziate le riduzioni e gli shift dela stringa di input analizzata. Nel tracciato che segue abbiamo l'output di una stringa di input di esempio processata con il parser relativo alla grammatica in esame. Seguire il tracciato ottenuto nella routine di parsing ottenuta con le relative tabelle, ci può aiutare a meglio comprenderelo schema tabellare e le operazioni svolte da yyparse().
Stringa campione: a,a;a,a$
$ è il carattere di fine(EOF). Quello che segue il listato del tracciato:
Starting parse
Entering state 0
Reading a token: Next token is token 'a' ()
Shifting token 'a' ()
Entering state 1
Reducing stack by rule 5 (line 26):
$1 = token 'a' ()
-> $$ = nterm P ()
Stack now 0
Entering state 5
Reducing stack by rule 4 (line 24):
$1 = nterm P ()
-> $$ = nterm E ()
Stack now 0
Entering state 4
Reading a token: Next token is token ',' ()
Shifting token ',' ()
Entering state 10
Reading a token: Next token is token 'a' ()
Shifting token 'a' ()
Entering state 1
Reducing stack by rule 5 (line 26):
$1 = token 'a' ()
-> $$ = nterm P ()
Stack now 0 4 10
Entering state 13
Reducing stack by rule 3 (line 23):
$1 = nterm E ()
$2 = token ',' ()
$3 = nterm P ()
-> $$ = nterm E ()
Stack now 0
Entering state 4
Reading a token: Next token is token ';' ()
Reducing stack by rule 2 (line 21):
$1 = nterm E ()
-> $$ = nterm L ()
Stack now 0
Entering state 3
Next token is token ';' ()
Shifting token ';' ()
Entering state 9
Reading a token: Next token is token 'a' ()
Shifting token 'a' ()
Entering state 1
Reducing stack by rule 5 (line 26):
$1 = token 'a' ()
-> $$ = nterm P ()
Stack now 0 3 9
Entering state 5
Reducing stack by rule 4 (line 24):
$1 = nterm P ()
-> $$ = nterm E ()
Stack now 0 3 9
Entering state 12
Reading a token: Next token is token ',' ()
Shifting token ',' ()
Entering state 10
Reading a token: Next token is token 'a' ()
Shifting token 'a' ()
Entering state 1
Reducing stack by rule 5 (line 26):
$1 = token 'a' ()
-> $$ = nterm P ()
Stack now 0 3 9 12 10
Entering state 13
Reducing stack by rule 3 (line 23):
$1 = nterm E ()
$2 = token ',' ().
$3 = nterm P ()
-> $$ = nterm E ()
Stack now 0 3 9
Entering state 12
Reading a token: Now at end of input.
Reducing stack by rule 1 (line 20):
$1 = nterm L ()
$2 = token ';' ()
$3 = nterm E ()
-> $$ = nterm L ()
Stack now 0
Entering state 3
Now at end of input.
Stack now 0 3
Cleanup: popping nterm L ()
Storia del documento/story of the document
Il presente documento è stato tradotto da www.ovum.it pertendo dal documento originale dell'autore alla pagina http://www.cs.uic.edu/~spopuri/cparser.html.
The present document has been translated by www.ovum.it starting from the original document at page: http://www.cs.uic.edu/~spopuri/cparser.html.
Autore/Author: Satya Kiran Popuri
Riferimenti
[1] Nigel P. Chapman "LR Parsing Theory and practice". Cambridge University Press 1987. Un libro eccellente sulla teoria e l'implementazione dei parser LR. La grammatica di esempio adottata in questo articolo è presente in questo libro.
[2] Aho, Sethi, Ullman "Compilers - Principles Techniques and Tools". Pearson Education. Conosciuto come il "red Dragon book" è un testo classico per chi si avvicina ai compilatori.
[3] Robert Endre Tarjan ed Andrew Chi-Chih Yao nel loro articolo "Storing a Sparse Table", una pubblicazione dell'ACM(Association for Computer Machinery), Volume 22, edizione 11, pagine 606-611.
[4] codice sorgente del GNU Bison. http://ftp.gnu.org/pub/gnu/bison/
[5] Il manuale utende di GNU Bison. http://www.gnu.org/software/bison/manual
Diritti di copia del presente documento
Copyright ©2006 Satya Kiran Popuri.
Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license is included in the section entitled ``GNU Free Documentation License''.
Licenza GNU
GNU Free Documentation License
Version 1.2, November 2002
Copyright (C) 2000,2001,2002 Free Software Foundation, Inc.
51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
Everyone is permitted to copy and distribute verbatim copies
of this license document, but changing it is not allowed.
0. PREAMBLE
The purpose of this License is to make a manual, textbook, or other
functional and useful document "free" in the sense of freedom: to
assure everyone the effective freedom to copy and redistribute it,
with or without modifying it, either commercially or noncommercially.
Secondarily, this License preserves for the author and publisher a way
to get credit for their work, while not being considered responsible
for modifications made by others.
This License is a kind of "copyleft", which means that derivative
works of the document must themselves be free in the same sense. It
complements the GNU General Public License, which is a copyleft
license designed for free software.
We have designed this License in order to use it for manuals for free
software, because free software needs free documentation: a free
program should come with manuals providing the same freedoms that the
software does. But this License is not limited to software manuals;
it can be used for any textual work, regardless of subject matter or
whether it is published as a printed book. We recommend this License
principally for works whose purpose is instruction or reference.
1. APPLICABILITY AND DEFINITIONS
This License applies to any manual or other work, in any medium, that
contains a notice placed by the copyright holder saying it can be
distributed under the terms of this License. Such a notice grants a
world-wide, royalty-free license, unlimited in duration, to use that
work under the conditions stated herein. The "Document", below,
refers to any such manual or work. Any member of the public is a
licensee, and is addressed as "you". You accept the license if you
copy, modify or distribute the work in a way requiring permission
under copyright law.
A "Modified Version" of the Document means any work containing the
Document or a portion of it, either copied verbatim, or with
modifications and/or translated into another language.
A "Secondary Section" is a named appendix or a front-matter section of
the Document that deals exclusively with the relationship of the
publishers or authors of the Document to the Document's overall subject
(or to related matters) and contains nothing that could fall directly
within that overall subject. (Thus, if the Document is in part a
textbook of mathematics, a Secondary Section may not explain any
mathematics.) The relationship could be a matter of historical
connection with the subject or with related matters, or of legal,
commercial, philosophical, ethical or political position regarding
them.
The "Invariant Sections" are certain Secondary Sections whose titles
are designated, as being those of Invariant Sections, in the notice
that says that the Document is released under this License. If a
section does not fit the above definition of Secondary then it is not
allowed to be designated as Invariant. The Document may contain zero
Invariant Sections. If the Document does not identify any Invariant
Sections then there are none.
The "Cover Texts" are certain short passages of text that are listed,
as Front-Cover Texts or Back-Cover Texts, in the notice that says that
the Document is released under this License. A Front-Cover Text may
be at most 5 words, and a Back-Cover Text may be at most 25 words.
A "Transparent" copy of the Document means a machine-readable copy,
represented in a format whose specification is available to the
general public, that is suitable for revising the document
straightforwardly with generic text editors or (for images composed of
pixels) generic paint programs or (for drawings) some widely available
drawing editor, and that is suitable for input to text formatters or
for automatic translation to a variety of formats suitable for input
to text formatters. A copy made in an otherwise Transparent file
format whose markup, or absence of markup, has been arranged to thwart
or discourage subsequent modification by readers is not Transparent.
An image format is not Transparent if used for any substantial amount
of text. A copy that is not "Transparent" is called "Opaque".
Examples of suitable formats for Transparent copies include plain
ASCII without markup, Texinfo input format, LaTeX input format, SGML
or XML using a publicly available DTD, and standard-conforming simple
HTML, PostScript or PDF designed for human modification. Examples of
transparent image formats include PNG, XCF and JPG. Opaque formats
include proprietary formats that can be read and edited only by
proprietary word processors, SGML or XML for which the DTD and/or
processing tools are not generally available, and the
machine-generated HTML, PostScript or PDF produced by some word
processors for output purposes only.
The "Title Page" means, for a printed book, the title page itself,
plus such following pages as are needed to hold, legibly, the material
this License requires to appear in the title page. For works in
formats which do not have any title page as such, "Title Page" means
the text near the most prominent appearance of the work's title,
preceding the beginning of the body of the text.
A section "Entitled XYZ" means a named subunit of the Document whose
title either is precisely XYZ or contains XYZ in parentheses following
text that translates XYZ in another language. (Here XYZ stands for a
specific section name mentioned below, such as "Acknowledgements",
"Dedications", "Endorsements", or "History".) To "Preserve the Title"
of such a section when you modify the Document means that it remains a
section "Entitled XYZ" according to this definition.
The Document may include Warranty Disclaimers next to the notice which
states that this License applies to the Document. These Warranty
Disclaimers are considered to be included by reference in this
License, but only as regards disclaiming warranties: any other
implication that these Warranty Disclaimers may have is void and has
no effect on the meaning of this License.
2. VERBATIM COPYING
You may copy and distribute the Document in any medium, either
commercially or noncommercially, provided that this License, the
copyright notices, and the license notice saying this License applies
to the Document are reproduced in all copies, and that you add no other
conditions whatsoever to those of this License. You may not use
technical measures to obstruct or control the reading or further
copying of the copies you make or distribute. However, you may accept
compensation in exchange for copies. If you distribute a large enough
number of copies you must also follow the conditions in section 3.
You may also lend copies, under the same conditions stated above, and
you may publicly display copies.
3. COPYING IN QUANTITY
If you publish printed copies (or copies in media that commonly have
printed covers) of the Document, numbering more than 100, and the
Document's license notice requires Cover Texts, you must enclose the
copies in covers that carry, clearly and legibly, all these Cover
Texts: Front-Cover Texts on the front cover, and Back-Cover Texts on
the back cover. Both covers must also clearly and legibly identify
you as the publisher of these copies. The front cover must present
the full title with all words of the title equally prominent and
visible. You may add other material on the covers in addition.
Copying with changes limited to the covers, as long as they preserve
the title of the Document and satisfy these conditions, can be treated
as verbatim copying in other respects.
If the required texts for either cover are too voluminous to fit
legibly, you should put the first ones listed (as many as fit
reasonably) on the actual cover, and continue the rest onto adjacent
pages.
If you publish or distribute Opaque copies of the Document numbering
more than 100, you must either include a machine-readable Transparent
copy along with each Opaque copy, or state in or with each Opaque copy
a computer-network location from which the general network-using
public has access to download using public-standard network protocols
a complete Transparent copy of the Document, free of added material.
If you use the latter option, you must take reasonably prudent steps,
when you begin distribution of Opaque copies in quantity, to ensure
that this Transparent copy will remain thus accessible at the stated
location until at least one year after the last time you distribute an
Opaque copy (directly or through your agents or retailers) of that
edition to the public.
It is requested, but not required, that you contact the authors of the
Document well before redistributing any large number of copies, to give
them a chance to provide you with an updated version of the Document.
4. MODIFICATIONS
You may copy and distribute a Modified Version of the Document under
the conditions of sections 2 and 3 above, provided that you release
the Modified Version under precisely this License, with the Modified
Version filling the role of the Document, thus licensing distribution
and modification of the Modified Version to whoever possesses a copy
of it. In addition, you must do these things in the Modified Version:
A. Use in the Title Page (and on the covers, if any) a title distinct
from that of the Document, and from those of previous versions
(which should, if there were any, be listed in the History section
of the Document). You may use the same title as a previous version
if the original publisher of that version gives permission.
B. List on the Title Page, as authors, one or more persons or entities
responsible for authorship of the modifications in the Modified
Version, together with at least five of the principal authors of the
Document (all of its principal authors, if it has fewer than five),
unless they release you from this requirement.
C. State on the Title page the name of the publisher of the
Modified Version, as the publisher.
D. Preserve all the copyright notices of the Document.
E. Add an appropriate copyright notice for your modifications
adjacent to the other copyright notices.
F. Include, immediately after the copyright notices, a license notice
giving the public permission to use the Modified Version under the
terms of this License, in the form shown in the Addendum below.
G. Preserve in that license notice the full lists of Invariant Sections
and required Cover Texts given in the Document's license notice.
H. Include an unaltered copy of this License.
I. Preserve the section Entitled "History", Preserve its Title, and add
to it an item stating at least the title, year, new authors, and
publisher of the Modified Version as given on the Title Page. If
there is no section Entitled "History" in the Document, create one
stating the title, year, authors, and publisher of the Document as
given on its Title Page, then add an item describing the Modified
Version as stated in the previous sentence.
J. Preserve the network location, if any, given in the Document for
public access to a Transparent copy of the Document, and likewise
the network locations given in the Document for previous versions
it was based on. These may be placed in the "History" section.
You may omit a network location for a work that was published at
least four years before the Document itself, or if the original
publisher of the version it refers to gives permission.
K. For any section Entitled "Acknowledgements" or "Dedications",
Preserve the Title of the section, and preserve in the section all
the substance and tone of each of the contributor acknowledgements
and/or dedications given therein.
L. Preserve all the Invariant Sections of the Document,
unaltered in their text and in their titles. Section numbers
or the equivalent are not considered part of the section titles.
M. Delete any section Entitled "Endorsements". Such a section
may not be included in the Modified Version.
N. Do not retitle any existing section to be Entitled "Endorsements"
or to conflict in title with any Invariant Section.
O. Preserve any Warranty Disclaimers.
If the Modified Version includes new front-matter sections or
appendices that qualify as Secondary Sections and contain no material
copied from the Document, you may at your option designate some or all
of these sections as invariant. To do this, add their titles to the
list of Invariant Sections in the Modified Version's license notice.
These titles must be distinct from any other section titles.
You may add a section Entitled "Endorsements", provided it contains
nothing but endorsements of your Modified Version by various
parties--for example, statements of peer review or that the text has
been approved by an organization as the authoritative definition of a
standard.
You may add a passage of up to five words as a Front-Cover Text, and a
passage of up to 25 words as a Back-Cover Text, to the end of the list
of Cover Texts in the Modified Version. Only one passage of
Front-Cover Text and one of Back-Cover Text may be added by (or
through arrangements made by) any one entity. If the Document already
includes a cover text for the same cover, previously added by you or
by arrangement made by the same entity you are acting on behalf of,
you may not add another; but you may replace the old one, on explicit
permission from the previous publisher that added the old one.
The author(s) and publisher(s) of the Document do not by this License
give permission to use their names for publicity for or to assert or
imply endorsement of any Modified Version.
5. COMBINING DOCUMENTS
You may combine the Document with other documents released under this
License, under the terms defined in section 4 above for modified
versions, provided that you include in the combination all of the
Invariant Sections of all of the original documents, unmodified, and
list them all as Invariant Sections of your combined work in its
license notice, and that you preserve all their Warranty Disclaimers.
The combined work need only contain one copy of this License, and
multiple identical Invariant Sections may be replaced with a single
copy. If there are multiple Invariant Sections with the same name but
different contents, make the title of each such section unique by
adding at the end of it, in parentheses, the name of the original
author or publisher of that section if known, or else a unique number.
Make the same adjustment to the section titles in the list of
Invariant Sections in the license notice of the combined work.
In the combination, you must combine any sections Entitled "History"
in the various original documents, forming one section Entitled
"History"; likewise combine any sections Entitled "Acknowledgements",
and any sections Entitled "Dedications". You must delete all sections
Entitled "Endorsements".
6. COLLECTIONS OF DOCUMENTS
You may make a collection consisting of the Document and other documents
released under this License, and replace the individual copies of this
License in the various documents with a single copy that is included in
the collection, provided that you follow the rules of this License for
verbatim copying of each of the documents in all other respects.
You may extract a single document from such a collection, and distribute
it individually under this License, provided you insert a copy of this
License into the extracted document, and follow this License in all
other respects regarding verbatim copying of that document.
7. AGGREGATION WITH INDEPENDENT WORKS
A compilation of the Document or its derivatives with other separate
and independent documents or works, in or on a volume of a storage or
distribution medium, is called an "aggregate" if the copyright
resulting from the compilation is not used to limit the legal rights
of the compilation's users beyond what the individual works permit.
When the Document is included in an aggregate, this License does not
apply to the other works in the aggregate which are not themselves
derivative works of the Document.
If the Cover Text requirement of section 3 is applicable to these
copies of the Document, then if the Document is less than one half of
the entire aggregate, the Document's Cover Texts may be placed on
covers that bracket the Document within the aggregate, or the
electronic equivalent of covers if the Document is in electronic form.
Otherwise they must appear on printed covers that bracket the whole
aggregate.
8. TRANSLATION
Translation is considered a kind of modification, so you may
distribute translations of the Document under the terms of section 4.
Replacing Invariant Sections with translations requires special
permission from their copyright holders, but you may include
translations of some or all Invariant Sections in addition to the
original versions of these Invariant Sections. You may include a
translation of this License, and all the license notices in the
Document, and any Warranty Disclaimers, provided that you also include
the original English version of this License and the original versions
of those notices and disclaimers. In case of a disagreement between
the translation and the original version of this License or a notice
or disclaimer, the original version will prevail.
If a section in the Document is Entitled "Acknowledgements",
"Dedications", or "History", the requirement (section 4) to Preserve
its Title (section 1) will typically require changing the actual
title.
9. TERMINATION
You may not copy, modify, sublicense, or distribute the Document except
as expressly provided for under this License. Any other attempt to
copy, modify, sublicense or distribute the Document is void, and will
automatically terminate your rights under this License. However,
parties who have received copies, or rights, from you under this
License will not have their licenses terminated so long as such
parties remain in full compliance.
10. FUTURE REVISIONS OF THIS LICENSE
The Free Software Foundation may publish new, revised versions
of the GNU Free Documentation License from time to time. Such new
versions will be similar in spirit to the present version, but may
differ in detail to address new problems or concerns. See
http://www.gnu.org/copyleft/.
Each version of the License is given a distinguishing version number.
If the Document specifies that a particular numbered version of this
License "or any later version" applies to it, you have the option of
following the terms and conditions either of that specified version or
of any later version that has been published (not as a draft) by the
Free Software Foundation. If the Document does not specify a version
number of this License, you may choose any version ever published (not
as a draft) by the Free Software Foundation.
ADDENDUM: How to use this License for your documents
To use this License in a document you have written, include a copy of
the License in the document and put the following copyright and
license notices just after the title page:
Copyright (c) YEAR YOUR NAME.
Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, Version 1.2
or any later version published by the Free Software Foundation;
with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.
A copy of the license is included in the section entitled "GNU
Free Documentation License".
If you have Invariant Sections, Front-Cover Texts and Back-Cover Texts,
replace the "with...Texts." line with this:
with the Invariant Sections being LIST THEIR TITLES, with the
Front-Cover Texts being LIST, and with the Back-Cover Texts being LIST.
If you have Invariant Sections without Cover Texts, or some other
combination of the three, merge those two alternatives to suit the
situation.
If your document contains nontrivial examples of program code, we
recommend releasing these examples in parallel under your choice of
free software license, such as the GNU General Public License,
to permit their use in free software.
Questo è il vettore ottenuto nel caso del nostro esempio:
static const yytype_int8 yycheck[] =
{
0, 5, 6, 3, 7, 4, 3, 2, 9, -1,
-1, -1, 10
};
