Γραμματική

Τη σύνταξη των γλωσσών την ορίζουμε με γραμματικές.

Μια γραμματική ορίζεται από την τετράδα: G = (V_N, V_T, P, S):

V_N: αλφάβητο με τα μη τερματικά σύμβολα (non-terminal symbols).
V_T: αλφάβητο με τα τερματικά σύμβολα (terminal symbols).
P: συντακτικοί κανόνες (syntax rules) που αποτελούνται από ζευγάρια (α, β) που συμβολίζονται α -> β. Το α αποτελείται από ένα σύμβολο ενώ το β από μια ακολουθία συμβόλων.
S: Το αρχικό μη τερματικό σύμβολο εκκίνησης.

Από μια γραμματική μπορούμε να παράξουμε συμβολοσειρές αρχίζοντας από το σύμβολο εκκίνισης με διαδοχικές εφαρμογές των συντακτικών κανόνων. Κάθε εφαρμογή αντικαθιστά ένα σύμβολο που βρίσκεται στα αριστερά ενός συντακτικού κανόνα με τα αντίστοιχα σύμβολα που βρίσκονται δεξιά. Με τον τρόπο αυτό μπορούμε να καταλήξουμε σε μια συμβολοσειρά από τερματικά σύμβολα. Η συμβολοσειρά αυτή ανήκει στη γλώσσα που ορίζεται από την αντίστοιχη γραμματική. Η διαδικασία δημιουργίας της συμβολοσειράς από τη γραμματική ονομάζεται παραγωγή (derivation).

Παράδειγμα

G = (V_N, V_T, P, S):

V_N

{SUM, PROD, NUM}

V_T

{0, 1, +, *}

P

{

NUM ->1,
NUM ->0,
SUM -> SUM + PROD
SUM -> PROD
PROD -> PROD * NUM
PROD -> NUM

}

S

SUM