Referenslösningar mästarprov syntax 2023

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.

SVAR:

- LBR: "["
- RBR: "]"
- COMMA: ","
- SEMICOLON: ";"
- NUM: (0|[1-9][0-9]*)
- PLUS: "+"
- VAR: [a-z]+

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.

SVAR:

<Exp> ::= <Exp> PLUS <Exp> | NUM | VAR
<Row> ::= <Exp> | <Exp> COMMA <Row>
<Rows> ::= <Row> | <Row> SEMICOLON <Rows>
<Col> ::= LBR <Rows> RBR

Startsymbol: <Col>

c) Ge en härledning i din grammatik för exempelsträngen.

SVAR:

Lämnas som övning.

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.

SVAR:

- CLS: "class"
- VAR: "var"
- NM: [a-z]+

- LBR: "{"
- RBR: "}"
- MTD: "method"
- EQ: "="
- INT: (0|[1-9][0-9]*)
- LPR: "("
- RPR: ")"

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å.

SVAR:

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.

SVAR:

(ab)*(c|d)+(ef|eg)*

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

SVAR:

<G> ::= <X> <Y> <Z>
<X> ::= <X> 'a' 'b' | ''
<Y> ::= 'c' | 'd' | <Y> 'c' | <Y> 'd'
<Z> ::= <Z> 'e' 'f' | <Z>'e' 'g' | ''

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.

SVAR:

L2 tillhör klassen av alla reguljära språk.

Motivering: Om L1 är ett reguljärt språk så finns ett reguljärt uttryck r1 som precis beskriver L1. Vi kan då definiera följande reguljära uttryck som beskriver L2:

(r1)?a(c)+b

b) L1 är ett kontextfritt språk.

SVAR:

L2 tillhör klassen av alla kontextfria språk.

Motivering: Om L1 är ett kontextfritt språk så finns en kontextfri grammatik G1 som precis beskriver L1. Denna grammatik kommer att ha en unik startsymbol i BNF, som vi kan kalla <G1>. Vi kan då definiera följande grammatik G2 i BNF som beskriver L2:

<G2> ::= <G1> 'a' <C> 'b' | 'a' <C> 'b'
<C> ::= 'c' <C> | 'c'

Denna grammatik är kontextfri med startsymbolen <G2>, eftersom G1 är kontextfri och tilläggen i G2 inte påverkar detta.

c) Det finns en (terminerande) algoritm som känner igen L1.

SVAR:

L2 tillhör klassen av alla avgörbara språk.

Motivering: Om det finns terminerande algoritm för att känna igen strängar i L1 kan vi kalla en implementation av denna algoritm för A1. Antag att vi har en sträng s som ska avgöras vara i L2 eller inte.

Vi går igenom s från början efter förekomster av 'a', och har följande möjligheter:
- om det inte finns någon förekomst av 'a' så tillhör inte s språket
- om första tecknet är 'a' så använder vi en DFA byggd från reguljära uttrycket "a(c)+b" på s för att avgöra om s tillhör språket
- om ett tecken som inte är det första tecknet är 'a' och prefixet av s före 'a' enligt A1 inte tillhör L1 så tillhör inte s språket
- om ett tecken som inte är det första tecknet är 'a' och prefixet av s före 'a' enligt A1 tillhör L1 så använder vi en DFA byggd från reguljära uttrycket "a(c)+b" på suffixet av s som börjar med 'a' för att avgöra om s tillhör språket