مروری بر lex و yacc

[fond]

توی این متن کوچولو یه نگاه ساده ای به دو ابزار lex  و yacc خواهیم داشت. چون این متن فقط برای آشنایی خوانندگان هست ما با این دو ابزار کار میکنیم وگرنه در دنیای واقعی، شما باید از نمونه های پیشرفته تر این ابزارها یعنی bison و flex استفاده کنید. این ابزارها معمولا برای طراحی کامپایلر ها و خوندن و تجزیه کردن فایل‌های پیکربندی استفاده میشن. پس آشنایی ابتدایی با زبان سی و کامپایلر ها لازم هست.

lex و yacc چی هستند؟
این ابزارها برای طراحی کامپایلرها استفاده میشن و با اونها میشه گرامرهای پیچیده ای رو تجزیه و تحلیل کرد. اگر میخواید یه کامپایلر بنویسید یا یه فایل پیکربندی پیچیده (مثل فایل فایل پیکربندی bind) رو تجزیه و تحلیل کنید، میتونید از این ابزارها استفاده کنید.

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

کد: [انتخاب]

Definition section
%%
Rules section
%%
C code section
این بخش ها توسط علامت %% از هم جدا شدند. توی قسمت Definition section ما میتونیم یه سری ماکرو دلخواه تعریف کنیم یا اینکه فایل‌های هدر مورد نیاز رو توی برنامه درج کنیم. توی قسمت Rules section که قسمت اصلی فایل هم هست، ما اون الگو های مورد نظرمون رو به lex معرفی می‌کنیم و تعیین میکنیم که اگر این الگو ها پیدا شدند، چه عملی باید انجام بشه.

توی قسمت C code section هم هر کدی بنویسیم به همون صورت توی خروجی قرار میگیره.
بذارید با یه مثال ادامه بدیم:

کد: [انتخاب]

%{
#include <stdio.h>
%}

%%
stop    printf("Stop command received\n");
start   printf("Start command received\n");
%%
کد بالا از چند قسمت تشکیل شده و در حقیقت یه برنامه c هست. قسمت اول به این صورت هست:

کد: [انتخاب]

%{
#include <stdio.h>
%}
هر چیزی که بین %{ و %} قرار بگیره به همون صورت توی برنامه خروجی قرار میگیره. چون توی ادامه مثال ما میخوایم از printf استفاده کنیم این فایل رو درج کردیم. دو قسمت بعدی فایل توسط علامت %% از هم جدا شدند.

توی قسمت دوم تعریف شده که هر جا عبارت stop رو دیدی، پیغام Stop command received رو چاپ کن. یا هر جا کلمه start رو دیدی، عبارت Start command received رو چاپ کن.

توی مثال بالا، قسمت آخر هم خالی هست.

خب کد بالا رو توی یه فایل با پسوند l. ذخیره کنید و اون رو به این صورت کامپایل کنید:

کد: [انتخاب]

lex example1.l
cc lex.yy.c -o example1 -ll
که فایل اجرایی نهایی example1 نام داره که شما میتونید اون رو از طریق ترمینال اجرا کنید. بعد از اینکه اجرا کردید، برنامه صبر میکنه تا شما یه چیزی تایپ کنید و کلید اینتر رو بزنید. بعدش هر چیزی که تایپ کردید رو دوباره بهتون نشون میده. اما اگه کلمه start یا stop رو تایپ کنید، برنامه پیغامهای Stop command received و Start command received رو برای شما چاپ میکنه. به این صورت ما تونستیم از ورودی، کلمات start و stop رو تشخیص بدیم و بر اساس اونها یه عمل خاصی که همون چاپ پیغام بود رو انجام بدیم. همینطور دیدیم که هر عبارت دیگه ای که برای برنامه ناشناخته باشه، به همون صورت توی خروجی چاپ میشه.

شاید تعجب کنید که چرا این برنامه ما  تابع main نداشت. خب این تابع قبلا برای ما توی کتابخانه libl تعریف شده. و به همین دلیل ما موقع کامپایل با سوئیچ -ll برنامه رو به این فایل لینک کردیم. البته میتونیم از این تابع از پیش تعریف شده استفاده نکنیم و و خودمون یکی بنویسیم.

خب حالا با یه مثال پیشرفته تر ادامه میدیم. توی مثال قبلی ما از یه الگوی ساده استفاده کردیم (همون کلمات start و stop) اما ما میتونیم از هر الگوی دیگه ای استفاده کنیم و حتی میتونیم از regex ها برای تظبیق این الگو ها استفاده کنیم. توی این مثال قصد داریم تشخیص بدیم که کاربر یه عدد وارد کرده یا یک کلمه. اگر عدد وارد کرده بود پیغام NUMBER و اگر کلمه وارد کرده بود پیغام WORD رو چاپ کنیم.

کد: [انتخاب]

%{
#include <stdio.h>
%}

%%
[0123456789]+           printf("NUMBER\n");
[a-zA-Z][a-zA-Z0-9]*    printf("WORD\n");
%%

متاسفانه توضیح در مورد regex ها از حوصله این متن کوتاه خارج هست. برنامه رو مانند قبل کامپایل کنید و اینبار یه همچین چیزهایی رو امتحان کنید:

کد: [انتخاب]

$ ./example2
foo
WORD

bar
WORD

123
NUMBER

bar123
WORD

123bar
NUMBER
WORD
نکته دیگه ای که شاید باعث تعجب شما بشه خطوط خالی اضافه توی خروجی هست. خب در این مورد باید بگیم که وقتی شما کلید اینتر رو فشار میدید، یه کاراکتر n\ به برنامه ارسال میشه و این کاراکتر به همون صورت هم توی خروجی چاپ میشه و lex این کاراکتر رو برای شما حذف نمیکنه.

