[컴파일러]Top-Down 방식과 Bottom-up 방식

소개글

Top-Down 방식과 Bottom-up 방식의 비교입니다.

목차

없음

본문내용

◆ Top-Down 방식
- 루트 노드로부터 생성 규칙이 적용되어 직접 유도될 때마다, 트리가 구성된다.
- 주어진 스트링이 정의된 문법에 의해 인식되는가를 검사하기 위하여 back tracking을 하며, 구문분석을 하는 방법으로 다음과 같은 과정을 가진다.

1. 처음에 시작 심벌의 첫번째 생성 규칙을 적용 유도한다.
2. 생성된 문장 형태의 스트링과 입력 스트링을 차례로 비교한다.
3. 비교 과정에서, nonterminal 이 생성된 스트링에 나오면, 이 nonterminal 의 첫번째 생성 규칙을 적용하여 유도하여, 유도된 스트링과 입력이 같으면 계속 비교해 나간다.
4. 비교한 두 심벌이 같지 않으면, 생성 규칙을 잘못 적용한 것이므로, 현재 적용된 생성 규칙을 제거하고 다른 생성 규칙을 적용한다. 입력 심벌의 위치는 제거한 생성 규칙에서 보았던 심벌의 개수만큼 입력으로 되돌려 보낸다.
5. 이상과 같은 과정을 반복하다가 더 이상 적용할 생성 규칙이 없으면, 주어진 스트링을 틀린 문장으로 인식하고, 문장형태에 나타난 스트링이 주어진 스트링과 같아지면, 올바른 문장으로 인식한다.

참고 자료

없음