파서 콤비네이터

Parser Combinators

t3.at ▲ 221 댓글 78 schindlabua

요약

파서 콤비네이터는 정규식보다 읽기 쉽고 tree-sitter보다 가벼운 파싱 방법입니다.

빈에서 일하는 개발자 플로가 애니메이션을 곁들여 장별로 풀어 쓴 해설입니다. 정규식은 복잡한 작업에서 금세 지저분해지고 tree-sitter(코드 편집기의 문법 강조에 쓰이는 무거운 파싱 라이브러리)는 과할 때가 많다며, 그 사이를 채울 도구로 파서 콤비네이터를 소개했습니다.

왜 중요한가

  • 정규식 하나로는 버겁고 정식 파서를 들이기는 부담스러운 중간 크기 작업에 쓸 방법을 보여 줍니다.
  • 파서가 평범한 함수라서 작은 조각을 따로 만들고 시험한 뒤 다시 조합해 쓸 수 있습니다.
  • 라이브러리 없이 TypeScript로 처음부터 만들어 보여 줘서 원리를 그대로 따라갈 수 있습니다.

핵심 내용

  • 파서를 문자열을 받아 읽어 낸 값과 남은 문자열을 돌려주는 함수로 정의합니다.
  • 차례로 실행하는 pSeq, 결과 모양을 바꾸는 pMap, 실패할 때까지 되풀이하는 pRepeat이 기본 도구입니다.
  • 클라우드플레어 1.1.1.1에 보낸 ping 출력을 헤더, 응답 패킷, 통계로 나눠 타입이 있는 객체로 바꾸는 예제를 끝까지 만듭니다.
  • pSeq를 겹쳐 쓰면 같은 일을 하는 정규식은 읽을 수 없게 되지만, 콤비네이터 코드는 읽기 쉽게 남는다고 했습니다.
  • 파싱은 여럿을 하나로 접는 reduce(폴드)와 반대로, 하나를 여럿으로 쪼개는 언폴드라고 설명했습니다.

HN 반응

  • 애니메이션이 이해를 돕는다는 칭찬과 함께, 장을 넘기는 화면이라 되돌아보거나 검색하기 어렵다는 불만이 이어졌습니다.
  • 결과를 튜플로 묶었다 푸는 코드가 늘어난다는 지적에는, 하스켈이나 OCaml에서는 전용 문법 덕분에 그런 번거로움이 적다는 반론이 나왔습니다.

댓글

30개 표시 · 전체 78개
  1. BoppreH HN

    파이썬을 쓰는데 문제가 정규식 하나로 처리하기엔 크고, 기사에 나온 것 같은 본격적인 파서를 쓰기엔 작다면 내장 re.Scanner0를 추천합니다. re 모듈에 들어 있는 정규식 기반 토크나이저1인데(그래서 재귀 파싱은 안 됩니다), 무슨 이유에선지 공식 문서에는 전혀 나오지 않습니다.

    토큰 종류마다 패턴을 주고 매치를 처리할 함수를 주면, 처리된 토큰의 리스트를 돌려줍니다.

    중요한 점은 리스트를 한 번에 처리하면서 매치가 끊기지 않고 이어지는지 확인해 준다는 겁니다. 캡처 그룹을 쓴 단순한 re.findall은 매치되지 않은 문자를 그냥 무시합니다. 실행 중인 스캐너에 대한 참조도 받을 수 있어서, 오류를 보고할 때 쓸 매치 위치를 기록할 수도 있습니다.

        import re

# Initialize the scanner.
    scanner = re.Scanner([
      (r"\d+",   lambda scanner, token: ('COUNT', int(token))),
      (r"\w+",   lambda scanner, token: ('ANIMAL', token.removesuffix('s'))),
      (r"[,. ]",     None), # None -> skip token.
    ])

# Scan a sample string.
    results, remainder = scanner.scan("45 pigeons, 23 cows, 11 spiders.")

# Ensure we parsed the whole thing.
    assert not remainder