حالا فرض کنید ما یه فایل پیکربندی پیچیده به این صورت داریم و میخوایم اون رو تجزیه کنیم:

کد: [انتخاب]

logging {
        category lame-servers { null; };
        category cname { null; };
};

zone "." {
        type hint;
        file "/etc/bind/db.root";
};
خب توی فایل بالا چند نوع «نشانه» وجود داره که ما باید اونها رو تشخیص بدیم.

یکی کلمات کلیدی zone و type که ما اسم این کلمات رو WORD میذاریم.
اسامی فایلها مثل '/etc/bind/db.root'
کاراکتر نقل و قول برای رشته ها
براکت باز
براکت بسته
سمی کالن

همینطور ما باید فضای خالی و کاراکتر خط جدید یا همون n\ رو تشخیص بدیم و اون رو نادیده بگیریم.
خب فایل lex به این صورت میشه:

کد: [انتخاب]

%{
#include <stdio.h>
%}

%%
[a-zA-Z][a-zA-Z0-9]*    printf("WORD ");
[a-zA-Z0-9\/.-]+        printf("FILENAME ");
\"                      printf("QUOTE ");
\{                      printf("OBRACE ");
\}                      printf("EBRACE ");
;                       printf("SEMICOLON ");
\n                      printf("\n");
[ \t]+                  /* ignore whitespace */;
%%
وقتی که کد بالا رو کامپایل کنیم و فایل پیکربندی رو بهش بدیم، این خروجی رو تحویل میگیریم:

کد: [انتخاب]

WORD OBRACE
WORD FILENAME OBRACE WORD SEMICOLON EBRACE SEMICOLON
WORD WORD OBRACE WORD SEMICOLON EBRACE SEMICOLON
EBRACE SEMICOLON

WORD QUOTE FILENAME QUOTE OBRACE
WORD WORD SEMICOLON
WORD QUOTE FILENAME QUOTE SEMICOLON
EBRACE SEMICOLON
خب این فایل برای ما نشانه گذاری شد و تونستیم این نشانه ها رو تشخیص بدیم. این دقیقا جایی هست که برنامه yacc وارد میشه ....

البته مبحث lex هنوز تموم نشده و ادامه داره و من فعلا این پست رو ذخیره میکنم تا به موقع بر اثر قطعی برق از بین نره ....
منابع رو هم سر فرصت مینویسم

[fond]

خب یه مرور کلی داشته باشیم:

ما اول اومدیم یه فایل lex نوشتیم که در کلی ترین حالت این فایل دو تا ستون داشت. ستون سمت چپ و ستون سمت راست. ستون سمت چپ یه «الگو» رو مشخص میکرد و ستون سمت راست یه «دستور» رو. هر جایی که اون الگو از توی ورودی تشخیص داده میشد، دستوری که جلوش نوشته شده هم اجرا میشد. مثلا دیدیم که اگر الگوی "stop" دیده میشد، دستور printf ای که جلوش بود اجرا میشد و پیغام Stop command received چاپ میشد. حالا توی این پست میخوایم کارهای پیشرفته تری انجام بدیم.

خب مثال پیشرفته تر بعدی، برنامه ای هست که یه فایل ورودی رو میگیره، تعداد کاراکتر‌های این فایل رو به همراه تعداد خطوط این فایل چاپ می‌کنه:

کد: [انتخاب]

%{
#include <stdio.h>
           int num_lines = 0, num_chars = 0;
%}

%%
\n      ++num_lines; ++num_chars;
.       ++num_chars;

%%
main()
   {       
           yylex();
           printf( "# of lines = %d, # of chars = %d\n",
                   num_lines, num_chars );
   }

خب تفاوت این مثال رو با مثال قبل مرور می‌کنیم. توی این مثال ما توی قسمت اول فایل دو تا متغیر تعریف کردیم num_lines و num_chars که هر دو برابر صفر مقدار دهی شدند. توی قسمت دوم فایل ما دو تا الگو تعریف کردیم. الگوی اول (n\) کاراکتر خط جدید رو شناسایی میکنه. و ما از این کاراکتر برای شمارش تعداد خطوط استفاده می‌کنیم. به محض اینکه این کاراکتر توی فایل ورودی پیدا شد، متغیرهای num_chars و num_lines افزایش پیدا می‌کنند. توی خط بعد ما یه الگو (.) تعریف کردیم که همونطور که میدونید این الگو با تمام کاراکتر ها منطبق میشه و بنابراین به ازای هر کاراکتر متغیر num_chars یکی بیشتر میشه.

توی همه مثال‌های قبلی ما از تابع main از قبل تعریف شده استفاده کردیم. اما این مثال ما یه تابع main مجزا نوشتیم و دیگه از تابع پیشفرض استفاده نکردیم. نکته اینکه توی این تابع main باید تابع yylex صدا زده بشه. این خیلی مهم هست که این تابع فراخوانی بشه.

توی دو خط بعدی هم ما به آسانی محتویات متغیر‌های num_chars و num_lines رو چاپ کردیم.
امیدوارم همه این مثالها دید کلی نسبت به lex رو به شما داده باشه. البته lex به همینجا محدود نمیشه و گسترده تر از این حرفاست اما من هدفم فقط یه آشنایی مختصر خوانندگان عزیز هست و توی دنیای واقعی شما باید از flex به جای lex استفاده کنید.

[fond]

«رزرو برای مطالب آینده»