(مبانی برنامه نویسی) تجزیه پائینگرد ( Recursive Descent Parsing ) (عمومی_ الکترونیک)

(مبانی برنامه نویسی) تجزیه پائینگرد ( Recursive Descent Parsing ) (عمومی_ الکترونیک)

پژوهشگر و نویسنده:  (  افشین رشید )

نکته: یکی از انواع پارسر ها که به صورت پیشگویانه عمل می کند پارسر پائینگرد یا (Recursive Descent) است. این پارسر بصورت بالا به پائین عمل میکند و در آن یک مجموعه رویه ها بطور بازگشتی رشته ورودی را مورد پردازش قرار می دهند .این رویه ها که برای پردازش رشته ورودی فراخوانی میشوند یک درخت پارس برای ورودی ایجاد میکنند.

علاوه بر رویه هایی که به ازای هر غیر پایانه وجود دارد یک پارسر پائینگرد از رویه دیگری بنام match برای تطبیق توکن های ورودی و پایانه های درخت تجزیه در حال ساخت استفاده می کند.یک پارسر پائینگرد به ازای هر غیرپایانه یک رویه دارد که دو کار انجام می دهد :

1 -تصمیم می گیرد که از کدام قاعده گرامر استفاده شود.

2 -از قاعده انتخاب شده استفاده میکند.

بعنوان مثال پارسر پائینگرد برای گرامر تعریف Type در زبان پاسکال دو رویه برای غیر پایانه های Type و Simple خواهد داشت.رویه match نیز بصورت زیر است :

Procedure match ( t : token );

 begin

 First روی رشته ای از پایانه ها و غیر پایانه ها عمل می کند .حاصل تابع (α(First مجموعه ای از پایانه ها است که در سمت چپ ترین قسمت از رشته های تولید شده از رشته α قرار می گیرند.تعریف رسمی تر این تابع بصورت زیر است:

First(α) = {a | α ═› aβ , a Є T , β Є (N U T)* }

به این ترتیب در گرامری که دو قاعده بصورت α → A و β → A داشته باشد پارسر پائینگرد با استفاده از First سمت راست این قواعد , قاعده مناسب را تعیین می کند بدون اینکه نیاز به عمل عقبگرد داشته باشد

نویسنده: دکتر (افشین رشید )