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