TIL
- BNF
- 상향식 파서
- 하향식 파서
1. BNF
HTML은 어떻게 파싱될까.
파싱은 기본적으로 노드로 구성된 트리 구조(파싱 트리 또는 문법 트리)를 생성한다.
이 파싱은 정해진 어휘와 구문 규칙에 따라서 이루어지고, 어휘와 구문 규칙을 문맥 자유 문법이라고 부른다.
어휘 : 보통 정규표현식으로 정의한다.
INTEGER : 0|[1-9][0-9]*
PLUS : +
MINUS : - 구문 규칙 : 보통 BNF라는 형식으로 정의한다.
expression := term operation term
operation := PLUS | MINUS
term := INTEGER | expression expression은term과operation으로 구성되어 있다.operation은PLUS또는MINUS로 구성되어 있다.term은INTEGER또는expression으로 구성되어 있다.
이러한 어휘와 구문 규칙을 가지고 `2 + 3 - 1` 이라는 수식을 파싱하면,
| 2 | + | 3 | - | 1 |
|---|---|---|---|---|
| INTEGER | PLUS | INTEGER | MINUS | INTEGER |
| 파싱 | 수식 |
|---|---|
| 2 + 3 - 1 | |
INTEGER (= term) | + 3 - 1 |
term PLUS( = operation) | 3 - 1 |
term operation term (= expression) | - 1 |
expression operation | 1 |
expression operation term (= expression) |
2. 상향식 파서
높은 수준의 규칙에서 시작해서, 낮은 수준의 규칙을 찾아가는 방식
위에 2 + 3 - 1에 대한 파싱은 상향식 파서에 따른 파싱 결과이다.
파싱 대상의 시작부터 끝까지 탐색하며, 작은 수준의 어휘인 INTEGER, PLUS, MINUS로부터 시작한다.
그것들로 구성된 term과 operation을 찾고, 이들로 이루어진 expression과 그 모두를 아우르는 더 상위의 expression을 찾으며 트리 구조를 생성한다.
이때 expression operation처럼 부분적으로 일치하는 경우에는 스택에 쌓인 상태로 파싱을 이어간다.
3. 하향식 파서
낮은 수준의 규칙에서부터 높은 수준의 규칙을 만들 때까지 찾아가는 방식
상향식 파서와 반대로 가장 큰 수준의 규칙부터 하위 규칙과 어휘 수준으로 탐색을 해나가는 방식이다.
마찬가지로 2 + 3 - 1을 예로 들면,
| 파싱 | 수식 |
|---|---|
expression | 2 + 3 |
term operation term | 2 + 3 |
expression | 2 + 3 - 1 |
(term operation term) operation term | 2 + 3 - 1 |
2 + 3이라는 표현식을 찾아 분리하여 확인한 후, 다음 표현식인 2 + 3 - 1을 찾아 다시 하위로 내려가며 해석한다.
여기서 문제는 HTML은 이 기본적인 상향식, 하향식 파서를 정상적으로 사용할 수 없다. 다소 너그럽다는 HTML의 특성 때문이다.
HTML은 태그를 작성함에 있어 생략이 가능하도록 되어있다. 이러한 특성은 개발자의 실수를 넘길 수 있다는 장점이 있지만 반대로 그러한 특성으로 인해 HTML 파싱은 일반적인 파서로는 어려워지는 문제가 생긴다.
다음은 이 HTML 파싱에 대해서 알아보자!
