[목차]
7.1. 결정적 구문분석
7.2. RD 파서
7.3. Predictive 파서
7.4. Predictive 파싱 테이블 구성
7.5. Strong LL(k) 문법과 LL(k) 문법
7.1 결정적 구문분석
Deterministic Top-Down Parsing
적용할 생성규칙을 결정적으로 고를 수 있을 때.
One pass nobackup
스캔을 한번만(left->right) 해서 파싱. no backtracking
Top-down parsing with nobackup = LL parsing(Left to right scanning and Left parse)
Backtraking 없이 하기 위한 조건: FIRST와 FOLLOW => LL condition
FIRST(alpha)
알파로부터 유도되는 string에서 첫번째로 나오는 terminal들의 집합
*FIRST 구하는 규칙
1) X가 terminal이라면, FIRST(X)={X}
2) X가 a(알파)를 유도해내면, FIRST(X)=FIRST(X) U {a}
3) X-> epsilon이면, FIRST(X)=FIRST(X) U {epsilon}
4) X->Y1Y2...Yk에서 Y1Y2...Yi-1이 * derivation을 거쳐 epsilon을 만들어낼 수 있다면,
Union(j=1, i-1)Yj-{epsilon}
if) Y1Y2...Yk가 * derivation에서 epsilon을 만들어 낼 수 있는 경우(즉, 마지막 nonterminal symbol까지 모두 epsilon을 만들어 낼 수 있다면), FIRST(X)=FIRST(X) U {epsilon}
FIRST(T) = FIRST(RS) U FIRST(TaT)에서 FIRST(RS)부분을 살펴보면,
R->epsilon 유도는 되지만 S->epsilon 유도는 안되기 때문에 4)번 규칙에 의해 Union(j=1, i-1)Yj-{epsilon} 해당 부분이 적용됨.(Y1Y2...Yk*=>epsilon이 불가하므로, FIRST에 epsilon을 추가하지 않도록 주의!)
FOLLOW(A)
임의의 sentential form에서 A symbol의 오른쪽에 바로 붙어서 나오는 터미널들의 집합
LL condition
backtracking을 안하기 위한 조건
LL condition을 만족하기 위한 규칙
A->alpha | beta 일 때,
1) 공통 lhs가 존재할 때, lhs에서 파생되는 rhs 각각의 FIRST들에 대한 교집합이 없어야 함.
FIRST(alpha) 교집합 FIRST(beta) = 공집합
Top Down 방식에 적합한 form은?
GNF이다.
CNF
GNF: 항상 터미널이 앞에 나오기 때문에 FIRST 계산하기가 정말 편함.
Recursive-Descent Parser
Top down 파서를 구성할 때, recursive procedures의 집합으로 구성이 됨.