Computer Software Engineering

 

چکيده

JavaCC طراحی و پياده سازی يک زبان برنامه سازی به وسيله جاوا[1] را تسهيل کرده است. با اين ابزار می توان از زبانهای کوچک برای مسائل خاص گرفته، تا مترجم[2] های پيچيده برای زبانهايی مثل سی پلاس پلاس[3] را به سادگی ساخت. در اين مقاله سعی شده، مقدماتی در مورد اين ابزار و چگونگی کار با آن را بيان گردد.

 

 

مقدمه

اساسا، يک تجزيه کننده[4] متنی را که برای انسان قابل خواندن است را به داده ساختاری که به درخت تجزيه[5] مشهور است، تبديل می کند. تجزيه کننده های مبتنی بر گرامر[6] تنها محدود به زبانهای برنامه نويسی نمی شوند. در واقع، بعضی از پيچيده ترين تجزيه کننده ها در بازيهای ماجرايی[7] بسيار قديمی که با جملاتی که کاربر وارد می کرد، کار می کردند، وجود داشت. همچنين، تجزيه کننده ها در پردازش زبانهای طبيعی، محاسبات رياضی و موتورهای جستجو کاربرد زيادی دارند.

ممکن است در نگاه اول به نظر برسد که تجزيه کردن يک زبان کار ساده ای است، و تنها بايد تعدادی جمله شرطی نوشت که کلمات مورد نظر زبان را پيدا کنند. شايد با اين روش بتوانيد مشکل گرامرهای ساده را حل کنيد، اما تجزيه گرامرهای پيچيده کار بسيار زيادی می طلبد. ممکن است لازم باشد يک کلمه را نديده بگيريد، يا با کلمه ای، بسته به اينکه کلمه بعد از آن چيست، برخوردهای متفاوتی کنيد. به همين ترتيب، تجزيه کننده ها پيچيده می شوند و به تدريج مفاهيم تخصصی در غالب کلماتی مثل گرامرهای LALR، تحليل واژه ای[8]، و تجزيه پايين به بالا[9] مطرح می شوند.

خوشبختانه، ابزارهايی وجود دارند که می توانند بيشتر جزئيات آزاردهنده ساخت يک تجزيه کننده، را از ديد شما مخفی نمايند. مشهورترين اين ابزارها YACC و همتای باز-منبع[10] آن، Bison، هستند. اين ابزارها (که تجزيه کننده هايی را به زبان C توليد می کنند) شما را قادر می سازند که تمرکزتان را  بر قالب[11] زبان خود و اينکه بعد از پيدا شدن يک جزء خاص چه کاری می خواهيد بکنيد، معطوف نماييد. اما برای هواداران جاوا نيز ابزار مشابهی وجود دارد که نام آن JavaCC است!

 

 

معرفی JavaCC

مترجم مترجم جاوا[12] يا JavaCC در اصل توسط شرکت SUN و به عنوان جزئی از يک بسته نرم افزاری ديگر ساخته شد، سپس شرکت ديگری با نام، Metameta، مسووليت توزيع آن را عهده دار شد، و نهايتا اين محصول به شرکت WebGain فروخته شد. در حال حاضر، صفحه رسمی مربوط به JavaCC  در پايگاه اين شرکت و در آدرس http://www.webgain.com/products/java_cc قرار دارد.

JavaCC در حال حاضر، پرکاربردترين سازنده تجزيه کننده[13] برای استفاده در برنامه های جاوا است. اين ابزار، يک توصيف سطح بالا از گرامر را می خواند و آن را به يک برنامه جاوا تبديل می کند که می تواند تطابق ها با گرامر را تشخيص دهد. به جز ساختن تجزيه کننده، JavaCC قابليت های استاندارد ديگری که مربوط به چنين کاريست، نظير ساختن درخت، کنش[14] ها و اشکال زدايی[15]، را فراهم می سازد. هم JavaCC و هم تجزيه کننده ای که توسط آن ساخته می شود را می توان نظير تمام برنامه های جاوا در محيط[16] های مختلف اجرا کرد.

 

 

استفاده از JavaCC

 

