목차
📁 Top-down으로 구문 분석하기
Top-down 방식은 직관적이고, 좌측 유도 과정과 유사하다.
진행 과정은 다음과 같다.
1) 시작 심벌이 왼쪽(lhs)에 존재하는 생성규칙 중 첫번째 생성규칙으로 유도하여 문자열을 생성한다.
2) 유도를 통해 생성된 문자열과 입력 문자열을 차례로 비교한다.
3) 유도된 문자열과 입력 문자열이 같으면 계속 비교해나간다.
4) 유도과정에서 생성된 문자열에 Nonterminal이 나오면, 이 Nonterminal의 첫번째 생성규칙으로 또 다시 유도해서 새 문자열을 생성한 후 비교해간다.
5) 유도된 문자열과 입력 문자열이 다른 경우, backtraking을 수행한다.
🌱 backtracking
비교한 두 문자열이 동일하지 않을 경우, 직전 생성규칙을 잘못 적용한 것이므로 원위치 시키고 다른 생성규칙을 적용해야한다. 이 과정을 backtracking이라고 한다.
1) 직전 생성규칙은 적용하지 않았던 것으로 하고, 생성된 문자열을 직전 규칙 적용 전으로 환원시킨다.
2) 입력 문자열을 직전 규칙 적용 후 비교됐던 문자 개수만큼 원위치시킨다.
3) 다른 생성규칙으로 유도를 시작하는데, 마찬가지로 같지 않은 문자가 나타나면 다시 위 과정을 반복한다.
4) 위 과정을 반복하다가 더 이상 적용할 생성규칙이 없으면 입력 문자열은 틀린 문장으로 인식한다.
backtracking은 Top-down 파싱 방법에서 좋지 않은 기능이다.
3번 과정과 같이 유도를 계속 반복하다보면 오버헤드가 커질 가능성이 있고, 최악의 경우 오류가 발생하면 모든 경우의 수를 봐야하기 때문이다.
backtracking의 예를 들어보자.
스트링 accd가 위 문법의 올바른 문장인지 확인해보자.
1) 먼저 1번 규칙을 수행한다.
2) 입력 문자열에서 a이후 c가 오므로 4번 규칙을 수행한다.
3) 지금까지 생성된 문자열은 ac로 입력문자열과 동일하지 않으므로 backtracking을 수행하여 다시 1번 규칙 이후 적용될 규칙을 찾는다.
4) A의 다른 규칙인 3번 규칙을 적용한다.
5) 이번에도 동일하지 않은 문자열이 생성되므로 backtracking을 진행하여 1번 규칙 이후 적용될 규칙을 찾는다.
6) 매칭시킬 A 규칙이 없으므로 다시 backtracking을 진행하여 처음 적용될 규칙을 찾는다.
7) 2번 규칙을 적용한다.
8) 입력 문자열에서 a이후 c가 오므로 5번 규칙을 먼저 수행한다.
9) 문자열이 동일한 것이 인식되었다.
오른쪽 유도 과정처럼 같지 않은 문자가 나온 경우 backtracking을 수행하고, 다시 다른 규칙으로 유도를 진행하면 왼쪽과 같은 결과를 얻을 수 있다.
📁 LL파싱
LL파싱이란 왼쪽에서 오른쪽으로 읽어가면서(Left to right scanning) 좌파스(Left Parse)를 생성하는 파싱방법이다.
즉 유도할 때 좌측 유도를 사용하고, top-down으로 구문을 분석하겠다는 뜻이다.
현재의 입력 문자와 생성된 terminal 심벌이 같지 않으면 되돌아가지 않고 바로 틀린것으로 간주하므로 backtracking이 없고, top down 방식의 시간 낭비를 줄인다는 장점이 있다.
하지만, LL파싱이 가능한 문법은 결정적 파싱이 가능한 문법 뿐이므로 파싱의 범위가 매우 좁다는 단점이 있다.
또한 입력문자를 보고, 각 입력문자 당 적용될 생성규칙을 미리 뽑아두어야하는 준비 과정이 필요하다.
🌱 결정적 파싱(deterministic Parsing)
입력 문자를 보고 적용될 생성규칙이 결정적으로 선택되어 유도하는 방식을 결정적 파싱이라고 한다.
예를 들어, 아래와 같은 문법은 a로 시작하는 규칙이 두 개이므로 입력 문자가 a일 경우 어떤 규칙을 선택해야하는지 결정할 수 없다.
LL 파싱은 결정적 파싱이 되는 문법을 선별하거나 다듬은 문법만 대상으로 수행하며, 각 입력문자 당 적용될 생성규칙을 미리 뽑아두고 시작한다.
이를 위해 규칙으로부터 필요한 정보를 파악하여 모으는데, 이는 FIRST, FOLLOW, LOOKAHEAD 등의 집합을 말한다.
