دسترسی کامل به Flex & Bison و 60K+ عناوین دیگر ، با آزمایش رایگان 10 روزه O'Reilly.

همچنین رویدادهای آنلاین زنده ، محتوای تعاملی ، مواد آماده سازی صدور گواهینامه و موارد دیگر وجود دارد.

فصل 1. - معرفی فلکس و بیسون

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

تجزیه و تحلیل واژگانی و تجزیه

اولین کامپایلرها در دهه 1950 از تکنیک های کاملاً موقت برای تجزیه و تحلیل نحو کد منبع برنامه هایی که در حال تهیه آنها بودند استفاده کردند. در دهه 1960 ، این زمینه توجه دانشگاهی زیادی به خود جلب کرد و تا اوایل دهه 1970 ، تجزیه و تحلیل نحو یک زمینه خوب درک بود.

یکی از بینش های مهم این بود که کار را به دو بخش تقسیم کنید: تجزیه و تحلیل واژگانی (که به آن لکسینگ یا اسکن نیز گفته می شود) و تجزیه و تحلیل نحو (یا تجزیه).

تقریباً صحبت می کند ، اسکن ورودی را به تکه های معنی دار ، به نام نشانه ها تقسیم می کند و تجزیه و تحلیل می کند که چگونه نشانه ها با یکدیگر ارتباط دارند. به عنوان مثال ، این قطعه کد C را در نظر بگیرید:

آلفا = بتا + گاما ؛

یک اسکنر این را به Tokens Alpha ، علامت برابر ، بتا ، به علاوه علامت ، گاما و نیمه رنگ تقسیم می کند. سپس تجزیه کننده تعیین می کند که بتا + گاما یک عبارت است و این عبارت به آلفا اختصاص می یابد.

انعطاف پذیری و بیسون

بیشتر سیستم های لینوکس و BSD به عنوان بخشی از سیستم پایه با Flex و Bison همراه هستند. اگر سیستم شما آنها را نداشته باشد ، یا نسخه های قدیمی داشته باشد ، نصب آنها آسان است.

Flex یک پروژه Sourceforge است ، در http://flex. sourceforge.net/. نسخه فعلی از اوایل سال 2009 2. 5. 35 بود. تغییرات از نسخه به نسخه معمولاً جزئی هستند ، بنابراین به روزرسانی نسخه خود در صورت نزدیک به 35. ضروری نیست ، اما برخی از سیستم ها هنوز هم با نسخه 2. 5. 4 یا 2. 5. 4a ارسال می شوند ، که این چیزی بیش از یک استدهه قدیمی

بیسون از http://www. gnu.org/software/bison/ در دسترس است. نسخه فعلی از اوایل سال 2009 2. 4. 1 بود. بیسون تحت توسعه نسبتاً فعال است ، بنابراین ارزش دریافت یک نسخه به روز را دارد تا ببینید چه چیزی جدید است. به عنوان مثال ، نسخه 2. 4 پشتیبانی از پارسرها در جاوا را اضافه کرد. کاربران BSD به طور کلی می توانند با استفاده از مجموعه پورت ها نسخه فعلی Flex یا Bison را نصب کنند. کاربران لینوکس ممکن است بتوانند RPM های فعلی را پیدا کنند. اگر اینطور نیست ، Flex و Bison هر دو از فرآیند استاندارد ساخت GNU استفاده می کنند ، بنابراین برای نصب آنها ، Tarballs Flex و Bison فعلی را از وب سایت ها بارگیری و باز کنید ، اجرا کنید. برای نصب آنها

Flex و Bison هر دو به ماکروپروسور GNU M4 بستگی دارند. لینوکس و BSD همه باید M4 داشته باشند ، اما در صورت عدم استفاده ، یا نسخه باستانی ، GNU M4 فعلی در http://www. gnu.org/software/m4/ قرار دارد.

برای کاربران ویندوز ، هر دو Bison و Flex در محیط شبیه سازی Cygwin Linux موجود در http://www. cygwin.com/ درج شده اند. شما می توانید از کد C یا C ++ که آنها با ابزارهای توسعه Cygwin یا با ابزارهای توسعه ویندوز بومی تولید می کنند ، استفاده کنید.

عبارات منظم و اسکن

