برنامه تشخیص عضویت یک جمله در یک زبان مستقل از متن

[mostafa_shaeri_tj]

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

همانطور که میدونید زبان های مستقل از متن توسط گرامرهای مستقل از متن تعریف می شوند. البته درک یک گرامر مستقل از متن نیاز به داشتن اطلاعات کافی در زمینه ی نظزیه زبان ها و ماشین ها رو داره. اینجا یه مثال از یک زبان ساده ی مستقل از متن رو میارم :




S---->AB
A---->BB
B---->AB
A---->a
B---->b



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

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

فقط یه چیزایی رو باید رعایت کنید :





1- متغییر شروع تون رو S بگیرید.
2-به جای نوشتن S---->AB باید بنویسد S>AB.
3-بعد از واردکردن آخرین قانون گرامر دیگر اینتر نکنید.
4- و از همه مهمتر اینکه گرامر باید در فرم نرمال چامسکی باشه.



تصویر نرم افزار رو که نحوه ی نوشتن گرامر را نشان میده همراه برنامه ضمیمه کردم.

درصورت درست بودن جمله پیغام Valid Sentence ظاهر خواهد شد.

[mortezamsp]

باسلام.

روش کارت چطوره ؟ یعنی میای یه رشته رو میگیری ، بعد حرف به حرف جلومیری میبینی با کدوم گرامر میشه این حرف رو تولیدکرد ، بعد یه درخت تشکیل میدی و همه رو تا آخر چک میکنی ؟؟

باید سخت تر از این باشه . نه ؟ مثلا اینکه درهر مرحله باید چند حرف از رشته رو بخونی ،یا ... بیشتر توضیح بده .

[mostafa_shaeri_tj]

سلام. نه اینط.وری نیست !

اول میام تک تک حروف جمله رو بررسی می کنم و می بینم که تک تک شون جدا جدا آیا توی زبان ما قرار دارند؟

مثلا :


S---->AB
A---->BB
B---->AB
A---->a
B---->b

و جمله ی aabc : میام تک تک شونو چک کی کنم می بینم a و b به تنهایی در زبان اومدن (دوتا قانون آخر) ولی c اصلا در زبان وجود نداره، بنا براین این جمله در زبان ما وجود نداره.


حالا اگر جمله ی ما aab بود : بعد از اینکه دیدم هرکدوم جداگانه تنهایی در زبان وجود داشت. میریم سراغ دوتایی ها : یعنی میبینیم که آیا تو زبان مون aa و ab داریم ؟ و همینطور ادامه مییدم تا آخر که آخر میرسیم به جمله ی 3 تایی که کل جمله ی ماست.

میدونم گیج کننده هست.:گیج: من اینو بوسیله برنامه نویسی پویا حلش کردم. ضرب ماتریس ها هم توش به کار بردم.

[newamir]

این مسأله رو با الگوریتم CYK میشه حل کرد. البته CYK هم در واقع یه الگویتم پویاست.

[zizi_zizi69]

سلام
آقا من متوجه نشدم این برنامه شما چطور کار میکنه؟
من برای گرامر خودتون برنامه را چک کردم.گرامر شما باید رشته ab را بپذیره ولی برنامه شما پیغام not valid می ده.
الگوریتم کار چیه ؟من اگه هر گرامری بدم میتونه عملیات ساده سازی را روی گرامرها انجام بده؟
ممنون

[مریم نظری]

باسلام و تشکر از شما .اگر من کد برنامه را لازم داشته باشم چطور می تونم تهیه اش کنم؟آیا میشود این کد را یا مشابه ان را در اختیارم قرار دهید؟

[armiya]

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

[mostafa_shaeri_tj]

سلام
آقا من متوجه نشدم این برنامه شما چطور کار میکنه؟
من برای گرامر خودتون برنامه را چک کردم.گرامر شما باید رشته ab را بپذیره ولی برنامه شما پیغام not valid می ده.
الگوریتم کار چیه ؟من اگه هر گرامری بدم میتونه عملیات ساده سازی را روی گرامرها انجام بده؟
ممنون

سلام. شما مطمئنی که گرامر رو به فرم چامسکی وارد کردید؟







.اگر من کد برنامه را لازم داشته باشم چطور می تونم تهیه اش کنم؟آیا میشود این کد را یا مشابه ان را در اختیارم قرار دهید؟

در مورد گذاشتن کد هم به خاطر اینکه تمرین دانشگاهیه معذورم.

[mansoureh_92]

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

[saeedeh63]