توصيف گرامر

چنان که گفته شد، JavaCC يک مترجم دستوری[17] است که فايلهای ورودی خاصی را پردازش می کنند و آنها را به کدهای منبع جاوا تبديل می نمايد. به طور قراردادی، اين فايلهای ورودی از پسوند ".jj" استفاده می کنند. هنگامی که کد جاوای مربوطه حاصل شد، آن را يک بار ديگر، مطابق معمول، ترجمه[18] می کنيد. برای اين کار نيز غالبا از ابزار javac استفاده می شود.

 

سه مولفه اصلی در فايلهای ".jj" وجود دارند:

•        تعريف نشانه[19]های پايانه[20] ای (يا پايانه ها) که کلماتی هستند که انتظار داريد در ورودی باشند.

•        قوانينی در مورد اينکه نشانه ها چگونه با هم ترکيب شوند تا دستور[21]های معتبر زبان (که توليدات[22] ناميده می شوند) پديد آيند.

•        کد جاوا برای متصل کردن همه قسمتها و برای انجام اعمال مربوطه در زمانی که توليدات مشخص به وجود می آيند.

 

از ديد تجزيه کننده، هر چيزی که بتوان آن را در زبان به کار برد، يک نشانه است. نشانه ها ممکن است از نشانه های ديگر تشکيل شده باشند و ممکن است که نشانه های پايانه، که کوچکترين بخش محسوب می شود، باشند. برای مثال HTML را به عنوان زبانی که بايد تجزيه شود، در نظر بگيريد. يک لينک[23] نوعی مثل، جزئی از اين زبان است. يک تجزيه کننده ممکن است اين جمله را متشکل از شش نشانه که همگی هم پايانه هستند، يعنی <، A، HREF، =، آدرس مربوطه و > در نظر بگيرد. در عين حال، اين فهرست نشانه های پايانه، ممکن است مجموعا يک نشانه پيچيده تر (که پايانه نيست، بسازند). می توان اين نشانه را، با نام TAG و به صورت زير در JavaCC تعريف کرد:

 

:=

 

در اين مثال، بيانگر پايانه ای است که از يک حرف A تشکيل شده، و <CLOSEBRACKET> نيز، هر دو پايانه هستند. ولی، نشانه HREF می تواند نشانه های ديگری مثل <HREFKEYWORD>، <EQUALS>، و <URL> را در خود جای دهد.

وقتی که با قالب فايل های ".jj" آشنا شويد، بيان کردن چنين روابطی در JavaCC بسيار ساده است.

فايلهای ورودی معمولا با بخش انتخابها[24] شروع می شوند. از اين بخش برای پيکربندی[25] و تعيين نوع تجزيه کننده ای که قرار است ساخته شود، استفاده می گردد. مثلا ممکن است، چنين بخشی در يک فايل ورودی به صورت زير باشد:

options
{
    IGNORE_CASE=true;

    STATIC=true;

    LOOKAHEAD=2;

}

 

دو انتخاب اول به ترتيب بيان می کنند که زبان مورد نظر، نسبت به حروف کوچک و بزرگ حساس نيست، و ايستاست، يعنی لازم نيست که امکان وجود چندين نمونه[26] از تجزيه کننده در نظر گرفته شود که اين انتخاب بر کارايی تجزيه کننده تاثير می گذارد. انتخاب سوم بيان می کند که گرامر مربوط به اين زبان يک گرامر LL(2) است و پيش از هر تصميم گيری در زمان تجزيه بايد دو نشانه بعدی بررسی شوند.

بعد از بخش انتخابها، دستور PARSER_BEGIN می آيد. JavaCC از کلمه ای که به همراه اين دستور می آيد برای نام گذاری فايل کلاس خروجی استفاده می کند. پس از اين دستور، می توان هر متدی را به زبان جاوا به برنامه اضافه کرد. به علاوه، لازم است که متد main هم در اينجا نوشته شود که وظيفه آن معمولا نمونه سازی از تجزيه کننده است. اين بخش با دستور PARSER_END پايان می يابد.

