Parser in Haskell

Programming/Haskell 2015.05.18 21:04


1.What is a Parser ?

a + b * c 가 있을때 a , b , c 를 leaf 로 하고 연산자 (+, *) 를 parent 로 하는 트리 구조와 같이 나타낼 수 있는, 흔히 알고 있는 문자열을 구분할 수 있는 parser.

The Parser Type

type Parser = String -> Tree
type Parser = String -> (Tree, String) --not complete
type Parser = String -> [(Tree, String)] --list of result 
    can be empty - 하스켈에서는 리스트를 주로 이용. 다른 언어에서 많이 사용하는 Maybe 와 같이 비어 있는 타입과 값이 있는 경우를 구분하는 타입을 사용해도. 리스트 연산자들을 사용하기 편하므로 리스트를 쓰는게 관용 (idiom)
type Parser a = String -> [(a, String)] --We don't care Tree or not

문제를 간단하게 하기 위해, 성공한 경우에는 singleton list 를 ex. ['a', "hello"], 실패한 경우에는 빈 리스트를 리턴하는 경우만을 고려.

Basic Parsers

더 복잡한 Parser 구현을 위해 먼저 단순한 부분부터. 단일 문자 추출

item :: Parser Char
item = \inp -> case inp of
                []     ->  []
                (x:xs) ->  [(x, xs)]
-- 문자열 inp 를 받아 비어있는 경우는 빈리스트를, 데이터가 있는 경우는 첫번째 문자열과 나머지 문자열을 pair 로
-- 좌변에 패턴매칭을 사용하지 않아 두개 절을 사용하는 대신, 하나의 람다 표현식에 case 표현식을 사용하여 내부에서 패턴매칭을 사용함 -> 저자는 싱글 톤을 리턴하거나 빈 리스트를 리턴하는 함수임이 잘 나타나 있어 이런 형태를 좋아한다함

항상 실패하는 parser

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

항상 성공하는 parser

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

parser p 가 성공한다면 parser p 와 같이 동작하고, 그렇지 않다면 parser q 와 같이 동작하는 parser (두 parser 를 받아 모두 시도해보는 parser)

-- 같은 타입을 parsing 하는 parser
(+++) :: Parser a -> Parser a -> Parser a     
p +++ q = \inp -> case p inp of
                    [] -> parse q inp
                    [(v, out)] -> [(v, out)]

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

monads 그냥 특정 operation 이 있는 타입이라고 생각하라 함


2. Sequencing

parser 가 monad 이게 하는 다른 연산자 - (parser 의 sequence라 한다) - 를 살펴본다.

하나가 실패하면 다음을 시도하는것이 아니라 순차적으로 결합하고자 함.

이를 위해 do - syntax 라고 불리는 문법을 활용한다. (do 문법을 사용할 수 있는것은 모나드를 사용하는 장점 중에 하나이다.)

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

parser 의 sequence 중 어느 하나라도 실패하면, 모두 실패한다.

Derived Primitives

predicate 를 만족하는 문자를 parsing 함

sat :: (Char -> Bool) -> Parser Char
-- 어떤 타입을 다른 타입을 통해 그 타입이 내포한 타입 시그니쳐를 표현 할 수 있다. 
-- sat :: (Char -> Bool) -> String -> [(a, String)]
sat p = do x <- item
           if p x then return x
           else failure

digit parsers

digit :: Parser Char
digit = sat isDigit

specific character parser

char :: Char -> Parser Char
char x = sat (x ==)
-- haskell 에서 sectioning (아마도 partial applying 을 지칭하는 것인듯) 을 하는 좋은 예
-- x 가 두군데 있으니 pointfree 스타일로 구성해 볼 수도 있다. 

parser 를 0 번 이상 적용하는 함수

many :: Parser a -> Parser [a]
-- String -> [(a, String)] -> String -> [([a], String)]
-- a 타입 파서를 받아서 a 의 리스트의 파서를 뱉는다 ?
many p = many1 p +++ return []
-- 먼저 최소한 한번의 Parser, p 를 적용해 보고 만약 실패하면 빈리스트를 리턴한다. 

many1 :: Parser a -> Parser [a]
many1 p = do v  <- p
             vs <- many p
             return (v:vs)
-- p 가 성공하면 다시 many 를 호출, 다시 parsing 을 시도한다. 
-- 성공한 파싱 결과들은 모두 v:vs 로 인해 append 된다.
-- 실패하는 순간 빈리스트가 append 되는것으로 종료. 
-- 왜, [a] 가 아니라 Parser [a] 인가 ? 
-- v <- p 이기 때문에..(결국 이녀석은 [a] 를 parsing 하는 함수를 리턴한다.)

parsing a specific string of characters

string :: String -> Parser String
string [] = return []
string (x:xs) = do char x
                   string xs
                   return (x:xs)
-- do sequence 에서 실패하면 이 함수 전체가 실패하므로, char 문자열에 반복적으로 적용하는 것으로 문자열을 파싱할 수 있다. 
-- 착각할 수 있는 부분이, 여기서 x 와 xs 는 파싱하고자하는 specific 문자열이지, 파싱 대상이 되는 문자열 ( input ) 이 아니다. 
-- Prefix 만을 파싱한다.

