Kompilatorer och interpretatorer: Hemtentamen 2020-08-18

Det här är hemtentan som går tisdag 18 augusti 2020 i kursen DT125G Kompilatorer och interpretatorer, provkod A001. Ansvarig lärare är Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), telefon 070-73 47 013.

Tid: 14:15 - 19:15

Instruktioner

  1. Den här hemtentan ersätter den planerade salstentan, och är endast för de studenter som anmält sig till den tentan.
  2. Uppgifterna ska lösas enskilt, dvs inga grupper av två eller flera studenter.
  3. Du får använda dator, böcker och vilka andra hjälpmedel som helst, men du får inte samarbeta eller fråga någon (utom mig). Exempelvis är det tillåtet att söka och läsa på webbplatser som Stack Overflow, men inte att ställa egna frågor. Du kan alltså provköra kommandon och program, om du vill.
  4. Diskutera inte uppgifterna eller dela med dig av svar förrän tidigast dagen efter tentan.
  5. Lös de angivna uppgifterna och samla svaren på lämpligt sätt, till exempel i en PDF.
  6. Den här kursen fick aldrig någon Blackboard-sida när den gick, så tentan kommer därför att publiceras på kursen vanliga webbsida, http://basen.oru.se/kurser/koi/2019-2020-p1/. Skicka in svaren med vanlig e-post (thomas.padron-mccarthy@oru.se), senast vid tentatidens slut. Om du inte senast en timme efter tentatidens slut fått ett svar från mig med en bekräftelse på att du skickat in svaren, bör du kontakta mig, enklast genom att ringa eller SMS:a mig (ifall det är e-posten som inte fungerar). Tänk på att en del mailtjänster (särskilt Microsoft-tjänster som Hotmail.com, Outlook.com och Live.com) ibland kastar bort brev med bilagor, utan att meddela det.
  7. Skriv gärna svaren i ett ordbehandlingsprogram. Rita gärna eventuella diagram i ett ritprogram. Det är inte förbjudet att skriva och rita för hand, men då måste text och bilder scannas in eller fotograferas. Det finnas scanner-appar till Android och iPhone, till exempel Adobe Scan, som ger bättre resultat än att bara ta vanliga kort med kameran.
  8. Tentatiden är utökad med en extra timme för att täcka in problem med e-post, inscanning eller fotografering av diagram, och liknande.
  9. Om du behöver fråga något, så kontakta gärna mig. Ring eller skicka SMS, för jag kanske inte kommer att sitta vid datorn hela tiden.
  10. Oklara och tvetydiga formuleringar kommer att misstolkas. Lösningar som inte går att läsa eller förstå kan naturligtvis inte ge några poäng.
  11. Antaganden utöver de som står i uppgifterna måste anges. Gjorda antaganden får inte förändra den givna uppgiften.
  12. 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.
  13. Maximal poäng är 36. För godkänt betyg krävs minst 20 poäng.
  14. Resultat meddelas senast 15 arbetsdagar efter tentamensdatum. Eftersom svaren skickas in elektroniskt scannas tentorna inte för retur.

Formelsamling

1. Eliminering av vänsterrekursion

En vänsterrekursiv grammatik kan skrivas om så att den inte är vänsterrekursiv. Antag att en regel (eller, korrektare uttryckt, två produktioner) i grammatiken ser ut så här:
A -> A x | y
A är en icke-terminal, men x och y står för godtyckliga konstruktioner som består av terminaler och icke-terminaler.

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

Antag att grammatiken innehåller denna regel (två produktioner):
A -> x y | x z
A är en icke-terminal, men x, y och z står för godtyckliga konstruktioner som består av terminaler och icke-terminaler.

Skriv om till dessa tre produktioner:

A -> x R
R -> y | z

Här kommer det att komma ett antal uppgifter...


Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), 13 augusti 2020