Bu postda qanday qilib parser combinator yasashni ko’ramiz. Ya’ni, kichkina parserlarni har xil usulda birlashtirib kattaroq parserlar yozish. Avvallambor, parser nima ekanligini ko’rib chiqaylik.

Parser – “flat” ma’lumotni strukturalik turga aylantirish deb ataylik. Parserga misollar:

json satrni json turiga aylantirish
email satrni bo’laklariga ajratish
dasturlash tilidagi kodni ASTga aylantirish
dasturlash tilidagi tokenlarni ASTga aylantirish

Tepadagilardan tashqari, parserlarning juda qo’l keladigan bir joyi: dasturlarning loglarini parse qilish. Bunga postning oxirida misol bor. Undan tashqari, regex ishlatiladigan joylarda parser combinatorlar ham ishlatsa bo’ladi.

Parserga birinchi urinish

Parser turini bunday yozib ko’raylik:

newtype Parser a = Parser
  { runParser :: String -> Maybe a
  }

Masalan, Parser Email satrni emailga o’tkazuvchi parserning turi bo’ladi. Endi parserlarni bunday yozsak bo’ladi. Bu yerda parseNull faqatgina "null" satrni parse qiladi, va qolgan satrlarda Nothing qaytaridr “fail” qiladi.

parseNull = Parser \case
  "null" -> Just ()  -- natija sifatida () qaytaramiz
  _ -> Nothing

ghci> runParser parseNull "null"
Just ()

Butun satrlarni parse qilish uchun abstraksiya qilsak bo’ladi:

string :: String -> Parser String
string t = Parser \s ->
  if s == t
  then Just t
  else Nothing

parseNull = string "null"
parseTrue = string "true"
parseFalse = string "false"
parseComma = string ","

ghci> runParser parseNull "null"
Just "null"
ghci> runParser parseNull "null,"
Nothing

Kombinatorlar

Biz bu kombinatorlarni qo’llab quvvatlamoqchimiz:

combine :: Parser a -> Parser b -> Parser (a, b) – ikkala parserni ketma-ket ishga tushiradi va natijalarini juftlik qilib qaytaradi.
alt :: Parser a -> Parser a -> Parser a – agar birinchi parser ishlamasa ikkinchi parserni ham urinib ko’radi.

Lekin tepadagi parser turi bilan combineni yoza olmaymiz. Bizga “null,” berilgan bo’lsa unda uni 1- va 2-parser qayerdan ikkiga bo’lib berishni bilmaymiz. Barchasini sinab ko’rish sekinlik qiladi.

combine pa pb = Parser \s -> ???

Ikkinchi urinish

Endi parserning turini ozgina o’gartiramiz. Bu safar parserimiz Stringning boshini parse qilishga harakat qiladi. Faqatgina natijani emas, Stringning qolgan qismini ham qaytaradi.

newtype Parser a = Parser
  { runParser :: String -> Maybe (a, String)
  }
  
string t = Parser \s ->
  case stripPrefix t s of
    Just rest -> Just (t, rest)
    Nothing -> Nothing

ghci> runParser parseNull "null,"
Just ("null",",")

Kombinatorlar

Endi combine funksiya uchun shunchaki birinchi parserning qaytargan satrni ikkinchi parserga beramiz.

combine pa pb = Parser \s ->
  case runParser pa s of
    Nothing -> Nothing
    Just (vala, resta) ->
      case runParser pb resta of
        Nothing -> Nothing
        Just (valb, restb) ->
          Just ((vala, valb), restb)

altni yozish murakkab emas:

alt pa pb = Parser \s ->
  case runParser pa s of
    Just output -> Just output
    Nothing -> runParser pb s

Endi parseBoolni yozib ko’raylik:

parseBool = alt parseTrue parseFalse

lekin parseBoolning turi Parser Stringdir. Uni Parser Bool qila olish uchun biz parserning natijasiga funksiya chaqira olishimiz kerak. Buning uchun Functor instance yozib, fmap ishlatsak bo’ladi:

instance Functor Parser where
  fmap :: (a -> b) -> Parser a -> Parser b
  fmap f p = Parser \s ->
    case runParser p s of
      -- shunchaki, funksiyani natija bilan chaqiramiz
      Just (x, rest) -> Just (f x, rest)
      Nothing -> Nothing
      
parseTrue, parseFalse, parseBool :: Parser Bool
parseTrue = fmap (\_ -> True) $ string "true"
parseFalse = fmap (\_ -> False) $ string "false"
parseBool = alt parseTrue parseFalse

