Parsing의 광의적인 의미
광의적인 의미에서는 특정 구조의 데이터에서 의미있는 정보를 추출하는 것들은 모두 파싱이라고 부른다.
- 이메일 이름에서 도메인을 분리하는 행위
- JSON 문자열을 객체로 변환시켜주는 행위
그냥 어떤 데이터 뭉치를 내가 쓰려는 데이터 뭉치로 바꾸는 모든 것들을 퉁쳐서 파싱이라고 부른다. 다만 형식언어론에서는 특정 조건을 만족시켜야만 파싱이라고 부를 수 있다.
촘스키 언어 계층이론
촘스키가 고안한 형식언어론에서 언어는 생성문법에 따라 해석되며, 생성문법에도 종류가 있어, 아래와 같은 계층을 이룬다고 가정했다.
- Type 3 — 정규 문법 (Regular Grammar)
- 정규식이 바로 이 단계의 언어
- DFA(유한오토마타)로 표현 가능
- 재귀 및 중첩구조는 표현하지 못하고, 단순히 이전의 출력값에 따라 수동적으로 해석된다.
- 정규 문법에 따라 데이터를 변환시키는 것을 lexer라고 한다.
- Type 2 - 문맥 자유 문법 (CFG)
- 재귀 및 중첩이 가능하다
- 일반적인 프로그래밍 언어가 CFG 레벨로 표현되는 언어이다.
- CFG에 따라 데이터를 변환시키는 것을 Parser라고 한다.
- Type 1,0
- 이론상으로 존재하지만, 일반적인 프로그래밍 언어는 type2 단계에서 충분히 표현된다.
즉, 재귀 및 중첩인 부분을 처리할 수 있어야 Parser라고 부를 수 있다. 위에서 들었던 사례 중, 이메일 이름에서 도메인을 분리하는 정규식은 엄밀히는 Parser가 아닌 것이다. (정규식은 type-3 문법에 속하기 때문) 반면 JSON을 파싱할 때는 반드시 재귀적인 문법으로 표현되어야 하므로, CFG 문법에 따라야한다. 즉 엄밀한 의미의 Parser가 맞다.
{ a: { c: { // ... 이런식으로 구조가 재귀되는 부분은 CFG 문법으로 해석해야 한다. // 따라서 JSON은 대표적인 CFG 문법으로 표현되는 언어이다. }, }, b: { } }
여담으로 촘스키가 고안한 형식언어론과 언어 계층이론은 언어학에서 인간 언어(자연어)의 문법을 설명하려고 등장한 이론이나, 현재 언어학계에서는 자연어는 촘스키 언어 계층이론으로 설명하기 힘들다는 것이 현대 중론이다. 정작 컴퓨터 과학 분야에서는 인공 언어를 쉽게 표현가능하다는 점에서 형식언어론이 절찬리에 사용된다. (컴파일러, 파서, 기타 데이터 변환이 필요한 온갖 분야…)
형식언어론, 생성문법에 대한 이론적인 내용과, lexer와 parser를 실제로 구현하는 방법에 대해서는 “컴파일러” 이론 과목에서 자세히 공부할 수 있다.
컴파일 단계
source.c ↓ Lexical Analysis (토큰화), token stream 생성 ↓ Parsing (구문 분석), AST(추상구문트리) 생성 ↓ Semantic / IR / Codegen, AST 순회하며 새로운 Code를 만들어낸다.
- Lexical 에서 오류가 났다는 것은, 곧 토큰 변환에 실패했다는 것이다.
- Parsing에서 오류가 났다는 것은, 곧 컴파일러가 프로그램의 구조를 만들어내는데 실패했다는 것이다.
- Parsing의 결과물로, AST라는 트리를 생성한다. 그냥 토큰 stream은 그저 의미없는 토큰의 나열일 뿐이다. 컴파일러는 이 상태에서는 아무것도 해석할 수 없다. AST를 만들게 되면 그 때서야 트리 구조를 이용해 재귀구조와 언어의 구조를 파악할 수 있게된다.
- Semantic Analysis에서는 AST를 순회하며 모순이 없는지 검사한다. (예를 들면 c언어에서 선언한 적 없는 함수를 호출하려고 한다면 이 때 오류가 난다)
- 이후 AST를 순회하며 코드를 생성하는 단계가 Codegen이다.