2장의 배경지식.
파서 컴비네이터
커밋 a9178695("Make a real compiler."(진짜 컴파일러 만들기), 2023-05-29)는
새 모듈 ParserComb.hs(165줄)를 추가하는데, 그 이름은 은유가 아니다:
작고 독립적인 파서 컴비네이터 라이브러리로, 파서 생성기나 외부 문법
파일이 아니라 평범한 하스켈 타입 클래스(Functor, Applicative,
Monad, Alternative)로 지은, Wadler/Hutton 파싱 계보의 Prsr 스타일
툴킷이다. 두 번째 새 모듈 Parse.hs(204줄)는 이를 이용해 2장이
소개하는 표면 문법을 파싱한다. 이 문서는 라이브러리 자체를 훑고, 2장은
그것이 무엇에 쓰이는지를 훑는다.
1. 파서 타입
a9178695:ParserComb.hs, 22–44행(LastFail, Res, Prsr를 함께,
전문 인용):
data LastFail
= LastFail Int [(String, [String])]
deriving (Show)
noFail :: LastFail
noFail = LastFail maxBound []
longest :: LastFail -> LastFail -> LastFail
longest lf1@(LastFail l1 x1) lf2@(LastFail l2 x2) =
case compare l1 l2 of
LT -> lf1
GT -> lf2
EQ -> LastFail l1 (x1 ++ x2)
longests :: [LastFail] -> LastFail
longests [] = undefined
longests xs = foldl1 longest xs
data Res s a = Many [(a, (String, s))] LastFail
deriving (Show)
newtype Prsr s a = P { runP :: (String, s) -> Res s a}
instance Show (Prsr s a) where show _ = "<<Prsr>>"
오류 기록 부분을 걷어내면 교과서적인 형태가 남는다: 파서란 남은 입력을 결과로 바꾸는 함수다. 다른 무엇보다 먼저 눈여겨볼 만한 점이 이 특정 함수에는 두 가지 있다:
String -> Maybe (a, String)가 아니다.Res s a는Many [(a, (String, s))] LastFail로, 하나가 아니라(결과, 나머지)쌍의 리스트다. 이 파서는 첫 번째로 성공한 파스에 곧바로 정착하지 않는다 — 여러 개를 돌려줄 수 있으며, 그 결과가 두 개 이상일 때 무엇을 할지 결정하는 곳이parseDie(a9178695:Parse.hs, 82–87행)다: 결과가 정확히 하나면 받아들이고, 없으면 정형화된 "found X, expected Y"(X를 찾았는데 Y를 기대함) 메시지가 되며(formatFailed,a9178695:ParserComb.hs101–113행 — 그 출력의 실제 트랜스크립트는 2장의 "직접 해보기" 연습 문제 2에 있다), 둘 이상이면error $ "Ambiguous:\n" ++ ...가 된다.Prsr s a는 두 번째 타입 매개변수s를 문자열과 나란히 꿰어 나른다. 이는 상태를 갖는 파서다 —s는 라이브러리가 고정하지 않는 임의의 파서 상태다.Parse.hs는 이를type P a = Prsr [Int] a로, 즉 들여쓰기 칼럼 스택으로 인스턴스화하여,ParserComb.hs가 레이아웃에 대해 아무것도 모른 채로도 완전한 하스켈식 레이아웃 규칙(아래 4절)을 얻어낸다.LastFail Int [(String, [String])]는 최종적으로 어느 파스가 성공하든 상관없이, 파서가 실패하기 전에 도달했던 가장 먼 지점과 거기서 무엇을 기대하고 있었는지를 기록한다(Int는 길이다 — 파서는 "입력을 얼마나 들어갔는지"를 남은 문자열의 양으로 측정하므로, 남은 길이가 짧을수록 더 멀리 진행한 것이다;longest라는 이름은 오해의 소지가 있다 — 실제로는 가장 짧은 나머지, 즉 가장 많이 소비한 파스를 고르고 있다). 이것이 "found X, expected Y" 오류 메시지의 원재료이며, 성공하든 실패하든 모든 컴비네이터를 관통해 나른다.
2. 순차 결합과 선택: 타입 클래스 배관
그 아래로 이어지는 모든 것 — do 표기법, <*>, <|> — 은 네 개의
인스턴스에서 나온다, 전문 인용(a9178695:ParserComb.hs, 46–75행):
instance Functor (Prsr s) where
fmap f p = P $ \ t ->
case runP p t of
Many aus lf -> Many [ (f a, u) | (a, u) <- aus ] lf
instance Applicative (Prsr s) where
(<*>) = ap
pure a = P $ \ t -> Many [(a, t)] noFail
instance Monad (Prsr s) where
return = pure
p >>= k = P $ \ t ->
case runP p t of
Many aus plf ->
let xss = [ runP (k a) u | (a, u) <- aus ]
in let (rss, lfs) = unzip [ (rs, lf) | Many rs lf <- xss ]
in Many (concat rss) (longests $ plf : lfs)
instance MonadFail (Prsr s) where
fail m = P $ \ (r, _) -> Many [] (LastFail (length r) [("fail", [m])])
instance MonadState s (Prsr s) where
get = P $ \ t@(_, s) -> Many [(s, t)] noFail
put s = P $ \ (f, _) -> Many [((), (f, s))] noFail
instance Alternative (Prsr s) where
empty = P $ \ (r, _) -> Many [] (LastFail (length r) [("empty", ["<empty>"])])
p <|> q = P $ \ t ->
case (runP p t, runP q t) of
(Many a lfa, Many b lfb) -> Many (a ++ b) (longest lfa lfb)
pure a는 입력을 소비하지 않고 성공해 a를 돌려준다 — 순차 결합의
기저 사례다. p >>= k는 "p로 파싱한 다음, p가 만들어낸 모든
결과 각각에 대해 k를 실행하고 그 결과로 나온 파서로 파싱하라"는
뜻이다 — 결과가 하나뿐인 파서라면 이는 그저 함수 합성이겠지만, Many가
(a, leftover) 쌍을 여러 개 담을 수 있으므로 >>=는 결과마다 한 번씩
k를 실행하고 이어 붙인다. Alternative의 p <|> q는 p와 q 둘
다를 같은 입력에 대해 실행하고, 둘의 성공 결과를 모두 이어 붙여
(a ++ b) 돌려준다 — 이는 보통 뜻하는 "p를 시도하고 실패하면 q로
넘어간다"가 아니다; 두 갈래가 항상 다 실행되고, 두 갈래의 결과가 모두
유지되며(단순한 백트래킹이 아니라 진짜 모호성이다), 두 개의 LastFail
기록만 longest로 병합된다.
마지막 대목은 라이브러리가 바로 옆에 다르게 동작하는 두 번째 선택
연산자를 함께 배치할 만큼 중요하다(a9178695:ParserComb.hs, 77–84행):
-- Left biased choice
(<|<) :: Prsr s a -> Prsr s a -> Prsr s a
p <|< q = P $ \ t ->
case runP p t of
Many [] lfa ->
case runP q t of
Many b lfb -> Many b (longest lfa lfb)
r -> r
<|<는 p가 결과를 전혀 만들어내지 못했을 때만 q를 시도한다 —
대부분의 파서 컴비네이터 튜토리얼이 <|>라고 부르는, 평범한 확정
선택이다. Parse.hs는 결정성이 중요한 곳(실제 중괄호 {와 들여쓰기로
촉발되는 가상의 중괄호를 가르는 것, 4절)에서는 정확히 <|<를 쓰고,
문법이 모호한 채로 있어도 되어 parseDie가 나중에 정리하게 둘 수 있는
곳에서는 그냥 <|>를 쓴다.
3. 문자를 직접 다루는 프리미티브
타입 클래스 계층 위에서, ParserComb.hs는 실제로 입력을 들여다보는
몇 안 되는 함수들을 정의한다. satisfy, char, eof
(a9178695:ParserComb.hs, 119–141행, string은 생략 — 같은 모양):
satisfy :: String -> (Char -> Bool) -> Prsr s Char
satisfy msg f = P $ \ t ->
case t of
(c:cs, s) | f c -> Many [(c, (cs, s))] noFail
(cs, _) -> Many [] (LastFail (length cs) [("satisfy", [msg])])
char :: Char -> Prsr s Char
char c = P $ \ t ->
case t of
(c':cs, s) | c == c' -> Many [(c, (cs, s))] noFail
(cs, _) -> Many [] (LastFail (length cs) [("char", [show c])])
...
eof :: Prsr s ()
eof = P $ \ t ->
case t of
("", _) -> Many [((), t)] noFail
(cs, _) -> Many [] (LastFail (length cs) [("eof", ["end-of-file"])])
이들 모두 똑같이 네 줄이다: 첫 글자(또는 eof의 경우 문자열 전체)를
보고, 성공하며 소비하거나 실패하며 이유를 기록한다. satisfy는 자신의
실패 기록을 위해 명시적인 msg 문자열을 받는다 — Parse.hs의 오류
출력(2장의 "직접 해보기", 연습 문제 2)에 보이는 "lower case",
"upper case", "digit", "symbol" 문자열은 모두 이 msg 인자에서
비롯된다.
그 위로, 세 가지 배관이 더 있다(a9178695:ParserComb.hs, 86–90행과
143–147행, 파일 내 서로 다른 두 지점, 각각 전문 인용):
emany :: Prsr s a -> Prsr s [a]
emany p = esome p <|< pure []
esome :: Prsr s a -> Prsr s [a]
esome p = (:) <$> p <*> emany p
...
(<?>) :: Prsr s a -> String -> Prsr s a
p <?> e = P $ \ t ->
-- trace ("<?> " ++ show e) $
case runP p t of
Many rs (LastFail l xs) -> Many rs (LastFail l [(m, e:es) | (m, es) <- xs ])
emany/esome은 "0개 이상"과 "1개 이상" — 통상적인 방식으로 상호
재귀하는 표준 클레이니 스타와 플러스다(esome p는 p를 하나 파싱한
다음 나머지를 emany p로 처리한다; emany p는 esome p이거나
아무것도 아니다). 라이브러리의 익스포트 목록은 Control.Applicative의
평범한 many와 some도 그대로 다시 익스포트한다(import Control.Applicative 줄의 --hiding (many, some) 주석은 주석
처리되어 있다 — 실제로는 임포트가 제한되어 있지 않다) — 그래서
Parse.hs에는 Alternative에서 나온 many/some과 이 모듈 자체의
즉시 실행형 emany/esome이 나란히 스코프에 들어와 있으며, 이
범위에서는 일관되게 e로 시작하는 쪽을 쓴다. <?>는 라벨을 붙이는
컴비네이터다: p를 실행하고, 실패 기록이 하나라도 생겼다면 그 안의
모든 기대 문자열 앞에 e를 붙인다 — 이 방식으로 pKeyword, pSymbol
등이, 그러지 않았다면 그냥 "symbol"이나 "lower case"라고만 했을
실패에 사람이 읽을 수 있는 이름("module", "=", "int")을 붙인다.
4. 생성 규칙 하나를 소리 내어 읽기
Parse.hs는 문법 전체를 이런 식으로 짓는다 — pModule, pDef,
pExpr, pCase 등등 — 각각이 더 작은 파서들로 지은 단일한
<$>/<*>/<|> 식이다. 맨 위의 것을 전문 인용한다
(a9178695:Parse.hs, 94–95행):
pModule :: P Module
pModule = Module <$> (pKeyword "module" *> pUIdent <* pKeyword' "where") <*> pBlock pDef
소리 내어 읽으면: 모듈을 파싱하려면, 먼저 키워드 module을 파싱하고
(*>는 그 결과를 버린다 — 키워드는 데이터를 담지 않으므로), 대문자
식별자를 파싱하고(pUIdent — 이것이 모듈 이름이 된다), 키워드
where를 파싱하고(<*가 이번에도 결과를 버린다), 정의들의 블록을
파싱한다(pBlock pDef — 레이아웃으로 경계 짓고 세미콜론으로 나눈
pDef의 목록, 아래에서 설명). 식별자와 정의 목록을 Module <$> ... <*> ...로 Module 값에 담는다. 여기에 새로 지은 파싱 코드는 하나도
없다 — 이미 정의된 파서 네 개(pKeyword, pUIdent, pKeyword',
pBlock)를 이미 정의된 컴비네이터 세 개(<$>, *>/<*, <*>)로
접착한 것뿐이다.
pBlock과 그 이웃들은 다시 볼 만한 가치가 있다 — 1절의 타입 매개변수
s가 제 몫을 하는 모습을 보여주기 때문이다: 하스켈식 레이아웃 규칙
(실제 {/;/} 또는 들여쓰기로 추론된 것)이 ParserComb.hs의
변경 없이 Prsr [Int] a 위의 사용자 수준 파서만으로 온전히 구현된다
(a9178695:Parse.hs, 176–204행, 전문 인용):
pLCurl :: P ()
pLCurl = pSym '{' <|< softLC
where softLC = do
msp <- pIndent
case msp of
Nothing -> fail "\\n"
Just sp -> do
-- traceM ("push " ++ show (length sp))
modify $ \ st -> length sp : st
pRCurl :: P ()
pRCurl = pSym '}' <|> softRC
where softRC = do
is <- get
if null is then
fail "}"
else do
put (tail is)
eof
pSemi :: P ()
pSemi = pSym ';'
pBlock :: P a -> P [a]
pBlock p = do
pLCurl
as <- esepBy p pSemi
pRCurl
pure as
pLCurl은 블록을 연다: 실제 { 리터럴이거나, 아니면 — 실제 {가
들여쓰기 경로도 함께 시도해서는 절대 안 되므로 <|<를 통한 확정
선택으로 — softLC인데, 이는 다음 줄의 들여쓰기를 읽고(여기서는 보이지
않는 pIndent) 그 칼럼을 modify로 상태 스택에 밀어 넣는다.
pRCurl은 블록을 닫는다: 실제 } 리터럴이거나, 스택을 팝하는
softRC인데 — 눈여겨볼 점은, 그 팝 뒤에 곧바로 eof가 따라올 때만
성공한다는 것이다. 이 덕분에 이 장난감 전체가 지금은 파일 내부에서
들여쓰기가 줄어들 때 가상의 닫는 중괄호를 결코 내보내지 않고도 버틴다
(일반적인 경우를 위해서는 Parse.hs의 다른 곳에 있는 pWhite가
inject를 통해 } 문자를 입력 스트림에 직접 주입한다). esepBy(여기
보이지 않음; esepBy1에 빈 리스트로의 대체 경로를 더한 것으로, 둘 다
emany와 <|>로 지은 평범한 사용자 코드다)가 세미콜론으로 나뉜
가운데 부분을 처리한다. pLCurl, pRCurl, pSemi, esepBy 어느
것도 ParserComb.hs가 특별한 지위로 익스포트하는 것이 아니다 — 이들은
pModule과 같은 방식으로, 2–3절의 같은 열한 개 남짓한 프리미티브로
지은 Parse.hs-지역 함수다.
5. 이 방식이 점진적 성장에 어울리는 이유
이것이야말로 상태 기계를 손으로 짜거나 파서 생성기 도구를 쓰는 대신
이런 식으로 파서를 작성하는 진짜 이득이다: 새 문법 조각은 같은
구성 요소로 지은 새 컴비네이터 식이 되어 다른 것들 옆에 끼워 넣어질
뿐, 재귀 하강 함수를 열두 가지에서 열여섯 가지 케이스로 밀어붙이는
재작성이 아니다. 바로 이 범위 안에서 이미 한 번 일어난 일이다: 커밋
4030f721("Parse more"(더 파싱하기))은 괄호로 감싼 연산자 형태((+),
연산자를 평범한 식별자로 쓰는 표기)를 총 열두 줄 추가로 붙인다: 파일의
다른 모든 파서와 똑같이 esome/satisfy/guard로 지은 새 pOper/
pOper' 쌍(열두 줄 중 아홉 줄), 정의를 반복하는 대신 pOper'를
재사용하도록 조정된 pSymbol, 그리고 <|>로 pAExpr에 덧붙인 새
대안 하나. 3장은 이를 더 큰 규모로
반복한다 — let, 중위 연산자, 튜플, 리스트 문법, do 표기법이 각각
p로 시작하는 새 정의 몇 개로 안착할 뿐, ParserComb.hs의 재구조화는
전혀 없다. 그 파일은 이 과정 내내 손대지 않은 채로 남는다. 1절의 파서
타입은 이후의 문법이 필요로 할 모든 것(순차 결합, 선택, 상태, 오류
추적)을 이미 갖추고 있다; 언어를 키우는 것은 문법 계층에서 순수하게
덧붙이기만 하면 되는 일이다.