بیاید تا عبارت 4w5d12h50m13s رو tokenize و parse کنیم

یکی از دروس تخصصی و خیلی زیبای رشته دانشگاهی مهندسی کامپیوتر درس نظریه‌ زبان‌ها و ماشین‌هاست.
در واقع این درس به همراه درس ریاضیات گسسته، دو درس اصلی علوم کامپیوتر هستند، که البته در علوم کامپیوتر با عنوان نظریه محاسبات تدریس می‌شود.
هدف درس نظریه محاسبات یا نظریه زبان‌ها اینست که حد و مرز توانایی ماشین‌‌ها برای انجام محاسبات را بفهمیم. در ابتدا با ساده‌ترین زبان‌ها شروع می‌کنیم و در پایان به زبان‌ها بازگشتی می‌رسیم که با ماشین تورینگ تشخیص داده می‌شوند.
در نهایت می‌گوییم هر مسئله‌ی محاسبات ریاضی را می‌توان توسط یک زبان مدلسازی کرد. مثلا این مسئله را در نظر بگیرید: آیا یک عدد اول است یا خیر؟ مسئله‌ی اول بودن یک عدد را می‌توانیم به شکل دیگری مطرح کنیم. آیا یک عدد متعلق به مجموعه‌ی اعداد اول است یا خیر؟ حال باید ماشینی طراحی کنیم که زبانی که شامل همه اعداد اول است را شناسایی کند. پس مسئله بررسی اول بودن یک عدد معادل است با طراحی ماشین برای تشخیص اول بودن عددی که به صورت رشته به ماشین داده می‌شود. حال می‌توانیم با استفاده از یک ماشین تورینگ (و کد گذاری اعداد) این کار را انجام دهیم.
پس می‌توانیم الگوریتم را بر اساس تشخیص پذیری در ماشین تورینگ تعریف کنیم.
همچنین اثبات می‌شود که مسئله‌هایی وجود دارند که برای آنها هیچ الگوریتمی وجود ندارد و یا به عبارت دیگر هیچ ماشین تورینگی برای زبان معادل آنها وجود ندارد. این مسئله‌ها تصمیم ناپذیرند.
پس همه‌ی علم محاسبات در مورد پیدا کردن حد و مرز توانایی محاسبات توسط ماشین‌هاست.[3]

یکی از منابع این درس (که استاد ما هم همین منبع رو استفاده کردن) این کتابه:

Linz, Peter, and Susan H. Rodger. An introduction to formal languages and automata. Jones & Bartlett Learning, 2022

در منطق، ریاضیات، علوم کامپیوتر و زبان‌شناسی، نظریهٔ زبان‌ها به مطالعهٔ زبان‌های صوری و دسته‌بندی آنها می‌پردازد. در نظریهٔ زبان‌ها تنها جنبه‌های نحوی زبان‌ها (یعنی الگوهای ساختاری درونی آنها) تجرید و انتزاع می‌شود و به معنای جملات و ... اهمیتی نمی‌دهیم (مثلاً جملهٔ «رنگ آسمان قرمز است» ممکن است در یک زبان صوری جملهٔ مورد قبولی باشد).

یک زبان تشکیل شده از کلماتی‌ست که حروف آن، توکن‌هایی گرفته شده از یک الفبای مشخص هستند که تحت یک سری قانون خاص به اسم گرامر به صورت خوش‌ساخت ساخته شده است.[۱]

در علوم نظری رایانه، نظریهٔ اتوماتا (به انگلیسی: Automata theory) یا نظریهٔ ماشین‌ها عبارت است از بررسی ریاضی ماشین‌های محاسبه‌گر انتزاعی و توانایی‌های آن‌ها برای حل مسایل. به این ماشین‌های انتزاعی اتوماتا گفته می‌شود. این نظریه بسیار نزدیک به نظریهٔ زبان صوری است. به‌طوری‌که اتوماتا اغلب توسط دستهٔ زبان‌های رسمی قابل تشخیص دسته‌بندی می‌شوند. اتوماتا نقش اساسی در طراحی کامپایلر و تجزیه کردن (parsing) ایفا می‌کند. زبان‌هایی که توسط این ماشین‌ها بررسی می‌شوند زبان‌های فرمال هستند.[۲]

