نظریه زبان ها و ماشین ها گرامرها
سلام محمدرضا احمدآبادی هستم با جلسه هفتم آموزش نظریه زبان ها درخدمتتون هستم. خوش بختانه بعد از رایزنی های زیاد با رئیس خانه تکانی واین که هرچقدر بخواهید خانه را تمیز کنید فقط یه باد بهاری کافیه تا دوباره برگردیم به روزگار قبل از خانه تکانی تونستم از ایشون قبل از عید چند ساعتی مرخصی گرفته تا بیام براتون آموزش بدهم. البته برای این چند ساعت مرخصی قول اضافه کاری در آینده را به رئیس دادم. امروز میخواهیم مبحث گرامر هارو شروع کنیم .
اصلا گرامر چی هست؟ گرامر ابزاری هست برای نشان دادن رشته های یک زبان. هر گرامر برای توصیف یک زبان نوشته میشود و این گرامر باید به گونه ای باشد که تمامی رشته های مورد پذیرش آن زبان را بپذیرد. گرامر ابزاری هست که برای همه انواع زبان ها میتوان طراحی کرد.( بر خلاف عبارت های منظم که فقط برای زبان های منظم کاربرد داشت.)
هر گرامر یک چهارتایی به فرم G=(V,T,P,S) می باشد که در آن:
V : یک مجموعه متناهی و غیر تهی از نمادهایی است که به هر یک از آن ها یک متغییر یا غیرپایانی و (nonterminal ) میگویند.
T : یک مجموعه متناهی و غیر تهی از نمادهایی است که به هریک از آن ها یک الفبا یا پایانی و(terminal) میگویند.( گاهی در تعریف گرامر ها این مجموعه با T نشان داده میشود. )
P : مجموعه قواعد تولید گرامر است که هر قاعده در گرامر به شکل روبرو خواهد بود:
X → y
X ԑ (V ᴜ T)(V U T) ̽
یعنی x عضو دنباله ای به طول یک یا بیشتر از الفباها یا متغیرها می باشد.
Y ԑ (V ᴜ T) ̽
یعنی y عضو دنباله ای به طول صفر یا بیشتر از الفباها یا متغیرها می باشد.
به زبون خودمونی اگه بخوام این دو خطو بگم این میشه: سمت چپ یه قاعده نمیتونه تهی یا لامبدا قرار بگیره اما سمت راست این امکان هست.
S : متغیر شروع گرامر را اعلام میکند.
معمولا برای نوشتن گرامر ها از یکسری قرارداد ها استفاده میشود که عبارتند از:
معمولا از حروف بزرگ انگلیسی و گاها از عبارت ها به عنوان متغیر استفاده میشود.
معمولا از حروف کوچک انگلیسی و یا ارقام و یا عملگرهای ریاضی به عنوان سمبل های الفبا استفاده میشود.
معمولا قاعده یا قواعد موبوط به متغیر شروع در سطر اول قواعد نوشته میشود.
قاعده تهی: هر قاعده به فرم A→λ در یک گرامر را قاعده تهی مینامند.
معمولا در یک گرامر چنانچه دو قاعده به فرم A→α و A→β را داشته باشیم ، آنگاه این دو قاعده را که دارای سمت چپ یکسان و سمت راست های متفاوت هستند به صورت A→α|β نشان میدهند.
S →AB
A →a
B → b
دراین مثالی که براتون نوشتممتغیر S ، متغیر شروع گرامر هست حروف بزرگ نشان دهنده متغیر هامون هست و حروف کوچک نشان دهنده الفبا های ما هست. (طبق قراردادی که در بالا گفتم)
رشته در گرامر ها:
به دنباله ای از سمبل هایی که در تمامی آن هاالفبا یا پایانی ها باشد رشته میگویند.
شبه جمله در گرامر ها:به دنباله ای از سمبل های پایانی و غیر پایانیشبه جمله گفته میشود ، که می تواند هر دو را دارا باشد و یا تنها دارای غیرپایانیباشد.
پذیرش یک رشته توسط یک گرامر:
به عمل جایگذاری متغیرهای یک گرامر که از متغیر شروع آغاز شده و با توجه به قوانین گرامر به تولید یک رشته می انجامد ، اشتقاق میگویند.
نکته1: در هر مرحله اشتقاقتنها می توان یکی از متغیرها را جایگذاری نمود.
برای نشان دادن پذیرش یک رشته توسط یک گرامر از اشتقاق استفاده میشود.
مثال) با توجه به گرامر زیر و با استفاده از عمل اشتقاق یکرشته دلخواه از گرامر را تولید کنید.
S →AB
A →a
B → b
خب طبق دستورالعمل اشتقاق باید از متغیر شروع ، شروع کنیم . در ضمن یه مطلب بهتون بگمکه تو این مثال نیومده اما شما باید بدونید . فرض کنید یکی از این قواعدمدو دستوری بود یعنی مثلا به این بود A→a|aa در این جا شما حق ندارید از هردو صورت استفاده کنید .فقط یکی از این قوانین . مثلا اگر در یک سوال گفته باشند که فلان رشته را با این گرامر تولید کنید اون وقت شما باید ببنید با انتخاب کدوم قانون به رشته مورد نظر خواهید رسید. یعنی در اون جا انتخاب های شما هدف دار خواهد بود .
خب در این مثال متغیر شروع یه قاعده داره پس همونو مینویسم:
S →AB
حالا به جای متغیر A ، طبق قانون A → a الفبای a را جایگذاری میکنم. پس خواهیم داشت:
S →AB →aB
این دفعه نوبت به سمبل B هست که مقدار آن را جایگذاری کنم پس رشته نهایی من که شامل هیچ متغیری نخواهد بود به این ترتیب خواهد بود:
S →AB →aB →ab
یه مطلب خنده دار بهتون بگم: تو صورت سوال من گفتم رشته دلخواهتون را تولید کنید . اما این گرامر فقط همین رشته ab را تولید میکند. پس شما مجبور هستید که رشته دلخواهتون رشته ab باشد .
نکته2 : در هر عمل اشتقاقبرای تولید یک رشته ممکن است چندین جمله وجود داشته باشد اما تنها یک رشته خواهیم داشت .
نکته 3: به تعداد مراحل جایگذاری برای تولید یک رشته ، تعداد مراحل اشتقاق گفته میشود.
انواع اشتقاق:
دو نوع اشتقاق خاص وجود دارد
اشتقاق از چپ( سمت چپ ترین اشتقاق): نوعی از اشتقاق است که در آن برای تولید یک رشته همواره در هر مرحله از اشتقاق سمت چپ ترین متغیر برای جایگذاری انتخاب میشود. در مثال بالا نحوه تولید رشته مورد نظر از طریق همین اشتقاق انجام دادم.
اشتقاق از راست( سمت راست ترین اشتقاق): نوعی از اشتقاق است که در آن برای تولید یک رشته همواره در هر مرحله از اشتقاق سمت راست ترین متغیر برای جایگذاری انتخاب میشود.
برای مثال در گرامر بالا اگر از سمت راست شروع میکردم به جایگذاری یعنی اول B را جایگذاری میکردم انگاه اشتقاق از سمت راست میشد.
نکته 4: الزاما همه اشتقاق هایا ازچپ و یا از راست نیستند. ممکن هست در یه مرحله اشتقاق از چپ داشته باشیم و در مرحله بعدی اشتقاق از راست . به این حالتاسمی داده نشده اما نه ازچپ هست و نه از راست ، چون اگر بخواهیم مثلا اشتقاق از چپ داشته باشیم باید تک تک مراحلمون اشتقاق از چپ داشته باشه.
درخت اشتقاق:
به نمایش درختی عمل اشتقاق ، درخت اشتقاق گفته میشود، که در رسم آن باید به نکات زیر توجه کنید:
در هر گره از درخت اشتقاق تنها یک سمبل چه پایانی و چه غیرپایانی قرار میگیرد.
ریشه درخت اشتقاق متغیر شروع گرامر خواهد بود.
متغیرهای گرامر در گره های داخلی درخت اشتقاق خواهند بود .
پایانی های گرامر و همین طور سمبل λ در برگ های درخت خواهند بود.
برای بسط دادن یک متغیر موجود در یک گره تنها میتوانیم یکی از قواعد آن متغیر را استفاده کنیم.
رشته حاصل از پایانی های موجود در برگ ها از چپ به راست همان رشته ای است که توسط گرامر تولید میشود.
مثال ) درخت اشتقاق گرامری که براتون نوشتم به این صورت خواهد بود.
آموزش نظریه زبان ها و ماشین ها
خب دوستان گرامی به پایان مطالب امروزمون رسیدیم . پیشاپیش سال جدیدو بهتون تبریک میگم و امیدوارم سالی پر از موفقیت و سربلندی براتون در تقدیر باشه . اگه حرفی ، سخنی ، لفظی اشتباه به کار بردم که باعث شده ناراحتتون کنم از همتون معذرت میخوام و امیدوارم به بزرگواری خودتون ببخشید. البته قول نمیدم ولی سعیمو میکنم که دیگه از این کلمات استفاده نکنم.
لحظه سال تحویل دعا برای من و دوستانم فراموشتون نشه.
آنچه در نظریه خواهید دید...
برای جلسه آینده قصد دارمزبان یک گرامر و انواع گرامرهارا براتون بگم
شادو موفق و سربلند باشید
نظرات کاربران