اسکنرها به طور کلی با جستجوی الگوهای شخصیت در ورودی کار می کنند. به عنوان مثال ، در یک برنامه C ، ثابت عدد صحیح یک رشته از یک یا چند رقم است ، یک نام متغیر نامه ای است که به دنبال آن صفر یا بیشتر حروف یا رقم است و اپراتورهای مختلف شخصیت های مجرد یا جفت شخصیت ها هستند. یک روش ساده برای توصیف این الگوهای ، عبارات منظم است که اغلب به Regex یا Regexp کوتاه می شوند. اینها همان نوع الگویی هستند که ویراستاران ED و VI و برنامه جستجو EGREP برای توصیف متن برای جستجوی متن استفاده می کنند. یک برنامه Flex اساساً شامل لیستی از regexps است که دستورالعمل هایی در مورد آنچه باید انجام شود در هنگام ورودی با هر یک از آنها ، معروف به اقدامات انجام می شود. یک اسکنر تولید شده با انعطاف پذیر از طریق ورودی خود می خواند و ورودی را در برابر همه Regexps مطابقت می دهد و اقدامات مناسب را در هر مسابقه انجام می دهد. Flex همه regexps را به یک شکل داخلی کارآمد ترجمه می کند که به آن اجازه می دهد تا با همزمان با ورودی در برابر همه الگوهای مطابقت داشته باشد ، بنابراین به همان سرعت برای 100 الگوی برای یک مورد سریع است.[1]

اولین برنامه Flex ما

سیستم های یونیکس (که من از آن منظورم سیستم های UNIX-ish از جمله Linux و BSD ها) با یک برنامه Count Word همراه است که از طریق یک پرونده می خواند و تعداد خطوط ، کلمات و کاراکترهای موجود در پرونده را گزارش می کند. Flex به ما اجازه می دهد WC را در چند ده خط بنویسیم ، که در مثال 1-1 نشان داده شده است.

مثال â 1-1. â تعداد کلمات FB1-1. l

/ * دقیقاً مانند UNIX WC */ ٪٪٪ [a-za-z]+ n. ٪٪ اصلی (int argc ، char ** argv)

بخش اعظم این برنامه باید برای برنامه نویسان C آشنا به نظر برسد ، زیرا بیشتر آن C. یک برنامه Flex از سه بخش تشکیل شده است که توسط خطوط ٪ ٪ از هم جدا شده است. بخش اول شامل اعلامیه ها و تنظیمات گزینه است. بخش دوم لیستی از الگوهای و اقدامات است و بخش سوم کد C است که در اسکنر تولید شده کپی می شود ، معمولاً روالهای کوچک مربوط به کد در اقدامات.

در بخش اعلامیه ، کد در ٪ ٪از طریق کلمه در نزدیکی آغاز پرونده منبع C تولید شده کپی می شود. در این حالت فقط متغیرهایی را برای خطوط ، کلمات و شخصیت ها تنظیم می کند.

در بخش دوم ، هر الگوی در آغاز یک خط است و پس از آن کد C برای اجرای الگوی اجرا می شود. کد C می تواند یک عبارت یا احتمالاً یک بلوک چند لایه در بریس ها باشد ،<>بشر(هر الگوی باید از ابتدای خط شروع شود ، زیرا Flex هر خطی را که با فضای سفید شروع می شود ، در نظر می گیرد تا کد در برنامه C تولید شده کپی شود.)

در این برنامه فقط سه الگوی وجود دارد. مورد اول ، [A-za-z]+ ، با یک کلمه مطابقت دارد. شخصیت های موجود در براکت ها ، که به عنوان یک کلاس کاراکتر شناخته می شوند ، با هر حرف بالا یا حروف کوچک مطابقت دارند ، و علامت + به معنای مطابقت با یک یا چند مورد قبلی است ، که در اینجا به معنی یک رشته حروف یا یک کلمه است. کد عمل تعداد کلمات و شخصیت های دیده شده را به روز می کند. در هر عمل Flex ، متغیر yytext تنظیم شده است تا به متن ورودی اشاره کند که الگوی فقط مطابقت دارد. در این حالت ، تنها چیزی که ما به آن اهمیت می دهیم این است که چند شخصیت در آن وجود دارد ، بنابراین می توانیم تعداد کاراکتر را به طور مناسب به روز کنیم.

الگوی دوم ، n ، فقط با یک خط جدید مطابقت دارد. این عمل تعداد خطوط و کاراکترها را به روز می کند.

الگوی نهایی یک نقطه است که برای هر شخصیت regex-ese است.(شبیه به اسکریپت های پوسته است.) این عمل تعداد کاراکترها را به روز می کند. و این تمام الگوهای مورد نیاز ما است.[2]

