Gammalt Mästarprov Syntax 2022

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.

Skriftliga lösningar ska lämnas in i Canvas (som PDF; om du skriver med LaTeX, använd pdflatex för att göra om det till en pdf; Om du skriver i Word, välj spara som och välj filformatet pdf; inskannade handskrivna lösningar går också bra men LaTeX är bäst) senast Deadline. Det är viktigt att du lämnar in i tid! Om du inte ser någon inlämningsknapp på denna sida så ska du kontrollera att du är inloggad i Canvas. Klicka i så fall på inloggningsikonen i den gråa vänstermenyn.

Skriv ditt namn och KTH-adress överst på framsidan av lösningarna. Läs på dina lösningar inför den individuella muntliga redovisningen som kommer att ske kort efter deadline 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 innan varje redovisning.

Det är viktigt att du förbereder dig inför den muntliga redovisningen. Se till att ha bra koll på materialet som gås igenom i uppgifterna.

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ågot är oklart.

Generella regler för mästarprov såsom vad som krävs för godkänt finns på mästarprovssidan i Canvas.

Som exempel på hur kod-delen av en inlämningsuppgift kan se ut, se facit och rättningsmallar från Tentaarkivet i DD1361Länkar till en externa sida., till exempel 2017-09-18 som gicks igenom på föreläsningen. Som exempel på hur en teorifråga kan besvaras, se facit och rättningsmallar från tentaarkivet i DD1362Länkar till en externa sida. till exempel juni 2021.

Lycka till!

1. Multiträd

I kursen använde vi följande grammatik för binärträd i BNF:

<BinTree> ::= Leaf LPar Num RPar
  | Branch LPar <BinTree> Comma <BinTree> RPar

Grammatiken har följande slutsymboler (tokens):
- Leaf: "leaf"
- Branch: `"branch"`
- Num: [0-9]+
- LPar: "(", RPar: ")", Comma: ","

Exempelsträng: "branch(branch(leaf(17),leaf(42)),leaf(5))"

Vi definierar nu en grammatik för träd med godtyckligt antal grenar på varje nivå:

<MultiTree> ::= Node LPar Num Comma <MultiTrees> RPar
<MultiTrees> ::= NoTrees | <MultiTree> Colon <MultiTrees>

Startsymbol: <MultiTree>

Följande tokens tillkommer:
- Node: "node"
- Colon: ":"
- NoTrees: "[]"

A. Uttryck exempelsträngen ovan som en sträng i den nya trädgrammatiken. Alla tal (Num) från binärträdet ska finnas representerade i det nya trädet på motsvarande position, och summan av alla tal ska vara densamma som i binärträdet.

B. Visa att din sträng tillhör språket som definieras av den nya grammatiken genom att ge en härledningskedja för strängen, och illustrera härledningen som ett syntaxträd. 

2. Talserier

Betrakta följande grammatik som beskriver talserier:

<Nums> ::= Num <NumsAux> | NoNums
<NumsAux> ::= <NumsAux> SemiColon Num | Epsilon

Startsymbol: <Nums>

Tokens:

- Num: [0-9]+
- SemiColon: ";"
- NoNums: "_"
- Epsilon: tomma strängen

Kan grammatiken parsas med en LL-parser, och tillhör språket som definieras av grammatiken LL-språkklassen? Motivera dina svar noggrant.

3. Ändliga automater

På matematisk nivå definierar vi språket L med hjälp av ordvariablerna w och v och tecknen a, b, c, d och e:

L = { wcdv | w är tom eller innehåller bara a och b, och v består av ett eller flera e }

A. Definiera ett reguljärt uttryck som precis beskriver L.

B. Betrakta språket L+ som innehåller alla ord i L upprepade en eller flera gånger. Definiera grafiskt en ändlig automat (DFA) som precis beskriver L+. Din DFA får inte ha fler än 15 tillstånd.

4. Stackautomater

Vi betraktar en delmängd av ett programspråk som berör kommentarer.

- Yttre kommentarer:
  - inleds med "/+"
  - avslutas med "+/"
  - inledningen följs av en rubrik som bara består av bokstäver i ASCII
  - innehåller förutom inledning, rubriken, inre kommentarer och avslut bara blanktecken
  - kan ej nästlas, måste avslutas innan nya yttre kommentarer kan påbörjas
  - mellan två yttre kommentarer förekommer bara blanktecken
- Inre kommentarer:
  - förekommer endast inuti yttre kommentarer
  - inleds med "/-"
  - avslutas med "-/"
  - kan innehålla blanktecken och bokstäver i ASCII
  - kan nästlas, men inledningar och avslut måste vara balanserade

Exempelsträng:

/+ Programmeringsparadigm

  /- Kursen har flera delar
     /- funktionsdelen -/
     /- inetdelen -/
     /- syntaxdelen -/
  -/

+/
/+ Algoritmer
  /- Sortering /- Snabbsortering -/ -/
+/

A. Definiera slutsymboler (tokens) för kommentarspråket. Du kan använda reguljära uttryck i definitionerna och du får maximalt definiera 15 tokens.

B. Definiera grafiskt en stackautomat (DPDA) som precis känner igen kommentarspråket och gör övergångar enbart med dina tokens eller tomma strängen. Stackautomaten får maximalt ha 20 tillstånd.

5. Tvetydig grammatik

Betrakta följande programspråksgrammatik:

<Stm> ::= Skip | <Stm> SemiColon <Stm> | Var Assign Num | If <Exp> Then <Stm> Else <Stm> End
<Exp> ::= Lt LPar <Exp> Comma <Exp> RPar | Var | Num

Startsymbol: <Stm>

Tokens:

- Skip: "skip"
- SemiColon: ";"
- Assign: ":="
- If: "if"
- Then: "then"
- Else: "else"
- End: "end"
- Lt: "lt"
- Comma: ","
- LPar: "("
- RPar: ")"
- Num: [0-9]+
- Var: [A-Za-z]+

A. Visa att grammatiken är tvetydig genom att definiera en exempelsträng med som mest 30 tokens som tillhör språket, och ge två olika härledningskedjor för strängen som följer grammatiken. Märk tydligt upp var härledningarna skiljer sig åt.

B. Definiera en ny LL-grammatik i BNF som beskriver precis samma språk som den ursprungliga grammatiken, men som inte är tvetydig. Du får ändra ickeslutsymboler, men du måste ha samma slutsymboler. Ange tydligt startsymbol för din grammatik, och förklara varför din exempelsträng bara har en enda härledning i grammatiken.