1. Scanner
   Recognize a language as a set of words (lexical level of PL)

2. Parser
   Recognize phrase structure of a language (syntactic level of PL)

Push Down Automata

1. P = (∑, Q, Δ, H, h0, q0, F) where
   

2. PDA may be non-deterministic (having more than one possible transition for any given configuration)

3. 

4. Example 2
   

5. LL(k) Parse
   Look ahead k input symbols before determining next more
   1) Ambiguity
   ▪ A grammar that produces more than one computation paths for a same sentence
   2) left recursion
   ▪ Same string is repeatedly produced such as A →Aα1 for some string α
   3) left factoring
   ▪ Not clear which of two or more alternative productions to use to expand a non-terminal for LL(k) parser
   

6. Ambiguous Statement
   
   

7. Resolution
   1) System applies a rule : Match each else with the closest (o)
   previous unmatched "then"
   2) Rewrite grammar to explicitly specify the order
   3) Enforce Programmer to write code : then clause must be matched to have else clause (x)

8. Left recursion
   A grammar is left recursion if A → Aα1for some string α
   Top down method cannot handle left-recursive grammars due to infinite looping

9. Resolution
   

10. Left factoring
    Not clear which of two or more alternative productions to use to expand non-terminal A

11. Resolution
    

12. Recursive Descent parsing
    A top-down parsing method of syntax analysis in which we execute a set of recursive procedures, that are associated with each nonterminals of a grammar, to process the input.

13. Predictive Parsing
    A special case of the recursive descent parsing in which the lookahead symbol unambiguously determines the procedure selected for each non-terminal (no backtracking)

Non-recursive Predictive Parsing

1. Constructing predictive parsing table
   https://kbs0210.tistory.com/6
   https://www.usna.edu/Users/cs/wcbrown/courses/F20SI413/firstFollowPredict/ffp.html
   
   

2. Example
   
   

3. 예시1
   
   예시2
   

4.