Seminarium 7 - Experimentering

Kapitel att läsa inför seminariet

• Interpretator och kompilator

Denna sida visar en del av det som kommer att diskuteras på seminariet. Ofta tar handledarna också upp andra uppgifter som inte behöver något specifikt studentmaterial och då syns dessa uppgifter inte på sidan.

Uppgift: Extended Backus-Naur Form

I denna uppgift övar vi på att läsa EBNF för att lättare kunna jobba med labb 6.

Instruktioner: Extended Backus-Naur Form

Givet är två språk i Extended Backus-Naur Form (EBNF). Orden i dessa språk består enbart av olika kombinationer av bokstäverna 'a' och 'b'. Dessa är alltså terminalerna (som i "avslutande").

Identifierare som S är så kallade 'icke-terminaler'. Icke-terminalen S är här startsymbolen för språket. För att få fram ett ord måste samtliga icke-terminaler ersättas med terminaler. I första exemplet nedan kan t.ex. S bli antingen 'a' följt av A eller 'b' följt av A (tecknet '|' betyder 'eller'). Då försvinner icke-terminalen S men man har ändå minst en icke-terminal kvar. Fortsätter man att applicera reglerna fler och fler gånger kan man till slut "bli av med" alla icke-terminaler och då har man ett ord som ingår i språket.

Vissa sekvenser av bokstäverna ingår i språken (kan "produceras" genom att man applicerar reglerna), vissa gör det inte.

Den här sortens språk studeras vidare i kursen Formella språk och automatateori (master-kurs för D, obligatorisk kurs för U)!

Exempel

S = "a", A | "b", A ;
A = "a" | "b" | "" ;

Detta är ett ändligt språk, som bara innehåller följande teckensekvenser: 'a', 'aa', 'ab', 'b', 'ba', 'bb' (utan citattecknen)

Uppgifter

Ange vilka sekvenser (ord) som ingår i följande språk.

1

S = 'a', A | 'b', B ;
A = 'a', B | '' ;
B = 'a' | 'b' ;

2

S = 'a', S, 'a' | 'b', S, 'b' | 'a' | 'b' | '' ;

Uppgift: Identifiera ord

Skriv pythonkod som identifierar om en given sträng ingår i språk 1 respektive språk 2 i uppgiften 'Extended Backus-Naur Form'. Den metod som används behöver inte fungera för alla sorters språk som kan beskrivas i EBNF.

Uppgift: Prefix

Skriv en funktion contains_prefixes som tar två listor med strängar som parametrar. Funktionen ska returnera True om varje sträng i den första listan är ett prefix till någon av strängarna i den andra listan.

Körexempel:

>>> contains_prefixes(["hej"], ["hejsan", "asdfasdf"])
True
>>> contains_prefixes(["hej", "sdf"], ["hejsan", "asdfasdf"])
False

Uppgift: Primtal i Fibbonacci-sekvensen

Skriv en funktion som returnerar en lista med tal i fibonacci-serien som dessutom är primtal.

Funktionen ska ta ett heltal n som på ett eller annat sätt avgör hur många tal som beräknas -- för större värden på n ska man få minst lika många primtal som för mindre. Du bestämmer själv exakt hur n ska tolkas.

För att testa funktionen bör du inte använda alltför stora värden på n då större fibonaccital tar lång tid att primtalstesta.

De 10 första primtalen i fibonacci-sekvensen är följande:

[3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437, 2971215073]

Uppgift: Ihopslagning

Skriv en funktion som slår ihop två sorterade listor till en sorterad lista.

Uppgift: Relativ sökväg

Skriv en funktion som givet två absoluta sökvägar på ett unix-system skapar en relativ sökväg från den ena till den andra.

Exempel

'/Users/Ingegerd/python/work'
'/Users/Ingegerd/haskell/work'
=>
'../../haskell/work'

'/Users/Ingegerd/'
'/Users/Ingegerd/haskell/work'
=>
'haskell/work'