Syntaktisk analyse

I den leksikalske analyse, scannede vi source-koden igennem, og fandt de forskellige tokens. Det næste skridt, er at finde ud af om de giver mening. Det kan gøres på to måder: Man kan få den leksikalske analyse til at generere en fil (symbol-tabel), med alle de tokens der forekommer i programmet. Udfra denne fil, udfører man så den syntaktiske analyse. Den anden metode går ud på, at man udfører den leksikalske og den syntaktiske analyse sideløbende. Det er denne metode FLEX og BISON benytter sig af. Hver gang den leksikalske analyse finder et token, giver den det videre til den syntaktiske, ét token af gangen.

Når man parser, opbygger man noget, der hedder et parse-træ. Dette træ repræsenterer et stykke kode, skrevet inden for en given grammatik. Bladene i et parse-træ er terminaler, og over dem ligger der non-terminaler. Jo højere man går op i træet, jo længere væk abstraherer man fra terminalerne. Når man går fra bunden af parse-træet til toppen, reducerer man. Omvendt deriverer man, når man går fra toppen af parse-træet og nedad. En derivation er med andre ord de terminaler og non-terminaler, en non-terminal kan afledes til.

Det der står længst til venstre i parse-træet, svarer til det der står længst til venstre i grammatikkens derivation, og omvendt er det der i træet står længst til højre ækvivalent med det der står længst til højre i grammatikkens derivation. Dette afføder mulighed for, at bestemme hvilken vej man skal læse derivationen, nemlig leftmost eller rightmost. Som navnene siger, opløser leftmost derivationen fra venstre mod højre, mens rightmost omvendt opløser derivationen fra højre mod venstre. (Se side 39-40 i J. P. Bennetts bog).

Der findes to generelle måder at parse på, nemlig Top-down- og Bottom-up-parsing. Disse to teknikker er (som navnene svagt antyder) diametrale modsætninger.

Top-down-parsing

Med denne teknik starter man øverst i parse-træet, og udarbejder derfra den rigtige struktur, der passer til koden. Ud fra grammatikken forsøger man at udlede det kode, man kompilerer. Hvis det kan lade sig gøre, er koden korrekt i forhold til grammatikken.

Eksempel:

Grammatik:

  S -> TUd
  T -> a
  U -> b

Parsetræ:

  S  ->  S  ->  S
 /|\    /|\    /|\
T U d  T U d  T U d
       |      | |
       a      a b

  S -> abd

Bottom-up-parsing

I modsætning til top-down parsing, starter man her fra bunden, og reducerer de forskellige terminaler til non-terminaler indtil man er kommet helt igennem parse-træet.

Eksempel:

  S -> TUd
  T -> a
  U -> b

Parsetræ:

                       S
                      /|\  
       T      TU     T U |
       |      ||     | | |
abd -> abd -> abd -> a b d

  S -> abd

For både Top-down- og Bottom-up-parsing gælder der en række Design-kriterier:

Tiden spiller selvfølgelig ind. Den tid det tager at parse, skal være proportional med den mængde kode der parses.

Det skal være muligt at generere parse-træet ud fra et på forhånd defineret størrelse Lookahead, der altså ikke må være vilkårlig. (Se mere om lookahead senere i dokumentet)

Backtracking (muligheden for at fortryde semantiske aktioner) skal undgås. Dette bruges, hvis man har lavet en tvetydig grammatik, og den første mulighed ikke var rigtig. Backtracking bruges sjældent, eftersom det er tidskrævende at bruge, da det skal forsøge sig meget frem. Derudover kan det være besværligt at implementere.

Der findes eksempler på top-down-parsere og bottom-up-parsere, der kan opfattes som en slags familie af parsere. Her tænker vi på Predictive Recursive Descent og Shift-Reduce parsere. De første er top-down baseret, mens de andre er baseret på bottom-up.

Klassificering

Der findes tre parametre der er kendetegnende for, hvilken type parser man har med at gøre:

Den retning, hvorved man læser source-programmet fra. Hvis man læser fra venstre er det L og fra højre R. Der vil næsten altid læses fra venstre mod højre (L), da det er det mest logiske. De fleste filer er i øvrigt nemmest at læse fra venstre (dvs fra starten).

Type af derivation, dvs. hvilken side af parse-træet eller grammatikken der først behandles. (leftmost eller rightmost)

Hvor mange tokens man skal kunne læse frem, når man står ved et token, for at generere parse-træet. Dette begreb kaldes for lookahead.

Dette er der lavet en notationsform for, hvor man skriver retningen, derivationen og til sidst lookahead i parenteser.

Parseren LR(1) er således en parser der læser sourcen fra venstre mod højre (L’et), benytter rightmost derivation (R’et), og højst kræver et token lookahead under parsing (1-tallet). Dette (LR(k)) er en parser, af den før omtalte Shift-Reduce type.

Figur 6-3: LR shift-reduce parser

Der findes ydermere tre meget brugte forskellige typer inden for denne familie (hvis man ser bort fra størrelsen på lookahead):

Parse-type	Forkortelse
Canoncial LR(k)	LR(k)
Lookahead LR(k)	LALR(k)
Simple LR(k)	SLR(k)

LR(k) er den mest komplicerede af disse tre, dvs. har de største tabeller, mens SLR(k) er den mest simple. Den mellemliggende LALR(k) er velegnet til de fleste sprog, da dens tabeller tager højde for de mest almindelige konstruktioner.

BISON benytter i øvrigt Lookahead LR(k), med et token lookahead (LALR(1)), og det er faktisk også det, den genererer til compileren.

Med hensyn til BISON, stødte vi ind i en del besværligheder, da vi ikke kendte til dens spidsfindigheder. Som eksempel kan nævnes, at hvis man starter med en C-linie (dvs. en linie omgivet af { og }) i definitionen af en non-terminal, får sætningen automatisk en lavere prioritering. Se nedenstående for eksemplificering:

 saetning        : {printf("(tildeling)\n");} ID '=' udtryk
                 | ID '(' udtryk ')'
                 | VAR_ERKLAER
                 ;

Eksempel 6-1: Uddrag af tidlig version af saetning-grammatik

Dette er ikke noget problem i sig selv, da C-linien i eksemplet ikke har nogen betydning. Det er bare sådan en regel, der gør det besværligt at finde fejl, da det ikke er videre logisk og ikke bliver beskrevet i vores bog.