์ฝ˜ํ…์ธ  ๋Œ€ํ‘œ ์ด๋ฏธ์ง€ - ๐Ÿงฉ Haskell๋กœ ๊ตฌํ˜„ํ•˜๋Š” ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ

๐Ÿงฉ Haskell๋กœ ๊ตฌํ˜„ํ•˜๋Š” ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ

ํ•จ์ˆ˜ํ˜• ํ”„๋กœ๊ทธ๋ž˜๋ฐ์˜ ๊ฝƒ, ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ๋ฅผ Haskell๋กœ ์™„์ „ ์ •๋ณตํ•˜๊ธฐ
Haskell Parser Combinator ํ•จ์ˆ˜ํ˜• ํ”„๋กœ๊ทธ๋ž˜๋ฐ ๊ธฐํƒ€ํ”„๋กœ๊ทธ๋žจ๊ฐœ๋ฐœ
์•ผ ๊ทผ๋ฐ Haskell๋กœ ํŒŒ์„œ ๋งŒ๋“ ๋‹ค๊ณ ? ๊ทธ๊ฑฐ ์–ด๋ ต์ง€ ์•Š์•„? ๐Ÿ˜…

ใ…‹ใ…‹ใ…‹ ์ฒ˜์Œ์—” ์ข€ ๋‚ฏ์„ค๊ธด ํ•œ๋ฐ, ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ ๊ฐœ๋… ์žก์œผ๋ฉด ์ง„์งœ ์‹ ์„ธ๊ณ„์ž„. ๋ ˆ๊ณ  ๋ธ”๋ก์ฒ˜๋Ÿผ ์กฐ๋ฆฝํ•˜๋Š” ๋А๋‚Œ์ด๋ผ ์˜คํžˆ๋ ค ์ง๊ด€์ ์ด๊ฑฐ๋“ !

์˜ค ๋ ˆ๊ณ ? ๊ทธ๊ฒŒ ๋ญ” ๋ง์ด์•ผ ใ„ทใ„ท

์ง€๊ธˆ๋ถ€ํ„ฐ ์ฐจ๊ทผ์ฐจ๊ทผ ์„ค๋ช…ํ•ด์ค„๊ฒŒ~ ๋”ฐ๋ผ์™€๋ด ๐Ÿš€
ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ์˜ ํ๋ฆ„ ์ž…๋ ฅ ๋ฌธ์ž์—ด "3 + 4 * 2" ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ many, choice between, sepBy... ๊ตฌ๋ฌธ ํŠธ๋ฆฌ(AST) Add(3, Mul(4, 2)) ์ตœ์ข… ๊ฒฐ๊ณผ 11 ์ž‘์€ ํŒŒ์„œ๋“ค์„ ์กฐํ•ฉ(combine)ํ•ด์„œ ๋ณต์žกํ•œ ์–ธ์–ด๋ฅผ ํŒŒ์‹ฑํ•˜๋Š” ๊ธฐ๋ฒ• char digit many choice โ†’ ์กฐํ•ฉ โ†’ ์™„์„ฑ๋œ ํŒŒ์„œ! ๐Ÿงฉ ๋ ˆ๊ณ ์ฒ˜๋Ÿผ ์กฐ๋ฆฝํ•˜๋Š” ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ
๐Ÿค” ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ๊ฐ€ ๋ญ”๋ฐ?

์ž, ์ผ๋‹จ ๊ธฐ๋ณธ๋ถ€ํ„ฐ ์งš๊ณ  ๊ฐ€์ž. ํŒŒ์„œ(Parser)๋Š” ํ…์ŠคํŠธ(๋ฌธ์ž์—ด)๋ฅผ ์ฝ์–ด์„œ ์˜๋ฏธ ์žˆ๋Š” ๊ตฌ์กฐ๋กœ ๋ณ€ํ™˜ํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์ด์•ผ. ์˜ˆ๋ฅผ ๋“ค์–ด "3 + 4 * 2"๋ผ๋Š” ๋ฌธ์ž์—ด์„ ์ฝ์–ด์„œ "๋ง์…ˆ์ด๊ณ , ์˜ค๋ฅธ์ชฝ ํ”ผ์—ฐ์‚ฐ์ž๋Š” ๊ณฑ์…ˆ์ด์•ผ"๋ผ๋Š” ๊ตฌ์กฐ๋กœ ๋ฐ”๊ฟ”์ฃผ๋Š” ๊ฑฐ์ง€.

๊ทธ๋Ÿฐ๋ฐ ํŒŒ์„œ๋ฅผ ๋งŒ๋“œ๋Š” ๋ฐฉ๋ฒ•์ด ์—ฌ๋Ÿฌ ๊ฐ€์ง€ ์žˆ์–ด. ์ „ํ†ต์ ์œผ๋กœ๋Š” ๋ ‰์„œ(Lexer) + ํŒŒ์„œ ์ œ๋„ˆ๋ ˆ์ดํ„ฐ(yacc, bison, ANTLR ๋“ฑ)๋ฅผ ์“ฐ๋Š” ๋ฐฉ์‹์ด ์žˆ๊ณ , ์•„๋‹ˆ๋ฉด ์ง์ ‘ ์†์œผ๋กœ ์žฌ๊ท€ ํ•˜๊ฐ• ํŒŒ์„œ(Recursive Descent Parser)๋ฅผ ์งœ๋Š” ๋ฐฉ๋ฒ•๋„ ์žˆ์–ด.

๊ทธ๋Ÿฐ๋ฐ Haskell ์„ธ๊ณ„์—์„œ๋Š” ํ›จ์”ฌ ์šฐ์•„ํ•œ ๋ฐฉ๋ฒ•์ด ์žˆ์–ด. ๋ฐ”๋กœ ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ(Parser Combinator)์•ผ!

๐Ÿ“Œ ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ์˜ ํ•ต์‹ฌ ์•„์ด๋””์–ด ์ž‘์€ ํŒŒ์„œ๋“ค์„ ํ•จ์ˆ˜๋กœ ํ‘œํ˜„ํ•˜๊ณ , ์ด ํ•จ์ˆ˜๋“ค์„ ์กฐํ•ฉ(combine)ํ•ด์„œ ๋” ํฐ ํŒŒ์„œ๋ฅผ ๋งŒ๋“œ๋Š” ๊ธฐ๋ฒ•.

๊ฐ๊ฐ์˜ ํŒŒ์„œ๋Š” "์ž…๋ ฅ ๋ฌธ์ž์—ด์„ ๋ฐ›์•„์„œ, ํŒŒ์‹ฑ ๊ฒฐ๊ณผ์™€ ๋‚จ์€ ๋ฌธ์ž์—ด์„ ๋ฐ˜ํ™˜ํ•˜๋Š” ํ•จ์ˆ˜"์•ผ.
๊ทธ๋ฆฌ๊ณ  ์ด ํŒŒ์„œ๋“ค์„ ์ปด๋น„๋„ค์ดํ„ฐ(combinator)๋ผ๋Š” ๊ณ ์ฐจ ํ•จ์ˆ˜๋กœ ์กฐํ•ฉํ•ด์„œ ๋ณต์žกํ•œ ํŒŒ์„œ๋ฅผ ๋งŒ๋“ค์–ด๋‚ด๋Š” ๊ฑฐ์ง€.

์™œ Haskell์ด ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ์— ํŠนํžˆ ์ž˜ ๋งž๋ƒ๊ณ ? ์ด์œ ๊ฐ€ ์žˆ์–ด ใ…‹ใ…‹ใ…‹

๐ŸŽฏ Haskell์ด ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ์— ์ฐฐ๋–ก์ธ ์ด์œ 
  • 1 ๊ณ ์ฐจ ํ•จ์ˆ˜(Higher-Order Functions): ํ•จ์ˆ˜๋ฅผ ๊ฐ’์ฒ˜๋Ÿผ ๋‹ค๋ฃจ๊ณ  ์กฐํ•ฉํ•˜๋Š” ๊ฒŒ ์ž์—ฐ์Šค๋Ÿฌ์›€
  • 2 ํƒ€์ž… ์‹œ์Šคํ…œ: ๊ฐ•๋ ฅํ•œ ํƒ€์ž… ์ถ”๋ก ์œผ๋กœ ํŒŒ์„œ ์กฐํ•ฉ ์‹œ ํƒ€์ž… ์•ˆ์ „์„ฑ ๋ณด์žฅ
  • 3 Monad / Applicative: ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ์˜ ์กฐํ•ฉ ํŒจํ„ด์ด Monad/Applicative์™€ ์™„๋ฒฝํ•˜๊ฒŒ ๋งž์•„๋–จ์–ด์ง
  • 4 ์ง€์—ฐ ํ‰๊ฐ€(Lazy Evaluation): ๋ฌดํ•œ ๋ฌธ๋ฒ•๋„ ์ž์—ฐ์Šค๋Ÿฝ๊ฒŒ ํ‘œํ˜„ ๊ฐ€๋Šฅ
  • 5 ๊ฐ„๊ฒฐํ•œ ๋ฌธ๋ฒ•: do ํ‘œ๊ธฐ๋ฒ•, ์—ฐ์‚ฐ์ž ์˜ค๋ฒ„๋กœ๋”ฉ์œผ๋กœ ํŒŒ์„œ ์ฝ”๋“œ๊ฐ€ BNF ๋ฌธ๋ฒ•์ฒ˜๋Ÿผ ์ฝํž˜

๐Ÿ—๏ธ ํŒŒ์„œ์˜ ํƒ€์ž…์„ ์ง์ ‘ ์ •์˜ํ•ด๋ณด์ž

์ด๋ก ๋งŒ ๋“ค์œผ๋ฉด ์ง€๋ฃจํ•˜๋‹ˆ๊นŒ ๋ฐ”๋กœ ์ฝ”๋“œ๋กœ ๊ฐ€๋ณด์ž! ใ„ฑใ„ฑ ๐Ÿ”ฅ

ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ๋ฅผ ์ดํ•ดํ•˜๋ ค๋ฉด ๋จผ์ € "ํŒŒ์„œ๊ฐ€ ๋ญ”์ง€"๋ฅผ ํƒ€์ž…์œผ๋กœ ํ‘œํ˜„ํ•ด์•ผ ํ•ด. Haskell์—์„œ ํŒŒ์„œ์˜ ๊ฐ€์žฅ ๊ธฐ๋ณธ์ ์ธ ํƒ€์ž…์€ ์ด๋ ‡๊ฒŒ ์ƒ๊ฒผ์–ด:

Haskell
-- ๊ฐ€์žฅ ๋‹จ์ˆœํ•œ ํŒŒ์„œ ํƒ€์ž…
newtype Parser a = Parser { runParser :: String -> Maybe (a, String) }

์ด๊ฒŒ ๋ญ” ๋œป์ด๋ƒ๋ฉด:

Parser a๋Š” String์„ ๋ฐ›์•„์„œ, ํŒŒ์‹ฑ์— ์„ฑ๊ณตํ•˜๋ฉด Just (๊ฒฐ๊ณผ๊ฐ’, ๋‚จ์€๋ฌธ์ž์—ด)์„ ๋ฐ˜ํ™˜ํ•˜๊ณ ,
์‹คํŒจํ•˜๋ฉด Nothing์„ ๋ฐ˜ํ™˜ํ•˜๋Š” ํ•จ์ˆ˜๋ฅผ ๊ฐ์‹ผ ํƒ€์ž…์ด์•ผ.

