چگونه Lex و Yacc را با توابع Apache AGE یاد گرفتم

معرفی

به عنوان یک توسعه دهنده برای پروژه منبع باز Apache AGE، من برنامه نویسی با استفاده از Lex و Yacc را به منظور ایجاد قابلیت هایی برای برنامه افزودنی یاد گرفته ام. Lex و Yacc ابزارهای قدرتمندی هستند که می توانند به ما در تولید تجزیه کننده و اسکنر برای زبان برنامه نویسی خود کمک کنند. با این حال، یادگیری و استفاده از این ابزارها بدون راهنمایی ممکن است دشوار باشد.

در پروژه AGE Command Line Interface (CLI)، هدف ما ساده سازی پرس و جو در Apache AGE با اجازه دادن به کاربران برای کدنویسی در Cypher بدون قرار دادن آن در داخل پرس و جوی SQL است. برای انجام این کار، ما از برنامه‌های Lex و Yacc برای تبدیل بندهای Cypher به توابع قابل تشخیص توسط psql CLI استفاده می‌کنیم.

در این پست وبلاگ، نگاهی دقیق تر به نحوه استفاده من از توابع Apache Age، به ویژه MATCH برای یادگیری کد نویسی Lex و Yacc و شروع ساختن برنامه خودم.

پردازش زبان

برای درک Lex/Yacc، اجازه دهید ابتدا در مورد پردازش زبان به عنوان یک کل صحبت کنیم. پردازش زبان یک جزء حیاتی در دنیای توسعه نرم افزار است و شامل چندین مرحله برای تبدیل کد منبع به برنامه های اجرایی است. این فرآیند معمولاً شامل چهار مرحله کلیدی است: تحلیل واژگانی، تحلیل نحوی، تحلیل معنایی و تولید کد، و تولید کد هدف.

تحلیل واژگانی شامل تجزیه کد منبع به یک سری نشانه است. سپس این توکن ها برای شناسایی کلاس های مربوطه خود، مانند شناسه ها، کلمات کلیدی و عملگرها تجزیه و تحلیل می شوند. این مرحله توسط ابزاری به نام lexer یا اسکنر انجام می شود که از مجموعه قوانین مشخص شده در زبان رسمی مانند Lex برای شناسایی و استخراج نشانه ها استفاده می کند.

تحلیل نحوی مرحله بعدی است که شامل تجزیه جریان نشانه برای تعیین اینکه آیا کد با گرامر زبان برنامه نویسی مطابقت دارد یا خیر. این مرحله توسط یک تجزیه کننده انجام می شود که از یک زبان رسمی مانند Yacc برای تولید درخت تجزیه استفاده می کند که ساختار نحوی برنامه را نشان می دهد.

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

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

ما روی دو مرحله اول تمرکز خواهیم کرد که با نوشتن فایل های Lex و Yacc مدیریت می شوند.

تدوین و اجرا

در این پست وبلاگ، به جای آن از Flex و Bison استفاده خواهم کرد، که اساساً نسخه های بهبود یافته Lex و Yacc هستند. را bison و flex دستورات موجود در مثال های زیر می توانند با آنها قابل تعویض باشند yacc و lex.

قبل از کامپایل، از هر دو مطمئن شوید {filename}.y و {filename}.l در همان دایرکتوری وجود دارد، با نام {filename} به هر نامی که می خواهید. ابتدا دستور زیر را در پنجره ترمینال اجرا کنید.

bison -d {filename}.y

این باعث ایجاد یک {filename}.tab.c فایل تجزیه کننده و -d گزینه را ایجاد می کند {filename}.tab.h فایل هدر، که ممکن است در فایل Lex به آن ارجاع داده شود. سپس دستور زیر را برای کامپایل کردن فایل Lex اجرا کنید.

flex match.l

این یک فایل به نام تولید می کند lex.yy.c. با دو فایل C تولید شده، دستور زیر را اجرا کنید تا آنها را در یک برنامه C اجرایی کامپایل کنید.

gcc lex.yy.c {filename}.tab.c -o {filename}

این یک C اجرایی با نام فایلی که بعد از آن مشخص کرده اید تولید می کند -o گزینه ای که به کامپایلر می گوید که فایل را در نام فایل مشخص شده خروجی دهد.

./{filename}

دستور بالا را اجرا کنید تا برنامه تازه ایجاد شده خود را اجرا کنید و برنامه خود را با موفقیت ساخته و اجرا کنید!

به عنوان مثال، یک کامپایل و اجرای کامل برای فایل “match.l” و “match.y” به شکل زیر خواهد بود:

yacc -d match.y
flex match.l
gcc lex.yy.c match.tab.c -o match
./match

در صورت بروز خطا، احتمالاً مشکلاتی در فایل Lex یا Yacc وجود دارد که با پیام خطا همراه با خط و کاراکتر مشکل دار مشخص می شود.

