렌더링 과정에서 파싱은 매우 중요하다. HTML등의 문서 파싱 작업은 브라우저가 코드를 이해하고 사용할 수 있는 구조로 바꾸는 것을 의미한다. 파싱으로 나오는 결과는 문서 구조를 나타내는 노드 트리 형태로 나오게 된다.

이를 파싱 트리(Parsing Tree) 혹은 문법 트리(Syntax Tree)라 지칭한다.

2+3+1을 예시로 들면, 아래와 같은 트리의 형태가 된다.

파서 - 어휘 분석기 조합

파싱은 두 개의 분석으로 나눌 수 있다.

  • 어휘 분석
    자료를 토큰으로 변환, 토큰은 유효하게 구성된 단위의 집합체이다.
    인간의 언어로 표현하면 사전이라 볼 수 있다.
  • 구문 분석
    언어 구문의 규칙을 나타낸다.

파싱 반복 순서

1) 어휘 분석기에게 새 토큰을 받아서 구문 규칙과 일치하는지 확인
2) 규칙에 맞으면 해당 토큰을 구문 분석기가 해당하는 노드를 파싱 트리에 추가한다.
3) 계속 또 다른 토큰을 요청한다.

규칙에 맞지 않으면 파서는 토큰을 내부적으로 저장하고 토큰과 일치하는 규격이 있을 때까지 요청한다. 맞는 규칙이 없을 경우 예외로 처리한다. 이는 문서가 유효하지 않은 구문 에러를 포함하고 있다는 걸 알 수 있다.

변환

파서는 어휘, 구문 분석을 담당하는 어휘 분석기, 구문 분석기가 내장되어 있다.

  • 어휘 분석기
    유효한 토큰으로 분해 (공백이나 개행 같은 의미없는 문자 제거)
  • 구문 분석기
    분석한 어휘를 구문 규칙에 따라 문서 구조를 분석해서 파싱 트리 생성

파싱으로 만들어진 파서 트리변환 과정을 통해 기계 코드로 만들어진다.

이 과정을 컴파일 과정이라고 생각하면 편하다. 즉, 기계와 의사소통을 하기 위해 파싱 트리로 만들어진 구조를 변환하여 기계 코드화 하는 과정이다.

파싱 예

수학 언어로 예를 들어보면,

어휘 : 수학 언어는 정수, 더하기 기호, 빼기 기호를 포함

구문 :

  1. 언어의 기본적인 요소는 표현식, 항, 연산자
  2. 표현자의 수 제한 X
  3. 표현식은 ‘항’ 뒤에 ‘연산자’, 그 뒤에 ‘항’이 붙는 형태로 정의한다.
  4. 연산자는 더하기 토큰 또는 빼기 토큰
  5. 정수 토큰 또는 하나의 표현식은 항이다.

예시 : 2 + 3 - 1

규칙에 맞는 첫 번째 부분 문자열은 2 (5번 규칙에 따르면 하나의 항) → 2 + 3 (3번 규칙) → 2 + 3 은 항과 연산자와 항으로 구성된 하나의 새로운 항, 2 + 3 + 1은 하나의 표현식, 2++은 어떤 규칙과도 맞지 않기 때문에 유효하지 않은 입력값인 걸 알 수 있다.

어휘와 구문에 대한 공식적인 정의

  • 어휘

    INTEGER : 0|[1-9][0-9]*
    PLUS : +
    MINUS : -

어휘는 보통 정규표현식으로 작성한다.

  • 구문

    expression := term operation term
    operation := PLUS | MINUS
    term := INTEGER | expression

구문은 BNF (Backus-Naur Form)표현되는 형식에 따라 정의한다.

문법이 문맥 자유 문법 이라면 언어는 정규 파서(위에서 살펴본)로 파싱 할 수 있다. 다시 말하면, 문맥 자유 문법BNF (Backus-Naur Form) 로 표현할 수 있는 언어를 뜻한다.

파서의 종류

  • 상향식 파서
    입력 값이 규칙에 맞을 때까지 찾아서 입력 값을 규칙으로 바꿈 이 과정은 입력값의 끝 값까지 이어진다.
  • 하향식 파서
    2+3 과 같은 표현식에 해당하는 높은 수준의 규칙을 먼저 찾는다. 그 다음 표현식으로 2+3+1을 찾을 것이다. 표현식을 찾는 과정은 다른 규칙을 점진적으로 찾아내는 방식.

파서 자동 생성기

위에서 다룬 일련의 과정을 자동으로 처리해주는 생성기들이 있다.

  • Flex

대표적으로

  • Flex
  • Bison

이 있다.