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.

SVAR:


node(0,node(0,node(17,[]):node(42,[]):[]):node(5,[]):[])

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.

SVAR:

Lämnas som övning.

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.

SVAR:

Den givna grammatiken kan inte parsas med en LL-parser, eftersom vi kräver att en korrekt parser terminerar (lämnar ett svar ja/nej för alla ändliga strängar). Vi kan dock ändra grammatiken så att parsning av listor ger bottnande rekursion, och vi har då en LL-grammatik. Så språket är i LL-språkklassen.

En möjlig LL-grammatik för språket:


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

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.

SVAR:

(a|b)*cd(e)+

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.

SVAR:

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.

SVAR:

EM (empty): [' ' '\t' '\n' '\r']+
BO (begin outer): "/+"
EO (end outer): "+/" (
BI (begin inner): "/-"
EI (end inner): "-/"
WD (word): ['A'-'Z' 'a'-'z']+

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.

SVAR:

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å härledningskedjor för strängen som följer grammatiken och har olika syntaxträd. Märk tydligt upp var härledningarna skiljer sig åt.

SVAR:

"skip; skip; skip"

- idé härledning 1: <Stm> -> ... -> skip; (skip; skip)

- idé härledning 2: <Stm> -> ... -> (skip; skip); skip

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.

SVAR:

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

Startsymbol: <Stms>

Tvetydigheten från tidigare undviks genom separationen mellan <Stms>, <Stm>, och <StmRest>.