fri2tilstand.sgml

<chapter id="c-parser-tilstandsmaskine">
<title>Parsning - hvordan oversættes et C program</title>

<sect1 id="declaration-parser">
<title>En declaration parser</title>

<para>
Erklæringer kan være vanskelige at læse, især når der indgår
pointere til funktioner. Installation af en signal handler med
funktionen signal(2) er kendt for sin vanskelige prototype.
</para>

<para>
Det ville være en god øvelse at skrive en komplet declaration
parser (og en sådan er på ønskesedlen til en udvidet version af
denne bog). Imidlertid findes der allerede en meget instruktiv
parser til interaktiv / didaktiv anvendelse, cdecl.
</para>

<para>
Cdecl manual-page går ud fra, at man er bekendt med de
væsentligste problemstillinger, men den forklarer ikke, hvordan
man løser læselighedsproblemet, hvis man ikke lige har cdecl ved
hånden!
</para>

<para>
For at gøre tingene vanskeligere, er Linux/Gnu signal.h fuld af
defines og særlige syntaktiske konstruktioner, som skal lette
læsningen for den erfarne multiplatform programmør - men som gør
det fuldstændigt umuligt for den almindelige begynder at finde
hoved og hale. I dette tilfælde er manual page for signal(2) en
lettelse. Der er oven i købet en forklaring på, hvordan man kan
opbygge deklarationen ved hjælp af "typedef"ning. Manual siderne
for glibc er med i RedHat og andre distributioner, men er ikke
en del af glibc systemet, der kun anvender info-pages.
</para>

<para>
Men i header filerne - kast et blik på /usr/include/signal.h - er
der så mange hensyn til diverse platforme at det bliver næsten
ulæseligt. Leder vi på "signal(" finder vi:
</para>

<para>
<literal>
#define signal(sig, handler) __sysv_signal ((sig), (handler))
</literal>
</para>

<para>
Ovenstående define kan man ikke fodre cdecl med. Heldigvis er
den ikke så svær at forstå. Signal er en funktion som skal
erstattes af __sysv_signal. De to parametre skal gives videre som
de er. Det ene skal være et signal, (fx. INTR, svarende
til control-C) og det andet skal være den funktion, som vi vil
have kørt, når vores program modtager signalet. Men så må vi jo
kigge efter, hvordan headerfilen definerer __sysv_signal().
</para>

<para>
<literal>
extern __sighandler_t __sysv_signal __P ((int __sig, __sighandler_t __handler));
</literal>
</para>

<para>
Heri indgår der - desværre - også en #define macro, nemlig
__sighandler_t. Så det er en større sag at finde rundt i.
</para>

<para>
Det, som cdecl er glimrende til, er at fodre den med en vanskelig
prototype og så se, hvordan den vil forklare det.
</para>

<para>
Vi finder med <command> man signal </command> følgende prototype:
</para>

<para>
<literal>
void (*signal(int signum, void (*handler)(int)))(int);
</literal>
</para>

<para>
Er det en void funktion? Jeg spørger bare ... Nej, det er ikke en
void funktion, det er en funktion, som returnerer en pointer til
en anden funktion, som er void. Nemlig den tidligere signal
handler. Så kan man jo geninstallere den, hvis man på et
tidspunkt skal tilbage til forrige niveau af signal handling.
</para>

<indexterm><primary>cdecl, eksempel på anvendelse</primary></indexterm>
<screen id="cdecl">
<prompt>ax@pluto:/udvik/$</prompt><userinput>cdecl</userinput>
<prompt>cdecl></prompt><userinput>void (*signal(int signum, void (*handler)(int)))(int)</userinput>
syntax error
</screen>

<para>
Ja, desværre kan denne udmærkede lille applikation heller ikke
klare denne iøvrigt korrekte prototype, så der er virkelig et
problem her.
</para>

<para>
Løsningen er at lære sig "højre-venstre" teknikken.
</para>

<para>
Højre venstre - teknikken består i at læse indefra den
identifier, som man ønsker at forstå. I ovenstående erklæring
"signal".
</para>

<para>
Til HØJRE for signal er der en parentes start. Det betyder:
"Signal er en funktion ..."
</para>

<para>
Efter parameter parentesen er der "lukket" ved hjælp af en
slut-parentes ekstra. Derfor må vi gå til VENSTRE. Vi er nu nået
til, at vi forventer angivelse af retur-type.
</para>

<para>
Til venstre står der '*' hvilket vi læser som "returnerer en
pointer til ..." - til hvad?
</para>

<para>
Parentes start spærrer for yderligere adgang til venstre, så vi
går mod højre, udenfor den matchende parentes og ser efter denne
endnu en parentes, aha, en pointer TIL EN FUNKTION, der står jo
igen parenteser, og i øvrigt med en int som parameter. Det mest
vanskelige er, at den VOID, som står forrest på linjen, er retur
type angivelse til denne funktionspointer.
</para>

