Beskrivelse af BISON

At lave en compiler helt fra bunden er en større opgave og temmelig besværlig. Heldigvis findes der hjælpeværktøjer, som ud fra en given grammatik og associerede semantiske aktioner (dvs. en attributgrammatik), kan hjælpe med at lave en parser og generere de tabeller den skal bruge. Parseren er selve analysedelen i en compiler, da den gennemløber koden, og checker om den er korrekt, ud fra grammatikken. En compiler består både af en parser og en kodegenerator (så det kan blive oversat). De forskellige dele af en compiler forklares yderligere senere.

De hjælpeværktøjer man kan bruge til at lave en parser og de tilhørende tabeller kaldes parser generatorer eller compiler compilere. Den parser som de genererer får som input et program i source language, eller en strøm af tokens fra en leksikalsk analysator (genereres seperat i et andet hjælpe-program).

Et af de mest brugte programmer inden for dette område er YACC (Yet Another Compiler Compiler), som er let tilgængeligt under UNIX. Vi har dog valgt at bruge BISON, som er en ikke-kommerciel version af YACC. BISON har bl.a. den fordel, at den kan køre på en almindelig PC. Vi vil i det efterfølgende referere til BISON, selvom de fleste kilder det følgende er bygget på, omhandler YACC.

BISON

BISON bruges til at lave en shift-reduce parser og de tilhørende LALR(1) parser-tabeller udfra et programmeringssprogs grammatik.

En shift-reduce parser gennemløber koden, ved at læse tokens et efter et. Den består af en generel parser (skrevet i C), og benytter en stak med tilstande (eller states), samt to tabeller (Action- og Goto-tabellen). Tabellerne er specifikke i forhold til sproget som skal parses (i dette tilfælde Svendsk). Tabellerne genereres af parser-generatoren ud fra sprogets grammatik.

Action-tabellen
Bestemmer ud fra den øverste state på stakken og det næste input-token, om der skal skiftes, reduceres, accepteres eller sættes flag for error.

Goto-tabellen
Hvis der skiftes (shift) eller reduceres (reduce), bestemmer denne tabel hvilken status der skal på stakken.

For yderligere dybdegående oplysninger, se Compiling Techniques s. 97-101.

Som før sagt får BISON som input en strøm af tokens fra en leksikalsk analysator. Denne analysator genereres af FLEX (eller LEX, hvis det skulle have modsvaret YACC).

En af BISONs stærke sider er muligheden for at skabe præcedens for operatorer, hvilket eliminerer de værste risici for at lave en tvetydig grammatik.

En tvetydig grammatik er især et problem med aritmetiske udtryk:

1+2*5 => (1+2)*5 = 15 // uden præcedens

%left ELLER
%left OG
%left SAMMENLIGN IKKELIG
%left '<' '>' MINDRELIG STOERRELIG
%left '+' '-'
%left '*' '/'
%right UMINUS IKKE

Ovenstående sætninger gør, at udtrykket bliver opfattet korrekt, dvs som:

1+2*5 => 1+(2*5) = 11 // med præcedens

Syntaks for BISON

Et BISON-program er delt op i tre generelle dele, nemlig deklarationer, regler og support-rutiner. Denne logiske opdeling er næsten identisk med den man finder i FLEX.

Et BISON programs generelle form:

Deklarationer
%%
Regler
%%
Support rutiner

Deklarationer:
Erklæring af tokens brugt af grammatikken. Det omfatter tokens på en karakter og tokens på flere karakterer (returneret af FLEX). Disse tokens får hver deres nummer startende fra 257. Numre fra 0 til 255 repræsenterer ASCII-tegnene, og 256 bruges som fejl-token.

I deklarations-afsnittet erklæres også præcedens- og associationsregler, dvs. hvilke tokens binder stærkest, og til hvilken side de binder. Fx har vi allerede været inde på, at * og / binder stærkere end + og -. Alle disse tokens binder til venstre, men et token som ikke (boolsk, ækvivalent med NOT eller !) binder til højre.

Endvidere erklæres der en union, der indeholder alle ID’ernes oplysninger. Det er opysninger som navn, type, virkefelt og indhold. Disse oplysninger bruges i symboltabellen.

Derudover tildeles der en type til terminalers og non-terminalers attribut ($$). Det vil sige at når man fx har et udtryk der indeholder heltals-addition, skal selve udtrykket tildeles typen heltal.

Regler:
Her defineres grammatik og semantiske aktioner.

Support rutiner: Dette er rutiner der understøtter de semantiske aktioner. Det kunne fx være en rutine til fejludskrift. I tilfælde af større programmer kan disse rutiner lægges ud i en separat fil. Dette kunne bl.a. være fornuftigt med alle de rutiner, der arbejder på symboltabellen (i vores tilfælde symbtab.c).

Følgende eksempel er vores udskrivningsrutine til fejl-meddelelser:

int yyerror(const char* c1, const char* c2)
{
  fprintf(stderr, "Fejl på linie %d, tegn %d - ", yylineno, yycharno);

  if (c2 == NULL)
    fprintf(stderr, c1);
  else
    fprintf(stderr, c1, c2);

  fprintf(stderr, "\n");

  return(1);
}

Hvorfor BISON?

Det var et naturligt valg for os at benytte BISON, da vores lærebog selv bruger den, men også fordi det er det mest udbredte værktøj inden for sin kategori.

BISON er ikke det eneste værktøj der kan bruges i denne sammenhæng, men det er mere robust end mange andre parser-generatorer. Dette kan forklares ved, at andre værktøjer ofte er beregnet på udforskning inden for området, fx på universiteter. BISON derimod, er meget udbredt (kan hentes på Nettet) og er dermed blevet gennemtestet af flere mennesker gennem en lang årrække, hvorfor det naturligvis er mere stabilt.