[컴파일러] 4. LR 파서

3/23, 3/24

 

상향식 파싱(Bottom-up Parsing)

• 이동 축소 파싱(shift-reduce parsing)과 동일
• 축소 과정을 반복하여 파싱
  • 축소: 생성규칙의 오른쪽과 일치하는 부분 문자열을 왼쪽의 기호로 대체(A->BC면 BC를 A로 대체)
• 맨 오른쪽 유도(right most derivation)의 역순

핸들

• 생성규칙의 오른쪽과 일치하는 부분문자열
• S=>aAw=>abw
• b는 A->b의 규칙에 해당하는 핸들
• w는 모두 단말기호들만으로 구성
• 핸들가지치기(handle pruning): 핸들을 발견하여 왼쪽의 문법기호로 계속 대체하여 파스트리를 축소(시작기호까지 축소)

스택을 이용한 이동 축소 파싱

• 동작
  • 스택이 빈 상태에서 입력문자열을 하나씩 스택 이동(shift)
  • 스택의 맨 위에 핸들 B가 오면 이 핸들을 생성 규칙에 의해 축소(reduce)
  • 다시 입력 문자열을 받아서 축소 동작 반복
  • 입력문자열이 모두 처리되고 스택에 시작기호만 있으면 분석 끝
• 동작의 종류
  • shift: 다음의 입력기호를 스택 위로 옮김
  • reduce: 핸들의 오른쪽 끝이 스택의 맨 위에 오면 이를 축소
  • accept: 파싱의 성공적인 완료
  • error: 오류 발생

이동/축소 충돌: 다음 입력기호에 대해 이동인지 축소인지 결정 불가

=> 우선순위가 필요

축소/축소 충돌: 어떤 생성규칙을 적용할 것인지 결정 불가

=> 선언한 것에 따라 다르게 처리

 

LR 파서(LR Parsers)

• LR(k) 파싱 용어
  • L: left to right scan(왼쪽부터 오른쪽으로 stack 입력)
  • R: right most derivation(오른쪽이 우선도가 큼)
  • k: 파싱을 결정하는데 사용되는 예측기호의 갯수(생략되면 1로 가정)
• 장단점
  • CFG로 쓰여질 수 있는 모든 언어는 LR파싱으로 인식 가능
  • 백트래킹없이 이동축소 파싱이 가능한 가장 일반적인 방법
  • 예측파서로 파싱할 수 있는 문법은 모두 LR 파서로 파싱 가능
  • left to right scan으로 구문오류가 발생하면 곧바로 발견
  • 문법 작성시 많은 작업이 필요: 파서생성기 필요
• 종류
  • SLR(Simple LR): 구현이 쉬우나 인식능력이 가장 빈약
  • CLR(canonical LR): 구현이 복잡하나 인식능력이 좋음
  • LALR(lookahead LR): 구현과 인식능력이 모두 중간정도
• 나열형태
  
  • 스택의 내용과 처리되지 않은 입력을 표시
  • 우문장형태(맨오른쪽유도)를 나열 형태로 표현
• 이동동작
  • 이동축소 파서의 동작과 동일하되 상태만 추가
  • 이동: 현재 입력기호 \a_i와 스택 맨 위의 상태 \S_m을 읽고 결정
• 4가지 유형
  • 나열 형태 (s0 X1 s1 X2 s2 .... Xm sm ai ai+1...an$)
  • action[Sm, ai] = shift s
    • 현재 입력기호 ai와 다음상태 s 푸시
  • action[Sm, ai] = reduce A->b
    • 스택에서 2r개의 기호 팝(r=|b|이고 팝되는 문법기호는 b와 일치)
    • 생성규칙의 왼쪽 기호 A와 다음 상태 s를 푸시
    • 입력기호 변화 없음
  • action[Sm, ai] = accept
    • 파싱 종료
  • action[Sm, ai] = error
    • 오류 발견. 오류 회복 루틴 호출