Saleh Askari | Programmer

بخش ۱: هدف و ایده اصلی تحلیل لغوی (Lexical Analysis)

وقتی شما یک کد برنامه‌نویسی می‌نویسید، از نظر کامپیوتر و سخت‌افزار، آن کد چیزی جز یک رشته طولانی از کاراکترهای پشت سر هم (شامل حروف، اعداد، فاصله‌ها، اینترها و تب‌ها) نیست.

مثال ورودی: فرض کن کدی شبیه به این داریم:

if (i == j)
    Z = 0;
else
    Z = 1;

دیدگاه کامپایلر: کامپایلر در اولین قدم این کد را به صورت یک رشته متنی خام شبیه به این می‌بیند: \tif (i==j)\n\t\tZ=0;\n\telse\n\t\tZ=1; (که در آن \t نشان‌دهنده کلید Tab و \n نشان‌دهنده خط جدید یا Enter است).

وظیفه تحلیل‌گر لغوی (Lexer / Scanner): این فاز وظیفه دارد این رشته کاراکتری طولانی را بخواند، فضاهای خالی (Whitespace) و کامنت‌ها را حذف کند و متن را به بخش‌های معناداری به نام توکن (Token) بخش‌بندی (Partition) کند. خروجی این فاز، جریانی از توکن‌ها (Stream of Tokens) است که به عنوان ورودی به فاز بعدی (Parser) داده می‌شود.

بخش ۲: توکن (Token) چیست؟

توکن یک دسته‌بندی نحوی (Syntactic Category) است.

مثال در زبان انسان: در زبان فارسی، کلمات را به دسته‌هایی مثل «اسم»، «فعل»، «صفت» و «حرف اضافه» تقسیم می‌کنیم.
مثال در زبان برنامه‌نویسی: کلمات کد را به دسته‌های زیر تقسیم می‌کنیم:
1. Identifier (شناسه): نام متغیرها و توابع (مثل foo, var1, Z). قانون کلی: رشته‌ای از حروف و اعداد که حتماً با یک حرف شروع می‌شود.
2. Integer (عدد صحیح): یک رشته غیرخالی از ارقام (مثل 0, 123, 45).
3. Keyword (کلمه کلیدی): کلمات رزرو شده زبان (مثل if, else, while, begin).
4. Whitespace (فضای خالی): توالی غیرخالی از فاصله‌ها، اینترها و تب‌ها.

تفاوت Token Class و String (مثال مهم صفحه ۴ و ۵):

یک «کلاس توکن» پایانی ندارد و می‌تواند شامل بی‌نهایت رشته باشد. مثلاً کلاس توکن Identifier شامل میلیون‌ها نام متغیر مختلف مثل x یا my_variable می‌شود. اما کلاس توکن Keyword معمولاً شامل یک مجموعه محدود و ثابت از کلمات (مثل خود کلمه if) است.

بخش ۳: چالش‌های فاز تحلیل لغوی (Issues in Lexical Analysis)

تقسیم کردن متن به توکن‌ها همیشه ساده نیست و کامپایلر با دو چالش بزرگ روبرو می‌شود:

چالش اول: نگاه به جلو (Lookahead)

گاهی اوقات کامپایلر نمی‌تواند بمحض دیدن یک کاراکتر تصمیم بگیرد که آن توکن چیست، بلکه باید به کاراکتر(های) بعدی هم نگاه کند.

