Gramatikk

Denne artikkelen vil gå kort igjennom gramatikk (eng: grammar), notasjon og bruksområder. Vi vil og prøve å definere en egen minigramatikk. For noen kan dette virke litt abstrakt, men gramatikk og parsing er veldig grunnleggende i alle typer språk, både naturlige og konstruerte.

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.

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.

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".

"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...