Soluzioni Proposte



Esercizio1a s

S::= r A I S t I
A::= a A | e
I::= i I | e

Esercizio2a

Eliminazione mutua ricorsione da A, B
 

S::= A | Bbb
A::= aB
B::= aaBb | e

Sottolinguaggi:
 

L(B) = {a2n bn | n >= 0}
L(A) = {aa2n bn | n >= 0}
L(S) = {aa2n bn | n >= 0}U{a2n bn bb | n >= 0}
= {a2n+1 bn , a2n bn+2 | n >= 0}

Esercizio3a

S::= (L) | ()
T::= E (L) | E
L::= L , T | T
E::= A | B

Esercizio4a

S::= A S | B
A::= a A | a
B::= a B b | e

    la grammatica genera il linguaggio richiesto, tuttavia essa e' ambigua. Infatti:

                S => AS => AAS =>* aa
    ma anche:

S => AS => * aa


Diversamente una soluzione all'esercizio e':

S::= A B
A::= a A | a
B::= a B b | e

 

Esercizio5a

Eliminazione mutua ricorsione da A, B
 

S::= AbB | B
A::= cB | a
B::= cB | a

Sottolinguaggi:
 

L(A) = L(B) = {cn a | n >= 0}
L(S) = {cn a b cm a, cm a | n, m >= 0}

Esercizio6a

S::= D | P
D::= u u D v | u v
P::= u u P v | v v

Esercizio7a

S::= S (L) | E
L::= L , S | S
E::= a | b

Esercizio8a

S::= S , E | e
E::= a | b

Esercizio9a

S::= A D
A::= a A b | e
D::= d D | e

Esercizio10a

Eliminazione mutua ricorsione da U, V
 

S::= U | V v v
U::= u V
V::= u u V v | v

Sottolinguaggi:
 

L(V) = {u2n v vn | n >= 0}
L(U) = {u u2n v vn | n >= 0}= {u2n+1 v vn | n >= 0}
L(S) = {u2n+1 v vn | n >= 0}U{u2n v vn v v | n >= 0}
= { u2n+1 vn+1, u2n vn+3 | n >= 0}

Esercizio11a

Dobbiamo escludere la frase vuota

S::= a N c | b B a
N::= a N c | B
B::= b B a | e

Esercizio12a

Sottolinguaggi:
 

L(U) = {un+1 | n >= 0}
L(S) = {x1 u xn u w v v vn | n >= 0}

Esercizio13a

In forma canonica e riordinando:
 

S::= S' A | A b S"
S'::= a S' a | c
S"::= S" a a | e
A::= A a | e

Sottolinguaggi:
 

