https://talkingaboutme.tistory.com/entry/Compiler-Bottom-Up-Parsing?category=484576

1. Introduction of Bottom-Up Parser
   ◼ Also called shift-reduce parser
   ◼ Construct a parse tree for an input string beginning at the leaves and working up toward the root
   ◼ Reducing a string ω to the start symbol S
   ◼ At each reduction step, a particular substring RHS of production is replaced with by the symbol on LH

2. Handles of String
   A substring that matches the right side of a production and whose reduction to the non-terminal on LHS presents one step along the reverse of a right derivation
   ◼ Formally, handle of a right sentential form γ is a production A → β and a position of γ where the string β may be found and replaced by A to produce the previous right sentential form in a rightmost derivation of γ

3. LR(k) Parsers
   

4. 

5. Constructing SLR (Simple LR) parser
   Three operations for construction
   1) Augmenting a grammar
   Add S' → · S to indicate the parser when it should stop and accept
   2) closure operation
   Suppose I is a set of items for G, then closure(I) ➔
   ① every item in I is added to closure(I)
   ② If A → α·Bβ ∈ closure(I)
   then add B → ·γ to closure(I) for ∀ B → γ in I
   
   3) goto operation
   Suppose Ii be a set of items and X be a grammar symbol, then goto(Ii, X) = Ij, where Ij is the closure of the set of all items of [A → αX·β] such that A → α·Xβ ∈ I
   
   
   
   

6. Constructing LR Parsing Table
   
   

7. 

8. LALR 많이씀 : SLR보다 같은 스테이트 가지면서 더 정확함.
   LR는 좋은데 너무 많이 스테이트를 만듦.
   

9. Every ambiguous grammar fails to be a LR
   Disambiguating rules
   ◼ Use precedence and associativity
   ◼ "Dangling else" ambiguity by favorable choice
   ◼ Ambiguities from special case productions

10. Use precedence
    

11. Using the associativity
    

12. "Dangling else" ambiguity by favorable choice
    

PLCOMP-ch10-2021-2.pdf
http://contents.kocw.or.kr/document/lec/2012/ChungBuk/LeeJaeSung/cp-13.pdf

Symbol Table

1. Symbol Table
   A data structure that stores information about various source language constructs
   A compiler uses symbol table to keep track of scope and binding information about names

2. An example of symbol table
   

3. Symbol table implementation
   Unordered list
   ◼ Simplest possible storage mechanism
   ◼ But impractically slow for large table
   Ordered list
   ◼ The entries are kept ordered
   ◼ Lookup is fairly efficient (O(logn), but insertion operation is relatively expensive
   ◼ It is useful for small sized tables

4. Scoping rules : determine which declaration is appropriate
   key와 value로 구성되어 있는 dictionary 타입의 데이터 구조로 패키지나 함수, 클래스 정보를 포함한 코드 내에 정의된 여러 변수들에 대한 정보가 담긴 테이블이다.
   함수를 실행하면 함수의 로컬 심볼 테이블이 생기고, 함수 내의 모든 변수 할당은 이 곳에 저장된다. 그래서 인터프리터가 코드를 해석할 때 변수의 실제 값을 찾기위해 로컬 심볼 테이블을 먼저 찾아보고 그 후로, 그 다음으로 함수를 둘러싸고 있는 로컬 심볼 테이블에서 찾아보고, 글로벌 심볼 테이블, 내장 심볼 테이블 순으로 찾는다. 여기를 참고하면 해당 내용을 볼 수 있다.

5. code generation과정 중에 생기는 forward reference문제
   정의하기 전의 name에 대해서 접근할 때 생기는 문제
   해결법 1 : Backpatching : 빈칸으로 남겨 놨다가 나중에 채워넣는다
   -> Backpatching : Leave space for unknown value and fill it later
   해결법 2 : Multiple pass resolution : 정의 안되었던 name에 대해서 pass를 여러번 거처서 나중에 해결(resolve it at the later passes)
   -> Multiple pass resolution : Resolve it at the later passes

https://arings.tistory.com/entry/%EC%BB%B4%ED%8C%8C%EC%9D%BC%EB%9F%AC