نرمالسازی گرامر ها جلسه اول

1396/5/2 محمدرضا احمدآبادی 7139

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

 تو این جلسه و احتمالا اگه نرسیم جلسه اینده قصد دارم مبحث نرمال سازی گرامر ها را براتون بگم.

نرمال سازی گرامر ها:

برای گرامر های مستقل از متن دو فرم نرمال به نام های فرم نرمال چامسکی(CNF) و فرم نرمال گریباخ (GNF) توصیف میشود. برای نرمال سازی یک گرامر به هریک از این دوشکل لازم است بعضی از محدودیت ها در مورد قواعد تولید یک گرامر رعایت شود . این محدودیت ها در قالب ساده سازی گرامر ها مطرح میشوند.  بنابراین  ساده سازی یک گرامر به معنی اعمال محدودیت هایی روی آن خواهد بود، که هرچند ممکن است  تعداد قواعد تولید را افزایش دهد اما غالبا  عمل اشتقاق برای تولید یک رشته را کوتاهتر میکند.

( پس ساده سازی به معنای کم شدن قواعد تولید نیست بلکه شاید باعث افزایش قواعد تولید شود.)

ساده سازی گرامرها:

  1. حذف قوانین تولید لامبدا(λ):

هر قاعده به فرم A→λ  که در آن A ԑV باشد را یک قاعده تولید λ (قانون تهی) مینامند. حذف قوانین تولید λ در یک گرامر باعث میشود تا اشتقاق کوتاهتری برای رسیدن به یک رشته داشته باشیم. به متغیرهایی که در یک گرامر مستقل از متن میتوانند λ تولید کنند اصطلاحا متغیرهای میرا یا nullable  گفته میشود . حذف قوانین تولید λ در یک گرامر  مستقل از متن شامل دو مرحله است:

  • یافتن متغیرهای nullable
  • حذف متغیرهای nullable

      یافتن متغیرهای nullable : متغیرهایی که در یک گرامر میتوانند λ تولید کنند بر دو نوع هستند: دسته اول متغیرهایی که به طور مستقیم  λ تولید میکنند و دسته دوم متغیرهایی که به طور غیر مستقیم λ تولید خواهند کرد.

مثال) در گرامر زیرمتغیرهای nullable را بیابید.

S → aA|BC

A →Aa|Bb

B →a|λ

C →b|B

 

خب در این گرامر چیزی که به صورت واضح  و عیان هست این هست که متغیر B داره λ تولید میکنه پس متغیر B جز nullable های ما خواهد بود. اما این پایان ماجرا نیست  باید ببینیم ایا متغیری به واسطه متغیر B ، λ تولید میکنه یا نه؟ اخرین خط گرامر نوشته C→b|B  ، متغیر C  یکی از قواعد تولیدش B هست  خب B هم لامبدا تولید میکنه پس متغیر C هم میتونه λ تولید کنه. حالا یه نگاه به متغیر شروع بندازید ، قانون دوم این متغیر را ببینید ، این قاعده هم میتونه λ بشه. پس متغیر شروع هم جز nullable خواهد بود. پس مجموعه nullable های ما خواهد بود:

 

Nullable={B,C,S}

حذف متغیرهای nullable :

برای حذف متغیرهای nullable  ما باید اینطوری عمل کنیم که اگر متغیری nullable هست یک بار خود اون متغیر را مینویسیم و یک بار هم در کنار اون قاعده  فرض میکنیم که این متغیر لامبدا تولید میکند و ان را نمینویسیم.

استثنا: اگر متغیر شروع λ تولید کند باید به انتهای قاعده متغیر شروع  قاعده تولید λ اضافه شود.

مثال ) با توجه به گرامر بالا قواعد تولید λ را حذف کرده و گرامر را باز نویسی کنید.

ما در قسمت قبلی به دست اوردیم که متغیر های nullable ما چیا هستند. خب برای اینکه تولید λ را حذف کنیم باید اول متغیری که λ تولید میکند را اصلاح کنیم و قاعده تولید λ آن را حذف کنیم. پس در مرحله اول خواهیم داشت:

B→b

حالا میگردیم داخل گرامر وقواعدی که داخل آن ها متغیر nullable وجود دارد را اصلاح میکنیم. مثلا قاعده دوم گرامر هست:

A →Aa|Bb

