Topics for the Final Exam in COP 3402 $Date: 2024/11/20 14:00:39 $ This examination covers topics related to homework assignments 2-4. REMINDERS This test will be for the period scheduled for the final exam, on the UCF exam schedule and in the course calendar on Webcourses, (in the usual classroom) and will be closed book. However, you may use one (1) page of notes on one (1) side of a standard 8.5 by 11 inch sheet of paper. These notes can either be hand-written or printed, but if printed, then the font must be a 9-point or larger font. These notes must be turned in with the exam. READINGS See the recommended textbook (Systems Software by Montagne) chapters 5-6. See also the course lecture notes, which are available from the course resources webpage (see http://www.cs.ucf.edu/~leavens/COP3402/resources.shtml#course) and the slides (from Files > filled-in-slides-from-lectures on Webcourses). CONCEPTS/TOPICS Topics marked + below are more important than topics marked - below, which are less important (but were mentioned in the class). Topics marked ++ are very important. Topics marked -- are very unimportant. In general, conceptual questions, and questions that connect topics, techniques, examples, and ideas will be more important than details; the exam may be somewhat of a different flavor than the homework sets. I. Basic Terminology It's important to know and understand these terms, so that you understand the questions and can write sensible answers. A. Grammars + How does a compiler use grammars to do its work? + What kinds of grammar is used in lexical analysis? ++ What does the flex lexical analyzer do? (What are its inputs and outputs?) ++ What does the bison parser generator do? (What are its inputs and outputs?) - What are the characteristics of a regular grammar? + Can a regular grammar recognize the same languages as regular expressions? + What languages can a context-free grammar recognize (vs. a regular grammar)? - What are the characteristics of a context-free grammar? - Can an LL(1) or LR(1) grammar be ambiguous? + How would you use a parser generated by bison to build ASTs? - What kinds of actions does a bison-generated parser take during parsing? B. Compilers 1. semantic analysis and symbol tables + What is a symbol table? What operations would it support? ++ What role does the symbol table play in a compiler? + What kind of information should be remembered for each declaration? Why? + What is an attribute? What kind of information is stored in attributes? ++ What kind of errors are caught in declaration checking? What is an example of each kind in SPL? + What is a scope? + What is the scope of a declaration in C? - What is a "forward declaration"? How are they used in C? + Does each scope have its own symbol table? ++ What is a scope? What is a potential scope in SPL? ++ Does a block in SPL determine scopes? ++ What is a scope in C? - What is a scope in the FLOAT language? ++ How is a symbol table used to check declarations and uses of identifiers? ++ How is does the symbol table deal with scopes? 2. Code generation a. general concepts - What is an IR? What is it used for in a compiler? - What are the advantages of using an IR in code generation? + What information from an identifier's use is needed to generate code? + What is the general way that the code for a code generator is written? + What does it mean for code to "follow the grammar"? b. declarations ++ How are constant declarations translated into machine code (for the VM)? ++ How are variable declarations translated into machine code? + Where are globally visible constants and variables allocated? c. lexical addressing - How practical would it be for a parser to determine the lexical address of a name that is used in a program with nested procedures? + Which part of the lexical address of a constant or variable can be easily determined during parsing? + When is the rest of the lexical address determined? (And why can't that be easily determined during parsing?) + What is an AR? How are ARs used on the runtime stack? + How are ARs laid out on the runtime stack? + Where are constants and variables located in an AR? d. expressions + How would numeric literals be handled in code generation? + How are identifier uses distinguished from identifier declarations? + Why are identifier uses important for code generation? + How is the lexical address of a variable (or constant) used to generate code? + What does the generated code for obtaining the value of a variable (or constant) look like? ++ Where should compiled code put the value of each expression? e. statements + How are assignment statements compiled? What VM code do they generate? + How are if-then-else statements compiled? What VM code do they generate? + How should the compiler compute the addresses needed for the code generated for if-statements? + How are while-loops compiled? What code do they generate? + How should the addresses needed for the code generated for while-statements be computed? f. procedures - How are procedure declarations compiled? - How is the starting address of a procedure obtained by a call instruction? - With static scoping, what does the frame register point to in an AR for a nested scope? C. Assembly Language - What is an assembly language? - What are the goals of assembly language? - How does assembly language differ from a (high-level) programming language? - How does an assembler differ from a compiler? - How does an assembler translate forward jumps (to a label)? D. linkers and loaders 1. linkers - What is a linker? What does a linker do? - Why is a linker useful for programming? - How does a linker support separate compilation? - How does a linker support program libraries? -- What is the difference between static linking and dynamic linking? - Which kind of linking is used to link together the compiled files of a user's program? -- Which kind of linking is performed to link a user's program to a shared library? 2. loaders - What is a loader? What does a loader do? - What are the types of loaders? When is each type used? - If we are using a computer with virtual memory, do we still need a relocating loader? E. Operating System (OS) - What are the goals of an operating system? - What are the main techniques that are used to implement an OS? - What are some ways to organize the code in an OS? - What are the advantages and disadvantages of different ways of organizing an OS? - What would happen if an OS was just a bunch of libraries? 1. processes -- What is a process? - Why does an OS have processes? - What are the advantages of the process concept for programming? - How does a process differ from a program? - How does a program become a process? - What states can a process be in? How does it change from one to another? -- What is a PCB? What information does it typically store? - Where do a process's permissions come from? -- What is a PAS? - What information needs to be saved when suspending a process? 2. interrupts - How does an OS enable sharing of resources? - What is needed for an OS to enforce sharing policies? - What is an interrupt? - Why are interrupts needed? - Why is an interrupt handling mechanism a useful idea in an OS? - When does a CPU notice interrupts? - What are the different kinds of interrupts? - What is a trap interrupt? - What does an interrupt handler do? - Why does an interrupt handler need to save the state of the running process? - What is an I/O interrupt? How does it differ from a trap interrupt? - What hardware is needed to handle interrupts? - What is a timer interrupt? Why is it needed? - How could an OS can handle multiple interrupts that occur at the same time? - What is a trap table (aka an interrupt vector)? - What software controls the contents of the interrupt vector? Is that crucial? 3. limited direct execution -- What is limited direct execution? How does it work? -- What is needed from the hardware (the ISA) to make limited direct execution work? - What are the differences between user mode and kernel mode? - Describe the kinds of instructions can only be executed successfully in kernel mode. - Why is it useful to have the ISA distinguish between user mode and kernel mode? - What mode (user or kernel) does the system's boot loader run in? - What mode does an OS run in? - What mode does an interrupt handler run in? 4. system calls - What is a system call? - How are system calls implemented in an OS? - If a user mode process cannot execute privileged instructions how can it do any I/O? - Is your program's process executed in kernel mode? - If your program is doing I/O, does that mean that the process you are running is executing privileged instructions? - What does a system call function need to do about security? - What is memory protection? Why is it needed? - What does a "segmentation fault" mean for a C program? - What is a PSW? Why is it useful in an OS? 5. threads - What is a thread? Why is it a useful concept for an OS? - Does each thread need its own stack? - What is the difference between apparent concurrency and true concurrency? - What is a race condition? Why are race conditions a problem? - Can a system with apparent concurrency have race conditions? - What is a critical section? Why is it important? - What is mutual exclusion? How is it used in concurrent programming? - What is serial execution? Why is it useful? - What is atomic execution? Why is that a useful concept? - What are some mechanisms for safely synchronizing programs? II. Skills When a question refers to a programming language, the language will either be described in the question (especially for questions related to grammars and parsing) or it will be C or the SPL language. A. Grammars and Parsing ++ Write regular expressions to recognize a given set of tokens - Convert a regular expression into a (deterministic) finite automaton + Determine if a context-free grammar is ambiguous - Write a context-free grammar for a language that is not ambiguous. + Determine if some text is recognized by a language's grammar. + Write a context-free grammar for a small programming language. B. Addressing and Subroutines ++ Determine the lexical address of a local variable in a SPL program - Draw before and after pictures showing the effect of call and return instructions on the run-time stack in a VM C. abstract syntax trees (ASTs) + Write C code to walk over an AST (e.g., to check for duplicate declarations) D. Static Analysis + Determine if a program has duplicate declarations + Determine if a program has undeclared identifier uses E. Compilers + Be able to write code to traverse an AST and check declarations and identifier uses (given some helping functions) + Be able to write code to traverse an enhanced AST and generate VM machine code (given some helping functions)