L(A) = {an | n >= 0}
L(S") = {a2n | n >= 0}
L(S') = {an c an | n >= 0}
L(S) = {an c an am | n,m >= 0}U{an b a2m | n, m >= 0}
= {an c an+m, an b a2m | n, m >= 0}

Esercizio14a

Sottolinguaggi:
 

L(C) = {xn cc y2n| n >= 0}
L(B) = {xn c yn| n >= 0}
L(A) = {xn a x2n| n >= 0, aISIN({cc}U{xn cc y2n| n >= 0})}
= {xn cc x2n, xn xm cc y2m x2n| n,m >= 0}
= {xn cc x2n, xn+m cc y2m x2n| n,m >= 0}
L(S) = {zn a z b1 z bn | n >= 0, a ISINL(A), biISINL(B)}

Esercizio15a

S::= S' | e
S'::= a a S' b | A | B
A::= a a A | a a
B::= b B | b

Esercizio16a

Sottolinguaggi:
 

L(C) = {c,l}
L(B) = {b,l}
L(A) = {be, e, cd, d}

L(S) = {abe, ae, acd, ad, bbd, bd}


 
 

Esercizio1b

        La grammatica aumentata:

            S'::= S
            S::= r A I S t I
            A::= a A | e
            I::= i I | e

       Collezione degli stati SLR:

I0 = Clos(S'->.S)

{S'->.S, S->.rAIStI}

I1 = G(0,S)

{S'->S.}

I2 = G(0,r) = G(5,r)

{S->r.AIStI, A->.aA, A->.}

I3 = G(2,A)

{S->rA.IStI, I->.iI, I->.}

I4 = G(2,a) = G(4,a)

{A->a.A, A->.aA, A->.}

I5 = G(3,I)

{S->rAI.StI, S->.rAIStI}

I6 = G(3,i) = G(6,i) = G(10,i)

{I->i.I, I->.iI, I->.}

I7 = G(4,A) 

{A->aA.}

I8 = G(5,S) 

{S->rAIS.tI}

I9 = G(6,I)

{I->iI.}

I10 = G(8,t)

{S->rAISt.I, I->.iI, I->.}

I11 = G(10,I) 

{S->rAIStI.}

        Possiamo ora controllare la presenza di conflitti, se non gia' fatto contestualmente alla
        generazione degli stati. Lo abbiamo gia' fatto per gli stati che possono presentare
        conflitti, ovvero: I2 (controllare follow(A)), I3 (controllare follow(I)), I4 (controllare
        follow(A)), I6 (controllare follow(I)), I10 (controllare follow(I)):
 

Follow

 S

 {$,t}

 

 A

 {i,r}

 

 I

 {r,$,t}

        Otteniamo la tabella di parsing SLR(1) seguente (produzioni riferite con progressivi da 0):
 
 

Action

r

t

a

i

$

Goto

S

A

I

I0

 S/2

  ---

  ---

  ---

  ---

 

  I1

  ---

  ---

I1

  ---

  ---

  ---

  ---

accept

 

  ---

  ---

  ---

I2

 R/3

  ---

  S/4

 R/3

  ---

 

  --- 

  I3

  ---

I3

 R/5

 R/5

  ---

  S/6

 R/5

 

  ---

  ---

  I5

I4

  R/3

  ---

  S/4

  R/3

  ---

 

  ---

  I7

  ---

I5

  S/2

  ---

  ---

  ---

  ---

 

  I8

  ---

  ---

I6

  R/5

  R/5

  ---

  S/6

  R/5

 

  ---

  ---

  I9

I7

  R/2

  ---

  ---

  R/2

  ---

 

  ---

  ---

  ---

I8

  ---

 S/10

  ---

  ---

  ---

 

  ---

  ---

  ---

I9

  R/4

  R/4

  ---

  ---

  R/4

 

  ---

  ---

  ---

I10

 R/5

  R/5

  ---

  S/6

  R/5

 

  ---

  ---

 I11

I11

  ---

  R/1

  ---

  ---

  R/1

 

  ---

  ---

  ---

Esercizio2b

        Esaminiamo la grammatica.

Considerazione1: Se ci e' chiaro il processo di riduzione effettuato da un analizzatore LR, allora osserviamo che la grammtica consente un riconoscimento di tale tipo. Infatti, Le due produzioni per S  ci dicono che il riconoscimento avverra' sempre cercando, inizialmente, una maniglia ad A o a B. Le produzioni per A e per B ci dicono che il riconoscitore trovando il simbolo acome lookahead operera' sempre uno shift, rimandando ogni riduzione alla lettura di un simbolo b. Quando cio' avverra', la maniglia e' B::=e. Dopo, se nello stack sono contenute aapplichera', in corrispondenza a b nel lookhaead, prima la maniglia A::=aB e dopo la maniglia B::=aAb. Se e quando nello stack le a accumulate sono state ridotte, allora o abbiamo $ nel lookahead (maniglia S::=A, applicabile), o abbiamo b. Quest'ultimo caso condurra' dopo due shift alla maniglia S::=Bbb.

Considerazione2: Le osservazioni precedenti, nella forma in cui sono state esposte, sebbene indicative, non formano una dimostrazione. Una dimostrazione puo' facilmente essere ottenuta costruendo la collezione canonica LR(0) e mostrando che essa non contiene stati con conflitti.


        Calcoliamo la collezione canonica degli stati LR(0).

            S'::= S
            S::= A | B b b
            A::= a B
            B:= a A b | e
 

I0 = Clos(S'->.S)

{S'->.S, S->.A, S->.Bbb, A->.aB, B->.aAb, B->.}

I1 = G(0,S)

{S'->S.}

I2 = G(0,A)

{S->A.}

I3 = G(0,B)

{S->B.bb}

I4 = G(0,a) = G(4,a)

{A->a.B, B->a.Ab, A->.aB, B->.aAb, B->.}

I5 = G(3,b)

{S->Bb.b}

I6 = G(4,B)

{A->aB.}

I7 = G(4,A)

{B->aA.b}

I8 = G(5,b)

{S->Bbb.}

I9 = G(7,b)

{B->aAb.}

La dimostrazione deve essere completata dal mostrare che gli stati sopra non contengono conflitti. Occorre quindi calcolare la tabella FOLLOW ed esaminare gli stati con possibili conflitti, ovvero: I0, I4.

Follow

   S

{$}

 

   A

{b,$}

 

   B

{b,$}

Esercizio3b
 

La soluzione alla parte a) propone una grammatica ed e' facile convincersi con argomentazioni simili a quelle fatte nelle considerazioni1 dell'esercizio2b, che tale grammatica e' adatta per l'analisi LR. Tuttavia ci e' richiesto un analizzatore LALR, calcolereremo allora, la collezione degli stati LALR e procederemo contestualmente alla verifica di non conflittualita' in essi.
Riportiamo di seguito grammatica (aumentata) e la tabella FOLLOW per essa (utile solo per confrontare la tabella con quanto avremmo ottenuto in un analisi SLR):
 
 

S'::= S
S::= (L) | ()
T::= E (L) | E
L::= L , T | T
E::= A | B

Follow

      S

{$}

 

     T

{',',)}

 

     L

{',',)}

 

     E

{',',),(}

Collezione stati LALR:
 

I0 = Clos(S'->.S/$)

{S'->.S/$, S->.(L)/$, S->.()/$}

I1 = G(0,S)

{S'->S./$}

I2 = G(0,()

{S->(.L)/$, S->(.)/$, L->.L,T/), L->.T/), T->.E(L)/), T->.E/), E->.A/(/), E->.B/(/)}

I3 = G(2,L)

{S->(L.)/$, L->L.,T/)}

I4 = G(2,))

{S->()./$}

I5 = G(2,T) = G(11,T)

{L->T./)}

I6 = G(2,E) = G(10,E) = G(11,E)

{T->E.(L)/), T->E./)}

I7 = G(2,A) = G(10,A) = G(11,A)

{E->A./(/)}

I8 = G(2,B) = G(10,B) = G(11,B)

{E->B./(/)}

I9 = G(3,))

{S->(L)./$}

I10 = G(3,,) = G(13,,)

{L->L,.T/), T->.E(L)/), T->.E/), E->.A/(/), E->.B/(/)}

