Total
Search
1. LR 구문분석
•
순위관계에 의한 구문분석
◦
handle을 찾기 위해서 여러 가지 제약조건들을 줌
◦
이런 제약조건들 때문에 일반적인 프로그래밍 언어의 구문구조를 표현하기에는 적당하지 못한 단점 존재
•
LR(Left to right scanning and Right parse) 구문분석
◦
일반적인 프로그래밍 언어의 구문구조를 표현하고 구문분석을 하기 위해서 나온 방법
◦
종류
▪
SLR : Simple LR
▪
CLR : Canonical LR
▪
LALR : Lookahead LR
◦
푸시다운오토마타
2. LR(0) 항목과 Closure
2.1. LR(0) 항목
•
생성규칙의 오른쪽에 점기호(dot symbol)를 가진 생성규칙
2.2. 증가문법
•
G=(Vn,Vt,P,S)에서 G에 첨가된 문법
•
즉, 시작기호 {S'→S} 를 하나 더 추가한 문법
2.3. Closure
•
정의
◦
마크기호가 [A→ α․Bβ]와 같이 논터미널인 경우에 이 논터미널을 생성규칙의 왼쪽으로 갖는 LR(0) 항목을 구하는 것
◦
[A→ α·Bβ] 에서, 논터미널 B를 생성규칙의 왼쪽으로 갖는 LR(0) 항목들의 집합
◦
closure는 반복적으로 계속 적용
•
예
3. Canonical Collection
•
파싱표에서 상태들의 집합
•
GOTO 함수
◦
GOTO(I, X) ＝ closure({[A → αX․β]| [A → α․Xβ∈I})
◦
현재 마킹한 상태에서 구문분석을 하기 위해, 마크기호를 하나씩 읽는 것을 의미
•
예시
GOTO 그래프
4. GOTO 그래프
•
GOTO 그래프
•
예시
5. SLR 파싱표 작성
5.1. SLR 파싱표 알고리즘
•
알고리즘
5.2. 예시
•
예시
•
논터미널 기호 → GOTO 함수
•
Reduce 항목을 포함한 상태들 예시
