Referenslösningar ommästarprov syntax 2022
1. Nummerteckenspråk
Betrakta ett språk som bara består av nummertecken ("#", tokennamn Hash) separerade med nyrad (tokennamn Newline).
Varje rad av nummertecken ingår i precis ett par av rader räknat från början av ett ord i språket, så t. ex. ingår den första raden i ett par med den andra raden, och den femte raden i ett par med den sjätte raden, osv.
För raderna x och y i varje par av rader gäller följande: om x har n stycken förekomster av Hash så har y antingen n stycken Hash eller n+1 stycken Hash eller n+2 stycken Hash.
Exempelsträng i språket:
#####
######
##
##
Definiera grafiskt en stackautomat (DPDA) som känner igen precis detta språk. Stackautomaten får bara ha övergångar som innehåller Hash, Newline eller tomma strängen (Epsilon). Märk tydligt ut starttillstånd och accepterande tillstånd i din DPDA.
SVAR:
2. Grammatikfunktion
Låt F vara en (beräkningsbar, matematisk) funktion som tar en grammatik G i en viss form och returnerar ett booleskt värde så att F(G) = true om och endast om det finns ett reguljärt uttryck som beskriver språket som definieras av G.
För varje möjligt värde för F(G), dvs. F(G) = true, F(G) = false, ange vad detta innebär för språket som definieras av G i förhållande till följande språkklasser, dvs. ange om språket tillhör klassen, språket inte tillhör klassen, eller om båda alternativen är möjliga:
A. Klassen av alla språk som kan parsas genom rekursiv medåkning.
B. Klassen av alla språk som känns igen av någon DFA.
C. Klassen av alla språk som känns igen av någon DPDA.
Motivera dina svar noggrant.
SVAR:
- A + F(G) = true: L tillhör klassen, eftersom L tillhör klassen av reguljära språk, som är en del av klassen som kan parsas med rekursiv medåkning, dvs LL-språkklassen
- A + F(G) = false: det går inte att säga om L tillhör klassen, eftersom det finns språk som varken tillhör klassen av reguljära språk eller tillhör klassen som parsas med rekursiv medåkning
- B + F(G) = true: L tillhör klassen, eftersom L tillhör klassen av reguljära språk, som är precis klassen av språk som känns igen av någon DFA
- B + F(G) = false: L tillhör inte klassen, eftersom L inte tillhör klassen av reguljära språk, som är precis klassen av språk som känns igen av någon DFA
- C + F(G) = true: L tillhör klassen, eftersom L tillhör klassen av reguljära språk, som är en del av klassen av språk som känns igen av någon DPDA, dvs LL-språkklassen
- C + F(G) = false: det går inte att säga om L tillhör klassen, eftersom det finns språk som varken tillhör klassen av reguljära språk eller kan kännas igen av någon DPDA
| språket tillhör klassen | språket tillhör ej klassen | går inte att säga |
---------------|-------------------------|----------------------------|-------------------|
A + F(G)=true | X | | |
A + F(G)=false | | | X |
B + F(G)=true | X | | |
B + F(G)=false | | X | |
C + F(G)=true | X | | |
C + F(G)=false | | | X |
3. Minusaritmetik
Betrakta en grammatik som beskriver ett språk med minusuttryck över tal:
<Exp> ::= <Exp> Minus <Exp> | Num | LPar <Exp> RPar
Startsymbol: <Exp>
Tokens i språket:
- Minus: "-"
- Num: [0-9]+
- LPar: "("
- RPar: ")"
A. Definiera grafiskt en ändlig automat (DFA) som känner igen minusuttryck från språket som har flera härledningar med olika syntaxträd i grammatiken. Din DFA får bara göra övergångar på tokens i språket. DFA:n behöver inte känna alla möjliga minusuttryck med flera härledningar, men den får inte vara begränsad till att känna igen minusuttryck som har ett visst förbestämt antal tokens. Märk tydligt ut starttillstånd och accepterande tillstånd i din DFA.
SVAR:
B. Ge ett exempel på ett minusuttryck som din DFA känner igen, både som sträng och tokensekvens, och ge två härledningar med olika syntaxträd i grammatiken för uttryckets tokensekvens. Ange vilken ickeslutsymbol som väljs i varje härledningssteg, och gör det tydligt var dina två härledningar skiljer sig åt.
SVAR: lämnas som övning.
4. Utökningar av BNF
I olika utökningar av den grundläggande BNF-syntaxen för grammatiker används ofta Kleenestjärnan ("*"), frågetecknet ("?"), och plustecknet ("+") för att beskriva upprepningar av symboler, och hakparenteser ("[" och "]") för att ange omfånget för dessa operatorer. Kleenestjärnan betyder som vanligt noll eller flera förekomster, frågetecknet noll eller en förekomst, och plustecknet en eller flera förekomster.
A. För varje operator (*, ? och +), förklara kortfattat hur en grammatik som använder den operatorn kan konverteras till en grammatik som inte använder operatorn men beskriver samma språk.
SVAR:
Produktioner med "?" kan översättas till två produktioner, en produktion med vad som finns i omfånget av "?", och en som inte finns i omfånget av "?"
exempel:
<Stm> ::= If <Exp> Then <Stms> [ Else <Stms> ]? End
ersätts med
<Stm> ::= If <Exp> Then <Stms> End | If <Exp> Then <Stms> End <Stms> End
Produktioner med "*" kan t. ex. ersättas med en ny slutsymbol som definieras som antingen tom (Epsilon) eller en förekomst och upprepning av slutsymbolen.
exempel:
<Stms> ::= <Stm> [SemiColon <Stm>]*
ersätts med
<Stms> ::= <Stm> <StmRest>
<StmRest> ::= SemiColon <Stms> | Epsilon
Produktioner med "+" kan t. ex. ersättas med en ny slutsymbol som definieras som antingen en enda förekomst av det som är i omfånget för "+", eller en förekomst tillsammans med en upprepning av slutsymbolen.
exempel:
<ClassDecl> ::= Class Ident Extends [ Ident ]+ LBrack RBrack
ersätts med
<ClassDecl> ::= Class Ident Extends <IdentList> LBrack RBrack
<IdentList> ::= Ident <IdentList> | Ident
Det är även möjligt att använda tomma strängen för en ny ickeslutsymbol.
B. Använd dina ansatser för att konvertera följande grammatik till en grammatik som inte använder operatorerna (och inte heller "[" eller "]") men som beskriver samma språk:
<Exp> ::= Var | <Exp> Lt <Exp>
<Stm> ::= Skip | Var Assign Num | If <Exp> Then <Stms> [ Else <Stms> ]? End
<Stms> ::= <Stm> [SemiColon <Stm>]*
<MethodDecl> ::= Ident LPar [ Var ]* RPar LBrack <Stms> RBrack
<ClassDecl> ::= Class Ident [ Extends [ Ident ]+ ]? LBrack [ <MethodDecl> ]+ RBrack
Startsymbol: <ClassDecl>
Tokens:
- Skip: "skip"
- SemiColon: ";"
- Var: [A-Za-z]+
- Assign: ":="
- Num: [0-9]+
- Ident: [A-Za-z]+
- If: "if"
- Then: "then"
- Else: "else"
- End: "end"
- Lt: "<"
- LPar: "("
- RPar: ")"
- LBrack: "{"
- RBrack: "}"
- Extends: "extends"
- Class: "class"
SVAR:
<Exp> ::= Var | <Exp> Lt <Exp>
<Stm> ::= Skip | Var Assign Num | If <Exp> Then <Stms> End | If <Exp> Then <Stms> Else <Stms> End
<Stms> ::= <Stm> <StmRest>
<StmRest> ::= SemiColon <Stms> | Epsilon
<MethodDecl> ::= Ident LPar <VarList> RPar LBrack <Stms> RBrack
<VarList> ::= <Var> <VarList> | Epsilon
<MethodDeclList> ::= <MethodDecl> <MethodDeclList> | <MethodDecl>
<IdentList> ::= Ident <IdentList> | Ident
<ClassDecl> ::= Class Ident LBrack <MethodDeclList> RBrack | Class Ident Extends <IdentList> LBrack <MethodDeclList> RBrack
C. Ge en exempelsträng i språket som definieras av grammatikerna. Representera även strängen som en tokensekvens och ge en härledning i den nya grammatiken för den sekvensen från startsymbolen.
SVAR:
Class MyClass Extends OtherClass {
myMethod ( x ) {
if x then
x := 3
else
x := 4
end
}
}
5. Komplementspråk
På matematisk nivå definierar vi språket L med hjälp av ordvariabeln w och tecknen a, b och c:
L = { wc | w är tom eller består av ett jämnt positivt antal a följt av ett jämnt positivt antal b }
Betrakta nu komplementspråket till L, dvs. mängden av alla ord som inte finns i L, över alfabetet med tecknen a, b och c. Ingår detta komplementspråk till L i klassen av alla reguljära språk? Motivera ditt svar noggrant.
SVAR:
Reguljära språk är slutna under komplement, så det räcker med att ge ett reguljärt uttryck för L:
((aa)+(bb)+)?c