a๋Š” ํŒŒ์‹ฑ ๊ฒฐ๊ณผ์˜ ํƒ€์ž…์ด์•ผ. ์˜ˆ๋ฅผ ๋“ค์–ด ์ˆซ์ž๋ฅผ ํŒŒ์‹ฑํ•˜๋ฉด Parser Int, ๋ฌธ์ž๋ฅผ ํŒŒ์‹ฑํ•˜๋ฉด Parser Char.

์‹ค์ œ๋กœ ์‚ฌ์šฉํ•˜๋Š” ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ๋“ค์€ ์ด๋ณด๋‹ค ํ›จ์”ฌ ์ •๊ตํ•˜์ง€๋งŒ, ๊ฐœ๋… ์ดํ•ด๋ฅผ ์œ„ํ•ด ์ด ๋‹จ์ˆœํ•œ ๋ฒ„์ „์œผ๋กœ ์‹œ์ž‘ํ•ด๋ณด์ž.

๊ธฐ๋ณธ ํŒŒ์„œ ๋งŒ๋“ค๊ธฐ

๊ฐ€์žฅ ๊ธฐ์ดˆ์ ์ธ ํŒŒ์„œ๋ถ€ํ„ฐ ๋งŒ๋“ค์–ด๋ณผ๊ฒŒ. ๋”ฑ ํ•œ ๊ธ€์ž๋ฅผ ํŒŒ์‹ฑํ•˜๋Š” ํŒŒ์„œ์•ผ:

Haskell
-- ์กฐ๊ฑด์„ ๋งŒ์กฑํ•˜๋Š” ๋‹จ์ผ ๋ฌธ์ž๋ฅผ ํŒŒ์‹ฑํ•˜๋Š” ํŒŒ์„œ
satisfy :: (Char -> Bool) -> Parser Char
satisfy predicate = Parser $ \input ->
  case input of
    []     -> Nothing          -- ์ž…๋ ฅ์ด ๋น„์–ด์žˆ์œผ๋ฉด ์‹คํŒจ
    (c:cs) -> if predicate c   -- ์ฒซ ๊ธ€์ž๊ฐ€ ์กฐ๊ฑด์„ ๋งŒ์กฑํ•˜๋ฉด
              then Just (c, cs) -- ์„ฑ๊ณต: (ํŒŒ์‹ฑ๋œ ๋ฌธ์ž, ๋‚จ์€ ๋ฌธ์ž์—ด)
              else Nothing      -- ์‹คํŒจ

-- ํŠน์ • ๋ฌธ์ž๋ฅผ ํŒŒ์‹ฑํ•˜๋Š” ํŒŒ์„œ
char :: Char -> Parser Char
char c = satisfy (== c)

-- ์ˆซ์ž ๋ฌธ์ž๋ฅผ ํŒŒ์‹ฑํ•˜๋Š” ํŒŒ์„œ
digit :: Parser Char
digit = satisfy isDigit

-- ์•ŒํŒŒ๋ฒณ์„ ํŒŒ์‹ฑํ•˜๋Š” ํŒŒ์„œ
letter :: Parser Char
letter = satisfy isAlpha

์ด์ œ ์ด ํŒŒ์„œ๋“ค์„ ์‹ค์ œ๋กœ ์‹คํ–‰ํ•ด๋ณด๋ฉด:

Haskell
-- ์‹คํ–‰ ์˜ˆ์‹œ
runParser (char 'H') "Hello"   -- Just ('H', "ello")
runParser (char 'H') "World"   -- Nothing
runParser digit "123abc"       -- Just ('1', "23abc")
runParser digit "abc"          -- Nothing
๐Ÿ’ก ํ•ต์‹ฌ ํฌ์ธํŠธ! ํŒŒ์„œ๊ฐ€ ์„ฑ๊ณตํ•˜๋ฉด ํŒŒ์‹ฑ๋œ ๊ฐ’๊ณผ ๋‚จ์€ ๋ฌธ์ž์—ด์„ ํ•จ๊ป˜ ๋ฐ˜ํ™˜ํ•ด. ์ด "๋‚จ์€ ๋ฌธ์ž์—ด"์ด ๋‹ค์Œ ํŒŒ์„œ์—๊ฒŒ ๋„˜์–ด๊ฐ€๋Š” ๊ฑฐ์•ผ. ์ด๊ฒŒ ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ์˜ ํ•ต์‹ฌ ๋ฉ”์ปค๋‹ˆ์ฆ˜์ด์•ผ!

โšก Functor, Applicative, Monad - ํŒŒ์„œ์˜ ์ŠˆํผํŒŒ์›Œ

์ž, ์ด์ œ ์ง„์งœ ์žฌ๋ฐŒ๋Š” ๋ถ€๋ถ„์ด์•ผ. Haskell์˜ ํƒ€์ž… ํด๋ž˜์Šค๋“ค์„ ํŒŒ์„œ์— ์ ์šฉํ•˜๋ฉด ํŒŒ์„œ ์กฐํ•ฉ์ด ์—„์ฒญ ์šฐ์•„ํ•ด์ ธ. ใ„นใ…‡ ๊ฐ๋™๋ฐ›์„ ์ค€๋น„ํ•ด ใ…‹ใ…‹ใ…‹

1๏ธโƒฃ Functor - ํŒŒ์„œ ๊ฒฐ๊ณผ๋ฅผ ๋ณ€ํ™˜ํ•˜๊ธฐ

Functor๋Š” "์ปจํ…Œ์ด๋„ˆ ์•ˆ์˜ ๊ฐ’์„ ํ•จ์ˆ˜๋กœ ๋ณ€ํ™˜"ํ•˜๋Š” ๊ฐœ๋…์ด์•ผ. ํŒŒ์„œ์— ์ ์šฉํ•˜๋ฉด "ํŒŒ์‹ฑ ๊ฒฐ๊ณผ๋ฅผ ๋ณ€ํ™˜"ํ•  ์ˆ˜ ์žˆ์–ด:

Haskell
instance Functor Parser where
  fmap f (Parser p) = Parser $ \input ->
    case p input of
      Nothing        -> Nothing
      Just (a, rest) -> Just (f a, rest)

-- ์‚ฌ์šฉ ์˜ˆ์‹œ
digitValue :: Parser Int
digitValue = fmap digitToInt digit
-- digit์€ '3' ๊ฐ™์€ ๋ฌธ์ž๋ฅผ ํŒŒ์‹ฑํ•˜๊ณ 
-- fmap digitToInt๋กœ ์ˆซ์ž 3์œผ๋กœ ๋ณ€ํ™˜!

runParser digitValue "3abc"  -- Just (3, "abc")
2๏ธโƒฃ Applicative - ์—ฌ๋Ÿฌ ํŒŒ์„œ๋ฅผ ์ˆœ์„œ๋Œ€๋กœ ์ ์šฉํ•˜๊ธฐ

Applicative๋Š” ์—ฌ๋Ÿฌ ํŒŒ์„œ๋ฅผ ์ˆœ์„œ๋Œ€๋กœ ์ ์šฉํ•˜๊ณ  ๊ฒฐ๊ณผ๋ฅผ ์กฐํ•ฉํ•  ๋•Œ ์จ. ์ด๊ฒŒ ์ง„์งœ ๊ฐ•๋ ฅํ•ด:

Haskell
instance Applicative Parser where
  pure a = Parser $ \input -> Just (a, input)
  -- pure: ํ•ญ์ƒ ์„ฑ๊ณตํ•˜๊ณ  ์ž…๋ ฅ์„ ์†Œ๋น„ํ•˜์ง€ ์•Š๋Š” ํŒŒ์„œ

  (Parser pf) <*> (Parser pa) = Parser $ \input ->
    case pf input of
      Nothing        -> Nothing
      Just (f, rest) ->
        case pa rest of
          Nothing         -> Nothing
          Just (a, rest') -> Just (f a, rest')
  -- <*>: ํ•จ์ˆ˜๋ฅผ ํŒŒ์‹ฑํ•˜๊ณ , ๊ทธ ํ•จ์ˆ˜๋ฅผ ๊ฐ’ ํŒŒ์‹ฑ ๊ฒฐ๊ณผ์— ์ ์šฉ

-- ์‚ฌ์šฉ ์˜ˆ์‹œ: ๋‘ ์ˆซ์ž ์‚ฌ์ด์˜ '+'๋ฅผ ํŒŒ์‹ฑ
-- "3+4" -> (3, 4)
addExpr :: Parser (Int, Int)
addExpr = (,) <$> digitValue <*> (char '+' *> digitValue)
-- <$>๋Š” fmap์˜ ์—ฐ์‚ฐ์ž ๋ฒ„์ „
-- *>๋Š” ์™ผ์ชฝ ํŒŒ์„œ ๊ฒฐ๊ณผ๋ฅผ ๋ฒ„๋ฆฌ๊ณ  ์˜ค๋ฅธ์ชฝ ๊ฒฐ๊ณผ๋งŒ ์ทจํ•จ

runParser addExpr "3+4"  -- Just ((3, 4), "")
3๏ธโƒฃ Monad - ์ด์ „ ๊ฒฐ๊ณผ์— ๋”ฐ๋ผ ๋‹ค์Œ ํŒŒ์„œ ๊ฒฐ์ •ํ•˜๊ธฐ

Monad๋Š” ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ์˜ ์ตœ์ข… ๋ณด์Šค์•ผ. ์ด์ „ ํŒŒ์‹ฑ ๊ฒฐ๊ณผ์— ๋”ฐ๋ผ ๋‹ค์Œ์— ์–ด๋–ค ํŒŒ์„œ๋ฅผ ์“ธ์ง€ ๋™์ ์œผ๋กœ ๊ฒฐ์ •ํ•  ์ˆ˜ ์žˆ์–ด:

Haskell
instance Monad Parser where
  return = pure
  (Parser pa) >>= f = Parser $ \input ->
    case pa input of
      Nothing        -> Nothing
      Just (a, rest) ->
        let (Parser pb) = f a
        in pb rest

-- do ํ‘œ๊ธฐ๋ฒ•์œผ๋กœ ์“ฐ๋ฉด ์ง„์งœ ์ฝ๊ธฐ ์‰ฌ์›Œ์ง!
-- "3+4" ํŒŒ์‹ฑํ•˜๊ธฐ
addExprM :: Parser Int
addExprM = do
  left  <- digitValue      -- ์™ผ์ชฝ ์ˆซ์ž ํŒŒ์‹ฑ
  _     <- char '+'        -- '+' ํŒŒ์‹ฑ (๊ฒฐ๊ณผ ๋ฒ„๋ฆผ)
  right <- digitValue      -- ์˜ค๋ฅธ์ชฝ ์ˆซ์ž ํŒŒ์‹ฑ
  return (left + right)    -- ๋‘ ์ˆซ์ž๋ฅผ ๋”ํ•œ ๊ฒฐ๊ณผ ๋ฐ˜ํ™˜