مثال ۱ (عملگرها): فرض کن کامپایلر به کاراکتر = می‌رسد. آیا این توکنِ «انتساب» است؟ تا زمانی که کاراکتر بعدی را نبیند نمی‌داند! اگر کاراکتر بعدی هم = باشد، کل توکن برابر با == (عملگر مقایسه) می‌شود. اگر کاراکتر بعدی > باشد، تبدیل به => می‌شود.
مثال ۲ (زبان فرترن - یک مورد تاریخی عجیب): در زبان Fortran فضاهای خالی کاملاً نادیده گرفته می‌شدند! به این دو خط کد دقت کن:
1. DO 5 I = 1, 25 $\rightarrow$ این یک حلقه DO است که متغیر I را از ۱ تا ۲۵ تغییر می‌دهد.
2. DO 5 I = 1.25 $\rightarrow$ این یک دستور انتساب ساده است که مقدار 1.25 را درون متغیری به نام DO5I می‌ریزد! کامپایلر فرترن برای اینکه بفهمد با یک حلقه طرف است یا یک متغیر، مجبور بود کل خط را تا رسیدن به , یا . جلوتر بخواند (Lookahead طولانی) که کار را بسیار سخت می‌کرد.

چالش دوم: ابهام در دسته‌بندی (Ambiguities)

گاهی اوقات یک رشته کاراکتر می‌تواند بر اساس قوانین به چند مدل مختلف توکن‌بندی شود.

مثال: رشته if8 را در نظر بگیر.
حالت اول: کلمه کلیدی if به همراه عدد 8.
حالت دوم: یک متغیر یا شناسه یکپارچه به نام if8.
راهکار حل ابهام: کامپایلرها برای حل این مشکل دو قانون طلایی دارند:
1. قانون بلندترین تطابق (Maximal Munch / Longest Match): کامپایلر همیشه ترجیح می‌دهد بلندترین رشته ممکن را به عنوان یک توکن بردارد. پس if8 را یکپارچه به عنوان یک Identifier در نظر می‌گیرد.
2. قانون اولویت کلمات کلیدی (Rule Priority): اگر یک رشته هم زمان بتواند شناسه باشد و هم کلمه کلیدی (مثل کلمه if)، اولویت با کلمه کلیدی است.

بخش ۴: فرمالیزه کردن و تعریف لکسر با استفاده از عبارت‌های منظم (Regular Expressions - Regex)

برای اینکه به کامپایلر بفهمانیم چه چیزی توکن است و چه چیزی نیست، باید ساختار توکن‌ها را به زبان ریاضی تعریف کنیم. ابزار ریاضی این کار عبارت‌های منظم (Regex) است.

تعاریف پایه‌ای الفبا و زبان:

الفبا ($\Sigma$ - Sigma): یک مجموعه محدود از کاراکترها است. (مثلاً الفبای باینری ${0, 1}$ یا الفبای اسکی ASCII).
زبان (Language): مجموعه‌ای از رشته‌ها (Strings) روی یک الفبای مشخص است.

۳ عملگر اصلی در عبارت‌های منظم (قوانین صفحه ۱۸ تا ۲۷):

یک عبارت منظم ($R$) نمایانگر یک زبان ($L(R)$) است. پایه‌های این روابط به سه شکل اصلی هستند:

اتصال (Concatenation): نوشتن دو عبارت پشت سر هم.
- فرمول: $L(AB) = { ab \mid a \in L(A) \text{ and } b \in L(B) }$
- مثال: اگر $A = {a}$ و $B = {b}$ باشد، $AB = {ab}$.
اجتماع / انتخاب (Union / Alternation): استفاده از علامت $+$ یا $\mid$ به معنی «یا».
- فرمول: $L(A + B) = L(A) \cup L(B)$
- مثال: عبارت $a + b$ یعنی یا کاراکتر $a$ یا کاراکتر $b$.
تکرار / ستاره کلین (Kleene Closure): استفاده از علامت $*$. به معنی صفر یا چند بار تکرار شدن عبارت قبلی.
- فرمول: $L(A^*) = \bigcup_{i=0}^{\infty} L(A^i)$ (شامل رشته خالی یا $\epsilon$ نیز می‌شود).

اختصارات و علامت‌های کمکی (مهم برای ساده‌نویسی):