کد C در پایان یک برنامه اصلی است که yylex () را صدا می کند ، نامی که Flex به روال اسکنر می دهد ، و سپس نتایج را چاپ می کند. در صورت عدم وجود هرگونه ترتیب دیگر ، اسکنر از ورودی استاندارد می خواند. پس بگذارید آن را اجرا کنیم.

$ Flex FB1-1. l $ CC lex. yy. c-lfl $ ./a. out پسر روی عرشه سوزش ایستاد گلوله های بادام زمینی توسط پک ^د2 12 63 $

ابتدا به فلکس می گوییم که برنامه خود را ترجمه کند ، و به صورت کلاسیک یونیکس از آنجا که هیچ خطایی وجود ندارد ، این کار را انجام می دهد و چیزی نمی گوید. سپس ما Lex. yy. c را کامپایل می کنیم ، برنامه C که تولید کرده است. پیوند آن را با کتابخانه فلکس ، -lfl ؛آن را اجرا کنید؛و کمی ورودی را تایپ کنید تا حساب شود. به نظر می رسد کار می کند

برنامه WC واقعی از تعریف کمی متفاوت از یک کلمه استفاده می کند ، مجموعه ای از کاراکترهای غیر فضای سفید. هنگامی که ما نگاه می کنیم که همه شخصیت های فضای سفید چیست ، فقط باید خط را جایگزین کنیم که کلمات را با یکی از شخصیت هایی که با یک سری از شخصیت های غیر WhiteSpace مطابقت دارد مطابقت داشته باشد:

[^ t n r f v]+

^ در ابتدای کلاس شخصیت به معنای مطابقت با هر شخصیتی غیر از شخصیت های کلاس است و + یک بار دیگر به معنای مطابقت با یک یا چند الگوهای قبلی است. این یکی از نقاط قوت فلکس را نشان می دهد - ایجاد تغییرات کوچک در الگوهای آسان است و اجازه می دهد تا انعطاف پذیری در مورد چگونگی تأثیرگذاری بر کد تولید شده نگران باشد.

برنامه هایی در Flex ساده

برخی از برنامه ها به اندازه کافی ساده هستند که می توانید همه چیز را به صورت فلکس بنویسید ، یا در Flex با کمی C. C. به عنوان مثال ، به عنوان مثال ، 1-2 اسکلت یک مترجم را از انگلیسی به آمریکایی نشان می دهد.

مثال Â 1-2. â انگلیسی به آمریکایی fb1-2. l

/* English>آمریکایی */ ٪٪ "رنگ""عطر و طعم""باهوش""هوشمندانه""محافظه کار"â بسیاری از کلمات دیگر â . %%

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

قرار دادن فلکس و بیسون

اولین برنامه ای که با استفاده از Flex و Bison می نویسیم یک ماشین حساب میز است. ابتدا یک اسکنر می نویسیم ، و سپس یک تجزیه کننده می نویسیم و دو نفر را با هم جدا می کنیم.

برای ساده نگه داشتن امور ، ما با شناخت فقط عدد صحیح ، چهار اپراتور حسابی اساسی و یک اپراتور با ارزش مطلق Unary (مثال 1-3) شروع خواهیم کرد.

مثال â 1-3. Â یک اسکنر فلکس ساده FB1-3. L

/ * نشانه های ماشین حساب را تشخیص داده و آنها را چاپ کنید */ ٪٪ "+""-" "*" "/" "|" [0-9]+

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

الگوی ششم با یک عدد صحیح مطابقت دارد. الگوی براکت [0-9] با هر رقم واحد مطابقت دارد ، و علامت + زیر به معنای مطابقت با یک یا چند مورد قبلی است ، که در اینجا به معنای رشته ای از یک یا چند رقم است. این عمل با استفاده از نشانگر yytext که اسکنر بعد از هر مسابقه تنظیم می کند ، رشته ای را که مطابقت دارد چاپ می کند.

الگوی هفتم با یک شخصیت خط جدید مطابقت دارد ، که با توالی معمول c n نشان داده شده است.

الگوی هشتم فضای سفید را نادیده می گیرد. با هر فضای یا برگه ( t) مطابقت دارد ، و کد عمل خالی هیچ کاری نمی کند.

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

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

در این برنامه Flex ساده ، کد C در بخش سوم وجود ندارد. کتابخانه Flex (-LFL) یک برنامه اصلی کوچک را ارائه می دهد که فقط اسکنر را صدا می کند ، که برای این مثال کافی است.

