Referenslösningar ommästarprov syntax 2023
1. Satsformler
Betrakta ett språk av satsformler, definierat enligt nedan:
- en eller flera stora bokstäver efter varandra ("A" till "Z") är en formel
- "0" är en formel
- "1" är en formel
- om X är en formel, så är detta en formel: "(" följt av X följt av ")"
- om X och Y är formler, så är detta en formel: X följt av "&" följt av Y
- om X och Y är formler, så är detta en formel: X följt av "#" följt av Y
- om X är en formel, så är detta en formel: "~" följt av X
a) Definiera tokens för satsformelspråket med hjälp av reguljära uttryck - högst 10 stycken tokens. Bortse från blanktecken som nyrad och blanksteg, och använd inte blanktecken i tokendefinitionerna.
SVAR:
- FA: "0"
- TR: "1"
- LPR: "("
- RPR: ")"
- NOT: "~"
- AND: "&"
- OR: "#"
- VAR: [A-Z]+
b) Använd dina tokens från a) som slutsymboler i en BNF-grammatik som beskriver formelspråket. Din grammatik måste gå att använda som grund för en parser för formelspråket baserad på rekursiv medåkning och får inte tillåta mer än ett syntaxträd för någon sträng i språket. Märk tydligt ut startsymbolen i din grammatik.
SVAR:
<F> ::= <F1> <F1L>
<F1L> ::= AND <F1> <F1L> | ''
<F1> ::= <F2> <F2L>
<F2L> ::= OR <F2> <F2L> | ''
<F2> ::= LPR <F> RPR | NOT <F> | FA | TR | VAR
Startsymbol: <F>
c) Ge en härledning i din grammatik från b) för följande sträng, och illustrera sedan härledningen med motsvarande syntaxträd. Motivera kort varför strängen inte kan ha flera olika syntaxträd i din grammatik.
A & 1 & ~B # (~D # 0)
SVAR:
Kontrolluppgift för a) och b), lämnas som övning.
2. Operatoralternering
Betrakta ett språk av temporalformler, definierat enligt nedan:
- en eller flera stora bokstäver efter varandra ("A" till "Z") är en formel
- en eller flera små bokstäver efter varandra ("a" till "z") är en formel
- om X och Y är formler, så är detta en formel: X följt av "&" följt av Y
- om X är en formel, så är detta en formel: "μ" (lilla grekiska mu
Links to an external site.) följt av en eller flera små bokstäver ("a" till "z") följt av "(" följt av X följt av ")"
- om X är en formel, så är detta en formel: "ν" (lilla grekiska nu
Links to an external site.) följt av en eller flera små bokstäver ("a" till "z") följt av "(" följt av X följt av ")"
a) Definiera tokens för formelspråket med hjälp av reguljära uttryck - högst 10 stycken tokens. Bortse från blanktecken som nyrad och blanksteg, och använd inte blanktecken i tokendefinitionerna.
SVAR:
- CV: ([A-Z]+|[a-z]+)
- VAR: [a-z]+
- AND: "&"
- LPR: "("
- RPR: ")"
- MU: "μ"
- NU: "ν"
b) Definiera grafiskt en DPDA som känner igen delspråket av temporalformelspråket där:
- endast instanser av en av operatorerna "μ" och "ν" förekommer på varje parentesnästlingsnivå, och
- förekomsten av "μ" eller "ν" alterneras mellan parentesnästlingsnivåerna.
Stackautomatens övergångar får bara innehålla tokens från a) och tomma strängen (epsilon), dvs blanktecken bortses från och ska inte ingå i tokendefinitionerna. Stackautomaten får inte får ha några begränsningar gällande antalet parentesnästlingsnivåer.
Ledning: din DPDA måste till exempel se till att om "μ" förekommer (en eller flera gånger) på den tredje parentesnästlingsnivån i en sträng så förekommer endast "ν" (en eller flera gånger) på den fjärde parentesnästlingsnivån - om den nivån innehåller någon operator överhuvudtaget.
SVAR:
c) Förklara kortfattat varför följande sträng accepteras av din DPDA:
μ y (ν x (A) & ν z (z))
SVAR:
Kontrolluppgift för a) och b), lämnas som övning.
d) Förklara kortfattat varför följande sträng inte accepteras av din DPDA:
ν x (A & ν y (B))
SVAR:
Kontrolluppgift för a) och b), lämnas som övning.
3. Grammatikkomplement
Betrakta språket L över alfabetet {a,b,c,d,e,f,g} som definieras av följande BNF-grammatik med startsymbolen <X>:
<X> ::= <X> <Y> 'c' | <X> <Z> 'd' | 'b'
<Y> ::= <Y1> 'e' <Y> | ''
<Y1> ::= 'f' | 'g'
<Z> ::= <Z> 'a' | 'e'
Definiera grafiskt en DFA som känner igen komplementspråket till L, dvs mängden av alla strängar över det givna alfabetet som inte finns i L.
EJ SVAR (reguljärt uttryck för L):
b((((f|g)e)*c)|(e(a)*d))*
EJ SVAR (DFA för L):
SVAR:
4. Okänt talspråk
Vi betraktar språk över alfabetet {p,q,r}. Givet ett tecken t i alfabetet och ett icke-negativt heltal j så menar vi med t^j strängen som består av precis j förekomster av t.
Låt nu k vara ett okänt men fixt positivt heltal i följande språkdefinitioner:
L1 = { p^n q^n | n <= k }
L2 = { p^n q^k | n > k }
L3 = { p^k q^n | k > n }
L4 = { p^n q^n r^n | n <= k }
L5 = { p^n q^n r^n | n >= k }
För vart och ett av språken L1, L2, L3, L4 och L5, ange om det går att parsa det med rekursiv medåkning. Motivera dina svar noggrant.
SVAR (L1):
Ja.
Följande reguljära uttryck beskriver språket:
(''|pq|ppqq|...|p^k q^k)
Här används p^k för att beteckna det reguljära uttrycket för k stycken p efter varandra. Andra notationer som p{k} används i litteraturen och i vissa regex-bibliotek.
SVAR (L2):
Ja.
Följande reguljära uttryck beskriver språket:
p^k p+ q^k
SVAR (L3):
Ja.
Följande reguljära uttryck beskriver språket:
(p^k|p^k q|...|p^k q^(k-1))
SVAR (L4):
Ja.
Följande reguljära uttryck beskriver språket:
(''|pqr|ppqqrr|...|p^k q^k r^k)
SVAR (L5):
Nej.
Som tas upp i slides i syntaxföreläsning 4 Download slides i syntaxföreläsning 4 så är t ex k = 1 ett kontextberoende språk, och därmed inte i LL-klassen som utgörs av språken som kan parsas med rekursiv medåkning.