I11 = G(6,()

{T->E(.L)/), L->.L,T/), L->.T/), T->.E(L)/), T->.E/), E->.A/(/), E->.B/(/)}

I12 = G(10,T)

{L->L,T./)}

I13 = G(11,L)

{T->E(L.)/),L->L.,T/)}

I13 = G(13,))

{T->E(L)./)}

Abbiamo gia' controllato l'assenza di conflitti nell'unico stato che avrebbe potuto contenerne, ovvero I6.
L'esercizio e' concluso.
Utilizzando la tabella dei FOLLOW, tuttavia, possiamo controllare:
    a)  se l'analisi SLR sarebe stata possibile
    b) eventuali differenze tra l'analisi LALR e l'analisi SLR per la grammatica sopra.
Ebbene:
    a) l'analisi SLR sarebbe stata possibile
    b) esistono differenze proprio nello stato I6 che conducono LALR ad un fallimento anticipato rispetto a SLR nel caso di alcune frasi, ovviamente non appartenenti al linguaggio. Una di tali frasi e': "(A,)"
 
 

Esercizio4b
 

Riprendiamo la grammatica data per la soluzione della parte a):

    S::= A B
    A::= a A | a
    B::= a B b | e

e domandiamoci se tale grammatica consente un'analisi LR. Una ragionevole conoscenza del processo di riduzione dovrebbe indurre ad aspettarci una risposta negativa. Infatti, la prima produzione ci dice che inizialmente in presenza di una prima 'a' opereremo uno shift nel tentativo di riconoscere successivamente una maniglia ad 'A". Purtroppo, gia' alla seconda 'a' nascono i problemi: la produzione A::= a tenderebbe a fornire una maniglia per A che ha nel proprio follow giusto un simbolo 'a', mentre la produzione A::= a A tenderebbe invece a considerare la nuova 'a' come parte di un viable prefix ad una successiva maniglia per 'a'. In altre parole, la grammatica non fornisce indicazioni all'analisi per capire quando una sequenza iniziale di 'a' sia riducibile ad A e quando, quindi, occorra iniziare a cercare la maniglia a B.
La soluzione va trovata scrivendo una grammatica che risolva questo punto.
Queste argomentazioni tuttavia, non forniscono una dimostrazione. Ne' una tale dimostrazione e' richiesta dall'esercizio. Occorre pero' convincersi che la grammatica sopra non consente un'analisi LR e comprendere come scriverne una che la consenta. Pertanto, prima di dare una nuova grammatica, mostreremo quanto detto sopra costruendo la collezione canonica LR(0) della grammatica (aumentata):
 
 
 