بنابراین اجازه دهید اسکنر ما را امتحان کنیم:

$ Flex FB1-3. L $ CC lex. yy. c-lfl $ ./a. out 12+34شماره 12 به علاوه شماره 34 Newline5 6 / 7qشماره 5 شماره 6 تقسیم شماره 7 شخصیت رمز و راز Q Newline^د $

ابتدا Flex را اجرا می کنیم ، که اسکنر را به یک برنامه C به نام Lex. yy. c ترجمه می کند ، سپس برنامه C را کامپایل می کنیم و در نهایت آن را اجرا می کنیم. خروجی نشان می دهد که اعداد را به عنوان اعداد به رسمیت می شناسد ، اپراتورها را به عنوان اپراتورها می شناسد و Q در آخرین خط ورودی توسط الگوی Catchall در پایان گرفتار می شود.(که ^d یک شخصیت انتهای پرونده یونیکس/لینوکس است. در ویندوز شما نوع ^z.)

اسکنر به عنوان Coroutine

بیشتر برنامه ها با اسکنرهای Flex از اسکنر برای بازگشت جریانی از نشانه هایی که توسط یک تجزیه کننده اداره می شوند ، استفاده می کنند. هر بار که برنامه به یک نشانه نیاز دارد ، yylex () را صدا می کند ، که کمی ورودی را می خواند و نشانه را برمی گرداند. هنگامی که به یک نشانه دیگر احتیاج دارد ، دوباره yylex () را صدا می کند. اسکنر به عنوان یک Coroutine عمل می کند. یعنی هر بار که باز می گردد ، به یاد می آورد که کجا بود ، و در تماس بعدی جایی که از آنجا خارج شده است ، انتخاب می شود.

در داخل اسکنر ، هنگامی که کد عمل دارای یک نشانه آماده است ، فقط آن را به عنوان مقدار از Yylex () برمی گرداند. دفعه بعد که این برنامه yylex () را صدا می کند ، اسکن را با کاراکترهای ورودی بعدی از سر می گیرد. برعکس ، اگر یک الگوی برای برنامه فراخوانی نتواند و بازگردد ، اسکنر فقط در همان تماس به Yylex () ادامه خواهد داد و شخصیت های ورودی بعدی را اسکن می کند. این قطعه ناقص دو الگوی را نشان می دهد که نشانه ها را برمی گرداند ، یکی برای + اپراتور و دیگری برای یک عدد و یک الگوی فضای سفید که هیچ کاری انجام نمی دهد ، از این طریق آنچه را که مطابقت دارد نادیده می گیرد.

"+" [0-9]+[ t]

این تلفات آشکار در مورد اینکه آیا کد عمل اغلب کاربران جدید Flex را گیج می کند ، اما این قانون در واقع بسیار ساده است: اگر کد عمل بازگردد ، اسکن از رزومه در تماس بعدی به Yylex () ؛اگر بازگردد ، اسکن سریعاً از سر گرفته می شود.

اکنون ما اسکنر خود را اصلاح می کنیم تا نشانه هایی را برگردانیم که یک تجزیه کننده می تواند برای اجرای یک ماشین حساب استفاده کند.

نشانه ها و ارزش ها

هنگامی که یک اسکنر فلکس جریانی از نشانه ها را برمی گرداند ، هر نشانه در واقع دارای دو قسمت است ، نشانه و ارزش توکن. نشانه یک عدد صحیح کوچک است. اعداد توکن دلخواه هستند ، به جز اینکه صفر توکن همیشه به معنای انتهای پرونده است. هنگامی که بیسون یک تجزیه کننده ایجاد می کند ، بیسون اعداد توکن را به طور خودکار از 258 شروع می کند (این کار از برخورد با نشانه های شخصیت تحت اللفظی ، که بعداً مورد بحث قرار می گیرد) جلوگیری می کند و با تعاریفی از شماره های توکن ایجاد می شود. اما در حال حاضر ، ما فقط چند نشانه را با دست تعریف خواهیم کرد:

شماره = 258 ، اضافه کردن = 259 ، زیر = 260 ، MUL = 261 ، DIV = 262 ، ABS = 263 ، EOL = 264آخر خط 

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

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

مثال Â 1-4. â اسکنر ماشین حساب FB1-4. L