<para>
Det er ikke nemt. Læs man - siden for signal, den forklarer (som
nævnt ovenfor), at meningen med signal er, at den returnerer den
tidligere handler, så man kan reinstallere den senere.
</para>

</sect1>


<sect1 id="expression-parser">
<title>En expression parser</title>
<para>
En kalkulator er et program, som kan fodres med beregningsudtryk
og som derefter beregner resultatet. Som regel skrives resultatet
på en computerskærm, men det kan jo lige så godt være på en
papirstrimmel eller i et felt i et regneark. Et udtryk kaldes på
engelsk et expression.
</para>

<para>
Hvis man vil forstå, hvordan en oversætter/compiler virker,
så er en kalkulator et godt sted at begynde. En kalkulator består
af analysator, som kaldes en expression parser, og en
beregningsdel. Expression parseren har til opgave at analysere
input og se, hvad der skal gøres.
</para>

<para>
En sådan expression parser findes også i en oversætter. I stedet
for at foretage beregning, så udskriver oversætteren assembler
kode, der vil kunne foretage beregningen.
</para>

<para>
En væsentlig del af kunsten at skrive en oversætter består i at
skille tingene ad. Det kræver stor forståelse for opgaven, en
stor abstraktionsevne, for kode-generator delen er jo flettet
ind, så at sige, i analysen. Hver gang man kommer til et
delresultat, skal det omsættes til kode. Endvidere kræves der
også en forståelse for assembler koden. Derfor er det meget
godt at begynde med en kalkulator. Den er simplere at skrive,
nemmere at forstå, men rummer de samme problemstillinger.
</para>

<para>
I en compiler har man brug for en expression parser, hver gang
der er et statement. Et statement eller en (programsprog-)sætning
kan i simple tilfælde blot være et beregningsudtryk efterfulgt af
et semikolon. I mere komplicerede tilfælde er det for eksempel keywordet
<emphasis> if </emphasis> efterfulgt af en betingelse og så et
eller andet stykke kode, som styres af <emphasis> if'et
</emphasis>. Betingelsen er, i C sproget, et expression (altså et
udtryk). Den efterfølgende sætning vil i mange tilfælde være et
funktionskald (også et udtryk, strengt taget) eller en tildeling
som i C sproget også er et udtryk.
</para>

<para>
Så en expression parser er en vigtig del af computer-software.
Her kommer et eksempel på en kalkulator, som beregner ganske
almindelige regnestykker som 2+3 eller mere komplicerede, hvori
der indgår aritmetiske funktioner og en enkelt variabel, X, som
er resultatet af foregående beregning. Ideen her er hentet fra
gode gamle Compas Pascal, men det er altså C-kode, dette her.
</para>

<para>
En lignende kalkulator i C++ er en god opgave for viderekomne.
(Jeg vil senere prøve at komme med nogle sammenligninger med
Stroustrups eksempel, Stroustrup[1997] p. 108.)
</para>

<para>
Eksempel på input:
</para>
<programlisting>
calcu '200 * sin(0.444)'
85.911

calcu &lt;&lt;SLUT
2 + 3
5 * X
SLUT

Calc:      5.0000
Calc:     25.0000
Calc:

calcu
Calc: 32/square(2)
         ^Error
</programlisting>

<para>
Programmet benytter til den viste fejlmeddelelse en særlig slem
variant af printf format specification, som skriver et antal
spaces ud styret af en variabel:
<literal>
printf("En padded string: %*s\n",lengde,string);
</literal>
Meget smart - men første gang lidt vanskeligt at læse og forstå.
Det styrer angivelsen af error positionen.
</para>

<para>
Programmet er i sin nuværende form ganske anvendeligt, fordi det
kan fungere som erstatning for expr programmet, der stiller alt
for mange krav til spaces og anden formatering til de
expressions, som skal evalueres. Men programmet kan simpelt hen
også anvendes til beregning af prislister (det har det faktisk
været!)
</para>

<example id="calculator">
<title>Calculator, recursive descent expression parsing </title>
<programlisting>
/* file calcu.c */
/* (c) Donald Axel GPL - license */
/* ANSI - C program demonstration, command line calculator */
/* Recursive descent parser */
/* Improve: Make a HELP command. Add more variables.       */

#include &lt;stdio.h>
#include &lt;stdlib.h>
#include &lt;string.h>
#include &lt;math.h>



#define MAXL 8196
char gs[MAXL];
char *cp;
char *errorp;
double oldval;

/* local prototypes: */
int calcu();
int evaluate(char *line, double *prev_result);
int stricmp(const char *s1, const char *s2);
int strnicmp(const char *s1, const char *s2, int len);