آخرين بخش يک فايل ".jj" تعريف نشانه ها و توليدات است. در JavaCC، قوانين گرامری که قرار است برای آن تجزيه کننده درست شود، با نماد قالب  گسترش يافته Backus-Naur[27]، (EBNF)، بيان می شوند. EBNF، گرامر را در قالب قوانين توليد تعريف می کند. يک قانون توليد تعيين می کند که يک عنصر گرامر چگونه از عناصر ديگر آن، ساخته می شود و به اين ترتيب عناصر مرکب از اعمال قوانين توليد به دست می آيند. اين قوانين در JavaCC به شکل زير بيان می شوند:

 

فهرست جايگزين | فهرستی از عناصر گرامر GRAMMAR_ELEMENT :=

 

به علاوه از توليدات عبارات منظم[28] نيز برای تعريف نشانه های گرامر استفاده می شود.

برای آشنايی بيشتر با نحوه بيان گرامرها در JavaCC ، گرامر توصيف عبارات رياضی در ضميمه 1 و گرامر توصيف يک محاسبه گر ساده در ضميمه 2 آمده است. برای توضيحات کامل تر در مورد محتويات فايل ".jj" و مشاهده تمام قابليت های تعبيه شده در آن، می توانيد به صفحه ای با عنوان توصيف فايل گرامر JavaCC که در آدرس

http://www.webgain.com/products/java_cc/javaccgrm.html

قرار دارد، مراجعه نماييد.

ايجاد تجزيه کننده

پس از اينکه فايل گرامر زبان کامل شد، با استفاده از JavaCC، به راحتی، می توان از روی آن تجزيه کننده نهايی را ساخت، مراحل کلی اين کار در شکل I مشخص شده است.

شکل I

 

همچنين، نام و توصيف فايل های جاوايی که پس از اجرای JavaCC بر روی فايل گرامر اوليه (با نام فرضی ParserName.jj) درست می شوند نيز، در جدول I آمده است.

جدول I

 

 

ساختن درخت نحوی

ابزار ديگری که در کنار JavaCC قرار دارد و يک افزودنی[33] برای آن محسوب می شود، برنامه ای با نام JJTree است. اين برنامه يک پيش پردازنده[34] برای JavaCC است که کنش های ساختن درخت تجزيه را در نقاط مختلف کد منبع قرار می دهد. JavaCC بر روی خروجی JJTree اجرا می شود تا تجزيه کننده به دست آيد.

به طور پيش فرض، JJTree کد لازم به منظور ساختن گره های درخت تجزيه برای تمام غيرپايانه[35] های زبان را توليد می کند، ولی اين رفتار می تواند به گونه ای عوض شود که برخی از غيرپايانه ها گره ای نداشته باشند، يا اينکه برای جزئی از بسط توليد[36]، گره ساخته شود.

با وجود اينکه JavaCC يک تجزيه کننده بالا به پايين[37] است، JJTree درخت تجزيه را از پايين به بالا می سازد. برای اين کار نيز از يک پشته[38] استفاده می کند که گره ها را پس از ساخته شدن در آن قرار می دهد. هر وقت که پدری برای اين گره ها پيدا شد، آنها را از پشته بر می دارد و به پدر اضافه می کند، و سپس خود گره جديد را  به پشته اضافه می کند. پشته باز است، به اين معنا که شما از طريق کنش های گرامر به آن دسترسی داريد و می توانيد محتويات آن را هرگونه که خود تشخيص می دهيد، برداريد، قراردهيد يا عوض کنيد.

JJTree امکانات ديگری را نيز فراهم می آورد، مثلا امکاناتی که JJTree برای رفتار با استثنا[39] پديد می آورد تجزيه کننده ها را قادر می سازد تا بازيافت خطا[40] انجام دهند و در يک وضعيت مناسب به کار با پشته گره ها ادامه دهند، به علاوه JJTree تمهيداتی برای پشتيبانی از الگو[41]ی بازديد کننده[42] پيش بينی کرده است. اين الگو در مواردی که يک عمليات بايد بر روی عناصر يک داده ساختار انجام شود و در عين حال نمی خواهيم کلاس های آن عناصر را تغيير دهيم، کاربرد دارد. استفاده از اين الگو راه مناسبی برای توليد کد[43] و يا اجرای برنامه از روی درخت معنايی است.

