تحلیل نحوی (Syntax Analysis)
که همان تجزیه یا parsing است .
پارسینگ وظیفه اش برعکس است ، یعنی چگونه اشتقاق انجام شده است .
در پارسینگ در اشتقاقهای ایجاد شده برعکس مگاه می کنیم تا به چگونگی اشتقاق پی ببریم .
روش تجزیه Parsing
1. روشهای عمومی { که این روش ها کارایی بهینه ندارند }
2. روشهای بالا به پایین
در این روش د درخت تجزیه از ریشه ها به سمت برگها حرکت می کنیم و روند طی شده را از ریشه ها به برگها طی می کنیم و یا در جمله ای بهتر آن که درخت تجزیه را از ریشه به برگها تولید می کنیم .
که به طور کلی به دو روش :
· پایین گرد
· LL(1)
دسته بندی می شوند .
3. روشهای پایین به بالا
در این روش برعکس روش قبل درخت تجزیه از برگها آغاز شده و به سمت ریشه گسترش می یابد .
که این روش نیز به سه گروه کلی تقسیم بندی می شود :
· تقدم عملگر
· تقدم ساده
· LR که این روش هم به طور کلی به 3 روش دیگر دسته بندی می شود :
1. SLR
2. LALR
3. CLR
در اینجا ما به روشهای پایین به بالا می پردازیم .
تجزیه پایین به بالا Bottom-Up Parsing
مقدمه:
ایده اصلی آن ، ساخت درخت تجزیه با شروع از برگ ها تا رسیدن به ریشه درخت می باشد .
در این روش از سمت راست گرامرها شروع کرده و با تشخیص آنها به سمت چپ هر گرامر رسیده و در آخر آنقدر جلو یم رویم تا به Start Symbol برسیم .
به طور مثال در گرامر زیر :
S -> aABe (1
A -> Abc|b (2,3
B->d (4
و در زیر رشته تولید شده توسط آن :
abbcde
این مراحل را طی می کنیم :
Abbcde
Abcde (3 گرامر سوم
aAde (2
aABe (4
S (1
مشاهده می شود که در گرامر از سمت چپ ها به سمت راست ها می رویم تا به سمبل شروع برسیم .
رشته ورودی را با جستجو به دنبال زیررشته ای که با سمت راست یک قاعده تولید منطبق شود پویش می کنیم .
مساله اصلی در تجزیه پایین به بالا انتخاب درست دست گیره (handle) و قاعده مربوط به آن است .
هدف :
ساخت درخت پارس رشته w با شروع از برگها تا رسیدن به ریشه پارسر به طور مکرر سمت راست یک قاعده تولید را در مقابل یک زیر رشته در فرم جمله ای راست تطابق می دهد .
در هر تطابق برای ساخت درخت پارس یک عمل کاهش reduce انجام میشود .
o هر کاهش زیررشته تطابق یافته ها با ناپایانه واقع در سمت چپ قاعده تولید جایگزین می کند و
o هر کاهش ، یک گره داخلی به درخت تجزیه ها می افزاید .
o حاصل هر عمل کاهش یک فرم جمله ای دیگر است.
o در نهایت حاصل یک اشتقاق راست به صورت معکوس خواهد بود .
دستگیره Handle
دسگیره بر اساس زیررشته ای تعیین می شود که:
- با سمت راست یک قاعده تولید A->α تطابق یابد
- کاهش α به A یک مرحله از عکس اشتقاق راست می باشد
به شکل رسمی : یک دستگیره از فرم جمله ای راست γ یک زوج مرتب از قاعده تولید βA -> و مکانی است که β در آن دریافت می شود .
Handle(γ) = <A -> β ,k>
1<= k <= |β|
اگر <A -> β ,k> دستگیره γ باشد ، آنگاه جایگزین β در مکان k با A، فرم جمله ای راست قبلی در اشتقاق راست را مشخص می کند .
هرس کردن دستگیره ها Handle pruning
برای بنا کردن درخت تجزیه از پایین به بالا ، فرزندان یک گره خذف می شوند و با پدر جایگزین می شوند .
قضیه:
اگر گرامر G مبهم نباشد آنگاه هر فرم جکله ای راست یک دستگیره یکتا دارد .
پارسر شیفت-کاهش Shift-Reduce
یکی از روشهای پیاده سازی هرس کردن دستگیره ها ، پارسر پایین به بالاست که shift-reduce parser نام دارد . این پارسر مطابق مدل [1]PDA از یک پشته و یک بافر ورودی استفاده می کند .
1. ابتدا یک علامت داده درون پشته push می شود.
2. مراحل زیر را تکرار می کنیم تاب الای پشته علامت δ و توکن جاری $ گردد :
i. دستگیره را می یابیم
اگر دستگیره ای بالای پشته وجود نداشت توکن ورودی را درون پشته شیفت می دهیم .
ii. دستگیره یافت شده را هرس می کنیم .
اگر دستگیره <A -> β ,k> بر روی پشته قرار داشت عمل reduce را انجام می دهیم : | β | علامت از بالای پشته pop می کنیم و به جای آن A را push می کنیم .
یک پارسر شیفت=کاهش چهار عمل اصلی دارد :
1. shift : push کردن توکن جاری به پشته
2. reduce : pop کردن دستگیره از بالای پشته و قرار دادن ناپایانه سمت راست قاعده به جای آن در پشته
3. accept : پارس با موفقیت حاتمه پیدا کند . ( lookahead =$, top=S)
4. error : در صورت عدم تطابق نحوی
یک دستگیره همیشه بالای پشته است چون گرامر و زبان مستقل از متن است .
دو نوع تداخل Conflict داریم :
o Shift –reduce conflict عدم تشخیص شیفت یا کاهش
o Reduce-reduce conflict عدم تشخیص قاعده مورد استفاده برای reduce
--------------------------------------------------------------------------------
[1] Push Down Automata
ممنون ، برای تحقیقم به مفید بود