/ * نشانه های ماشین حساب را تشخیص داده و آنها را چاپ کنید */ ٪; int yylval; %> %% "+" "-" "*" "/" "|" [0-9]+ n[ t]. >

ما شماره های توکن را در یک C enum تعریف می کنیم. سپس yylval را می سازیم ، متغیری که مقدار توکن را ذخیره می کند ، یک عدد صحیح ، که برای نسخه اول ماشین حساب ما کافی است.(بعداً می بینیم که این مقدار معمولاً به عنوان اتحادیه تعریف می شود تا انواع مختلفی از نشانه ها بتوانند انواع مختلفی از مقادیر را داشته باشند ، به عنوان مثال ، یک شماره نقطه شناور یا یک اشاره گر برای ورود به نماد در یک جدول نماد.)

لیست الگوهای مشابه در مثال قبلی است ، اما کد عمل متفاوت است. برای هر یک از نشانه ها ، اسکنر کد مناسب را برای نشانه برمی گرداند. برای اعداد ، رشته ها از رقم ها را به یک عدد صحیح تبدیل می کند و قبل از بازگشت آن را در Yylval ذخیره می کند. الگویی که با فضای سفید مطابقت دارد ، برمی گردد ، بنابراین اسکنر فقط به دنبال آنچه در آینده می آید ادامه می دهد.

فقط برای آزمایش ، یک برنامه اصلی کوچک yylex () را صدا می کند ، مقادیر توکن را چاپ می کند ، و برای نشانه های شماره ، Yylval را نیز چاپ می کند.

$ Flex FB1-4. L $ CC lex. yy. c-lfl $ ./a. out A / 34 + | 45 شخصیت رمز و راز a 262 258 = 34 259 263 258 = 45 264 ^د $

اکنون که یک اسکنر کار داریم ، توجه خود را به تجزیه می کنیم.

فلکس و بیسون از کجا آمده اند؟

بیسون از YACC ، یک ژنراتور تجزیه کننده که بین سالهای 1975 و 1978 توسط استفان سی جانسون در Bell Labs نوشته شده است ، فرود می آید. به عنوان نام آن ، کوتاه برای کامپایلر دیگر کامپایلر ، "بسیاری از مردم در آن زمان مشغول نوشتن ژنراتورهای تجزیه کننده بودند. ابزار جانسون یک بنیاد نظری محکم را از تجزیه کار D. E. Knuth ترکیب کرد ، که باعث می شد تجزیه کنندگان آن بسیار قابل اعتماد و یک نحو ورودی مناسب باشند. اینها این امر را در بین کاربران سیستم های UNIX بسیار محبوب کرد ، اگرچه مجوز محدود کننده ای که UNIX در آن توزیع می شد ، در زمان استفاده از آن در خارج از آکادمی و سیستم بل محدود شد. در حدود سال 1985 ، باب کوربت ، دانشجوی فارغ التحصیل در دانشگاه کالیفرنیا ، برکلی ، با استفاده از الگوریتم های داخلی تا حدودی بهبود یافته ، که در برکلی YACC تکامل یافت ، YACC را مجدداً اجرا کرد. از آنجا که نسخه او سریعتر از YACC Bell'S بود و تحت مجوز انعطاف پذیر برکلی توزیع شد ، به سرعت به محبوب ترین نسخه YACC تبدیل شد. ریچارد استالمن از بنیاد نرم افزار رایگان (FSF) کار Corbettâ را برای استفاده در پروژه GNU اقتباس کرد ، جایی که رشد کرده است که تعداد زیادی از ویژگی های جدید را شامل می شود زیرا در نسخه فعلی Bison تکامل یافته است. بیسون اکنون به عنوان پروژه FSF نگهداری می شود و تحت مجوز عمومی GNU توزیع می شود.

در سال 1975 ، مایک لسک و کارآموز تابستانی اریک اشمیت ، لکس ، یک مولد آنالایزر واژگانی را نوشتند که بیشتر برنامه نویسی توسط اشمیت انجام می شود. آنها آن را هم به عنوان ابزاری مستقل و هم به عنوان همراه با YACC جانسون دیدند. لکس نیز علی رغم اینکه نسبتاً کند و حشره دار است ، بسیار محبوب شد.(با این وجود اشمیت در صنعت رایانه ای که اکنون مدیرعامل Google است ، حرفه ای نسبتاً موفقی را پشت سر گذاشت.)

