Seminarium 7 - En sak i taget

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 ska studenterna få öva 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.

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

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.