Topics for Midterm Exam in COP 3402 $Date: 2023/10/06 21:17:50 $ This examination covers topics related to homework (project) assignments 1-2. REMINDERS This test will be for about half of the 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