print(results)
    # [('COUNT', 45),
    #  ('ANIMAL', 'pigeon'),
    #  ('COUNT', 23),
    #  ('ANIMAL', 'cow'),
    #  ('COUNT', 11),
    #  ('ANIMAL', 'spider')]
  2. analog_daddy HN

    와! 좋은 꿀팁이네요.

    “re”보다는 크고 “parsimonious”보다는 작은, 애매한 영역에 딱 맞는 도구네요.

    보통 이런 주제들은 서로 겹치지 않게
    따로 언급되더라고요. (적어도 제가 지난번에 사람이 읽기 쉬운 정규식을 만들고 싶어서 파고들었던 좁은 토끼굴에서는 그랬어요.)

    https://github.com/mikaelho/python-human-regex

    https://github.com/vinta/awesome-python#text-processing

  3. odyssey7 HN

    공식 문서에는 전혀 나오지 않는다

    가독성과 의사소통에 문제가 있다니, 참 파이썬답네요.

  4. sovrin HN

    파서 컴비네이터라는 개념을 꽤 잘 설명한 글입니다.

    저는 개인적으로 모나드와 데이터 처리라는 개념이 무척 흥미롭습니다. 몇 년 전 어디선가 “모나딕 파서 컴비네이터”에 관한 논문을 읽었는데, 호기심이 생겨서 이 아이디어로 많이 실험해 봤습니다. 반환값에 대한 제 첫 생각도 이 글과 똑같았습니다.

    추출한 값과 나머지를 함께 반환하는 것이 “논리”상으로는 말이 되지만, 성능 면에서는 그렇지 않습니다. 문자열 슬라이싱이 인덱스만 가지고 작업하는 것보다 훨씬 느린 것 같습니다. 적어도 nodejs에서는 그렇습니다.

    다만 인덱스 방식으로 하면 순수성을 유지하기 위해 함수 시그니처가 조금 달라져야 해서, 아쉽게도 그만큼 쓰기에 덜 우아해집니다.

    이 타입스크립트 라이브러리는 이것저것 짜깁기해서 만들었고, 나중에는 Claude의 도움도 받았습니다(뻔뻔한 자기 홍보입니다: https://github.com/sovrin/unitas ). 타입이 어느 정도는 붙어 있고(재귀는 되는 경우도 있고 안 되는 경우도 있습니다) 필요할 만한 함수는 다 들어 있을 겁니다.

  5. ArneCode HN

    애니메이션이 정말 마음에 듭니다. 무슨 일이 일어나는지 직관적으로 이해하게 해 주네요!

    제 생각에 파서 컴비네이터의 단점 하나는, 예를 들어 (별도의 문법 파일로 파서를 생성하는) 파서 제너레이터 라이브러리와 비교하면 매핑/언래핑 코드를 많이 추가해야 한다는 점입니다. 제 생각에는 이 때문에 파서를 읽기가 더 어려워집니다.

    이를 개선해 보려고 러스트로 파서 컴비네이터 라이브러리를 만들고 있습니다. 컴비네이터를 두 개(capture와 bind) 더 추가해서, 파서의 결과를 버킷에 저장하고(bind) 나중에 그 버킷에 저장된 값으로 결과를 만들 수(capture) 있게 했습니다. 그러면 언래핑/매핑 코드를 없애고 문법과 결과 생성을 분리할 수 있습니다.

    시간 되시면 피드백을 주시면 정말 감사하겠습니다!

    여기서 보실 수 있습니다: https://github.com/ArneCode/marser

  6. pxc HN

    제가 처음 접한 파서 컴비네이터는 파서 제너레이터 라이브러리 안에 있었습니다: https://github.com/engelberg/instaparse

    (OP가 쓴 방식이 파서 컴비네이터를 처음 도입한 원조 방식이라는 걸 방금 알았으니, 아마 이상하게 들리겠습니다만) 파서가 이렇게 그냥 함수인 파서 컴비네이터는 이번에 처음 봤습니다. 파서를 조합하고 싶은데 매핑/언래핑 코드를 잔뜩 쓰기는 싫다면, 파서 제너레이터가 만들어 준 파서 위에 컴비네이터를 쓰면 되지 않나요?

  7. pdpi HN

    이게 무슨 의미가 있는지 잘 모르겠어요. roll 예제를 Winnow로 쓰면 (언)래핑 로직이 그렇게 많지도 않거든요:

        use winnow::{Result, ascii::digit1, combinator::separated_pair, prelude::*};

#[derive(Debug, PartialEq)]
    struct Roll {
        count: u32,
        sides: u32,
    }

fn number(input: &mut &str) -> Result<u32> {
        digit1.try_map(str::parse).parse_next(input)
    }

fn roll(input: &mut &str) -> Result<Roll> {
        let (count, sides) = separated_pair(number, 'd', number).parse_next(input)?;
        Ok(Roll { count, sides })
    }

#[cfg(test)]
    mod test {
        use super::*;

#[test]
        fn test_roll() {
            let input = &mut "3d6";
            assert_eq!(roll(input), Ok(Roll { count: 3, sides: 6 }));
        }
    }
  8. ArneCode HN

    이 경우에는 그렇습니다. 하지만 그건 roll 문법이 상대적으로 단순해서, 서로 다른 컴비네이터가 중첩되는 일 등이 없기 때문이라고 생각합니다. (이해하기 쉬워서 README에 쓴 예제입니다.) winnow 코드도 “d” 값을 무시하려고 separated_pair를 쓰는데, 이 역시 count와 sides 결과만 남기는 로직을 얹는 셈입니다.

    비교용으로 써 온 문법 하나는 함수 시그니처입니다. nom, chumsky와 비교해 봤습니다: https://blog.arnedebo.com/posts/a-grammar-first-approach-to-parser-combinators/#parsing-function-signatures

    이 라이브러리들은 “언래핑” 코드를 separated_by나 .ignore_then 같은 컴비네이터로 대체하는 방법을 찾아냈지만, 그래도 결과 처리 코드가 많이 남아서 제 생각에는 코드를 읽고 이해하기가 더 어려워집니다. 제가 개선하려는 것이 바로 이 부분입니다.

    물론 아주 주관적인 문제라서, 다른 라이브러리들의 방식을 더 선호하는 분도 있을 겁니다.

  9. mrkeen HN

    파서 컴비네이터를 쓰면 대체 어떤 매핑/언래핑을 감수해야 하나요?

  10. ArneCode HN

    이 사이트의 pSeq처럼 파서 두 개를 조합할 때는 각 파서의 반환값을 어떻게 할지 생각해야 합니다. 한 가지 방법은 모든 반환값을 튜플에 넣는 겁니다. 파서 p1,p2,...,p_n을 순서대로 조합한다고 하고 R(p)를 파서 p의 반환값이라고 하면, pSeq(p1,p2,...,p_n)이 만든 파서의 반환값은 (R(p1), R(p2), ..., R(p_n))입니다.

    파서를 작성할 때는 컴비네이터를 여러 겹 중첩해서 쓰는 일이 흔합니다. 그러면 튜플이 중첩되고, 여기서 값을 꺼내는 일이 곧 이 튜플을 “언래핑”하는 일입니다. 게다가 순서에 들어 있는 값을 전부 쓰지는 않을 수 있습니다. 공백을 파싱하기 위한 것일 뿐인 값도 있으니까요. 그래서 파서 결과로 값을 만들 때는 이런 값을 무시해야 합니다. 예를 들어 결과 튜플을 “매핑”해서 관련 있는 필드만 남기는 식으로 할 수 있습니다. 다른 방법도 있는데, 예컨대 R(p1)만 반환하는 p1.then_ignore(p2)처럼 파서를 이어 붙이는 방법입니다.

    표현을 좀 더 잘 골랐으면 좋았겠네요. 제가 뜻한 바가 이제 더 분명해졌기를 바랍니다.

    제 라이브러리로 작성한 문법의 파서와 다른 라이브러리로 작성한 파서를 나란히 비교한 글도 써 봤습니다. 예시로 도움이 될 수 있겠습니다: https://blog.arnedebo.com/posts/a-grammar-first-approach-to-parser-combinators/

  11. Jaxan HN

    저는 하스켈에서 늘 파서 컴비네이터를 써 왔는데, 말씀하신 그런 건 본 적이 없습니다. 하스켈에서는 보통 각 부분을 원하는 함수(예: AST 노드 생성자)에 바로 적용하니까 그런 것 같습니다.

  12. black_knight HN

    우리는 하스켈 덕분에 여러 모로 호강하고 있어요!

    파서 컴비네이터 하나만으로도 모나드(정확히는 애플리커티브 펑터)를 쓸 만한 가치가 있죠. 게다가 모나드로 할 수 있는 멋진 일이 그 밖에도 얼마나 많은데요!

  13. n_plus_1_acc HN

    맞아요. <$와 $> 연산자는 파서에 쓰기에 정말 우아해요.

  14. n_plus_1_acc HN

    맞아요. <$와 $> 연산자는 파서에 쓰기에 정말 우아해요.

  15. n_plus_1_acc HN

    맞아요. <$와 $> 연산자는 파서에 쓰기에 정말 우아해요.

  16. thedufer HN

    하스켈은 do 표기법으로 튜플을 만들고 푸는 과정을 숨길 수 있기 때문이라고 생각합니다. 저는 주로 OCaml에서 파서 컴비네이터를 쓰는데, 바인딩 연산자로 비슷한 요령을 씁니다. 이런 문법적 설탕이 없으면 훨씬 다루기 번거로워지는 게 사실입니다.

  17. kccqzy HN

    쓰시는 언어에 튜플 구조 분해 문법이 기본으로 있나요?

    무시하는 예시는 하스켈에서는 그냥 p1 <* p2예요(그 연산자는 표준 라이브러리에 있어요).

  18. marginalia_nu HN

    이게 왜 한 페이지로 안 되어 있는지 이해가 안 돼요. 슬라이드쇼라서 새로운 정보가 나올 때 앞의 “챕터”를 다시 찾아보기가 정말 어렵고, 검색도 안 되고요.

    디지털 매체에는 없는 종이 매체의 제약을, 괜한 미적 취향 때문에 굳이 다시 들여오는 것 같지 않나요?

  19. MomsAVoxell HN

    맞아요, 저도 처음에는 계속 읽을 엄두가 안 났어요 .. 끝까지 읽길 잘했지만요 .. 다음으로 넘기는 방법을 몰라서, 그냥 스크롤하면 될 걸 스크롤과 넘기기를 번갈아 해야 하는 게 짜증스러웠어요 ..

    그래도 사용자 경험이 훌륭한 내용을 가려 버리네요.

  20. MattRix HN

    말씀하시는 바는 알겠는데, 저는 좋았어요! 각 부분을 따로 떼어 놓으니 오히려 더 읽기 편하게 느껴지거든요. 이상적인 세상이라면 이런 글마다 독자가 “슬라이드쇼”와 “한 페이지” 보기를 전환할 수 있게 해 줄 텐데요. 같은 내용이 둘 다에 어울리니까요.

  21. testerius HN

    맞아요, 그러면 좋겠어요. 다만 챕터/섹션을 간단히 보이거나 숨기는 기능만 있어도 꽤 도움이 될 것 같아요. 코드 에디터의 폴더나 코드 조각 접기와 비슷한 식으로요(예를 들어 VS Code에 이 기능이 있죠).

  22. akst HN

    정말 멋진 웹사이트이고 이 주제도 아주 좋아합니다.

    그런데 작은 화면에서도 한번 테스트해 보시면 좋겠습니다. 관심 있는 콘텐츠를 위한 화면 공간이 너무 제한적이에요. 오른쪽 위 절반은 여백이 많고, 스크롤되는 콘텐츠는 사실상 사용 가능한 화면 공간의 3분의 1 정도만 쓰고, 왼쪽에도 또 다른 3분의 1 정도가 차지되어 있습니다.

    님의 웹사이트이고 님의 비전이니 이해하고, UI에서 다른 시도를 하시는 것도 존중합니다. 하지만 목표가 생각을 전달하는 것이라면, 독자로서는 콘텐츠에 더 많은 화면 공간이 주어지면 좋겠습니다. 이 글을 보려고 링크를 눌렀을 때는 다른 글에는 관심이 없거든요(적어도 일부러 찾아온 이 글을 다 읽기 전까지는요).

    참고로 지금 맥북 에어를 쓰고 있습니다.

  23. schindlabua HN

    피드백 감사합니다. 유튜브 영상과 블로그 글의 중간쯤, 한입 크기로 나눠 소비할 수 있는 무언가를 만들자는 아이디어였습니다. 비주얼이 말을 대부분 하게 하고 싶었는데, 파서 컴비네이터는 결국 글이 많이 나온 것 같네요. UI를 좀 더 다듬고, 테스트용으로 더 작은 폰도 구해 보겠습니다.

  24. akst HN

    계속 실험해 보세요.

    그리고 오른쪽 위에서 일어나는 일도 멋지지만, 사용자는 다른 콘텐츠를 어떻게 봐야 하는지 알아내는 데 정신이 팔려 있어서 그걸 제대로 감상하기가 어렵습니다. 아마 거기에 가장 많은 공을 들이셨을 텐데 말이죠.

    비주얼이 말을 대부분 하게 하고 싶었습니다

    좀 더 다듬어진 경험을 목표로 하신다면, 의도한 경험이 무엇인지 사용자가 헷갈릴 만한 요소를 줄이는 것도 고려해 볼 만합니다. 많은 사용자는 UI 각 부분이 어떻게 동작하는지에 대해 이미 선입견이 있어서, 의도하신 경험을 전달하는 데 방해가 될 수 있습니다.

  25. layer8 HN

    또 하나 나쁜 점은 페이지를 넘겨도 브라우저 기록에 남지 않아서, 브라우저의 뒤로/앞으로 가기로 이동할 수 없다는 겁니다.

    문서여야 할 것에 새 내비게이션 UI를 브라우저 위에 발명해 얹고 브라우저의 탐색 관례를 우회하는 건, 정말이지 좋은 생각이 아닙니다.

  26. doginasuit HN

    정말 재미있게 봤고, 여기 나온 아이디어를 직접 써 보는 것이 기대됩니다.

    효과적인 발표 형식에 아주 가까이 가셨다고 생각하는데, 글을 위한 공간이 좁은 게 가장 큰 불편이었습니다. 움직이는 비주얼도 도움은 되지만, 글의 의미를 받아들이려 할 때는 조금 산만하게 느껴지기도 했습니다. 비주얼을 숨기거나 펼치는 토글 하나로 두 문제를 모두 해결할 수 있을 것 같습니다.

  27. justinnk HN

    아주 멋진 시각 가이드네요! 여기서 파서에 관한 짧은 시 하나를 소개하는 게 어울릴 것 같습니다. 프리츠 뤼어(Fritz Ruehr)가 쓴 시인데, 컴퓨터공학 첫 학기 때부터 머릿속에 남아 있습니다. 이 시만 있으면 파서의 타입 시그니처는 절대 잊지 않을 겁니다.

    „사물을 위한 파서는 문자열에서 출발하여 사물과 문자열로 이루어진 쌍의 목록으로 가는 함수!“

    https://people.willamette.edu/~fruehr/haskell/seuss.html

  28. dmkolobov HN

    저도 그걸 찾아서 올리려던 참이었어요! 그런데 구글이 알아서 닥터 수스 풍 파서 컴비네이터 예제를 지어내려고 하더라고요.

    그리고 저도 컴퓨터공학 첫 학기에 이런 걸 접했으면 좋았을 텐데요.

  29. boomlinde HN

    첫 번째 주소는 호스트 이름일 수도 있으니 IP 주소로 파싱해서는 안 될 것 같습니다. 사소한 트집처럼 보일 수 있지만, 여러 종류의 구문 중 어느 하나가 올 수 있을 때 어떻게 하는지를 보여 줄 기회가 되기도 합니다.

    본문에 할당된 영역이 좁아서 글을 읽기가 다소 힘들었습니다. 챕터가 짧은데도 여러 페이지에서 스크롤해야 했습니다.

  30. mrkeen HN

    시작 타입으로는 좋지 않습니다:

      type Parser<T> = (input: string) => [T, string]

    이 타입은 문자열을 받으면 T를 반드시 반환한다는 뜻입니다. 하지만 파서는 T를 반환할 수도 있는 것입니다.

    기사는 또 ‘부분 파서(partial parser)’라는 개념으로 시작하고, 여기서 다른 (부분이 아닌?) 파서를 만들어 낸다고 하는데요?

      또는, 그리고 여기서 부분 파서의 진정한 힘이 나오는데, 체인 전체를 하나로 감싸 그 자체로 새로운 파서로 만듭니다.

    아니요, 구분은 없습니다. 부분 파서를 조합하면 부분 파서가 나옵니다. 완전한 파서(그게 무슨 뜻이든)를 조합하면 완전한 파서가 나오고요.

    (아이러니하게도 여기에는 ‘partial’이라는 말이 딱 맞는 정의가 있습니다. 모든 입력에 대해 잘 정의되지 않은 함수라는 뜻이죠. 어떤 입력에는 T가 반환되고, 다른 입력에는 어쩌면 오류가 던져질 수도 있고, 누가 알겠습니까..)

Hacker News에서 보기 ↗