BottomUpParsing

oak_cassia·2022년 6월 4일
0

Compiler

목록 보기
6/9

BottomUpParsing

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

augmented Grammar

  • SS'이 추가된 문법
  • L(G)=L(G)L(G')=L(G)
  • VN=VNSV_N'=V_N \cup S'
  • P=P{SS}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α.aβA \rightarrow \alpha.a\beta a가 터미널 심볼이면 a를 입력 받았을 때
    • Aαa.βA \rightarrow \alpha a.\beta
  2. 논 터미널인 경우
    • 하나는 위와 같은 방식
    • 논터미널 심볼로 시작되는 state로 ϵ\epsilon을 입력 받아 이동

LR(0) parsing algorithm

  • 시작: $0\$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α.BβA \rightarrow \alpha.B \beta 이면 shift
  2. Aα.A \rightarrow \alpha . 이면 Lookahead
    • 다음 문자열이 Follow(A): reduce
    • 아니면 Shift
  • SLR(1) 파싱 테이블 형태
    • State | Input | Goto
    • s1: 1로 이동
    • r2: 프로덕션 룰 2 수행

LR(1) Item

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

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

  1. 터미널 심볼이면 shift
  2. 논터미널 심볼이면
    • 하나는 위와 같은 shift
    • [Aα.Bβ,b]ϵ[B.Υi,a][A \rightarrow \alpha.B \beta, b] \,\,\,\, \underrightarrow \epsilon \,\,\, [B \rightarrow .\Upsilon_i, a]
      • aFirst(βb)a \in First(\beta b)
  • Start state: [S.S,$][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가 가능하다

profile
벽에 붙은 달팽이 ↑i@

0개의 댓글