Kompilatorer och interpretatorer
för Dataingenjörsprogrammet
måndag 17 oktober 2005 kl 08:00 - 13:00 i L0001
Hjälpmedel: | Inga hjälpmedel. |
Poängkrav: |
Maximal poäng är 60.
För betyget 3 krävs 30 poäng. För betyget 4 krävs 40 poäng. För betyget 5 krävs 50 poäng. |
Resultat: | Meddelas på kursens hemsida senast måndag 7 november 2005. |
Visning och frågestund: |
Måndag 7 november 2005 kl 12:00-12:30 i T2220.
Därefter kan tentorna hämtas på expeditionen. |
Examinator och jourhavande: | Thomas Padron-McCarthy, telefon 070-7347013. |
a) den lexikaliska analysen ("scannern")
b) den syntaktiska analysen ("parsern")
c) den semantiska analysen
S -> X Y Z X -> a | b Y -> Z | c Z -> d
a) (2p) Rita upp parse-trädet för strängen bdd.
b) (3p) Vilka strängar, förutom bdd, kan genereras av denna grammatik?
c) (1p) Vad innebär det att en grammatik är tvetydig (engelska: "ambiguous")?
d) (2p) Är grammatiken ovan tvetydig? Motivera svaret!
e) (2p) Just den här grammatiken definierar ett språk som också kan beskrivas med ett reguljärt uttryck. Skriv ett reguljärt uttryck som beskriver språket!
f) (2p)
Skulle man kunna beskriva samma språk med ett annat
reguljärt uttryck?
Om ja: Ange ett sådant alternativt reguljärt uttryck.
Om nej: Förklara varför man inte kan det.
b) (2p) Visa med ett exempel hur man kan eliminera, dvs ta bort, vänsterrekursion från en grammatik.
c) (1p) Hur påverkas det språk som grammatiken beskriver av att man tar bort vänsterrekursionen från den grammatiken?
d) (2p) I vilka sammanhang behöver man ta bort vänsterrekursion? Varför behöver man göra det?
e) (2p) Man kan ha semantiska aktioner instoppade i grammatiken. Förklara, med exempel, hur man hanterar dessa vid eliminering av vänsterrekursion.
Det reguljära uttrycket a*b[cd] beskriver ett språk som består av strängar som:
b) (7p) Skriv den prediktiva recursive-descent-parsern i ett språk som åtminstone liknar C, Java eller Pascal. Du behöver inte skriva exakt korrekt programkod, men det ska framgå vilka procedurer som finns, hur de anropar varandra, och vilka jämförelser med tokentyper som görs. Du kan anta att det finns en funktion som heter scan, och att den returnerar typen på nästa token.
Översätt ovanstående programavsnitt tillif (x < 7 + y) { x = 9 - x - y; } else { while (x > 10) { z = x + 1; x = 2 * x * (y - 1); } }
a) (3p) ett abstrakt syntaxträd (genom att rita upp trädet!)
b) (3p) postfixkod för en stackmaskin
c) (4p) treadresskod
Ett exempel, där vi först deklarerar de tre variablerna f, i och s:
Här är en grammatik för språket:f : flyttal; i : heltal; s : sträng; i = 17; i + i; // Resultat: heltalet 34 i + 3; // Resultat: heltalet 20 2 + 5; // Resultat: heltalet 7 14; // Resultat: heltalet 14 f = 3.14; f + f; // Resultat: flyttalet 6.28 2.1 + f; // Resultat: flyttalet 5.24 f = 17; // typfel: f ska innehålla ett flyttal f = "hej"; // typfel: f ska innehålla ett flyttal 3.5 + 12; // typfel: flyttal + heltal ej tillåtet i + 0.5; // typfel: heltal + flyttal ej tillåtet "hej" + "hopp" // typfel: sträng + sträng ej tillåtet
Visa hur kompilatorn kan hantera typinformation, i en syntaxstyrd översättning och i symboltabellen, så att den upptäcker typfelen i exemplet ovan.S -> Deklarationslista Satslista Deklarationslista -> Deklarationslista Deklaration | empty Satslista -> Satslista Sats | empty Deklaration -> id ":" Typ ";" Typ -> "flyttal" | "heltal" | "sträng" Sats -> Uttryck ";" | id "=" Uttryck ";" Uttryck -> Konstant | id | Uttryck "+" Uttryck Konstant -> heltalskonstant | flytalskonstant | strängkonstant