Tenta januari 2025

Question 1

Vad ingår i symboltabellen?

Answer 1

• The lexemeitself
• Corresponding token
  *Its semantic component(e.g.,variable,operator, constant, functions, procedure, etc.)
• Datatype
• Pointers to oth erentries(when necessary)

Namn: Identifierare
Datatyp: Exempelvis int, float, string, etc.
Scope: Omfattning, t.ex. global, lokal eller block.
Minnesadress: Var identifieraren lagras.
Attribut: Extra information, som storlek, parametrar, och modifierare (t.ex. const, static).
Referenser: Var identifieraren används i koden.
Synlighet: Åtkomstspecifikationer

Question 2

The interaction between the Symbol Table and the phases of a compiler

Answer 2

Virtually every phase of the compiler will use the symbol table.

Lexikal analys använder symboltabellen för att lägga till identifierare när de upptäcks.
Syntaxanalys använder symboltabellen för att verifiera att identifierare används korrekt enligt språkets syntax.
Semantisk analys använder symboltabellen för att kontrollera typer, scope och deklarationer av identifierare.
Generering av mellanliggande kod använder symboltabellen för att hämta information om identifierares typer och adresser.
Optimering använder symboltabellen för att analysera och eliminera överflödig kod eller redundant användning av identifierare.
Kodgenerering använder symboltabellen för att tilldela minnesadresser eller register till identifierare.

• The initialization phase will place keywords, operators, and standard identifiers in it.
• The scanner will place user-defined identifiers and literals in it and will return the corresponding token.
• The parser uses these token to create the parse tree, the product of the syntactic analysis of the program.
• The semantic action routines place data type in its entries and uses this information in performing basic type- checking.
• Theintermediatecodegenerationphaseuse pointers to entries in the symbol table in creating the intermediate representation of the program
• Theobjectcodegenerationphaseusespointersto entries in the symbol table in allocating storage for its variables and constants, as well as to store the addresses of its procedures and functions.

Question 3

Vilka är alla kompilatorns faser i ordning

Answer 3

Lexical analyzer(Scanner), Parser, Semantic analyzer, Intermediate code generation, Machine independent code optimizer, Code generator, Machine dependent code
optimizer

Question 4

Ge skillnad på en machine independent optimiering och en machine dependant optimering:

Answer 4

Machine Independent Optimization
Fokus ligger på att förbättra koden utan att ta hänsyn till den specifika maskinarkitekturen.
Exempel: Eliminering av död kod, loopunrolling, och gemensam subuttryckseliminering.

Machine Dependent Optimization
Fokus ligger på att anpassa koden för att utnyttja den specifika maskinens arkitektur och egenskaper.
Exempel: Tilldelning av register, utnyttjande av specifika CPU-instruktioner och pipelineoptimering.

Question 5

Input Output Faserna

Answer 5

L: Source code as a sequence of characters -> tokens (keys, id, symbols)
P: Tokens -> Parse tree (abstract syntax tree)
S: Parse Tree -> Annoted Syntax Tree (type checks, scope info)
I: Annoted syntax tree -> Intermediate Code Representation (simple machine independent)
IO:Optimized intermediate representation
CG: Target Code in assembly(machine code)
DO: Optimized assembly (machine)

Question 6

Kodens utveckling från start till slut i kompilator

Answer 6

Source code as sequence of characters
Tokens
Parse Tree (Abstract syntax tree)
Annoted Syntax Tree
Intermediate Code Representation
Optimized IR
Target code
Optimized Target Code

Question 7

Copy propagation

Answer 7

Copy propagation är en optimeringsteknik där onödiga kopior av variabler tas bort. Om en variabel bara används som en kopia av en annan, ersätts den med originalvariabeln

t1 = a
t2 = t1
c = t2 + b

->

c = a + b

Question 8

Syntax-directed translation table

Answer 8

Produktionerna och dess regler

Question 9

Skillnad på proceduranrop proceduraktivering

Answer 9