در یک گروه پرسش و پاسخ پایتونی در تلگرام (PyFarsi@) یکی از اعضا یک سوالی پرسید که دیدم میشه یکمی مباحث نظریه زبان‌ها و ماشین‌ها رو باهاش بررسی کرد و بعدش اون‌ها رو کد کرد.

پس بیاید تا سوال رو ببینیم و بعدش راه‌حلش رو هم به صورت تئوری و هم به صورت عملی (کدی) بنویسیم.

سلام بچه‌ها
ببخشید من میخوام از کاربر یک ورودی بگیرم و بعدش با توجه به یک سری اصول اون رو بفهمم و اگه اشتباه بود ارور بدم و اگه نبود اون رو تبدیل به اطلاعات قابل استفاده بکنم. ورودی من اینه:
4w13d16h10m14s
که میخوام متوجه بشم که بهم گفته ۴ هفته و ۱۳ روز و ۱۶ ساعت و ۱۰ دقیقه و ۱۴ ثانیه.
ترتیب هم برام مهم نیست یعنی میتونه اول ثانیه بگه بعد هفته بگه و... صرفا چیزی که برام مهمه اینه که یک عدد و سپس یه حرف باید بهم بده.

نوشتن عبارت منظم (regular expression)

اگه دقت بکنید، ما با یک ساختار نظام‌مند طرف هستیم: «عددحرف | عددحرف | عددحرف‌ | ...» که چون نظام‌مند هست میتونیم براش یک زبان و عبارت منظم بنویسیم، سپس برای اون عبارت منظم یک DFA یا NFA بنویسیم، و اون رو تبدیل به کد کنیم. این دقیقا کاری هست که برای طراحی کامپایلر‌ها انجام میدن (البته خییلی پیشرفته‌تر و حرفه‌ای‌تر.)

اولین چیزی که نیاز داریم الفبای زبانمونه. الفبای زبان ما از حروف زیر تشکیل شده:

۰، ۱، ۲، ...، ۹ و w, d, h, m و s.

در واقع در نظریه زبان‌ها ما به تمام الفبامون میگیم یک حرف (letter) و مجموعه‌ی الفبای ما میشه مجموعه سیگما

به علت اینکه جلوتر ما با اعداد و حروف به صورت جداگانه کار داریم بیاید تا مجموعه‌ی سیگما به صورت اجتماع ۴ تا مجموعه‌ی دیگه بنویسیم:

که مجموعه‌‌های اعداد مثبت غیر صفر (positive)، مجموعه‌ی ارقام (digits) و مجموعه‌ی حروف (letters) رو داریم.

حالا باید عبارت منظم (regular expression) این زبان رو بنویسیم. اگه نمیدونید عبارات منظم چی هستن یه سر به این لینک بزنید و بیاید

حالا کمی عبارتی که بهمون داده شده رو تفسیر کنیم و کم کم عبارت منظمش رو بنویسیم.

توی عبارت ما یک الگوی مشخص می‌بینیم: «عددحرف» و کل عبارت ما میشه ۱ یا چند تا از این «عددحرف»ها پس ما اول باید برای «عددحرف» یک عبارت منظم بنویسیم.

اگه دقت کنید میتونیم اینجوری بگیم که قسمت عدد این تیکه، میتونه اعدادِ تک رقمی (از ۱ تا ۹) و یا ۲ رقمی، ۳ رقمی و... باشن، و با صفر هم نمیتونن شروع بشن (یعنی ۰۰۱۳ رو معتبر نمیدونیم) پس میشه چنین چیزی براش نوشت:

که عملگر dot در اینجا به معنی concatenation هست. یعنی دو تا حرف رو بهم بچسبونیم. و آوردن اسم مجموعه‌ها یعنی یکی از اعضای اون‌ها.

این عبارت نشون میده اولین رقم میتونه از بین اعداد ۱ تا ۹ انتخاب بشه و رقم بعدی میتونه از بین ۰ تا ۹ انتخاب بشه، این رو هم یادمون باشه که چیزی که الزامیه حضور یک رقمه و این یعنی تعداد رقم‌ها باید بزرگ‌تر مساوی یک باشه.

خب ما که حضور اولین رقم از مجموعه‌ی p رو تضمین کردیم، پس تعداد رقم‌های بعدش میشن بزرگ‌تر مساوی صفر که این مفهوم رو در عبارات منظم با این نوتِیشن نشونش میدیم:

این شد قسمت «عدد» از «عددحرف»مون.

