Parser란 무엇일까요? 아래 정의와 같이 한 text를 구조에 따라 분석하는 프로그램을 의미합니다. 흔히 우리는 문장을 나눌때 사용합니다.

A parser is a program that analyses a piece of text to determine its syntactic structure.

The Parser Type

Haskell에서의 Parser를 알아봅시다.

type Parser = String -> Tree  

Haskell에서 Parser는 한 함수로 String을 입력받아 tree형태를 돌려줍니다. 하지만, Parser가 꼭 입력받은 String 전체를 필요하지 않을 수 있습니다. 따라서 사용하지 않은 입력값을 돌려줄 수도 있습니다.

type Parser = String -> (Tree, String)  

또한, 아무 것도 없는 것을 포함하여 다양한 방법으로 Parsing 될 수 있어 다음과 같이 list를 돌려줄 수도 있습니다.

type Parser = String -> [(Tree, String)]  

마지막으로 Parser가 필히 tree를 돌려주는 것은 아닙니다. 따라서 any type을 이용하여 표현할 수 있습니다.

type Parser a = String -> [(a, String)]  

위와 같은 경우에는 Tree를 돌려줄지 무엇을 돌려줄지 신경쓰지 않겠다는 의미와 같습니다.

하지만, 저희는 간단하게 하기 위해 실패할 경우 비어있는 list를 돌려주고, 성공할 경우 singleton list을 돌려주는 것만 고려하겠습니다. (물론 이 강의 이후 any type 등을 적용한 Parser 를 만들 수도 있습니다.)

Basic Parsers

복잡한 Parser 를 만들기 이전에 간단한 Parser를 만들어 봅시다.

item :: Parser Char  
item = \inp -> case inp of  
                []     -> []
                (x:xs) -> [(x,xs)]

Parser 인 item 은 단순히 입력값이 비어있을 경우 빈 list를 돌려주고, (x:xs) 형태의 경우 (x,xs) 형태의 singleton list를 돌려줍니다.

다음 failure Parser는 항상 실패하게 됩니다.

failure :: Parser a  
failure = \inp -> []  

반면 다음 return v 항상 성공하게 됩니다. 결과를 주기위해 입력값 v 가 필요하며, 입력값을 쓰지 않은체 결과를 돌려줍니다.

return   :: a -> Parser a  
return v = \inp -> [(v,inp)]  

그럼 우리는 두개 Parser를 어떻게 조합하여 결과를 얻을 수 있을까요? 성공했을 경우는 앞서 말씀드린 return 을, 실패했을 경우에는 failure 를 이용하고 싶을 경우에는 어떻게 할지 알아봅시다.

(+++)  :: Parser a -> Parser a -> Parser a
p +++ q = \inp -> case p inp of  
                   []        -> parse q inp
                   [(v,out)] -> [(v,out)]

위와 같이 두개의 Parser 를 입력받고, 만일 빈 list일 경우 실패하는 경우로 q 에 대해서 다시 parse 를 실행하고, 아닌 경우(p 성공 시) singleton list를 돌려줍니다.

parse :: Parser a -> String -> [(a,String)]  
parse p inp = p inp  

위의 parse 는 단순히 입력으로 받은 Parser p 를 실행시켜 결과를 얻습니다.

위의 내용들을 종합하면 다음과 같은 test 결과를 볼 수 있습니다.

> parse item ""
[]

> parse item "abc"
[('a',"bc")]

> parse failure "abc"
[]  -- always fail

> parse (return 1) "abc"
[(1,"abc")]

> parse (item +++ return 'd') "abc"
[('a',"bc")] -- parser item successfully parse "abc", so not (return 'd') is not executed

> parse (failure +++ return 'd') "abc"
[('d',"abc")]

• Parsing 라이브러리 파일은 Haskell 홈페이지에서 구할 수 있습니다.
• 기술적인 이유로, 위의 예제 중 첫번째 failure 예제는 type때문에 error를 발생합니다. 하지만, 다른 경우에서는 발생하지 않습니다.
• Parser 의 type은 monad입니다. 여기서 monad는 매우 다양한 종류의 계산 모델링을 위해 사용되는 수학 구조입니다. (다음에 더 자세히 다루도록 하겠습니다. Parser 를 공부하는데 큰 영향을 주지 않습니다.)

Sequencing

Sequencing 은 앞서 배웠던 Parser 들을 하나로 구성된 Parser 를 말합니다. 한 예를 봅시다.

p :: Parser (Char, Char)  
p = do x <- item  
       item
       y <- item
       return (x,y) 

이를 위해 위와같이 do 를 사용하는데, monad가 가지는 이점 중 하나 입니다. 이를 통해 sequential composition parser 를 깔끔하게 구현할 수 있습니다.