Proceduranrop är när ett program anropar en funktion eller procedur för att exekvera den, medan proceduraktivering är den faktiska processen när kontrollen övergår till den anropade proceduren och dess exekvering börjar.

Question 10

Skillnad på kontrolllänk och processlänk

Answer 10

En kontrolllänk är en länk som används för att hålla reda på var exekveringen ska fortsätta efter att en procedur har avslutats.
En accesslänk är en länk som kopplar till de lokala variablerna i en procedur eller funktion för att ge åtkomst till dem under exekveringen.

Question 11

Statisk och dynamisk namnuppslagning

Answer 11

Statisk namnuppslagning sker vid kompileringstid, där variabelnamn och deras adresser bestäms innan programmet körs.
Dynamisk namnuppslagning sker vid körningstid, där variabelnamn och deras adresser bestäms under programmets exekvering beroende på programmets tillstånd.

Question 12

Call by Value:

Answer 12

Skickar en kopia av argumentet till funktionen.

Call by Need: Liknar call by name, men utvärderar uttrycket bara när det behövs.
Macro Expansion: Ersätter ett makro med dess definition vid preprocessor-steget.

Question 13

Call by Reference:

Answer 13

Skickar en referens till argumentet, vilket gör att funktionen kan ändra det.

Question 14

Call by Name:

Answer 14

Skickar uttrycket till funktionen för att utvärdera det varje gång det används.

Question 15

Call by Need:

Answer 15

Liknar call by name, men utvärderar uttrycket bara när det behövs.

Question 16

Macro Expansion:

Answer 16

Ersätter ett makro med dess definition vid preprocessor-steget.

Question 17

Skärpsamling

Answer 17

Skräpsamling (garbage collection) är en automatisk process som frigör minne genom att identifiera och ta bort objekt eller resurser som inte längre används eller är åtkomliga i ett program. Detta förhindrar minnesläckor genom att säkerställa att oanvänd minnesresurs återanvänds.

Question 18

Skärp

Answer 18

Ej nåbar. data

Question 19

Mark and sweep

Answer 19

Mark and Sweep är en skräpsamlingsalgoritm som består av två faser. I markeringfasen markeras alla objekt som kan nås från aktiva referenser som “levande”. Under sopningsfasen tas alla objekt som inte är markerade bort och deras minne frigörs. Processen är en stop-the-world-operation, vilket innebär att programmet stannar för att säkerställa att inga referenser ändras under markeringen och sopningen. Algoritmen kan vara ineffektiv eftersom den måste genomgå hela minnet varje gång och stoppa exekveringen, vilket kan orsaka fördröjning.

Question 20

Varianter av mark and sweep

Answer 20

generationer, inkementell, trådad

Question 21

Förklara vad och en av varianterna av mark and sweep

Answer 21

Generationer: äldre körs enbart var 100e gång, med 2 generationer så kan de råka hamna i äldre fast de bara hade kort livslängd, därför kör man ofta 3
Inkrementell: reda på hur långt vi kommit, kan stoppa mitt i och fortsätta med programmet, hålla koll noga vart man är
Trådad: trådad stör inte huvudtråden men använder cachen, sämgre cache på huvudtråd

Question 22

Annan metod ön mark and sweep

Answer 22

Referensräkning: rotmängd, håller reda på hur många pekare till varje objekt, cirkulära datastrukturer ligger kvar för alltid, sätt ihop med mark and sweep, sämre prestanda behöver gå huller om buller i minnet.
Konservativ skärpsamling: Följa adresser i rotmängden i adress rymden, BOHM

Question 23

Skillnad på statiska och dynamiska kontroller

Answer 23

Statiska kontroller: vid kompileringstillfälle genom att kolla på koden, statiska fel syns exempel int i, *i=2, i är ingen pekare, vill gärna ha statisk kontroll pga upptäcka fel så tidigt som möjligt.
Dynamiska kontroller: när programmet körs, vissa fel upptäcks inte förrens det körs, exempel objektorienterad programmering och en funktion inte finns i grunden och man castar så djuret verkligen är en hund, så kommer kompilatorn lägga en kontroll och kolla så det verkligen är en hund, kan bara kollas vid körningstillfälle

