Seongyu's Blog

Lexical의 Markdown 변환 과정에서 복잡한 Emphasis(기울임, 굵게) 문법을 올바르게 처리하기 위해 CommonMark Delimiter Algorithm을 도입한 과정을 공유합니다.

개요

Markdown에서 * 또는 _를 사용해 텍스트를 강조할 때, 중첩되거나 연속된 기호가 있는 경우 기존의 정규표현식 기반 방식으로는 CommonMark Spec을 완벽하게 따르기 어려웠습니다. 이를 해결하기 위해 구분자(Delimiter)를 스캔하고 처리하는 알고리즘을 구현했습니다.

문제 상황

기존 로직은 다음과 같은 케이스에서 Markdown을 올바르게 파싱하지 못했습니다.

입력: *foo**bar***
기대 결과: foobar
실제 동작: *foobar*

Markdown을 Text로 변환하는 과정에서 강조 *가 적용되지 않는 문제가 발생합니다.

원인 분석

디버깅 과정:

텍스트: *foo**bar***
* 패턴 매칭 시도 -> 실패
** 패턴 매칭 시도 -> **bar** 부분 매칭 성공
결과적으로 바깥쪽의 * 쌍을 인식하지 못하고 **만 처리

정규표현식에서 *을 탐색할 경우 매칭되는 쌍은 독립적으로 존재해야 하지만, 예제에서는 닫는 *는 독립적으로 존재하지 않아 매칭되지 않았습니다.

단순한 정규표현식으로는 CommonMark에 명시되어 있는 Left-Flanking, Right-Flanking, 그리고 3의 배수 규칙 등의 복잡한 강조 규칙을 모두 처리하기에는 한계가 있었습니다.

해결 방법: CommonMark Delimiter Algorithm 도입

문제를 근본적으로 해결하기 위해 CommonMark Delimiter Algorithm을 도입했습니다.

CommonMark 핵심 개념

Left-Flanking
- 구분자가 강조를 열 수 있는지 판단하는 기준입니다.
- 뒤에 공백이 없어야 하며, 뒤에 문장 부호가 있다면 앞에도 문장 부호나 공백이 있어야 합니다.
Right-Flanking
- 구분자가 강조를 닫을 수 있는지 판단하는 기준입니다.
- 앞에 공백이 없어야 하며, 앞에 문장 부호가 있다면 뒤에도 문장 부호나 공백이 있어야 합니다.
Rule of 3
- 여는 구분자와 닫는 구분자가 서로 다른 길이를 가질 때 모호함을 해결하는 규칙입니다.
- 두 구분자의 길이 합이 3의 배수이면 강조 처리하지 않습니다. (단, 둘 다 3의 배수인 경우는 예외)
- 예시: foo*bar**baz에서 *와 **는 합이 3이므로 매칭되지 않습니다.

이러한 개념을 바탕으로 알고리즘은 크게 두 단계로 나뉩니다.

1. Delimiter Run 스캔

먼저 텍스트를 순회하며 구분자(Delimiter)들의 연속된 구간(Run)을 찾고, 해당 구분자가 열리는 역할을 할 수 있는지, 닫히는 역할을 할 수 있는지 판별합니다.

이때 Left-Flanking과 Right-Flanking 조건을 검사합니다.

function scanDelimiters(
  text: string,
  transformersIndex: TextFormatTransformersIndex,
  excludeRanges: Array<{ start: number; end: number }> = [],
): Delimiter[] {
  // ... (중략) ...
  while (i < text.length) {
    // ... 구분자 탐색 ...
    const canOpen = canEmphasis(char, text, i, len, true); // Left-Flanking 검사
    const canClose = canEmphasis(char, text, i, len, false); // Right-Flanking 검사

    if (canOpen || canClose) {
      delimiters.push({
        active: true, // 짝이 맞춰지면 false로 변함
        canClose,
        canOpen,
        char,
        index: i,
        length: len, // Delimiter Run의 길이
        originalLength: len, // 3의 배수 규칙 검사를 위한 초기 길이
      });
    }
    i += len;
  }
  return delimiters;
}

2. Emphasis 처리

스캔된 구분자 목록을 순회하며 짝을 맞추고 가장 바깥에 존재하는 구분자를 반환합니다. 이때 "3의 배수 규칙" 등을 적용하여 올바른 중첩 관계를 검증합니다.

function processEmphasis(
  text: string,
  delimiters: Delimiter[],
  transformersIndex: TextFormatTransformersIndex,
): {
  startIndex: number;
  endIndex: number;
  tag: string;
  content: string;
} | null {
  // ... (중략) ...
  while (currentPos < delimiters.length) {
    const closer = delimiters[currentPos];
    // ... 닫는 구분자 찾기 ...

    // 스택을 거슬러 올라가며 짝이 맞는 여는 구분자(opener) 찾기
    for (let openIdx = currentPos - 1; openIdx > bottom; openIdx--) {
      // ... 조건 검사 ...

      // Rule of 3 (3의 배수 규칙) 검사
      if (opener.canClose || closer.canOpen) {
        const sum = opener.originalLength + closer.originalLength;
        if (
          sum % 3 === 0 &&
          opener.originalLength % 3 !== 0 &&
          closer.originalLength % 3 !== 0
        ) {
          continue;
        }
      }

      // 매칭 성공 시 기존 결과와 Outermost인지 비교
      // ...
    }
  }
  return result;
}

이 알고리즘을 통해 *foo**bar***와 같은 문제를 해결했을 뿐만이 아닌, *a `*` b `x`* 같은 복잡한 경우들도 정확하게 스펙대로 처리할 수 있게 되었습니다.

Playground

느낀점

기존에 포맷을 처리할 때는 정규표현식을 활용하여 변환했지만, 올바른 변환을 위해 파싱 알고리즘 자체를 교체하는 큰 작업을 했습니다. Markdown 스펙 문서를 정독하며 "Delimiter Run", "Flanking" 같은 개념을 이해하고 코드를 작성하는데 어려움이 있었습니다.

기존 코드를 들어내고 새로운 알고리즘을 적용하는 것이라 반대가 걱정되었지만, 리뷰어분들께서 "긍정적인 변화"라며 코드를 꼼꼼히 봐주셔서 무사히 머지될 수 있었습니다. 기존 로직에 큰 변화를 주었고 스펙을 준수하는 올바른 코드를 작성했다는 점에서 큰 성취감을 느꼈습니다.

CommonMark Delimiter Algorithm 도입으로 올바른 Emphasis 변환