int main(int argc, char *argv[])
{
    int rv, jj;

    jj = 0;
    while (++jj &lt; argc) {
        strcat(gs, argv[jj]);
    }
    if (argc == 1)
        return calcu();
    strcat(gs, "\n");
    rv = evaluate(gs, &amp;oldval);
    if (!rv)
        printf("%g\n", oldval);
    else
        printf("Calcu:%s\n%*s\n", gs, rv, "^Error");
    return rv;
}


/* Description: */
/* calcu() sets up a string which is then evaluated as an expression  */
/* If (argc>1) main sets up string for evaluate() and prints result.  */
/* stricmp does not stop at '\n' - so we have to compare with "xx\n"  */
/* gettok() could solve that problem. TRY to use gettok().            */



int nextchar()
{
    ++cp;
    while (*cp == ' ')
        ++cp;
    return *cp;
}


int eatspace()
{
    while (*cp == ' ')
        ++cp;
    return *cp;
}


int calcu()
{
    FILE *ifil;
    char line[MAXL];
    int rpos;
    double r;

    ifil = stdin;
    while (1) {
        errorp = NULL;
        printf("Calc:");
        if (!fgets(line, MAXL, ifil))
            break;
        if (strlen(line) &amp;&amp; strnicmp(line,"QUIT",4)
&amp;&amp; stricmp(line,"Q\n"))
            rpos = evaluate(line, &amp;r);
        else
            break;
        if (!rpos) {
            printf("%-18g\n", r);
            oldval = r;
        } else {                /* prints Error in field min. 12 wide */
            printf("%*s\n", rpos, "^Error");
        }
    }
    return rpos;                /* if interactive rpos should always be 0 */
}


/* More local prototypes. This could, of course, be a separate file. */
double expression();
double product();
double potens();
double signedfactor();
double factor();
double stdfunc();


int evaluate(char *s, double *r)
{
    cp = s;
    eatspace();
    *r = expression();
    eatspace();
    if (*cp == '\n' &amp;&amp; !errorp)
        return (0);
    else
        return (cp - s) + 11;
}


double expression()
{
    double e;
    int opera2;

    /* printf("test arg:%s\n",cp); */

    e = product();
    while ((opera2 = *cp) == '+' || opera2 == '-') {
        nextchar();
        if (opera2 == '+')
            e += product();
        else
            e -= product();
    }
    eatspace();
    return e;
}


double product()
{
    double dp;
    int ope;

    dp = potens();
    while ((ope = *cp) == '*' || ope == '/') {
        nextchar();
        if (ope == '*')
            dp *= potens();
        else
            dp /= potens();
    }
    eatspace();
    return dp;
}


double potens()
{
    double dpo;

    dpo = signedfactor();
    while (*cp == '^') {
        nextchar();
        dpo = exp(log(dpo) * signedfactor());
    }
    eatspace();
    return dpo;
}


double signedfactor()
{
    double ds;
    if (*cp == '-') {
        nextchar();
        ds = -factor();
    } else
        ds = factor();
    eatspace();
    return ds;
}


double factor()
{
    double df;

    /* while (*cp!='\n') {
       putchar(*cp++);
       } 
     */

    switch (*cp) {
    case '0':
    case '1':
    case '2':
    case '3':
    case '4':
    case '5':
    case '6':
    case '7':
    case '8':
    case '9':
        df = strtod(cp, &amp;cp);
        break;
    case '(':
        nextchar();
        df = expression();
        if (*cp == ')')
            nextchar();
        else
            errorp = cp;
        break;
    case 'X':
        nextchar();
        df = oldval;
        break;

    default:
        df = stdfunc();
    }
    /* printf("ddt: df = %lf, *cp = %c\n",df,*cp); */

    eatspace();
    return df;
}


char *functionname[] =
{
    "abs", "sqrt", "sin", "cos", "atan", "log", "exp", "\0"
};

double stdfunc()
{
    double dsf;
    char **fnptr;
    int jj;

    eatspace();
    jj = 0;
    fnptr = functionname;
    while (**fnptr) {
        /* printf("%s\n",*fnptr); */
        if (strncmp(*fnptr, cp, strlen(*fnptr)) == 0)
            break;

        ++fnptr;
        ++jj;
    }
    if (!**fnptr) {
        errorp = cp;
        return 1;
    }
    cp += (strlen(*fnptr) - 1);
    nextchar();
    dsf = factor();
    switch (jj) {
    case 0: dsf = abs(dsf);  break;
    case 1: dsf = sqrt(dsf); break;
    case 2: dsf = sin(dsf);  break;
    case 3: dsf = cos(dsf);  break;
    case 4: dsf = atan(dsf); break;
    case 5: dsf = log(dsf);  break;
    case 6: dsf = exp(dsf);  break;
    default:{
            errorp = cp;
            return 4;
        }
    }
    eatspace();
    return dsf;
}