Question 24

Skillnad på stark och svag typning

Answer 24

Svag typning: går runt typkontroll
Stark typning: Mer strikt; kräver explicit typkonvertering. Säker men mindre flexibel.
Svag typning: Mer flexibel; kan automatiskt konvertera typer. Mindre säker men snabbare att skriva.

Question 25

Reguljära uttryck

Answer 25

Sätt att specifiera mönster, b*: noll eller flera b a|b: a eller b b*|a abc a|b* (a|b)*: a,b,abaab (a*|b*): a,b, aaa, bbb

Question 26

Tillståndsmaskiner (skillnad deterministic)

Answer 26

DFA (Deterministic Finite Automation): Icke deterministic maskin: behöver chansa och backa, kan även göra om till deterministic

Question 27

Is it a good idea to have a grammar that allows for type errors, and leave type checking to the next phase after parsing, the semantic analyzer?

Answer 27

YES

Question 28

Is it a good idea to have an ambiguous grammar, which is made un-ambiguous when removing all parse trees that result in a type error?

Answer 28

NO

Question 29

Basic blocks

Answer 29

Rader som garanterat körs efter varandra

Question 30

Gemensamma deluttryck

Answer 30

Gemensamma deluttryck: inga hopp mitt i, med hjälp av basblock

Question 31

Looptrullning

Answer 31

ar man otur, rullar ut loopen så den inte får plats i instruktions cachen om den ligger inuti en annan loop, kompilatorn får hålla koll på vilka loopar de rullat ut (1 miljon iterationer) Man vill inte hoppa runt i en array: rullar ut loop istället

Question 31

Svansrekursion

Answer 31

Använder samma aktiveringspost, samma stack frame, med hopp Svansrekursion är en typ av rekursion där det sista steget i en funktion är ett rekursivt anrop. Eftersom det inte finns några ytterligare beräkningar efter det rekursiva anropet kan den aktuella aktiveringsposten återanvändas, och ingen ny stack frame behövs. Istället hoppar programmet direkt tillbaka till början av funktionen för nästa anrop, vilket gör att det är minnesmässigt effektivare än vanlig rekursion. Detta gör att svansrekursion ofta kan optimeras av kompilatorn eller tolken genom en teknik som kallas tail call optimization.

Question 32

