KOI: Instuderingsfrågor inför tentan

Frågorna på tentan kommer att likna de nedanstående.

Formlerna för vänsterfaktorisering och eliminering av vänsterrekursion kommer att finnas med på tentan.

Viktigast

Följande frågor måste man kunna svara på, dvs om man svarar helt fel på någon av dem blir man underkänd på tentan.
  1. Man brukar dela in en kompilator i ett antal faser. Vad är en fas?
  2. Varför delar man upp kompilatorn i faser?
  3. Vad heter de olika faserna?
  4. Beskriv varje fas med några meningar.
  5. Vad är in- och utdata för respektive fas?

Fler frågor

Följande frågor bör man kunna svara på. De ger poäng, och man ska ha ett visst antal poäng (ungefär hälften) för att bli godkänd, precis som det ofta är på andra tentor.

När det står "grammatiken ovan", "följande programavsnitt" och så vidare, är tanken att man ska kunna besvara den typen av frågor, med olika givna grammatiker och programavsnitt. Titta på de gamla tentorna på hemsidan (både gamla och nya kursplanen) för att få konkreta exempel.

  1. Ange vilka terminaler, dvs typer av tokens, som behövs för att man ska kunna skriva en grammatik för följande enkla språk.
  2. Skriv en grammatik för följande enkla språk.
  3. Rita upp parse-trädet för den här inmatningen, givet grammatiken ovan.
  4. Skriv en prediktiv recursive-descent-parser i något C-liknande språk för det språket. (Kan innefatta vänsterfaktorisering och eliminering av vänsterrekursion.)
  5. Skriv en prediktiv recursive-descent-parser i något C-liknande språk för den här grammatiken. (Kan innefatta vänsterfaktorisering och eliminering av vänsterrekursion.)
  6. Beskriv det språk som följande grammatik definierar.
  7. Ange tio olika strängar som ingår i det språk som beskrivs av följande grammatik.
  8. Är den här grammatiken tvetydig?
  9. Här är några fel i källkoden som upptäckts av kompilatorn. I vilken fas är det troligt att respektive fel upptäcktes?
  10. Översätt följande programavsnitt i ett C-liknande språk till ett abstrakt syntaxträd, genom att rita upp trädet.
  11. Översätt följande programavsnitt i ett C-liknande språk till postfixkod för en stackmaskin.
  12. Översätt följande programavsnitt i ett C-liknande språk till treadresskod.
  13. Skriv ett reguljärt uttryck ("regexp") som matchar följande.
  14. Här är lite treadresskod. Dela in koden i basic blocks.
  15. Optimera koden med hjälp av de vanliga metoderna för optimering, såväl inom ett enskilt basic block som i flera block. Beskriv inte bara resultatet, utan de olika stegen, gärna med namn.
  16. Flera olika typer av optimeringar kan göras på koden inuti ett enskilt basic block. Vilka? Beskriv dem, och använd treadresskod för att ge exempel på hur de fungerar.
  17. Här är ett C-program. Ett programs adressrymd kan delas upp i fyra delar: programkod och konstanter, statiska data, heap och stack. Rita upp hur stacken (med aktiveringsposter), heapen och statiska data ser ut när programkörningen kommer till kommentaren "Här!".
  18. Skriv en grammatikregel för den här satsen från språket C.
  19. Skapa ett syntaxstyrt översättningsschema, med produktioner och semantiska aktioner, för översättning av den satsen till mellankod. Välj själv om du vill generera ett abstrakt syntaxträd, postfixkod för en stackmaskin eller treadresskod. (Tala också om vilket du valde.)
  20. Antag att minnet innehåller dessa dataobjekt. Vi använder skräpsamlingsmetoden "mark and sweep". Vilka av objekten kommer att markeras i markeringsfasen?
  21. Vilka av objekten kommer att tas bort i sopfasen?
  22. Vi använder referensräkning. Ange värdet på referensräknaren för vart och ett av dataobjekten.
  23. Jämför mark and sweep med referensräkning. Vilja fördelar och nackdelar har de?
  24. Förklara kort följande begrepp från kompilatortekniken:
    1. aktiveringspost (på engelska: "activation record")
    2. anropskonventioner (på engelska: "call sequence")
    3. anropsstack
    4. basic block
    5. Bison
    6. call by value
    7. copy propagation
    8. DAG
    9. deterministisk ändlig tillståndsmaskin
    10. döda data ("dead data")
    11. död kod ("dead code")
    12. dynamisk
    13. eliminering av vänster-rekursion
    14. fas (på engelska: "phase")
    15. FIRST()-konflikt
    16. Flex
    17. front end (på engelska: "front end")
    18. grammatik
    19. heap
    20. intermediärkod
    21. interpretator
    22. kodgenerator
    23. kompilator
    24. konservativ skräpsamling
    25. länkare
    26. Lex
    27. lexem
    28. lexikalisk analys
    29. literal (på engelska: "literal")
    30. målprogram
    31. målspråk
    32. mark and sweep
    33. mark bit (vid skräpsamling)
    34. markeringsfas (vid skräpsamling)
    35. maskinberoende optimering
    36. maskinoberoende optimering
    37. mellankod
    38. mellankodsgenerator
    39. namnekvivalens (på engelska: "name equivalence")
    40. nyckelhålsoptimering ("peep-hole optimization")
    41. onåbara data ("unreachable data")
    42. optimering, kodoptimering
    43. parser
    44. parser-generator (på engelska: "parser generator")
    45. parseträd (ibland kallad "konkret syntaxträd")
    46. pass (på engelska: "pass")
    47. postfixkod
    48. referensräkning ("reference counting")
    49. registerallokering
    50. reguljärt uttryck
    51. reserverat ord
    52. rotmängd ("root set")
    53. run-time-omgivning
    54. scanner
    55. semantisk analys
    56. shift-reduce-konflikt
    57. skräpsamling ("garbage collection")
    58. stackmaskin
    59. statisk
    60. statiska data
    61. strukturekvivalens (engelska: "structural equivalence"), som är motsatsen till namnekvivalens (engelska: "name equivalence")
    62. symboltabell (engelska: "symbol table")
    63. syntaktisk analys
    64. syntaxträd (ibland kallad "abstrakt syntaxträd")
    65. token
    66. treadresskod
    67. tvetydig grammatik
    68. tvetydighet
    69. typsystem
    70. uppsamlingsfas (vid skräpsamling, på engelska: "sweep phase")
    71. vänsterfaktorisering
    72. Yacc
  25. Varför kallas kompilatorer för "kompilatorer"?

Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), 20 oktober 2014