일상/개발

Markdown 구문해석기 구현 회고록

은율실험실 2024. 6. 25. 00:00
반응형

우리 팀은 코드잇 스프린트 FE 6기 파트 3에서 민주적으로 익명투표를 통해 프로젝트를 선정하였고, 그 결과 Wikid가 선택되었다. Wikid 시안의 요구사항은 인물에 대한 정보의 등록, 수정, 삭제 등으로, 이름에서 유추할 수 있듯 위키를 구현하는 것이다. 그리고 일부 페이지에는 markdown을 적용하는 요소들이 있었다. 개인적으로 해당 프로젝트를 강하게 다른 팀원에게 권유한 이유는 (결국 민주적으로 익명 투표를 통해 주제를 선정했지만), 프로젝트를 완성하고 나서 팀원들끼리 서로서로 정보를 기입하고 싶은 바렘도 컸지만, 무엇보다 작년에 markdown 구문해석기를 구현하려고 노력했었지만 여러 한계에 부딪힌 경험이 있기에, 이번 기회를 순풍삼아 다시금 도전하고 싶었던 개인적인 소망이 나의 가장 큰 동기였다.

 
우선, 구문해석이란 무엇일까? 구문해석의 사전적 정의는 다음과 같다.

언어학에서 구문 분석 또는 '파싱'은 문장을 그것을 이루고 있는 구성 성분으로 분해하고 그들 사이의 위계 관계를 분석하여 문장의 구조를 결정하는 것을 말한다. 컴퓨터 과학에서 파싱은 일련의 문자열을 의미 있는 토큰으로 분해하고 이들로 이루어진 파스 트리를 만드는 과정을 말한다.

출처: 위키피디아

 
추가적으로, 컴파일러 이론에서 언어의 처리 과정은 크게 다음과 같다.

Tokenizer/Scanner (Tokenizing, 토큰화) → Parser (Parsing, 해석) → Interpreter (Execution, 실행)

 
이 밖에도 lexing, compiling 등의 처리 단계 및 각각의 처리기가 존재하지만, 이번에 만들 구문해석기는 실행을 브라우저에 내장된 JS 엔진에 일임할 것이기 때문에 interpreter, compiler을(를) 생략 가능하다.

 
때문에 가장 처음 할 일은 토큰의 기준을 나누는 것이었다. 이때 일부 구문해석기는 토큰(token)을 처리하는 parser의 복잡도를 줄이기 위해 scanner 단계에서부터 다음과 같이 각 토큰에 정보를 저장하기도 한다.

// Token[]
[
	Token.NUMBER // extends Token
	{
		data: 123
	},
]

 
그러나 나는 위 같은 설계는 토큰화 단계에서 정보 추출의 난해함과 더불어 토큰과 AST(Abstract Syntax Tree)와의 경계가 매우 희박하다고 판단하여 다음과 같이 각 토큰에 정보를 저장하지 않는 방식을 채택했다.

// Token[]
[
	Token.DIGIT_1,
	Token.DIGIT_2,
	Token.DIGIT_3,
]

 
단, 이러한 설계는 하나의 토큰이 여러 문법을 가질 수 있다면, 역직렬화를 통해 원본을 복원하는 작업이 불가능하다.

public static readonly INDENT = new (class INDENT extends Token
{
	override toString()
	{
		return /* ??? */;
	}
})
("	", "  ", "    "); // 1 tab, 2 spaces, 4 spaces

 
이를 해결하기 위해서는 단일 토큰은 반드시 하나의 문법만을 허용해야 한다.

public static readonly INDENT_1T = new (class INDENT_1T extends Token
{
	override toString()
	{
		return this.grammar;
	}
})
("	"); // 1 tab

public static readonly INDENT_2S = new (class INDENT_2S extends Token
{
	override toString()
	{
		return this.grammar;
	}
})
("  "); // 2 spaces

public static readonly INDENT_4S = new (class INDENT_4S extends Token
{
	override toString()
	{
		return this.grammar;
	}
})
("    "); // 4 spaces

 
프로그래밍 언어는 일반적으로 문맥 자유 문법(contex-free grammar)으로, 요약하자면 문맥에 비종속적인 문법이다. 그러나 우리에게 친숙한 Markdown 은 이와 대조되는 문맥 의존 문법(context-sensitive grammar)이다. 시작할 당시에는, 이전에 간단한 HTML 구문해석기를 제작한 적이 있기에, 해당 경험을 살려 주어진 입력에 문법적 오류가 없는 이상적인 환경에 한해 시간 복잡도 O(n)의 처리기를 제작하려고 했으나 이후 금세 문제에 맞닥트렸다.

 
기존에 작업하던 방식은 재귀(recursive) 함수 또는 그에 준하는 선형(linear) 함수를 사용하여, 매 순환(iteration)마다 유한 상태 기계(finite state machine)에서 현 상태/문맥에 올 수 있는 문법이 있는지 여부를 연관 배열(associative array)을 연상케 하는 사전에 정의된 switch문으로 확인 및 분기하는 구조였다.

