چگونگی ساخت جدول پارسینگ برای Simple precedence parser

[volvo B12]

با سلام خدمت همه ی دوستان
همانطور که عنوان تاپیک نشان می دهد سوالی داشتم در مورد پارسر تقدم ساده و اینکه چگونه در آن جدول پارسینگ رو بسازیم؟:متفکر:
چند تا نمونه مثال از ویکی پدیا و کتابهای پارسه نگاه کردم اما نفهمیدم چطوری جدول رو ساختند؟:اشتباه:
ضمن اینکه یکی از دوستان می گفت اصلا جدول این نوع پارسرها با جدول پارسرهایی مثل تقدم عملگر فرقی نمی کنه !!! :قهقهه: که من هم مثال ویکی پدیا رو نشونش دادم ولی هیچکدوممون سر در نیاوردیم!!!:متعجب:
اگه کسی اطلاعاتی راجع به پارسر تقدم ساده و نحوه ساخت جدول پارسینگ در اون رو داره با یه مثال لطف کنه اینجا بزاره :چشمک:
ممنون :بوس:

[hessam8008]

با سلام
من هم یه سوال کنکور با پارسر تقدم ساده دیدم اما از حلش چیزی سر در نیاوردم
تو فاروم پارسه راجعبش بحث کرده می تونی بری اونجا البته همونطور که گفتید تو سایت ویکی پدیا کامل بحث کرده یه سرچ کنی پیداش می کنی
http://msc.parsehportal.com/viewtopic.php?f=30&t=702&sid=be81c2a75dcfecc1551251e01ab7305b (http://msc.parsehportal.com/viewtopic.php?f=30&t=702&sid=be81c2a75dcfecc1551251e01ab7305b)

[hessam8008]

با سلام
من هم یه سوال کنکور با پارسر تقدم ساده دیدم اما از حلش چیزی سر در نیاوردم
تو فاروم پارسه راجعبش بحث کرده می تونی بری اونجا البته همونطور که گفتید تو سایت ویکی پدیا کامل بحث کرده یه سرچ کنی پیداش می کنی
http://msc.parsehportal.com/viewtopic.php?f=30&t=702&sid=be81c2a75dcfecc1551251e01ab7305b (http://msc.parsehportal.com/viewtopic.php?f=30&t=702&sid=be81c2a75dcfecc1551251e01ab7305b)

[volvo B12]

سلام مجدد
آقا کسی نیست به ما کمک کنه؟!!! :گریه:

[hessam8008]

سلام
من دوبار پست زدم نمی دونم چرا نمی رسه و سایت پیام های مختلفی بهم داد!!!

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

[volvo B12]

سلام و تشکر از شما
جای شکرش باقیه که حداقل یه نفر یه راهنمایی ما رو فرمود
ولی با کمال احترام به کاربر محترم hessam8008 می گویم آبا واقعا از مطالب داخل کتاب آقای دکتر مطلب مورد نظر بنده درمیاد؟
الان دارم روش کار می کنم تا چند روز دیگه خودم جواب سوالم رو ارائه خواهم کرد
ممنون

[volvo B12]

با سلام مجدد و عذر خواهی بابت تاخیر حدود 20 روزه در پاسخ به سوال خودم:لبخند:

مورد اول در پاسخ دوستمون اینکه در کتاب استاد محبوبم جناب آقای دکتر دلداری مبحث پارسر تقدم ساده تشریح نشده و با ارائه تمرینی به عهده خواننده گذاشته شده است و البته خودم شخصا از ایشان دلیل عدم تشریح این مبحث رو پرسیدم که استاد هم پاسخ قانع کننده ای برای آن داشتند

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






روش پارسینگ تقدم ساده

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



1- دارای قاعده اپسیلون نباشند
2- سمت راست هیچ دو قاعده ای از گرامر نباید یکسان باشد

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

چگونگی ساخت جدول پارسینگ
برای این منظور ابتدا روابط تقدم ساده بین ترمینال ها و غیرترمینال ها و علامت $ در گرامر تعریف می شود
برای این کار دو تابع Head و Tail که روی مجموعه ی غیرترمینال ها ی گرامر عمل می کنند و مجموعه ای از ترمینال ها و غیرترمینال های گرامر را تولید می کنند تعریف می شوند :


