۲۳ - ۳درکِ فرایند پارس‌کردن

پارسر یه تابع‌ه که یه ورودیِ نوشتاری می‌گیره (ممکنه ‏‎String‎‏ باشه، یا نوع‌داده‌ای دیگه مثل ‏‎ByteString‎‏ یا ‏‎Text‎‏) و یه ساختار رو به عنوان خروجی برمی‌گردونه. اون ساختار برای مثال ممکنه یه درخت، یا یه نگاشت اندیس‌دار از مکان‌های مختلف در داده ِ پارس‌شده باشه. پارسرها با توجه به قواعدِ تعیین شده در یه گرامر (چه گرامر ِ زبان انسانی، زبان برنامه‌نویسی، یا یه فرمت مثلِ JSON)، ساختار رو بررسی می‌کنن.

یک ترکیب‌کننده‌ی پارسر، یه تابعِ سطح‌بالا هست که به عنوانِ ورودی‌هاش پارسر می‌گیره و یه پارسر ِ جدید خروجی میده. ممکنه توضیحِ کوتاهی که از ترکیب‌کننده‌ها در فصلِ جبرِ لاندا دادیم خاطرتون باشه. ترکیب‌کننده‌ها بیانیه‌هایی‌اند که هیچ متغیر آزادی ندارن.

پارسر تابع‌ه، پس ترکیب‌کننده‌ی پارسر یه تابعِ سطح‌بالا ِه که آرگومان‌هاش پارسِر اند. واسط تعاملی ِ ترکیب‌کننده‌ها معمولاً شبیهِ موند ِ ‏‎State‎‏‌هاست، یعنی دادنِ آرگومان‌ها می‌تونه به سبکِ ‏‎Reader‎‏ و ضمنی باشه. ترکیب‌کننده‌ها امکانِ خوداتکایی و چسبوندنِ ماژولار ِ پارسرها به همدیگه رو دارن تا برمبنای قواعدی پیچیده داده‌ها رو پارس کنن.

میشه پارس‌کردن برای کامپیوترها رو مشابهِ خوندنِ شما در دورانِ کودکی‌تون دونست. احتمالاً بهتون یاد داده بودن در حین خوندن، با انگشت‌تون حروف رو دنبال کنین. بعداً بجای حروف، لغت به لغت پیش می‌رفتین، بعد از اون هم با چشم‌هاتون دنبال می‌کردین. آخر سر هم یاد گرفتین ذهنی بخونین.

قیاس برای ‏‎Monad‎‏

اینجا ایده‌ی پارسینگ رو با چندتا کُد نشون میدیم. اول با نصبِ کتابخونه ِ ‏‎trifecta‎‏^* کار رو شروع می‌کنیم، و بعد یه مثالِ کوتاه از طرزِ کارش میزنیم. فعلاً یه کم با بی‌خیالی باهاش کار می‌کنیم، اما جلوتر از طراحیِ ‏‎trifecta‎‏ بیشتر صحبت می‌کنیم.

کد بنویسیم:

module LearnParsers where

import Text.Trifecta

stop :: Parser a
stop = unexpected "stop"

با ‏‎unexpected‎‏ میشه در پارسرهایی مثل ‏‎trifecta‎‏ که نمونه‌ای از تایپکلاسِ ‏‎Parsing‎‏ هستن خطا داد. اینجا به منظور نمایش می‌خوایم کاری کنیم که پارسر شکست بخوره.

نمایشِ چی؟

مرسی که پرسیدین! ایده‌ی کلیِ پارسر، حرکتِ یه جور نشانگر روی یه جریان ِ خطی از نوشتاره. در ساده‌ترین حالت، هر واحد مجرد از این جریان یک حرف یا اندیشه‌نگاشت^* ِه، ولی جلوتر که پیش میرین، بهتره نگرش‌تون به مسائلِ پارسینگ کلی‌تر بشه. این نشانگر شبیهِ خوندن با انگشت می‌مونه:

Julie bit Papuchon
^

حالا فرض کنیم لغتِ Julie رو پارس کردیم – اون ورودی رو مصرف کردیم، پس نشانگر میره روی bit:

Julie bit Papuchon
      ^