ساختار Lex

ساختار فایل های Lex چیزی شبیه به زیر خواهد بود:

%{
DECLARATIONS
%}

%%
PATTERNS    ACTIONS;
%%

FUNCTIONS

قسمت اول ضمیمه شده است %{ ... %} و شامل اعلان های C مانند #include.

بخش محصور شده با %% ... %% جفت‌های الگو-عمل را نشان می‌دهد که به تجزیه‌کننده اجازه می‌دهد تا توکن‌های خاصی را که توسط کاربر وارد می‌شود، شناسایی کند و بر اساس ورودی، یک عمل یا چند عمل انجام دهد.

آخرین بخش شامل توابع C است که از پردازش زبان پشتیبانی می کند. این توابع ممکن است با اقدامات بخش قبلی فراخوانی شوند.

ساختار Yacc

ساختار فایل های Yacc شبیه به فایل های Lex است و چیزی شبیه به زیر خواهد بود:

%{
DECLARATIONS
%}

DEFINITIONS

%%
GRAMMARS : RULES;    {ACTIONS}
%%

FUNCTIONS

قسمت اول ضمیمه شده است %{ ... %} و شامل اعلان های C مانند #include.

بخش بعدی برای تعاریف yacc است که با عبارت شروع می شود % نماد، که شامل %start، %token، %union، و %types تعاریف

بخش محصور شده با %% ... %% نشان دهنده گرامرهایی است که مجموعه ای از تولیدات هستند. سمت چپ که گرامر هستند به دنبال آن است :، و الف ; برای به پایان رساندن مجموعه قوانین یا | برای اضافه کردن قوانین بیشتر، و سمت راست با اقداماتی که در آن گنجانده شده است { ... }.

آخرین بخش شامل توابع C است که از پردازش زبان پشتیبانی می کند. این توابع ممکن است با اقدامات بخش قبلی فراخوانی شوند.

کار با Lex

در این مثال، ما سعی خواهیم کرد دستور سایفر “MATCH” را که معمولا در AGE استفاده می شود، تکرار کنیم.

در قسمت اول هدر ‘match.tab.h’ را که پس از کامپایل کردن فایل ‘match.y’ تولید می شود، قرار می دهیم. یک متغیر نیز ایجاد خواهیم کرد yyerror با نوع void که تجزیه کننده هر زمان که خطای نحوی رخ دهد آن را فراخوانی می کند.

%{
#include "match.tab.h"

void yyerror(char* s);
%}

بخش بعدی با الگوها و اقدامات آنها تعریف می شود. الگوی اول [ \t\n] فضاهای سفید، فضاهای برگه و خطوط جدید را تعریف می کند و به کامپایلر می گوید که این ورودی ها را نادیده بگیرد. را MATCH و RETURN توکن ها بصری هستند و به سادگی برمی گردند MATCH و RETURN به کامپایلر نمادهای زیر به‌عنوان کلمات کلیدی که در فایل Yacc استفاده خواهند شد، برگردانده می‌شوند. را exit توکن را برمی گرداند exit_commandو هر رشته نویسه ای که با یک کاراکتر الفبایی و به دنبال آن هر کاراکتر الفبایی یا عددی شروع شود به عنوان یک علامت شناخته می شود. VAR. هر چیز دیگری که توسط کاربر وارد شود یک خطای نحوی ایجاد می کند.

%%
[ \t\n]                 ;
"MATCH"                 { return MATCH; }
"RETURN"                { return RETURN; }
"-"                     { return DASH; }
"("                     { return LP; }
")"                     { return RP; }
"["                     { return LB; }
"]"                     { return RB; }
"{"                     { return LC; }
"}"                     { return RC; }
"<"                     { return LT; }
">"                     { return GT; }
";"                     { return yytext[0]; }
"exit"                  { return exit_command; }
[a-zA-Z][a-zA-Z0-9]*    { return VAR; }
.                       { ECHO; yyerror("unexpected character"); }
%%

در قسمت پایانی فایل Lex تابعی وجود دارد که به آن می گویند yywrap()، که در صورت استفاده از چندین فایل ورودی ضروری است.

int yywrap(void) {
    return 1;
}

کار با Yacc

در قسمت اول، هدرهای استاندارد io و lib و همچنین هدر ‘match.tab.h’ را که پس از کامپایل این فایل تولید می شود، قرار می دهیم. یک متغیر نیز ایجاد خواهیم کرد yyerror با نوع void که تجزیه کننده هر زمان که خطای نحوی رخ دهد آن را فراخوانی می کند.

%{
#include <stdio.h>
#include <stdlib.h>
#include "match.tab.h"

void yyerror(char* s);
%}

