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 |
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 <=> ~(بالایی ها )