برای اطلاعات بيشتر در مورد JJTree می توانيد به صفحه رسمی مربوط به اين ابزار که در آدرس

 

http://www.webgain.com/products/java_cc/jjtree.html

 

قرار دارد مراجعه کنيد.

 

 

نتيجه گيری

JavaCC يک سازنده تجزيه کننده برای جاوا است که نوشتن تجزيه کننده ها برای زبانهای برنامه نويسی را تسهيل می کند. JavaCC نمادگذاری[44] سطح بالايی برای تعريف گرامرها و توصيف موجزی برای گرامرها و کنش های مربوط به آنها، را فراهم می سازد.

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

 

ضميمه ها

 

ضميمه 1: گرامر توصيف عبارات رياضی

options

{

    LOOKAHEAD=2;

}

 

PARSER_BEGIN(Arithmetic)

 

public class Arithmetic

{

}

 

PARSER_END(Arithmetic)

 

SKIP :

{

    " "

|   "\r"

|   "\t"

}

 

TOKEN:

{

    < NUMBER: ()+ ( "." ()+ )? >

|   < DIGIT: ["0"-"9"] >

}

 

double expr():

{

}

{

    term() ( "+" expr() | "-" expr() )*

}

 

double term():

{

}

{

    unary() ( "*" term() | "/" term() )*

}

 

double unary():

{

}

{

    "-" element() | element()

}

 

double element():

{

}

{

    | "(" a=expr() ")"

}

 

ضميمه 2: گرامر توصيف يک محاسبه گر ساده

options

{

    LOOKAHEAD=2;

}

 

PARSER_BEGIN(Calculator)

 

public class Calculator

{

    public static void main(String args[]) throws ParseException

    {

        Calculator parser = new Calculator(System.in);

        while (true)

        {

            parser.parseOneLine();

        }

    }

}

 

PARSER_END(Calculator)

 

SKIP :

{

    " "

|   "\r"

|   "\t"

}

 

TOKEN:

{

    < NUMBER: ()+ ( "." ()+ )? >

|   < DIGIT: ["0"-"9"] >

|   < EOL: "\n" >

}

 

void parseOneLine():

{

    double a;

}

{

    a=expr()       { System.out.println(a); }

  |

  |                { System.exit(-1); }

}

 

double expr():

{

    double a;

    double b;

}

{

    a=term()

    (

        "+" b=expr()    { a += b; }

    |   "-" b=expr()    { a -= b; }

    )*

                        { return a; }

}

 

double term():

{

    double a;

    double b;

}

{

    a=unary()

    (

        "*" b=term()    { a *= b; }

    |   "/" b=term()    { a /= b; }

    )*

                        { return a; }

}

 

double unary():

{

    double a;

}

{

    "-" a=element()     { return -a; }

|   a=element()         { return a; }

}

 

double element():

{

    Token t;

    double a;

}

{

    t=          { return Double.parseDouble(t.toString()); }

|   "(" a=expr() ")"    { return a; }

}

 

 

 

منابع

1.    http://www.webgain.com/products/java_cc/

2.    Oliver Enseling, “Build your own languages with JavaCC”,  http://www.javaworld.com/javaworld/jw-12-2000/jw-1229-cooltools.html

3.    Al Williams, “Java Parsing Made Easy”, http://www.webtechniques.com/archives/2001/09/java/

4.    Jocelyn Paine, “Introduction to JJTree”, http://www.ifs.org.uk/~popx/jjtree.html

5.    Chuck McManis, “Looking for lex and yacc for Java? You don't know Jack“, http://www.javaworld.com/javaworld/jw-12-1996/jw-12-jack.html

 

* انتخاب معادلهای فارسی در اين متن با توجه به معادلهای ذکر شده در "فرهنگ بسامدی واژگان کامپيوتر و انفورماتيک" از انتشارات دبيرخانه شورای عالی انفورماتيک کشور، انجام شده است.