مشکل چپگردی در روش تقدم ساده :
U -> U …
U -> …XU..
تداخل به صورت زیر خواهیم داشت:
X = U , X < U
راه حل آن است که :
U -> U ..
V -> …XW…
W -> U
که در این صورت اینگونه خواهد شد :
X = W
X < Head(W) ={U}
مشکل راست گردی:
U -> …U
V ->…UX..
رفع مشکل:
U -> …U
V -> ..W X…
W -> U
در پیوست باید گفت که در این مقاله X,Y,W هم می تواند ناپایانه باشد و هم پایانه .
روش تقدم ساده 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);
S -> $ E $ این خط را در ابتدا خود اضافه می کنیم
E -> E + T | T
T -> T*F | F
F -> (E) | id
که این گرامر دارای جدول پارس زیر است .
|
$ |
Id |
( |
) |
* |
+ |
|
|
> |
< |
> |
< |
> |
< |
+ |
|
< |
> |
< |
> |
< |
> |
* |
|
|
> |
= |
> |
> |
> |
) |
|
< |
|
< |
|
< |
< |
( |
|
< |
|
< |
|
< |
< |
id |
|
= |
> |
|
> |
> |
> |
$ |
اگر سطر اول b و ستون اول از چپ a باشد :
a := stack top terminal
b:= lookahead
اول از همه با push($) آغاز می شود .
if p[a,b] = < => a
if p[a,b] = = => a=b then push(=);push(b);
if p[a,b] = > => a>b then reduce();
if p[a,b] = => a b then error();
a+(a*a)
|
Input |
Stack |
|
a+(a*a)$ +(a*a)$ a*a)$ a*a)$ *a)$ *a)$ a)$ )$ )$ )$ $ $ $ |
$ $ N $N<+ $N<+<( $N<+<( $N<+<(N $N<+<(N<* $N<+<(N<* $N<+<(N<*N $N<+<(N $N<+<(N=) $N<+N $N |
reduce( ): یافتن دستگیره بالای پشته ، حذف آن از بالای پشته و قرار دادن ناپایانه نوعی N در بالای پشته
به عبارتی ساده تر آنقدر از بالای پشته پایین می آییم تا به اولین نماد کوچکتر برسیم. رشته میان نماد کوچکتر و بالای پشته و ناپایانه زیر > (در صورت وجود) دستگیره است .
حالا با یک عبارت ، جدول را تست می کنیم .
با حذف آنها یک ناپایانه N جایگزین می شود و همراه دستگیره کاهش می یابد .
روش به دست آوردن جدول پارس :
P: (T Ụ {$}) * (T Ụ {$}) ->{<,>,+, }
firstterm(A)={a :A=>a α or A =>B a α }
Lastterm(A)={ a :A=>α a or A =>α a β}
a = b <=> ЗU (U-> …ab…. Or U->…a W b ….)
a < b <=> ЗU (U-> a W , b is member of firstterm(W) )
a < first term (W)
a > b <=> ЗU (U-> W b , a is member of lastterm(W) )
lastterm(W) > b
a b <=> ~(بالایی ها )
تحلیل نحوی (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