JSON 파서 구현 2 - 파서
1부에서 JSON 스캐너를 구현했다. JSON 스캐너는 JSON을 읽어 토큰 리스트를 생성한다. 이제 토큰 리스트를 읽어 데이터 구조로 바꿔줄 파서를 구현할 차례다.
JSON의 문법을 BNF(Backus-Naur Form)으로 다음과 같이 나타낼 수 있다.
json ::= object
| array
| string
| number
| "true"
| "false"
| "null"
object ::= "{" "}"
| "{" member ("," member)* "}"
array ::= "[" "]"
| "[" json ("," json)* "]"
member ::= string ":" json
스캐너에서 문자열이나 숫자 등 토큰을 이미 분리했으므로 여기서 string이나 number에 대한 문법을 상세히 기술하지 않았다. 그 외에도 구현 복잡도를 줄이기 위해 문법을 단순화했다. JSON의 전체 문법은 Json.org에서 확인할 수 있다.
Json 클래스
파서는 스캐너로 생성한 토큰 리스트를 JSON 구조를 나타내는 자료구조로 변환할 것이다. 따라서 JSON을 어떻게 나타내는 게 좋을지 생각해봐야 한다. 여기서는 위 문법 구조를 나타내는 Json 클래스를 다음과 같이 정의한다.
public abstract class Json {
static class Obj extends Json {
List<Member> members = new ArrayList<>();
}
static class Arr extends Json {
List<Json> elements = new ArrayList<>();
}
static class Member {
String key;
Json val;
Member(String key, Json val) {
this.key = key;
this.val = val;
}
}
static class Literal extends Json {
Object val;
Literal(Object val) {
this.val = val;
}
}
}
Json.Obj는 JSON 객체를 나타낼 클래스로 List<Member> 타입의 필드를 가지고 있다. Map<String, Json> 타입을 쓸 수도 있지만, 위에서 보인 JSON 문법 구조와 비슷하게 하기 위해 List<Member>를 썼다.
재귀 하향 파서
재귀 하향 파서(recursive descent parser)는 상호 순환 절차의 집합으로 이루어진 하향식(top-down) 파서다. 재귀 하향은 Yacc, Bison 또는 ANTLR 같은 파서 생성기 도움 없이 파서를 만드는 가장 단순한 방법이다. 재귀 하향 파서는 최상위 문법 규칙(여기서는 json)부터 시작해 문법 트리의 종말(여기서는 string, number, true, false, null)까지 처리해가기 때문에 하향식이라 불린다. 또한 문법 규칙이 직간접적으로 자신을 참조하기 때문에 재귀적이라 할 수 있다. 각 문법 규칙은 하나의 함수(또는 메서드)가 될 것이다.
파서 클래스
이제 파서 클래스 구현을 시작해보자.
public class Parser {
private final List<Token> tokens;
private int current = 0;
Parser(List<Token> tokens) {
this.tokens = tokens;
}
}
파서는 토큰 리스트를 입력으로 받아, 토큰을 하나씩 읽어가며 JSON 구조를 생성할 것이다. current는 파싱을 위해 읽어들일 토큰 리스트의 인덱스다.
그리고 다음과 같이 현재 토큰이 인자로 주어진 토큰 타입에 매치되는지 확인하는 도우미 메서드를 추가한다.
private boolean match(TokenType... types) {
for (TokenType type : types) {
if (check(type)) {
advance();
return true;
}
}
return false;
}
match() 메서드는 인자로 주어진 토큰 타입 중 하나라도 현재 토큰 타입과 같으면 advance()를 호출한 후 true를 리턴한다.
check() 메서드는 주어진 인자 타입이 현재 토큰 타입과 같으면 true를 리턴한다. match()와 달리 current 인덱스를 증가시키지 않는다.
private boolean check(TokenType type) {
if (isAtEnd()) return false;
return peek().type() == type;
}
advance() 현재 토큰을 리턴하면서 current 인덱스를 하나 증가시킨다. 스캐너에 있던 advance() 메서드와 비슷하다.
private Token advance() {
if (!isAtEnd()) current++;
return previous();
}
그리고 다음 도우미 메서드도 추가한다.
private boolean isAtEnd() {
return peek().type() == EOF;
}
private Token peek() {
return tokens.get(current);
}
private Token previous() {
return tokens.get(current - 1);
}
isAtEnd()는 처리할 토큰이 남아있지 않은지 확인한다. peek()는 현재 토큰을, previous()는 바로 전 토큰을 리턴한다.
그리고 다음과 같이 consume() 메서드를 정의한다. consume()은 현재 토큰이 인자로 주어진 토큰 타입과 같은 경우 토큰을 소모한다. }나 ]를 처리할 때 사용할 것이다.
private Token consume(TokenType type, String message) {
if (check(type)) return advance();
throw new RuntimeException(message);
}
그리고 다음과 같이 parse() 메서드를 추가한다.
Json parse() {
return json();
}
JSON 객체 파싱
지금부터 문법 규칙을 하나씩 코드로 바꿔갈 것이다. 첫 규칙은 json이다.
json ::= object
| array
| string
| number
| "true"
| "false"
| "null"
이걸 코드로 옮기면 다음과 같다.
Json json() {
if (match(LEFT_BRACE)) return obj();
if (match(LEFT_BRACKET)) return arr();
if (match(STRING, NUMBER, TRUE, FALSE, NULL)) return literal();
throw new RuntimeException("Invalid Json");
}
첫 토큰이 LEFT_BRACE({)면 객체 시작으로 판단하고, LEFT_BRACKET([)이면 배열 시작으로 판단하며, STRING, NUMBER, TRUE, FALSE, NULL인 경우는 모두 리터럴로 판단한다.
다음 문법 규칙은 JSON 객체다.
object ::= "{" "}"
| "{" member ("," member)* "}"
코드로 옮기면 다음과 같다. 문법에 나오는 *는 코드에서 루프로 바뀐다.
Json obj() {
Json.Obj obj = new Json.Obj();
if (check(RIGHT_BRACE)) { // empty object
advance();
return obj;
}
Json.Member member = member();
if (member != null) {
obj.members.add(member);
}
while (match(COMMA)) {
member = member();
obj.members.add(member);
}
consume(RIGHT_BRACE, "Invalid token: expected '}'");
return obj;
}
현재 토큰이 RIGHT_BRACE면 빈 객체가 된다. 빈 객체가 아니면 member가 한 번 이상 나올 수 있고 member간에는 COMMA가 있다. 마지막 member를 처리하고 나면 RIGHT_BRACE가 나와야 한다.
member 규칙은 다음과 같다.
member ::= string ":" json
코드로 옮기면 다음과 같다.
Json.Member member() {
String key = (String) string().val;
if (!match(COLON)) throw new RuntimeException("Invalid token: expected `:` ");
Json val = json();
return new Json.Member(key, val);
}
string()은 현재 토큰이 문자열인 경우 문자열 리터럴을 리턴하고, 문자열이 아닌 경우는 예외를 던진다.
private Json.Literal string() {
if (match(STRING)) return new Json.Literal(previous().literal());
throw new RuntimeException("Invalid token: expected string");
}
배열 파싱
배열의 문법 규칙은 다음과 같다.
array ::= "[" "]"
| "[" json ("," json)* "]"
obj 규칙과 비슷하지만 {, } 사이에 member가 있는 대신 [, ] 사이에 json이 있다. 따라서 코드도 obj() 메서드와 비슷하다.
Json arr() {
Json.Arr arr = new Json.Arr();
if (check(RIGHT_BRACKET)) { // empty array
advance();
return arr;
}
arr.elements.add(json());
while (match(COMMA)) {
arr.elements.add(json());
}
consume(RIGHT_BRACKET, "Invalue token: expected ']'");
return arr;
}
리터럴 파싱
객체나 배열이 아닌 경우는 모두 리터럴로 처리한다.
private Json.Literal literal() {
return new Json.Literal(previous().literal());
}
match() 메서드가 current 인덱스를 증가시키므로 리터럴 값을 얻으려면 previous().literal()을 호출해야 한다.
그런데 문자열도 리터럴인데 왜 위에서 string()을 따로 정의했는지 의아할 수 있다. string()은 member를 파싱할 때 사용했는데 member의 키는 반드시 문자열이어야 하기 때문이다.
파서 연결하기
1부에서 구현한 스캐너와 여기서 구현한 파서는 다음과 같이 사용할 수 있다.
public class Test {
public static void main(String[] args) {
String input = """
{
"a": 10,
"b": true,
"c": "hello",
"d": null,
"e": [1,2,3,4,5],
"f": {
"f1": "hello",
"f2": "world",
"arr": [{"a":10}, {"b":20}]
},
"g": [-10, 20.0, 0.003, -0.04],
"h": {},
"i": []
}
""";
Scanner scanner = new Scanner(input);
List<Token> tokens = scanner.scanTokens();
Parser parser = new Parser(tokens);
Json json = parser.parse();
...
}
}
다음 단계
지금까지 JSON 스캐너와 파서를 간단히 구현해 보았다. 스캐너와 파서 모두 100줄 조금 넘는 간단한 프로그램이고, 스캐너/파서 생성기의 도움을 받지 않고 구현했다. JSON을 어떻게 파싱할 수 있을지 확인하는 정도로는 충분하지만 몇 가지 개선점이 눈에 보인다.
- 스캐너도 그렇고 파서도 그렇고 에러를 만나면 예외를 던진다. 입력 JSON에 오류가 많은 경우 모든 오류를 한꺼번에 보여주지 않고 처음 만나는 에러 하나만 보여주며 에러 위치도 알려주지 않기 때문에, 모든 오류를 찾는 게 지루한 작업이 될 수 있다. 에러를 만났을 때 예외를 던지는 대신 에러 위치와 내용을 기록해두었다가 입력 JSON을 끝까지 처리한 다음 모든 에러를 위치와 함께 보여준다면 더욱 사용하기 편리한 JSON 파서가 될 것이다.
parse()는Json타입을 리턴하는데, 이것만 가지고는 파싱한 결과를 제대로 사용하기 어렵다. 이것은 JSON이 어떤 타입인지 알 수 없기 때문에 일부러 이렇게 한 것이지만, 클라이언트 쪽에서 쉽게 사용할 수 있도록 개선할 필요가 있다.
참고
- Robert Nystrom, Crafting Interpreters, Chapter 6
1부에서와 마찬가지로 위에서 설명한 코드 역시 이 책에 나오는 코드를 JSON에 맞게 변형한 것이다. - JsonParser
위에서 설명한 코드 전체를 확인할 수 있다. - json_parser
위 설명의 Rust 구현을 확인할 수 있다.