اگه اینجا انتظارِ bit رو نداشتیم، پارسر شکست می‌خورد و سرِ لغتِ bit پیغامِ خطا می‌گرفتیم. ولی اگه با موفقیت bit رو پارس و متعاقباً اون ورودی رو مصرف می‌کردیم، اینطوری میشد:

Julie bit Papuchon
          ^

چنین قیاسی خیلی دقیق نیست. یکی از سخت‌ترین مسائل در نوشتنِ پارسرها، بخصوص خودِ کتابخونه‌های پارسر، اینه که برنامه‌نویس همه چیز رو اونطور که براش مطلوبه به سادگی بیان کنه و در عین حال پارسر ِ نهایی سریع هم باشه.

برگردیم به کُد

با در نظر داشتنِ اون قیاسی که با یه نشانگر گفتیم، برگردیم به ماژولی که شروع کردیم.

اول یه تابعِ کوچولو درست می‌کنیم که فقط یک کاراکتر رو پارس می‌کنه، بعد اون رو با ‏‎stop‎‏ سکانس می‌کنیم (م. یا تسلسل میدیم. به عبارتِ دیگه، ‏‎stop‎‏ رو میذاریم جلوی اون پارسر) تا یک حرف رو بخونه و بعد بمیره:

-- ‎‏رو بخون‏‎ '1' ‎‏یک کارکتر مجرد‏‎
one = char '1'

-- ‎‏رو بخون، بعد بمیر‏‎ '1' ‎‏یک کاراکتر مجرد‏‎
one' = one >> stop
-- char '1' >> stop معادل با

برای ‏‎one'‎‏ از عملگر ِ تسلسل از ‏‎Monad‎‏ برای ترکیب ِ دو پارسر ِ ‏‎stop‎‏ و ‏‎char '1'‎‏ استفاده کردیم. با توجه به تایپِ ‏‎(>>)‎‏:

(>>) :: Monad m => m a -> m b -> m b

میشه قاطعانه فرض کرد که هرچی ‏‎char '1'‎‏ از بیانیه‌ی:

char '1' >> stop

برمی‌گردونه دور انداخته میشه. اما هر اثری که اجراییه ِ ‏‎m a‎‏ روی بافت ِ موندی میذاره باقی می‌مونه. به عبارتِ دیگه مقدارِ حاصل از تابعِ پارس دور انداخته میشه، اما اثر ِ "حرکت دادنِ نشانگر" باقی می‌مونه. "باعثِ شکست ِ پارسر شدن،" یکی دیگه از اثراتِ احتمالی‌ه.

یه کم شبیه...

‏‎State‎‏. به علاوه‌ی شکست. جدی میگیم، یه نگاه به تعریفِ تایپِ ‏‎Parser‎‏ بندازین:

type Parser a = String -> Maybe (a, String)

این رو میشه اینطوری خوند:

حالا تایپ‌های ‏‎Reader‎‏ و ‏‎State‎‏ رو به خاطر بیارین:

newtype Reader r a =
  Reader { runReader :: r -> a }

newtype State s a =
  State { runState :: s -> (a, s) }

اگه متقاعد شدین که ‏‎State‎‏ یه جور بسط از ‏‎Reader‎‏ ِه، و شباهتِ ‏‎Parser‎‏ با ‏‎State‎‏ هم می‌بینین، ادامه بدیم.

ایده‌ی تایپِ ‏‎Parser‎‏ اینه که با ‏‎State‎‏ یه ورودیِ نوشتاری قبول می‌کنه، و پارس ِ یه چیزی از اون نوشته منجر به یه حالت ِ جدید از جریانِ ورودی میشه؛ اون مقدارِ خروجی از حالت مستقل‌ه، و ‏‎Maybe‎‏ هم احتمالِ شکستِ پارسر رو به عهده داره.

اگه به پشت‌پرده‌ی یه تابعِ پارسینگ مثلِ ‏‎char‎‏ نگاه کنیم، الگویی مشابهِ ‏‎State‎‏ می‌بینیم (فقط دقت کنین با اینکه این کد به عنوان یه تابعِ پارس ِ کاراکتر می‌تونه کار کنه، خیلی ساده‌ست و کد منبع ِ هیچ کتابخونه ِ پارسینگ ِ مُدِرنی این شکلی نیست):