-- bunday yozsa ham bo'ladi:
parseTrue' = True <$ string "true"

-- shunchaki combine qilsa Parser (Bool, ()) bo'lib qoladi
parseBoolComma = fmap fst $ combine parseBool parseComma

ghci> runParser (combine parseBool parseBool) "truefalse"
Just ((True,False),"")

Applicative

Haskellda combine o’xshash funksiyalar uchun typeclass bor: Applicative. Uni implement qilish do-notation bilan combine qilish osonroq bo’ladi:

instance Applicative Parser where
  -- doim muvaffaqiyatli natija qaytaradigan parser
  pure :: a -> Parser a
  pure x = Parser \s -> Just (x, s)
  
  liftA2 :: (a -> b -> c) -> Parser a -> Parser b -> Parser c
  liftA2 f pa pb = fmap (\(a, b) -> f a b) $ combine pa pb

liftA2 alohida funksiya oladi va uni aslida amalda ishlatish combinega nisbatan qulayroq.

many, some

many :: Parser a -> Parser [a] – parserni 0 yoki undan ko’p marta ishga tushiradi, va natijalarini listga to’playdi.
some :: Parser a -> Parser [a] – many kabi ishlaydi lekin parser kamida 1marta ishlashi kerak.

E’tibor bering, many agar hech nimani parse qila olmasa ham error qaytarmaydi, shunchaki [] qaytaradi.

Bu kombinatorlarni yozish uchun aslida biz Parserning konstruktorini ishlatishimiz shart emas:

