JSON.parse 직접 만들어보기

Riiid Teamblog
Riiid Teamblog KR
Published in
15 min readDec 24, 2020

By 최종찬

최종찬님은 Front-end Engineer로 Riiid의 Web Chapter를 리드하고 있습니다.

웹 개발을 하다보면 JSON 형식을 일상적으로 다루게 됩니다.

다른 많은 직렬화 형식들은 자바스크립트에 내장된 파서가 따로 없어서 사용이 불편하지만 JSON은 JSON.parse 함수가 제공돼서 편리하게 사용할 수 있죠.

반면 객체의 키를 항상 쌍따옴표로 감싸야 하고 주석도 사용할 수 없고 객체나 배열 끝에 콤마를 남길 수도 없는 등 미묘하게 불편한 지점도 있습니다.

JSON.parse 같은 함수는 어떻게 만드는 걸까요? 직접 만들 수 있다면 문법을 약간 고쳐서 불편했던 부분들을 개선한 나만의 JSON을 만들수도 있지 않을까요?

이 글에서는 JSON.parse의 이론적 배경과, 이런 파서를 쉽게 만들 수 있게 해주는 실용적인 도구들을 소개하려고 합니다.

파서란

어떤 언어로 작성된 코드가 어떤 구조를 갖고있는지 분석하는 프로그램을 파서(Parser)라고 부릅니다. 파서를 사용해서 분석한 어떤 구조를 추상 구문 트리(Abstract Syntax Tree. 이하 AST)라고 부릅니다.

자바스크립트의 JSON.parse 함수는 JSON 문자열을 입력받아서 자바스크립트 런타임 객체를 반환하는데, 이 런타임 객체가 AST라고 볼 수 있습니다.

JSON.parse 함수는 문자열을 받아서 자바스크립트 객체를 반환합니다.

정규표현식으로 JSON을 파싱할 수 있을까?

TL;DR — 정규표현식만 갖고는 안됩니다.

자바스크립트에는 정규표현식 엔진(RegExp)이 내장돼있죠. 이걸로 정규표현식을 많이 작성해본 분들은 어느 순간 정규표현식 만으로는 분석이 불가능한 언어를 만나본 경험이 있을 겁니다.

얼핏 보기에는 정규표현식으로 분석이 될 것 같이 생겼지만 실제로 그렇지 않은 예시로 회문(Palindrome)이 있는데요, 회문은 토마토, 별똥별 처럼 거꾸로 읽었을 때도 원문과 일치하는 문자열을 뜻합니다.

예를 들어 ab 글자의 조합으로 이루어진 문자열이 회문인지 판단하는 정규표현식을 작성해보려고 하면, /a*|b*|(ab)+a|(ba)+b|a(ab)+aa|b(ba)+bb|(aab)+aa|(bba)+bb|(aabb)+aa|.../ 이렇게 한없이 길어지게 됩니다.

어떤 언어가 정규표현식으로 파싱이 될지 안될지는 이렇게 정규표현식으로 작성을 시도했을때 표현이 한없이 길어지는지를 보거나, 재귀적인 문법이 있는지, 문맥 의존적인 문법이 있는지를 따져보는 것으로 알 수 있습니다.

재귀적인 문법이란 예를 들자면 임의 깊이의 짝 맞추기가 있는지 보는 겁니다. JSON, XML, 수식 등은 임의 깊이의 괄호 짝 맞추기를 해야합니다.

문맥 의존적인 문법이 있는지 보려면 주변 맥락에 따라 분석하는 방법이 달라지는지 보면 됩니다. XML은 닫는 태그에 들어가는 이름이 여는 태그에 적혀있던 이름과 같아야 하기 때문에 문맥 의존적인 문법입니다.

정규표현식은 정규 언어를 분석할 수 있는 도구인데, 재귀적인 문법이나 문맥 의존적인 문법을 사용하면 정규 언어에 속하지 않게 되므로 이러한 문법이 있다면 정규표현식으로 분석이 불가능합니다.

형식 언어와 촘스키 위계

정규 언어는 형식 언어의 일종입니다. 일정한 규칙(문법)으로 구성된 문자열의 집합을 형식 언어라고 부르는데, 프로그래밍 언어도 일정한 규칙으로 분석할 수 있으니 형식 언어라고 볼 수 있습니다.