این قاعده باید اصلاح شود چون متغیر B در دسته nullable  های ما وجود داشت. طبق جمله بالا من باید قاعده دوم متغیر A را یکبار با متغیر و یکبار بدون متغیر بنویسم. پس خواهم داشت:

A →Aa|Bb|b

برای متغیر شروع هم باید همین کار را انجام بدم چون متغیر شروع هم جز همین دسته بود.

تیرخلاص: اگر در یک قاعده تولید بیش از چند متغیر وجود داشته باشد که باعث تولید λ باشد باید تمامی حالات متغیر و بدون متغیر آن نوشته شود.

S →aA|BC

همه مشکلات من سر قاعده دوم متغیر شروع هست   در این قاعده من دارم:

S →BC

برای باز نویسی این قاعده مرحله به مرحله بریم جلو. اول فرض میکنم که نه متغیرB و نه متغیر C هیچکدوم λ تولید نمیکنند . پس خودشون را خواهم نوشت. در مرحله دوم فرض من بر این خواهد بود که متغیر B ، λ تولید خواهد کرد پس آن را نمینویسم و در نتیجه قاعده تولید من خواهد شد:

S →C

در مرحله سوم فرض خودمو معکوس میکنم و متغیر C را عامل تولید λ خواهم دید. پس قاعده تولید من خواهد شد:

S → B

حالا نوبت به این هست که فرض خودمو بر این بزارم که هر دو متغیر B,C باعث تولید λ شوند پس باید هردومتغیر حذف شوند. اما اینجا یه تبصره وجود داره و اون هم این هست که با این کار مجبور خواهیم بود که در این قاعده بنویسیم λ. واین خلاف کاری هست که میخواهیم انجام دهیم. پس از این حالت صرف نظر خواهیم کرد. پس در نهایت قواعد تولید متغیر شروع ما خواهد بود:

S →aA|BC|C|B

به نظرتون کار ما این جا تمام هست؟ تبصره متغیر شروع که یادتون نرفته. پس باید به این قانون اضافه کنیم. پس شکل نهایی قاعده تولید متغیر شروع خواهد بود:

S →aA|BC|C|B|λ

دلیل نوشتن λ این هست که ما نباید با ساده سازی گرامر زبان گرامرمون عوض بشه. خب این زبان شاید بتواند λ هم تولید کند اما اگر ما این قاعده را از آن بگیریم مثل این هست که در زبان این گرامر دست بردیم. (ولی ما در اصل میخواهیم گرامر را ساده کنیم نه تحریف)

و حالا میرسیم به اخرین قاعده گرامر یعنی:

C →b|B

قاعده دوم این متغیر باید بازنویسی بشه ، یه بار خود متغیر B و یه بار با حذف اون متغیر . اما اگر من این کار را بکنم مجبور خواهم بود که درصورت حذف B از سمبل λ استفاده کنم و این خلاف قانون هست پس از شکل قاعده بدون متغیر B مجبور هستم که صرف نظر کنم.

گرامر نهایی( بازنویسی شده) ما خواهد بود:

S →aA|BC|C|B|λ

A →Aa|Bb|b

B →a

C →b|B

 

مثال) قوانین λ را در گرامر زیر حذف کنید.

 

S →ABaC

A →BC

B →d|λ

C →D|λ

D →d

 

مثل روش مثال قبلی شروع میکنیم از ظاهر حرکت میکنیم روبه باطن. دو متغیر B,C هرکدوم مستقیما دارند λ تولید میکنند. حالا بریم سراغ متغیری که به صورت غیر مستقیم رشته λ را تولید میکند. در این گرامر متغیر A داره دو متغیر BC را اشاره بهشون میکنه پس این متغیر هم میتونه λ تولید کند . متغیر شروع که اصلا نمیتونه λ تولید کنه چون یه الفبای a داخل قانونش به کار رفته و این الفبا مانع از این میشود که رشته λ تولید شود . پس nullable های ما خواهد بود :

 

Nullable={A,B,C}

حالا باید قوانین گرامر را باز نویسی کنیم . در متغیر شروع ما سه متغیر داریم که دارند λ تولید میکنند پس باید همه حالات ممکن را برای این گرامر در متغیر شروع بنویسیم. یعنی یه بار خود متغیر و یه بار هم همون قانون بدون اون متغیر . پس قوانین تولید مربوط به متغیر شروع ما خواهد شد:

S →ABaC|BaC|AaC|Aba|aC|Ba|Aa|a

این از بازنویسی قوانین متغیر شروع. حالا بریم خط دوم سراغ متغیر A . همون طور که در مثال قبلی براتون گفتم ما باید سه حالت برای متغیر A بنویسیم پس خواهیم داشت:

A →BC|C|B

رسیدیم به خط بعدی گرامر . حالا باید متغیر B را بدون λ بازنویسی کنیم . یعنی تولید λ را از این متغیر بگیریم.

B →d

همین کار را هم برای متغیر C باید انجام دهیم .

C →D

و در اخر هم میرسیم به متغیر D که احتیاج به بازنویسی نداره و خودش را مینویسیم.

D →d

شکل نهایی گرامر ما خواهد شد:

S →ABaC|BaC|AaC|Aba|aC|Ba|Aa|a

A →BC|C|B

B →d

C →D

D →d

 

  1. حذف قوانین زنجیر:

 

به قوانینی مانند A →B که در آن  A,B ԑ V باشد در اصطلاح قوانین زنجیر یا واحد یا یکه میگویند. از آنجایی که در قوانین زنجیر نه الفبایی در سمت راست قانون وجود دارد و نه این که تعداد متغیرهارا تغییر میدهد ، لذا استفاده از آن ها در عمل اشتقاق تنها باعث افزایش تعداد مراحل اشتقاق میشود . بنابراین برای کوتاه تر شدن اشتقاق ، قوانین زنجیر یک گرامر را حذف میکنیم.

روند حذف زنجیر:

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

مثال) در گرامر زیر قوانین زنجیر را حذف کنید.

S →aA|B

A→a|B

B →bB|C

C →b

 

خب برای اینکه زنجیر های گرامر را حذف کنیم باید اول رنجیرهارا شناسایی کنیم . زنجیر دو نوع خواهیم داشت زنجیرهای اشکار و زنجیرهای پنهان. (دلیل این که گفتم باید از یک گراف استفاده کنیم همین هست که زنجیرهای پنهان را بتونیم شناسایی کنیم )

 

من تو این گرامر زنجیر هایی که میبینم  ایناها هست:

S →B

A →B

B →C

 

پس گراف وابستگی ما خواهد شد:

 

گراف وابستگی

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

S →C

A →C

 

حالا باید زنجیرهارا حذف کنیم. اخرین جمله روند حذف زنجیر را بخوانید. این طور گفته :

 

برای بدست آوردن گرامر حاصل ابتدا گرامر اولیه را بدون هیچ یک از قواعد  زنجیرش مینویسیم

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

S →aA

A →a

B →bB

C →b

 

 

 

سپس با توجه به هریک از مسیرها و با استفاده از گرامر جدید اگر مسیری به صورت  X →Y (از X به Y ) وجود دارد، هر آنچه Y تولید میکند ، به X اضافه میکنیم.

حالا باید یه نیم نگاه به زنجیرهابیاندازیم و ببینیم چه متغیرهایی دارای زنجیر هستند و متغیر زنجیرشون چیست.

مثلا متغیر S دارای دو زنجیر هست .   

S →B , S →C  . درگرامر بدون زنجیر که نوشتیم ، هر آنچه که متغیر B , C دارد تولید میکند باید به S اضافه کنیم پس خواهیم داشت:

S →aA|bB|b

متغیر A هم مثل S دارای دوتا زنجیر هست .

A →B , A →C  .  پس هر آنچه متغیر های B,C در گرامر بدون زنجیر تولید میکنند باید به متغیر A اضافه شود . یعنی خواهیم داشت:

A →a|bB|b

متغیر B  دارای یک زنجیر است . B →C   پس هر آنچه متغیر C در گرامر بدون زنجیر دارد تولید میکند باید به متغیر B اضافه شود. 

B →bB|b

ودر انتها قاعده  C →b که زنجیر نیست باید همان را به انتهای گرامر اضافه کنیم . پس گرامر نهایی ما خواهد شد:

S →aA|bB|b

A →a|bB|b

B →bB|b

C →b

 

