JSON 파서 구현 1 - 스캐너
Lex나 Yacc와 같은 스캐너/파서 생성기를 사용하지 않고 JSON 파서를 구현하는 방법을 2부에 걸쳐 정리하려 한다. 시리즈를 끝까지 읽고 나면, JSON 파서를 만드는 게 생각보다 어렵지 않음을 알게 될 것이다.
1부에서는 스캐너를 설명할 것이다. 스캐너(scanner)는 입력 코드를 읽어 토큰(token)의 열(series)로 바꿔주는 프로그램이다. 렉서(lexer) 또는 어휘 분석기(lexical analyser)라 불리기도 한다. 토큰 열은 이후 파서의 입력이 된다.
렉심과 토큰
다음과 같은 간단한 JSON을 생각해보자.
{ "a": "hello", "b": 10 }
여기서 {는 JSON 객체의 시작을, "a"는 속성의 이름을, "hello"는 "a"의 값을 나타낸다. 그러나 "hello"에서 ello만 취한다면 이건 아무것도 의미하지 않는다. 이렇게 입력 코드에서 어떤 의미를 가지는 가장 작은 문자열 조각을 렉심(lexeme)이라 한다.
파서에서 문자열 비교를 통해 렉심 종류를 파악할 수도 있지만, 그렇게 하는 것은 속도도 느리고 우아하지도 않다. 렉심을 분리해낸 다음 바로 렉심의 종류도 함께 저장해두는 것이 낫다. 이걸 토큰(token)이라 한다. 토큰은 렉심의 종류, 소스 문자열(렉심), 그리고 경우에 따라 리터럴 값을 갖는다.
Token은 다음과 같이 정의할 수 있다. Java 14에서 도입된 레코드를 사용했다.
public record Token(
TokenType type,
String lexeme,
Object literal
) {}
토큰 타입은 다음과 같이 정의할 수 있다. {, }, [, ], :, ,가 JSON에서 쓰인다. 문자열 리터럴과 숫자 리터럴, 그리고 true, false, null 키워드도 있다.
public enum TokenType {
LEFT_BRACE, RIGHT_BRACE,
LEFT_BRACKET, RIGHT_BRACKET,
COLON, COMMA,
STRING, NUMBER,
TRUE, FALSE, NULL,
EOF,
}
스캐너 클래스
이제 스캐너 구현을 시작해보자.
public class Scanner {
private final String source;
private final List<Token> tokens;
public Scanner(String source) {
this.source = source;
this.tokens = new ArrayList<>();
}
}
입력 JSON 문자열을 읽어 토큰을 하나씩 생성해 tokens 리스트에 채울 것이다. 문자열을 읽어가며 토큰을 생성하는 루프는 다음과 같이 쓸 수 있다.
List<Token> scanTokens() {
while (!isAtEnd()) {
start = current;
scanToken();
}
tokens.add(new Token(EOF, "", null));
return tokens;
}
스캐너는 입력 문자열 끝까지 읽으며 토큰을 생성해 리스트에 넣는다. 마지막에 EOF 토큰을 넣는데, 꼭 필요한 건 아니지만 이렇게 하면 나중에 파서 코드를 좀더 깔끔하게 작성할 수 있다.
루프 안에서 스캐너가 문자열의 어느 부분을 스캔하고 있는지 나타내기 위해 start와 current 필드를 사용하고 있다. 따라서 tokens 밑에 두 필드를 추가한다.
private int start = 0;
private int current = 0;
...
start는 현재 스캔하고 있는 lexeme의 첫 문자를 가리키는 인덱스고, current는 현재 스캔하고 있는 문자의 인덱스다.
그리고 다음과 같이 입력 문자열을 끝까지 읽었는지 확인하는 함수가 필요하다.
private boolean isAtEnd() {
return current >= source.length();
}
렉심 인식
위 scanTokens()에서는 루프를 돌면서 토큰을 하나씩 스캔한다. 이 부분이 스캐너의 핵심이다. 제일 간단한 토큰부터 생각해보자. 문자 하나가 토큰이라면 한 글자씩 읽어 토큰으로 바꾸면 된다. JSON에서 문자 하나로 된 토큰은 다음과 같다.
private void scanToken() {
char c = advance();
switch (c) {
case '{' -> addToken(LEFT_BRACE);
case '}' -> addToken(RIGHT_BRACE);
case '[' -> addToken(LEFT_BRACKET);
case ']' -> addToken(RIGHT_BRACKET);
case ':' -> addToken(COLON);
case ',' -> addToken(COMMA);
case ' ', '\n', '\t', '\r' -> {} // ignore whitespace
}
}
여기서도 다음과 같은 도우미 함수가 사용되었다.
private char advance() {
return source.charAt(current++);
}
private void addToken(TokenType type) {
addToken(type, null);
}
private void addToken(TokenType type, Object literal) {
String text = source.substring(start, current);
tokens.add(new Token(type, text, literal));
}
advance()는 현재 문자를 리턴하고 current 인덱스를 하나 증가시킨다. addToken()은 스캔한 토큰을 tokens 리스트에 추가한다.
문자열 리터럴
문자열 리터럴을 처리하기 위해 scanToken()의 switch에 다음을 추가한다.
case '"' -> string();
문자열은 항상 "로 시작하므로, "을 만나면 문자열 시작으로 판단하고 string()을 호출한다.
private void string() {
while (peek() != '"' && !isAtEnd()) {
advance();
}
if (isAtEnd()) {
throw new RuntimeException("Unterminated string");
}
advance();
String value = source.substring(start + 1, current - 1);
addToken(STRING, value);
}
string()에서는 다음 "을 만날 때까지 읽기를 계속한다. 입력 코드의 끝까지 읽었는데 "를 만나지 못하면 예외를 던진다. string()에서는 peek() 도우미 함수를 사용한다. 토큰을 저장할 때 문자열 리터럴(따옴표 안의 문자열)도 함께 저장한다.
private char peek() {
if (isAtEnd()) return '\0';
return source.charAt(current);
}
peek()는 advance()와 비슷하지만 current 인덱스를 증가시키지 않는다.
숫자 리터럴
숫자 리터럴을 처리하기 위해 scanToken()의 switch에 다음을 추가한다.
case '-', '0', '1', '2', '3', '4',
'5', '6', '7', '8', '9' -> number();
0 ~ 9 또는 -를 만다면 숫자가 시작하는 것으로 판단하고 number() 도우미 함수를 호출한다.
private void number() {
if (peek() == '-') {
advance();
}
while (isDigit(peek())) {
advance();
}
if (peek() == '.' && isDigit(peekNext())) {
advance();
}
while (isDigit(peek())) {
advance();
}
addToken(NUMBER, Double.parseDouble(source.substring(start, current)));
}
처음 문자가 -면 다음 문자로 넘어간다. 문자가 숫자면 다른 문자가 나올 때까지 계속 읽는다. 마침표(.)가 나오고 그 다음 문자가 숫자면 마침표를 소숫점으로 인식하고 넘어간다. 그 다음 계속 숫자를 읽어나간다. 이후 숫자 이외의 문자를 만나면 숫자 렉심이 끝난다. 숫자 렉심을 잘라낸 다음 Double.parseDoule()로 double로 바꾼다. number()에서는 다음 도우미 함수를 사용한다.
private boolean isDigit(char c) {
return c >= '0' && c <= '9';
}
isDigit()는 0부터 9까지 문자를 숫자로 판단한다. .를 만났을 때는 그 다음 문자가 숫자인지 봐야 .가 소숫점으로 사용됐는지 확인할 수 있다. 따라서 다음 문자를 확인하는 도우미 함수를 추가한다.
private char peekNext() {
if (current + 1 >= source.length()) return '\0';
return source.charAt(current + 1);
}
JSON에서는 숫자를 과학적 표기법(scientific notation)으로 써도 되고, Java의 Double.parseDouble()도 과학적 표기법으로 작성된 숫자를 문제없이 한다. 따라서 number() 함수에 코드를 조금 더 추가하면 과학적 표기법으로 작성된 숫자도 지원할 수 있지만, 여기서는 생략한다.
true, false, null
마지막으로 scanToken()의 switch에 다음을 추가한다. 위에서 나열한 경우가 아니면 모두 default 브랜치로 넘어간다.
default -> {
if (isAlpha(c)) {
keyword();
} else {
throw new RuntimeException("Unexpected token.");
}
}
isAlpha() 도우미 함수의 구현은 다음과 같다.
private boolean isAlpha(char c) {
return (c >= 'A' && c <= 'Z') || (c >= 'a' && c<= 'z');
}
JSON에서 키워드라 할 만한 것은 true, false, null 뿐이다. 렉심이 셋 중 하나에 해당하면 그에 대응하는 토큰을 추가하고, 그렇지 않은 경우는 예외를 던진다.
private void keyword() {
while (isAlpha(peek())) {
advance();
}
String text = source.substring(start, current);
switch (text) {
case "true" -> addToken(TRUE, true);
case "false" -> addToken(FALSE, false);
case "null" -> addToken(NULL);
default -> throw new RuntimeException("Unexpected token: " + text);
};
}
다음 단계
이렇게 100줄 조금 넘는 코드로 JSON 스캐너를 만들었다. scanTokens()는 토큰 리스트 List<Token>을 리턴한다. 파서는 이 토큰 리스트를 이용해 JSON을 나타내는 데이터 구조를 생성할 것이다. JSON 파서에 대한 설명은 2부에서 이어진다.
참고
- Robert Nystrom, Crafting Interpreters Chapter 4
위에서 설명한 코드는 사실 이 책에 나오는 코드를 JSON에 맞게 약간 수정한 것에 불과하다. 놀랍게도 웹사이트에 책 전체 내용이 공개되어 있다. - JsonParser
위에서 설명한 코드 전체를 확인할 수 있다. - json_parser
위 설명의 Rust 구현을 확인할 수 있다.