Parser for Lambda Calculator

이번엔 parser를 만들어보겠다. 앞서 설명했듯, Lambda Calculus의 syntax는 다음과 같다. (아직 괄호와 currying은 지원하지 않는다.)

LambdaExpr := Identifier
LambdaExpr := \ Identifier . LambdaExpr
LambdaExpr := LambdaExpr LambdaExpr

Haskell로 syntax object를 저장할 data type을 다음과 같이 정의한다. BNF 문법과 거의 일치한다. Haskell의 아름다운 문법이다.

data Lexpr =
    Lid String
        | Ldef String Lexpr
        | Lapp Lexpr Lexpr
        | ParseError

주어진 token이 identifier인지 아닌지 체크하는 함수 (lambda 기호 및 . 그리고 괄호를 제외한 모든 것들이 identifer로 사용 가능하다.)

valid_id :: String -> Bool
valid_id id = [ a | a <- "\\.()", [a]==id] == []

이제 Lexpr 타입의 syntax object를 만들어내는 함수다! 1st token list는 accept된, 2nd token list는 accept할 token list이다.

parse :: [[Char]] -> [[Char]] -> Lexpr
parse [] (x:[]) =
    if valid_id x then Lid x else ParseError
parse [] ("\\":x:".":xs) =
    if valid_id x then Ldef x (parse [] xs) else ParseError
parse [] ("\\":xs) = ParseError
parse ls ("\\":xs) = Lapp (parse [] ls) (parse [] ("\\":xs))
parse ls (x:[]) = Lapp (parse [] ls) (parse [] [x])
parse ls (x:xs) = parse (ls++[x]) xs -- shift to left

생성된 syntax object를 텍스트로도 봐야지 제대로 되는지 알 수 있겠지?

to_string :: Lexpr -> String
to_string (Lid id) = id
to_string (Ldef id le) = "LE(" ++ id ++ " -> " ++ (to_string le) ++ ")"
to_string (Lapp le1 le2) = "APP(" ++ (to_string le1) ++ " . " ++ (to_string le2) ++ ")"
to_string ParseError = "*parse error*"

이를테면 다음과 같은 실행 결과를 얻을 수 있다.

*Main> to_string $ parse [] $ lexer [] "\\x. f x \\y. g x y"
"LE(x -> APP(APP(f . x) . LE(y -> APP(APP(g . x) . y))))"

다음에는 괄호와 currying을 처리하도록 해보겠다. 그 다음엔 beta reduction, eta conversion 등을 구현하여 실제로 계산기로 활용할 수 있도록 한다.