[PROJECT] Array Parser 만들기 - (1) 기본 개념 정리

[PROJECT] Array Parser 만들기 - (1) 기본 개념 정리

서론

Codesquad step6-1 미션인 Array Parser 미션에 대해 분석하고 프로젝트를 시작하기 전에 알아할 기본 배경 지식을 조사해보겠다.

미션 분석

우리가 사용하는 JSON.Parse() 메서드를 구현하는 것으로 총 3가지 미션이 있다.

1. 단순한 1차원 배열안에 있는 요소를 파싱
2. 중첩된 배열의 요소 파싱
3. 오브젝트 파싱

설계를 할때 단순히 미션을 성공에 초점이 아니라 다음 미션을 같이 생각해서 설계하는 것이 좋을 것 같다.

배경 지식

트리와 그래프
트리와 그래프 모두 자료 구조의 일종으로 서로 비슷한 모양을 가지고 있다.

각각의 성질이 있는데 우선 트리는 다음과 같은 성질이 있다.

트리의 성질

• node 와 edge로 구성되어 있다.
• 하나의 루트노드를 갖는다.
• 로트노드는 자식노드를 가지고 있다.
• 또한 자식노드들도 자식 노드를 가지고 있고, 반복적으로 정의된다.

그래프는 트리를 포함하는 개념을 가지고 있고 따라서 트리는 그래프의 일종이다.

그래프의 성질

• node 와 edge로 구성되어 있다.
• 사이클이 가능하다.

실생활에서 찾아볼수 있는 그래프는 지하철 노선도나, 지도등이 있고 트리는 족보나, 회사 조직도가 있다.

각각의 자료구조 마다 순회하는 방식등이 다르고 사용하는 용도가 다르다.

DFS와 BFS

그래프 탐색 방식으로, 알고리즘 문제에 자주 등장한다.

DFS(Depth First Search)는 한국말로 하면 깊이 우선 탐색이다. 탐색을 진행할 때 한 루트로 찾아보다가 더 이상 탐색할 노드가 없으면 돌아와서 다시 탐색하는 방식이다. 이와 다른 개념인 BFS(Breadth First Search)는 너비 우선 탐색으로 연결된 노드를 모두 탐색 하고 다시 연결되어 있는 노드를 탐색하는 방식이다.

아래 그림을 보면 두 탐색의 차이를 이해하는데 도움이 된다.

아래 동영상은 BFS, DFS를 좀더 쉽게 이해하는데 도움을 주는 동영상이다.

tokenizer, lexer, parser

이번 프로젝트의 주요 핵심인 tokenizer, laxer, parser이다.
우선 이번 프로젝트에서 각각의 하는 일이 다르다. 우선 tokenizer 는 의미있는 단위로 쪼개는 역할을 한다. 그리고 laxer는 각각의 쪼개진 데이터에 의미를 부여한다. 마지막으로 parser는 의미를 부여한 데이터를 구조화시킨다.

좀 더 이해를 돕기 위해 이번 6-1 미션의 문자열을 예로 들어 설명하겠다.

초기에 받은 데이터이다.

"[123, 45, 'hello']"

tokenizer를 거친 문자열이다. 의미있는 단위로 문자열을 쪼갠 상태이다.

['[', '123', '45', "'hello'", ']']

laxer를 거친 데이터이다. 각각의 데이터에 의미를 부여하였다.

[{type: 'LBracket', value: '['},
 {type: 'number', value: 123},
 {type: 'number', value: 45},
 {type: 'string', value: 'hello'},
 {type: 'RBracket', value: ']'}]

parser를 거친 데이터이다.

{ type: 'array',
  child: 
   [ { type: 'number', value: 123, child: [] },
     { type: 'number', value: 45, child: [] },
     { type: 'string', value: 'hello', child: [] } 
    ] 
}

출처

그래프와 트리 이미지 http://blog.daum.net/kimjaehun12/93

DFS와 BFS 이미지 https://mygumi.tistory.com/102