many' p =
  alt
    (liftA2 (:) p $ many' p)
    (pure [])
some' p =
  liftA2 (:) p $
    alt
      (some' p)
      (pure [])

ghci> runParser (many' parseBoolComma) "true,false,false,123"
Just ([True,False,False],"123")

Tepadagi kod tushunarsiz bo’lsa, unda u kodni rekursiv funksiya deb o’ylab ko’ring:

Boshlang’ich xolat: hech nimani parse qilmasdan shunchaki [] qaytarish
Rekursiv xolat: bir marta pni parse qilib rekursiya qilish

Aslida Haskellda alt kabi funksiyalar uchun ham typeclass bor - Alternative. Uni yozsak, bizga o’zi many va some funksilarani beradi.

instance Alternative Parser where
  -- doim muvaffaqiyatsiz qaytadigan parser
  empty = Parser \_ -> Nothing
  
  (<|>) = alt

ghci> :t many parseBoolComma
many parseBoolComma :: Parser [Bool]

Bizga bu ikkita parser foydali bo’ladi. Birinchisi: berilgan qoidaga oid harflarni parse qilish. Bu safar () emas Char qaytarish kerak.

charP :: (Char -> Bool) -> Parser Char
charP f = Parser \case
  [] -> Nothing
  (c : rest) | f c -> Just (c, rest)
  _ -> Nothing

Ikkinchisi: iloji boricha barcha whitespaceni parse qilish:

-- convention bo'yicha sc deb nomlanadi
sc = many $ charP \c -> c `elem` " \n\r\t"

-- p ni ishga tushiradi va orqasidan barcha whitespaceni olib tashlaydi
lexeme :: Parser a -> Parser a
lexeme p = liftA2 (\a b -> a) p sc

symbol = lexeme . string

Endi ,ning atrofida bo’sh joy tashlangan bo’lsa ham parse qila olamiz:

parseBoolComma2 = liftA2 (\x _ -> x) (lexeme parseBool) (lexeme parseComma)

Do-notation

Hozirda bizda parserlarning yozishning bir necha xil usullari bor:

liftA2/combine
<*>/<*/*>
do-notation

2-usulga qaraylik. U barcha Applicativelar uchun, lekin bu yerda Parser turiga specialize qilamiz:

(<*) :: Parser a -> Parser b -> Parser a
(*>) :: Parser a -> Parser b -> Parser b
(<*>) :: Parser (a -> b) -> Parser a -> Parser b

Misol uchun, p1 <* p2 qilsak ikkala parser ham ishga tushadi lekin faqatgina birinchi parserning natijasi qaytariladi:

lexeme' p = p <* sc
parseBoolComma3 = lexeme parseBool <* lexeme parseComma

ghci> runParser parseBoolComma3 "true ,  false, true,"
Just (True,"false, true,")

<*>-operator g’alati tuyilishi mumkin, lekin u orqali bunday kod yozsa bo’ladi:

pure f <*> p1 <*> p2 <*> p3
== f <$> p1 <*> p2 <*> p3
== liftA3 f p1 p2 p3

Agar fga ko’proq parametr kerak bo’lsa unda shunchaki ko’proq <*> ishlatsak bo’ladi.

Do-notationga keladigan bo’lsak, biz monadic emas applicative parser yozganimiz uchun ApplicativeDo extensionni yoqish kerak. (Xohlasangiz, Monad instance ham yozib qo’ying.) Undan so’ng, parselar bunday ko’rinishda yozish mumkin:

p = do
  val1 <- p1
  val2 <- p2
  val3 <- p3 
  val4 <- p4
  pure $ ...

Oxirida purening ichiga avvalgi vallardan foydalanadigan istagan ifoda yozsak bo’ladi. p1larning o’rniga ham istagan ifoda yozsa bo’ladi, lekin u yerda vallardan foydalanish mumkin emas. Agar parserning natijasi kerak emas bo’lsa shunchaki

  _ <- p2
  -- yoki
  p2

yozsa bo’ladi.

Lisp parser

Endi juda oddiy parser yozib ko’raylik. Bunday qavsli ifodalarni bu ASTga o’tkazaylik:

data Ast = Atom String | Cell [Ast]
  deriving (Show)

(a b (c d))
==> Cell [Atom "a",Atom "b",Cell [Atom "c",Atom "d"]]

Atom uchun parser yozamiz:

parseAlpha = charP \c -> 'a' <= c && c <= 'z' || 'A' <= c && c <= 'Z'

parseAtom = do
  name <- lexeme $ some parseAlpha
  pure $ Atom name

So’ng, Cell uchun parser yozamiz:

parseCell = do
  symbol "("
  body <- many parseAtom
  symbol ")"
  pure $ Cell body

Lekin bu parser (a (b c))ga o’xshash rekursiv qavslarni parse qila olmaydi. Chunki body uchun parseAtomni ishlatyapmiz. To’g’ri ishlashi uchun parseAtom <|> parseCellni ishlatishimiz kerak:

parseCell = do
  symbol "("
  body <- many parseAst
  symbol ")"
  pure $ Cell body

parseAst = parseAtom <|> parseCell

Do-notation o’rniga operatorlar bilan yozsa bunday bo’ladi:

parseAtom = Atom <$> lexeme (some parseAlpha)
parseCell = Cell <$> (symbol "(" *> many parseAst <* symbol ")")
parseAst = parseAtom <|> parseCell

Lv tiliga parser

Endi sal murakkabroq tilga parser yozib ko’raylik. U tilda butun sonlar va +-* binar operatorlar bor:

(+ 42 37)

Va o’zgaruvchilar bor:

(let [varname varvalue] body)
(let [x (+ 1 2)]
 (+ x 30))

data Lv
  = Var String
  | LInt Int
  | Add Lv Lv
  | Sub Lv Lv
  | Mul Lv Lv
  | Let String Lv Lv
  deriving (Show)

Avvalambor tepadagi parseAst kabi hamma narsani birlashtiradigan parser yozaylik:

parseLv =
  parseVar
  <|> parseLInt
  <|> parseAdd
  <|> parseSub
  <|> parseMul
  <|> parseLet

Var uchun va sonlar uchun parser yozishdan boshlaylik:

parseVar = Var <$> lexeme (some parseAlpha)

parseDigit = charP \c -> '0' <= c && c <= '9'
parseLInt = do
  digits <- lexeme $ some parseDigit
  pure $ LInt (read digits)

Agar noldan kichik sonlarni ham parse qila olishimiz kerak bo’lsa bunday yozsa bo’ladi, lekin hozircha buni ishlatmaymiz:

option x p = p <|> pure x

parseSignedInt :: Parser Int
parseSignedInt = do
  sign <- option "" (string "-")
  digits <- some parseDigit
  pure $ read $ sign ++ digits

Binary operatorlar uchun alohida abstraksiya yasasak bo’ladi:

parseBinary op f = do
  symbol "("
  symbol op
  lhs <- parseLv
  rhs <- parseLv
  symbol ")"
  pure $ f lhs rhs

parseAdd = parseBinary "+" Add
parseSub = parseBinary "-" Sub
parseMul = parseBinary "*" Mul

parseLetni yozish ham oson:

parseLet = do
  symbol "("
  symbol "let"
  symbol "["
  name <- lexeme $ some parseAlpha
  value <- parseLv
  symbol "]"
  body <- parseLv
  symbol ")"
  pure $ Let name value body

Demonstratsiya uchun, operatorlar bilan bunday ko’rinishda bo’ladi:

parseLet = 
  Let
    <$> (symbol "(" *> symbol "let" *> symbol "[" *> lexeme (some parseAlpha))
    <*> parseLv
    <*> (symbol "]" *> parseLv <* symbol ")")

Parserni yozish juda ham oson bo’ldi degan gapga qo’shalisizmi?

ghci> runParser parseLv "(let [x (+ 1 2)] (let [y x] (- x y)))"
Just (Let "x" (Add (LInt 1) (LInt 2)) (Let "y" (Var "x") (Sub (Var "x") (Var "y"))),"")

Bu bugmi yoki featuremi hali hal qilmadim:

ghci> runParser parseLv "(+1x)"
Just (Add (LInt 1) (Var "x"),"")

Kutubxonalar

Haskellda parser kombinatorlar yozish oson bo’lgani uchun bunday kutubxonalar soni ham ko’p. Bulardan megaparsec yoki attoparsecni ishlatishni maslahat beraman. Bu kutubxonalarda biznikiga nisbatan ancha ko’proq featurelar bor:

Parser qayerda yiqilganini hisob-kitob qilib yurish. Biznikida shunchaki doim Nothing qaytaramiz.
Parserlarning qismiga <?> orqali nom berish. Parser-errorlar shu nomlarni ishlatib foydaliroq xabar chiqaradi.
Parserlarni debug qilish
Stringdan boshqa turlar bilan ishlay olish: Text, ByteString, Vector Token
Yuqori samaradorlik
Oqimlarni (ya’ni inputning faqatgina bosh qismi bor bo’lsa) parse qila olish
backtrack qilishni yaxshiroq boshqarish

Oxirgi nuqtada to’xtalib o’tsak. Bizning parser muvaffaqiyatsiz bo’lsa doim eng yaqin <|>ga qaytib boradi, lekin bu kutubxonalarning parseri bunday qilmaydi. Ularda eng yaqin tryga qaytib boradi. Misol uchun bizning parserda:

ghci> p = string "a" *> string "b" <|> string "a" *> string "a"
ghci> runParser p "aa"
Just ("a","")

Lekin megaparsecda birinchi string "a" muvaffaqiyatli ishlagandan so’ng <|>ga hech qachon qaytmaydi. Ikkinchi string muvaffaqiyatlimi yo’qmi farqi yo’q:

import Control.Applicative
import Data.Void
import Text.Megaparsec.Char
import Text.Megaparsec

type Parser = Parsec Void String

p :: Parser String
p = p1 <|> p2
 where
  p1 = string "a" *> string "b"
  p2 = string "a" *> string "a"

ghci> parseTest p "aa"
1:2:
  |
1 | aa
  |  ^
unexpected 'a'
expecting 'b'

Agar shu “trial period” ni kattalashtirmoqchi bo’lsak, try kombinatorini ishlatishimiz kerak:

p = (try p1) <|> p2
 where ...

ghci> parseTest p "aa"
"a"

Ya’ni, megaparsecdagi try .. <|> .. bu bizi parserdagi .. <|> ..ga teng.

Yana esda saqlash muhim bo’lgan narsa: bu kutubxonalarda ba’zi funksiyalar boshqalaridan tezroq ishlaydi. Masalan, bizning tepadagi charP bu kutubxonalarada satisfy deb nomlanadi, lekin many . satisfy juda ham sekin ishlaydi. Uning o’rniga takeWhileP ishlatish kerak.

Pythonda ham parsy nomli parser kutubxona bor. Uning arxitekturasi huddi shu postdagiqada. Bu kutubxonalar haqida o’rganmoqchi bo’lsangiz ularning dokumentatsiyasini o’qishingiz mumkin.

Qo’shimcha

Butun Haskell faylni yuklab olish

Parserga birinchi urinish#

Kombinatorlar#

Ikkinchi urinish#

Kombinatorlar#

Applicative#

many, some#

Do-notation#

Lisp parser#

Lv tiliga parser#

Kutubxonalar#

Qo’shimcha#

Parserga birinchi urinish

Kombinatorlar

Ikkinchi urinish

Kombinatorlar

Applicative

many, some

Do-notation

Lisp parser

Lv tiliga parser

Kutubxonalar

Qo’shimcha