در حدود سال 1987 ، ورن پاکسون از آزمایشگاه لارنس برکلی نسخه ای از لکس را که در آن زمان در Ratfor نوشته شده بود ، گرفت و آن را به C ترجمه کرد و آن را به C Flex می خواند ، برای ژنراتور آنالایزر آنالایزر AST lex. از آنجا که سریعتر و قابل اطمینان تر از AT& T Lex بود و مانند برکلی YACC که تحت مجوز برکلی موجود است ، لکس اصلی را به طور کامل تکمیل کرده است. Flex اکنون یک پروژه Sourceforge است که هنوز تحت مجوز برکلی است.

گرامرها و تجزیه

کار تجزیه کننده این است که رابطه بین نشانه های ورودی را تشخیص دهیم. یک روش مشترک برای نمایش چنین روابطی ، یک درخت پارس است. به عنوان مثال ، طبق قوانین معمول حسابی ، بیان حسابی 1 * 2 + 3 * 4 + 5 می تواند درخت تجزیه را در شکل 1-1 داشته باشد.

شکل â 1-1. â بیان درخت تجزیه

ضرب از برتری بالاتری نسبت به علاوه بر این ، بنابراین دو عبارت اول 1 * 2 و 3 * 4 است. سپس این دو عبارت به هم اضافه می شوند و سپس این جمع به 5 اضافه می شود. هر شاخه از درخت رابطه بین نشانه ها یا زیر درختان زیر آن را نشان می دهد. ساختار این درخت خاص بسیار ساده و منظم است و دارای دو فرزندان در زیر هر گره است (به همین دلیل ما از یک ماشین حساب به عنوان نمونه اول استفاده می کنیم) ، اما هر تجزیهگر بیسون باعث ایجاد یک درخت پارس می شود زیرا ورودی خود را تجزیه می کند. در برخی از برنامه ها ، درخت را به عنوان یک ساختار داده در حافظه برای استفاده بعدی ایجاد می کند. در برخی دیگر ، درخت فقط در توالی عملیاتی که تجزیه کننده انجام می دهد ، ضمنی است.

گرامرهای BNF

برای نوشتن یک تجزیه کننده ، ما به روشی نیاز داریم تا قوانینی را که تجزیه کننده از آن استفاده می کند برای تبدیل دنباله ای از نشانه ها به یک درخت پارس استفاده کنیم. متداول ترین نوع زبانی که تجزیه کننده های رایانه ای از آن برخوردار هستند ، یک دستور زبان بدون زمینه (CFG) است.[3] فرم استاندارد برای نوشتن CFG فرم Backus-Naur (BNF) است که در سال 1960 برای توصیف Algol 60 ایجاد شده است و به نام دو عضو کمیته Algol 60 نامگذاری شده است.

خوشبختانه ، BNF بسیار ساده است. BNF در اینجا برای عبارات حسابی ساده به اندازه کافی برای رسیدگی به 1 * 2 + 3 * 4 + 5:

:: = |+ :: = شماره |* عدد

هر خط قانونی است که می گوید چگونه شاخه ای از درخت تجزیه را ایجاد کند. در bnf ، :: = قابل خواندن است â aâ یا Â می شود ، â و |Â یا ، Â راه دیگری برای ایجاد شاخه ای از همان نوع است. نام در سمت چپ یک قاعده یک نماد یا اصطلاح است. طبق کنوانسیون ، تمام نشانه ها به عنوان نمادها در نظر گرفته می شوند ، اما نمادهایی نیز وجود دارند که نشانه ها نیستند.

BNF مفید کاملاً کاملاً بازگشتی است ، با قوانینی که به طور مستقیم یا غیرمستقیم به خودشان اشاره می کنند. این قوانین ساده می توانند با استفاده از آنها به صورت بازگشتی ، دنباله ای پیچیده و اضافی از اضافات و ضربها را مطابقت دهند.

زبان ورودی قانون بیسون

قوانین بیسون اساساً BNF هستند ، با نگارشی کمی ساده می شود تا تایپ آنها آسان تر شود. مثال Â 1-5 کد بیسون ، از جمله BNF را برای اولین نسخه از ماشین حساب ما نشان می دهد.

مثال â 1-5. â ماشین حساب ساده FB1-5. y

/ * ساده ترین نسخه ماشین حساب */ ٪<#include %>/ * نشانه های توکن */٪ number ٪ token اضافه کردن sub mul div abs ٪ token eol ٪٪ calclist:/ * هیچ چیز *//در ابتدای ورودی مطابقت دارد|Calclist ext eol