runParser addExprM "3+4"   -- Just (7, "")
runParser addExprM "3-4"   -- Nothing ('+' ํŒŒ์‹ฑ ์‹คํŒจ)
๐Ÿ’ก do ํ‘œ๊ธฐ๋ฒ•์˜ ๋งˆ๋ฒ•! Monad์˜ do ํ‘œ๊ธฐ๋ฒ•์„ ์“ฐ๋ฉด ํŒŒ์„œ ์ฝ”๋“œ๊ฐ€ ๋งˆ์น˜ ๋ช…๋ นํ˜• ํ”„๋กœ๊ทธ๋ž˜๋ฐ์ฒ˜๋Ÿผ ์ฝํ˜€. "์ด๊ฑธ ํŒŒ์‹ฑํ•˜๊ณ , ์ €๊ฑธ ํŒŒ์‹ฑํ•˜๊ณ , ๊ฒฐ๊ณผ๋ฅผ ์กฐํ•ฉํ•ด" ์ด๋Ÿฐ ์‹์œผ๋กœ. ๊ทผ๋ฐ ๋‚ด๋ถ€๋Š” ์™„์ „ํžˆ ํ•จ์ˆ˜ํ˜•์ด์•ผ. ์ง„์งœ ์šฐ์•„ํ•˜์ง€ ์•Š๋ƒ ใ„ทใ„ท
Monad ์ฒด์ธ: "3+4" ํŒŒ์‹ฑ ๊ณผ์ • digitValue ์ž…๋ ฅ: "3+4" ๊ฒฐ๊ณผ: (3, "+4") 3 โ†’ char '+' ์ž…๋ ฅ: "+4" ๊ฒฐ๊ณผ: ('+', "4") ๋ฒ„๋ฆผ digitValue ์ž…๋ ฅ: "4" ๊ฒฐ๊ณผ: (4, "") 4 โ†’ return (3 + 4) = 7 โœ“ ๋‚จ์€ ์ž…๋ ฅ: "" ๊ฐ ํŒŒ์„œ๊ฐ€ ์ˆœ์„œ๋Œ€๋กœ ์‹คํ–‰๋˜๊ณ , ๊ฒฐ๊ณผ๊ฐ€ ๋‹ค์Œ ํŒŒ์„œ๋กœ ์ „๋‹ฌ๋ผ ์ค‘๊ฐ„์— ํ•˜๋‚˜๋ผ๋„ ์‹คํŒจํ•˜๋ฉด ์ „์ฒด๊ฐ€ Nothing์œผ๋กœ ๋‹จ๋ฝ(short-circuit) ์‹คํŒจ ์ผ€์ด์Šค: "3-4" ์ž…๋ ฅ ์‹œ โ†’ char '+' ๋‹จ๊ณ„์—์„œ Nothing โ†’ ์ „์ฒด Nothing Monad์˜ ๋‹จ๋ฝ ํ‰๊ฐ€(short-circuit) ๋•๋ถ„์— ์ž๋™์œผ๋กœ ์ฒ˜๋ฆฌ๋จ!
๐Ÿ”ง ํ•ต์‹ฌ ์ปด๋น„๋„ค์ดํ„ฐ ์ด์ •๋ฆฌ

์ด์ œ ์‹ค์ œ๋กœ ๋งŽ์ด ์“ฐ์ด๋Š” ์ปด๋น„๋„ค์ดํ„ฐ๋“ค์„ ์‚ดํŽด๋ณด์ž. ์ด๊ฒƒ๋“ค์ด ๋ ˆ๊ณ  ๋ธ”๋ก์ด์•ผ ใ…‹ใ…‹ใ…‹ ์ด๊ฑธ ์กฐํ•ฉํ•ด์„œ ๋ญ๋“  ๋งŒ๋“ค ์ˆ˜ ์žˆ์–ด!

Alternative - ์„ ํƒ ์ปด๋น„๋„ค์ดํ„ฐ

ํŒŒ์„œ A๊ฐ€ ์‹คํŒจํ•˜๋ฉด ํŒŒ์„œ B๋ฅผ ์‹œ๋„ํ•˜๋Š” ์„ ํƒ(choice) ์ปด๋น„๋„ค์ดํ„ฐ์•ผ:

Haskell
instance Alternative Parser where
  empty = Parser $ \_ -> Nothing
  -- empty: ํ•ญ์ƒ ์‹คํŒจํ•˜๋Š” ํŒŒ์„œ

  (Parser pa) <|> (Parser pb) = Parser $ \input ->
    case pa input of
      Nothing -> pb input  -- pa ์‹คํŒจํ•˜๋ฉด pb ์‹œ๋„
      success -> success   -- pa ์„ฑ๊ณตํ•˜๋ฉด ๊ทธ๋Œ€๋กœ ๋ฐ˜ํ™˜

-- ์‚ฌ์šฉ ์˜ˆ์‹œ
-- ์ˆซ์ž ๋˜๋Š” ์•ŒํŒŒ๋ฒณ ํŒŒ์‹ฑ
alphaNum :: Parser Char
alphaNum = digit <|> letter

runParser alphaNum "3abc"  -- Just ('3', "abc")
runParser alphaNum "abc3"  -- Just ('a', "bc3")
runParser alphaNum "!@#"   -- Nothing
many์™€ some - ๋ฐ˜๋ณต ์ปด๋น„๋„ค์ดํ„ฐ

ํŒŒ์„œ๋ฅผ 0๋ฒˆ ์ด์ƒ, ๋˜๋Š” 1๋ฒˆ ์ด์ƒ ๋ฐ˜๋ณต ์ ์šฉํ•˜๋Š” ์ปด๋น„๋„ค์ดํ„ฐ์•ผ:

Haskell
-- many: 0๋ฒˆ ์ด์ƒ ๋ฐ˜๋ณต (ํ•ญ์ƒ ์„ฑ๊ณต)
many :: Parser a -> Parser [a]
many p = some p <|> pure []

-- some: 1๋ฒˆ ์ด์ƒ ๋ฐ˜๋ณต (์ตœ์†Œ 1๋ฒˆ ์„ฑ๊ณตํ•ด์•ผ ํ•จ)
some :: Parser a -> Parser [a]
some p = (:) <$> p <*> many p

-- ์‚ฌ์šฉ ์˜ˆ์‹œ: ์—ฌ๋Ÿฌ ์ž๋ฆฌ ์ˆซ์ž ํŒŒ์‹ฑ
digits :: Parser String
digits = some digit

number :: Parser Int
number = read <$> digits

runParser number "123abc"  -- Just (123, "abc")
runParser number "abc"     -- Nothing (์ตœ์†Œ 1๊ฐœ ํ•„์š”)
runParser (many digit) "abc"  -- Just ("", "abc") (0๊ฐœ๋„ OK)
between - ๊ฐ์‹ธ๊ธฐ ์ปด๋น„๋„ค์ดํ„ฐ
Haskell
-- between: ์•ž๋’ค๋ฅผ ํŠน์ • ํŒŒ์„œ๋กœ ๊ฐ์‹ธ๊ธฐ
between :: Parser open -> Parser close -> Parser a -> Parser a
between open close p = open *> p <* close

-- ์‚ฌ์šฉ ์˜ˆ์‹œ: ๊ด„ํ˜ธ ์•ˆ์˜ ์ˆซ์ž ํŒŒ์‹ฑ
parens :: Parser a -> Parser a
parens = between (char '(') (char ')')

runParser (parens number) "(123)"   -- Just (123, "")
runParser (parens number) "[123]"   -- Nothing
sepBy - ๊ตฌ๋ถ„์ž ์ปด๋น„๋„ค์ดํ„ฐ
Haskell
-- sepBy: ๊ตฌ๋ถ„์ž๋กœ ๋ถ„๋ฆฌ๋œ ๋ชฉ๋ก ํŒŒ์‹ฑ
sepBy :: Parser a -> Parser sep -> Parser [a]
sepBy p sep = sepBy1 p sep <|> pure []

sepBy1 :: Parser a -> Parser sep -> Parser [a]
sepBy1 p sep = (:) <$> p <*> many (sep *> p)

-- ์‚ฌ์šฉ ์˜ˆ์‹œ: ์‰ผํ‘œ๋กœ ๋ถ„๋ฆฌ๋œ ์ˆซ์ž ๋ชฉ๋ก
numberList :: Parser [Int]
numberList = sepBy number (char ',')

runParser numberList "1,2,3,4"  -- Just ([1,2,3,4], "")
runParser numberList ""          -- Just ([], "")
optional๊ณผ lookAhead
Haskell
-- optional: ์žˆ์–ด๋„ ๋˜๊ณ  ์—†์–ด๋„ ๋˜๋Š” ํŒŒ์„œ
optional :: Parser a -> Parser (Maybe a)
optional p = (Just <$> p) <|> pure Nothing

-- lookAhead: ํŒŒ์‹ฑํ•˜๋˜ ์ž…๋ ฅ์„ ์†Œ๋น„ํ•˜์ง€ ์•Š์Œ
lookAhead :: Parser a -> Parser a
lookAhead (Parser p) = Parser $ \input ->
  case p input of
    Nothing      -> Nothing
    Just (a, _)  -> Just (a, input)  -- ์ž…๋ ฅ ๊ทธ๋Œ€๋กœ ์œ ์ง€!

-- notFollowedBy: ๋‹ค์Œ์— ํŠน์ • ํŒจํ„ด์ด ์˜ค์ง€ ์•Š์•„์•ผ ์„ฑ๊ณต
notFollowedBy :: Parser a -> Parser ()
notFollowedBy (Parser p) = Parser $ \input ->
  case p input of
    Nothing -> Just ((), input)
    Just _  -> Nothing
โš ๏ธ ์ฃผ์˜! many์™€ some์„ ์“ธ ๋•Œ ๋ฌดํ•œ ๋ฃจํ”„ ์กฐ์‹ฌ! ํ•ญ์ƒ ์„ฑ๊ณตํ•˜๋Š” ํŒŒ์„œ(์˜ˆ: pure ())๋ฅผ many์— ๋„ฃ์œผ๋ฉด ๋ฌดํ•œ ๋ฃจํ”„์— ๋น ์ ธ. ๋ฐ˜๋“œ์‹œ ์ž…๋ ฅ์„ ์†Œ๋น„ํ•˜๋Š” ํŒŒ์„œ๋ฅผ ๋„ฃ์–ด์•ผ ํ•ด.

๐Ÿš€ ์‹ค์ „! ์ˆ˜์‹ ํŒŒ์„œ ๋งŒ๋“ค๊ธฐ

์ด์ œ ์ง„์งœ ์‹ค์ „์ด์•ผ. ์‚ฌ์น™์—ฐ์‚ฐ ์ˆ˜์‹์„ ํŒŒ์‹ฑํ•˜๋Š” ํŒŒ์„œ๋ฅผ ์ฒ˜์Œ๋ถ€ํ„ฐ ๋งŒ๋“ค์–ด๋ณผ๊ฒŒ. ์ด๊ฒŒ ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ์˜ ์ง„๊ฐ€๋ฅผ ๋ณด์—ฌ์ฃผ๋Š” ์˜ˆ์ œ์•ผ ใ„ทใ„ท

์ˆ˜์‹ ํŒŒ์„œ? ๊ทธ๊ฑฐ ์—ฐ์‚ฐ์ž ์šฐ์„ ์ˆœ์œ„ ๊ฐ™์€ ๊ฑฐ ์ฒ˜๋ฆฌํ•˜๊ธฐ ์–ด๋ ต์ง€ ์•Š์•„?

๋งž์•„! ๊ทธ๊ฒŒ ํ•ต์‹ฌ ๋‚œ์ด๋„์•ผ. ๊ทผ๋ฐ ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ๋กœ ํ•˜๋ฉด BNF ๋ฌธ๋ฒ•์„ ๊ทธ๋Œ€๋กœ ์ฝ”๋“œ๋กœ ์˜ฎ๊ธฐ๋Š” ๋А๋‚Œ์ด๋ผ ์ƒ๊ฐ๋ณด๋‹ค ๊น”๋”ํ•ด ใ…‹ใ…‹

