Gammalt Mästarprov Syntax

Mästarprovet ska lösas individuellt och redovisas både skriftligt och muntligt. Inget samarbete är tillåtet, se vidare hederskodexen. Du ska alltså inte diskutera lösningar med någon annan fram till dess att alla muntliga redovisningar är avklarade. Inlämningarna plagiatgranskas. Nytt för 2023 är att det inte är tillåtet att använda verktyg baserade på AI/maskininlärning i arbetet med lösningarna. Exempel på förbjudna verktyg är Github Copilot och ChatGPT.

Skriftliga lösningar ska lämnas in i Canvas.

Det bästa är att använda LaTeX för att skapa texten. De flesta som använder LaTeX gör det via ett webbgränssnitt som till exempel Overleaf Links to an external site.. Om du bygger lokalt, tänk på att använda pdflatex så att resultatet blir en pdf-fil. Assistenterna ska inte behöva bygga LaTeXfiler själva och framför allt inte installera externa bibliotek.
Det näst bästa är att använda Markdown Links to an external site. som är enklare än LaTeX och ger nästan lika bra resultat.
Resterande: Om ni använder Microsoft Word eller liknande - tänk på att spara som pdf så att alla kan läsa texten som det är tänkt utan att ha Word installerat.

Krav på lösningar:

Skriv ditt namn och KTH-mailadress överst på framsidan av inlämnad pdf eller markdownfil. Läs på dina lösningar inför den individuella muntliga redovisningen som kommer att ske kort efter deadline i Zoom, eller på plats för någon i lärarlaget. Tidsbokningen kommer att komma upp nära uppgiftens deadline och det kommer att anslås på Canvas när de har kommit upp. Den muntliga redovisningen tar 10 minuter för dig, men de som bedömer dig har 5 minuters paus mellan varje par av redovisningar.

Det är viktigt att du förbereder dig inför den muntliga redovisningen. För att en uppgift ska godkännas ska du kunna förklara och motivera dina lösningar.

Läs uppgifterna mycket noga så att du inte råkar basera dina lösningar på en missuppfattning. Fråga en lärare på kursen om någon formulering är oklar.

Generella regler för mästarprov såsom vad som krävs för godkänt finns på mästarprovssidan i Canvas. Tänk på att mästarprovet bedöms efter sin sämst lösta uppgift så överarbeta inte enskilda uppgifter förrän alla andra är OK.

För inspiration till hur lösningar kan se ut, se lösningsförslag för syntaxdelar i facit och rättningsmallar från Tentaarkivet i DD1361. Det finns också referenslösningar för gamla syntaxmästarprov länkade i kursöversikten, men tänk på att dessa inte innehåller motiveringar som behövs i en inlämnad lösning!

1. Uttryckssamlingar

Betrakta ett språk av samlingar av uttryck, definierat som följer:
- En samling inleds med och avslutas med hakparentes ("[" och "]").
- Samlingar innehåller en eller flera rader av uttryck, där rader separeras från varandra med semikolon (";").
- Uttryck på samma (abstrakta) rad separeras från varandra med komma (",").
- Icke-negativa heltal är uttryck.
- En eller flera små bokstäver ("a" till "z") är uttryck.
- Två uttryck med plustecken ("+") mittemellan dem är uttryck.

Exempelsträng i språket:

[
 0, x + 3 ;
 7, 3, f + 23 ;
 87, 4, l + ab + 3, 98
]

a) Definiera tokens för uttryckssamlingsspråket med hjälp av reguljära uttryck - högst 10 stycken. Bortse från blanktecken som nyrad och blanksteg.
b) Använd dina tokens från a) som slutsymboler i en BNF-grammatik som precis beskriver uttryckssamlingsspråket. Bortse från blanktecken och begränsa inte antalet uttryck i en rad eller antalet rader. Ange tydligt startsymbolen i din grammatik.
c) Ge en härledning i din grammatik för exempelsträngen.

2. Nästlade klasser

Betrakta ett programspråk med klasser och metoder, där klassdeklarationer kan vara nästlade till ett djup utan övre gräns.

- Deklarationer av klasser inleds med nyckelordet "class", följt av ett namn med en eller flera små bokstäver ("a" till "z"), följt av öppnande hakparentes "{", följt av klassvariabeldeklarationer (om det finns några), följt av metoddeklarationer (om det finns några), följt av deklarationer av nästlade klasser (om det finns några), följt av avslutande hakparentes "}".

- Deklarationer av klassvariabler inleds med nyckelordet "var", följt av ett namn med en eller flera små bokstäver ("a" till "z").

- Deklarationer av metoder inleds med nyckelordet "method", följt av ett namn med en eller flera små bokstäver ("a" till "z"), följt av öppnande parentes "(", följt av tilldelningar (om det finns några), följt av avslutande parentes ")".

- Tilldelningar inleds med ett klassvariabelnamn, följt av ett likhetstecken "=", följt av ett uttryck.

- Uttryck är antingen icke-negativa heltal eller klassvariabelnamn.

Exempelsträng i språket:

class c {
  var x
  var y
  method mc (
   x = 12
  )
  class d {
   var z
   method md (
    z = x
    y = 1
   )
  }
}

a) Definiera tokens för språket med hjälp av reguljära uttryck - högst 12 stycken. Bortse från blanktecken som nyrad och blanksteg.
b) Definera grafiskt en stackautomat (DPDA) som känner igen språket av klassdeklarationer med nästling. Stackautomatens övergångar får bara innehålla tokens från a) och tomma strängen (epsilon), dvs blanktecken bortses från. Märk tydligt ut starttillstånd i din DPDA. Det får inte finnas några begränsningar i antal klassdeklarationer på någon nästlingsnivå.

3. Bokstavsmaskin

Betrakta följande DFA över alfabetet {a,b,c,d,e,f,g}:

a) Definiera ett reguljärt uttryck som beskriver samma språk som denna DFA.
b) Definiera en vänsterrekursiv grammatik i BNF som beskriver samma språk som denna DFA. Märk tydligt ut startsymbolen i din grammatik.

4. Okänt språk

Låt L1 vara ett språk över alfabetet {b,c,d}. Med hjälp av L1 och strängvariablerna x och y definierar vi matematiskt språket L2 över alfabetet {a,b,c,d}:

L2 = { xayb | x är tom eller är en sträng i L1, och y består av ett eller flera c }

För varje scenario nedan, ange den minsta språkklass som nämnts i kursen som du vet med säkerhet att L2 tillhör. Motivera dina svar noggrant.

a) L1 är ett reguljärt språk.
b) L1 är ett kontextfritt språk.
c) Det finns en (terminerande) algoritm som känner igen L1.