I VILKEN FAS BLIR FELET: printf("En övning i addition!\n) warning: missing terminating " character

Answer 32

Scanner

Question 33

I VILKEN FAS BLIR FELET: printf("En övning i addition!\n) printf("Ange två tal och deras summa: "); error: expected ';' before 'printf'

Answer 33

Parsing

Question 34

I VILKEN FAS BLIR FELET: Segmentation fault (core dumped)

Answer 34

Program execution

Question 35

I VILKEN FAS BLIR FELET: error: 'gissning' undeclared

Answer 35

Semantic

Question 36

I VILKEN FAS BLIR FELET: warning: 'summan' is used uninitialized

Answer 36

Semantic

Question 37

I VILKEN FAS BLIR FELET: undefined reference to 'print'

Answer 37

Linker

Question 38

I VILKEN FAS BLIR FELET: warning: returning 'char *' from a function with return type 'int'

Answer 38

Semantic

Question 39

I VILKEN FAS BLIR FELET: (1) error: invalid suffix "a" on integer constant (2) warning: implicit declaration of function 'printg' (3) error: undefined reference to `printg'

Answer 39

(1)Scanner (2)Semantic (3)Linking

Question 40

I VILKEN FAS BLIR FELET: (1) missing terminating " character (2) error: incompatible types in assignment (3) warning: double format, different type arg (arg 2) (4) error: syntax error before "s" (5) warning: `return' with no value, in function returning non-void

Answer 40

(1)Scanner (2)Semantic (3)Semantic (4)Parsing (5)Semantic

Question 41

I VILKEN FAS BLIR FELET: error: invalid preprocessing directive #inglude

Answer 41

Preprocessor

Question 42

I VILKEN FAS BLIR FELET: (2) warning: missing terminating " character (3) error: expected ';' before '}' token (4) Segmentation fault (core dumped) (5) warning: variable 't' set but not used (6) error: 'u' undeclared (7) warning: 'z' is used uninitialized (8) warning: implicit declaration of function 'f' (9) undefined reference to 'f'

Answer 42

(2)Scanner (3)Parser (4)Program executed (5) Optimizer or semantic (6)Semantic (7) Optimizer or semantic (8)Semantic (9)Linking

Question 43

Recursive- descent parser

Answer 43

En rekursiv nedstigningsparser är en parser som börjar från startsymbolen och använder en funktion för varje icke-terminal i grammatiken. Den anropar dessa funktioner rekursivt baserat på grammatikkens regler. Till exempel, för att analysera ett uttryck som 2+3, skulle den kalla funktioner för Expr, Term och hantera +-symbolen steg för steg. Den är enkel att implementera men fungerar bäst med grammatik som inte är vänster-rekursiv.

Question 44

What do we mean by a predictive parser?

Answer 44

A predictive parser decides which grammar rule to apply by looking at the next token. It uses this information to parse the input efficiently without guessing or backtracking.

Question 45

VILKEN FAS UPPSTÅR FELET: (1) Segmentation fault (core dumped) (2) control reaches end of non-void function (3) expected ")" before ";" token (4) too few arguments to function "f" (5) undefined reference to "h"

Answer 45

(1) Vid programkörningen ("exekvering", "run-time") (2) Semantisk analys (3) Syntaktisk analys ("parser") (4) Semantisk analys (5) Länkning

Question 46

eliminering av svansrekursion

Question 47

eliminering av svansrekursion

Question 48

lexem

Question 49

operatorassociativitet

Question 50

reduce-reduce-konflikt

Question 51

registerallokering

Question 52

startsymbol

Question 53

Yacc

Question 54

Att tänka på syntax träd:

Answer 54

Semikolon!!!!!! Börja med semikolon Om if else, if har 3 streck ifrån sig While har två If har två i vanliga fall

Question 55

Att tänka på postfix för stackmaskin:

Answer 55

label behövs bara om man ska återvända dit!! gå dit igen JUMP while-start Gofalse after-while gofalse after if goals else start

Question 56

Att tänka på treadresskod:

Answer 56

label while blir if() goto afterwhile dela upp i basic block försvinner labels men goto är kvar

Question 57

När man ska rita minne vad tänka på

Answer 57

Heap högst och växer ner, stack under och växer uppåt

Question 58

Vad gör alla faser i kompilatorn?

Answer 58

1. Lexer (lexikalisk analysator): Läser in källkoden som en ström av tecken och delar upp den i mindre enheter som kallas tokens (t.ex. nyckelord, identifierare, operatorer). Lexer ansvarar också för att ignorera kommentarer och mellanslag. 2. Parser (syntaktisk analysator): Tar tokens från lexern och bygger en syntaxträd (eller parse tree) som representerar programmets grammatiska struktur enligt språkspecifikationen. Parsern kontrollerar att koden följer språksyntaxen. 3. Semantic Analyzer (semantisk analysator): Kontrollerar den semantiska korrektheten i koden, t.ex. att variabler är deklarerade innan användning, att typer matchar i operationer och att funktioner anropas med rätt antal och typ av argument. 4. Intermediate Code Generator: Översätter syntaxträdet till en intermediär representation (IR), som är ett enklare och språkoberoende format, ofta tredelade adresser eller en form av pseudokod. 5. Optimizer: Förbättrar den intermediära koden för att göra den mer effektiv, t.ex. genom att eliminera död kod, minska antalet instruktioner eller optimera loopar och uttryck. 6. Code Generator: Översätter den optimerade intermediära representationen till maskinkod eller assemblerkod för målplattformen. Den ser också till att resurser som register används effektivt.