Top-down, Bottom-up Parsing
Category: Compilers
Tags: parsing
Parsing
Parsing은 구문을 분석하는 과정으로, 입력 받은 문자열이 해당 문법을 잘 따르고 있는지 검사하고 parse tree를 반환한다. Lexar는 구문을 토큰 단위로 쪼개는 역할을 했다면, Parser는 쪼개진 토큰을 구조화해서 계층 구조로 나타낸다.
Parser의 종류는 파싱 방식에 따라 다음과 같이 구분된다.
- Top-down : 위에서부터 아래로 parse tree를 그리면서 결과를 찾는 방식
-
Bottom-up : 아래에서 위로 leaves에서 root를 찾아가는 방식
Top Down Parsing
Top-down 방식은 큰 문제를 여러 작은 문제로 분해해서 해결하는 방식으로, 결국 위에서부터 아래로 토큰을 하나씩 검증하고 돌아가면서 해결하는 방식이다. 예를 들어, 다음과 같은 grammar가 있다고 했을 때,
“bcd”가 해당 문법에 해당되는지 top-down 방식으로 검증하는 과정이다.
Top Down 단점 1 : backtracking
계속 가지치기를 해보면서 해당 선택이 맞는지 아닌지를 확인하고, 아니면 다시 돌아가는 backtracking을 하기 때문에 시간이 오래 걸린다는 단점이 있다. 또한 가지치기를 한 결과가 최종 결과가 맞지 않으면 중간 과정에 대한 computation들의 의미가 전부 사라지는데, 이를 방지하기 위해 미리 결과를 예측해볼 수 있는 Top-Down Predictive Parsing을 수행한다.
Top-Down Predictive 방식으로 파싱하는 과정 -> 자세한 내용은 LL(1) parsing에서 !
Top Down 단점 2 : Left Recursion
Left-Recursion 문제가 생길 수 있다. 예를 들어 $A -> dA$ 라는 규칙에서 진행하게 되면, d가 나올 때까지 반복하기 때문에 무한 루프에 빠지게 될 수 있다. 따라서 이러한 문제를 방지하기 위해서는 Left Recursion을 Right Recursion으로 바꾸어서 제거해야 한다.
Left factoring 방법을 통해 Right Recursive 형태로 바꾸는 과정
-> 새로운 변수를 통해 무한루프가 생성되는 부분($Aa$)을 치환하는 역할
Bottom-up Parsing
아래 leave에서 root로 올라가며 찾는 방식이다. 아래 결과에서부터 위로 찾아나가기 때문에 다음에 어떤 것이 올지에 대한 고민을 할 필요가 없고, left recursion으로 인한 무한 루프도 고려하지 않아도 된다. 따라서 기존의 grammar를 그대로 사용해도 된다는 장점이 있다. Top Down의 단점을 대부분 보완하고 있어서 많은 컴파일러 파서가 이 방식으로 구현되어 있다.
다음은 Bottom Up 방식을 통해 파싱하는 과정이다. 문자열의 뒤에서 시작해서 하나씩 reduce하면서 위로 올라가며 찾는 방법이다. -> 자세한 내용은 SLR, CLR parsing에서 !
Top Down vs. Bottom Up 비교
| Direction of scanning | Derivation discovered | Parse tree construction | Algortithm used | |
|---|---|---|---|---|
| Top-Down (LL) | left → right | left-most | top-down | predictive |
| Bottom Up (LR) | left → right | right-most | bottom-up | shift to stack and reduce(pop) |