�ݺ�ߣ

Recursive-descent:
By: Fereshteh Jadidi 2
proc A
If lookahead = ‘a’ then lookahead=nexttoken() else
{sw=1; error;}
call B;
return;
proc B
If lookahead = ‘b’ then lookahead=nexttoken() else
{sw=1; error;}
return;
1. S → cAd
2. S → fBAc
3. A → aB
4. B → b

Recursive-descent:
‫مثال‬
:
1. S → cAd
2. A → aB
3. │a
4. B → b
4/6/2022

Buttom-up parser
4/6/2022
SLR
LALR
CLR
Simple
Left to right scanning input
Right most deviration in revese

Buttom_up parser
S →aABe
A → Abc
│b
B → d
By: Fereshteh Jadidi
6

‫باشد‬ ‫قواعد‬ ‫از‬ ‫يكي‬ ‫معادل‬ ‫كه‬ ‫اي‬ ‫رشته‬ ‫زير‬ ‫به‬
handle
‫گويند‬
‫مثال‬
:
a b b c d e
a A b c d e
a A d e
a A B e
S

Buttom_up parser:
)Shift_reduce Parser(
4/6/2022
stack
Input Buffer
‫برنامه‬
parser
Pars table
$
State diagram

•
Reduce
:
‫عنصر‬ ‫چند‬ ‫يا‬ ‫يك‬ ‫كه‬ ‫وقتي‬
stack
‫را‬
pop
‫آن‬ ‫در‬ ‫عنصر‬ ‫يك‬ ‫و‬ ‫كرده‬
push
‫كنيم‬ ‫مي‬
•
Shift
:
push
‫استك‬ ‫در‬ ‫را‬ ‫عنصر‬ ‫كردن‬
buttom_up
‫را‬
shift
‫گويند‬
4/6/2022
‫ا‬ ‫يعني‬ ‫هست‬ ‫ابتدا‬ ‫در‬ ‫نقطه‬
‫ز‬
‫است‬ ‫نخوانده‬ ‫چيزي‬ ‫ورودي‬
‫دهد‬ ‫مي‬ ‫نشان‬ ‫را‬ ‫پردازش‬ ،‫نقطه‬
‫يعن‬ ‫برسد‬ ‫انتها‬ ‫به‬ ‫نقطه‬ ‫اگر‬
‫ي‬
‫و‬ ‫است‬ ‫شده‬ ‫تمام‬ ‫پردازش‬
‫بررسي‬ ‫كامل‬ ‫طور‬ ‫به‬ ‫ورودي‬
‫است‬ ‫شده‬
.
LR(0) item:
A →xyz
A →.xyz
A →x.yz
A →xy.z
A →xyz.

Closure:
A →XYZ ‫امر‬‫ر‬‫گ‬
:
x →awz
x →FM
y →d
z →f
F →(E)
F →id
4/6/2022
Closure of grammar:
A →.XYZ
x →.awz
x →.FM
F →.(E)
F →.id

‫از‬ ‫قبل‬ ‫نقطه‬ ‫اگر‬
terminal
‫قبل‬ ‫اگر‬ ‫اما‬ ‫كرد‬ ‫شود‬ ‫نمي‬ ‫جايگذاري‬ ‫باشد‬
‫از‬
non_terminal
‫ممكن‬ ‫هاي‬ ‫جايگذاري‬ ‫دنبال‬ ‫گرديم‬ ‫مي‬ ‫قواعد‬ ‫در‬ ‫باشد‬

‫نوشتن‬
parser
‫روش‬ ‫به‬
LR
4/6/2022
.1
‫کشيدن‬
State diagram
.2
‫پارس‬ ‫جدول‬ ‫رسم‬
)
‫روي‬ ‫از‬ ‫جدول‬ ‫کردن‬ ‫پر‬
(SD
.3
‫جدول‬ ‫به‬ ‫توجه‬ ‫با‬ ‫پارسر‬ ‫برنامه‬ ‫نوشتن‬
0. E΄ → E
1. E →E+T
2. E →T
3. T →T*F
4. T →F
5. F → (E)
6. F → id

E΄ →.E
E →.E+T
E →.T
E →.E+T
E →.T
T →.T*F
T →.F
T →.T*F
T →.F
F →.(E)
F →.id
0
SLR STATE DIAGRAM:
0. E΄ → E
1. E →E+T
2. E →T
3. T →T*F
4. T →F
5. F → (E)
6. F → id

E΄ →.E
E →.E+T
E →.T
E →.E+T
E →.T
T →.T*F
T →.F
T →.T*F
T →.F
F →.(E)
F →.id
F →id.
E΄ →E.
E →E.+T
E →T.
T →T.*F
T →F.
F →(.E)
E →.E+T
E →.T
E →.E+T
E →.T
T →.T*F
T →.F
T →.T*F
T →.F
F →.(E)
F →.id
0
5
4
3
2
1
F
(
id
T
E




SLR STATE DIAGRAM:
12
0. E΄ → E
1. E →E+T
2. E →T
3. T →T*F
4. T →F
5. F → (E)
6. F → id
‫ناقص‬

E΄ →.E
E →.E+T
E →.T
E →.E+T
E →.T
T →.T*F
T →.F
T →.T*F
T →.F
F →.(E)
F →.id
F →id.
E΄ →E.
E →E.+T
E →T.
T →T.*F
T →F.
F →(.E)
E →.E+T
E →.T
E →.E+T
E →.T
T →.T*F
T →.F
T →.T*F
T →.F
F →.(E)
F →.id
E →E+.T
T →.T*F
T →.F
T →.T*F
T →.F
F →.(E)
F →.id
T →T*.F
F →.(E)
F →.id
F →(E.)
E →E.+T
F →(E).
T →T*F.
E →E+T.
T →T.*F
0
5
4
3
2
1
6 9
7
8 11
10
F
(
id
T
E
5
T
E
*
+
F
(
id
(
(
id
T +
id
F
)
2
5
4
5
4
3
6
4
3







7
*
SLR STATE DIAGRAM:
13
0. E΄ → E
1. E →E+T
2. E →T
3. T →T*F
4. T →F
5. F → (E)
6. F → id
F



Id + * ( ) $ E T F
0 s5 s4 1 2 3
1 s6 End
2 r2 s7 r2 r2
3 r4 r4 r4 r4
4 s5 s4 8 2 3
5 r6 r6 r6 r6
6 s5 s4 9 3
7 s5 s4 10
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
goto
action
‫جدول‬
SLR
:
14

i n p u t
s t a c k
( i d + i d ) * i d $
0
$
i d + i d ) * i d $
0 ( 4
$
+ i d ) * i d $
0 ( 4 i d 5
$
+ i d ) * i d $
0 ( 4 F 3
$
+ i d ) * i d $
0 ( 4 T 2
$
+ i d ) * i d $
0 ( 4 E 8
$
i d ) * i d $
0 ( 4 E 8 + 6
$
) * i d $
0 ( 4 E 8 + 6 i d 5
$
) * i d $
0 ( 4 E 8 + 6 F 3
$
) * i d $
0 ( 4 E 8 + 6 T 9
$
) * i d $
0 ( 4 E 8
$
* i d $
0 ( 4 E 8 ) 1 1
$
* i d $
0 F 3
$
* i d $
0 T 2
$
i d $
0 T 2 * 7
$
$
0 T 2 * 7 i d 5
$
$
0 T 2 * 7 F 1 0
$
$
0 T 2
$
$
0 E 1
$
SLR:
‫در‬ ‫هرگاه‬
stack
،
0E1
‫و‬ ‫بگيرد‬ ‫قرار‬
‫ورودي‬ ‫در‬
$
‫ن‬ ‫نتيجه‬ ‫به‬ ‫يعني‬ ‫باشد‬
‫هايي‬
‫ايم‬ ‫رسيده‬ ‫مطلوب‬
.
0. E΄ → E
1. E →E+T
2. E →T
3. T →T*F
4. T →F
5. F → (E)
6. F → id

4/6/2022 16
‫جديدی‬ ‫فرشته‬
-
‫شمال‬ ‫تهران‬ ‫آزاد‬ ‫دانشگاه‬ ‫علمی‬ ‫هيئت‬ ‫عضو‬
BUTTOM-UP PARSER: SLR
‫جدول‬
SLR
‫کنيد‬ ‫رسم‬ ‫زير‬ ‫گرامر‬
:
0
S’→ .S
S → .CC
C →.cC
C → .d



(0)S’ → S
(1)S → CC
(2)C → cC
(3)C → d

4/6/2022 17
-
‫جدول‬
SLR
:
0
6
5
4
3
2
1
d
C
C
d
c
C
d
c
S’→ .S
S → .CC
C →.cC
C → .d
S’→ S.
S → C.C
C → .cC
C→ .d
C → c.C
C →.cC
C → .d
S
S → CC.
3
4
C → cC.
c
3
4



(0)S’ → S
(1)S → CC
(2)C → cC
(3)C → d
C → d.
 



4/6/2022
18
-
‫جدول‬
SLR
:
0
6
5
4
3
2
1
d
C
C
d
c
C
d
c
S’→ .S
S → .CC
C →.cC
C → .d
S’→ S.
S → C.C
C → .cC
C→ .d
C → c.C
C →.cC
C → .d
S
S → CC.
3
4
C → cC.
c 3
4



(0)S’ → S
(1)S → CC
(2)C → cC
(3)C → d
C → d.
 


State c d $ S C
0
1
2
3
4
5
6


4/6/2022
19
-
‫جدول‬
SLR
:
1
(0)S’ → S
(1)S → CC
(2)C → cC
(3)C → d
State c d $ S C
0 s3 s4 1 2
1 acc
2 s3 s4 5
3 s3 s4 6
4 r3 r3 r3
5 r1
6 r2 r2 r2

4/6/2022 20
-
0. S΄ → S
1. S →CC
2. C →cC
3. C →d
BUTTOM-UP PARSER: CLR

S΄ →.S {$}
S →.CC {$}
C →.cC {c,d}
C →.d {c,d}
C →d.{c,d}
S΄ →S. {$}
S →C.C {$}
C→.cC {$}
C →.d {$}
C →c.C {c,d}
C →.cC {c,d}
C →.d {c,d} C→cC. {c,d}
C →c.C {$}
C →.cC {$}
C →.d {$}
C →d. {$}
S →CC.{$}
C →cC.{$}
0
4
3
2
1 C
6 9
c
8
c
d
C
S
7
5
d
c
c
d
d
C
3
7





6
C
CLR STATE DIAGRAM
4

By: Fereshteh Jadidi
0. S΄ → S
1. S →CC
2. C →cC
3. C →d

c d $ S C
0 s3 s4 1 2
1 End
2 s6 s7 5
3 s3 s4 r4 8
4 r3 r3
5 r1
6 s6 s7 9
7 r3
8 r2 r2
9 r1
CLR PARS TABLE:

action
input
s t a c k
s 4
d c c d $
0
$
r 3
c c d $
d 4 0 ( 4
$
s 6
c c d $
$ 0 C 2
s 6
c d $
$ 0 C 2 c 6
s 7
d $
$ 0 C 2 c 6 c 6
r 3
$
$ 0 C 2 c 6 c 6 d 7
r 2
$
$ 0 C 2 c 6 c 6 C 9
r 2
$
$ 0 C 2 c 6 C 9
r 1
$
$ 0 C 2 C 5
A C C
$
$ 0 S 1
4/6/2022
‫در‬ ‫هرگاه‬
stack
،
0S1
‫در‬ ‫و‬ ‫بگيرد‬ ‫قرار‬
‫ورودي‬
$
‫ب‬ ‫يعني‬ ‫باشد‬
‫ه‬
‫مطلوب‬ ‫نهايي‬ ‫نتيجه‬
‫ايم‬ ‫رسيده‬
.
‫ک‬ ‫پارس‬ ‫قبل‬ ‫صفحه‬ ‫پارس‬ ‫جدول‬ ‫توسط‬ ‫را‬ ‫زیر‬ ‫رشته‬
‫نید‬
.

LALR PARSER:
•
‫بروش‬ ‫پارسی‬ ‫جدول‬ ‫قبل‬ ‫مثال‬ ‫گرامر‬ ‫برای‬ ‫ميخواهيم‬
LALR
‫کنيم‬ ‫رسم‬
•
‫پارس‬ ‫جدول‬ ‫بايد‬ ‫ابتدا‬
CLR
‫کنيم‬ ‫رسم‬ ‫آنرا‬
.
•
‫سپس‬
kernel
‫بيابيم‬ ‫را‬ ‫مساوی‬ ‫های‬
:
36 47 89
•
‫پارس‬ ‫جدول‬ ‫همان‬ ‫در‬ ‫سپس‬
CLR
،‫شده‬ ‫رسم‬
state
‫های‬
‫با‬
kernel
‫ميکنيم‬ ‫ادغام‬ ‫هم‬ ‫در‬ ‫را‬ ‫مساوی‬
)
‫معموال‬
‫ميکن‬ ‫ادغام‬ ‫باالتر‬ ‫رديفهای‬ ‫در‬ ‫را‬ ‫پايينتر‬ ‫رديفهای‬
‫يم‬
(
•
‫بروش‬ ‫پارس‬ ‫جدول‬ ‫حاصل‬ ‫جدول‬
LALR
‫دارد‬ ‫نام‬
.
4/6/2022 24
-

�ݺ�ߣ

Bottom up parser

More Related Content

Bottom up parser