๋จผ์ € ํŒŒ์‹ฑํ•  ๋ฌธ๋ฒ•์„ BNF๋กœ ์ •์˜ํ•ด๋ณด์ž:

๐Ÿ“ ์ˆ˜์‹ ๋ฌธ๋ฒ• (BNF) expr ::= term (('+' | '-') term)*
term ::= factor (('*' | '/') factor)*
factor ::= number | '(' expr ')'
number ::= digit+

์ด ๋ฌธ๋ฒ•์ด ์—ฐ์‚ฐ์ž ์šฐ์„ ์ˆœ์œ„๋ฅผ ์ž๋™์œผ๋กœ ์ฒ˜๋ฆฌํ•ด์ค˜. *์™€ /๊ฐ€ +์™€ -๋ณด๋‹ค ๋จผ์ € ์ฒ˜๋ฆฌ๋˜๋„๋ก ๊ณ„์ธต ๊ตฌ์กฐ๋กœ ํ‘œํ˜„ํ•œ ๊ฑฐ์•ผ.
Haskell - ์™„์ „ํ•œ ์ˆ˜์‹ ํŒŒ์„œ
import Control.Applicative
import Data.Char

-- ํŒŒ์„œ ํƒ€์ž… ์ •์˜
newtype Parser a = Parser { runParser :: String -> Maybe (a, String) }

-- Functor ์ธ์Šคํ„ด์Šค
instance Functor Parser where
  fmap f (Parser p) = Parser $ \input ->
    fmap (\(a, rest) -> (f a, rest)) (p input)