قسمت حرفش هم خیلی راحته، بعد از هر عددی، *باید* یکی از حروف مجموعه اِل حاضر باشن که میشه اینجوری نشونش داد:

یا برای واضح‌تر نشون دادنش اینجوری:

که عملگر pipe میشه یا این یا این یا این، یعنی تنها یکی از اینا اجازه دارن که حضور داشته باشن.

این هم قسمت «حرف» از «عددحرف»مون

حالا وقشته که این دو رو بهم concat کنیم:

اینم شد عبارت منظم «عددحرف» ما.

اما کار ما هنوز با عبارت منظم تموم نشده، اگه دقت کنید این عبارت فقط یک دونه از «عددحرف»‌ها تولید میکنه؛ اما چیزی که به ما میدن میتونه بیشتر از یکی هم از این «عددحرف»‌ها داشته باشه که عبارت منظم نهایی ما میشه:

عملگر + هم مثل عملگر * هست ولی حضور یک عبارت رو تاکید و تضمین میکنه ولی * میشه صفر یا بیشتر.

کشیدن ماشین متناهی (DFA)

حالا، برای راحت‌‌تر شدن فهمیدن عبارت منظم، میتونیم از روی r، یک DFA طراحی کنیم.

برای مطالعه‌ی DFA میتونید یه سر به این لینک بزنید:

و DFA ما (که از روی عبارت منظممون کشیدمش) میشه:

و اما چرا این؟ بیاید تا بررسیش کنیم:

1. اول از همه state شروع هست که همه‌ی automataها اون رو دارن،
2. سپس ورودی ما میتونه از بین عدد ۰، یک حرف (مجموعه L) و یکی از اعداد ۱ تا ۹ (مجموعه p) باشه
3. در ابتدا، ۰ و یک حرف قابل قبول نیستن و ما وارد یک تله میشیم که هررر ورودی دیگه‌ای بهش بدیم فقط به خودش برمیگرده. این یک تکنیک برای نوشتن DFAهاست که بگیم دیگه از این به بعد ورودی کاملا غلطه
4. حالا اگه ورودی از مجموعه‌ی p بود وارد digits میشیم، الان یک رقم عدد داریم که غیر صفره -> یعنی یکی شرط وجود عدد در عبارت «عددحرف» رو رعایت کردیم. و یه حلقه روی این state داریم از بین اعدا ۰ تا ۹ میتونه هیچ و یا هرر چی دلش خواست ورودی دریافت کنه
5. به محض اینکه یک حرف دریافت کردیم وارد success میشیم. این یعنی یک ترکیب «عددحرف» دریافت کردیم.
6. حالا باز دوباره مثل state عه شروع ما میتونیم از بین ۰ و حرف و اعداد بین ‍۱ تا ۹ ورودی دریافت کنیم که باز هم مثل state عه شروع فقط میتونیم از اعداد داخل مجموعه‌ی p چیزی رو قبول کنیم و در غیر این صورت باید به تله بریم.

این هم ماشین متناهی این سوال. حالا باید بریم و کدش رو بنویسیم :)

بررسی کد‌های tokenizer

اول از همه بیاید یک دیکشنری از حروفی که توی الفبامون هستن و کلمه‌ی نظیرشون بسازیم:

سپس برای کار با توکن‌های تولید شده و همچنین type annotation یک کلاس این چنینی می‌نویسیم:

اما برسیم به tokenizer 😁

تابع tokenize

اول کد تابع رو ببینیم یبار و بعدش تیکه به تیکه اون رو بررسی می‌کنیم:

اِستیت start

اگر به DFAمون نگاه کنیم در state شروع، یک دوراهی داریم:

1. اینکه یک عدد از بین مجموعه‌ی اعداد غیر صفر بگیره
2. یا اینکه ۰ یا یک حرف دریافت کنه

مورد دوم رو توی این خطوط هندل کردیم:

که خروجی‌هاشون:

و

استیت digits

فرض کنیم از state عه start با دریافت یک عدد از بین مجموعه‌ی p با موفقیت عبور کردیم به state عه digits رسیدیم. حالا می‌تونیم هر چقدر که بخوایم عدد از ورودی دریافت کنیم، که با این تیکه کد اون رو پیاده‌سازی کردیم:

که واسه‌ی توضیح واضح‌ترش یه مثال رو توی دیباگر ببینیم:

