Kompilatorer och interpretatorer: Lösningar till tentamen 2025-01-16

En grammatik för ett språk är en beskrivning, vanligtvis med någon form av regler, som beskriver vilka meningar som är giltiga i språket. Samma språk kan beskrivas av många olika grammatiker.

En parser är ett datorprogram, eller en del av ett datorprogram, som analyserar inmatningen för att avgöra om den är giltig på ett visst språk. Den matar vanligtvis också ut någon representation av indata, till exempel som en trädstruktur.

S -> a T
S -> a b U

I parsern kommer det att finnas en procedur S som man anropar när det ska komma en S i inmatningen. Eftersom en S kan vara antingen a T eller a b U, kommer det att finnas ett val (typiskt en if-sats), och eftersom båda alternativen börjar med a kan man inte veta vilken gren av if-satsen man ska välja om nästa token är a.

Den här produktionen för icke-terminalen T innehåller vänsterrekursion:

T -> T c

I parsern kommer det att finnas en procedur T som man anropar när det ska komma en T i inmatningen. Om man då ska jämföra inmatningen med T c, kommer koden att se ut som T(); match(c);. Man börjar alltså med att anropa proceduren T. Då är man tillbaka till att jämföra inmatningen med T c, och inmatningen har inte ändrats. Då händer samma sak igen, och igen och igen, så parsern har fastnat i en oändlig rekursion.

1. Från början är stacken tom.
2. Nästa token i inmatningen är a. Eftersom stacken är tom kan vi inte göra något annat än att skifta a, dvs lägga det på stacken. Nu innehåller stacken a.
3. Nästa token i inmatningen är b. Stacken innehåller a, men det finns ingen produktion som låter oss reducera a, så vi kan inte göra något annat än att skifta b. Nu innehåller stacken a b.
4. Nästa token i inmatningen är e. Stacken innehåller a b, men det finns ingen produktion som låter oss reducera a b, så vi kan inte göra något annat än att skifta e. Nu innehåller stacken a b e.
5. Inmatningen är slut, så det finns inget att skifta, utan vi måste reducera. Stacken innehåller a b e. Enligt produktionen U -> e kan vi reducera e till U. Efter att vi reducerat e innehåller stacken a b U.
6. Inmatningen är förstås fortfarande slut, och vi måste reducera. Stacken innehåller a b U. Enligt produktionen S -> a b U kan vi reducera a b U till S. Nu innehåller stacken S, vilket är startsymbolen, så vi har reducerat inmatningen till startsymbolen och är klara.

        rvalue a
        rvalue b
        <
        gofalse AFTER-IF-1
        lvalue c
        rvalue d
        =
        lvalue e
        rvalue f
        =
        rvalue g
        rvalue h
        +
        rvalue i
        rvalue j
        rvalue k
        *
        +
        rvalue l
        +
        >
        gofalse ELSE-START-2
        lvalue m
        rvalue n
        rvalue o
        /
        rvalue p
        /
        =
        goto AFTER-IF-2
label ELSE-START-2:
        lvalue q
        rvalue r
        =
label AFTER-IF-2:
        lvalue s
        rvalue t
        rvalue u
        *
        rvalue v
        rvalue w
        *
        rvalue x
        *
        =
label AFTER-IF-1:

        if a ≥ b goto AFTER-IF-1
        c = d
        e = f;
        temp1 = g + h
        temp2 = j * k
        temp3 = i + temp2
        temp4 = temp3 + l
        if temp1 ≤ temp4 goto ELSE-START-2
        temp5 = n / o
        m = temp5 / p
        goto AFTER-IF-2
label ELSE-START-2:
        q = r
label AFTER-IF-2:
        temp6 = t * u
        temp7 = v * w
        temp8 = temp7 * x
        s = temp6 + temp8
label AFTER-IF-1:

Token-typer som scannern antas returnera: BYT FRAS KLART KOLON SEMIKOLON ORD

int lookahead;

void match(int expected) {
    if (lookahead != expected)
        error();
    else
        lookahead = scan();
}

void inmatning(void) {
    kommandon(); klartkommando();
}

void klartkommando(void) {
    match(KLART); match(SEMIKOLON);
}

void kommandon(void) {
    if (lookahead == BYT) {
        kommando(); kommandon();
    }
    else {
        // Ingenting
    }
}

void kommando(void) {
    match(BYT); kommandorest();
}

void kommandorest(void) {
    if (lookahead == ORD) {
        match(ORD); match(KOLON); flera_ord(); match(SEMIKOLON);
    }
    else if (lookahead == FRAS) {
        match(FRAS); flera_ord(); match(KOLON); flera_ord(); match(SEMIKOLON) ;
    }
    else
        error();
}

void flera_ord(void) {
    match(ORD); noll_eller_flera_ord();
}

void noll_eller_flera_ord(void) {
    if (lookahead == ORD) {
        match(ORD); noll_eller_flera_ord();
    }
    else {
        // Ingenting
    }
}

void parse() {
    lookahead = scan();
    inmatning();
    printf("Ok.\n");
}

int main() {
    printf("Skriv en inmatning enligt grammatiken!!\n");
    printf("Avsluta med CTRL-D!\n");
    parse();
}