• Skriv tydligt och klart. Lösningar som inte går att läsa kan naturligtvis inte ge några poäng. Oklara och tvetydiga formuleringar kommer att misstolkas.
• Skriv den personliga tentamenskoden på varje inlämnat blad. Skriv inte namn eller personnummer på bladen.
• Skriv bara på en sida av papperet. Använd inte röd skrift.
• Antaganden utöver de som står i uppgifterna måste anges.
• Skriv gärna förklaringar om hur du tänkt. Även ett svar som är fel kan ge poäng, om det finns med en förklaring som visar att huvudtankarna var rätt.

Formelsamling

1. Eliminering av vänsterrekursion

A -> A x | y

Regeln ersätts av följande två regler (eller, korrektare uttryckt, tre produktioner), som beskriver samma språk men som inte är vänsterrekursiva:

A -> y R
R -> x R | empty

2. Vänsterfaktorisering

A -> x y | x z

Skriv om till dessa tre produktioner:

A -> x R
R -> y | z

Uppgift 1 (10 p)

Uppgift 2 (8 p)

    a = b - 2 * c - 3;
    d = 1;
    while (e * 4 < f * 5) {
        g = g + 6;
        h = j + 7;
        k = g + 6;
        m = j + 7;
    }

a) Översätt ovanstående programavsnitt till antingen ett abstrakt syntaxträd (genom att rita upp trädet) eller postfixkod för en stackmaskin. (Inte båda!)

b) Översätt programavsnittet till treadresskod. Identifiera vilka basic blocks som finns, och rita upp flödesgrafen. (Flödesgrafen, med treadresskoden i, räcker som svar.)

c) Visa någon optimering som går att göra inom ett av dessa basic blocks.

Scenario till uppgift 3-6

Vi ska arbeta med en delmängd av SQL som kan uttrycka sökningar, eller "SQL-frågor", som ser ut så här:

• Först skriver man nyckelordet select.
• Därefter kommer ett eller flera namn, åtskilda med kommatecken, som är namn på kolumner i tabeller.
• Därefter kommer nyckelordet from, följt av ett eller flera namn, åtskilda med kommatecken, som är namn på tabeller.
• Därefter är frågan antingen slut, eller så kommer nyckelordet where, följt av ett villkor.
• Villkoret består av ett eller flera delvillkor, somm sammanbinds med nyckelordet and.
• Ett delvillkor är en jämförelse av något slag. Det består av två operander, som kan vara antingen konstanter eller namn på kolumner, som jämförs med en jämförelseoperator.
• En konstant är antingen ett heltal, som 17, eller en textsträng med enkla citationstecken, som 'Kalle'.
• Jämförelsen görs med någon av de här jämförelseoperatorerna:
  =     !=     <     <=     >     >=
• Hela SQL-frågan avslutas med ett semikolon (;).

select Nummer from Gurkor where Vikt > 3;

select Nummer, Vikt from Gurkor where Vikt > 3 and Bredd <= 3;

select Kod, Maxlast, Bruttovikt
from Vagnar, Bilar, Personer
where Vagninnehavare = Personnummer
and Bilinnehavare = Personnummer
and Namn = 'Thomas';

select Nummer, Nummer, Nummer
from Gurkor, Gurkor, Gurkor
where Vikt != Vikt and 17 < 17;

     select
Nummer from
     Gurkor where Vikt

   > 3;

Uppgift 3 (4 p)

b) (1p) En annan av terminalerna som behövs är text, som är en textsträng med enkla citationstecken, som 'Kalle'. Innanför citationstecknen kan det finnas vilka tecken som helst utom just de citationstecknen. Skriv ett reguljärt uttryck som beskriver hur en textsträng får se ut.

c) (2p) Vilka andra terminaler, förutom namn och textsträng, behövs för att man ska kunna skriva en grammatik för SQL-delmängden?

Uppgift 4 (5 p)

Uppgift 5 (3 p)

select Nr from Bilar, Fiskar where Kod = 'X7';

Uppgift 6 (8 p)