-- ؛char پیاده‌سازی ابتدایی برای
-- فقط برای نمونه، در همین
-- .وضعیت کار نمی‌کنه
char :: Char -> Parser Char
char c = 
  Parser $ \s ->
    case s of
      (x:xs) -> if c == x
                then [(c, xs)]
                else []
      _ -> []

میشد با ‏‎Maybe‎‏ احتمال شکست هم اضافه کنیم، ولی مهم نیست چون می‌خوایم از کتابخونه‌ای استفاده کنیم که خودش این کار رو برامون انجام داده؛ ‏‎char‎‏ هم حسابی بهینه کرده. فقط می‌خواستیم نشون بدیم که چطور تابع پشت‌پرده‌ی ‏‎s ->‎‏ زیرِ ‏‎Parser‎‏ قرار گرفته.

تایپِ پارسر ِ هاتون-مِیِر رو در نظر بگیرین:

-- Text.ParserCombinators.HuttonMeijer از
-- polyparse-1.11

type Token = Char
newtype Parser a =
  P ([Token] -> [(a, [Token])])

-- :همونه، فقط فرمت‌ش عوض شده
type Parser' a = String -> [(a, String)]

با این پارسر، برخلاف پارسر ِ قبلی (که ساده‌تره و رواجِ کمتری هم داره) میشه یه تعدادی از پارس‌های معتبرِ حاصل از ورودی رو گرفت. این پارسر از مدلِ ‏‎Maybe‎‏ قوی‌تره، اما دیگه از این طرح برای ترکیب‌کننده‌های پارسر در کتابخونه‌های محبوبِ هسکل استفاده نمیشه. با اینکه پیشرفت و کشفِ طرحهای جدید باعث تغییرات زیادی در کتابخونه‌های پارسینگ شدن، رابط تعاملی ِ بیشتر اونها در هسکل رفتاری شبیهِ ‏‎State‎‏ داره؛ از این لحاظ که پارس ِ هر چیزی، روی یک یا چند بخش از حالت یه اثر ِ قابل مشاهده میذاره.

معادل چنین چیزی در ‏‎State‎‏ اینه که هر ‏‎put‎‏ روی یه مقدارِ ‏‎State‎‏، برای اجراییه ِ بعدی در همون ‏‎Monad‎‏ قابل مشاهده باشه (برای امتحان کردنِ کُدِ زیر تو REPL، اول ‏‎Control.Monad.Trans.State‎‏ رو وارد کنین). این مثال‌ها از مدلِ ترانسفورمر ِ ‏‎State‎‏ استفاده می‌کنن، اما اگه اون T رو نادیده بگیرین، ایده‌ی کلی رو یاد می‌گیرین:

get :: Monad m => StateT s m s
put :: Monad m => s -> StateT s m ()
runStateT :: StateT s m a -> s -> m (a, s)

Prelude> runStateT (put 8) 7
((),8)
Prelude> runStateT get 8
(8,8)
Prelude> runStateT (put 1 >> get) 8
(1,1)
Prelude> (runStateT $ put 1 >> get) 0
(1,1)
Prelude> (runStateT $ put 2 >> get) 10021490234890
(2,2)
Prelude> (runStateT $ put 2 >> return 9001) 0
(9001,2)

حالا ‏‎put‎‏ یه مقدارِ واحد برمی‌گردونه (یه مقدارِ دورانداختنی) پس درهرصورت فقط برای اثری که میذاره حساب‌ش می‌کنیم. حالت رو تغییر میده ولی هیچ مقداری از خودش نداره. پس وقتی مقدارش رو دور میندازیم فقط اثرش روی حالت باقی می‌مونه. از طرفِ دیگه ‏‎get‎‏ اون مقدار رو بجای هردو جاهای ‏‎a‎‏ و ‏‎s‎‏ در توپل جاگذاری می‌کنه.

چنین چیزی خیلی شبیه وقتهایی‌ه که مثل بالا یه تابعِ پارسینگ مثلِ ‏‎char‎‏ رو با ‏‎stop‎‏ سکانس می‌کنیم. هیچ جوابِ واقعی‌ای از ‏‎char‎‏ بدست نمیاد، ولی حالت رو تغییر میده. اینجا حالت، مکانِ نشانگر در جریان ِ ورودی‌ه. راست‌ش رو بخواین، یه طرحِ مدرن و پخته‌ی پارسر در هسکل همونقدر براتون آشنایی داره که یکی از غارهای زیر پوسته‌ی یخ‌زده‌ی یکی از ماه‌های مشتری براتون آشناست. خیلی اون غار رو جدی نگیرین، ولی احتمالاً اینطوری فرض‌کردن یه فایده‌ای داشته باشه.