Example

1. parser that consumes a list of one or more digits from a string

p :: Parser String
p = do char '['
        d <- digit
        ds <- many (do char ','
                       digit)
        char ']'
        return (d:ds)
-- '[' 와 첫 번째 숫자를 파싱하고난 후에는 ',' 와 숫자로 이루어진 한개 이상의 문자를 파싱해야한다. 
-- 여기서 주목해야할 것은, many 의 인자 Parser a 에 다시 do 로 sequence parser 를 넣었다는 것이다. (익숙치 않아 어려웠다.)

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

3. Arithmetic Expressions

괄호를 사용한 수학식을 생각해보자.

표현식 문법 정의

expr -> term '+' expr | term
term -> factor '*' term | factor
factor -> digit | '(' expr ')'
digit -> '0' | '1' | ... | '9'
  • expr : term + expr 혹은 term - 즉, 0개 이상의 + 로 엮은 식
  • term : factor * term 혹은 factor - 즉, 0 개 이상의 * 로 엮은 식
  • factor : 숫자 혹은 (expr) - 단일 숫자 혹은 괄호로 엮은 식
  • digit : 0 ~ 9 - 수

massage to simpler definition

expr -> term ('+' expr | ɛ)
term -> factor ('*' term | ɛ)

여기서 엡실론 (ɛ) 은 어떤 것도 parsing 못하는 empty 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 :: String -> Int
eval xs = fst (head (parse expr xs))

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


저작자 표시 비영리 변경 금지
신고

'Programming > Haskell' 카테고리의 다른 글

IO Type  (0) 2015.05.20
Parser in Haskell  (0) 2015.05.18
Parser 의 bind  (0) 2015.05.15

Parser 의 bind

Programming/Haskell 2015.05.15 18:28

결론부터 이야기하자면, 잘 모르겠다. 

잘 모르겠으나 최대한 이해해 보려고 하는 차원에서 조금씩 뜯어보아 정리했다. 


여기서 bind ( >>= ) 는 시그니쳐를 풀어보면 a 타입의 parser 를 첫번째 인자로, a 타입을 인자로 해서 b 타입의 parser 로 변환하는 함수를 두번째 인자로해서 b 타입의 parser 를 리턴한다. 


정의를 살펴보면, .parse p inp 의 파싱이 성공한 경우 그 결과에 f 를 적용하여 Parser b 타입으로 ( 즉, b 타입을 파싱할 수 있는 함수 ) 변경하고, 이를 out 에 적용한다. ( 즉, out 으로부터 b 타입의 파싱을 시도한다 )


저작자 표시 비영리 변경 금지
신고

'Programming > Haskell' 카테고리의 다른 글

IO Type  (0) 2015.05.20
Parser in Haskell  (0) 2015.05.18
Parser 의 bind  (0) 2015.05.15

Daytime.2 - A synchronous TCP daytime server

Programming/Boost asio 2015.04.19 13:05

다음에 기반함

http://www.boost.org/doc/libs/1_57_0/doc/html/boost_asio/tutorial/tutdaytime2.html


이번엔 TCP asio 를 사용하여 어떻게 서버 응용프로그램을 구현할 수 있는지 살펴본다.

#include <ctime>
#include <iostream>
#include <string>
#include <boost/asio.hpp>

using boost::asio::ip::tcp;


클라이언트로 다시 보내줄 문자열을 생성하는 make_daytime_string() 함수를 정의해보겠다.

이 함수는 daytime 서버 응용프로그램 내에서 재사용 될 것이다.

std::string make_daytime_string()
{
  using namespace std; // For time_t, time and ctime;
  time_t now = time(0);
  return ctime(&now);
}

int main()
{
  try
  {
    boost::asio::io_service io_service;


ip::tcp::acceptor 객체는 새로운 커넥션을 listen 하기 위해 생성하였다. IPv4, TCP 포트 13 을 listen 하도록 초기화 했다. 

    tcp::acceptor acceptor(io_service, tcp::endpoint(tcp::v4(), 13));


한번에 하나의 커넥션을 다루는 iterative 서버가 될 것이다. 클라이언트의 커넥션을 표현할 socket 를 생성하고, 커넥션을 기다리도록 하자. 

 for (;;)
    {
      tcp::socket socket(io_service);
      acceptor.accept(socket);


클라이언트가 우리의 서비스에 접속했다. 현재 시간을 확인하고 클라이언트로 정보를 보낸다.

      std::string message = make_daytime_string();

      boost::system::error_code ignored_error;
      boost::asio::write(socket, boost::asio::buffer(message), ignored_error);
    }
  }


마지막으로, 예외를 처리한다. 

 catch (std::exception& e)
  {
    std::cerr << e.what() << std::endl;
  }

  return 0;
}


- full_source code



- main



- 실행결과


클라이언트바이너리를 별도로 만들어놓은 후, ( 이전 포스트 ) 서버실행후 클라이언트를 실행했다.




저작자 표시 비영리 변경 금지
신고