Topics for Midterm Exam in COP 3402 $Date: 2023/10/06 16:24:44 $ This examination covers topics related to homework (project) assignments 1-2. REMINDERS This test will be for the entire period in class 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 textbook (Systems Software by Montagne) chapters 1-3, 5, and 6. See also the course lecture notes, which are available from the Files section of Webcourses or from the course resources webpage (see http://www.cs.ucf.edu/~leavens/COP3402/resources.shtml#course). 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. * Basic Terminology It's important to know and understand these terms, so that you understand the questions and can write sensible answers. ** Systems software + What is systems software? + What is a compiler? An interpreter? What is the difference? + What is an assembler? - What does a linker do? What does a loader do? ++ What does a compiler do (overall)? + What role does a VM play in systems software? - What is an object file? What is its format? *** VMs and processors - What is the ISA? + When does the program counter get adjusted in a VM's cycle? ++ What does a jump instruction do in terms of how it affects the PC? -- What are the details (e.g., opcodes) for the Tiny VM? -- What are the details (e.g., opcodes, function codes, etc.) for the SRM? - How can one tell if an ISA has enough instructions? + Why does an ISA need an EXIT (halt) instruction? + What happens if there is no EXIT instruction in a program? + How would an if-then-else statement in a high-level language get translated into machine code (in terms of branch or jump instructions)? + How would a while loop be translated into machine instructions (in terms of what branch or jump instructions and needed)? - What is the memory hierarchy? Why is it important? *** Assembly language - What are the advantages of assembly language over machine code? *** Support for subroutines + Why are subroutines important? + What capabilities does a programming language need from a VM to support subroutines? + What features in a VM help support subroutines? ++ What is static scoping? Why is it useful? + What is dynamic scoping? - When is dynamic scoping useful? ++ What is the difference between a static property and a dynamic property (in general terms)? + What is block structure in a programming language? - What are the advantages of block structure? - Why should a language support recursion? - Why is it useful to have recursion to write a context-free parser? + What data structure in a VM or computer is necessary for supporting recursive procedures? ++ What is an AR? + What information is stored in an AR? + How is an AR (and the information stored in it) used to implement procedure calls? Returns from procedures? + How should a VM (or compiler) address local variables (that are inside procedures) that are in surrounding scopes? + What information is needed to address local variables in surrounding scopes? + What is a static link and how is it used to address local variables? ++ What is a lexical address? How is it used to address local variables? + How can a compiler determine which static link to pass to a procedure in a call instruction? ** Compilers ++ What are the main jobs of a compiler? + What are the main goals of a compiler? + What is done in the "front end" of a compiler? + What is done in the "back end" of a compiler? + What are the advantages of a compiler over an interpreter? - What are the advantages of an interpreter over a compiler? - Is it possible to combine a compiler and an interpreter? *** lexical analysis + What is a token? How are tokens used in a compiler? + What information is stored (or remembered) for each token? + What is a reserved word? What role do they play? - What is the difference between reserved words and key words? -- What are the advantages and disadvantages of using token objects over global variables holding the same information? + What is a regular expression? + How are regular expressions used in generating a lexer? + How are comments and whitespace handled in a lexical analyzer? *** grammars and languages - How is a language defined using a grammar? + What is the relationship between a language and a grammar? + What kind of grammar is typically used for lexical analysis? Why? + What kind of grammar is typically used for parsing (syntax analysis)? Why? ++ What is a grammar? ++ What is BNF notation? ++ What does `::=' mean in BNF notation? ++ What does `|' mean in BNF notation? ++ How does one indicate 0-or-more repetitions of a symbol in EBNF notation? ++ How are nonterminal symbols written in BNF notation? ++ How are terminal symbols written in BNF notation? + Do BNF grammars allow recursion in their rules? + How can a grammar be used to recognize legal programs? + How can a grammar be used to generate programs? - What does it mean when a compiler says it was "expecting" a certain kind of symbol? - What is an AST? - What role does an AST play in a compiler? - How does an AST differ from a parse tree? * Skills When skill questions refer to a particular VM, the VM is likely to be either the SRM of homework 1 or the Tiny VM discussed in class (for the Tiny VM, see also: http://www.cs.ucf.edu/~leavens/COP3402/example-code/index.html#TinyVM). When such 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 PL/0 language. ** VMs + Write C code to interpret instructions for a VM + Explain what happens when a given program is run on a VM + Give the content of memory or registers after a VM executes an instruction or a program (starting from a particular state) ** Grammars and Parsing + Describe a given language using regular expressions + Determine if a string is recognized by a regular expression + Determine the set of tokens for a language based on its grammar + Convert a string of characters for a language into tokens based on its grammar + Determine the set of reserved words for a language based on its grammar - Determine if a terminal string is in the language of a given context-free grammar - Determine what kind of error message should be produced by a parser for a given terminal string that is not in the language of a given grammar - Write a derivation (or a leftmost derivation) that produces a given terminal string using a context-free grammar, or explain why that cannot be done - Draw a parse tree for a terminal string, using a given context-free grammar