برگردیم به نظم سابق‌مون در کدنویسی

به سوی کدنویسی:

-- '2' و '1' دوتا کاراکتر بخون،
oneTwo = char '1' >> char '2'

-- ‎‏دوتا کاراکتر بخون،‏‎
-- ‎‏، بعد بمیر‏‎'2' ‎‏و‏‎ '1'
oneTwo' = oneTwo >> stop

testParse :: Parser Char -> IO ()
testParse p =
  print $ parseString p mempty "123"

آرگومانِ ‏‎p‎‏ یه پارسر ِه. دقیق‌تر بگیم، یه پارسر ِ کاراکتره. توابع ‏‎one‎‏ و ‏‎oneTwo‎‏ تایپ‌شون ‏‎Parser Char‎‏ هست. خودتون می‌تونین تایپِ ‏‎one'‎‏ و ‏‎oneTwo'‎‏ رو چک کنین.

به خاطرِ ابهامی که پیش میومد، لازم بود تایپِ ‏‎testParse‎‏ رو تعیین کنیم تا بشه چیزی که پارس کردیم رو نشون بدیم (‏‎Show‎‏ کنیم).

یکی از نکات کلیدی اینه که داریم با پارسرها مثلِ مقادیر برخورد می‌کنیم و ترکیب ِ اونها رو با توابعِ معمولی یا عملگر‌های ‏‎Applicative‎‏ و ‏‎Monad‎‏ انجام میدیم. اینجا ساختار ِ ‏‎Applicative‎‏ یا ‏‎Monad‎‏، خودِ ‏‎Parser‎‏ ِه.

بعد یه تابع می‌نویسیم که یه نوشته رو با یه پیشوندِ خط‌جدید (‏‎\n‎‏) به خروجیِ استاندارد (یا stdout) چاپ کنه، و اون تابع رو به عنوانِ بخشی از یه ‏‎main‎‏ که نشون میده تا نقطه‌ای که رسیده چی بدست آورده استفاده می‌کنیم.

pNL s =
  putStrLn ('\n' : s)

main = do
  pNL "stop:"
  testParse stop
  pNL "one:"
  testParse one
  pNL "one':"
  testParse one'
  pNL "oneTwo:"
  testParse oneTwo
  pNL "oneTwo':"
  testParse oneTwo'

اجراش کنیم و نتیجه‌هاش رو ببینیم. چون اینها برگ چای نیستن و بجاش حروفِ روی صفحه‌ی کامپیوتراند، اسم‌ش رو میذاریم کار علمی. اگه هنوز به ارزش علمی این کار متقاعد نشدین، اجازه دارین یه کت آزمایشگاهی بپوشین و خروجی رو با یه چاپگر ماتریس سوزنی چاپ کنین. بعضی از شما شاید اصلاً ندونین یه چاپگر ماتریس سوزنی چی هست.^*

‏‎main‎‏ رو اجرا کنین و ببینین چی میشه:

Prelude> main

stop:
Failure (interactive):1:1: error: unexpected
    stop
123<EOF>
^

آناً بدون اینکه هیچ ورودی‌ای مصرف کنه شکست خورد، به همین خاطر اون نشانگر در پیغامِ خطا، اولِ نوشته‌ست.

جواب بعدی:

one:
Success '1'

یه کاراکتر مجرد رو پارس کردیم، رقمِ ۱. اینکه می‌دونیم موفق شدیم، جواب‌ه. اما مابقیِ جریان ِ ورودی چطور؟ خوب اون چیزی که باهاش پارسر رو اجرا کردیم، باقیِ ورودی رو انداخت زمین. راه‌هایی برای تغییر چنین رفتاری وجود دارن که تو تمرین‌ها توضیح میدیم.

بعدی:

one':
Failure (interactive):1:2: error: unexpected
    stop
123<EOF>
 ^