촘스키 위계는 형식 언어를 언어가 갖는 제약에 따라 몇가지 단계로 구분해 둔 것인데요, 정규 언어, 문맥 자유 언어, 문맥 의존 언어 등으로 나뉩니다.

뒤로 갈수록 제약이 없어지는 구분이기 때문에, 문맥 의존 언어는 문맥 자유 언어를 포함하는 개념이고, 문맥 자유 언어는 정규 언어를 포함하는 개념입니다.

이메일, URL 등은 정규 언어이기도 하지만 문맥 자유 언어이기도 한 거죠. 반면 JSON, 수식 등은 문맥 자유 언어지만 정규 언어가 아닙니다.

XML은 JSON과 유사하게 생겼지만 여는 태그에 들어있는 이름이 닫는 태그에도 똑같이 쓰여야 하므로 문맥 의존성이 있습니다. 파이썬의 블록 들여쓰기 문법 같은 경우에도 앞줄에서 들여쓴 횟수가 뒷줄을 해석하는데 영향을 주므로 문맥 의존 언어입니다.

문맥 자유 언어를 분석할 수 있다면 정규 언어 또한 분석할 수 있습니다. 마찬가지로 문맥 의존 언어를 분석할 수 있다면 문맥 자유 언어 또한 분석할 수 있습니다.

파서 생성기

자바스크립트에 내장된 정규표현식 엔진이, 정규표현식 리터럴을 받아서 정규 언어에 속하는 문자열을 분석해주는 메서드를 제공하듯이, 파서 생성기라는게 있어서 이러한 파서 생성기들은 문맥 자유 문법을 입력으로 받아서 문맥 자유 언어에 속하는 문자열을 분석해주는 프로그램을 생성해줍니다.

우리가 이메일 등을 파싱하기 위해 정규표현식 엔진부터 직접 만들지 않듯이, 좀 더 복잡하게 생긴 언어를 분석할 때에도 파서 생성기를 가져다 사용하면 좀 더 편리합니다.

배커스 나우르 표기법과 기찻길 다이어그램

문맥 자유 문법은 배커스 나우르 표기법(Backus Naur Form. 이하 BNF) 또는 기찻길 다이어그램(Railroad Diagram)으로 표현할 수 있습니다. 각각 문맥 자유 문법을 텍스트 형태로, 그림 형태로 표현하는 방법이라고 생각하면 됩니다.

배커스 나우르 표기법은 비말단기호 -> 말단기호 또는 비말단기호의 나열 같이 생긴 유도규칙의 모음으로 구성됩니다.

json -> object
json -> array
object -> "{}"
object -> "{" members "}"
array -> "[]"
array -> "[" elements "]"
...

위의 BNF는 “jsonobject 또는 array로 치환될 수 있고 object{} 또는 {} 사이에 members가 오도록 치환될 수 있고 ..." 같이 읽으면 됩니다.

보통 가장 위에 있는 유도규칙(json -> ...)이 진입점이 됩니다.

“또는” 부분은 위처럼 여러개의 규칙으로 나눠적어서 표현할 수도 있고, 아래처럼 | 기호를 사용해서 하나의 규칙으로 표현할 수도 있습니다.

# 이 BNF는 바로 위에 있는 BNF와 같은 뜻입니다. json -> object | array
object -> "{}" | "{" members "}"
array -> "[]" | "[" elements "]"
...

위 BNF에서 쌍따옴표로 감싸진 {}, {, }, [], [, ] 등을 말단기호(Terminal)라고 부르고, json, object, array, members, elements 등은 비말단기호(Non-Terminal)라고 부릅니다.

비말단기호는 BNF에 나열돼있는 유도규칙에 의해 다른 내용으로 치환될 수 있지만, 말단기호는 더이상 다른 내용으로 치환되지 않고 말단기호 그대로 출력하거나, 입력과 비교하는데에 사용됩니다.

위의 BNF를 기찻길 다이어그램으로 표현하면 아래와 같습니다.

이 기찻길 다이어그램은 위의 두 BNF와 같은 뜻입니다.