Note

• 사용된 모든 Parser 는 layout rule에 따라 작성되어야 합니다. (do 이후 간격(space)이 동일하게 적용되어 있어야합니다.)
• 위 예에서 가운데 item 과 같이 이름이 지정되지 않은 Parser 는 기본적으로 사용되지 않습니다.
• 마지막에 적용된 Parser 가 돌려주는 값이 전체 Sequence 가 돌려주는 값이 됩니다.
• 만일 Sequence 도중 어떠한 Parser 에서 실패할 경우, 결과는 항상 실패하게 됩니다.

> parse p "abcdef"
[(('a','c'),"def")]

> parse p "ab"
[]

• do 는 Parser 에만 적용가능한 것이 아닌, 어떠한 monadic type에도 사용할 수 있습니다.

Derived Primitives

predicate(번역: 술부)를 만족하는 문자를 parsing할 수 있습니다.

sat  :: (Char -> Bool) -> Parser Char  
sat p = do x <- item  
           if p x then
              return x
           else
              failure

위를 설명하면, item 을 이용하여 parsing한 값 x 에 대하여 p 를 만족할 경우 return x 를 실행하고, 아닐 경우 failure 를 실행하게 됩니다.

이를 이용하여 몇가지 예에 적용해 봅시다.

• digit과 특정한 문자들을 parsing하는 경우

digit :: Parser Char  
digit  = sat isDigit

char  :: Char -> Parser Char  
char x = sat (x ==)  

char 의 경우 앞서 배웠던 section을 이용한 것을 볼 수 있습니다. 결과적으로 특정한 문자를 parsing해 오는 결과를 볼 수 있습니다.

• 한 Parser 를 0번 또는 그 이상 적용할 수 있습니다.

many  :: Parser a -> Parser [a]  
many p = many1 p +++ return []  

many1  :: Parser a -> Parser [a]  
many1 p = do v  <- p  
             vs <- many p
             return (v:vs)

위와 같이 do 와 재귀를 이용하여 여러번 parsing하는 것을 볼 수 있습니다.

• 다음과 같이 문자열을 parsing 할 수 있습니다.

string       :: String -> Parser String  
string []     = []  
string (x:xs) = do char x  
                   string xs
                   return (x:xs)

조금 더 실제 상황과 어울리는 예제를 보겠습니다. 문자열로부터 하나씩 문자를 뽑아 parsing을 하는 Parser 입니다.

p :: Parser String  
p  = do char '['  
        d  <- digit
        ds <- many (do char ','
                       digit)
        char ']'
        return (d:ds)

> parse p "[1,2,3,4]"
[("1234","")]

> parse p "[1,2,3,4"
[]

물론 이 또한 정말 간단한 Parser 입니다. 실제 라이브러리는 error로부터 다양한 해결 방법을 제공합니다.

Artithmetic Expressions

+ 와 * 를 괄호안에 함께 사용한 expression 형태를 봅시다. 먼저 다음을 가정합니다.

• * 와 + 는 오른쪽에 있는 것과 연관되어 있습니다.
• + 보다 * 가 높은 우선순위를 갖습니다.

그럼 우리가 앞서 배웠던 Parser 들을 이용해서 어떠한 expression을 표현할 지 알아봅시다.

expr   -> term '+' expr | term  
term   -> factor '*' term | factor  
factor -> digit | '(' expr ')'  
digit  -> '0' | '1' | ... |'9'  

위와 같은 경우 서로 여러가지 expression이 엉켜있는 것을 볼 수 있습니다. 하지만 효율성을 위해 다음과 같이 인수분해(factorize)하는 것은 중요합니다.

expr -> term ('+' expr | [])  
term -> factor ('*' term | [])  

이러한 expression을 해석하는 Parser 를 만들면 다음과 같습니다.

expr :: Parser Int  
expr  = do t <- term  
           do char '+'
              e <- expr
              return (t + e)
           +++ return t

term :: Parser Int  
term  = do f <- factor  
           do char '*'
              t <- term 
              return (f * t)
           +++ return f

factor :: Parser Int  
factor  = do d <- digit  
             return (digitToInt d)
          +++ do char '('
                 e <- expr 
                 char ')'
                 return e

이를 통해 우리가 만약 다음과 같이 eval 을 정의한다면 결과를 Parser 를 통해 얻을 수 있습니다.

eval   :: String -> Int  
eval xs = fst (head (parse expr xs))  

> eval "2*3+4"
10

> eval "2*(3+4)"
14  

간략히 xs 를 expr 을 이용하여 parsing을 하면 singleton list를 돌려주게 되어 이중 head와 fst element를 받아와 결과를 주게 됩니다.

Reference

• Introduction to Functional Programming