브라우저

[브라우저] 파싱이란?(Parsing이란?) - 파싱의 과정(어휘 분석, 구문 분석)

디벨로펄 2023. 2. 26.
반응형

■ 파싱

특정 데이터에서 원하는 데이터만 추출해내는 과정을 '파싱'이라 알고 사용해왔다. 또는 특정 양식의 문서를 원하는 양식으로 변환하는 것을 파싱이라 사용했다. (뇌피셜...)

여기서는 '문서 파싱'은 브라우저가 이해할 수 있는 구조로 코드를 변환하는 작업을 말한다. 파싱의 결과로는 노드트리(=파싱트리=문법트리)가 도출된다.

 

예시) 2+3-1 와 같은 식은 다음과 같은 트리가 된다. 식은 표현식과 숫자로 이루어져 있으며, 각각은 노드가 된다.

 

문법(파싱의 문법)

문맥 자유 문법 : 파싱은 문서에 작성된 언어 또는 형식의 규칙에 따르는데, 파싱할 수 있는 모든 형식은 정해진 용어와 구문 규칙에 따라야 한다. (쉽게 말해서, 특정 규칙에 따라 작성된 문서들만 파싱이 가능하다. 대부분의 프로그래밍 언어가 문맥 자유 문법에 해당한다고 한다.) 인간의 언어와 같이 규칙을 규정하기 어려운 경우는 기계적인 파싱이 불가능하다.

 파서 - 어휘 분석기 조합

파싱은 어휘 분석구문 분석 두 가지로 구분된다.

어휘 분석은 자료를 토큰으로 분해하는 과정이다. (토큰 = 유효하게 구성된 단위의 집합체...? = 의미를 가지는 하나의 단어 정도로 이해하면 될듯. ex : body, div...)

구문 분석은 언어의 규칙을 적용한다.

 

파싱 과정은 아래와 같이 이루어지며, 문서를 모두 읽고 파싱 트리 완성 또는 예외 처리하기 전까지 반복된다.

 

 변환

파싱을 통해서 보통 문서를 다른 양식으로 변환하게 된다.

소스코드> 파싱> 파싱 트리 > 변환> 기계코드(ex 컴파일 과정) 

 

 

* BNF 형식(Backus Naur Form)
: https://atoz-develop.tistory.com/entry/%EA%B5%AC%EB%AC%B8%EB%A1%A0-BNF-EBNF-%EA%B5%AC%EB%AC%B8%EB%8F%84%ED%91%9C-%ED%91%9C%ED%98%84%EB%B2%95

메타 기호 의미
::= 정의
| 택일(OR)
<> 비단말 기호

어휘는 정규표현식(Regular Expression)으로 표현되고, 구문은 BNF라는 형식에 따라 정의된다.

 

 파서의 종류 : 하항식, 상향식

- 하향식 파서 : 높은 수준에서 낮은 수준으로 구문 분석.

ex ) 2+3-1 : 2+3 먼저 분석 => 2+3-1 분석.

 

- 상향식 파서 : 낮은 수준에서 점차 높은 수준으로 구문 분석.( = 이동 감소 파서라고 부르기도 한다.)

입력 값이 규칙에 맞을때까지 찾아서 맞는 입력 값을 규칙으로 바꾼다. 부분적으로 일치하는 표현식은 파서 스택에 쌓인다.

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

 

 파서 생성기 : 파서를 생성해줄 수 있는 도구

언어에 어휘나 구문 규칙 같은 문법을 부여하면 동작하는 파서를 만들어준다. 직접 파서를 만들고 최적화하는 것은 어려우므로 파서 생성기를 잘 활용해야한다.

Webkit은 : 어휘 생성을 위한 플렉스(Flex) 와 파서 생성(구문분석)을 위한 바이슨(Bison)을 사용한다. 

Flex는 토큰의 정규 표현식 정의를 포함하는 파일을 입력 받으며,

Bison은 BNF 형식의 언어 구문 규칙을 입력받는다.

 

■ 정리

- 파싱되는 문서는 특정 규칙에 따라 작성되어야 한다.

- 파싱은 어휘분석과 구문 분석 단계로 이루어진다.

- 어휘 분석기는 토큰화작업을 하며

- 구문 분석기는 토큰을 읽어 노드로 바꾸고 파싱 트리에 추가한다.

 

* 파서 생성기에 대해서는 지금 시점(2023.02.26)에서는 더 deep하기 들어가기 힘들듯.

개념만 확실하게 집고 가는 걸로 하자.

 

 

 

■ 참고자료

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

반응형

댓글