Hvad er en grammatik?

En grammatik er bestemmende for syntaksen i et sprog. Syntaksen kan bestemmes top-down, idet man siger hvordan hvert enkelt komponent er konstrueret ud fra simplere komponenter. Således er fx en ID bygget op af bogstaver, cifre og underscores, og skal starte med et bogstav. Dette kunne medføre en delmængde af en grammatik, der så således ud:

ID    -> bogstav tegn
tegn  -> bogstav tegn
         | ciffer tegn
         | ’_’ tegn
         | e
Tegnet e kaldes epsilon, og betyder i ovenstående at et tegn kan være tomt. Det vil med andre ord sige, at en ID kan nøjes med at være et bogstav, eftersom der først kommer et bogstav og derefter komponenten tegn, der kan være epsilon. tegn er rekursivt, eftersom det kan ’kalde’ sig selv.

Grammatikken bestemmer om rækkefølgen af komponenter i et sprog er lovlige vha. derivation. I hvert skridt af en derivation, sker der en udskiftning, der bygger på et valg i grammatikken. Et element der ikke kan brydes yderligere ned (eller deriveres), kaldes en terminal. Alle andre elementer kaldes non-terminaler.

Grammatikken benyttes af compileren, eftersom det der kompileres gerne skulle stemme overens med sprogets grammatik. En given compiler er derfor nærmest opbygget omkring grammatikken.

Nedenfor har vi vist grammatikken for Svendsk. I stedet for tegnet e har vi indsat den ækvivalente kommentar /* epsilon */. For overskuelighedens skyld, har vi skrevet alle terminaler med store bogstaver, og non-terminaler med små.

svendsk_program : SVENDSK ID
                  variabel_liste
                  FELT_START
                  variabel_liste saetnings_liste
                  FELT_STOP
                ;

variabel_liste  : variabel variabel_liste
                | /* epsilon */
                ;

variabel        : VAR_ERKLAER
                ;

saetnings_liste : saetning saetnings_liste
                | /* epsilon */
                ;

saetning        : ID '=' udtryk
                | variabel
                | HVIS '(' udtryk ')' saetning ellers_del
                | loop_tal '{' saetnings_liste '}' loop_type
                | FELT_START saetnings_liste FELT_STOP
                | AFBRYD
                | NYLINIE
                | TABULATOR
                | SKRIV '(' skriv_indhliste ')'
                | LAES '(' ID ')'
                ;

ellers_del      : ELLERS saetning
                | /* epsilon */
                ;

loop_tal        : TAL
                | ID
                ;

loop_type       : '+'
                | '-'
                | TAL loop_plus_minus
                | ID loop_plus_minus
                ;

loop_plus_minus : '+'
                | '-'
                ;

skriv_indhliste : skriv_indh skriv_indhliste
                | /* epsilon */
                ;

skriv_indh      : '[' udtryk ']'
                | LOVLIG_TEKST
                ;

udtryk          : udtryk '+' udtryk
                | udtryk '-' udtryk
                | udtryk '*' udtryk
                | udtryk '/' udtryk
                | '-' udtryk
                | '(' udtryk ')'
                | udtryk '<' udtryk
                | udtryk '>' udtryk
                | udtryk '=' udtryk
                | udtryk IKKELIG udtryk
                | udtryk STOERRELIG udtryk
                | udtryk MINDRELIG udtryk
                | udtryk OG udtryk
                | udtryk ELLER udtryk
                | IKKE '(' udtryk ')'
                | SAND
                | FALSK
                | ID
                | TAL
                | ITERATION
                ;