Parser.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "6cd135ea-58c1-4100-880b-8c5f4e30c0a2",
   "metadata": {},
   "outputs": [],
   "source": [
    ":opt no-lint"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6922524f-0987-4b49-9fc4-b55c75afb5f0",
   "metadata": {},
   "source": [
    "# 파서의 타입\n",
    "파서의 타입을 다음과 같이 여러 번에 걸쳐 일반화할 수 있다. \n",
    "```haskell\n",
    "type Parser = String -> Tree                -- 문자열을 처리해 Tree로 변환\n",
    "type Parser = String -> (Tree, String)    -- 처리하고 남은 뒷부분 문자열 고려\n",
    "type Parser = String -> [(Tree, String)]  -- 실패할 경우 길이 0인 빈 리스트\n",
    "type Parser a = String -> [(a, String)]   -- 특정 Tree가 대신 타입 a로 일반화\n",
    "type Parser a = [Char] -> [(a, [Char])]   -- 윗줄과 같음  String = [Char]\n",
    "type Parser tok a = [tok] -> [(a, [tok])] -- Char 대신 토큰 타입 tok로 일반화\n",
    "```\n",
    "첫번째로는 가장 단순하게 파서를 문자열을 처리해 특정 추상문법나무(`Tree`)로 변환하는 것으로 이해할 수 있다.\n",
    "이것은 물론 파서에 대한 올바른 설명이긴 하지만 문법분석이라는 커다란 문제를 처리하는 전체 과정에 대한 설명이다.\n",
    "일반적으로 큰 문제는 작은 문제들로 쪼개서 생각할 수 있으므로 프로그래밍언어 전체의 문법도 더 작은 부분으로 나누어\n",
    "더 간단한 각 부분에 대한 작은 파서들을 만드는 부분적인 문제을 해결한 다음,\n",
    "이런 작은 파서를 엮어 프로그래밍언어 전체의 문법을 분석하는 파서를 구성할 수도 있을 것이다.\n",
    "따라서 파서란 전체 문자열이 아닌 앞부분 일부의 문자열을 처리하여 추상문법나무(`Tree`)를 구성하고 뒷부분의 일부 문자열(`String`)이 남아있을 수도 있다는\n",
    "개념으로 접근한다면 더 유연하고 일반적인 파서에 대한 설명이 될 것이다. 그러니까 두번째로는 파서를\n",
    "문자열(`String`)을 받아 추상문법나무와 문자열의 순서쌍(`(Tree, String)`)을 만들어낸다고 설명할 수 있을 것이다. \n",
    "그런데 파서가 모든 문자열에 대해 성공하지는 않을 수도 있으므로 세번째로는 실패하는 경우를 빈 리스트로 표현하고\n",
    "성공하는 경우를 추상문법나무와 문자열의 순서쌍이 들어 있는 비어 있지 않은 리스트를 만들어내도록 파서 타입의 정의를 일반화하였다.\n",
    "\n",
    "그 다음부터는 특정 타입에 한정된 분석 결과(`Tree`) 및 분석 대상(`String`)이 아니라\n",
    "이들을 파라미터화한 타입으로 파서를 일반화하는 과정이다. 그러니까 네번째로는 분석 결과를\n",
    "특정 추상문법나무로 한정하지 않고 분석 결과의 타입(`a`)에 대해 파라미터화한 타입(`Parser a`)으로\n",
    "일반할 수 있다. 마지막으로는 분석의 대상을 문자열(`String`) 즉 문자의 리스트(`[Char]`)인 경우로만\n",
    "한정짓지 않고, 분석의 대상이 되는 단위를 문자(`Char`)가 아닌 일반적인 토큰 타입(`tok`)으로 추가로\n",
    "파라미터화하여 파서의 타입을 `Parser tok a`로 표시하였으며, 이는 토큰열(`[tok]`)을 인자로 넘겨받아\n",
    "앞부분 일부를 분석한 결과(`a`)와 아직 분석하지 못한 뒷부분의 나머지 토큰열을 만들어 내려고 하는데,\n",
    "혹여 실패할 수도 있으므로 `[(a, [tok])]`타입의 값을 계산해 내는 함수로써 정의된다. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "8ef17e5b-9374-4cc6-9433-c7e91b213c02",
   "metadata": {},
   "outputs": [],
   "source": [
    "type Parser tok a = [tok] -> [(a, [tok])]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e469384e-4997-45ee-8838-c27dcd428449",
   "metadata": {},
   "source": [
    "# 가장 간단한 파서\n",
    "가장 기본적인 세 가지 파서인 `return`, `failure`, `item`을 소개하는 것으로 시작해 보자.\n",
    "정확히는 `return`이란 분석 결과값(`v`)을 미리 정해주면\n",
    "분석 대상을 전혀 처리하지 않고 무조건 성공하는 파서(`return v`)를 만들어내는 함수다.\n",
    "반면 `failure`는 무조건 실패하는 파서다.\n",
    "그리고 `item`은 주어진 토큰열로부터 맨 앞의 토큰 하나만을 분석하여\n",
    "그 토큰 그대로를 분석 결과로 하는 파서이다. 그러니까 `item`은\n",
    "길이 0이 아닌 모든 토큰열에 대해 성공한다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "38299726-37c0-42fa-a713-a9422d5dbb95",
   "metadata": {},
   "outputs": [],
   "source": [
    "return :: a -> Parser tok a -- 입력 토큰열 ts를 소비하지 않고\n",
    "return v = \\ts -> [(v,ts)]  -- 그냥 v를 리턴하며 성공하는 파서\n",
    "\n",
    "failure :: Parser tok a -- 입력에 관계없이 무조건 실패하는 파서\n",
    "failure = \\_ -> []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "30459eef-24d0-495f-8286-17ba1fd5d02a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1,\"abc\")]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "(return 1) \"abc\"\n",
    "failure    \"abc\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "8cb20c2b-6e64-4fd1-affc-2a85b00907a7",
   "metadata": {},
   "outputs": [],
   "source": [
    "item :: Parser tok tok\n",
    "item []     = []       -- 길이 0인 토큰열에 대해서는 실패\n",
    "item (t:ts) = [(t,ts)] -- 맨 앞의 토큰 t하나만 처리해 t를 리턴 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "304a87dc-ea6a-4724-babb-dce4da2591d8",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[('a',\"bc\")]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "item \"\"\n",
    "item \"abc\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ef6b4ebd-473c-44ae-870e-2ec00b19cce8",
   "metadata": {},
   "source": [
    "# 기존의 파서를 조합해 새로운 파서 만들기\n",
    "기존의 파서를 조합해 새로운 파서를 만들어내는 다섯 가지 유용한 파서 컴비네이터\n",
    "`(>>=)`, `(<|>)`, `sat`, `many`, `many1`에 대해 알아보자."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "8e3a1633-8c93-4bff-a8dc-f39950b0f188",
   "metadata": {},
   "outputs": [],
   "source": [
    "(>>=) :: Parser tok a -> (a -> Parser tok b) -> Parser tok b\n",
    "p1 >>= pf = \\ts -> [ (v2,ts2) | (v1,ts1) <- p1 ts,\n",
    "{- 이어붙이기 sequencing -}       (v2,ts2) <- (pf v1) ts1 ]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "223507fe-1688-48ef-857c-d77689c2839b",
   "metadata": {},
   "source": [
    "위의 `(>>=)`는 첫째 파서와 바로 그 첫째 파서의 분석 결과에 따라 다르게 만들어질 수 있는 둘째 파서를 이어붙이는 연산으로,\n",
    "첫째 파서가 분석하고 남은 토큰열을 둘째 파서로 분석한 결과를 전체 결과로 삼는다.\n",
    "즉, `p1 >>= pf`는 첫번째 파서(`p1`)의 성공적인 분석 결과가 `v1`이고 아직 분석되지 않고 남아있는 토큰열 `ts1`이라 할 때,\n",
    "앞선 파서의 분석 결과를 넘겨받아 따라 만들어지는 두번째 파서(`pf v1`)로 토큰열 `ts1`을 분석한 결과를 바로 전체 결과로 삼는\n",
    "파서라는 말이다.\n",
    "\n",
    "참고로 아래의 `item >>= \\_ -> item`은 `item >>= (\\_ -> item)`에서 하스켈 문법상 우선순위에 따라 불필요한 괄호가 생략된 표현이다.\n",
    "이렇게 앞선 파서의 분석 결과를 넘겨받은 파라미터를 활용하지 않고 무시하면 앞선 결과에 무관하게 항상 똑같은 내용의 둘째 파서가 만들어진다.\n",
    "그리고 이 연산을 두 번 중첩해서 사용하면 세 개의 파서를\n",
    "(`item`, `item`, `return` 순서로) 차례로 엮어 이어붙인 것과 같은 파서를 만들어낼 수도 있다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "efdd40ec-8630-40cb-859c-24b612e70467",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('b',\"cd\")]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[(\"ab\",\"cd\")]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "( item >>= \\_  ->  item                            ) \"abcd\"\n",
    "( item >>= \\c1 ->  item >>= \\c2 ->  return [c1,c2] ) \"abcd\" "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5ceeef63-ecc0-4d4c-ac89-e9729b297eb0",
   "metadata": {},
   "source": [
    "물론 다음과 같이 앞선 파서의 내용에 따라 두번째는 다른 파서(`item` 또는 `failure`)가 만들어지며 이어지도록 하는 것도 당연히 가능하다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "314917d6-f069-4a14-b4d4-595c627ce0dc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('e',\"llo\")]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "( item >>= \\c -> if c=='h' then item else failure ) \"hello\"\n",
    "( item >>= \\c -> if c=='h' then item else failure ) \"world\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "96aa7013-ef86-445d-8226-6211aed9640f",
   "metadata": {},
   "source": [
    "이미 한번 살펴본 바와 같이 `(>>=)`를 활용하며 다음과 같이 마지막에 `return`으로 이전 파서의 결과를 모아서 전체 분석 결과를 만들어내도록 조합할 수도 있다.\n",
    "그리고 가독성을 위해 `(>>=)`를 쓸 때마다 줄을 바꿔가며 작성해도 좋다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "141a54eb-8205-40ba-8dd0-4cba65c7ab68",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(\"he\",\"llo\")]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "( item                                >>= \\c1 ->\n",
    "  (if c1=='h' then item else failure) >>= \\c2 ->\n",
    "  return [c1,c2]                                 ) \"hello\"\n",
    "( item                                >>= \\c1 ->\n",
    "  (if c1=='h' then item else failure) >>= \\c2 ->\n",
    "  return [c1,c2]                                 ) \"world\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e3240146-a8b8-4a31-9a7c-ce86d7fff542",
   "metadata": {},
   "source": [
    "방금 살펴본 실행 사례처럼 첫째 파서의 결과가 특정 조건을 만족할 때만 성공하는\n",
    "활용 방식을 또 하나의 파서 컴비네이터로 다음과 같이 정의하자."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "c9c9fad1-46a5-446b-9618-6f55a2359153",
   "metadata": {},
   "outputs": [],
   "source": [
    "sat :: (tok -> Bool) -> Parser tok tok\n",
    "sat test = item >>= \\t ->          -- 토큰 하나를 읽어들여\n",
    "           if test t then return t -- 조건에 맞는 경우에만 성공하고 \n",
    "                     else failure  -- 그렇지 않으면 실패하는 파서"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "062e8f1a-145d-49cb-bcb6-6c5a30f44c37",
   "metadata": {},
   "source": [
    "이렇게 정의된 `sat`을 활용하면 조금 전에 살펴봤던 실행 사례를 아래와 같이 더 간결하게 표현할 수 있다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "314e9e21-fe5f-4cd0-a1db-ebc0705ca39f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(\"he\",\"llo\")]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "( sat (=='h') >>= \\c1 -> item >>= \\c2 -> return [c1,c2] ) \"hello\"\n",
    "( sat (=='h') >>= \\c1 -> item >>= \\c2 -> return [c1,c2] ) \"world\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "f3993312-52b8-4d6c-a5a9-132499ca24b3",
   "metadata": {},
   "outputs": [],
   "source": [
    "(<|>) :: Parser tok a -> Parser tok a -> Parser tok a  -- 선택 choice\n",
    "p1 <|> p2 = \\ts -> case p1 ts of\n",
    "                     []  -> p2 ts  -- 첫번째 파서가 실패하면 두번째로\n",
    "                     rs1 -> rs1    -- 첫번째가 성공하면 첫번째만으로"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "d51cf76d-d1e9-449f-8398-66e0e1c7b698",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('a',\"b\")]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[('a',\"b\")]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "item                  \"ab\"\n",
    "(item <|> return '?') \"ab\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "1a440878-aec0-4e9b-9dbb-93c66705a019",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[('?',\"\")]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "item                  \"\"\n",
    "(item <|> return '?') \"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "a0ebb43e-b676-4cda-889d-bdbce67addb5",
   "metadata": {},
   "outputs": [],
   "source": [
    "many, many1  :: Parser tok a -> Parser tok [a]  -- 상호재귀적으로 정의됨\n",
    "many  p = many1 p <|> return [] -- 1회 성공 또는 무조건 0회라 치고 성공\n",
    "\n",
    "many1 p = p      >>= \\v  ->  -- 한번 성공한 다음\n",
    "          many p >>= \\vs ->  -- 0회 이상 성공\n",
    "          return (v:vs)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3fc9b662-a289-4340-b106-adca2938a543",
   "metadata": {},
   "source": [
    "`many p`와 `many1 p`는 각각 0회 및 1회 이상 주어진 파서 `p`의 분석이 연달아 성공한 결과를 차례대로 모아놓은 리스트를 전체 분석 결과로 만들어낸다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "0638f45b-8504-47b7-b3ca-027fabcbe7cd",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(\"hhh\",\"i\")]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[(\"\",\"iiii\")]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "( many (sat (=='h')) ) \"hhhi\"\n",
    "( many (sat (=='h')) ) \"iiii\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "aaadea49-cc35-4cef-85eb-cbfc5754b16c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(\"hhh\",\"i\")]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "( many1 (sat (=='h')) ) \"hhhi\"\n",
    "( many1 (sat (=='h')) ) \"iiii\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "96eb4da6-3beb-498a-be01-bfbab044b5ef",
   "metadata": {},
   "source": [
    "# 문자열을 처리하는 파서\n",
    "지금까지는 분석의 단위 대상과 분석 결과에 대해 파라미터화된 일반적인 파서에 대해 다루었다.\n",
    "단지 실행 사례를 보여주기 위해 일반적인 파서를 문자열에 적용해 보았을 따름이다.\n",
    "이번에는 구체적으로 분석의 대상이 문자열로 한정된 파서를 정의해 보도록 하자.\n",
    "\n",
    "다음은 문자열에서 가장 특정 조건을 만족하는 첫 글자 하나를 처리하는 파서들이다.\n",
    "하스켈 뿐 아니라 대부분의 범용 프로그래밍 언어의 표준라이브러리에서 지원할 법한,\n",
    "어떤 유형(숫자, 소문자, 대문자, $\\ldots$, 공백문자)의 문자인지 검사하는\n",
    "조건함수(`isDigit`, `isLower`, `isUpper`, $\\ldots$, `isSpace`)를\n",
    "활용해 정의되어 있으며, 각 조건함수를 만족하는 첫 글자 하나만 분석한다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "c6c1ecc2-c896-4c06-ac96-234c6177a707",
   "metadata": {},
   "outputs": [],
   "source": [
    "import Data.Char ( isDigit, isLower, isUpper,\n",
    "                   isAlpha, isAlphaNum, isSpace )\n",
    "digit = sat isDigit\n",
    "lower = sat isLower\n",
    "upper = sat isUpper\n",
    "letter = sat isAlpha\n",
    "alphanum = sat isAlphaNum\n",
    "space = sat isSpace"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9122bd6c-0a0c-4795-b0e5-4e60cf2b5ab5",
   "metadata": {},
   "source": [
    "여기서는 `isDigit`을 활용해 정의된 `digit`에 대한 실행 사례만 아래에 나타나 있다. 나머지도 어떤 파서들인지 알아보고 시험해 보라."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "bcc13a66-9f35-4943-86a1-aef147ab7302",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style>/* Styles used for the Hoogle display in the pager */\n",
       ".hoogle-doc {\n",
       "display: block;\n",
       "padding-bottom: 1.3em;\n",
       "padding-left: 0.4em;\n",
       "}\n",
       ".hoogle-code {\n",
       "display: block;\n",
       "font-family: monospace;\n",
       "white-space: pre;\n",
       "}\n",
       ".hoogle-text {\n",
       "display: block;\n",
       "}\n",
       ".hoogle-name {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-head {\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-sub {\n",
       "display: block;\n",
       "margin-left: 0.4em;\n",
       "}\n",
       ".hoogle-package {\n",
       "font-weight: bold;\n",
       "font-style: italic;\n",
       "}\n",
       ".hoogle-module {\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-class {\n",
       "font-weight: bold;\n",
       "}\n",
       ".get-type {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "font-family: monospace;\n",
       "display: block;\n",
       "white-space: pre-wrap;\n",
       "}\n",
       ".show-type {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "font-family: monospace;\n",
       "margin-left: 1em;\n",
       "}\n",
       ".mono {\n",
       "font-family: monospace;\n",
       "display: block;\n",
       "}\n",
       ".err-msg {\n",
       "color: red;\n",
       "font-style: italic;\n",
       "font-family: monospace;\n",
       "white-space: pre;\n",
       "display: block;\n",
       "}\n",
       "#unshowable {\n",
       "color: red;\n",
       "font-weight: bold;\n",
       "}\n",
       ".err-msg.in.collapse {\n",
       "padding-top: 0.7em;\n",
       "}\n",
       ".highlight-code {\n",
       "white-space: pre;\n",
       "font-family: monospace;\n",
       "}\n",
       ".suggestion-warning { \n",
       "font-weight: bold;\n",
       "color: rgb(200, 130, 0);\n",
       "}\n",
       ".suggestion-error { \n",
       "font-weight: bold;\n",
       "color: red;\n",
       "}\n",
       ".suggestion-name {\n",
       "font-weight: bold;\n",
       "}\n",
       "</style><span class='get-type'>isDigit :: Char -> Bool</span>"
      ],
      "text/plain": [
       "isDigit :: Char -> Bool"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<style>/* Styles used for the Hoogle display in the pager */\n",
       ".hoogle-doc {\n",
       "display: block;\n",
       "padding-bottom: 1.3em;\n",
       "padding-left: 0.4em;\n",
       "}\n",
       ".hoogle-code {\n",
       "display: block;\n",
       "font-family: monospace;\n",
       "white-space: pre;\n",
       "}\n",
       ".hoogle-text {\n",
       "display: block;\n",
       "}\n",
       ".hoogle-name {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-head {\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-sub {\n",
       "display: block;\n",
       "margin-left: 0.4em;\n",
       "}\n",
       ".hoogle-package {\n",
       "font-weight: bold;\n",
       "font-style: italic;\n",
       "}\n",
       ".hoogle-module {\n",
       "font-weight: bold;\n",
       "}\n",
       ".hoogle-class {\n",
       "font-weight: bold;\n",
       "}\n",
       ".get-type {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "font-family: monospace;\n",
       "display: block;\n",
       "white-space: pre-wrap;\n",
       "}\n",
       ".show-type {\n",
       "color: green;\n",
       "font-weight: bold;\n",
       "font-family: monospace;\n",
       "margin-left: 1em;\n",
       "}\n",
       ".mono {\n",
       "font-family: monospace;\n",
       "display: block;\n",
       "}\n",
       ".err-msg {\n",
       "color: red;\n",
       "font-style: italic;\n",
       "font-family: monospace;\n",
       "white-space: pre;\n",
       "display: block;\n",
       "}\n",
       "#unshowable {\n",
       "color: red;\n",
       "font-weight: bold;\n",
       "}\n",
       ".err-msg.in.collapse {\n",
       "padding-top: 0.7em;\n",
       "}\n",
       ".highlight-code {\n",
       "white-space: pre;\n",
       "font-family: monospace;\n",
       "}\n",
       ".suggestion-warning { \n",
       "font-weight: bold;\n",
       "color: rgb(200, 130, 0);\n",
       "}\n",
       ".suggestion-error { \n",
       "font-weight: bold;\n",
       "color: red;\n",
       "}\n",
       ".suggestion-name {\n",
       "font-weight: bold;\n",
       "}\n",
       "</style><span class='get-type'>digit :: Parser Char Char</span>"
      ],
      "text/plain": [
       "digit :: Parser Char Char"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    ":type isDigit\n",
    ":type digit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "b62c46b3-d6eb-4ec0-bf73-eb3ff210d595",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('1',\"23\")]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "digit \"123\"\n",
    "digit \"a23\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "a0f212a0-cbaf-4985-82e4-9d522f83ff6f",
   "metadata": {},
   "outputs": [],
   "source": [
    "char :: Char -> Parser Char Char    -- char c는 주어진 글자 c와 첫글자가\n",
    "char c = sat (==c)                  -- 일치하는 경우에만 성공하는 파서\n",
    "\n",
    "string :: String -> Parser Char String  -- string s는 주어진 문자열 s와\n",
    "string []     = return []               -- 앞부분이 일치하는 경우에만 성공\n",
    "string (c:cs) = char c    >>= \\_ ->\n",
    "                string cs >>= \\_ ->\n",
    "                return (c:cs)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8dc5448f-0ab9-413d-b175-782d77fe967b",
   "metadata": {},
   "source": [
    "`char c`와 `string s`는 분석 대상 문자열의 앞부분이 주어진 글자 하나(`c`) 혹은 주어진 문자열(`s`)과 일치하는 경우에만 성공하는 파서이다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "3c680080-e6e8-46f4-8a0c-c1fe4ff2eab3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('h',\"ello\")]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "(char 'h') \"hello\"\n",
    "(char 'h') \"world\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "aa855f92-2958-4664-ab7d-8f4d5ebf2981",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(\"abc\",\"def\")]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "(string \"abc\") \"abcdef\"\n",
    "(string \"abc\") \"ab1234\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "8d415b46-12ea-4dac-98ab-c01d549ad686",
   "metadata": {},
   "outputs": [],
   "source": [
    "nat :: Parser Char Int\n",
    "nat = many1 digit >>= \\s ->  -- 1개 이상의 digit(숫자)\n",
    "      return (read s)        -- 문자열 s를 정수로 변환한 값으로 성공시킴\n",
    "\n",
    "ident :: Parser Char String\n",
    "ident = lower         >>= \\c  ->  -- 첫글자는 소문자\n",
    "        many alphanum >>= \\cs ->  -- 그 뒤에는 0개 이상의 문자 또는 숫자\n",
    "        return (c:cs)\n",
    "\n",
    "spaces  :: Parser Char ()\n",
    "spaces  = many  space >>= \\_ -> return ()  -- 0개 이상의 공백문자 처리\n",
    "spaces1 :: Parser Char ()\n",
    "spaces1 = many1 space >>= \\_ -> return ()  -- 1개 이상의 공백문자 처리"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0b51a28e-70ee-4cbd-a1b4-3c12d499c205",
   "metadata": {},
   "source": [
    "`nat`은 1개 이상의 연속적인 숫자로 이루어진 문자열을 처리하여 이를 정수로 변환한 값을 분석 결과로 하여 성공한다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "0185f815-5e55-4a93-9cf6-209c77627e9f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(\"123\",\"def\")]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[(123,\"def\")]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "(many1 digit) \"123def\"\n",
    "nat           \"123def\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a08438b2-b150-4bd3-8393-bf5df10f6645",
   "metadata": {},
   "source": [
    "`ident`는 소문자로 시작하고 그 이후로는 0개 이상의 문자 또는 숫자로 이루어진 단어를 분석한다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "d23773e3-7997-40b6-a501-25a5cd1831bb",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(\"abc123defghi\",\"\")]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[(\"abc123d\",\"  ghi\")]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "ident \"abc123defghi\"\n",
    "ident \"abc123d  ghi\"\n",
    "ident \"123abcd  ghi\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1afc06bd-526f-4fc9-832b-75f576673ed2",
   "metadata": {},
   "source": [
    "`spaces`는 0개 이상의 공백문자, `spaces1`은 1개 이상의 공백문자를 처리한다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "cb7fd708-e82f-4bd1-aa78-ec87529d918f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[((),\"abc\")]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[((),\"abc\")]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "spaces \"  abc\"\n",
    "spaces \"abc\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "674187ca-a7ed-4636-95a8-9fb061d2eb79",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[((),\"abc\")]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "spaces1 \"  abc\"\n",
    "spaces1 \"abc\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c1a07878-3b03-40f5-a447-ec7122a42635",
   "metadata": {},
   "source": [
    "\\newpage\n",
    "\n",
    "# 어휘분석(토큰화)\n",
    "어휘분석(lexical analysis) 혹은 토큰화(tokenization)란 구체적 문법을 따라 작성된 문자열을 토큰열로 변환하는 과정이다.\n",
    "\\ref{chap:FunArithEval}장에서 다룬 FAC언어의 토큰화를 위해 FAC언어의 어휘를 종류별로 분류한 토큰 데이터 타입을 다음과 같이 선언하자."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "653e1ae3-ee42-43d5-b87a-05a1e3c8e3c4",
   "metadata": {},
   "outputs": [],
   "source": [
    "data Tok = KW String -- 키워드\n",
    "         | ID String -- 변수 이름\n",
    "         | INT Int   -- 정수\n",
    "         | LP        -- (\n",
    "         | RP        -- )\n",
    "         | LAM       -- \\\n",
    "         | DOT       -- .\n",
    "         | ADD       -- +\n",
    "         deriving (Eq,Ord,Show)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7c96117e-ff2b-4785-a6a7-d19a1eb5204b",
   "metadata": {},
   "source": [
    "이 장에서 지금까지 소개한 파서 컴비네이터를 활용해 FAC언어의 토큰화를 한번 직접 시도해 보라.\n",
    "여러분들의 시도를 돕기 위해 FAC언어의 일부 어휘를 토큰화하는 아래와 같은 작은 토크나이저를 두 개 작성해 보았다.\n",
    "`word`는 식별자를 표현하는 문자열을 분석하는 파서(`ident`)가 성공적으로 분석한 결과(`s`)가\n",
    "키워드 목록으로 제시된 `if`, `then`, `else` 중 하나이면 분석 결과를 `KW s`로 그렇지 않은 일반적인 식별자이면 분석 결과를 `ID s`로 성공시킨다.\n",
    "`natural`은 자연수를 표현하는 문자열을 분석하는 파서(`nat`)가 성공적으로 분석한 정수값 결과(`n`)를 토큰으로 변환한 `INT n`을 분석 결과로 하여 성공시킨다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "a4e00030-9ab6-4a1b-b69c-16c38fc238eb",
   "metadata": {},
   "outputs": [],
   "source": [
    "word :: Parser Char Tok\n",
    "word = ident  >>= \\s ->\n",
    "       if s `elem` [\"if\",\"then\",\"else\"] then return (KW s)\n",
    "                                        else return (ID s)\n",
    "\n",
    "natural :: Parser Char Tok\n",
    "natural = nat >>= \\n -> return (INT n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "8b8ce72e-9db9-4084-9c15-d0629cdc49d6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "\"if\" `elem` [\"if\",\"then\",\"else\"] -- 리스트에 들어있는\n",
    "\"hi\" `elem` [\"if\",\"then\",\"else\"] -- 원소인지 검사하기"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6f5faed6-0744-47fc-9d51-c1fb022286ff",
   "metadata": {},
   "source": [
    "아래의 `word`를 실행한 사례 둘을 살펴보자.\n",
    "첫번째는 키워드로 분석되고 두번째는 일반적인 식별자로 분석된다.\n",
    "각각의 실행 사례가 어째서 그런 분석 결과가 나오는지 설명할 수 있는지 스스로 점검해 보라."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "ddd1fd58-b470-461c-80b6-60672f8b533b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(KW \"if\",\" then else  \")]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[(ID \"ifthen\",\"  else  \")]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "word \"if then else  \"\n",
    "word \"ifthen  else  \""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "61e19379-6fa4-4ab5-8f31-4558b2f1d527",
   "metadata": {},
   "source": [
    "아래는 여러 식별자 혹은 키워드의 나열로 이루어진 연속된 단어들을 처리하기 위해 `many` 컴비네이터를 활용하려 시도했지만 기대에 못미치는 분석 결과가 나온 실행 사례이다.\n",
    "왜 그냥 `word`로만 분석했을 때처럼 한 단어만 분석될까?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "39ccd24a-8eaf-4b25-bdc7-a12fbea98726",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[([KW \"if\"],\" then else  \")]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[([ID \"ifthen\"],\"  else  \")]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "(many word) \"if then else  \"\n",
    "(many word) \"ifthen  else  \""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "00b21de6-2d64-4c36-9e5c-5f4250c09529",
   "metadata": {},
   "source": [
    "\\noindent\n",
    "앞의 질문에 대한 답은 바로 공백문자를 어떻게 처리해야 하는지 고려하지 않고 작성한 파서로 공백문자가 포함된 문자열에 대한 분석을 시도했기 때문이다.\n",
    "\n",
    "많은 경우 프로그래밍언어에 나타나는 개별 어휘를 분석한 후 뒤따르는 공백문자를 건너뛰곤 한다.\n",
    "이렇듯 주어진 파서로 분석에 성공한 이후 뒤따르는 공백문자를 뛰어넘는 내용까지 포함된\n",
    "파서를 만들어내는 유용한 파서 컴비네이터인 `tok`를 다음과 같이 작성할 수 있다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "9ef5451c-dac7-4672-a01c-c3a1324145cc",
   "metadata": {},
   "outputs": [],
   "source": [
    "tok :: Parser Char a -> Parser Char a\n",
    "tok p = p      >>= \\v ->\n",
    "        spaces >>= \\_ ->\n",
    "        return v"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d5d38c94-e97c-49fd-890d-1e630e706078",
   "metadata": {},
   "source": [
    "\\noindent\n",
    "이제 `tok`와 `many`를 함께 활용하면 키워드나 식별자가 연달아 나타나는 문자열을 다음과 같이 여러개의 토큰으로 이루어진 토큰열로 분석할 수 있다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "d5eeeddf-2b26-493a-a0ff-050ee9a0b0ce",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[([KW \"if\",KW \"then\",KW \"else\"],\"\")]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[([ID \"ifthen\",KW \"else\"],\"\")]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "(many (tok word)) \"if then else  \"\n",
    "(many (tok word)) \"ifthen  else  \""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9c046a5c-4ab3-42cc-88c8-c56bed4e655f",
   "metadata": {},
   "source": [
    "앞서 다루었던 `<|>` 컴비네이터까지 같이 활용하면 키워드나 식별자 및 정수가 여럿 나타나는 문자열을 다음과 같이 토큰열로 분석할 수 있다.\n",
    "물론 아직 모든 모든 종류의 FAC언어의 어휘를 다 다루지는 않았으므로 그 이외의 어휘가 나타나면 그 이후로는 분석하지 못한 문자열이 남아있게 된다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "68cf50f4-ecb9-4a01-85d2-85f0d778f9cb",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[([KW \"if\",ID \"b1\",KW \"then\",INT 123,KW \"else\",ID \"x3\"],\"\")]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[([KW \"if\",ID \"b1\",KW \"then\",INT 123,KW \"else\",INT 3],\"+ (\\\\y. y) \")]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "(many (tok word <|> tok natural)) \"if b1 then 123 else x3  \"\n",
    "(many (tok word <|> tok natural)) \"if b1 then 123 else 3 + (\\\\y. y) \""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "28774b02-968f-48ea-8f18-df1265646bed",
   "metadata": {},
   "source": [
    "# 문법분석\n",
    "FAC언어에 대한 어휘분석은 문자열(`[Char]`)을 분석하여 토큰열(`[Tok]`)을 만들어내는 `Parser Char [Tok]` 타입의 프로그램으로 나타낼 수 있다.\n",
    "FAC언어에 대한 문법분석은 이렇게 만들어진 토큰열(`[Tok]`)을 분석하여 추상문법구조(`Expr`)를 만들어내는 `Parser Tok Expr` 타입의 프로그램으로 나타낼 수 있다. \n",
    "\n",
    "다음은 람다식을 제외한 FAC언어의 일부분에 대한 추상문법을 나타내는 `Expr` 데이터 타입 선언이다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "35d2044e-fe9f-4f97-ac27-e1b9ea931072",
   "metadata": {},
   "outputs": [],
   "source": [
    "data Expr = Lit Int            -- n\n",
    "          | Add Expr Expr      -- e1 + e2\n",
    "          | If Expr Expr Expr  -- if e then e1 else e0\n",
    "          deriving (Eq, Ord, Show)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9c3d6dfa-9b34-4522-83e3-1a91b93c2f93",
   "metadata": {},
   "source": [
    "우선, 그 중에서도 정수와 덧셈식만을 문법분석하는 `aexp` 파서를 다음과 같이 결합도에 따라 \n",
    "`aexp0`와 `aexp1`두 단계로 구분하여 작성할 수 있다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "2b677f9d-c927-46bf-8ce6-726c51a94eba",
   "metadata": {},
   "outputs": [],
   "source": [
    "aexp, aexp0, aexp1 :: Parser Tok Expr\n",
    "aexp = aexp0  -- 덧셈식만 처리하는 파서\n",
    "\n",
    "-- EBNF로는 aexp0 ::= { aexp1 \"+\" } aexp1\n",
    "aexp0 = many ( aexp1       >>= \\e ->\n",
    "               sat (==ADD) >>= \\_ -> \n",
    "               return e              )  >>= \\es ->\n",
    "        aexp1                           >>= \\e' ->\n",
    "        return (foldl1 Add (es ++ [e']))  -- 덧셈을 좌결합으로 처리\n",
    "\n",
    "-- EBNF로는 aexp1 ::= lit | \"(\" aexp0 \")\"\n",
    "aexp1 = lit <|> paren aexp0\n",
    "\n",
    "lit = sat isINT  >>= \\(INT n) -> return (Lit n)\n",
    "    where isINT (INT _) = True\n",
    "          isINT _       = False\n",
    "\n",
    "paren p = sat (==LP) >>= \\_ ->\n",
    "          p          >>= \\e ->\n",
    "          sat (==RP) >>= \\_ ->\n",
    "          return e"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4ffdf2eb-d2e1-42a1-8e11-ad07872685ef",
   "metadata": {},
   "source": [
    "`aexp0`는 덧셈 기호로 연결된 느슨하게 결합된 식을 분석하는 파서다.\n",
    "덧셈 기호는 더 단단하게 묶여 있는 `aexp1` 사이사이에 나타날 수 있다.\n",
    "그러니까 `aexp0`가 처리하는 토큰열이란, `aexp1`으로 분석되는 토큰열과\n",
    "그에 바로 뒤따르는 덧셈 연산자(`ADD`)가 0회 이상 반복된 다음\n",
    "마지막에 `aexp1`로 분석되는 토큰열로 마무리된다.\n",
    "여기서 덧셈 연산자는 좌결합(즉, `1+2+3`을 `(1+2)+3`으로 이해)으로 처리하므로 `foldl1`을 활용해 선언하고 있다. \n",
    "\n",
    "`aexp1`은 더 이상 쪼갤 수 없는 정수 리터럴(`lit`) 혹은 구체적 문법에서 프로그래머가 강제로 괄호로\n",
    "명시적으로 묶어 놓은 식(`paren expr0`)에 해당하는 토큰열을 분석한다."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "7f11da27-f01f-4f2a-b5af-06248753adaa",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(Lit 1,[])]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[(Lit 1,[ADD,INT 2])]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "lit [INT 1]             -- 1\n",
    "lit [INT 1, ADD, INT 2] -- 1 + 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "450403b1-3705-4f9b-9001-c6563030479a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(Lit 2,[])]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[(Lit 2,[ADD,INT 3])]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[(Add (Lit 2) (Lit 3),[])]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "aexp1 [INT 2]                     -- 2\n",
    "aexp1 [INT 2, ADD, INT 3]         -- 2 + 3\n",
    "aexp1 [LP, INT 2, ADD, INT 3, RP] -- (2 + 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "763dbc50-2a41-452f-9192-e84533166562",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(Add (Lit 1) (Lit 2),[])]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[(Add (Lit 1) (Add (Lit 2) (Lit 3)),[])]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "aexp [INT 1, ADD, INT 2]                     -- 1 + 2\n",
    "aexp [INT 1, ADD, LP, INT 2, ADD, INT 3, RP] -- 1 + (2 + 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "4fb66c43-55f0-4df5-b902-dfe70af29fbe",
   "metadata": {},
   "outputs": [],
   "source": [
    "expr, expr0, expr1 :: Parser Tok Expr\n",
    "expr = expr0 -- Expr에 대한 파서\n",
    "\n",
    "-- EBNF로는 expr0 ::= { expr1 \"+\" } (expr1 | cexpr)\n",
    "expr0 = many ( expr1       >>= \\e ->\n",
    "               sat (==ADD) >>= \\_ -> \n",
    "               return e              )  >>= \\es ->\n",
    "        (expr1 <|> cexpr)               >>= \\e' ->\n",
    "        return (foldl1 Add (es ++ [e']))\n",
    "\n",
    "expr1 = lit <|> paren expr0\n",
    "\n",
    "cexpr = sat (== KW \"if\")   >>= \\_  -> expr0 >>= \\e  ->\n",
    "        sat (== KW \"then\") >>= \\_  -> expr0 >>= \\e1 ->\n",
    "        sat (== KW \"else\") >>= \\_  -> expr0 >>= \\e0 ->\n",
    "        return (If e e1 e0)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4db7cfce-5679-422e-8007-862a588b9eb9",
   "metadata": {},
   "source": [
    "\\newpage\n",
    "\n",
    "위의 `expr`은 정수 리터럴과 덧셈식만이 아니라 조건식까지 포함한 `Expr`를 문법분석하는 파서다.\n",
    "`aexp`의 경우와 마찬가지로 결합도에 따라 `expr0`와 `expr1`의 두 단계로 작성하였다.\n",
    "조건식이 별도의 결합도 단계로 구분되는 것이 아니라 `expr0`에서 덧셈 기호들이 나타나고\n",
    "가장 마지막에 `(expr1 <|> cexpr)`이 온다. 즉 `expr1`과는 별개이지만 동등한 레벨로\n",
    "`cexpr`을 취급한다. 이와 같이 파서를 선언하면 아래의 하스켈 예시와 마찬가지로 \n",
    "FAC언어에서도 조건식이 덧셈의 오른쪽에 나타나는지 왼쪽에 나타나는지에 따라 적절히 분석된다. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "7fb2b7e2-2ad7-4a28-9f99-38598456c9d1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "1 + if False then 1 else 0  -- 하스켈의 경우\n",
    "1 +(if False then 1 else 0) -- 조건식 왼쪽에 오는 덧셈은 이렇게"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "3eb84918-35a6-47f3-ab2c-79d94797b68a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "if True then 1 else 0 + error \"?\"  -- 하스켈의 경우 조건식 오른쪽\n",
    "if True then 1 else(0 + error \"?\") -- else 다음에 오는 덧셈은 이렇게"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "14aa1712-eb56-4a5b-8fb1-0748a838cec0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(Add (Lit 1) (If (Lit 10) (Lit 20) (Lit 30)),[])]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[(If (Lit 10) (Lit 20) (Add (Lit 30) (Lit 1)),[])]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "[(Add (If (Lit 10) (Lit 20) (Lit 30)) (Lit 1),[])]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "--    1 + if 10 then 20 else 30\n",
    "expr [INT 1, ADD,\n",
    "      KW \"if\", INT 10, KW \"then\", INT 20, KW \"else\", INT 30]\n",
    "--    if 10 then 20 else 30 + 1\n",
    "expr [KW \"if\", INT 10, KW \"then\", INT 20,\n",
    "                       KW \"else\", INT 30, ADD, INT 1]\n",
    "--  (if 10 then 20 else 30) + 1\n",
    "expr [LP, KW \"if\", INT 10,KW \"then\", INT 20, KW \"else\", INT 30, RP,\n",
    "      ADD, INT 1]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "39955f07-3754-45dc-8afa-07d9e13e40fc",
   "metadata": {},
   "source": [
    "\\section*{연습문제}\n",
    "1. `[25]`번 셀의 `nat :: Parser Char Int`는\n",
    "   `\"12\"`나 `\"0\"`처럼 자연수(0 이상의 정수)를 나타내는 문자열은 처리할 수 있지만\n",
    "   `\"-123\"`처럼 음의 정수를 나타내는 문자열을 처리하지 못한다.\n",
    "   `\"12\"`나 `\"0\"`처럼 자연수를 나타내는 문자열과 `\"-123\"`처럼 음의 정수를 나타내는\n",
    "   문자열을 모두 처리할 수 있는, 즉 십진수 정수를 나타내는 문자열을 처리하는\n",
    "   `int :: Parser Char Int`를 작성해 보라.\n",
    "1. 다음 두 파서가 어떤 문자열에 대해 처리 결과가 달라지는지 실행 사례를 들고\n",
    "   어째서 그러한 차이점이 발생하는지도 설명해 보라.\n",
    "   - `(string \"if\" <|> string \"then\" <|> string \"else\" <|> ident)`\n",
    "   - `(ident <|> string \"if\" <|> string \"then\" <|> string \"else\")`\n",
    "1. `[30]`번 셀의 `Tok`는 FAC언어(\\ref{chap:FunArithEval}장)의 어휘에 대한\n",
    "   토큰을 나타내는 데이터 타입이다. 맨 앞에도 공백문자들이 나타나는 것을 허용하면서\n",
    "   FAC언어를 나타내는 문자열을 토큰화하는\n",
    "   `lexFAC :: Parser Char [Tok]` 함수를 작성해 보라.\n",
    "1. `[38]`번 셀의 `Expr`에 람다식의 세 요소(변수, 함수요약식, 함수적용식)를 추가하여 FAC언어의 문법을 모두 나타낼 수 있도록 수정한 다음\n",
    "   `[43]`번 셀의 파서도 그에 맞게 람다식의 세 요소도 처리할 수 있도록 수정해 보라.\n",
    "1. `lexFAC`과 바로 위 문제에서 수정된 `expr`을 연결하여 문자열로 된 FAC언어의 소스코드를\n",
    "   요약문법으로 분석하는 `parseFAC :: Parser Char Expr`을 작성하라."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e84b45e1-5b52-40e8-9537-d42917c2023b",
   "metadata": {},
   "source": [
    "\\newpage\n",
    "\\section*{탐구과제}\n",
    "1. 우선순위와 결합성이 다른 연산자가 나타나는 산술식의 파서를 어떻게 작성해야 할지 생각해 보라.\n",
    "   좀더 구체적으로는, 덧셈(`+`)보다 강하게 결합하는 곱셈(`*`), 그리고 그보다 더 강하게 결합하는\n",
    "   거듭제곱(`^`)의 세 연산자를 포함하는 산술식을 처리하는 파서를 이 장에서 배운 방식대로 작성해 보라.\n",
    "   단, 덧셈과 곱셈은 좌결합으로 거듭제곱은 우결합으로 처리하라.\n",
    "1. 정규언어로 주석(comment) 제거를 포함한 어휘분석(lexing)이 가능하도록 설계된 언어는 겹쳐진 여러 줄 주석을 처리하지 못한다.\n",
    "   예컨대, C언어에서는 다음과 같이 주석을 작성하면 오류가 난다. \\`\\``처리된 부분 */`\\'\\'까지만 주석으로 처리되기 때문이다.\n",
    "   ```C\n",
    "   /* 아래의 여러 줄 주석을\n",
    "      한겹 더 여러 줄 주석으로 감싸려 하면\n",
    "      /* 먼저 여러 줄 주석으로\n",
    "         처리된 부분 */\n",
    "      여기서부터는 주석으로 처리되지\n",
    "      않아 어휘분석 오류가 발생한다 */\n",
    "   ```\n",
    "   정규언어로는 왜 이런 주석을 처리할 수 없는지 설명해 보라.\n",
    "1. 대부분의 실제 프로그래밍 언어들은 문맥자유문법(CFG)만으로는 표현하기 불가능하거나 어려운 문법요소를 포함한다.\n",
    "   C/C++의 경우에 어떠한 사례가 있는지 조사해 보라.\n",
    "1. 이 장에서 소개한 아이디어를 기반으로 하는 Haskell의 Parsec 등의 파서 컴비네이터 라이브러리를\n",
    "   \\`내장형 특수목적언어\\' (embeded Domain-Specific Language, eDSL)라고도 한다.\n",
    "   내장형 특수목적언어의 개념에 대해, 특히 일반적인 특수목적언어와 비교되는 특징을 중심으로, 알아보라.\n",
    "   참고로, 그냥 \\`특수목적언어\\'(DSL)라고 언급할 할 때는 일반적으로 내장형이 아닌 경우를 말하며,\n",
    "   내장형(embedded)이 아님을 강조하기 위해 독립적(stand-alone) 혹은 외장형(external) 특수목적언어라 부르기도 한다.\n",
    "1. C와 함께 활용하는 lex과 yacc, Haskell과 함께 활용하는 alex와 happy를 비롯한 많은\n",
    "   렉서 생성기(lexer generator)와 파서 생성기(parser generator)들이 있다.\n",
    "   이런 렉서 생성기 및 파서 생성기와 이 장에서 다루는 파서 컴비네이터의 차이점과 장단점을 비교하며 알아보라.\n",
    "   참고로, 렉서 성생기나 파서 생성기는 독립적 혹은 외장형 특수목적언어에 대한 컴파일러로 볼 수 있다.\n",
    "   그러므로 조사하려는 렉서/파서 생성기와 파서 컴비네이터와 비교되는 장단점은\n",
    "   일반적으로 비슷한 문제에 접근하는 독립적 특수목적언어와 내장형 특수목적언어를 비교할 때 나타나곤 하는 장단점과도 일맥상통할 수 있다."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Haskell",
   "language": "haskell",
   "name": "haskell"
  },
  "language_info": {
   "codemirror_mode": "ihaskell",
   "file_extension": ".hs",
   "mimetype": "text/x-haskell",
   "name": "haskell",
   "pygments_lexer": "Haskell",
   "version": "8.10.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}