UCR CS152 Final

Bottom-up Parsing

• LR(1) Parsing [recording of last year’s lecture]

• How to construct a DFA and its parsing table?
• [Nonterminal → .blabla, Follow terminal of Nonterminal or $]
1. 첫번째 논터미널 아닌 애들 말고 시작하는 논터미널들 initial state
2. 맨 앞 터미널 논터미널 별로 state 이동가능
3. 그 뒤에 논터미널이면 그놈으로 시작하는 걸로 변경해

• How to execute an LR(1) parser?
• Parsing Table
• nonterminal - target state or r(nonterminal → blabla)
• $ - single accept of main(A’ → A) end or r(nonterminal → blabla)
• terminal - target state number
• Conflict
• in State ~, the shift items [A → a. B b, $] and [B → . a, b] and the reduce item [C → a ., d] do not form any conflicts as their second components are different.
• Execution
• stack - $blabla
• input - blabla$
• action - shift or reduce or accept - reduce 하면 table nonterminal state로 이동

Semantic Analysis [recording1, recording2(incomplete), recording3]

• Basic Concepts
• What is syntax directed semantics?
• Compute attributes based on attribute equation (Semantic Rule)
• What is semantic rule/equation and what is attribute grammar?
• A set of CFG grammar rules along with their semantic rules
• if else statement also can to used in Semantic rule 가능하면 쓰지말고
• What are inherited and synthesized attributes?
• Synthesized Attributes +
• Inherited Attributes -

• Application
• Be able to write down semantic rules for computing attributes of commonly used language constructs, such as values of expressions and types variables

• Evaluation:
• Be able to draw the dependence graph along with the parse tree for a given input
• RHS 시작점에서 따라서 트리구조로 그려나가
• Understand the evaluation order of the attributes
• Understand the concepts of S-attributed and L-attributed grammars
• S-attributed grammar
• L-attributed grammar

• Symbol Table
• What is a
  Symbol Table and how is it used?
• Symbol Type
• Symbol Scope

• Understand the complexity of scopes

• Understand its basic implementations: chained hash table and scoped hash table

• Type Checking
• Structured types and their type trees
• Be able to write down semantic rules to perform basic type checking

Code Generation [recording1, recording2]

• Intermediate Representation
• What is an IR and how is it obtained?
• Common types of IR: three-address code and stack machine code

• Code Generation
• Understand the idea of treating code as a synthesized attribute
• Be able to write semantic rules to generate code for expressions and assignments, array references, control structures (if-else and loops), and functions
• newtemp()
• newlab()
• goto + newlab
• label + newlab
• if_false blabla.name + goto~

Runtime Environment [recording]

• Basic tasks of a runtime environment

• Memory model/layout for code and data
• registers
• memory low to high

• Function call management in stack-based runtime environment (no need to memorize the assembly code, but should be able to read the assembly code)
• Interpreter directly manages memory and func
• Compiler indirectly manages memory and func
• pushq %rbp - push base pointer onto stack
• movq %rsp, %rbp - set base pointer with stack pointer
• subq $16, %rsp - allocate memory for local variables
• …
• callq _inc - save return address onto the stack; goto the callee
• addq $16, %rsp - deallocate memory of local variables
• popq %rbp - pop (old) base pointer; set it as the current
• retq - pop return address; return to the caller

• What is a prologue and what is an epilogue?

Code Optimization [recording]

• Be able to apply VN to a given basic block

• Understand some complexities in applying VN

• Understand the optimization scopes, including concepts of BB and EBB

Target Code Generation [recording]

• Instruction selection: basic ideas

• Instruction scheduling: list scheduling algorithm

• Register allocation: graph-coloring-based allocation algorithm