Τα προβλήματα που συναντάμε στην Top down ανίχνευση μιας γραμματικής και πρέπει να ξεπεράσουμε για να είναι κατάλληλη για Αναδρομική Κατάβαση, είναι τρία.

1. Να μην έχει αριστερές αναδρομές άμεση ή έμμεση στους κανόνες. 

2. Να μην έχει κοινό αριστερό πρόθεμα στους κανόνες. 

3. Από τα ν εναλλακτικά μέρη ενός κανόνα τα ν-1 θα πρέπει να ξεκινάνε με τερματικά.

Έστω η γραμματική με τα μη τερματικά σύμβολα {S, A, B}, τα τερματικά σύμβολα {a, b, c, d,f} και αρχή το σύμβολο S:

Μετασχηματίστε τη δοθείσα γραμματική ώστε να είναι κατάλληλη για συντακτική ανάλυση recursive – descent (προβλέπουσα αναδρομική κατάβαση).

Απάντηση

Από τον κανόνα 1 (S       -->          S a) παρατηρούμε αριστερή αναδρομή , ενώ από τους κανόνες 2,3(Α   -->          b Sd και Β  -->    b dB) παρατηρούμε έμμεσο κοινό πρόθεμα. Θα είναι:

Για τον κανόνα  1 εφαρμόζω απαλοιφή της αριστερής αναδρομής έτσι γίνεται

S            -->         Sa           |              cA           |              f

•             S            -->           cAS’       |              fS’   και

•             S’           -->          aS’|        ε

Για τους κανόνες 2,3 θα προχωρήσω σε αντικατάσταση του Β στον Α --> bSd      |              Β a

από τον Β-->    bdB        |              dB           |              S  θα είναι

Α à       b Sd       |              b dBa     |              dBa        |              Sa           κοινό πρόθεμα το b 

προχωρώ στην απαλοιφή του κοινού προθέματος και θα είναι

Α-->      bΑ΄         |              dBa        |              Sa

Α΄--> Sd                |              dBa       

 Έτσι οι νέοι κανόνες που προκύπτουν είναι

S-->cAS’|fS’   

S’--> aS’|ε

Α΄-->Sd |dBa    

Α -->bΑ΄|dBa|Sa