BottomUpParsing

BottomUpParsing

• Right most derivation
• shift: input에서 stack의 top으로
• reduce: production을 역으로 수행
• stack과 input에 대한 lookahead

augmented Grammar

• $S'$이 추가된 문법
• $L(G')=L(G)$
• $V_N'=V_N \cup S'$
• $P' = P \cup \{S' \rightarrow S\}$

Right sentential form

• 유도 과정 중간에 있는 스트링들, 파싱 스택과 인풋으로 분리 가능

Viable prefix

• 파싱 스택에 있는 형태
  • (E||+n), (E+||n), (E+n||) 형태에서 왼 쪽에 있는 것

Handle

• reduction 가능할 때 까지 shift
• 모호하지 않을 때 행동은 고유(결정적)

LR Parsing

• Right most derivation

LR(0) iteem

• . 으로 위치를 구별한다.
• initial과 complete 아이템 존재
  • complete 아이템일 때 reduce 가능

Finite automata of LR(0) items

• LR(0) 아이템은 오토마타의 상태로 치환

1. $A \rightarrow \alpha.a\beta$ a가 터미널 심볼이면 a를 입력 받았을 때
   • $A \rightarrow \alpha a.\beta$
2. 논 터미널인 경우
   • 하나는 위와 같은 방식
   • 논터미널 심볼로 시작되는 state로 $\epsilon$을 입력 받아 이동

LR(0) parsing algorithm

• 시작: $\$0$ 을 스택에 push
• 이후 DFA state나 이로 만든 테이블을 보고 행동
  • complete 아이템이라면 reduce 아니면 shift
  • reduce 하고 나면 이전 상태로 복귀(필요한 만큼 스택에서 제거)
  • 바뀐 심볼과 긍 대한 state로 채움
• conflict가 발생할 수 있다.
  • shift-reduce conflict
  • reduce-reduce conflict
  • 충돌이 발생하면 LR(0) 문법이 아니다.
• LR(0) 파싱 테이블 형태
  • State | Action | Rule | Input(하위 그룹 존재) | Goto(하위 그룹 존재)

SLR(1)

• Simple LR(1) parsing
• LR(0)와 같은 DFA 사용

SLR(1) parsing algorithm

1. $A \rightarrow \alpha.B \beta$ 이면 shift
2. $A \rightarrow \alpha .$ 이면 Lookahead
   • 다음 문자열이 Follow(A): reduce
   • 아니면 Shift

• SLR(1) 파싱 테이블 형태
  • State | Input | Goto
  • s1: 1로 이동
  • r2: 프로덕션 룰 2 수행

LR(1) Item

• $[A \rightarrow \alpha. \beta, a]$
  • $a$: Lookahead 토큰 추가

LR(1) Item으로 만든 오토마타

1. 터미널 심볼이면 shift
2. 논터미널 심볼이면
   • 하나는 위와 같은 shift
   • $[A \rightarrow \alpha.B \beta, b] \,\,\,\, \underrightarrow \epsilon \,\,\, [B \rightarrow .\Upsilon_i, a]$
     • $a \in First(\beta b)$

• Start state: $[S' \rightarrow .S,\$]$
• Final state: complete item

General LR(1) Parsing algorithm

• complete item 이면 reduce 아니면 shift

LALR(1)

• 오토마타를 만드는 두 가지 방법
  • LR(0) DFA를 만든다. Propagation lokkaheads
  • LR(1) DFA를 만든다. LALR로 합친다.
    • Lookahead만 다른 상태들을 합친다.

Shift 가 Reduce 보다 우선순위가 높음
Reduce 끼리는 우선순위를 부여
Parser는 Error detect 및 recovery가 가능하다