روش تقدم ساده

روش تقدم ساده Simple precedence  

این روش بهبود یافته تقدم عملگر است . در این روش رابطه بین پایانه ها و ناپایانه ها هم بررسی می شود.

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

ویژگی ها:

1.     وجود ناپایانه ها و پایانه های مجاور مجاز است .

2.     قاعده ε  نباید در گرامر وجود داشته باشد.

3.     محدودیت : سمت راست دو قاعده ای نباید یکسان باشد .

4.     جدول پارسی نباید حاوی تداخل باشد .

جدول پارس:

یک جدول مربعی با ابعاد (|T| + | N | + 1)  با توان 2 می باشد .

تعریف:

Head(U)={X => X α}

Tail (U)={X => α X}

Head: پایانه یا ناپایانه ای که در ابتدای فرم های جمله ای خاصل از U ظاهر شود .

Tail: پایانه یا ناپایانه هایی که انتهای فرم جمله ای ظاهر شده باشند .

روابط موجود در این روش:

 X = Y ó З U ( U -> .. XY ..)

X < Y ó З U ( U ->  .. X A ..) Y is member of head(A)

X < Head(A)

X > Y ó З U ( U ->  ..  A Y ..) X is member of Tail(A)

TaiL(A) . Y

برای مثال برای گرامر زیر:

N -> $S$ این خط را در ابتدا خود اضافه می کنیم                               ///

S ->(SS)

S -> c

	S	(	)	C	$
S	=	<	=	<	=
(	=	<		<
)	>	>	>	>	>
c	>	>	>	>	>
$	=	<		<	accepted

Head(S) = { ( ,c }

Tail(S) = { ),c }

X := stack top terminal / non-terminal

B := lookahead

if p[X,b] =  <    then push (<); push(b);

if p[X,b] =  =    then push (=); push(b);

if p[X,b] =  >    then reduce( );

if p[X,b] =        then  error( );

reduce: ابتدا دستگیره را پیدا می کنیم به این ترتیب که آنقدر در پشته پایین می رویم تا به اولین نماد کوچکتر برسیم رشته میان > و بالای پشته دستگیره است .

TOP: عنصر بالای پشته پس از حذف دستگیره

LHS : سمت چپ قاعده مورد استفاده برای کاهش

برای کاهش با توجه به تعاریف داده شده اگر روابط به صورت زیر باشد این کارها را انجام می دهیم:

If p[TOP,LHS] =  <   then  push(<);push(LHS);

If p[TOP,LHS] =  =   then  push(=);push(LHS);