회문을 BNF로 표현해보자

아까 정규식으로 표현하지 못했던 “ab 글자의 조합으로 이루어진 회문"은 BNF 상에서는 아주 간단하게 표현할 수 있습니다.

p -> null | "a" | "b" | "a" p "a" | "b" p "b"

여기서 null은 조금 특수한 뜻인데, 비어있는 문자열이라는 뜻입니다. 엡실론(Epsilon)이라고 부르기도 합니다.

BNF상에서 회문이 간단하게 표현될 수 있는 이유는 "a" p "a", "b" p "b" 규칙에서 확인할 수 있듯이 p라는 비말단기호를 재귀적으로 사용하고있기 때문입니다.

일반적인 정규표현식에서는 이런 재귀적인 표현을 할 수 있는 기능을 제공하지 않습니다.

nearley.js

자바스크립트 파서 생성기로는 jison, peg.js, nearley.js 등이 있는데요, 각각 장단점이 있지만 이 중에서 nearley.js가 가장 사용하기 쉽기 때문에, 처음 파서를 작성하는 분들은 nearley.js를 사용하는 것을 추천드립니다.

위에 예시로 든 BNF들은 nearley.js의 문법을 사용해서 작성했으니, nearley.js에 입력으로 넣어서 테스트해볼 수 있습니다.

# nearley를 설치하면 몇가지 cli 프로그램들이 설치됩니다.
npm install -g nearley
# nearleyc는 nearley 문법(.ne) 파일을 받아서 자바스크립트 라이브러리(.js) 파일을 출력합니다.
nearleyc palindrome.ne -o palindrome.js
# nearley-test를 사용해서 생성된 라이브러리를 테스트 해볼 수 있습니다.
nearley-test palindrome.js -i "ababa"
# nearley-railroad는 nearley 문법 파일을 받아서 위에 예시로 사용된 기찻길 다이어그램을 그려줍니다.
nearley-railroad palindrome.ne -o palindrome.html

그리고 플레이그라운드가 있어서, 웹상에서 바로 파서를 작성해볼 수도 있습니다: https://omrelli.ug/nearley-playground/

구문트리 다듬기

플레이그라운드에서 다음과 같은 문법을 작성해봅시다.

expr -> num "+" num | num "*" num
num -> "4" | "2"

오른쪽 테스트 란에다가 4+2를 입력으로 넣어보면 아래처럼 생긴 구문트리가 나옵니다.

[["4"], "+", ["2"]]
플레이그라운드에서는 이렇게 보입니다.

nearley.js에서는 이러한 구문트리를 자바스크립트를 사용해서 원하는 값으로 변환할 수 있는 문법을 제공합니다.

각 유도규칙 뒤쪽에 구문트리 노드를 받아서 원하는 값으로 변환하는 자바스크립트 함수를 아래처럼 {% %}로 감싸서 넣어주면 됩니다.

expr ->
num "+" num {% op %}
| num "*" num {% op %}
num ->
"4" {% num %}
| "2" {% function (data) { parseInt(data[0]); } %}
# ^ 이렇게 아무 자바스크립트 코드나 집어넣을 수 있습니다.
# 임의의 자바스크립트 블럭을 작성할 수 있습니다.
# 여기서 작성된 코드들은 호이스팅되기 — 맨 위로 끌어올려지기 때문에
# 위에 적혀있는 속성문법에서 문제없이 참조할 수 있습니다.
@{%
const op = ([left, op, right]) => ({ left, op, right });
const num = ([value]) => parseInt(value);
%}
보기 좋게 변환된 것을 확인할 수 있습니다.

BNF가 아닌 추가적인 문법({% ... %})이 사용됐는데, 이런 문법을 속성 문법(Attribute Grammar)이라고 부릅니다.

nearley.js에서는 후처리기(Postprocessor)라는 이름으로 지원하고 있습니다.

JSON 파서

여기까지 왔으면 이제 JSON 파서를 작성하는 것은 매우 쉬운 일입니다.

JSON의 사양이 정리돼있는 ECMA-404 표준 문서나 json.org에 접속해보면, JSON 문법을 위에서 설명했던 기찻길 다이어그램으로 기술하고 있습니다.

