파서 콤비네이터를 17장 슬라이드로 설명한 T3 블로그 글, Parser 타입 정의와 ping 출력 파싱 예시 소개
- 글은 Parser 타입을 입력 문자열을 받아 [결과, 나머지 문자열] 쌍을 돌려주는 함수로 정의하고, 이런 부분 파서를 조합해 더 큰 파서를 만드는 방식을 설명함
- pSeq로 pHello, pIgnoreWhitespace, pInteger를 묶으면 [string, null, number] 튜플을 돌려주는 pHello100 파서가 되고, pMap으로 감싸면 {greeting, who} 객체가 나옴
- 저자는 정규식이 복잡한 파싱에는 맞지 않고 tree-sitter는 과하다고 보며, 그 중간 영역에 파서 콤비네이터가 적합하다고 주장함
- ping 출력 한 덩어리를 헤더, 패킷 7개 목록, 통계 객체로 바꾸는 예시가 들어 있음. 전송 8개 중 7개 수신으로 손실률 12.5%, RTT 평균 115.88ms가 추출됨
Hacker News opinions
학부 때 문법 이론이랑 실무 파싱이 연결이 안 됐는데, 콤비네이터가 그 다리 역할을 해줬음. 근데 코드 스니펫 글씨가 커서 스크롤하기 불편하니까 폰트랑 헤더 좀 줄여주면 좋겠음.
NFA는 셀 수 없어서 균형 괄호 같은 건 정규식으로 못 잡음. 실무에선 쓰기 쉽거나 빨라야 해서 고르는 거고, 콤비네이터는 파싱 작업을 함수로 생각하기 쉬워서 좋음. 나도 학생들 가르치려고 TypeScript 콤비네이터 라이브러리를 하나 관리 중임.
글 쓴 사람인데 사이트 리디자인 중이라 덜 다듬어진 부분이 있음. 다음 버전에 반영하겠음. PCRE 같은 정규식이랑 콤비네이터 비교는 나도 아직 확실하지 않음.
Parser 타입 정의가 입력을 받으면 T를 준다는 식으로 읽혀서 시작 예제로는 별로임. partial이라는 말도 헷갈림. 조합하면 전부 partial이 되는 거 아님?
TypeScript에선 partial parser가 예외를 던질 수 있어서 그런 식으로 이해하면 됨. parsimmon도 그렇게 동작하는 걸로 앎.
콤비네이터는 함수형이라 항상 뭔가 반환해야 하는데, 반환할 게 없으면 unit 타입 같은 싱글턴 타입을 쓰면 됨.
partial을 실패할 수 있다는 뜻으로 보면, optional(elem)이랑 repeat(elem)은 elem이 실패할 때 입력을 소비하지 않으면 전체 함수임. 다만 repeat에 빈 문자열 매칭하는 elem을 넣으면 프로그래머 실수로 봐야 함.
Fritz Ruehr가 쓴 파서 시 하나 추천함. Parser for Things is a function from Strings to Lists of Pairs of Things and Strings 이 한 줄이면 타입 시그니처 절대 안 잊음.
pDigit이 123을 보면 (1, '23 ')을 주고, pInt는 (123, ' ')을 줌. 어디서 자를지는 각 파서 규칙이 정하는 거임. 나는 반환 타입을 (T, 나머지) 대신 Either<Error, (T, 나머지)>로 해야 한다고 주장하는 중임.
슬라이드 말고 한 페이지로 못 만드나? 이전 챕터 다시 보기도 힘들고 검색도 안 됨. 디지털인데 종이 매체 한계를 그대로 가져온 느낌임.
나도 처음엔 슬라이드 넘기는 게 짜증났는데, 챕터별로 끊어져 있어서 읽기는 편하더라. 둘 다 골라 볼 수 있게 하면 제일 좋을 듯함.
ping 출력에서 icmp_seq=3 ttl=52 같은 콜론 뒤 내용을 그냥 key-value로 파싱하는 pKeyVal() 같은 범용 파서를 넣었으면 훨씬 설득력 있었을 듯함.
첫 번째 주소는 IP로 파싱하면 안 됨. 호스트네임일 수도 있으니까. 그걸 살려서 두 종류 중 하나를 받는 경우를 보여줬으면 좋았을 텐데 아쉬움.
글에 한계도 좀 써줬으면 좋겠음. 좌재귀 문법은 못 다루고, 모호한 문법은 백트래킹이 많아져서 성능이 지수적으로 나빠짐.
나는 이걸 앱 흐름 쪽으로 옮기는 언어를 만들고 있음. 함수 사이에 seam을 선언하면 컴파일러가 중간 코드를 처리하는 식임. 메인 로직은 타입 집합 확장이랑 압축으로만 남음.