Οι γραμματικές που ικανοποιούν τις απαιτήσεις ώστε να είναι κατάλληλες για την υλοποίηση ενός αναλυτή Αναδρομικής Κατάβασης ανήκουν στην κατηγορία LL1.

Για να εξετάσουμε αν μια γραμματική είναι LL1 θα πρέπει πρώτα να την έχουμε καταστήσει κατάλληλη για Αναδρομική Κατάβαση με τις τεχνικές που αναπτύξαμε προηγουμένως.



Στην συνέχεια θα πρέπει να φτιάξουμε το πίνακα ανίχνευσης της LL1. Αυτό γίνεται εφικτό χρησιμοποιώντας δύο αλγόριθμους υπολογισμού των συνόλων First και Follow για τα μη τερματικά σύμβολα της γραμματικής.

Ο υπολογισμός των first



Ο υπολογισμός των follow

Ο υπολογισμός του Πίνακα Ανίχνευσης 

Θα δώσουμε και ένα αναλυτικό παράδειγμα υπολογισμού
Έστω η γραμματική
S --> xS | ErS | By
B --> CCE | ε
C --> zS |  w    
E-->qS | ε
Α. Να υπολογίσετε τα σύνολα First και Follow για τα μη τερματικά σύμβολα της γραμματικής (S, B, C, E).
Β. Να υπολογίσετε τον LL(1) πίνακα ανίχνευσης για τη δοθείσα γραμματική

Απάντηση
Υπολογισμός των First
Από S--> xS | ErS | By θα είναι
First(S)=First(xS)UFirst(ErS)U First(By)  (1)
Θα είναι First(xS) = First(x)-{ε}= {x}-{ε}  = {x}   (2)
Είναι First (ErS)= First(E)-{ε} È First(rS)-{ε}= First(E)-{ε} U First(r)-{ε} = First(E)-{ε} U{r}      (3)
Ακόμα είναι First(By)= First(B)-{ε} U First(y)-{ε}= First(B)-{ε}U{y} (4)
Από B--> CCE | ε  θα είναι
First (B)= First (CCE) UFirst(ε)= First (CCE) U {ε}   (5)
Είναι First (CCE)= First (C ) –{ε}  (6)μη απαλείψιμο
Από C--> zS |  w  θα είναι
First (C ) = First(zS) U First(w)= First(zS) U First(w)-{ε}= First(zS) U {w}-{ε}= First(zS) U {w}   
Είναι First(zS)= First(z)-{ε}= {z}-{ε}={z}    άρα γίνεται  First (C )={z}U{w} ={z,w}    (7) 
Από E --> qS | ε θα είναι
First(Ε)= First(qS) U First(ε) = First(qS) U{ε}
Είναι First(qS)= First(q)-{ε}={q}- {ε}={q}  άρα γίνεται First(Ε)={ q}U{ε}={q,ε}   (8)
Οπότε η (6) από (7) γίνεται First (CCE)= {z,w} (9)
Συνεπώς η (5) από την (9) γίνεται First (B)= {z,w,}U{ε}= {z,w,ε}    (10)
Ακόμα η (4) από (10) γίνεται First(By)={z,w,ε} -{ε}U{y}= {z,w,y}   (11)  
και η (3) από την(8) γίνεται  First (ErS)=  {q,ε}   -{ε} U{r} ={q,r}   (12)
Άρα η (1) από τις (2), (12), (11) είναι First(S)={x} U{q,r}  U{z,w,y} = {x,q,r,z,w,y}

Υπολογισμός των Follow
Follow (S)={$} U Follow(S) U Follow(C) U Follow(E) (1’ )
Θα είναι Follow (B) =  {y}
Ακόμα  Follow(C) = (First(CE)-{ε})U (First(E) –{ε} )={z,w,q}   (2’)
Επίσης  Follow (E)= (First(rS)-{ε})U Follow (Β)={r}U  {y}={r,y}  (3’)
Συνεπώς η (1’) γίνεται από (2’), (3’)  Follow (S)={$}U {z,w,q}  U {r}  = {$,z,w,q,r,y}
Ένας συγκεντρωτικός πίνακας με τις τιμές First και Follow θα είναι ο παρακάτω

FIRST
FOLLOW
S
{x,q,r,z,w,y}
{$,z,w,q,r,y}
Β
{z,w,ε}   
{y}
C
{z,w}   
{z,w,q}  
E
{q,ε}  
{r,y}  


Β. Να υπολογίσετε τον LL(1) πίνακα ανίχνευσης για τη δοθείσα γραμματική

Απάντηση
Από τον κανόνα S à xS | ErS | By θα είναι
S-->xS  είναι First(xS)={x}
S -->ErS είναι First (ErS)= {q,r}  
S--> By είναι First(By)={z,w,y}
Από τον κανόνα B --> CCE | ε  θα έχω
B --> CCE είναι First (CCE)= {z,w}
B --> ε είναι First(ε)={ε} οπότε Follow(B)={y}
Από τον κανόνα C-->zS|w θα είναι
C-->zS είναι First(zS)={z}
C-->w είναι First(w)={w}
Από τον κανόνα E --> qS | ε θα είναι
E--> qS είναι First(qS)={q}
E -->ε είναι First(ε)={ε} οπότε Follow(E) ={r,y}




Συνεπώς θα έχω τον πίνακα

FIRST
FOLLOW
x
y
z
w
r
q
$
S
{x,q,r,z,w,y}
{$,z,w,q,r,y}
S --> xS 
S-->By
S-->By
S-->By
S-->ErS
S-->ErS

Β
{z,w,ε}   
{y}

B--> ε
B--> CCE
B-->CCE



C
{z,w}   
{z,w,q}  


C-->zS
C-->w



E
{q,ε}  
{r,y}  

E--> ε


E-->ε
E--> qS


Παρατηρούμε ότι δεν έχουμε συγκρούσεις οπότε η γραμματική είναι LL1