[Advanced Compiler Lecture Notes]
Week 04 (2003/10/6)

1. Review on parsing techniques
(a) top-down parsing
	-> beginning at the start symbol, expanding nonterminals in depth-first manner (predictive in nature)
	-> left-most derivation
	-> pre-order traversal of parse tree
	-> e.g.	LL(k) [read from Left; Left-most derivation; k lookaheads], 			recursive descent parsing
(b) bottom-up parsing
	-> beginning from terminal string, determining the production used to generate leaves
	-> right-most derivation (in reverse order)
	-> post-order traversal of parse tree
	-> e.g.	LR(k) [read from Left; Right-most derivation; k lookaheads]

2. LR Parser
(a) Parsing stack: containing contextual information of parsed symbols 
(b) Two actions:
	-> shift
		=> when top of stack doesn't contain a handle
		=> push input token (with contextual information) into stack
		=> push a state (using the goto table) to the parsing stack
	-> reduce
		=> when top of stack contains a handle
		=> pop the handle & push reduced nonterminal (with contextual information)
		=> reduce a rule (using the  grammar), push a state (using the goto table) to the parsing stack
(c) Two tables:
	-> action table: (terminals) X (states) -> (what to do?)
	-> goto table: (terminals + nonterminals) X (states) -> (what state to be?)