Λεκτική Ανάλυση

Δουλειά του λεκτικού αναλυτή είναι να διαβάζει ένα -ένα τους χαρακτήρες του προγράμματος και να τους μετατρέπει σε tokens( to Keywords identifiers, constants). Για να αναγνωριστεί ένα token πολλές φορές χρειάζεται ο λεκτικός αναλυτής, να διαβάσει αρκετούς χαρακτήρες μέχρι να το αναγνωρίσει και να το κάνει αποδεκτό.
Η όλη αυτή διαδικασία, δηλαδή η ανάγνωση των tokens μέχρι την αναγνώριση και αποδοχή τους την παριστάνουμε με τα διαγράμματα Μετάβασης Καταστάσεων.
Σε αυτά υπάρχει μια αρχική κατάσταση όπου συνδέετε με άλλη με βέλη που μας δείχνουν την ακολουθία αναγνώρισης του token και μια τελική κατάσταση. Συνήθως πάνω στα βέλη αναγράφουμε τις εισόδους των καταστάσεων. Με άλλα λόγια η λειτουργία του λεκτικού αναλυτή προσομοιώνεται με την λειτουργία ενός πεπερασμένου αυτόματου που δέχεται στην είσοδο μια έκφραση, δηλαδή ένα πεπερασμένο σύνολο από σύμβολα ή χαρακτήρες και αποφασίζει στο τέλος αν αποδέχεται ή όχι την είσοδο.
Κάθε κανονική έκφραση είναι εκείνη που κατασκευάζεται και προφανώς υποδηλώνει μια κανονική γλώσσα. Ακολουθούν οι κανόνες κατασκευής τόσο των κανονικών εκφράσεων όσο και των κανονικών γλωσσών.

1. Η ε είναι μια κανονική έκφραση που υποδηλώνει την γλώσσα {ε} που περιέχει την κενή συμβολοσειρά.

2. Για κάθε α ανήκει Σ το α υποδηλώνει τη γλώσσα {α} με μια μόνο συμβολοσειρά.

3. Αν G, F είναι δύο κανονικές εκφράσεις που δηλώνουν τις γλώσσες LG και LF αντίστοιχα τότε
  • G | F είναι κανονική έκφραση που υποδηλώνει την γλώσσα LG U LF 
  • GxF είναι κανονική έκφραση που υποδηλώνει την γλώσσα LG • LF
  • G* είναι κανονική έκφραση που υποδηλώνει την γλώσσα LG* 

Παράδειγμα 

Έστω L={ x ανήκει {0,1} * | η x έχει ζυγό αριθμό 0} δηλώνει ότι μια συμβολοσειρά της θα περιέχει: 
1. την κενή συμβολοσειρά 
2. ή θα ξεκινά με ένα ή κανένα 1
3. και ακολουθεί η μορφή 01…10 με ένα πλήθος άσσων μεταξύ των δύο μηδενικών. 

Κανονική έκφραση αυτής είναι S=(1* +01* 0)*
Μερικές συμβολοσειρές που αναγνωρίζονται από το αυτόματο θα είναι :
1. 00
2. 010
3. 0110
4. 1010
........
Αναπαράσταση με αυτόματο  

S : αρχική κατάσταση 
Ε: τελική κατάσταση, αποδοχή
Όταν εμφανιστεί 1 παραμένει στην αρχική κατάσταση ενώ με μηδέν προχωρά στην κατάσταση Α. 
Στην κατάσταση Α αν εμφανιστεί άσσος παραμένει ενώ με μηδέν προχωρά στην κατάσταση Ε όπου είναι η τελική. Αν είναι και το τέλος της συμβολοσειράς τότε  την αποδέχεται και τερματίζει. 
Αν όμως ακολουθεί άσσος μένει στην ίδια κατάσταση και τερματίζει ή αν ακολουθήσει μηδέν (περιττός αριθμός από 0) επιστρέφει στην κατάσταση Α, ώστε αν δεχτεί ξανά  μηδέν και είναι το τελευταίο σύμβολο (άρτιος αριθμός 0) μεταβαίνει στην κατάσταση Ε και τερματίζει.