-- Applicative ์ธ์Šคํ„ด์Šค
instance Applicative Parser where
  pure a = Parser $ \input -> Just (a, input)
  (Parser pf) <*> (Parser pa) = Parser $ \input -> do
    (f, rest)  <- pf input
    (a, rest') <- pa rest
    return (f a, rest')

-- Alternative ์ธ์Šคํ„ด์Šค
instance Alternative Parser where
  empty = Parser $ \_ -> Nothing
  (Parser pa) <|> (Parser pb) = Parser $ \input ->
    pa input <|> pb input

-- Monad ์ธ์Šคํ„ด์Šค
instance Monad Parser where
  return = pure
  (Parser pa) >>= f = Parser $ \input -> do
    (a, rest) <- pa input
    runParser (f a) rest

-- ๊ธฐ๋ณธ ํŒŒ์„œ๋“ค
satisfy :: (Char -> Bool) -> Parser Char
satisfy pred = Parser $ \input ->
  case input of
    (c:cs) | pred c -> Just (c, cs)
    _               -> Nothing

char :: Char -> Parser Char
char c = satisfy (== c)

digit :: Parser Char
digit = satisfy isDigit

spaces :: Parser String
spaces = many (satisfy isSpace)

-- ๊ณต๋ฐฑ์„ ๋ฌด์‹œํ•˜๋Š” ํ† ํฐ ํŒŒ์„œ
token :: Parser a -> Parser a
token p = spaces *> p <* spaces

-- ์ˆซ์ž ํŒŒ์„œ
number :: Parser Int
number = token $ read <$> some digit

-- ์—ฐ์‚ฐ์ž ํŒŒ์„œ
addOp :: Parser (Int -> Int -> Int)
addOp = token $ (char '+' *> pure (+)) <|> (char '-' *> pure (-))

mulOp :: Parser (Int -> Int -> Int)
mulOp = token $ (char '*' *> pure (*)) <|> (char '/' *> pure div)

-- ์ˆ˜์‹ ํŒŒ์„œ (์—ฐ์‚ฐ์ž ์šฐ์„ ์ˆœ์œ„ ์ฒ˜๋ฆฌ)
-- chainl1: ์™ผ์ชฝ ๊ฒฐํ•ฉ ์—ฐ์‚ฐ์ž ์ฒ˜๋ฆฌ
chainl1 :: Parser a -> Parser (a -> a -> a) -> Parser a
chainl1 p op = do
  x <- p
  rest x
  where
    rest x = (do
      f <- op
      y <- p
      rest (f x y)) <|> pure x

-- factor: ์ˆซ์ž ๋˜๋Š” ๊ด„ํ˜ธ ํ‘œํ˜„์‹
factor :: Parser Int
factor = number <|> parens expr

-- term: ๊ณฑ์…ˆ/๋‚˜๋ˆ—์…ˆ
term :: Parser Int
term = chainl1 factor mulOp

-- expr: ๋ง์…ˆ/๋บ„์…ˆ
expr :: Parser Int
expr = chainl1 term addOp

-- ๊ด„ํ˜ธ ์ฒ˜๋ฆฌ
parens :: Parser a -> Parser a
parens p = token (char '(') *> p <* token (char ')')

-- ์ „์ฒด ํŒŒ์„œ ์‹คํ–‰
calculate :: String -> Maybe Int
calculate input = fst <$> runParser expr input

์ด์ œ ์‹ค์ œ๋กœ ์จ๋ณด๋ฉด:

Haskell - ์‹คํ–‰ ๊ฒฐ๊ณผ
calculate "3 + 4"          -- Just 7
calculate "3 + 4 * 2"      -- Just 11  (์šฐ์„ ์ˆœ์œ„ ์ฒ˜๋ฆฌ!)
calculate "(3 + 4) * 2"    -- Just 14  (๊ด„ํ˜ธ ์ฒ˜๋ฆฌ!)
calculate "10 / 2 + 3"     -- Just 8
calculate "1 + 2 + 3 + 4"  -- Just 10  (์™ผ์ชฝ ๊ฒฐํ•ฉ!)
calculate "abc"             -- Nothing  (ํŒŒ์‹ฑ ์‹คํŒจ)
๐Ÿ’ก ์ง„์งœ ์‹ ๊ธฐํ•œ ๋ถ€๋ถ„! BNF ๋ฌธ๋ฒ•์„ ๋ณด๋ฉด:
expr ::= term (('+' | '-') term)*
์ฝ”๋“œ๋ฅผ ๋ณด๋ฉด:
expr = chainl1 term addOp

๊ฑฐ์˜ 1:1 ๋Œ€์‘์ด์•ผ! ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ์˜ ์ฝ”๋“œ๊ฐ€ ๋ฌธ๋ฒ• ๋ช…์„ธ ์ž์ฒด์ฒ˜๋Ÿผ ์ฝํ˜€. ์ด๊ฒŒ ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ์˜ ์ตœ๋Œ€ ์žฅ์ ์ด์•ผ ใ…‹ใ…‹ใ…‹

๐Ÿ“ฆ ์‹ค์ „ ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ: Parsec & Megaparsec

์œ„์—์„œ ์ง์ ‘ ๋งŒ๋“  ํŒŒ์„œ๋Š” ๊ฐœ๋… ์ดํ•ด์šฉ์ด๊ณ , ์‹ค์ œ ํ”„๋กœ์ ํŠธ์—์„œ๋Š” ๊ฒ€์ฆ๋œ ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ๋ฅผ ์จ์•ผ ํ•ด. Haskell ์ƒํƒœ๊ณ„์—์„œ ๊ฐ€์žฅ ์œ ๋ช…ํ•œ ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ๋“ค์„ ์†Œ๊ฐœํ• ๊ฒŒ!

๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ ํŠน์ง• ์ถ”์ฒœ ์šฉ๋„
Parsec Haskell ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ์˜ ์›์กฐ, ์•ˆ์ •์  ํ•™์Šต, ๊ฐ„๋‹จํ•œ ํŒŒ์„œ
Megaparsec Parsec ๊ฐœ์„ ํŒ, ๋” ๋‚˜์€ ์—๋Ÿฌ ๋ฉ”์‹œ์ง€ ์‹ค๋ฌด ํ”„๋กœ์ ํŠธ
Attoparsec ์„ฑ๋Šฅ ์ตœ์ ํ™”, ๋ฐ”์ด๋„ˆ๋ฆฌ ํŒŒ์‹ฑ ์ง€์› ๊ณ ์„ฑ๋Šฅ ํŒŒ์‹ฑ
trifecta ์˜ˆ์œ ์—๋Ÿฌ ๋ฉ”์‹œ์ง€, ์ƒ‰์ƒ ์ถœ๋ ฅ ๊ฐœ๋ฐœ์ž ๋„๊ตฌ
Megaparsec์œผ๋กœ ๋‹ค์‹œ ์“ฐ๊ธฐ

Megaparsec์„ ์“ฐ๋ฉด ์—๋Ÿฌ ์ฒ˜๋ฆฌ๊ฐ€ ํ›จ์”ฌ ๊ฐ•๋ ฅํ•ด์ ธ. ์‹ค์ œ ์ฝ”๋“œ๋ฅผ ๋ณด์ž:

Haskell - Megaparsec ์‚ฌ์šฉ
{-# LANGUAGE OverloadedStrings #-}

import Text.Megaparsec
import Text.Megaparsec.Char
import qualified Text.Megaparsec.Char.Lexer as L
import Data.Void

type Parser = Parsec Void String

-- ๊ณต๋ฐฑ ์ฒ˜๋ฆฌ
sc :: Parser ()
sc = L.space space1 lineCmnt blockCmnt
  where
    lineCmnt  = L.skipLineComment "--"
    blockCmnt = L.skipBlockComment "{-" "-}"

-- ํ† ํฐ ํŒŒ์„œ (๊ณต๋ฐฑ ์ž๋™ ์ฒ˜๋ฆฌ)
lexeme :: Parser a -> Parser a
lexeme = L.lexeme sc

symbol :: String -> Parser String
symbol = L.symbol sc

-- ์ •์ˆ˜ ํŒŒ์„œ
integer :: Parser Int
integer = lexeme L.decimal

-- ๊ด„ํ˜ธ ํŒŒ์„œ
parens :: Parser a -> Parser a
parens = between (symbol "(") (symbol ")")

-- ์ˆ˜์‹ ํŒŒ์„œ (Megaparsec ๋ฒ„์ „)
expr :: Parser Int
expr = makeExprParser term operatorTable

term :: Parser Int
term = parens expr <|> integer

operatorTable :: [[Operator Parser Int]]
operatorTable =
  [ [ InfixL ((*) <$ symbol "*")
    , InfixL (div <$ symbol "/") ]
  , [ InfixL ((+) <$ symbol "+")
    , InfixL ((-) <$ symbol "-") ] ]

-- ํŒŒ์‹ฑ ์‹คํ–‰
parseExpr :: String -> Either (ParseErrorBundle String Void) Int
parseExpr = parse (sc *> expr <* eof) ""

Megaparsec์˜ makeExprParser๋ฅผ ์“ฐ๋ฉด ์—ฐ์‚ฐ์ž ์šฐ์„ ์ˆœ์œ„ ์ฒ˜๋ฆฌ๊ฐ€ ๋” ์„ ์–ธ์ ์œผ๋กœ ๋ผ. ํ…Œ์ด๋ธ” ํ˜•ํƒœ๋กœ ์šฐ์„ ์ˆœ์œ„๋ฅผ ์ •์˜ํ•˜๋ฉด ๋์ด์•ผ!

๐ŸŽฏ Megaparsec์˜ ๊ฐ•๋ ฅํ•œ ์—๋Ÿฌ ๋ฉ”์‹œ์ง€

์ง์ ‘ ๋งŒ๋“  ํŒŒ์„œ๋Š” ์‹คํŒจํ•˜๋ฉด ๊ทธ๋ƒฅ Nothing์ด์ง€๋งŒ, Megaparsec์€ ์ด๋Ÿฐ ์—๋Ÿฌ๋ฅผ ์ค˜:

1:5:

|

1 | 3 + * 4

|     ^

unexpected '*'

expecting integer or '('


์ค„ ๋ฒˆํ˜ธ, ์ปฌ๋Ÿผ ๋ฒˆํ˜ธ, ๊ธฐ๋Œ€ํ–ˆ๋˜ ๊ฒƒ๊นŒ์ง€ ์•Œ๋ ค์ค˜. ์‹ค์ œ ์ปดํŒŒ์ผ๋Ÿฌ ์ˆ˜์ค€์˜ ์—๋Ÿฌ ๋ฉ”์‹œ์ง€์•ผ!

๐Ÿ—‚๏ธ ์‹ค์ „ ์˜ˆ์ œ: JSON ํŒŒ์„œ ๋งŒ๋“ค๊ธฐ

ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ์˜ ์ง„๊ฐ€๋ฅผ ๋ณด์—ฌ์ฃผ๋Š” ์˜ˆ์ œ๋กœ JSON ํŒŒ์„œ๋ฅผ ๋งŒ๋“ค์–ด๋ณด์ž. JSON์€ ์‹ค์ œ๋กœ ๋งŽ์ด ์“ฐ์ด๋Š” ํ˜•์‹์ด๊ณ , ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ๋กœ ๋งŒ๋“ค๋ฉด ์–ผ๋งˆ๋‚˜ ๊ฐ„๊ฒฐํ•œ์ง€ ๋ณด์—ฌ์ค„๊ฒŒ!

JSON ํŒŒ์„œ๋ฅผ? ๊ทธ๊ฑฐ ๊ฝค ๋ณต์žกํ•˜์ง€ ์•Š์•„? ๋ฌธ์ž์—ด, ์ˆซ์ž, ๋ฐฐ์—ด, ๊ฐ์ฒด ๋‹ค ์ฒ˜๋ฆฌํ•ด์•ผ ํ•˜์ž–์•„

๋งž์•„! ๊ทผ๋ฐ ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ๋กœ ํ•˜๋ฉด ๊ฐ ํƒ€์ž…๋ณ„๋กœ ํŒŒ์„œ ๋งŒ๋“ค๊ณ  ์กฐํ•ฉํ•˜๋ฉด ๋ผ. ์ƒ๊ฐ๋ณด๋‹ค ์ฝ”๋“œ๊ฐ€ ์งง์•„์„œ ๋†€๋ž„ ๊ฑฐ์•ผ ใ…‹ใ…‹ใ…‹
Haskell - JSON ํŒŒ์„œ
import Text.Megaparsec
import Text.Megaparsec.Char
import qualified Text.Megaparsec.Char.Lexer as L
import Data.Map (Map)
import qualified Data.Map as Map

-- JSON ๊ฐ’ ํƒ€์ž… ์ •์˜
data JsonValue
  = JsonNull
  | JsonBool Bool
  | JsonNumber Double
  | JsonString String
  | JsonArray [JsonValue]
  | JsonObject (Map String JsonValue)
  deriving (Show, Eq)

type Parser = Parsec Void String

-- ๊ณต๋ฐฑ ์ฒ˜๋ฆฌ
sc :: Parser ()
sc = L.space space1 empty empty

lexeme :: Parser a -> Parser a
lexeme = L.lexeme sc

symbol :: String -> Parser String
symbol = L.symbol sc

-- null ํŒŒ์„œ
jsonNull :: Parser JsonValue
jsonNull = JsonNull <$ symbol "null"

-- bool ํŒŒ์„œ
jsonBool :: Parser JsonValue
jsonBool = JsonBool True  <$ symbol "true"
       <|> JsonBool False <$ symbol "false"

-- ์ˆซ์ž ํŒŒ์„œ
jsonNumber :: Parser JsonValue
jsonNumber = JsonNumber <$> lexeme L.float
         <|> JsonNumber . fromIntegral <$> lexeme L.decimal

-- ๋ฌธ์ž์—ด ํŒŒ์„œ (์ด์Šค์ผ€์ดํ”„ ์ฒ˜๋ฆฌ ํฌํ•จ)
jsonString :: Parser JsonValue
jsonString = JsonString <$> lexeme stringLiteral

stringLiteral :: Parser String
stringLiteral = char '"' *> manyTill L.charLiteral (char '"')

-- ๋ฐฐ์—ด ํŒŒ์„œ
jsonArray :: Parser JsonValue
jsonArray = JsonArray <$>
  between (symbol "[") (symbol "]")
          (jsonValue `sepBy` symbol ",")

-- ๊ฐ์ฒด ํŒŒ์„œ
jsonObject :: Parser JsonValue
jsonObject = JsonObject . Map.fromList <$>
  between (symbol "{") (symbol "}")
          (keyValue `sepBy` symbol ",")
  where
    keyValue = do
      key <- stringLiteral <* symbol ":"
      val <- jsonValue
      return (key, val)

-- ์ „์ฒด JSON ๊ฐ’ ํŒŒ์„œ (์žฌ๊ท€!)
jsonValue :: Parser JsonValue
jsonValue = lexeme $
      jsonNull
  <|> jsonBool
  <|> jsonNumber
  <|> jsonString
  <|> jsonArray
  <|> jsonObject

-- ํŒŒ์‹ฑ ์‹คํ–‰
parseJson :: String -> Either (ParseErrorBundle String Void) JsonValue
parseJson = parse (sc *> jsonValue <* eof) ""

์‹ค์ œ๋กœ ์จ๋ณด๋ฉด:

Haskell - JSON ํŒŒ์„œ ์‹คํ–‰
-- ๊ฐ„๋‹จํ•œ JSON
parseJson "null"          -- Right JsonNull
parseJson "true"          -- Right (JsonBool True)
parseJson "42"            -- Right (JsonNumber 42.0)
parseJson "\"hello\""     -- Right (JsonString "hello")

-- ๋ฐฐ์—ด
parseJson "[1, 2, 3]"
-- Right (JsonArray [JsonNumber 1.0, JsonNumber 2.0, JsonNumber 3.0])

-- ๊ฐ์ฒด
parseJson "{\"name\": \"Alice\", \"age\": 30}"
-- Right (JsonObject (fromList [("age", JsonNumber 30.0),
--                              ("name", JsonString "Alice")]))

-- ์ค‘์ฒฉ ๊ตฌ์กฐ
parseJson "{\"data\": [1, {\"x\": true}, null]}"
-- Right (JsonObject ...)
๐Ÿ’ก ์žฌ๊ท€ ํŒŒ์„œ์˜ ๋งˆ๋ฒ•! jsonValue๊ฐ€ jsonArray์™€ jsonObject๋ฅผ ์ฐธ์กฐํ•˜๊ณ , ๊ทธ ์•ˆ์—์„œ ๋‹ค์‹œ jsonValue๋ฅผ ์ฐธ์กฐํ•ด. ์ด๋Ÿฐ ์ƒํ˜ธ ์žฌ๊ท€๊ฐ€ Haskell์˜ ์ง€์—ฐ ํ‰๊ฐ€ ๋•๋ถ„์— ์ž์—ฐ์Šค๋Ÿฝ๊ฒŒ ๋™์ž‘ํ•ด. ๋‹ค๋ฅธ ์–ธ์–ด์—์„œ๋Š” ์ด๋Ÿฐ ์žฌ๊ท€ ํŒŒ์„œ ์ •์˜๊ฐ€ ๊นŒ๋‹ค๋กœ์šธ ์ˆ˜ ์žˆ์–ด!
JSON ํŒŒ์„œ ๊ตฌ์กฐ (์žฌ๊ท€ ์กฐํ•ฉ) jsonValue (์ค‘์‹ฌ ํŒŒ์„œ) jsonNull jsonBool jsonNumber jsonString jsonArray ์žฌ๊ท€! jsonObject jsonValue = jsonNull <|> jsonBool <|> jsonNumber <|> jsonString <|> jsonArray <|> jsonObject
๐Ÿšจ ์—๋Ÿฌ ์ฒ˜๋ฆฌ์™€ ์ข‹์€ ์—๋Ÿฌ ๋ฉ”์‹œ์ง€ ๋งŒ๋“ค๊ธฐ

ํŒŒ์„œ๋ฅผ ๋งŒ๋“ค ๋•Œ ์—๋Ÿฌ ์ฒ˜๋ฆฌ๋Š” ์ •๋ง ์ค‘์š”ํ•ด. ์‚ฌ์šฉ์ž๊ฐ€ ์ž˜๋ชป๋œ ์ž…๋ ฅ์„ ๋„ฃ์—ˆ์„ ๋•Œ "ํŒŒ์‹ฑ ์‹คํŒจ"๋ผ๊ณ ๋งŒ ํ•˜๋ฉด ๋„ˆ๋ฌด ๋ถˆ์นœ์ ˆํ•˜์ž–์•„ ใ…‹ใ…‹ใ…‹

Megaparsec์˜ ์—๋Ÿฌ ์ฒ˜๋ฆฌ
Haskell - ์—๋Ÿฌ ์ฒ˜๋ฆฌ
-- label: ์—๋Ÿฌ ๋ฉ”์‹œ์ง€์— ์„ค๋ช… ์ถ”๊ฐ€
jsonValue :: Parser JsonValue
jsonValue = label "JSON ๊ฐ’" $
      jsonNull
  <|> jsonBool
  <|> jsonNumber
  <|> jsonString
  <|> jsonArray
  <|> jsonObject

-- <?> ์—ฐ์‚ฐ์ž (label์˜ ์ค‘์œ„ ๋ฒ„์ „)
integer :: Parser Int
integer = L.decimal <?> "์ •์ˆ˜"

-- try: ํŒŒ์‹ฑ ์‹คํŒจ ์‹œ ์ž…๋ ฅ์„ ๋˜๋Œ๋ฆฌ๊ธฐ
-- (๋ฐฑํŠธ๋ž˜ํ‚น ํ™œ์„ฑํ™”)
jsonNumber :: Parser JsonValue
jsonNumber = JsonNumber <$>
  (try (lexeme L.float) <|> fromIntegral <$> lexeme L.decimal)

-- ์ปค์Šคํ…€ ์—๋Ÿฌ ๋งŒ๋“ค๊ธฐ
data MyError = InvalidEscape Char
  deriving (Show, Ord, Eq)

instance ShowErrorComponent MyError where
  showErrorComponent (InvalidEscape c) =
    "์ž˜๋ชป๋œ ์ด์Šค์ผ€์ดํ”„ ๋ฌธ์ž: \\" ++ [c]

-- ์—๋Ÿฌ ๋ฐœ์ƒ์‹œํ‚ค๊ธฐ
parseEscape :: Parser Char
parseEscape = do
  _ <- char '\\'
  c <- anySingle
  case c of
    'n'  -> return '\n'
    't'  -> return '\t'
    '"'  -> return '"'
    '\\' -> return '\\'
    _    -> customFailure (InvalidEscape c)
์—๋Ÿฌ ๋ณต๊ตฌ (Error Recovery)

์‹ค์ œ ์ปดํŒŒ์ผ๋Ÿฌ์ฒ˜๋Ÿผ ์—๋Ÿฌ๊ฐ€ ๋‚˜๋„ ๊ณ„์† ํŒŒ์‹ฑ์„ ์ง„ํ–‰ํ•˜๊ณ  ์‹ถ์„ ๋•Œ:

Haskell - ์—๋Ÿฌ ๋ณต๊ตฌ
-- withRecovery: ์—๋Ÿฌ ๋ฐœ์ƒ ์‹œ ๋ณต๊ตฌ ์ „๋žต ์ ์šฉ
robustParser :: Parser [JsonValue]
robustParser = many $
  withRecovery recover jsonValue
  where
    recover err = do
      -- ์—๋Ÿฌ๋ฅผ ๊ธฐ๋กํ•˜๊ณ  ๋‹ค์Œ ์‰ผํ‘œ๋‚˜ ์ค„๋ฐ”๊ฟˆ๊นŒ์ง€ ์Šคํ‚ต
      registerParseError err
      skipManyTill anySingle (void (char ',') <|> void newline <|> eof)
      return JsonNull  -- ์‹คํŒจํ•œ ์ž๋ฆฌ์— null ๋ฐ˜ํ™˜

โšก ์„ฑ๋Šฅ ์ตœ์ ํ™”: ๋น ๋ฅธ ํŒŒ์„œ ๋งŒ๋“ค๊ธฐ

ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ๋Š” ํŽธ๋ฆฌํ•˜์ง€๋งŒ ์„ฑ๋Šฅ์ด ๊ฑฑ์ •๋  ์ˆ˜ ์žˆ์–ด. ํŠนํžˆ ํฐ ํŒŒ์ผ์„ ํŒŒ์‹ฑํ•  ๋•Œ. ๋ช‡ ๊ฐ€์ง€ ์ตœ์ ํ™” ํŒ์„ ์•Œ์•„๋ณด์ž!

1. Attoparsec ์‚ฌ์šฉํ•˜๊ธฐ

์„ฑ๋Šฅ์ด ์ค‘์š”ํ•˜๋‹ค๋ฉด Attoparsec์„ ์จ. ByteString ๊ธฐ๋ฐ˜์œผ๋กœ ๋™์ž‘ํ•ด์„œ ํ›จ์”ฌ ๋น ๋ฅด๊ฑฐ๋“ :

Haskell - Attoparsec
import Data.Attoparsec.ByteString.Char8
import Data.ByteString (ByteString)

-- Attoparsec์€ API๊ฐ€ Megaparsec๊ณผ ๋น„์Šทํ•ด
-- ํ•˜์ง€๋งŒ ByteString ๊ธฐ๋ฐ˜์ด๋ผ ํ›จ์”ฌ ๋น ๋ฆ„!
fastNumber :: Parser Int
fastNumber = decimal

fastJson :: Parser JsonValue
fastJson = skipSpace *> (
      (JsonNull   <$ string "null")
  <|> (JsonBool True  <$ string "true")
  <|> (JsonBool False <$ string "false")
  <|> (JsonNumber <$> double)
  <|> (JsonString <$> stringLiteral)
  <|> (JsonArray  <$> arrayParser)
  <|> (JsonObject <$> objectParser))
2. ๋ฐฑํŠธ๋ž˜ํ‚น ์ตœ์†Œํ™”
๐Ÿ”‘ ์„ฑ๋Šฅ์˜ ํ•ต์‹ฌ: ๋ฐฑํŠธ๋ž˜ํ‚น(Backtracking) ์ตœ์†Œํ™” ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ์—์„œ ์„ฑ๋Šฅ ๋ฌธ์ œ์˜ ์ฃผ๋ฒ”์€ ๊ณผ๋„ํ•œ ๋ฐฑํŠธ๋ž˜ํ‚น์ด์•ผ.
try๋ฅผ ๋‚จ๋ฐœํ•˜๋ฉด ๊ฐ™์€ ์ž…๋ ฅ์„ ์—ฌ๋Ÿฌ ๋ฒˆ ํŒŒ์‹ฑํ•˜๊ฒŒ ๋ผ์„œ ๋А๋ ค์ ธ.

ํ•ด๊ฒฐ์ฑ…: ์ฒซ ๊ธ€์ž(lookahead)๋กœ ์–ด๋–ค ํŒŒ์„œ๋ฅผ ์“ธ์ง€ ๋ฏธ๋ฆฌ ๊ฒฐ์ •ํ•˜๋Š” ์˜ˆ์ธก ํŒŒ์‹ฑ(Predictive Parsing)์„ ํ™œ์šฉํ•ด!
Haskell - ํšจ์œจ์ ์ธ ํŒŒ์„œ
-- ๋น„ํšจ์œจ์ : ๋ชจ๋“  ๊ฒฝ์šฐ์— try ์‚ฌ์šฉ
badJsonValue :: Parser JsonValue
badJsonValue =
      try jsonNull
  <|> try jsonBool
  <|> try jsonNumber
  <|> try jsonString
  <|> try jsonArray
  <|> try jsonObject

-- ํšจ์œจ์ : ์ฒซ ๊ธ€์ž๋กœ ๋ถ„๊ธฐ
goodJsonValue :: Parser JsonValue
goodJsonValue = do
  c <- lookAhead anySingle
  case c of
    'n'  -> jsonNull
    't'  -> jsonBool
    'f'  -> jsonBool
    '"'  -> jsonString
    '['  -> jsonArray
    '{'  -> jsonObject
    _    -> jsonNumber  -- ์ˆซ์ž๋‚˜ '-'๋กœ ์‹œ์ž‘
3. ์ŠคํŠธ๋ฆฌ๋ฐ ํŒŒ์‹ฑ
Haskell - ์ŠคํŠธ๋ฆฌ๋ฐ
-- ํฐ ํŒŒ์ผ์„ ํ•œ ๋ฒˆ์— ๋ฉ”๋ชจ๋ฆฌ์— ์˜ฌ๋ฆฌ์ง€ ์•Š๊ณ  ์ŠคํŠธ๋ฆฌ๋ฐ์œผ๋กœ ํŒŒ์‹ฑ
import qualified Data.Attoparsec.ByteString as A
import qualified Data.ByteString as BS

streamParse :: FilePath -> IO [JsonValue]
streamParse path = do
  content <- BS.readFile path
  case A.parseOnly (many fastJson) content of
    Left err  -> error err
    Right vals -> return vals

๐ŸŒ ์‹ค์ œ ํ™œ์šฉ ์‚ฌ๋ก€๋“ค

ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ๊ฐ€ ์‹ค์ œ๋กœ ์–ด๋””์— ์“ฐ์ด๋Š”์ง€ ์•Œ์•„๋ณด์ž. ์ƒ๊ฐ๋ณด๋‹ค ์—„์ฒญ ๋งŽ์€ ๊ณณ์—์„œ ์“ฐ์—ฌ!

๐Ÿ”จ ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ ์‹ค์ œ ํ™œ์šฉ ๋ถ„์•ผ
  • 1 ํ”„๋กœ๊ทธ๋ž˜๋ฐ ์–ธ์–ด ๊ตฌํ˜„: GHC(Haskell ์ปดํŒŒ์ผ๋Ÿฌ) ์ž์ฒด๊ฐ€ ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ ์‚ฌ์šฉ
  • 2 ์„ค์ • ํŒŒ์ผ ํŒŒ์‹ฑ: YAML, TOML, INI ํŒŒ์ผ ํŒŒ์„œ
  • 3 ์ฟผ๋ฆฌ ์–ธ์–ด: SQL ํŒŒ์„œ, GraphQL ํŒŒ์„œ
  • 4 ๋งˆํฌ์—… ์–ธ์–ด: Markdown, HTML, XML ํŒŒ์„œ
  • 5 ํ”„๋กœํ† ์ฝœ ํŒŒ์‹ฑ: HTTP ํ—ค๋”, ์ด๋ฉ”์ผ ํ—ค๋” ํŒŒ์‹ฑ
  • 6 DSL(๋„๋ฉ”์ธ ํŠนํ™” ์–ธ์–ด): ๋น„์ฆˆ๋‹ˆ์Šค ๊ทœ์น™ ์–ธ์–ด, ํ…œํ”Œ๋ฆฟ ์–ธ์–ด
  • 7 ๋ฐ์ดํ„ฐ ๋ณ€ํ™˜: CSV, ๋กœ๊ทธ ํŒŒ์ผ ํŒŒ์‹ฑ
์‹ค์ œ ์˜ˆ: ๊ฐ„๋‹จํ•œ ๋งˆํฌ๋‹ค์šด ํŒŒ์„œ
Haskell - ๋งˆํฌ๋‹ค์šด ํŒŒ์„œ (์ผ๋ถ€)
data MarkdownBlock
  = Heading Int String      -- # ์ œ๋ชฉ
  | Paragraph String        -- ์ผ๋ฐ˜ ๋ฌธ๋‹จ
  | CodeBlock String String -- ์ฝ”๋“œ ๋ธ”๋ก (์–ธ์–ด, ๋‚ด์šฉ)
  | BulletList [String]     -- ๋ชฉ๋ก
  deriving (Show)

-- ์ œ๋ชฉ ํŒŒ์„œ (# ~ ######)
heading :: Parser MarkdownBlock
heading = do
  hashes <- some (char '#')
  _ <- char ' '
  title <- manyTill anySingle newline
  return $ Heading (length hashes) title

-- ์ฝ”๋“œ ๋ธ”๋ก ํŒŒ์„œ
codeBlock :: Parser MarkdownBlock
codeBlock = do
  _ <- string "```"
  lang <- manyTill anySingle newline
  code <- manyTill anySingle (string "```")
  _ <- newline
  return $ CodeBlock lang code

-- ๋ชฉ๋ก ํŒŒ์„œ
bulletList :: Parser MarkdownBlock
bulletList = BulletList <$> some bulletItem
  where
    bulletItem = do
      _ <- char '-' <|> char '*'
      _ <- char ' '
      item <- manyTill anySingle newline
      return item

-- ์ „์ฒด ๋งˆํฌ๋‹ค์šด ํŒŒ์„œ
markdown :: Parser [MarkdownBlock]
markdown = many $
      try heading
  <|> try codeBlock
  <|> try bulletList
  <|> paragraph
์˜ค ์ด๊ฑฐ ์žฌ๋Šฅ๋„ท ๊ฐ™์€ ํ”Œ๋žซํผ์—์„œ ๋งˆํฌ๋‹ค์šด ์—๋””ํ„ฐ ๋งŒ๋“ค ๋•Œ๋„ ์“ธ ์ˆ˜ ์žˆ๊ฒ ๋‹ค!

๋งž์•„! ์žฌ๋Šฅ๋„ท์ฒ˜๋Ÿผ ์ฝ˜ํ…์ธ ๋ฅผ ๋‹ค๋ฃจ๋Š” ํ”Œ๋žซํผ์—์„œ ๋งˆํฌ๋‹ค์šด ํŒŒ์„œ๋‚˜ ์ปค์Šคํ…€ ํ…์ŠคํŠธ ํฌ๋งท ํŒŒ์„œ ๋งŒ๋“ค ๋•Œ ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ๊ฐ€ ๋”ฑ์ด์•ผ. ์œ ์ง€๋ณด์ˆ˜๋„ ์‰ฝ๊ณ  ํ™•์žฅ๋„ ํŽธํ•˜๊ฑฐ๋“  ใ…‹ใ…‹

โš–๏ธ ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ vs ๋‹ค๋ฅธ ํŒŒ์‹ฑ ๋ฐฉ๋ฒ•

ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ๊ฐ€ ํ•ญ์ƒ ์ตœ์„ ์€ ์•„๋‹ˆ์•ผ. ์ƒํ™ฉ์— ๋”ฐ๋ผ ๋‹ค๋ฅธ ๋ฐฉ๋ฒ•์ด ๋” ๋‚˜์„ ์ˆ˜๋„ ์žˆ์–ด. ๋น„๊ตํ•ด๋ณด์ž!

๋ฐฉ๋ฒ• ์žฅ์  ๋‹จ์  ์ ํ•ฉํ•œ ์ƒํ™ฉ
ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ ์ฝ”๋“œ = ๋ฌธ๋ฒ•, ์œ ์ง€๋ณด์ˆ˜ ์‰ฌ์›€, ํƒ€์ž… ์•ˆ์ „ ์„ฑ๋Šฅ์ด ํŒŒ์„œ ์ œ๋„ˆ๋ ˆ์ดํ„ฐ๋ณด๋‹ค ๋‚ฎ์„ ์ˆ˜ ์žˆ์Œ ๋ณต์žกํ•œ ๋ฌธ๋ฒ•, ๋น ๋ฅธ ๊ฐœ๋ฐœ
ํŒŒ์„œ ์ œ๋„ˆ๋ ˆ์ดํ„ฐ (ANTLR, yacc) ์„ฑ๋Šฅ ์ตœ์ ํ™”, ๋Œ€๊ทœ๋ชจ ์–ธ์–ด์— ์ ํ•ฉ ๋ณ„๋„ ๋„๊ตฌ ํ•„์š”, ํ•™์Šต ๊ณก์„  ํ”„๋กœ๋•์…˜ ์ปดํŒŒ์ผ๋Ÿฌ
์†์œผ๋กœ ์ง  ์žฌ๊ท€ ํ•˜๊ฐ• ์ตœ๊ณ  ์„ฑ๋Šฅ, ์™„์ „ํ•œ ์ œ์–ด ์ฝ”๋“œ ๋งŽ์Œ, ์œ ์ง€๋ณด์ˆ˜ ์–ด๋ ค์›€ ์„ฑ๋Šฅ ๊ทนํ•œ ์ตœ์ ํ™”
์ •๊ทœ์‹ ๊ฐ„๋‹จํ•œ ํŒจํ„ด์— ๋น ๋ฆ„ ์ค‘์ฒฉ ๊ตฌ์กฐ ์ฒ˜๋ฆฌ ๋ถˆ๊ฐ€ ๋‹จ์ˆœ ํ…์ŠคํŠธ ๋งค์นญ
๐Ÿ’ก ์–ธ์ œ ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ๋ฅผ ์จ์•ผ ํ• ๊นŒ? - ๋ฌธ๋ฒ•์ด ๋ณต์žกํ•˜๊ณ  ์ž์ฃผ ๋ฐ”๋€” ๋•Œ
- ํŒ€์›๋“ค์ด ๋ฌธ๋ฒ•์„ ์ดํ•ดํ•ด์•ผ ํ•  ๋•Œ (์ฝ”๋“œ๊ฐ€ ๋ฌธ๋ฒ• ๋ช…์„ธ์ฒ˜๋Ÿผ ์ฝํžˆ๋‹ˆ๊นŒ)
- ๋น ๋ฅธ ํ”„๋กœํ† ํƒ€์ดํ•‘์ด ํ•„์š”ํ•  ๋•Œ
- Haskell์ด๋‚˜ Scala, F# ๊ฐ™์€ ํ•จ์ˆ˜ํ˜• ์–ธ์–ด๋ฅผ ์“ธ ๋•Œ

๐ŸŽ“ ๊ณ ๊ธ‰ ๊ธฐ๋ฒ•: ๋” ๋‚˜์•„๊ฐ€๊ธฐ
Phantom Types๋กœ ํƒ€์ž… ์•ˆ์ „ํ•œ ํŒŒ์„œ

ํŒŒ์„œ์— ํŒฌํ…€ ํƒ€์ž…์„ ์ ์šฉํ•˜๋ฉด ์ปดํŒŒ์ผ ํƒ€์ž„์— ๋” ๋งŽ์€ ์˜ค๋ฅ˜๋ฅผ ์žก์„ ์ˆ˜ ์žˆ์–ด:

Haskell - ํŒฌํ…€ ํƒ€์ž…
-- ํŒŒ์„œ๊ฐ€ ๊ณต๋ฐฑ์„ ์ฒ˜๋ฆฌํ–ˆ๋Š”์ง€ ํƒ€์ž…์œผ๋กœ ํ‘œํ˜„
data Trimmed
data Untrimmed

newtype Parser s a = Parser { runParser :: String -> Maybe (a, String) }

-- ๊ณต๋ฐฑ ์ฒ˜๋ฆฌ๋œ ํŒŒ์„œ๋งŒ ์กฐํ•ฉ ๊ฐ€๋Šฅํ•˜๋„๋ก ์ œํ•œ
combine :: Parser Trimmed a -> Parser Trimmed b -> Parser Trimmed (a, b)
combine pa pb = ...

-- ๊ณต๋ฐฑ ์ฒ˜๋ฆฌ ํ•จ์ˆ˜
trim :: Parser Untrimmed a -> Parser Trimmed a
trim (Parser p) = Parser $ \input ->
  p (dropWhile isSpace input)
Generalized Parsing: ๋ฌธ์ž์—ด ์™ธ ๋‹ค๋ฅธ ์ŠคํŠธ๋ฆผ ํŒŒ์‹ฑ
Haskell - ์ผ๋ฐ˜ํ™”๋œ ํŒŒ์„œ
-- Megaparsec์€ ์ŠคํŠธ๋ฆผ ํƒ€์ž…์„ ์ถ”์ƒํ™”ํ•ด์„œ
-- ๋ฌธ์ž์—ด๋ฟ๋งŒ ์•„๋‹ˆ๋ผ ํ† ํฐ ์ŠคํŠธ๋ฆผ๋„ ํŒŒ์‹ฑ ๊ฐ€๋Šฅ!
type TokenParser = Parsec Void [Token]

data Token
  = TNumber Int
  | TPlus
  | TMinus
  | TLParen
  | TRParen
  deriving (Show, Eq, Ord)

-- ํ† ํฐ ์ŠคํŠธ๋ฆผ์„ ํŒŒ์‹ฑํ•˜๋Š” ํŒŒ์„œ
tokenExpr :: TokenParser Int
tokenExpr = ...

-- ์ด๋ ‡๊ฒŒ ํ•˜๋ฉด ๋ ‰์„œ + ํŒŒ์„œ๋ฅผ ๋ถ„๋ฆฌํ•  ์ˆ˜ ์žˆ์–ด
-- ๋ ‰์„œ: String -> [Token]
-- ํŒŒ์„œ: [Token] -> AST
Incremental Parsing (์ฆ๋ถ„ ํŒŒ์‹ฑ)

์—๋””ํ„ฐ๋‚˜ IDE์ฒ˜๋Ÿผ ์‹ค์‹œ๊ฐ„์œผ๋กœ ํŒŒ์‹ฑํ•ด์•ผ ํ•  ๋•Œ๋Š” ์ฆ๋ถ„ ํŒŒ์‹ฑ์ด ํ•„์š”ํ•ด. Attoparsec์€ ์ด๋ฅผ ์ง€์›ํ•ด:

Haskell - ์ฆ๋ถ„ ํŒŒ์‹ฑ
import qualified Data.Attoparsec.ByteString as A

-- ์ฆ๋ถ„ ํŒŒ์‹ฑ: ๋ฐ์ดํ„ฐ๋ฅผ ์กฐ๊ธˆ์”ฉ ๋ฐ›์•„์„œ ํŒŒ์‹ฑ
incrementalParse :: IO ()
incrementalParse = do
  let initialResult = A.parse jsonValue ""
  -- ๋ฐ์ดํ„ฐ๋ฅผ ์กฐ๊ธˆ์”ฉ ํ”ผ๋“œ
  let result1 = A.feed initialResult "{\"key\":"
  let result2 = A.feed result1 "\"value\"}"
  -- ํŒŒ์‹ฑ ์™„๋ฃŒ
  case A.feed result2 "" of
    A.Done _ val -> print val
    A.Fail _ _ err -> putStrLn $ "์—๋Ÿฌ: " ++ err
    A.Partial _ -> putStrLn "๋ฐ์ดํ„ฐ ๋ถ€์กฑ"
โš ๏ธ Left Recursion ์ฃผ์˜! ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ๋Š” ๊ธฐ๋ณธ์ ์œผ๋กœ ์ขŒ์žฌ๊ท€(Left Recursion)๋ฅผ ์ฒ˜๋ฆฌํ•˜์ง€ ๋ชปํ•ด.
์˜ˆ: expr ::= expr '+' term | term ์ด๋Ÿฐ ๋ฌธ๋ฒ•์€ ๋ฌดํ•œ ๋ฃจํ”„์— ๋น ์ ธ!
chainl1 ๊ฐ™์€ ์ปด๋น„๋„ค์ดํ„ฐ๋ฅผ ์จ์„œ ์ขŒ์žฌ๊ท€๋ฅผ ์šฐ์žฌ๊ท€๋กœ ๋ณ€ํ™˜ํ•ด์•ผ ํ•ด.

๐Ÿ—บ๏ธ ํ•™์Šต ๋กœ๋“œ๋งต

ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ๋ฅผ ๋งˆ์Šคํ„ฐํ•˜๊ณ  ์‹ถ๋‹ค๋ฉด ์ด ์ˆœ์„œ๋กœ ๊ณต๋ถ€ํ•ด๋ด!

ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ ํ•™์Šต ๋กœ๋“œ๋งต 1๋‹จ๊ณ„: Haskell ๊ธฐ์ดˆ ํƒ€์ž…, ํ•จ์ˆ˜, ํŒจํ„ด ๋งค์นญ Maybe, List ๋ชจ๋‚˜๋“œ 2๋‹จ๊ณ„: ํƒ€์ž… ํด๋ž˜์Šค Functor, Applicative Monad, Alternative 3๋‹จ๊ณ„: ํŒŒ์„œ ์ง์ ‘ ๊ตฌํ˜„ satisfy, char, digit many, choice ๊ตฌํ˜„ 4๋‹จ๊ณ„: Parsec/Megaparsec ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ ํ•™์Šต ์—๋Ÿฌ ์ฒ˜๋ฆฌ, ์œ„์น˜ ์ถ”์  5๋‹จ๊ณ„: ์‹ค์ „ ํ”„๋กœ์ ํŠธ JSON, CSV ํŒŒ์„œ ๊ฐ„๋‹จํ•œ ์–ธ์–ด ์ธํ„ฐํ”„๋ฆฌํ„ฐ 6๋‹จ๊ณ„: ๊ณ ๊ธ‰ ๊ธฐ๋ฒ• ์„ฑ๋Šฅ ์ตœ์ ํ™” ์ฆ๋ถ„ ํŒŒ์‹ฑ, DSL ์„ค๊ณ„ ๐Ÿ“š ์ถ”์ฒœ ํ•™์Šต ์ž๋ฃŒ โ€ข "Programming in Haskell" (Graham Hutton) โ€ข Megaparsec ๊ณต์‹ ํŠœํ† ๋ฆฌ์–ผ (hackage.haskell.org) โ€ข "Write You a Haskell" (Stephen Diehl) ์žฌ๋Šฅ๋„ท์—์„œ๋„ Haskell ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ ๊ด€๋ จ ํŠœํ„ฐ๋ง์„ ์ฐพ์•„๋ณผ ์ˆ˜ ์žˆ์–ด! ํ•จ์ˆ˜ํ˜• ํ”„๋กœ๊ทธ๋ž˜๋ฐ ์ „๋ฌธ๊ฐ€๋“ค์˜ ๋„์›€์„ ๋ฐ›์•„๋ณด๋Š” ๊ฒƒ๋„ ์ข‹์€ ๋ฐฉ๋ฒ•์ด์•ผ ๐Ÿ˜Š
์ถ”์ฒœ ์—ฐ์Šต ํ”„๋กœ์ ํŠธ๋“ค
๐Ÿ‹๏ธ ์‹ค๋ ฅ ํ‚ค์šฐ๊ธฐ ์—ฐ์Šต ํ”„๋กœ์ ํŠธ
  • 1 ๊ณ„์‚ฐ๊ธฐ ํŒŒ์„œ: ์‚ฌ์น™์—ฐ์‚ฐ + ๊ด„ํ˜ธ + ๋ณ€์ˆ˜ ์ง€์› (์ด ๊ธ€์—์„œ ๋‹ค๋ฃฌ ๋‚ด์šฉ!)
  • 2 CSV ํŒŒ์„œ: ์‰ผํ‘œ, ๋”ฐ์˜ดํ‘œ, ์ด์Šค์ผ€์ดํ”„ ์ฒ˜๋ฆฌ
  • 3 INI ํŒŒ์ผ ํŒŒ์„œ: [์„น์…˜], ํ‚ค=๊ฐ’ ํ˜•์‹
  • 4 ๊ฐ„๋‹จํ•œ Lisp ์ธํ„ฐํ”„๋ฆฌํ„ฐ: S-ํ‘œํ˜„์‹ ํŒŒ์‹ฑ + ํ‰๊ฐ€
  • 5 SQL SELECT ํŒŒ์„œ: SELECT, FROM, WHERE, ORDER BY
  • 6 ๋งˆํฌ๋‹ค์šด ํŒŒ์„œ: ์ œ๋ชฉ, ๊ตต๊ฒŒ, ๊ธฐ์šธ์ž„, ๋งํฌ, ์ฝ”๋“œ ๋ธ”๋ก
  • 7 ๋ฏธ๋‹ˆ ํ”„๋กœ๊ทธ๋ž˜๋ฐ ์–ธ์–ด: ๋ณ€์ˆ˜, ํ•จ์ˆ˜, ์กฐ๊ฑด๋ฌธ, ๋ฐ˜๋ณต๋ฌธ

๐ŸŽ‰ ๋งˆ๋ฌด๋ฆฌ: ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ์˜ ์ฒ ํ•™

์ž, ์—ฌ๊ธฐ๊นŒ์ง€ ์™”์œผ๋ฉด ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ์˜ ํ•ต์‹ฌ์„ ๋‹ค ์ดํ•ดํ•œ ๊ฑฐ์•ผ! ๋งˆ์ง€๋ง‰์œผ๋กœ ์ด ๊ธฐ๋ฒ•์˜ ์ฒ ํ•™์  ์˜๋ฏธ๋ฅผ ์งš์–ด๋ณด์ž.

๐ŸŒŸ ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ๊ฐ€ ๊ฐ€๋ฅด์ณ์ฃผ๋Š” ๊ฒƒ ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ๋Š” ๋‹จ์ˆœํžˆ "ํŒŒ์„œ๋ฅผ ๋งŒ๋“œ๋Š” ๊ธฐ๋ฒ•"์ด ์•„๋‹ˆ์•ผ.
์ด๊ฑด ํ•จ์ˆ˜ํ˜• ํ”„๋กœ๊ทธ๋ž˜๋ฐ์˜ ํ•ต์‹ฌ ์ฒ ํ•™์„ ๋ณด์—ฌ์ฃผ๋Š” ์™„๋ฒฝํ•œ ์˜ˆ์ œ์•ผ:

"์ž‘๊ณ  ๋‹จ์ˆœํ•œ ๊ฒƒ๋“ค์„ ์กฐํ•ฉํ•ด์„œ ๋ณต์žกํ•œ ๊ฒƒ์„ ๋งŒ๋“ ๋‹ค."

satisfy ํ•˜๋‚˜๋กœ ์‹œ์ž‘ํ•ด์„œ, char, digit, many, choice๋ฅผ ๊ฑฐ์ณ,
๊ฒฐ๊ตญ ์™„์ „ํ•œ ํ”„๋กœ๊ทธ๋ž˜๋ฐ ์–ธ์–ด ํŒŒ์„œ๊นŒ์ง€ ๋งŒ๋“ค ์ˆ˜ ์žˆ์–ด.
์ด๊ฒŒ ๋ฐ”๋กœ ํ•ฉ์„ฑ ๊ฐ€๋Šฅ์„ฑ(Composability)์˜ ํž˜์ด์•ผ.
์˜ค ์ง„์งœ ๋ ˆ๊ณ  ๋ธ”๋ก ๊ฐ™์€ ๊ฑฐ์˜€๋„ค ใ…‹ใ…‹ใ…‹ ์ฒ˜์Œ์— ๋งํ•œ ๊ฑฐ ์ด์ œ ์ดํ•ด๋จ!

ใ…‹ใ…‹ใ…‹ ๋งž์ง€! ๊ทธ๋ฆฌ๊ณ  ์ด ๊ฐœ๋…์€ Haskell์—๋งŒ ๊ตญํ•œ๋œ ๊ฒŒ ์•„๋‹ˆ์•ผ. Scala์˜ FastParse, F#์˜ FParsec, Rust์˜ nom, Python์˜ Parsita ๋“ฑ ๋‹ค๋ฅธ ์–ธ์–ด์—๋„ ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ๊ฐ€ ์žˆ์–ด!

์˜ค ๊ทธ๋Ÿผ Haskell๋กœ ๊ฐœ๋… ์ตํžˆ๋ฉด ๋‹ค๋ฅธ ์–ธ์–ด์—์„œ๋„ ์“ธ ์ˆ˜ ์žˆ๊ฒ ๋‹ค!

์ •ํ™•ํ•ด! Haskell์ด ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ์˜ ์›์กฐ์ด์ž ๊ฐ€์žฅ ์šฐ์•„ํ•˜๊ฒŒ ํ‘œํ˜„๋˜๋Š” ์–ธ์–ด๋ผ์„œ, Haskell๋กœ ๋ฐฐ์šฐ๋ฉด ๋‹ค๋ฅธ ์–ธ์–ด ๋ฒ„์ „์€ ํ›จ์”ฌ ์‰ฝ๊ฒŒ ์ดํ•ด๋ผ ๐Ÿ˜Ž
๐Ÿ“Š ํ•ต์‹ฌ ๋‚ด์šฉ ์š”์•ฝ ํŒŒ์„œ ํƒ€์ž… Parser a = String -> Maybe (a, String)

Functor ํŒŒ์‹ฑ ๊ฒฐ๊ณผ๋ฅผ ํ•จ์ˆ˜๋กœ ๋ณ€ํ™˜

Applicative ์—ฌ๋Ÿฌ ํŒŒ์„œ๋ฅผ ์ˆœ์„œ๋Œ€๋กœ ์ ์šฉํ•˜๊ณ  ๊ฒฐ๊ณผ ์กฐํ•ฉ

Monad ์ด์ „ ๊ฒฐ๊ณผ์— ๋”ฐ๋ผ ๋™์ ์œผ๋กœ ๋‹ค์Œ ํŒŒ์„œ ๊ฒฐ์ •

Alternative ํŒŒ์„œ A ์‹คํŒจ ์‹œ ํŒŒ์„œ B ์‹œ๋„

many/some ๋ฐ˜๋ณต ํŒŒ์‹ฑ

between/sepBy ๊ตฌ์กฐ์  ํŒŒ์‹ฑ

Megaparsec ์‹ค๋ฌด์šฉ ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ, ๊ฐ•๋ ฅํ•œ ์—๋Ÿฌ ๋ฉ”์‹œ์ง€

Attoparsec ์„ฑ๋Šฅ ์ตœ์ ํ™”์šฉ ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ

ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ๋Š” ์ฒ˜์Œ์—” ๋‚ฏ์„ค์–ด ๋ณด์—ฌ๋„, ํ•œ ๋ฒˆ ์ตํžˆ๋ฉด "์ด๊ฑธ ์™œ ์ด์ œ์•ผ ์•Œ์•˜์ง€?" ์‹ถ์€ ๊ธฐ๋ฒ•์ด์•ผ. ํŠนํžˆ Haskell์˜ ํƒ€์ž… ์‹œ์Šคํ…œ๊ณผ ๋งŒ๋‚˜๋ฉด ์ง„์งœ ๊ฐ•๋ ฅํ•œ ๋„๊ตฌ๊ฐ€ ๋ผ.

์žฌ๋Šฅ๋„ท์—์„œ Haskell์ด๋‚˜ ํ•จ์ˆ˜ํ˜• ํ”„๋กœ๊ทธ๋ž˜๋ฐ ๊ด€๋ จ ์žฌ๋Šฅ์„ ๊ฐ€์ง„ ๋ถ„๋“ค์„ ์ฐพ์•„๋ณด๋ฉด, ํŒŒ์„œ ์ปด๋น„๋„ค์ดํ„ฐ๋ฅผ ์ง์ ‘ ๊ฐ€๋ฅด์ณ์ค„ ์ˆ˜ ์žˆ๋Š” ์ „๋ฌธ๊ฐ€๋“ค๋„ ๋งŽ์ด ์žˆ์„ ๊ฑฐ์•ผ. ํ˜ผ์ž ๊ณต๋ถ€ํ•˜๋‹ค ๋ง‰ํžˆ๋ฉด ์ „๋ฌธ๊ฐ€์˜ ๋„์›€์„ ๋ฐ›๋Š” ๊ฒƒ๋„ ์ข‹์€ ๋ฐฉ๋ฒ•์ด์•ผ! ๐Ÿ’ช

์ž, ์ด์ œ ์ง์ ‘ ์ฝ”๋“œ๋ฅผ ์งœ๋ด. ์ด๋ก ๋งŒ ์ฝ์–ด์„œ๋Š” ์ ˆ๋Œ€ ์•ˆ ๋ผ ใ…‹ใ…‹ใ…‹ satisfy๋ถ€ํ„ฐ ์‹œ์ž‘ํ•ด์„œ ํ•˜๋‚˜์”ฉ ์Œ“์•„๊ฐ€๋‹ค ๋ณด๋ฉด ์–ด๋А์ƒˆ ์™„์ „ํ•œ ํŒŒ์„œ๋ฅผ ๋งŒ๋“ค๊ณ  ์žˆ๋Š” ์ž์‹ ์„ ๋ฐœ๊ฒฌํ•˜๊ฒŒ ๋  ๊ฑฐ์•ผ! ๐Ÿš€

๋Œ“๊ธ€ ์ž‘์„ฑ

์ด ๊ธ€์— ๋Œ€ํ•œ ์—ฌ๋Ÿฌ๋ถ„์˜ ์ƒ๊ฐ์„ ๋“ค๋ ค์ฃผ์„ธ์š”

๋Œ“๊ธ€ 0
๋Œ“๊ธ€์„ ๋ถˆ๋Ÿฌ์˜ค๋Š” ์ค‘์ž…๋‹ˆ๋‹ค.

์•„์ง ๋Œ“๊ธ€์ด ์—†์Šต๋‹ˆ๋‹ค.