/* end calcu.c */


</programlisting>
</example>
</sect1>


<sect1 id="sect-uCc">
<title>En komplet compiler</title>
<para>
Nu har vi haft mulighed for at se nærmere på en tag-parser og en
expression parser. Hvor langt er der så til at skrive en komplet
compiler? Ikke så langt. Vi får brug for en kode-generator,
d.v.s. den del, som ved, hvordan maskin instruktioner for
addition, subtraktion, kopiering og funktionskald etc. ser ud.
Desuden vil det være klogt at lave en præprocessor, som kan
håndtere #include of #define.
</para>

<para>
Når man kan skrive en expression parser som <xref
linkend="expression-parser"/> og -- i stil med tag-parseren <xref
linkend="ex-tagbal-sammenligning"/> -- kan behandle forskellige
typer input efter forskellige regler, så har man teknikken til
det meste af en C compiler. Kodegeneratoren hæftes på
parser-delen, således at hver gang man har analyseret sig til en
basis-operation (tildeling, aritmetik, funktionskald osv) så
skrives de tilsvarende assembler instruktioner til outputfilen.
</para>

<para>
Preprocessor er derimod det aller første behandlings-trin
i C-compileren. Alle linjer med havelåge tegn (hash
character, eller nummer-tegn <emphasis> # </emphasis>) bliver
behandlet af præprocessoren. Det er #include, #define, #ifdef mv.
De kaldes direktiver eller præprocessor kommandoer.
</para>

<para>
En compiler kan somme tider indgyde ærefrygt. Hvordan får man et
stykke software til at forandre programsætninger til maskinkode,
oven i købet lange, komplicerede programsætninger, med iffer og
while, med komplicerede beregningsudtryk og så videre. Og
maskin-instruktioner, er det noget for hvide mennesker? Er det et
mirakel, at compileren kan finde ud af at oversætte <literal> if
(a > b) duut(); </literal> til maskininstruktioner, eller kender
den måske maskin-instruktionerne i forvejen? Ja - selvfølgelig
kender compileren maskinen og dens instruktionssæt i forvejen!
</para>

<para>
Det er efter min erfaring et vigtigt skridt, måske det vigtigste,
for forståelse af computeren, at man forstår, hvordan CPU og
adressebus fungerer. <!--TODO appendix D--> En CPU kan bedst
sammenlignes med en regnemaskine, som har flere små
resultat-display, eller celler til at gemme
kalkulationsresultater. En sådan celle kaldes et register, og
CPU'er kan anvende disse direkte i deres instruktioner. Til
gengæld er der begrænsninger på, hvordan man kan anvende tal
(data) fra RAM modulerne. Nogle CPU typer insisterer på kun at
lave aritmetik med register-indhold. Andre, som Intel-x86 er mere
alsidige og derfor også mere komplicerede.
</para>

<para>
Intel 386 familien har til almindelig afbenyttelse for alle slags
programmer registrene %eax, %ebx, %ecx og %edx. Desuden er der
nogle ekstra registre, %esi og %edi, som er specielt gode til
index-operationer, samt et base-pointer register %ebx og et
stack-pointer register %esp. Desuden er der selvfølgelig en
instruktions pointer %eip og mange specielle registre, bl.a. til
administration af hukommelsen. De er ikke interessante i denne
sammenhæng.
</para>

<para>
Et typisk lille assembler program i GNU assembler til at lægge to
tal sammen med kunne skrives sådan her:
</para>

<example id="ex-gas-programmering">
<title>Assembler programmering</title>
<programlisting>
# dette er en kommentar
        .comm tal1,4,4
        .comm tal2,4,4
        movl tal1, %eax
        addl tal2, %eax   # nu lægges tal2 til tal1,
                          # resultatet ligger i %eax
        ret
</programlisting>
<blockquote><sidebar><para>
GNU assembleren benytter traditionelt sin egen syntaks. Man
skal huske, at Intel assembler er forskellig på væsentlige
punkter (og er copyrighted!).
</para><para>
Der findes en "nasm" netwide portable 80x86 assembler, som
benytter en mere Intel-agtig syntaks, hvis man foretrækker det.
</para></sidebar></blockquote>
</example>

<example id="ex-oversat">
<title>Output fra GNU-C oversætter</title>
<screen>
<prompt>ax@pluto:fri$</prompt><userinput>cat xyzzy.c</userinput>
xyzzy()
{
    return 42;
}
<prompt>ax@pluto:fri$</prompt><userinput>cc -O2 -fomit-frame-pointer -S xyzzy.c</userinput>
<prompt>ax@pluto:fri$</prompt><userinput>cat xyzzy.s</userinput>
	.file	"xyzzy.c"
	.version	"01.01"
gcc2_compiled.:
.text
	.align 4
.globl xyzzy
	.type	 xyzzy,@function
xyzzy:
	movl $42,%eax  # <<=== OBS! HER ER OVERSÆTTELSEN!!!
	ret
.Lfe1:
	.size	 xyzzy,.Lfe1-xyzzy
	.ident	"GCC: (GNU) 2.95.2 19991024 (release)"
<prompt>ax@pluto:fri$</prompt>
</screen>
</example>

<para>
Den linje, som interesserer os mest, er <literal> movl $42,%eax
</literal>. Det er oversættelsen af <literal> return 42
</literal>. movl betyder move long, altså flyt en integer, som er
lang. På intel x86 kaldes 32 bit integers for long. Andre
assembler sprog ville kalde det for en load operation.
$42 betyder en konstant med værdien 42 (Dollar = værdi). %eax er
en snedig måde at betegne 386 multi purpose registrene, procent
tegnet gør, at dette symbol ikke kan være en variabel, så
programmøren kan altså godt have en variabel eax i programmet,
uden at den støder sammen med %eax.
</para>

<para>
Når jeg i en funktion skriver <literal> return 42; </literal> --
så sker der åbenbart det, at værdien, som skal returneres, lægges
i det CPU-register, som er det almindeligst anvendte (og - tjek
Intel manualer - også det hurtigste). Når computerprogrammet
vender tilbage til de instruktioner, som kaldte vores funktion,
så har den altså resultatet i %eax. I gamle dage kaldte man %eax
for kalkulator registeret. I dag kan flere registre bruges som
kalkulatorregistre.
</para>

<para>
Ellers er det meste af ovenstående output er fileheader og functions
type-erklæringer, som jo blot kan genereres som en ramme, hvori
man indsætter funktionsnavnet.
</para>

<example id="ex-uC-oversaettelse">
<title>uC oversættelse</title>
<screen>
<prompt>ax@pluto:fri$</prompt><userinput>uC -A xyzzy.c</userinput>
<prompt>ax@pluto:fri$</prompt><userinput>cat xyzzy.y86</userinput>
#* * * * uCC Small-c Compiler v3.01,  Feb. 2001 * * * *
#Linux version 0.9 beta; 32 bit 80386 code, Serial#0018
#
	.text
	.align 4
#xyzzy()
	.globl xyzzy
	.type	xyzzy,@function
xyzzy:
	pushl %ebp
	movl %esp,%ebp
#{
#    return 42;
	movl $42,%eax     # <<=== OBS! HER ER OVERSÆTTELSEN!!!
	movl %ebp,%esp
	popl %ebp
	ret
#}
	.extern 
# const strings: 
.section 	.rodata
.LC0:
# end of constant strings


	.ident "uC 0.9e. 2001-06-02"
<prompt>ax@pluto:fri$</prompt>
</screen>
<blockquote><sidebar>
<para>
Det er meget tekst, der kommer ud af uC oversættelsen, men igen
er det vigtigste linjen med <literal> movl $42,%eax </literal>.
</para>
</sidebar>
</blockquote>
</example>

<para>
I foregående gcc oversættelse var der færre instruktioner. Det
skyldes, at vi anvendte en option -fomit-frame-pointer, som
betyder, at compileren (om muligt) ikke skal udspy
instruktionerne, som saver base-pointer registeret %ebx.
</para>

<para>
En compiler oversætter de enkelte statements til symbolsk
assembler, det vil sige maskin instruktioner i tekst form.
Oversætterens output er en fil med symbolske
maskin-instruktioner, kaldet assembler source.
</para>

<para>
Man behøver ikke at kunne <emphasis> så forfærdelig </emphasis>
meget assembler for at få noget ud af dette afsnit. De
nødvendigste ting bliver forklaret undervejs.
</para>

<para>
Måske det bedste ved uC er, at der er masser af opgaver, som man
kan gå i gang med. Man kan pynte lidt hist og her på
hjælpetekster, banner tekster osv. Man kan også lave ganske små
ændringer, som gør den nemmere at bruge.  Men man kan også
forbedre den <emphasis> væsentligt </emphasis> på kodekvaliteten
ved at tilføje nyttige funktioner i kodegeneratoren.
</para>

<para>
Når man ser, hvordan et program bliver "nedbrudt" under
oversættelsen, så kan man få den helt store aha-oplevelse.
P.J. Plauger har på et tidspunkt <!--TODO, C Journal -->
skrevet, at han for at lære et nyt programmeringssprog skrev
en (lille) compiler til det pågældende sprog. Det er derfor,
at dette eksempel er taget med.
</para>


<sect2 id="uC-compiler">
<title> uC - en mikroskopisk C compiler </title>

<para>
I dette afsnit præsenteres en lille C compiler, som man selv kan
skrive - eller skrive videre på, nemlig Small-C, som jeg i denne
version har kaldt Micro-C, eller uC.
</para>

<para>
Small-C compileren er legendarisk. I microcomputerens barndom
skrev Ron Cain en artikel (eller en artikelserie?) om en lille
C compiler, som kunne kompilere sig selv, og som faktisk var/er
et nyttigt sub-set af C sproget. Small-C var skrevet til Intel
8080 CPUen, en 8/16 bit CPU og det udbredte styresystem CP/M
(Control Program for Microcomputers) fra Digital Research inc.
</para>

<para>
Den oprindelige source til Small-C har jeg aldrig kunnet finde.
Der findes imidlertid mange varianter. En af de bedste er James
E. Hendrix's Small-C 2.2, men den er på den anden side også mere
kompliceret.  En anden version for MS-DOS hed Caprock System PC
eller CPC, og det er den, som jeg har arbejdet videre på. Den
vigtigste ændring er, at den kører 32 bit under linux og at den i
øvrigt benytter samme call-sequence som GNU-C.
</para>

<para>
Kildetekst og nogle primitive make filer m.v. finder man i et
gzippet tar arkiv i eksempel-kataloget, uC09e-3.tgz hedder det
pr. 2. juni 2001.
</para>

<para>
Eksempel på udpakning og installation:
<screen id="sc-install">
<prompt>[root@linus /root]# </prompt><userinput>mkdir -p /hjem/src/compiler/ucc</userinput>
<prompt>[root@linus /root]# </prompt><userinput>cd /hjem/src/compiler/ucc</userinput>
<prompt>[root@linus ucc]# </prompt><userinput>tar xzvf /tmp/uC09e-3.tgz</userinput> # OBS! Nyeste version kan hedde noget andet
<prompt>[root@linus ucc]# </prompt><userinput>make</userinput>
<prompt>[root@linus ucc]# </prompt><userinput>make install</userinput>
</screen>
</para>

<para>
Hvis man kører <command>make install</command>, vil
programmerne lave et symbolsk link fra /usr/local/uC til det
sted, hvor man installerer fra. Derfor skal man ikke flytte
installations-dir. Man kan let selv lave om på disse ting. Hvis
man i forvejen har et directory /usr/local/uC vil man blive bedt
om at fjerne det manuelt, så installationen er altså ikke destruktiv.
</para>


<para>
Leder man på nettet kan man sagtens finde source
til andre C compilere, og som bekendt er GNU C "fri software",
der distribueres med kildetekst og dokumentation, så
den kan man jo også begynde at læse på. 
</para>

<para>
Inden jeg valgte at det skulle være uC, som skulle med som
eksempel i denne bog, havde jeg Dennis Ritchies oprindelige
"pre-struct" C, LCC, cc68 og cc386 i kikkerten, før end jeg
valgte denne. Den er lille og kunne nemt tilpasses til GNU/Linux
miljøet. Og -- indrømmet -- jeg kendte den godt i forvejen!
</para>

<para>
Den nuværende version nummerering indeholder to oplysninger.
Linux-porteringen (32 bit versionen) er version 0.9, og den
centrale del, parseren, har jeg ladet hedde version 3.01 fordi
den jo er baseret på tidligere versioner.
</para>

<para>
  Uddrag fra uCannoncering - filen:
</para>

<para>
  Revision: Version 09 (næsten poleret ...) pr. 6-apr-2001.
</para>
<para>
  Parser-delen er version 3.01
</para>

<para>
  Med tilføjelse af options for extended stackframe og
for saving %ebx. (brug -h for at se options).
</para>

<para>
Assembler output oversættes af GNU "as" og linkes med
ld via en gcc kommando.
</para>

<para>
Den kan bootstrappes på en RedHat 5.2, 6.0 og RedHat 7.0 (benyt
--bx option til kompilering af main, se Changelog.dk); jeg
formoder, at der også er andre distributioner, som lader sig
anvende.
</para>

<para>
Koden er "acceptabelt ineffektiv", idet den performer ca 1/3
langsommere end gcc genereret kode. Det er egentlig ret
forbløffende, idet compileren er meget simpel og har nogle
indlysende skavanker, når der skal anvendes array indexering og
pointere. Forklaringen er, at de simplere instruktioner, der
anvendes, er hurtigere end de komplicerede instruktioner til
adressering, som gcc kan generere.
</para>

<para>
uC er instruktiv i 2 henseender:
</para>

<para>
1. Dels viser den hvordan man laver en minimal C -
compiler med en SUBSET af C, som alligevel er så
kompatibelt med (old-style) C at den kan kompileres
med en "stor" C compiler
</para>

<para>
2. Den kan oversætte sig selv. 
</para>

<para>
Hønen og ægget! Hvad nu, hvis man ikke lige har en C compiler ved
hånden. Kan man så få denne compiler til at fungere? Ja, det kan
man.  Den er lille nok til, at den kan hånd-oversættes.
</para>

<programlisting>

EN SPECIFIKATION AF uC

-----------------------------------------------------
Preprocessor direktiver:
-----------------------------------------------------

#include &lt;stdio.h>  /* leder i /usr/local/uC/include */

#include "fil.h"    /* current dir */

#define YXI 1       /* ikke parameter-macroer */

#ifdef              /* Betinget compilering */

#ifndef
#else
#endif
#asm                /* for hånd - optimering! */
#endasm

-----------------------------------------------------
Datatyper:
----------------------------------------------------
int x;
char w;
int array[n]
char arr[n];
int *ip;
char *cp;

eller

char s[];

extern int y;
&amp;function();

-----------------------------------------------------
Operatorer:
-----------------------------------------------------
Assignment: =  ++ --
Aritmetik:  + - * / % 
Bit:        ~ ^ | &amp;
+shift:     &lt;&lt; >>
Logiske:    INGEN (sic)
Dereference *
Address     &amp;

Pointer aritmetik er tilladt (er unsigned)
Struct klares som char[n] med #define offsets

-----------------------------------------------------
Flow
-----------------------------------------------------

if (x) {}
else   {}

while(x) {
break;
continue;
}

return x;

-----------------------------------------------------
Modularitet
-----------------------------------------------------
extern int x;   /* static mangler */

/* extern f(); automatisk hvis ukendt fcn-navn optræder. */

functions returnerer en int. Altid!
function type må ikke specificeres, men den er jo også
redundant, da funktioner altid returnere en int.
prototyper er forbudt! Hu!

separat kompilering og linkning med gnu as og ld.

-----------------------------------------------------
Slut på specifikation af uC
-----------------------------------------------------

</programlisting>

<para>
Det er meningen her at give en ganske kort beskrivelse af denne
compiler. En forsmag kan være den centrale funktion, som parser
eksterne objekter:
</para>

<example id="ex-parser-externe-obj">
<title>C oversætter, parsning på øverste niveau</title>
<programlisting>
/*                                              */
/*      Behandling af alt input                 */
/*                                              */
/* På dette niveau er kun statiske erklæringer  */
/*      defines, includes, og function          */
/*      definitions legale                      */
/* Input kaldes fra (a)match                    */

parse()
{
    while (eof == 0) {
        if (amatch("extern", 6)) {
            cextern = 1;
            if (amatch("char", 4)) {
                declglb(cchar); /* declare global */
                ns();
            } else if (amatch("int", 3)) {
                declglb(cint);
                ns();
            } else {
                declglb(cint);
                ns();
            }
            cextern = 0;
        } else if (amatch("char", 4)) {
            declglb(cchar);
            ns();
        } else if (amatch("int", 3)) {  /* cannot handle function type! */
            declglb(cint);
            ns();
        } else if (match("#asm"))
            doasm();
        else if (match("#include"))
            doinclude();
        else if (match("#define"))
            addmac();
        else
            newfunc();
        blanks();               /* preprocess, force eof if pending */
    }
}

</programlisting>
</example>

<para>
Mere i næste version af "Friheden til at programmere i C" ...
</para>

</sect2>
</sect1>


<sect1 id="Tilstandsmaskiner">
<title>Tilstandsmaskiner</title>
<para>
Tilstandsmaskiner er betegnelse for 2 ting: (1) generelt for
computer programmer, idet alle programmer er tilstands-maskiner,
og (2) en speciel teknik, som består i, at man bruger en
tabel til at beskrive de tilstande, et program kan være i.
Tilstandstabeller anvendes blandt andet i parsere.
</para>

<para>
Hvis man vil se en "rigtig" tilstandsmaskine, så kan man studere
output fra yacc eller bison parser-generatorer. De egner sig
imidlertid også til opgaver. Da ID-Software frigav koden til
Quake og Quake-2 projekterne, kunne man se, at botternes
bevægelser og strategi blev styret af simple tilstandsmaskiner.
</para>

<para>
Tilstandsmaskiner kaldes mere præcist Finite State Machines,
(FSM) maskiner med et endeligt antal tilstande. Tilstandene kan
noteres i en tabel, for der er jo kun et endeligt antal af dem.
Hver tilstand er karakteriseret af, at der er et begrænset antal
muligheder for, hvordan maskinen kan reagere. Maskinen reagerer
på input, som skal kunne opdeles i et endeligt antal kategorier.
Input kan være fra et tastatur, men i et spil kan det
selvfølgelig også være fra en joy-stick.
</para>

<para>
For at få et billede af en FSM kan man forestille sig en
adventure-lignende situation: Jeg står foran indgangen til en
grotte, og jeg kan vælge at gå ind, kravle op af bjergvæggen, gå
baglæns eller til højre eller venstre. Jeg vælger at gå ind. Nu
har jeg andre muligheder, tilstanden er en anden. Det at gå fra
én tilstand til en anden kaldes en tilstandsændring (state
transition) og mulighederne for hver tilstand noteres i
tilstandstabellen.
</para>

<para>
Hvis jeg havde valgt at gå tilbage, havde jeg haft andre
muligheder bagefter, jeg var gået til en anden tilstand.
</para>

<para>
For at tabellen kan være på siden har jeg udeladt muligheden for
at gå til venstre.
</para>

<para>
 <informaltable frame="all">
   <tgroup cols="5">
<thead>
  <row>
    <entry>foran-grotte tilstand</entry>
    <entry>Inp.kategori 1</entry>
    <entry>Inp.kategori 2</entry>
    <entry>Inp.kategori 3</entry>
    <entry>Inp.kategori 4</entry>
    <entry>Inp.kategori 5</entry>
  </row>
</thead>
<tbody>
  <row>
    <entry>--</entry>
    <entry>Skift til ind i grotte-tilstand</entry>
    <entry>Skift til væk-fra-indgang tilstand</entry>
    <entry>Skift til op-over-grotte tilstand</entry>
    <entry>Skift til højre-for-grotte tilstand</entry>
    <entry>Skift til ubrugeligt-input tilstand</entry>
  </row>
</tbody>
</tgroup>
</informaltable>
</para>

<para>
Det er væsentligt for teorien at der er en kategori af
ikke-brugbart input, og det har yderligere den fordel, at
tilstandstabellen bliver mere overskuelig.  Næste tabel viser
hvilke muligheder, vi har, når vi er gået ind i grotten, jeg er i
"grotte tilstand". Der er samme antal input-kategorier, blot for
at gøre det lettere at håntere implementeringen senere.
</para>

<para>
 <informaltable frame="all">
   <tgroup cols="5">
<thead>
  <row>
    <entry>inde-i-grotte tilstand</entry>
    <entry>Inp.kategori 1</entry>
    <entry>Inp.kategori 2</entry>
    <entry>Inp.kategori 3</entry>
    <entry>Inp.kategori 4</entry>
    <entry>Inp.kategori 5</entry>
  </row>
</thead>
<tbody>
  <row>
    <entry>--</entry>
    <entry>Skift til støde-ind-i-væg tilstand</entry>
    <entry>Skift til foran-grotte tilstand</entry>
    <entry>Skift til ubrugeligt-input tilstand</entry>
    <entry>Skift til gennem-dør tilstand</entry>
    <entry>Skift til ubrugeligt-input tilstand</entry>
  </row>
</tbody>
</tgroup>
</informaltable>
</para>


<para>
I et rigtigt spil skal der selvfølgelig være mange, mange
tilstande, ligesom der i et godt adventure spil er mange huler,
grotter og underlige steder, man kan komme hen. I hver situation
udløser input-katetori X et skift til en tilstand (det kan godt
være samme tilstand og evt. en action, for eksempel at man kommer i
besiddelse af nye ting - og det er så en anden tilstand. Antallet
at tilstande kan derfor være ret stort i sådan et spil, og man
laver derfor heller ikke én FSM for hele spillet, men for eksempel som i
Quake en tilstandsmaskien for en "bot". Her bliver input til
"bot"en så ikke nødvendigvis input direkte fra tastaturet, men
resultatet af en beregning fra en tilstandsmaskine et andet sted
i programmet.
</para>

<para>
Antallet af tilstande, en CPU kan være i, fås ved at tage alle
registre og flag og lægge i forlængelse af hinanden og så tælle
antallet af bits, T, så er antallet 2<superscript>T</superscript>
</para>

<para>
Det almindeligste eksempel på en tilstandsmaskine er parsning af
en tekststring, som formodes at indeholde et floating point tal,
for eksempel <literal>123.45</literal>. Vi benytter den
internationale standard for floating point, altså punktum, i hele
kapitlet. Det kan være en god øvelse at lave et program, som også
kan acceptere flydendetals-komma.
</para>

<para>
Næste udgave af denne bog vil bringe nogle overskuelige eksempler
på tilstandstabeller, genererede med bison og "håndlavede". Følg
med på www.sslug.dk i de nye udgaver af "Friheden" bøgerne!
</para>

</sect1>
</chapter>