//
// <TIME COMPLEXITY> O(n)
//
// n = length of input

switch (char)
	case "0": case "1": ... case "9":
	{
		handle_number();
		break;
	}
	default:
	{
		// do something
		break;
	}
}

 
그러나 사실 위 방식은 hard-coding 요소가 많기 때문에 문법이 복잡해질수록 더욱 관리하기가 힘들었다. 더불어 재귀함수를 통한 처리는 오버헤드(overhead)로 인한 성능저하 및 문제의 원인 파악(debugging)을 어렵게 만들었다. 그럼에도 당시에는 해당 설계가 확장성 및 유지보수성이 떨어지더라도 그만한 성능적 이점이 있다고 생각했었다. 그리고 무엇보다 문법이 방대해질수록 look-up이 아닌 look-ahead의 일종인 정규식(regular expression) 패턴 매칭은 비효율적이었다.

//
// <TIME COMPLEXITY> O(n * t * r)
//
// n = length of input, t = number of tokens, r = average length of regex per token

buffer.push(char); // consume

const chunk = buffer.join("");

look_ahead:
for (const token of Token.of(Level.BLOCK))
{
	for (const regex of token.grammar)
	{
		if (regex.test(chunk))
		{
			// build
			tokens.push(token);
			break look_ahead;
		}
	}
	// do something
}

 
그러나 markdown은 분류하자면 문맥 의존 문법에 속하고 HTML과 다르게 문법의 시작과 종결이 생략되어도 되는 특수성과 구현해야하는 다양한 문법들로 인해 작업의 진척이 진행될수록 FSM의 복잡도가 기존의 switch 문과 엮여 지나치게 비대해졌으며, 결국 look-up을 통한 성능 개선으로 얻을 수 있는 이득보다 정규식을 사용하여 얻을 수 있는 확장성 및 유지보수성이 더 많다고 생각되는 지경까지 이르게 되었었다. 결정을 내린 그 즉시 정규식을 사용한 scanner를 제작하였고, 이후 parser의 작업에 들어갔지만, parser를 작업하는 매 순간을 포함해 며칠간 다른 방법을 사용하면 시간 복잡도를 줄일 수 있지 않을까 고민에 고민을 거듭하던 도중, LL(1) parser 관련 문서를 둘러보다 parsing table에서 영감을 받아 노드(node)를 사용해 확장성 및 유지보수성, 그리고 마침내 시간 복잡도 O(n)을 고려한 scanner를 제작할 수 있었다. 생각해 보면 간단한 문제였다. 기존의 hard-coding으로 작성된 switch문의 분기를 동적으로 생성해 주는 것일 뿐이기 때문이다.

//
// <TIME COMPLEXITY> O(n)
//
// n = length of input

buffer.write(char); // consume

if (char in node)
{
	if (node instanceof Token)
	{
		// build
		tokens.push(node);
		// flush
		tokens.push(buffer.flush());
		// and more...
	}
	else
	{
		// delve branch
		node = node[char];
	}
}
else
{
	// do something
}

 
다만 노드 기반의 scanner 또한 처음에는 완벽한 것은 아니었다. 매우 다양한 문제를 겪었지만, 가장 주목할만한 문제는 교차되는 문법의 처리였다. 내가 작성한 구문해석기는 문법이 주어지면 다음과 같은 trie를 생성하는 전처리 과정을 거친다.

{
	[Context.BLOCK]: // 문맥
	{
		"#":
		{
			" ": H1,
			"#":
			{
				" ": H2,
				"#":
				{
					" ": H3,
					"#":
					{
						" ": H4,
						"#":
						{
							" ": H5,
							"#":
							{
								" ": H6,
							},
						},
					},
				},
			},
		},
	},
	// and more...
}

 
이때 H1...H6 처럼 문법의 분기가 명확하지 않고 다음과 같이 겹치는 경우에는 분기의 모호성 문제가 발생한다.

// <=
{
	"<":
	{
		"=": <token> // less than or equal to, ≤
	}
}

// <==
{
	"<":
	{
		"=":
		{
			"=": <token> // fat arrow left, ⇐
		}
	}
}

// <merged>
{
	"<":
	{
		"=": // ???
	}
}

 
나는 이러한 경우에도 look-ahead를 사용하지 않기 위해 다음과 같이 노드의 병합을 처리했다.

// <merged>
{
	"<":
	{
		"=":
		{
			"=": <token> // fat arrow left, ⇐
			default: <token> // less than or equal to, ≤
		}
	}
}

 
비록 대단한 업적은 아니지만, 그럼에도 내게는 하나의 큰 성취라 오늘을 기억하고자 이렇게 글을 남긴다.
 

 

GitHub - Sombian/markdown

Contribute to Sombian/markdown development by creating an account on GitHub.

github.com

반응형