پارسینگ LR(1(

[Neda.T]

سلام
برای نوشتن یه برنامه که یه گرامر ثابت داره و جدول پارسینگ هم از قبل داده شده راهنمایی میخواستم
کاربر یه رشته ورودی میده و خروجی جدول تجزیه رو باید نمایش بده یعنی اینکه انتقال و کاهش به چه صورتی انجام میشه تا اینکه به acc برسه.
مثلا وقتی توی حالت 2 در پایانه id داشته باشیم r4 و سر رشته وردی هم id باشه و سر استک 2 پس باید با توجه به قاعده 4 کاهش صورت بگیره و باید از جدول پارسینگ عدد قسمت goto رو پیدا کنه و چاپ کنه!
اگه کمکم کنین یا حداقل یه راهنمایی کوچیک برای شروع ممنون میشم

[همایون افشاری]

سوال واقعا خیلی کلیه
قدم اول اینه که برای اطلاعاتی که استفاده می کنید ساختار داده مناسب رو انتخاب کنید مثلا برای جدول پارسینگ (درست یادم نیست اما فکر می کنم یه جور state machine بود!) و ...
قدم دوم پیاده سازی الگوریتم مورد نظر هست که اگه ساختار داده مناسب باشه سخت نیست یعنی با توجه به قواعد و مقادیر استک و ورودی کار مناسب انجام بگیره...

[saeed-esfandi]

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

[Neda.T]

سلام خیلی ممنون که جواب دادین
از روش پارسینگ LR(1( باید استفاده کنم.اینکه گفتین برای شیفت و ردیوس از مثبت و منفی میشه استفاده کرد ایده خوبی بود ممنون
شما منظورتون اینه که جدول پارسینگ رو که باید به برنامه بدم از پشته استفاده کنم؟از آرایه نمیشه استفاده کرد؟
قواعد گرامر رو چطور؟اینکه چطوری موقع ردیوس کردن از کدوم قاعده باید بفهمه استفاده کنه!؟
ممنون

[saeed-esfandi]

خب الگوریتم ایهو برای LR1 اینه


let a be the first symbol of w$;
while(1) { /* repeat forever */
let s be the state on top of the stack;
if ( ACTION[s, a] = shift t ) {
push t onto the stack;
let a be the next input symbol;
} else if ( ACTION [s, a] = reduce A (3 ) {
pop \{31 symbols off t he stack;
let state t now be on top of the stack;
push GOTOft, A] onto the stack;
output the production A -» /?;
} else if ( ACTION[s,a] = accept ) break; /* parsing is done */
else call error-recovery routine;
}

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

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

[maktoom]

سلام
مراجعه کنید به کتاب آقای آلفرد آهو. تمامی روش ها رو بحث کرده. ضمن اینکه الگوریتم و شبه کد رو هم گذاشته.