علامت مثبت ($A^+$): یعنی یک یا چند بار تکرار. فرمول: $A^+ = A A^*$ (دیگر شامل رشته خالی نمی‌شود).
علامت سوال ($A?$): یعنی صفر یا یک بار تکرار (اختیاری بودن). فرمول: $A? = A + \epsilon$.
محدوده یا Range ($[a-z]$): به معنی انتخاب یکی از کاراکترهای داخل این محدوده است. فرمول: $[a-z] = a + b + c + \dots + z$.

بخش ۵: مثال‌های کاربردی و بسیار مهم از تعریف توکن‌ها با Regex (صفحات ۳۰ تا ۴۰)

این بخش از جزوه دقیقاً همان جایی است که باید با مثال یاد بگیری چون پایه سوالات امتحانی است:

۱. تعریف شناسه (Identifier):

تعریف متنی: رشته‌ای از حروف یا ارقام که حتماً باید با یک حرف شروع شود.

فرمول با Regex: $$\text{letter} = [A-Za-z]$$ $$\text{digit} = [0-9]$$ $$\text{identifier} = \text{letter } (\text{letter} + \text{digit})^*$$
یک چالش مفهومی (صفحه ۳۵): آیا عبارت $(\text{letter}^* + \text{digit}^* )$ با عبارت $(\text{letter} + \text{digit})^* $ برابر است؟
- پاسخ خیر است! عبارت اول یعنی یا فقط حروف تکرار شوند (مثل aaaa) یا فقط اعداد (مثل 1111) و نمی‌تواند ترکیب متناوب داشته باشد. اما عبارت دوم اجازه می‌دهد حروف و اعداد کاملاً با هم ترکیب شوند (مثل a1b2).

۲. تعریف فضای خالی (Whitespace):

یک توالی غیرخالی از کاراکترهای فاصله (Blank)، خط جدید (\n) و تب (\t).

فرمول با Regex: $$\text{whitespace} = (\text{' '} + \text{'\n'} + \text{'\t'})^+$$

۳. تعریف شماره تلفن (Phone Numbers - صفحه ۳۷):

فرض کن می‌خواهیم شماره تلفنی شبیه به (650)-723-3232 را مدل‌سازی کنیم:

فرمول با Regex: $$\text{area} = \text{digit}^3 \quad \text{(۳ بار تکرار رقم)}$$ $$\text{exchange} = \text{digit}^3$$ $$\text{phone} = \text{digit}^4$$ $$\text{phone\_number} = \text{'(' } \text{area} \text{ ')-' } \text{exchange} \text{ '-' } \text{phone}$$

۴. تعریف آدرس ایمیل (Email Addresses - صفحه ۳۸):

برای مدلی مثل anyone@cs.stanford.edu:

فرمول با Regex: $$\text{name} = \text{letter}^+$$ $$\text{address} = \text{name } \text{'@'} \text{ name } \text{('.' name)}^+$$

۵. تعریف اعداد بدون علامت در زبان پاسکال (Unsigned Pascal Numbers - صفحه ۳۹ و ۴۰):

این یکی از جامع‌ترین مثال‌های جزوه است. اعدادی مثل 52 یا 3.14 یا 1E-5 (اعداد علمی):

فرمول تفکیک شده: $$\text{digit} = [0-9]$$ $$\text{digits} = \text{digit}^+$$ $$ \text{opt\_fraction} = (\text{'.' } \text{digits}) + \epsilon \quad \text{(بخش اعشاری اختیاری)}$$ $$ \text{opt\_exponent} = (\text{'E' } (\text{'+'} + \text{'-'} + \epsilon) \text{ digits}) + \epsilon \quad \text{(بخش توان علمی اختیاری)}$$
فرمول نهایی عدد: $$ \text{num} = \text{digits} \quad \text{opt\_fraction} \quad \text{opt\_exponent} $$

جمع‌بندی خلاصه فصل دوم:

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

مطالبی که مطالعه کردید تمام توسط هوش مصنوعی Google Gemini ترجمه و تهیه شده. در صورت نیاز به توضیح بیشتر قسمتی یا اصلاح قسمتی به بنده پیام بدید.

lecture 02