سپس تعاریف Yacc را خواهیم داشت. %union به ما این امکان را می دهد که انواع مختلفی را که تحلیلگر می تواند برگرداند، مشخص کنیم { ... }. %start دستور زبان تولید پیش‌فرض را نشان می‌دهد که باید در شروع برنامه به دنبال آن باشید. %token توکن های مورد انتظاری را که تحلیلگر به عنوان نوع مشخص دریافت می کند، توصیف می کند. را <str> بعد از %token توکن ها را در عضو اتحادیه ‘str’ ذخیره می کند.

%union { char *str; }
%start query
%token <str> MATCH RETURN DASH LP RP LB RB LC RC LT GT VAR exit_command

در مجموع 4 گرامر تولید وجود خواهد داشت، با query گرامر پیش فرض است. این گرامر شامل statement گرامر یا exit_command، که از برنامه خارج می شود. دستور دستور عبارت می تواند باشد match_clause، return_clause، یا هر دو با هم را match_clause می تواند گرامرهایی شبیه یکی از لیست داشته باشد:

• MATCH (u)
• MATCH (u)-[r]-(v)
• MATCH (u)<-[r]-(v)
• MATCH (u)-[r]->(v)

را return_clause تنها به ما اجازه می دهد تا از هم اکنون یک متغیر را برگردانیم که در آینده برطرف خواهد شد.

%%
query : statement ';'                                                   { ; }
      | exit_command ';'                                                { printf("Exiting program...\n"); exit(EXIT_SUCCESS); }
      ;

statement : match_clause                                                { ; }
          | return_clause                                               { ; }
          | match_clause return_clause                                  { ; }

match_clause : MATCH LP VAR RP                                          { ; }
             | MATCH LP VAR RP DASH LB VAR RB DASH LP VAR RP            { ; }
             | MATCH LP VAR RP LT DASH LB VAR RB DASH LP VAR RP         { ; }
             | MATCH LP VAR RP DASH LB VAR RB DASH GT LP VAR RP         { ; }
             ;

return_clause : RETURN VAR                                              { ; }
              ;
%%

دو تابع در قسمت پایانی فایل Yacc وجود دارد که عبارتند از: main() و yyerror() کارکرد. را main() تابع به سادگی برمی گردد yyparse()، که یک تابع Yacc است که از طریق گرامر تکرار می شود تا به طور مداوم ورودی را بخواند و عمل مربوطه را تا زمانی که به صورت دستی خارج شود یا با خطایی مواجه شود تولید می کند. را yyerror() هر زمان که یک خطای نحوی رخ دهد فراخوانی می شود که به سادگی خطا را چاپ می کند.

int main(void) {
    return yyparse();
}

void yyerror(char *s) {
    fprintf(stderr, "%s\n", s);
}

نسخه ی نمایشی برنامه

پس از کامپایل و اجرای برنامه، می توانید چندین ورودی مختلف را تایپ کنید تا بررسی کنید که آیا برنامه به درستی کار می کند یا خیر.

امتحان هر یک از اینها از لیست با نام متغیر قابل تعویض، با موفقیت تجزیه می شود.

• MATCH (u);
• MATCH (u)-[r]-(v);
• MATCH (u)<-[r]-(v);
• MATCH (u)-[r]->(v);
• RETURN u;
• MATCH (u) RETURN u;
• MATCH (u)-[r]-(v) RETURN u;
• MATCH (u)<-[r]-(v) RETURN u;
• MATCH (u)-[r]->(v) RETURN u;
• exit;

اگر ترکیب دیگری از نمادهای شناخته شده و ناشناخته را امتحان کنید، برنامه پیغام خطا ارسال می کند و از برنامه خارج می شود.

در حال حاضر، هیچ اقدامی برای گرامرهای تولید تنظیم نشده است، که هیچ خروجی را از طریق تجزیه موفقیت آمیز به کاربران نشان نمی دهد، اما در آینده برای کاربردی تر کردن برنامه به روز می شود.

نتیجه

یادگیری برنامه نویسی Lex و Yacc با استفاده از توابع Apache Age می تواند برای هر برنامه نویسی که علاقه مند به پردازش زبان و توسعه کامپایلر است، یک سفر هیجان انگیز و مفید باشد. با کمک توابع Apache Age، یاد گرفتم که چگونه برنامه خود را بسازم و یک کامپایلر بسازم که بتواند کد منبع را به برنامه های اجرایی تبدیل کند.

با تسلط بر مراحل مختلف پردازش زبان، از جمله تحلیل واژگانی، تجزیه و تحلیل نحو، تحلیل معنایی، تولید کد و بهبود کد، می توانید درک عمیقی از نحوه کار زبان های برنامه نویسی به دست آورید و مهارت هایی را توسعه دهید که در صنعت نرم افزار بسیار مورد توجه است.

من از این آموزش در Lex و این آموزش در Flex برای یادگیری اصول برنامه نویسی Lex و Flex استفاده کرده ام.