브라우저는 어떻게 동작하는가 (part. 04)

본 내용은 NAVER D2의 '브라우저는 어떻게 동작하는가? (by Tali Garsiel)'의 내용을 복습하며 작성했습니다.

https://d2.naver.com/helloworld/59361

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

어휘는 보통 정규 표현식으로 표현한다. 예를 들면 언어는 다음과 같이 정의될 것이다.

 

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

 

보시다시피 정수는 정규 표현식으로 정의한다.

 

구문은 보통 BNF 라고 부르는 형식에 따라 정의한다. 언어는 다음과 같이 정의될 것이다.

 

---

 

BNF 표기법

 

---

 

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

 

문법이 문맥 자유 문법이라면 언어는 정규 파서로 파싱할 수 있다. 문맥 자유 문법을 쉽게 말하면 완전히 BNF로 표현 가능한 문법이다.

 

파서의 종류

파서는 기본적으로 하향식 파서와 상향식 파서가 있다. 하향식 파서는 구문의 상위 구조로부터 일치하는 부분을 찾기 시작하는데 반해 상향식 파서는 낮은 수준에서 점차 높은 수준으로 찾는다.

 

두 종류의 파서의 예제 파싱 과정 확인

 

하향식 파서는 2+3과 같은 표현식에 해당하는 높은 수준의 규칙을 먼저 찾는다. 그 다음 표현식으로 2+3-1을 찾을 것이다. 표현식을 찾는 과정은 일치하는 다른 규칙을 점진적으로 더 찾아내는 방식인데 어쨌거나 가장 높은 수준의 규칙을 먼저 찾는 것으로부터 시작한다.

 

상향식 파서는 입력 값이 규칙에 맞을 때까지 찾아서 맞는 입력 값을 규칙으로 바꾸는데 이 과정은 입력 값의 끝까지 진행된다. 부분적으로 일치하는 표현식은 파서 스택에 쌓인다.

 

스택	입력값
	2+3-1
항	+3-1
항 연산자	3-1
표현식	-1
표현식 연산자	1
표현식

상향식 파서는 입력 값의 오른쪽으로 이동하면서(입력 값의 처음을 가리키는 포인터가 오른쪽으로 이동하는 것을 상상) 구문 규칙으로 갈수록 남는 것이 점차 감소하기 때문에 이동-감소 파서라고 부른다.

 

파서 자동 생성

파서를 생성해 줄 수 있는 도구를 파서 생성기라고 한다. 언어에 어휘나 구문 규칙 같은 문법을 부여하면 파서 생성기가 파싱을 위해 동작하는 파서를 만들어준다. 파서를 생성하는 것은 파싱에 대한 깊은 이해를 필요로 하고 수동으로 파서를 최적화하여 생성하는 것은 쉬운 일이 아니기 때문에 파서 생성기는 매우 유용하다.

 

웹킷은 잘 알려진 두 개의 파서 생성기를 사용한다. 어휘 생성을 위한 플렉스(Flex)와 파서 생성을 위한 바이슨(Bison)이다. 렉스(Lex)와 약(Yacc)이라는 이름과 함께 들어본 적이 있을지도 모르겠다. 플렉스는 토큰의 정규 표현식 정의를 포함하는 파일을 입력받고 바이슨은 BNF 형식의 언어 구문 규칙을 입력 받는다.