سلام
من کد این الگوریتم رو لازم دارم الانم نمی تونید کدشو در اختیارمون بزارید
فروشی نیست؟

[majid_i68]

من برای فروش دارم ..خواستی پیام بده

[سعید مهکی]

salam....kassi hast ke code in algoritmo betone beman bede,??

[aminbl5]

دوستان من این برنامه رو ربا C++‎‎ نوشتم، به طوری که گرامری که بهش میدین نیاز نیست فرم نرمال (چامسکی یا ...) باشه، قابلیت مدیریت لوپ رو هم داره و الگوریتمی که استفاد میکنه کاملا ابتکاریه، اگه لازم داشتین( برنامه تحت consloe) پیام بدین بدم بهتون.

[hashemezati]

سلام برنامه (تشخیص عضویت یک جمله در یک زبان مستقل از متن) که به زبان ++C هستش و یا الگوریتمشو میخام اگه کسی داره لطفا به ایمیلم بفرسته
دستش درد نکنه
پیشاپیش ممنون
hashemezati1371@gmail.com

[davood1370]

سلام دوست عزیز من یه برنامه میخوام که در اون یک گرامر مستقل از متن رو گرفته و اون رو ساده کنه.( قانون لاندا و یکه و بی فایده رو حذف کنه) اگه کسی میدونه چجوری نوشته میشه خواهشا کمکم کنه خیلی نیاز دارم. با تشکر. ghane_davood@yahoo.com

[sajjadssh]

لینک دانلود مشکل داره چرا؟

[persina.group]

سلام

اونی که davood1370 خواسته ساده سازی (نرمال سازی) گرامر به فرم نرمال چامسکیه.
گروه ما نرمال سازی گرامر مستقل از متن رو با زبان جاوا انجام داده؛ سفارشیش هم می تونه بکنه (به انواع ساده سازی):
persina.blogfa.com

در صورتی که قبلا گرامر ما به CNF ساده شده باشه می شه با الگوریتم CYK که یک نمونه از الگوریتمهای برنامه نویسی پویاست و بنابراین با جدول سر و کار داره، تشخیص عضویت داشته باشیم.
کتاب Linz عنصر خانه ij رو به این صورت تعریف کرده:
http://manesht.ir/forum/attachment.php?thumbnail=798 (http://dl.dropbox.com/s/xl9xtu07h86fbsi/1.png)

یعنی برای خانه ij، تقاطع خانه های سطر i با خانه های ستون j به ترتیبی که مشخص شده باید در نظر گرفته شه: خانه اول سطر عنصر ij با خانه بعد از خانه عنصر در ستون این عنصر، خانه دوم سطر این عنصر با خانه بعدی در ستون این عنصر و ... تا وقتی در سطر این عنصر به خانه ij برسیم که کار رو در اینجا متوقف می کنیم.

این شکل خانه هایی که برای عنصر ij (خانه سبزرنگ) باید با هم در نظر گرفته بشن رو بهتر مشخص می کنه:
http://manesht.ir/forum/attachment.php?thumbnail=800 (http://dl.dropbox.com/s/0vpx2k1dq9dbesg/2.jpg)



از متغیر k برای حرکت روی خانه های سطر و ستون عنصر ij استفاده می شه. می تونید مثل متغیر یک حلقه for در نظر بگیریدش. یه شبه کد نه چندان دقیق برای نشون دادن عمل الگوریتم به این صورته:
کد:

for k = i to j-1 do
if X -> V[i,k]V[k+1,j] is a rule then
add X to V[i,j]

یعنی اگه از کنار هم گذاشتن دو متغیر خانه های ik و k+1,j یک قانون به صورت X->AB به دست اومد، X رو هم به V_ij اضافه کن (در هر خانه بیش از یک متغیر می تونه قرار بگیره).

فراموش نشه گرامر باید در فرم نرمال چامسکی باشه




منبع سایت مانشت (http://manesht.ir/forum/thread-2197.html)

[M._salimi75]

من میخام دوست عزیز
Maisamsalimi75@Gmail.com

[nastaran_mfz]

دوستان من این برنامه رو ربا C++‎‎ نوشتم، به طوری که گرامری که بهش میدین نیاز نیست فرم نرمال (چامسکی یا ...) باشه، قابلیت مدیریت لوپ رو هم داره و الگوریتمی که استفاد میکنه کاملا ابتکاریه، اگه لازم داشتین( برنامه تحت consloe) پیام بدین بدم بهتون.
سلام میشه به من گرامرشو بدین؟