심지어 JSON 홈페이지 오른쪽을 보면 BNF의 간략한 버전인 맥키먼 표기법으로 전체 문법이 기술돼있으니 이 코드를 그대로 nearley 문법으로 옮겨적으면 끝납니다.

우와 세상에

아래는 json.org에 적혀있는 문법을 nearley.js로 포팅한 파서입니다.

json -> element {% id %}value ->
object {% id %}
| array {% id %}
| string {% id %}
| number {% id %}
| "true" {% () => true %}
| "false" {% () => false %}
| "null" {% () => null %}
object ->
"{" ws "}" {% () => ({}) %}
| "{" members "}" {% ([, members]) => Object.fromEntries(members) %}
members ->
member {% ([member]) => [member] %}
| member "," members {% ([member, , members]) => [member, ...members] %}
member -> ws string ws ":" element {% ([, string, , , element]) => [string, element] %}array ->
"[" ws "]" {% () => [] %}
| "[" elements "]" {% ([, elements]) => elements %}
elements ->
element {% ([element]) => [element] %}
| element "," elements {% ([element, , elements]) => [element, ...elements] %}
element -> ws value ws {% ([, value]) => value %}string -> "\\"" characters "\\"" {% ([, characters]) => characters %}characters ->
null {% () => "" %}
| character characters {% ([character, characters]) => character + characters %}
character ->
[\\u0020-\\u0021\\u0023-\\u005c\\u005d-\\u10FFFF]
| "\\\\" escape
escape ->
"\\"" {% () => "\\"" %}
| "\\\\" {% () => "\\\\" %}
| "/" {% () => "\\/" %}
| "b" {% () => "\\b" %}
| "f" {% () => "\\f" %}
| "n" {% () => "\\n" %}
| "r" {% () => "\\r" %}
| "t" {% () => "\\t" %}
| "u" hex hex hex hex {%
([u, _0, _1, _2, _3]) => String.fromCharCode(parseInt(_0 + _1 + _2 + _3, 16))
%}
hex ->
digit {% id %}
| [a-fA-F] {% id %}
number -> integer fraction exponent {%
([integer, fraction, exponent]) => parseFloat(integer + fraction + exponent)
%}
integer ->
digit {% id %}
| onenine digits {% ([onenine, digits]) => onenine + digits %}
| "-" digit {% ([minus, digit]) => minus + digit %}
| "-" onenine digits {% ([minus, onenine, digits]) => minus + onenine + digits %}
digits ->
digit {% id %}
| digit digits {% ([digit, digits]) => digit + digits %}
digit ->
"0" {% id %}
| onenine {% id %}
onenine -> [1-9] {% id %}fraction ->
null {% () => "" %}
| "." digits {% ([dot, digits]) => dot + digits %}
exponent ->
null {% () => "" %}
| "E" sign digits {% ([E, sign, digits]) => E + sign + digits %}
| "e" sign digits {% ([e, sign, digits]) => e + sign + digits %}
sign ->
null {% () => "" %}
| "+" {% id %}
| "-" {% id %}
ws ->
null
| "\\u0020" ws
| "\\u000A" ws
| "\\u000D" ws
| "\\u0009" ws

마치며

이 글에서는 파싱이라는 개념을 쉽게 설명하기 위해 모호한 문법, 파싱 알고리즘, 오토마타, 어휘 분석 등의 설명을 생략했습니다. 좀 더 효율적으로 작동하는 파서를 작성하거나 파서 이용자에게 친절한 에러메세지를 보여주기 위해서는 이러한 개념들도 같이 알고있으면 좋습니다.

이 글이 좋은 반응을 얻으면 나중에 시간이 날 때 여기서 생략했던 개념들에 대해 다루는 글을 작성해보겠습니다. 감사합니다.

--

--

Riiid Teamblog
Riiid Teamblog KR

교육 현장에서 실제 학습 효과를 입증하고 그 영향력을 확대하고 있는 뤼이드의 AI 기술 연구, 엔지니어링, 이를 가장 효율적으로 비즈니스화 하는 AIOps 및 개발 문화 등에 대한 실질적인 이야기를 나눕니다.