Esercizio1a

Esercizio1b

Considereremo anzitutto la grammatica proposta come soluzione all'esercizio1a. Esaminandola anzitutto rispetto ad una analisi SLR, la piu' semplice tra gli LR.
Allo scopo dovremo generare la collezione canonica LR(0) della grammatica aumentata.

Una dimostrazione puo' facilmente essere ottenuta costruendo una collezione canonica (preferibilemente LR(0) piu' semplice e con pochi stati, prima di addentrarci nelle piu' impegnative LR(1)) e mostrando che essa non contiene stati con conflitti.

Occorre osservare che una tale grammatica forse l'abbiamo gia' definita come soluzione alla parte (a) dell'esercizio. Quindi si tratta con argomentazioni simili
a quelle fatte nelle considerazioni1 dell'esercizio2b, che tale grammatica e' adatta per l'analisi LR o viceversa no: in questo caso modificarla perche' lo sia.
Quindi produrre la collezione degli stati LALR(1) e verificare l'assenza di conflitti.

Nella parte a) dell'esercizio abbiamo gia' definito una grammatica non ambigua: Ebbene vediamo come sempre (considerazioni1 dell'esercizio2b) anzitutto, se tale grammatica e' anche adatta ad una analisi LR: Scopriremo di no. Dall'analisi delle cause di tale risultato negativo, vedremo come sia possibile definire una nuova grammatica per il linguaggio analizzabile SLR(1).

Si deve scoprire che la grammatica non e' SLR. Tuttavia e' LALR quindi analizzabile LR.

Possiamo partire dalla grammatica non ambigua definita nella parte (a) e studiarne le caratteristiche LL.

L'analisi delle espressioni di insieme ottenute per la definizione del linguaggio non ci inducono a ritenere la grammatica ambigua. Procediamo allora con l'analisi LR.
Dopo un'esame delle produzioni della grammatica per prevedere la presenza di eventuali conflitti SLR, si puo' procedere allo sviluppo sistematico della collezione LR(0) oppure LR(1).

La grammatica non e' LL(k) per nessun k. Nella soluzione data si giunge a questa conclusione con semplici osservazioni e con una dimostrazione.

Esercizio15b
 

Potremmo partire dalla grammatica non ambigua e context-free data nella parte (a), ed esaminarla per un'analisi LR. Troveremmo che tale grammatica non e' nemmeno LR(K). Una piu' attenta osservazione delle ragioni di tale falimento dovrebbero farci osservare strette analogie tra il linguaggio di questo esercizio e il linguaggio dell'esercizio 4. Se non avete affrontato l'esercizio4b: prima risolvete quello e poi affrontate questo. In analogia alla soluzione per 4b anche qui introdurremo una grammatica, differente da quella data nella parte (a), ma analizzabile LR. La nuova grammatica struttura le frasi del linguaggio in modo tale che le frasi della forma:
    (aa)^n+m b^m, sia riconosciute come strutturate in (aa)ⁿ (aa)^m b^m riducendo anzitutto, la parte (aa)^m b^m, ovvero la stinga (aa)ⁿ deve essere ridotta dopo e formare viable prefix a maniglie per (aa)^m b^m: esattamente come nella soluzione dell'eserczio4b.

Esercizio16b

Chiediamoci intanto se sia LL(1): verifichiamo, direttamente sulle produzioni della grammatica, le due semplici regole. Dovremmo scoprire che la grammatica e' LL(1) e, calcolate le funzioni first e follow, la relativa tabella di analisi LL e' immediata.

Chiediamoci intanto se sia LL(1): verifichiamo, direttamente sulle produzioni della grammatica, le due semplici regole. Dovremmo scoprire che la grammatica e' LL(1) e, calcolate le funzioni first e follow, la relativa tabella di analisi LL e' immediata.

Considereremo anzitutto la grammatica proposta come soluzione all'esercizio1a. Esaminandola rispetto alla presenza di: a) stella di Klenee, b) fattori, c) ricorsione sinistra. Sappiamo, infatti, che se una di tali condizioni occorre la grammatica non e' LL(1) ed allora occorre generare una nuova grammatica possibilmente trasformando la corrente rimuovendo la condizione violata.
Nell'ipotesi che nessuna di a), b), c), si presenti occorre verificare le proprieta' LL(1), basate sul calcolo dei first (o inizi) e dei follow (o seguiti).
La nostra grammatica soddisfa. Quindi generiamo la tabella applicando le note regole

Occorre mostrare che esiste almeno un K>=0 tale che per ogni sentenziale sinistra aAb tutte le produzioni applicabili A::=g_i (in una d. sinistra) sono tali che prese a coppie, ovvero per i diverso da j, first_k(g_ib) ha intersezione vuota con first_k(g_jb). Nel nostro caso, dobbiamo vedere che cio' e' falso almeno per sentenziale sinistra S: per essa, per ogni K, esistono due produzioni che rendono falsa tale condizione. Completate la dimostrazione.

Mentre non esiste grammatica LL(1), un analizzatore LL(1) esiste.

Occorre mostrare che esiste almeno un K>=0 tale che per ogni sentenziale sinistra aAb tutte le produzioni applicabili A::=g_i (in una d. sinistra) sono tali che prese a coppie, ovvero per i diverso da j, first_k(g_ib) ha intersezione vuota con first_k(g_jb). Nel nostro caso, dobbiamo vedere che cio' e' falso almeno per sentenziale sinistra S: per essa, per ogni K, esistono due produzioni che rendono falsa tale condizione. Completate la dimostrazione.

Dobbiamo procedere come nell'esercizio5c. Nel nostro caso, dobbiamo vedere che esiste una sentenziale sinistra tale che: per ogni K, esistono due produzioni che rendono falsa tale condizione. Completate la dimostrazione.

La dimostrazione data per la parte (b) dell'esercizio fornisce una dimostrazione valida anche per questa parte.
 

Non siamo in grado di esprimere una grammatica LL per linguaggi {aⁿ b^m | n>m}.

Dobbiamo calcolare la collezione LR(0). Calcolandola correttamente dovremmo scoprire un conflitto reduce/reduce.
Conclusione: ci troviamo di fronte a una grammatica per un linguaggio finito. La grammatica e' LL(1) ma non SLR(1).

Dobbiamo calcolare la collezione LR(0). Calcolandola correttamente dovremmo scoprire un conflitto reduce/reduce.
Come in esercizio16, ci troviamo di fronte a una grammatica LL(1) ma non SLR(1). Qui tuttavia la situazione e' piu' interessante.

Esercizio2d

La grammatica data struttura le frasi in modo infelice per un'analisi LL, infatti esaminando le produzioni per S o l'espressione di insieme (vedi soluzione2a) ottenuta per il linguaggio vediamo che produzioni differenti derivano frasi differenti (altrimenti avremmo ambiguita') ma con prefisso identico. Occorre individuare una grammatica che per tutte le frasi con identico prefisso utilizzi una identica derivazione sinistra, derivazione che cambiera' solo sulla base dei differenti suffissi delle frasi.

Si deve scoprire che e' possibile definire una grammatica LL(1) per il linguaggio. Tale grammatica e' ottenuta per tarsformazioni conservative della grammatica (quali, rimpiazzamenti di non terminali con la loro definizione, fattorizzazione, rimozione di ricorsione sinistra, etc...).

Banale trovare una grammatica per il linguaggio che sia analizzabile LL(1): se ne dia una.

Esercizio14d
 

Occore rimuovere l'ambiguita'.

Dobbiamo calcolare la collezione LR(1) e, contestualmente alla generazione dei vari stati, accorpare stati con kernel identici. Non dovremo trovare alcun conflitto e dalla collezione LALR e immediato costruire la relativa tabella di analisi.

Esercizio17d

Dobbiamo calcolare la collezione LR(1) operando come nell'esercizio16d. Qui tuttavia dovremmo scoprire che accorpando due stati della collezione aventi stesso kernel si ha un conflitto reduce/reduce. Notiamo anche che tale conflitto non permane se tali stati sono trattati come stati diversi, come avviene in LR(1).
Conclusione: ci troviamo di fronte a una grammatica per un linguaggio finito. La grammatica e' LL(1) ma non SLR(1), non e' LALR(1), e' tuttavia LR(1)

Esercizio16e

L'analizzatore LALR(1) gia' fornisce un analizzatore LR(1).

Esercizio17e

Calcolata la collezione LR(1) si nota la mancanza di conflitti e si puo' costruire facilmente la relativa tabella di analisi.
Notate: per un linguaggio cosi' banale nessuno si sognerebbe di ricorrere ad una grammatica di questo tipo. Tuttavia e' facile convincersi che semplici modifiche delle produzioni possono condurre ad una grammatica con caratteristiche di analisi del tutto analoghe alla grammatica originale, ma generante un linguaggio non banale. Potete tentare.