Definisjonen av en kontekst fri gramatikk

En kontekst fri gramatikk (eng: context-free grammar) består av fire komponenter.

1: Et sett med tokens eller terminaler. Dette er atomiske symboler i språket.

2: Et sett med ikkje-terminaler. Dette er variabler som representerer konstruksjoner i språket.

3: Et sett med regler, produksjoner, for å bestemme komponentene i konstruksjonene. Hver produksjon har en ikkje-terminal på sin venstre side, symbolet ::=, og en string av terminaler / ikkje-terminaler på sin høyre side.

4: En ikkje-terminal som er den grunnleggende ikkje-terminalen. Dette er hovedkonstruksjonen i språket.

Såfremt ikke annet er sagt vil produksjonen av den grunnleggende ikkje-terminalen komme først.

BNF (Backus Naur Form)

En vanlig notasjon for gramatikker. Vises v.h.a eksempel.

BNF gramatikk for reelle tall. <real-number> ::= <integer-part> . <fraction> <integer-part> ::= <digit> | <integer-part> <digit> <fraction> ::= <digit> | <digit> <fraction> <digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Linjen "<integer-part> ::= <digit> | <integer-part> <digit>", kan leses slik: "Et heiltall kan være et nummer, eller et heiltall etterfulgt av et nummer"

Eksempel: 3.14, vi viser første regelen i bruk.

<real-number>	<integer-part>	.	fraction
3.14
	3	.	14

Eksempelet kan følges videre for de resterende elementene "heltallet 3" og "desimaltallet .14", Tilslutt vil vi ha kommet helt ned til <digit> som er de atomiske verdiene i denne gramatikken. Vi er da ferdige.

Vi kan og bruke <empty> for å indikere den tomme strengen. Dette kan være nyttig for tilfeller der gramatikken tillater valg. F.eks ".5" og "0.5".

<real> ::= <integer-part> . <fractional-part> <integer-part> ::= <empty> | <digit-sequence> <fractional-part> ::= <digit-sequence>

"Et reelt tall har en heitlalls del, et desimal tegn, og en desimaltalls del. Heiltallsdelen er en valgfri tallsekvens, desimaltallsdelen er en tallsekvens.

Parse trær

Produksjonene i en gramatikk er regler for hvordan man skal bygge opp strenger med token. Et parse tre viser hvordan disse strengene kan bygges. Et parsetre for en gitt gramatikk må oppfylle følgende:

1: Hvert blad må være en terminal, eller <empty>.

2: Kvar node som ikke er et blad må bære en ikkje-terminal.

3: Ei node, som ikke er et blad, er venstre siden av en produksjon. Barna til denne noden, fra venstre til høyre, er høyre siden av produksjonen.

4: Rotnoden er den grunnleggende ikkje-terminalen.

En streng tilhører en gramatikk dersom, og kun dersom, den e generert av et parsetre. Det å lage parsetrær kalles parsering. Dersom vi har mer en et parsetre for en gitt streng i en gramatikk har vi en såkallt "ambigious grammar".

Fortsettes...