اگر برای مثال ورودی ما فقط عدد باشه، DFA ما وقتی که تمام رقم‌ها رو دریافت کرد، همونجا توی state عه digits میمونه و دیگه تکون نمیخوره که نشونه اشتباه بودن ورودیه.

اما توی کد چی کار کردیم، من اومدم و این تابع رو با ورودی 143 صدا زدم. این حلقه دونه دونه کاراکتر از ورودی میگیره و چک میکنه آیا عدد هستن یا خیر، اگه بودن اون‌ها رو به digits اضافه میکنه و شمارنده‌ی indexها رو یکی زیاد میکنه.

مثل الان، ما هیچ حرفی بعد از این اعداد نداریم و وقتی می‌خوایم به ایندکس ۳ دسترسی پیدا کنیم خطای IndexError میگیریم و یک SyntaxError رِیز میکنیم و میگیم:

اما اگه بعد از اعداد یک حرفی بود:

ما حرف رو میگیریم و توی letter ذخیره می‌کنیم و برای وارد شدن به state عه success آماده میشیم.

حالا وقت اینه که چک کنیم حرفی که دریافت کردیم، از بین حروف الفبامون هست یا خیر:

که اگه اون حرف از بین حروف مجاز نبود:

استیت success

حالا که هم ارقام را داریم و هم یک حرف درست، وقتشه که توکنمون رو درست کنیم و تابع رو برای ادامه‌ی رشته‌مون صدا بزنیم تا این روندی که توی استیت‌های بالاتر گفتیم برای کل رشته‌مون تکرار بشه:

خط ۶۱ کارش اینه:
ببینید ما تا الان تا index عه iام رشته‌مون رو خوندیم و اون رو tokenize کردیم، حالا میخوایم که از index بعدش به بعد رو به تابع‌مون پاس بدیم تا ترکیب «عددحرف» بعدی رو برامون پیدا کنه، پس ما رشته رو slice میکنیم و از اون ایندکس i به بعد رو جدا و به تابع‌مون پاس می‌دیم.

وقتی هم که کل رشته‌مون رو گذر کردیم می‌رسیم، این اسلایس کردن برای ما یک رشته خالی تولید میکنه که وقتی پاسش بدیم به تابع، شرطِ base case ما:

اجرا میشه و یک لیست از Tokenها در نهایت بازگردانده میشه.

بررسی کد‌های parser

بعد از نوشتن tokenizer ما باید توکن‌های تولید شده رو parse کنیم و معناشون رو متوجه بشیم.

اول از همه کد پارسر این مسئله رو ببینیم:

این ورودی رو در نظر بگیرید:

tokenizer(&quot2w1d2d3d5s4d7h&quot)

ملاحظه می‌شود که 1d و 2d و 3d و 4d همگیشان عبارت‌های «عددحرفی‌» هستند که راجع به روز صحبت می‌کنند. ما در تابع parse اومدیم و یک دیکشنری از کلید‌ها (که days و weeks و...) هستند درست می‌کنیم و مقدار این کلید‌ها میشن اون اعدادی که توی توکن‌ها دخیره هستن.

علی که در اولین خط‌های این فایل این دیکشنری رو ساختیم:

و این مقادیر رو به عنوان valueهای این کلید‌ها انتخاب کردیم اینه که signature عه تایپ timedelta اینجوریه:

و با آنپک کردن این دیکشنری براحتی میتونیم این تایپ رو instantiate کنیم و اون رو برگردونیم :)

نمونه‌هایی از خروجی‌های این کد:

تمامی عکس‌ها و کد‌هایی که در این مقاله استفاده شدن در این ریپازیتوری:

قابل دسترسی هستن.

نوشتنی‌ها و DFA در پوشه‌ی docs قرار دارند. کد‌های اصلی در timetp.py و تست‌هاش در tests.py

برای اجرا کردنش هم میتونید ریپازیتوری رو فورک کنید و سپس در پوشه‌ای که پوشه‌ی ریپازیتوری هست، با این دستور help اون رو ببینید:

$ python -m timetp help

این هم مقاله‌ی نوشتن یک tokenizer و یک parser کوچیک برای یک عبارت منظم :)

[۱]: https://en.wikipedia.org/wiki/Formal_language
[۲]: https://en.wikipedia.org/wiki/Automata_theory
[۳]: از کلام دکتر آرش شفیعی، عضو هیئت علمی دانشگاه اصفهان (http://fce.ui.ac.ir/~a.shafiei)