ITEC 460: Exam 1 topics - Spring 2014

• Updates :
  1. No updates at this time.

1. Coverage
1. Chapters 1 - 5
2. Lecture and notes, supplemented by relevant sections of the text
3. Homeworks
4. Programs


2. Chapter 1: Introduction
• Briefly describe each of the following
• History and evolution of compilers
• Possible kinds of machine code (ie pure, augmented, VM)
• Steps of bootstrapping a compiler
• Benefits of a compiler producting VM code
• Characteristics of 3 kinds of output (ie asm, relocatable and pure binary)
• Cross compilation, native compiler
• Role of linking, modular compilation, cross language support)
• Similarities and differences, pros and cons of compilation vs interpretation
• Similarities and differences of syntax and semantics
• Similarities and differences of static and rt/dynamic semantics
• Compiler phases
• syntax directed compilation, syntactic and semantic analysis
• Abstract and Concrete sytax tree
• Role of scanner, parser, type checker, translator, optimizer, code generator


3. Chapter 2: A Simple Compiler
• Answer questions about the example language, grammar, parser, visitor code


4. Chapter 3: Scanning
• Define the task of scanning
• Describe the input and output of a scanner generator
• Discuss declarative and procedural (ie imperative) program wrt scanner (and parser) generators
• Define regular expressions as related to scanners
• Write and interpret RE for various token types
• Describe keywords and reserved words and their significance
• Discuss importance of scanner performance to compiler performance
• Describe double buffering and its role in scanning
• Transform a RE to a NFA and the NFA to a DFA
• Simplify a DFA to minimize the number of states
• Implement a simple FSM, either hand written or table driven


5. Chapter 4: Grammars and Parsing
• Define CFG, CFL, leftmost derivation, leftmost parse, top down parse
• Define rightmost derivation, rightmost parse, bottom up parse, parse tree
• Describe and simulate the algorithm to remove useless variables from a grammar
• Define ambiguous grammar and discuss an algorithm to determine if a grammar is ambiguous
• Describe EBNF
• Distinguish parser and recognizer
• Define LL and LR and relate them to parsers
• Define First(alpha) and follow(A)
• Find in grammar G: First(alpha) and follow(A)


6. Chapter 5: Top Down Parsing
• Define top down, LL, Recursive Descent, Predictive, and LL(k) Parsers
• Give pros and cons of Top Down Parsers
• Create a NPDA for a top down parse
• Trace a TD parse
• Explain the role of the stack in a TD parse
• Define Predict(A -> Alpha)
• Describe how to calculate and use Predict(A -> Alpha)
• Build a RD parser for a given grammar
• Explain how to tell if a grammar is LL
• Desribe 2 problems that can keep a grammar from being TD (ie common prefix and left recur)
• Fix common prefix and left recursion problems
• Explain the problem with ambiguous grammars and how they are approached in TD parsing
• Discuss parse table representation
• Differentiate between error recovery and repair
• Describe Wirth's approach to error recovery