공부/컴파일러2011. 8. 22. 16:26


일반적인 top-down을 사용하면 backtracking이 생길 경우 느리니까, backtracking하지 않도록 결정적인 파싱 방법이 필요. 그러한 파싱 방법을 LL 파싱.

FIRST
논터미널 A로 부터 유도되어 첫번째로 나타날 수 있는 터미널의 집합.

nullable
논터미널 A가 ε를 유도할 수 있으면 A를 nullable하다. 

FOLLOW
생성규칙이 ε을 유도할 수 있으면 FIRST만 가지고는 생성 규칙을 결정적으로 선택할 수 없다.
논터미널 A 다음에 나오는 심벌에 따라 어느 생성 규칙으로 유도할 것인가를 결정한다. 

LL 조건
논터미널을 대치하기 위한 생성 규칙을 결정적으로 선택하기 위한 조건.
한 논터미널에 2개 이상의 생성규칙이 있을 때,
각 생성규칙의 FIRST가 달라야 하고,
한 생성 규칙이 ε을 유도할 수 있으면, 그 생성규칙의 FOLLOW와 다른 생성규칙의 FIRST가 달라야 한다.

LL방법을 실제로 사용하는 구문분석기
1) Recursive-descent
논터미널에 대한 유도를 각 논터미널별로 구현되어 있는 함수 호출로 처리.
논터미널에 적용할 생성 규칙을 정하기 위해 Lookahead를 조사. Lookahead는 각 생성규칙에서 첫번째로 유도될 수 있는 터미널들의 집합.
2) Predictive 파서
Recursive-descent파서는 생성규칙이 바뀔 때마다 프로그램을 다시 고쳐야 하는 단점이 있다.
Predictive파서는 파싱테이블만 수정하면 된다.
스택의 top과 현재 입력 심벌이 같을 경우 pop, 
expand : 스택의 top이 논터미널일 경우 생성규칙으로 바꿔서 역순으로 넣는다.
accept : 스택의 top과 입력이 모두 $인 경우, 파싱 성공
error

'공부 > 컴파일러' 카테고리의 다른 글

중간언어  (0) 2011.08.24
LR 구문 분석  (0) 2011.08.24
구문 분석 (syntax analysis)  (0) 2011.08.22
context-free grammar  (0) 2011.08.20
regular language  (0) 2011.08.20


Posted by skyjumps