Head(A) = {Y| A -> Yx}
Tail(A) = {Y| A -> xY


نکته 1 :
برای به دست آوردن Head و Tail های یک گرامر برای شامل شدن علامت $ در فرآیند مذکور قاعده ی M->S$S را به ابتدای گرامر اضافه می کنیم


نکته 2 :
اگر قاعده ای به شکل A->BxCداشته باشیم آنگاه اعضای Head(B) در Head(A) و هچنین اعضای Tail(C) در Tail(A قرار دارد


به عنوان مثال مجموعه ی Head و Tail را برای غیرترمینال های گرامر زیر بدست می آوریم:


S->+AB|-
A->(A*|*
B->c





داریم:


Head(S) = + -
Head(A) = ( *
Head(B) = c
Head(M) = $


Tail(S) = - c B
Tail(A) = *
Tail(B) = c
Tail(M) = $





قوانین به دست آوردن روابط تقدم ساده میان ترمینال ها و غیرترمینال های گرامر

1- اگر U -> ... XY ... آنگاه X=Y

2- اگرU -> ... XA ... آنگاه X<Y به طوری که Y عضو Head(A)
3- اگر U -> ... AZ ... انگاه X>Y به طوری که X عضو Tail(A) و Y هم عضو Head(Z)


که X و Y و Z می توانند ترمینال یا غیرترمینال باشند در حالی که A فقط غیرترمینال است.

حال با استفاده از قوانین مذکور روابط بین ترمینال ها و غیرترمینال های گرامر فوق را به دست می آوریم :


طبق قاعده ی اول داریم : A=* (=A A=B +=A $=S S=$

طبق قاعده ی دوم داریم : +<* (<* (<( +<( $<- $<+


طبق قاعده ی سوم داریم : ->$ B>$ *>* c>$ *>c



حال که روابط مشخص شد نوبت به رسم جدول پارسینگ می رسد برای این کار کلیه ترمینال ها و غیرترمینال ها را در سطرها و هچنین در ستون ها نوشته سپس براساس روابط فوق جدول را مقدار دهی می کنیم یعنی چنانچه X R Y یعنی X با Y رابطه R داشته باشد آنگاه X را از سطرها و Y را از ستون ها انتخاب کرده و علامت R را در محل تلاقی ان ها در جدول پارسینگ تقدم ساده قرار می دهیم

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

[volvo B12]

ضمن عرض سلام مجدد به همه دوستان
در ارتباط با مبحث پارسرها که جستجو می کردم به مطالب بسیار متنوعی برخوردم که به خاطر احترام به دوستانم و همچنین به پاسداشت زحمات افرادی که در جهت توسعه علمی کشور گام بر می دارند و نمونه های ان را در تالارهای گفتگوی علمی مثل همین سایت خوب برنامه نویس زیاد می بینید دوست دارم آنها را برای سایرین ارایه دهم
ازهمین رو نرم افزاری با عنوان parsing Emulator که نرم افزاری کوچک و دارای یک فرم ساده هستش رو در اینجا قرار می دهم
توضیح اینکه این نرم افزار گرامری رو از کاربر دریافت کرده و براساس چند نوع از پارسرهای LR خروجی مناسب شامل جدول پارسینگ و همچنین مجموعه های First And Follow را به کاربر به شکلی بسیار ساده نمایش می دهد
من با این دید که از این نرم افزار برای مقاصد آموزشی استفاده می شود آن را در اینجا قرار می دهم اما اگر کسی از دوستان و صاحب نظران معتقد است با ارایه این نرم افزار حقی از شخص یا اشخاصی ضایع می گردد حتما موضوع را اطلاع دهد تا نسبت به رفع ان اقدام گردد
تشکر

http://up.iranblog.com/images/1gh1ys3epswrpum3aseg.zip

برای دانلود لطفا از لینک فوق استفاده نمایید