I0 = Clos(S'->.S)

{S'->.S, S->.AB, A->.aA, A->.a}

Follow

 S

{$}

 

 A

{a,$}

 

 B

{b,$}

I1 = G(0,S)

{S'->S.}

 

I2 = G(0,A)

{S->A.B}

 

I3 = G(0,a)

{A->a.A, A->a.}

 conflitto shift/reduce

Definiamo una grammatica che risolve il problema di ridurre le frasi di A prima di riconoscere B. Otteniamo cio' evitando di introdurre il sottolinguaggio per A. Ecco una soluzione.
 

S::= a S | a B
B::= a B b | e


Ed ecco la relativa collezione canonica LR(0): infatti la grammatica e' SLR come e' dimostrato dall'assenza di conflitti negli stati della collezione.
 
 

I0 = Clos(S'->.S)

{S'->.S, S->.aS,
  S->.aB}

Follow

 S

 {$}

 

 B

{b,$}

 

I1 = G(0,S)

{S'->S.}

 

 

I2 = G(0,a)

{S->a.S, S->a.B
  S->.aS, S->.aB, 
  B->.aBb, B->.}

 

nessun conflitto:
 {a} insect{b,$} = {}

I3 = G(2,S) = G(5,S)

{S->aS.}

 

 

I4 = G(2,B) 

{S->aB.}

 

 

I5 = G(2,a) = G(5,a)

{S->a.S, S->a.B, 
  B->a.Bb, 
  S->.aS, S->.aB, 
  B->.aBb, B->.}

 

nessun conflitto:
 {a} insect{b,$} = {}

I6 = G(5,B)

{S->aB.,  B->aB.b}

 

nessun conflitto:
 {b} insect{$} = {}

I7 = G(6,b)

{B->aBb.}

 

 

Esercizio5b
 

Il calcolo del linguaggio generato dalla grammatica non ci induce a ritenere la grammatica ambigua. Pertanto, consideriamo la grammatica data per un'analisi di tipo LR.

S::= AbB | B
A::= cB | a
B::= A

Consideriamo SLR: osserviamo subito che ogni stringa di L(A) fornisce un viable prefix tanto per S->AbB che per B->A, conducendo ad un conflitto shift/reduce. Verifichiamo quanto osservato:
 

I0 = Clos(S'->.S)

{S'->.S, S->.AbB, S->.B, A->.cB, A->.a, B->.A}

Follow

 S

 {$}

 

 A

 {b,$}

 

 B

 {$,b}

 

I1 = G(0,S)

{S'->S.}

 

 

I2 = G(0,A)

{S->A.bB, B->A.}

 

  conflitto
  {b} insect {$,b} = {b}

 
Potremmo passare alla collezione LALR e in caso di conflitto esaminare la collezione LR(1). Decidiamo di calcolare subito la collezione LR(1) per l'analisi LR(1) e solo dopo, ridurci alla LALR, se possibile.
 

I0 = Clos(S'->.S/$)

{S'->.S/$, S->.AbB/$, S->.B/$, A->.cB/b/$, A->.a/b/$, B->.A/$}

 

I1 = G(0,S)

{S'->S./$}

 

I2 = G(0,A)

{S->A.bB/$, B->A./$}

 nessun conflitto
  {b} insect {$} = {}

I3 = G(0,B)

{S->B./$}

 

I4 = G(0,c) = G(4,c)

{A->c.B/b/$, B->.A/b/$, A->.cB/b/$, A->.a/b/$}

 

I5 = G(0,a) = G(4,a) 

{A->a./b/$}

 

I6 = G(2,b) 

{S->Ab.B/$, B->.A/$, A->.cB/$, A->.a/$}

 

I7 = G(4,B)

{A->cB./b/$}

 

I8 = G(4,A)

{B->A./b/$}

 

I9 = G(6,B) 

{S->AbB./$}

 

I10 = G(6,A) = G(11,A)

{B->A./$}

 

I11 = G(6,c) = G(11,c)

{A->c.B/$, B->.A/$, A->.cB/$, A->.a/$}

 

I12 = G(6,a) = G(11,a)

{A->a./$}

 

I13 = G(11,B)

{A->cB./$}

 

Possiamo vedere che la grammatica e' anche LALR e calcolare gli stati della tabella LALR: si tratta di compattare I4 con I11, I5 con I12, I7 con I13, I8 con I10.
 

I0 = Clos(S'->.S/$)

{S'->.S/$, S->.AbB/$, S->.B/$, A->.cB/b/$, A->.a/b/$, B->.A/$}

 

I1 = G(0,S)

{S'->S./$}

 

I2 = G(0,A)

{S->A.bB/$, B->A./$}

 nessun conflitto
  {b} insect {$} = {}

I3 = G(0,B)

{S->B./$}

 

I4 = G(0,c) = G(4,c) = G(6,c)

{A->c.B/b/$, B->.A/b/$, A->.cB/b/$, A->.a/b/$}

 

I5 = G(0,a) = G(4,a) = G(6,a)

{A->a./b/$}

 

I6 = G(2,b) 

{S->Ab.B/$, B->.A/$, A->.cB/$, A->.a/$}

 

I7 = G(4,B)

{A->cB./b/$}

 

I8 = G(4,A) = G(6,A)

{B->A./b/$}

 

I9 = G(6,B) 

{S->AbB./$}

 

Concludiamo: la grammatica e' strettamente LALR.
 

Esercizio7b

Esaminiamo anzitutto se la grammatica definita nella parte (a) sia adatta ad un'analisi LL. La presenza della ricorsione sinistra ci dice NO. Provvediamo a rimuoverla, otteniamo la grammatica sotto e le tabelle first e follow a fianco.
 
 

S::= E S'
S'::= (L) S' | e
L::= S L'
L'::= , S L | e
E::= a | b

FIRST

 

E S' 

 {a,b}

(L) S'

 {(}

S L'

 {a,b}

, S L

 {,}

a

 {a}

b

 {b}

FOLLOW

 

S

 { $, ',',) }

S'

 {$, ',',) }

L

 { ) }

L'

 { ) }

E

 { (,$, ',',) }

La grammatica cosi' ottenuta per trasformazioni conservative (rimozione ricorsione sinistra) calcola il linguaggio richiesto ed e' analizzabile LL(1). La tabella di analisi e':
 
 

 

a

b

(

)

,

$

S

1

1

--- 

--- 

--- 

--- 

S'

--- 

--- 

2

3

3

3

L

4

4

--- 

--- 

--- 

--- 

L'

--- 

--- 

--- 

6

5

--- 

E

7

8

--- 

--- 

--- 

--- 


Esercizio10b

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.

S ::= U
S ::= Vvv
U ::= uV
V ::= uUv
V ::= v

Analisi SLR: calcolo della collezione LR(0) della grammatica aumentata.
 

I0 = Clos (S'->.S)

 {S'->.S, S->.U, S->.Vvv, U->.uV, V->.uUv, V->.v}

FOLLOW

 

S'

 {$}

S

 {$}

U

 {$,v}

V

 {$,v}

I1 = G(0,S)

{S'->S.}

 

I2 = G(0,U)

{S->U.}

 

I3 = G(0,V)

{S->V.vv}

 

I4 = G(0,u) = G(4,u)

{U->u.V, V->u.Uv, V->.uUv, V->.v, U->.uV}

 

I5 = G(0,v) = G(4,v)

{V->v.}

 

I6 = G(3,v)

{S->Vv.v}

 

I7 = G(4,V)

{U->uV.}

 

I8 = G(4,U)

{V->uU.v}

 

I9 = G(6,v)

{S->Vvv.}

 

I10 = G(8,v)

{V->uUv.}

 

Glis stati LR(0) sono stati calcolati tutti, nessuno presenta conflitti, quindila grammatica ha analizzatore SLR(1)
Conclusione: La grammatica ha analizzatore LR di tipo SLR/LALR/LR.
Il calcolo della tabella di analisi e' banale e viene omesso.

Esercizio14b
 

La grammatica non e' LL(K) per nessun K, infatti la grammatica e' ambigua. Cio' puo' essere gia' notato dal calcolo del linguaggio generato: l'espressione su insiemi {cc}U{xn cc y2n| n >= 0}, generata nel calcolo del sottolinguaggio L(A), mostra che la stringa cc e' contenuta in piu' di un insieme componente l'unione. Questa osservazione ci fornisce anche una dimostrazione formale con due alberi di derivazione aventi stessa frontiera ma differente struttura: si considerino gli alberi ottenuti dalle seguenti due derivazioni sinistre

    derivazione 1 -    S -> A -> cc
    dervazione 2 -    S -> A -> C -> cc


Esercizio15b

Potremmo partire dalla grammatica non ambigua e context-free data nella parte (a), ed esaminarla per un'analisi LR.

    S::= S1 | e
    S1::= a a S1 b | A | B
    A::= a a A | a a
    B::= b B | b

Questa grammatica non e' LR(k) per nessun k. Infatti, la stringa "aa" e' viable prefix sia per maniglie S1::= aaS1b, sia per A::= aa. Purtroppo il contesto di lookahead che puo' seguire S1 e' esattamente lo stesso che puo' seguire A (notare la produzione S1::=A). Potete verificare facilmente che la collezione LR(1) ha un conflitto shift/reduce nello stato raggiunto, a partire da I0, dopo la lettura di "aa" (items B->.bB, A->aa.). In realta', tale contesto di lookahead e' della forma bn, con n arbitrario naturale. Quindi anche utilizzando k>>1 simboli di lookahead, troveremmo che per stringhe con suffisso bn per n>k, l'analizzatore LR(k) ha un conflitto.
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. In definitiva dobbiamo introdurre una grammatica che definisca il linguaggio in modo tale che l'analisi ascedente di stringhe della forma (aa)h(aa)i bi riconosca prima le coppie annidate (aa)i bi e dopo il prefisso (aa)h. Riscriviamo l'espressione di insiemi che definisce il linguaggio evidenziando questi aspetti:
            L(S)= {l}U L(A) U L(B)
            L(A)= {(aa)h (aa)i bi | i>=0, h>0}
            L(B)= {(aa)i bi bh | i>=0, h>0}

Otteniamo la grammatica seguente (oppure):

    S::= aaA | B | e
    A::= aaA | C    leproduzioni di Aconsentono di avere come prima maniglia C
    C::= aa C b | e
    B::= C D
    D::= bD | b

Calcoliamo la collezione LR(0) della grammatica aumentata:
 

I0=Clos(S'->.S)

{S'->.S, S->.aaA, S->.B, S->., B->.CD, C->.aaCb, C->.}

FOLLOW

 

S

{$}

A

{$}

B

{$}

C

{$,b}

D

{$}

 conflitto reduce/reduce
  {$} insect {$,b} = {$}

La grammatica non e' SLR(1). Osserviamo che il fallimento e' dovuto ad un conflitto falso, dovuto alla mancanza di contesto. Infatti la maniglia a C e' attraversata in modi diversi dalla produzione per A e da quella per B. Possiamo modificare la grammatica per risolverlo (soluzione bis).
Calcoliamo la collezione LALR della grammatica aumentata:
 

I0=Clos(S'->.S)

{S'->.S/$, S->.aaA/$, S->.B/$, S->./$, B->.CD/$, C->.aaCb/b, C->./b}

    nessun conflitto

I1=G(0,S)

{S'->S./$}

 

I2=G(0,a)

{S->a.aA/$, C->a.aCb/b}

 

I3=G(0,B)

{S->B./$}

 

I4=G(0,C)

{B->C.D/$, D->.bD/$, D->.b/$}

 

I5=G(2,a)

{S->aa.A/$, C->aa.Cb/b, A->.aaA/$, A->.C/$, C->.aaCb/$/b, C->./$/b}

    nessun conflitto

I6=G(4,D)

{B->CD./$}

 

I7=G(4,b)=G(7,b)

{D->b.D/$, D->b./$, D->.bD/$, D->.b/$}

     nessun conflitto

I8=G(5,A)

{S->aaA./$}

 

I9=G(5,C)=G(13,C)

{C->aaC.b/b/$, A->C./$}

     nessun conflitto

I10=G(5,a)=G(13,a)

{A->a.aA/$, C->a.aCb/$/b}

 

I11=G(7,D)

{D->bD./$}

 

I12=G(9,b)

{C->aaCb./b}

 

I13=G(10,a)

{A->aa.A/$, C->aa.Cb/$/b, A->.aaA/$, A->.C/$, C->.aaCb/$/b, C->./$/b}

    nessun conflitto

I14=G(13,A)

{A->aaA./$}

 

 
Dobbiamo calcolare ora, la tabella di analisi LALR(1):
 

-------------- omessa ---------------

        una grammatica SLR per il linguaggio

Riprendiamo la grammatica precedente e modifichiamo le produzioni per C nel seguente modo:

 
    S::= A | B
    A::= aa A | aa C | e  
    C::= aa C b | aab
    B::= C D | D
    D::= bD | b


in questo modo, come vedremo, rimuoviamo il conflitto. Da osservare che il linguaggio calcolato e' lo stesso della precedente grammatica (ovvio, ripensate alla relazione tra produzioni ed equazioni tra linguaggi), tuttavia la struttura delle frasi e' cambiata in particolare il sottolinguaggio L(C) non contiene piu la stringa vuota e ogni maniglia a C deve attraversare almeno una stringa aab.
Calcoliamo la collezione SLR(1):
 

I0=Clos(S'->.S)

{S'->.S, S->.A, S->.B, A->., A->.aaA, A->.aaC, B->.CD, B->.D, C->.aaCb, C->.aab, D->.bD, D->.b}

FOLLOW

 

S

{$}

A

{$}

B

{$}

C

{b,$}

D

{$}

  nessun conflitto reduce/reduce
  nessun conflitto shift/reduce
    {a,b} insect {$} = {}

I1=G(0,S)

{S'->.S}

 

I2=G(0,A)

{S->A.}

 

I3=G(0,B)

{S->B.}

 

I4=G(0,a)=G(8,a)

{A->a.aA, A->a.aC, C->a.aCb, C->a.ab}

 

I5=G(0,C)

{B->C.D, D->.bD, D->.b}

 

I6=G(0,D)

{B->D.}

 

I7=G(0,b)=G(5,b)=G(7,b)

{D->b.D, D->b., D->.bD, D->.b}

  nessun conflitto shift/reduce
    {b} insect {$} = {}

I8=G(4,a)

{A->aa.A, A->aa.C, C->aa.Cb, C->aa.b, A->.aaA, A->.aaC, A->., C->.aaCb, C->.aab}

  nessun conflitto shift/reduce
    {a,b} insect {$} = {}

I9=G(5,D)

{B->CD.}

 

I10=G(7,D)

{D->bD.}

 

I11=G(8,A)

{A->aaA.}

 

I12=G(8,C)

{A->aaC., C->aaC.b}

  nessun conflitto shift/reduce
    {b} insect {$} = {}

I13=G(8,b)

{C->aab.} 

 

I14=G(12,b)

{C->aaCb.}

 

Da notare che la collezione SLR(1) della nuova grammatica e' 'pesante' quanto la LALR della prima grammatica data.

Esercizio16b
 

La grammatica e' LL(K) per ogni k>=1: ci basta dimostrare che e' LL(1). Infatti, calcoliamo le tabelle first e follow:

First

aA

{a}

Follow

S

{$}

 

bBd

{b}

 

A

{$}

 

Be

{b,e}

 

B

{d,e}

 

Cd

{c,d}

 

C

{d}

 

b

{b}

 

 

 

 

c

{c}

 

 

 

otteniamo la seguente tabella LL(1) che risulta deterministica, ovvero priva di conflitti:
 
 

 

a

b

c

d

e

$

S

S::= aA

S::= bBd

---

---

---

---

A

---

A::= Be

A::=Cd

A::=Cd

A::= Be

---

B

---

B::= b

---

B::= e

B::= e

---

C

---

---

B::= c

C::= e

---

---

Esercizio1c

  Grammatica:

            S::= r A I S t I
            A::= a A | e
            I::= i I | e
 

·       a),b),c): verificate

·       calcolo first e follow

FIRST

rAIStI

{r}

FOLLOW

S

{t,$}

 

aA

{a}

 

A

{i,r}

 

e

{e}

 

I

{r,t,$}

 

iI

{i}

 

 

 

·       verifica delle proprieta':

first(aA) insectfollow(A) = {}
first(iI) insectfollow(I) = {}

·       costruzione tabella:


 

 

    r

     t

     a

     i

     $

    S

     0

       ---

       ---

       ---

         ---

    A

       2

       ---

        1

      2

         ---

    I

       4

      4

       ---

        3

       4

Esercizio2c

La grammatica non e' LL(K) per alcun K.
Dimostrazione.
    Sia K un arbitrario naturale non 0.
    Osserviamo
        S e' una sentenziale sinistra della grammatica
        S::=A ed S::=Bbb sono entrambe produzioni applicabili (in una d. sin.) a tale sentenziale:
                S => A
                S => Bbb
   Ma vediamo che:
                ak incluso in Firstk(A), infatti A =>* akB
                ak incluso in Firstk(Bbb), infatti Bbb =>* akakBbkbb
    Cio' conclude la dimostrazione.
 
 

Esercizio4c

L'analizzatore e' stato dato dal prof. Andrea Maggiolo, modificando un analizzatore nondeterministico ottenuto dalla grammatica ambigua seguente:

S::= a S'
S'::= a S' B | e
B::= b | e

l'analizzatore e' il seguente:
 

 

a

b

$

S

1

 ---

--- 

S'

2

3

---

B

---

4

5

L'analizzatore risulta possibile grazie al ruolo del simbolo speciale $. Possiamo ottenere analizzatori di questo tipo per il seguente linguaggio: {ai bj ch | 0 < i=j+h}? Qui abbiamo il simbolo 'c': un vero simbolo del linguaggio.
 
 

Esercizio5c

La grammatica non e' LL(K) per alcun K.
Dimostrazione.
    Sia K un arbitrario naturale non 0.
    Osserviamo
        S e' una sentenziale sinistra della grammatica
        S::=AbB ed S::=B sono entrambe produzioni applicabili (in una d. sin.) a tale sentenziale:
                S => AbB
                S => B
   Ma vediamo che:
                ck incluso in Firstk(AbB), infatti A =>* ckBbB
                ck incluso in Firstk(B), infatti B =>* ckB
    Cio' conclude la dimostrazione.
 

Esercizio10c

La grammatica non e' LL(K) per alcun K.
Dimostrazione.
    Sia K un arbitrario naturale non 0.
    Osserviamo
        S e' una sentenziale sinistra della grammatica
        S::=U ed S::=Vvv sono entrambe produzioni applicabili (in una d. sin.) a tale sentenziale:
                S => U
                S => Vvv
   Ma vediamo che:
                uk incluso in Firstk(U), infatti U =>* ukVvk-1
                uk incluso in Firstk(Vvv), infatti Vvv =>* ukVvk+2
    Cio' conclude la dimostrazione.
 
 
 

Esercizio14c
 

Essendo gia' stata dimostrata l'ambuita' della grammatica, possiamo concludere che la grammatica non e' LR(k) per alcun k.

Esercizio16c

La grammatica non e' SLR(K) per nessun k>=1. Dimostriamo intanto che non e' SLR(1). Infatti, calcoliamo la collezione LR(0) della grammatica aumentata:
 

I0 = Clos(S'->.S)

{S'->.S, S->.aA,
  S->.bBd}

Follow

 S

 {$}

 

 A

 {$}

 

 B

 {d,e}

 

 C

 {d}

 

I1 = G(0,S)

{S'->S.}

 

 

I2 = G(0,a)

{S->a.A, A->.Be, A->.Cd, B->.b, B->.,
C->.c, C->.}

 

conflitto r/r:
 {d,e} insect{d} = {d}

Il conflitto non si riduce utilizzando k>1


 

Esercizio2d

Possiamo operare in vari modi alternativi tra loro: 1) analiziamo il linguaggio e definiamo una grammatica LL che tenga conto delle osservazioni fatte, 2) cerchiamo una soluzione con trasformazioni conservative del linguaggio generato. Useremo 1).
Il linguaggio e':
                      L = {a2n+1 bn , a2n bn bb| n >= 0}

Le frasi hanno suffisso diverso secondo che il numero di a nel prefisso sia dispari o pari. Allora possiamo vedere tali frasi come costiuite dal solo bb oppure inizianti con ae seguite da frasi di un linguaggio L' = {a a2n+1 bn b, a a2n bn bb b, l| n >= 0}. Ma vediamo che vi e' stretta relazione tra le frasi di L ed L', ottenendo la grammatica seguente

                    S::= a S' | bb
                    S'::= a S b | e

E' facile vedere che la grammatica e' LL(1). E' altrettanto facile vedere che essa genera lo stesso linguaggio, peraltro il metodo indutivo con cui e' stata derivata fornisce anche una dimostrazione.

Usare il metodo 2) richiede maggiore accortezza e si basa essenzialmente sulla relazione che abbiamo tra produzioni ed equazioni tra linguaggi. Mostriamo come puo' operare un metodo basato su una trasformazione conservativa.
        Partiremo dalla grammatica ottenuta rimuovendo la mutua ricorsione.

            S::= A | Bbb
            A::= aB
            B::= aaBb | e

        Rimpiaziamo A ed eliminiamo i non terminali diventati inutili:

            S::= aB | Bbb
            B::= aaBb | e

            Fattoriziamo e operiamo l'introduzione di un nuovo linguaggio con S':
 

            S::= a (B | aBb bb) | bb
            B::= aaBb | e
 

            S::= a S' | bb
            S'::=(B | aBb bb)
            B::= aaBb | e
 

        Rimpiaziamo B in S', e fattoriziamo:

            S::= a S' | bb
            S'::= aaBb | aBb bb | e
            B::= aaBb | e
 
 

            S::= a S' | bb
            S'::= a(aB | Bb b)b | e
            B::= aaBb | e

Rimpiaziamo in S' la sottoespressione aB | Bb b con il non terminale S a cui essa corrisponde vedi produzione S::=aB | Bb b occorrente nella seconda delle grammatiche equivalenti prodotte dalle nostre trasformazioni (che hanno sempre mantenuto il significato dei vari simboli)

            S::= a S' | bb
            S'::= a S b | e
            B::= aaBb | e

        Eliminiamo i terminali diventati inutili:
 

            S::= a S' | bb
            S'::= a S b | e

Abbiamo ottenuto la stessa grammatica LL(1).
 

Esercizio5d

Il linguaggio e' LL(K) per ogni K>=1.
Dimostrazione.

Rimpiaziamo ogni occorrenza di B, nella grammatica, con il non terminale A. Cio' conduce alla grammatica:

S::=AbA | A
A::=cA | a
B::=A

ma B non contribuisce a definire il linguaggio L(S) della grammatica che pertanto puo essere ridotta a:

S::=AbA | A
A::=cA | a

e fattorizzata:

S::=A S'
S'::= bA | e
A::=cA | a

Questa grammatica e' equivalente a quella data ed e' LL(1), infatti:
                    first(bA)insectfollow(S')={b}insect{$}={}

Questo conclude la dimostrazione.
 

Esercizio14d
 

Possiamo rimuovere la produzione A::=cc dalla grammatica senza che il linguaggio L(S) risulti modificato: Dimostrazione di cio' e' che tale rimozione conduce a rimpiazzare nella definizione di L(A) l'espressione su insiemi {cc}U{xn cc y2n| n >= 0} con la seguente espressione {xn cc y2n| n >= 0}. Ma le due espressioni definiscono lo stesso insieme.
Possiamo ora mostrare che la grammatica cosi' ottenuta:

S ::= zSzB | A
A ::= xAxx | C
B ::= xBy | c
C ::= xCyy | cc

(e' non ambigua) ammette analizzatore LR. Allo scopo costruiamo la collezione SLR della grammatica aumentata:
 

I0 = Clos(S'->.S)

{S'->.S, S->.zSzB, S->.A, A->.xAxx, A->.C, C->.xCyy, C->.cc}

Follow

 S

 {$,z}

 

 A

 {$,z,x}

 

 B

 {$,z,y}

 

 C

 {$,z,x,y}

 

I1 = G(0,S)

{S'->S.}

 

 

I2 = G(0,z)

{S->z.SzB, S->.zSzB, S->.A, A->.xAxx, A->.C, C->.xCyy, C->.cc}

 

 

I3 = G(0,A)

{S->A.}

 

 

I4 = G(0,x) = G(4,x)

{A->x.Axx, C->x.Cyy, A->.xAxx, A->.C, C->.xCyy, C->.cc}

 

 

I5 = G(0,C)

{A->C.}

 

 

I6 = G(0,c) = G(4,c)

{C->c.c}

 

 

I7 = G(4,A)

{A->xA.xx}

 

 

I8 = G(4,C)

{C->xC.yy, A->C.}

 

nessun conflitto:
 {y} insect {$,z,x} = {}

I9 = G(6,c)

{C->cc.}

 

 

I10 = G(7,x)

{A->xAx.x}

 

 

I11 = G(8,y)

{C->xCy.y}

 

 

I12 = G(10,x)

{A->xAxx.}

 

 

I13 = G(10,x)

{C->xCyy.}

 

 

La collezione contiene stati con conflitti. Possiamo calcolare la tabella di parsing SLR.

Esercizio16d

La grammatica e' LALR(K) per k>=1. Dimostriamo che e' LALR(1). Infatti, calcoliamo la collezione LR(1) della grammatica aumentata ed accorpiamo stati diversi che abbiano stesso kernel:
 

I0 = Clos(S'->.S/$)

{S'->.S/$, S->.aA/$,
  S->.bBd/$}

 

I1 = G(0,S)

{S'->S./$}

 

I2 = G(0,a)

{S->a.A/$, A->.Be/$,    A->.Cd/$, B->.b/e, B->./e,
C->.c/d, C->./d}

nessun coflitto:

I3 = G(0,b)

{S->b.Bd/$, B->.b/d, B->./d}

nessun conflitto

I4 = G(2,A)

{S->aA./$}

 

I5 = G(2,B)

{A->B.e/$}

 

I6 = G(2,C)

{A->C.d/$}

 

I7 = G(2,b) = G(3,b)

{B->b./e/d}

 

I8 = G(2,c)

{C->c./d}

 

I9 = G(3,B)

{S->bB.d/$}

 

I10 = G(5,e)

{A->Be./$}

 

I11 = G(6,d)

{A->Cd./$}

 

I12 = G(9,d)

{S->bBd./$}

 

Definiamo ora, la relativa tabella di analisi (produzioni numerate da 0, produzione S'::=S, a 8):
 

ACTION

a

b

c

d

e

$

GOTO

S

A

B

C

I0

S/2

S/3

---

---

---

---

---

I1

---

---

---

I1

---

---

---

---

---

accept

---

---

---

---

---

I2

---

S/7

S/8

R/8

R/6

---

---

---

 I4

I5

I6

I3

---

S/7

---

R/6

---

---

---

---

---

I9

---

I4

---

---

---

---

---

R/1

---

---

---

---

---

I5

---

---

---

---

S/10

---

---

---

---

---

---

I6

---

---

---

S/11

---

---

---

---

---

---

---

I7

---

---

---

R/5

R/5

---

---

---

---

---

---

I8

---

---

---

R/7

---

---

---

---

---

---

---

I9

---

---

---

S/12

---

---

---

---

---

---

---

I10

---

---

---

---

---

R/3

---

---

---

---

---

I11

---

---

---

---

---

R/4

---

---

---

---

---

I12

---

---

---

---

---

R/2

---

---

---

---

---


 
 

Esercizio16e

Le inclusioni SLR < LALR < LR  ed anche LL < LR e il fatto che la grammatica abbia un riconoscitore LALR (ovvero abbia un riconoscitore LL) forniscono gia' una dimostrazione del fatto che il linguaggio L(G) e' LR. Inoltre la tabella di analisi LALR e' gia una tabella LR.
Tuttavia come esercizio ulteriore mostriamo la tabella ottenuta per una analisi LR canonica. La tabella differisce dalla LALR per la presenza di uno stato in piu', che abbiamo indicato con I7bis e per la definizione degli stati I7 e I7bis.
 

I0 = Clos(S'->.S/$)

{S'->.S/$, S->.aA/$,
  S->.bBd/$}

 

I1 = G(0,S)

{S'->S./$}

 

I2 = G(0,a)

{S->a.A/$, A->.Be/$,    A->.Cd/$, B->.b/e, B->./e,
C->.c/d, C->./d}

nessun coflitto:

I3 = G(0,b)

{S->b.Bd/$, B->.b/d, B->./d}

nessun conflitto

I4 = G(2,A)

{S->aA./$}

 

I5 = G(2,B)

{A->B.e/$}

 

I6 = G(2,C)

{A->C.d/$}

 

I7 = G(2,b) 

{B->b./e}

 

I8bis = G(2,c)

{C->c./d}

 

I9bis = G(3,B)

{S->bB.d/$}

 

I7bis = G(3,b) 

{B->b./d}

 

I10bis = G(5,e)

{A->Be./$}

 

I11bis = G(6,d)

{A->Cd./$}

 

I12bis = G(9bis,d)

{S->bBd./$}

 


 
 
 

[ Home | Back ]