یک کاراکتر رو با موفقیت پارس کردیم، ولی چون از ‏‎>>‎‏ برای سکانس کردن با ‏‎stop‎‏ اسفاده کرده بودیم، مقدارِ پارس‌شده رو انداختیم. یعنی به خاطر موفقیتِ پارسر ِ قبلی، نشانگر یه کاراکتر رفته جلو. ‏‎trifecta‎‏ میگه پارسر کجا شکست خورد، که خیلی کمک می‌کنه.

و جواب آخر:

oneTwo:
Success '2'

oneTwo':
Failure (interactive):1:3: error: unexpected
    stop
123<EOF>
  ^

مشابه قبلی‌هاست، فقط دو کاراکتر رو مستقل از هم پارس کردیم. اگه نخوایم اولین کاراکتری که پارس کردیم رو دور بندازیم، و در عوض ‏‎"12"‎‏ رو پارس کنیم چطور؟ تمرینِ زیر!

تمرین‌ها: تمرینِ پارسینگ

آنتراکت: پارس ِ بیشتر

بیاین با این پارسرها بازی کنیم! معمولاً برای اجرای پارسرها از تابعِ ‏‎parseString‎‏ استفاده می‌کنیم، اما اگه راهی پیدا کردین که باهاش راحت‌تر بودین، ازش استفاده کنین! یه ذره پارسینگ نوشتیم تا یه کم بیشتر با قضیه آشنا بشین:

λ> import Text.Trifecta
λ> :t char
char :: CharParsing m => Char -> m Char
λ> :t parseString
parseString
  :: Parser a
  -> Text.Trifecta.Delta.Delta
  -> String
  -> Result a
λ> let gimmeA = char 'a'
λ> :t parseString gimmeA mempty
parseString gimmeA mempty :: String -> Result Char

λ> parseString gimmeA mempty "a"
Success 'a'
λ> parseString gimmeA mempty "b"
Failure (interactive):1:1: error: expected: "a"
b<EOF>
^

λ> parseString (char 'b') mempty "b"
Success 'b'
λ> parseString (char 'b' >> char 'c') mempty "b"
Failure (interactive):1:2: error: unexpected
    EOF, expected: "c"
b<EOF>
 ^
λ> parseString (char 'b' >> char 'c') mempty "bc"
Success 'c'
λ> parseString (char 'b' >> char 'c') mempty "abc"
Failure (interactive):1:1: error: expected "b"
abc<EOF>
^

به نظر میرسه بجای اینکه مجبور باشیم بیت به بیت پارسِرهای کاراکتر رو پشت هم سوار کنیم. باید یه راهی برای اینکه بگیم "این نوشته رو پارس کن" وجود داشته باشه، اینطور نیست؟ از قرار معلوم، وجود داره:

λ> parseString (string "abc") mempty "abc"
Success "abc"
λ> parseString (string "abc") mempty "bc"
Failure (interactive):1:1: error: expected: "abc"
bc<EOF>
^

λ> parseString (string "abc") mempty "ab"
Failure (interactive):1:1: error: expected: "abc"
ab<EOF>
^

یک پارسر به تنهایی قرار نیست تمام ورودی‌ش رو مصرف کنه – فقط مقداری از نوشته رو که برای تولید یه مقدار از تایپِ درخواستی لازم داره مصرف می‌کنه.

λ> parseString (char 'a') mempty "abcdef"
Success 'a'
λ> let stop = unexpected "stop pls"
λ> parseString (char 'a' >> stop) mempty "abcdef"
Failure (interactive):1:2: error: unexpected
    stop pls
abcdef<EOF>
 ^
λ> parseString (string "abc") mempty "abcdef"
Success "abc"
λ> parseString (string "abc" >> stop) mempty "abcde"
Failure (interactive):1:4: error: unexpected
    stop pls
abcde<EOF>
   ^

با ‏‎trifecta‎‏، مقادیرِ ‏‎ByteString‎‏ که با ‏‎UTF-8‎‏ کدبندی شدن هم میشه پارس کرد:

λ> import Text.Trifecta
λ> :t parseByteString
parseByteString
  :: Parser a
  -> Text.Trifecta.Delta.Delta
  -> Data.ByteString.Internal.ByteString
  -> Result a
λ> parseByteString (char 'a') mempty "a"
Success 'a'

بازی دیگه بسه. برگردیم سراغ چیزای جدی.