امیدوارم این جمله ((اگر مسیری به صورت  X →Y (از X به Y ) وجود دارد، هر آنچه Y تولید میکند ، به X اضافه میکنیم.)) بعد از این مثال ملکه ذهنتون شده باشه.

 

گرامری که در مثال دوم حذف λ به دست آوردیم را میخوام قاعده حذف زنجیر را روی اون براتون پیاده کنم. این گرامری هست که ما به دست اوردیم :

S →ABaC|BaC|AaC|Aba|aC|Ba|Aa|a

A →BC|C|B

B →d

C →D

D →d

 

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

 

A →B

A→C

C→D

 

دیگه من زنجیر اشکاری نمیبینم. پس میرم سراغ رسم گراف وابستگی.

 

رسم گراف وابستگی

 از این گراف من یه زنجیر پنهان میبینم .

A →D

حالا باید روند حذف زنجیر را روی این گرامر اجرا کنم گرامر بدون زنجیر من خواهد شد:

S →ABaC|Aba|AaC|BaC|Aa|aC|Ba|a

A→BC

B→d

D →d

 

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

 

متغیر شروع اصلا زنجیر نداشت پس عینا همه قواعدش باید نوشته بشه .

S →ABaC|Aba|AaC|BaC|Aa|aC|Ba|a

متغیر   سه تا زنجیر داشت  . اما هر سه زنجیر داشتن الفبای b را تولید میکردن پس من کافیه یکی از زنجیرهارا جایگذاری کنم  و مابقی چون تکراری خواهد بود از نوشتنش باید خودداری کنم.

A →BC|b

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

S →ABaC|Aba|AaC|BaC|Aa|aC|Ba|a

A→BC|b

B→d

D →d

C →d

 

  1. حذف متغیر های بدون استفاده (غیرمفید):

 

متغیر X را در یک گرامر مفید یا قابل استفاده میگوییم ، هر گاه دو شرط زیرراداشته باشد:

  1. از طریق متغیر X و طی چند مرحله  اشتقاق بتوانیم به یک رشته الفبا برسیم.
  2.  متغیر X از متغیر شروع قابل دسترس باشد.

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

متغیرهایی را که به هیچ وجه نتوان از آن ها به یک رشته از الفبا رسید متغیرهای بدون استفاده از جنبه اول و آن هایی را که از متغیر شروع نتوان به آن ها رسید متغیر بدون استفاده از جنبه دوم می نامند.

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

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

 

مثال) متغیر های غیر مفید از جنبه اول  و دوم را در گرامر زیر پیدا کنیدو پس از حذف گرامر را بازنویسی کنید.

S →aS|A|C

A →a

B→aa

C →aCb

 

غیر مفید جنبه اول میگفت : متغیری که به یک رشته از الفبا نتواند برسد. متغیر S  میتونه به یک رشته الفبا برسه. متغیر A که مستقیم الفبای a را تولید میکند متغیر B هم در حال تولید  رشته aa هست. متغیر C یک قاعده بازگشتی هست و راه خلاصی از بازگشتی را ندارد پس نمیتواند یک رشته تولید کند. 

 

متغیر غیر مفید از جنبه اول={C}

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

پس گرامر نهایی من خواهد شد:

S →aS|A

A →a

B →aa

 

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

 

غیر مفید جنبه دوم میگفت: متغیری که  از متغیر شروع (چه مستقیم و چه با واسطه) قابل دسترسی نباشد  باید حذف گردد.

حالا در این گرامر تنها متغیر B هست که قابل دسترسی نیست. پس باید این متغیر و قوانین تولید آن حذف شود. پس گرامر نهایی ما خواهد شد:

S →aS|A

A →a

 

مثال) در گرامر زیر متغیر های غیر مفید را حذف کنید  و سپس زبان گرامر را بدست آورید.

 

S →AC|BS|B

A→aA|aF

B →CF|b

C→cC|D

D→aD|BD|C

E →aA|BSA

F→bB|b

 

این مثال به عنوان تمرین برای شما . جوابتون را برام بفرستید  .

 

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

انچه در نظریه خواهید دید...

در جلسه آینده قصد دارم مبحث ساده سازی و نرمال سازی گرامر را تموم کنم.

کلمات کلیدی

محمدرضا احندآبادی
مهندس نرم افزار
کارشناسی مهندسی نرم افزار
مدرس دوره نظریه زبان ها و ماشین ها