Bài giảng Chương trình dịch (tt)

CH NG TRÌNH D CH ƯƠ Ị

Gi

i thi u

ớ

ệ

M c tiêu giáo trình

ụ

1. Cung c p nh ng ki n th c c b n ứ ơ ả

ế ữ ng trình d ch ấ v ch ề ươ ị

ng pháp phân

tích t 2. Cung c p các ph ấ ươ v ng, phân tích cú pháp. ừ ự

3. C s cho vi c tìm hi u các ngôn ể ệ

ng l p trình. ơ ở ữ ậ

4. Rèn luy n k năng l p trình cho ậ ỹ

ệ sinh viên

Gi

i thi u

ớ

ệ

N i dung giáo trình

ộ

CH

NG TRÌNH D CH

ƯƠ

NG 1. NH P MÔN CH Ậ

ƯƠ

Ị

CH

NG 2. PHÂN TÍCH T V NG

ƯƠ

Ừ Ự

CH

NG 3. CÁC V N Đ C B N V PHÂN TÍCH CÚ PHÁP

ƯƠ

Ề Ơ Ả

Ấ

Ề

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ PHÁP

ƯƠ

CH

NG TRÌNH D CH

ƯƠ

NG 1. NH P MÔN CH Ậ

ƯƠ

Ị

1. Các khái ni m c b n

ơ ả

ệ

2. Đ c tr ng c a ngôn ng l p trình (NNLT) b c cao

ữ ậ

ủ

ư

ặ

ậ

3. Các qui t c t

v ng và cú pháp

ắ ừ ự

4. Các ch c năng c a m t trình biên d ch ủ

ứ

ộ

ị

4 ng 2 ươ

CH

NG TRÌNH D CH

ƯƠ

NG 1. NH P MÔN CH Ậ

ƯƠ

Ị

1. Các khái ni m c b n ơ ả ệ

1.1. S phát tri n c a ngôn ng l p trình ể ủ ữ ậ ự

1.2. Khái ni m ch ng trình d ch ệ ươ ị

1.3. Phân lo i ch ng trình d ch ạ ươ ị

5 ng 2 ươ

1.4. Các ng d ng khác c a k thu t d ch ủ ỹ ậ ị ụ ứ

CH

NG TRÌNH D CH

ƯƠ

NG 1. NH P MÔN CH Ậ

ƯƠ

Ị

1. Các khái ni m c b n ơ ả ệ

1.1. S phát tri n c a ngôn ng l p trình ể ủ ữ ậ ự

ậ

ợ

H p ng ữ (Assembly)

NNLT b c cao (Higher _level language)

NN máy (machine language)

6 ng 2 ươ

CH

NG TRÌNH D CH

ƯƠ

NG 1. NH P MÔN CH Ậ

ƯƠ

Ị

1. Các khái ni m c b n ơ ả ệ

1.2. Khái ni m ch ng trình d ch ệ ươ ị

ươ

Ch ị ươ ồ

ồ ộ

ng (CT đích) trên m t NN ươ

7 ng 2 ươ

ng trình d ch là ch ng trình dùng đ ị ươ ể ng trình (CT ngu n) vi d ch m t ch t trên ế ộ ng NNLT nào đó (NN ngu n) sang m t ch ươ trình t ng đ ộ ươ khác (NN đích)

CH

NG TRÌNH D CH

ƯƠ

NG 1. NH P MÔN CH Ậ

ƯƠ

Ị

1. Các khái ni m c b n ơ ả ệ

1.3. Phân lo i ch ng trình d ch ạ ươ ị

 Trình biên d chị

D li u ữ ệ

K t quế

ả

CT đích

Máy tính th c thi ự

Trình biên d chị

CT ngu nồ

Th i gian ờ th c thi ự

Th i gian ờ d chị

CH

NG TRÌNH D CH

ƯƠ

NG 1. NH P MÔN CH Ậ

ƯƠ

Ị

1. Các khái ni m c b n ơ ả ệ

1.3. Phân lo i ch ng trình d ch ạ ươ ị

 Trình thông d chị

D li u ữ ệ

K t quế

ả

Trình thông d chị

CT ngu nồ

CH

NG TRÌNH D CH

ƯƠ

NG 1. NH P MÔN CH Ậ

ƯƠ

Ị

1. Các khái ni m c b n ơ ả ệ

1.4. Các ng d ng khác c a k thu t d ch ủ ỹ ậ ị ụ ứ

- Trong các h th ng: ph n giao ti p gi a ệ ố ữ ầ

ng i và máy thông qua các câu l nh. ườ ế ệ

- H th ng x lý NN t ự nhiên: d ch thu t, ị ậ

ng 2

10 ươ

ử t văn b n. tóm t ệ ố ắ ả

CH

NG TRÌNH D CH

ƯƠ

NG 1. NH P MÔN CH Ậ

ƯƠ

Ị

2. Đ c tr ng c a NNLT b c cao ủ ư ặ ậ

- Tính t nhiên ự

- Tính thích nghi

- Tính hi u quệ ả

- Tính đa d ngạ

CH

NG TRÌNH D CH

ƯƠ

NG 1. NH P MÔN CH Ậ

ƯƠ

Ị

3. Các qui t c t v ng và cú pháp ắ ừ ự

3.1. B n ch cái ữ ả

t

ệ ượ

c phép s d ng đ vi ử ụ

ể ế

- G m nh ng ký hi u đ ữ ng trình

ồ ch ươ

ng, ý nghĩa s d ng c a các ký t

trong b n

ử ụ

ủ

ự

ả

ch cái c a các NN là khác nhau.

- S l ố ượ ữ

ủ

- Nhìn chung b n ch cái c a các NNLT: ữ

ủ

ả

Z, az

+ 52 ch cái: A ữ

+ 10 ch s : 0

ữ ố 9

+ Các ký hi u khác:*, /, +, -, …

ệ

CH

NG TRÌNH D CH

ƯƠ

NG 1. NH P MÔN CH Ậ

ƯƠ

Ị

3. Các qui t c t v ng và cú pháp ắ ừ ự

- T t

3.2. T t (Token) ừ ố

là đ n v nh nh t có nghĩa

ừ ố

ơ ị ỏ ấ

- T t

c xây d ng t

b n ch cái

đ ừ ố ượ

ự

ừ ả

ữ

- Ví d : h ng, bi n, t

khoá, các phép toán,…

ụ ằ

ế ừ

CH

NG TRÌNH D CH

ƯƠ

NG 1. NH P MÔN CH Ậ

ƯƠ

Ị

3. Các qui t c t v ng và cú pháp ắ ừ ự

- Ph m trù cú pháp là m t dãy t

3.3. Ph m trù cú pháp ạ

k t h p

t

ạ

ừ ố ế ợ

ộ theo m t qui lu t nào đó

ộ

ậ

ng

- Các cách bi u di n cú pháp thông th ễ

ể

ườ

+ BNF(Backus Naus Form):

::=:=
ể

ế

ệ

th c>ứ

14

CH

NG TRÌNH D CH

ƯƠ

NG 1. NH P MÔN CH Ậ

ƯƠ

Ị

3. Các qui t c t v ng và cú pháp ắ ừ ự

3.3. Ph m trù cú pháp ạ

+ Bi u đ cú pháp:

ể ồ

Ch

ng trình

ươ

Program Danh bi uể  Kh iố

Kh i ố - var…

- procedure  Danh bi u ể Kh iố

- begin l nh ệ  end .

- M c tiêu c a ph m trù cú pháp là vi c đ nh ệ

ệ ị ng trình đ n ế 15

ươ

ụ nghĩa đ m c đ t

ạ ủ c khái ni m ch có

ượ ứ ộ ự

CH

NG TRÌNH D CH

ƯƠ

NG 1. NH P MÔN CH Ậ

ƯƠ

Ị

3. Các qui t c t v ng và cú pháp ắ ừ ự

3.4. Các qui t c t v ng thông d ng ắ ừ ự ụ

- Cách s d ng kho ng tr ng(d u tr ng), ả ử ụ ố ắ

ấ d u tab(‘\t’), d u sang dòng(‘\n’) ấ ấ

- Đ i v i liên k t t ế ự ố do, có th s d ng ả ể ử ụ ộ ả

16

ố ớ nhi u kho ng tr ng thay vì m t kho ng ề tr ng. ố

CH

NG TRÌNH D CH

ƯƠ

NG 1. NH P MÔN CH Ậ

ƯƠ

Ị

3. Các qui t c t v ng và cú pháp ắ ừ ự

3.4. Các qui t c t v ng thông d ng ắ ừ ự ụ

- M t kho ng tr ng là b t bu c gi a các t ữ ộ ố ắ ả ừ

khoá và tên,… ộ : t t ố ừ

Ví d : program tenct; ụ

- Kho ng tr ng không b t bu c: s và các ố ố ộ ả ắ

phép toán, tên bi n và các phép toán ế

17

Ví d : x:=x+33; ụ

- Cách s d ng chú thích và xâu ký t ử ụ ự

CH

NG TRÌNH D CH

ƯƠ

NG 1. NH P MÔN CH Ậ

ƯƠ

Ị

4. Các ch c năng c a m t ch ng trình biên ủ ứ ộ ươ

d chị

- Phân tích t v ng ừ ự

- Phân tích cú pháp

- Phân tích ng nghĩa ữ

- X lý l ử i ỗ

- Sinh mã trung gian

18

- T i u mã trung gian ố ư

- Sinh mã đ i t ng ố ượ

CH

NG TRÌNH D CH

ƯƠ

NG 1. NH P MÔN CH Ậ

ƯƠ

Ị

4. Các ch c năng c a m t ch ng trình biên ủ ứ ộ ươ

d chị

4.1. Phân tích t v ng ừ ự

- CT ngu n là m t dãy các ký t ồ ộ . ự

ồ

- Phân tích t thành các t (Token). v ng là phân tích CT ngu n ừ ự t ừ ố

- Các Token này s là d li u đ u vào c a ữ ệ ủ ầ

19

ẽ phân tích cú pháp.

CH

NG TRÌNH D CH

ƯƠ

NG 1. NH P MÔN CH Ậ

ƯƠ

Ị

4. Các ch c năng c a m t ch ng trình biên ủ ứ ộ ươ

d chị

4.2. Phân tích cú pháp

- Đ u vào s là dãy các Token n i nhau b ng ố ằ

ẽ m t qui t c nào đó. ắ ầ ộ

20

cú pháp c a ngôn ng không - Phân tích xem các Token có tuân theo qui t c ắ ữ ủ

CH

NG TRÌNH D CH

ƯƠ

NG 1. NH P MÔN CH Ậ

ƯƠ

Ị

4. Các ch c năng c a m t ch ng trình biên ủ ứ ộ ươ

d chị

4.3. Phân tích ng nghĩa ữ

- Ki m tra tính h p l c a các phép toán và các ợ ệ ủ ể

phép x lýử

- Ví d :ụ

c khi s d ng • Bi n ph i khai báo tr ả ướ ử ụ

ế (Pascal)

• Ki m tra tính t ng thích ki u d li u c a ể ữ ệ ủ 21

ươ bi n và bi u th c ứ ể ế ể

CH

NG TRÌNH D CH

ƯƠ

NG 1. NH P MÔN CH Ậ

ƯƠ

Ị

4. Các ch c năng c a m t ch ng trình biên ủ ứ ộ ươ

d chị

4.4. X lý l ử i ỗ

- CT ngu n v n có th x y ra l i. ồ ẫ ể ả ỗ

i s thông báo l i cho NSD - Ph n x lý l ầ ử ỗ ẽ ỗ

22

- L i ph n nào báo ph n đó. ỗ ở ầ ở ầ

CH

NG TRÌNH D CH

ƯƠ

NG 1. NH P MÔN CH Ậ

ƯƠ

Ị

4. Các ch c năng c a m t ch ng trình biên ủ ứ ộ ươ

d chị

4.4. X lý l ử i ỗ

- Có các lo i l i: ạ ỗ

v ng (trong Pascal s d ng bi n mà ử ụ ế

ch a khai báo) • L i t ỗ ừ ự ư

• L i cú pháp ((a+5; l i thi u d u ‘)’ ) ỗ ỗ ế ấ

23

• L i ng nghĩa (int x=3.5; ) ữ ỗ

• L i th c hi n (phép chia 0) ệ ỗ ự

CH

NG TRÌNH D CH

ƯƠ

NG 1. NH P MÔN CH Ậ

ƯƠ

Ị

4. Các ch c năng c a m t ch ng trình biên ủ ứ ộ ươ

d chị

4.5. sinh mã trung gian

- Sau giai đo n phân tích ng nghĩa ữ ạ

ủ

ngu n có 2 đ c đi m: - Mã trung gian là m t d ng trung gian c a CT ộ ạ ể ồ ặ

• D đ c sinh ra ễ ượ

24

• D d ch sang ngôn ng đích ễ ị ữ

CH

NG TRÌNH D CH

ƯƠ

NG 1. NH P MÔN CH Ậ

ƯƠ

Ị

4. Các ch c năng c a m t ch ng trình biên ủ ứ ộ ươ

d chị

4.6. T i u mã trung gian ố ư

- B b t các l nh th a. ỏ ớ ừ ệ

ng thì th i gian th c thi mã đ i t i mã trung gian đ khi sinh mã đ i ố ể ng s ẽ ờ ố ượ ự

25

- C i ti n l ả ế ạ t ượ ng n h n ắ ơ

CH

NG TRÌNH D CH

ƯƠ

NG 1. NH P MÔN CH Ậ

ƯƠ

Ị

4. Các ch c năng c a m t ch ng trình biên ủ ứ ộ ươ

d chị

4.7. Sinh mã đ i t ng ố ượ

- Giai đo n cu i c a trình biên d ch. ố ủ ạ ị

ố ượ ữ ể

m t ngôn ng khác ngôn ng ngu n. - Mã đ i t ộ ng có th là mã máy, h p ng hay ữ ữ ợ ồ

 Các pha (giai đo n) có th th c hi n song ể ự ệ ạ

hành

 M t vài pha có th ghép l i thành l ộ ể ạ ượ

t 26 (chuy n)ế

 M t l t s đ c toàn b CT ngu n hay m t ộ ượ ẽ ọ ộ ồ ộ

d ng trung gian c a CT ngu n, sau đó ghi k t ủ ồ ế ạ

qu đ l t sau đ c và x lý ti p. ả ể ượ ử ọ ế

CH

NG TRÌNH D CH

ƯƠ

NG 1. NH P MÔN CH Ậ

ƯƠ

Ị

a:=(b+c)6

B sinh mã trung gian

ộ

4. Các ch c năng c a m t ch ng trình biên ủ ứ ộ ươ

B PTTV

ộ

id1:=(id2+id3)Num4

Temp1:=intoreal(6)

d chị

Temp2:=id2+id3

B PTCP

ộ

Temp3:=temp2temp1

n1

Id1:=temp3

:=

id1

n2

B t

i u sinh mã trung gian

ộ ố ư

n3

*

Num4

Temp1:=id2+id3

+

id2

id3

Id1:=temp16.0

B PTNN

ộ

B sinh mã đ i t

ng

ố ượ

ộ

n1

MovF

id2, R1

:=

id1

n2

MovF

id3, R2

n3

Intoreal(6)

Add

R2, R1

27

Mult

#6.0, R1

+

id2

id3

MovF

R1, id1

Ví d : ụ

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

- M c đích ụ

- N i dung ộ

- Otomat h u h n đ n đ nh ữ ạ ơ ị

- B phân tích t v ng ộ ừ ự

28

- B ng danh bi u ể ả

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

1. M c đích ụ

- Chia c t xâu vào (CT ngu n) thành dãy các ồ ắ

.ừ ố t t

- Hai cách cài đ tặ

• S d ng m t l ử ụ ộ ượ ệ ừ

t cho vi c phân tích t v ng ự  dãy các token phân tích cú pháp.

29

• Phân tích t v ng dùng chung m t l ừ ự

ộ ầ ỉ ti p đ n. t t ộ ượ v i phân tích cú pháp. M t l n ch phát ớ hi n 1 token g i là t ệ ừ ố ế ọ ế

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

2. N i dung ộ

- Đ c xâu vào t ng ký t ọ i ạ

ự ộ  gom l ự ặ không th ể

m t ừ thành token đ n khi g p ký t ế k t h p thành token. ế ợ

- Luôn luôn đ c tr ọ ướ c m t ký t ộ . ự

- Lo i b ký t ạ ỏ ự ố tr ng và xác đ nh chú thích. ị

ữ ữ

- Chuy n nh ng thông tin c a nh ng t ệ ủ ạ ừ ể ả

30

t ừ ố (văn b n, mã phân lo i) v a phát hi n cho b phân tích cú pháp. ộ

- Phát hi n l i. ệ ỗ

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

2. N i dung ộ

- S giao ti p gi a b phân tích t v ng và ừ ự

ữ ộ ế b phân tích cú pháp ự ộ

G i token

ử

Yêu c u token ầ

CT ngu nồ

B ộ phân tích cú pháp

B ộ phân tích v ng t ừ ự

B ng ả danh bi uể

31

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

3. Otomat h u h n đ n đ nh ữ ạ ơ ị

3.1. Đ nh nghĩa: M(Σ, Q, δ, q0, F)

ị

Σ: b ch vào ộ ữ

ậ ữ ạ

ạ

Q: t p h u h n các tr ng thái q0 ˛

Q: tr ng thái đ u

ầ

ạ

F ˝

Q: t p các tr ng thái k t thúc

ế

ậ

ạ

δ: hàm chuy n tr ng thái có d ng δ(q,a)=p

ạ

˛

ể V i q,p

ạ Q, a ˛

Σ

ớ

tr ng thái q, đ c a, chuy n

ở ạ

ọ

ể

32

 δ(q,a)=p: nghĩa là sang tr ng thái p ạ

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

3. Otomat h u h n đ n đ nh ữ ạ ơ ị

3.2. Bi u di n các hàm chuy n tr ng thái ể ễ ể ạ

 Dùng b ng: s d ng ma tr n δ có: ử ụ ả ậ

- Ch s hàng: tr ng thái ỉ ố ạ

- Ch s c t: ký hi u vào ỉ ố ộ ệ

- Giá tr t i hàng q, c t a là tr ng thái ị ạ ộ ạ

33

p, sao cho δ(q,a)=p

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

3. Otomat h u h n đ n đ nh ữ ạ ơ ị

3.2. Bi u di n các hàm chuy n tr ng thái ể ễ ể ạ

 Dùng b ng: ả

ụ ể ủ ộ

Ví d : có hàm chuy n c a m t Otomat δ(1,a)=2, δ(2,b)=2, δ(2,c)=2 nh sau: ư

a

δ

b

c

2

1

2

2

2

34

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

3. Otomat h u h n đ n đ nh ữ ạ ơ ị

3.2. Bi u di n các hàm chuy n tr ng thái ể ể ễ ạ

 Hình v : ẽ

- m i tr ng thái q ˛ Q đ c đ t trong các vòng ỗ ạ ượ ặ

tròn.

- Tr ng thái b t đ u q0 có thêm d u ‘>’ ắ ầ ấ ở

ạ đ u.ầ

- Tr ng thái k t thúc q ˛ F đ c đ t trong ạ ượ ặ

35

ế vòng tròn kép.

- Các cung n i t tr ng thái q sang tr ng thái ố ừ ạ ạ

p có mang các nhãn a˛ Σ, có nghĩa δ(q,a)=p

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

3. Otomat h u h n đ n đ nh ữ ạ ơ ị

3.2. Bi u di n các hàm chuy n tr ng thái ể ễ ể ạ

 Hình v : ẽ

ụ ể ủ ộ

Ví d : có hàm chuy n c a m t Otomat δ(1,a)=2, δ(2,b)=2, δ(2,c)=2 nh sau: ư

b

a

c

2

1

36

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

3. Otomat h u h n đ n đ nh ữ ạ ơ ị

3.2. Bi u di n các hàm chuy n tr ng thái ể ể ễ ạ

 Nh n xét: ậ

ễ ể ạ ằ

ẽ

ị

- Bi u di n hàm chuy n tr ng thái b ng ể hình v có u đi m h n. Trong hình v ta ẽ ơ ể ư xác đ nh đ y đ t t c các thành ph n c a ầ ủ ầ ủ ấ ả Otomat.

ả ễ ị

ằ ậ

37

ộ ữ c tr ng thái ạ

- Bi u di n b ng b ng xác đ nh hàm chuy n ể tr ng thái, t p các tr ng thái, b ch vào ạ t đ nh ng không phân bi ệ ượ b t đ u và tr ng thái k t thúc. ế ể ạ ư ắ ầ ạ

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

3. Otomat h u h n đ n đ nh ữ ạ ơ ị

3.3. Ho t đ ng c a Otomat ạ ộ ủ

trái sang ệ ủ

- Đ c các ký hi u c a xâu vào t ừ tr ng thái q0. ph i, b t đ u t ọ ả ắ ầ ừ ạ

ộ ể

ệ ể ọ

38

c đ c m t ký hi u thì chuy n sang tr ng thái theo δ. Có th đ c xong hay không đ c xong xâu vào. - M i b ỗ ướ ọ ạ ọ

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

3. Otomat h u h n đ n đ nh ữ ạ ơ ị

3.3. Ho t đ ng c a Otomat ạ ộ ủ

˛ F ọ ế

thì xâu vào đ - Đ c xong xâu vào đ n m t tr ng thái p ộ ạ c đoán nh n (xâu đúng). ậ ượ

ọ ạ

- Đ c xong xâu vào mà r i vào tr ng thái c đoán nh n. ơ pˇ F thì xâu vào không đ ượ ậ

- Không đ c xong xâu vào (do δ r i vào đi m ơ ọ ể

c ị ượ

39

không xác đ nh) thì xâu vào không đ đoán nh n.ậ

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

3. Otomat h u h n đ n đ nh ữ ạ ơ ị

3.4. Ví d : Xác đ nh Otomat đoán nh n s nh ậ ố ị ụ ị

phân. M(Σ, Q, δ, q0, F)

Σ: {0, 1, tr ng}ắ

Q: {0, 1, 2}

q0: 0

F : {2}

ắ δ(1,0)=1, δ(1,1)=1, δ(1,tr ng)=2 40 δ: δ(0,tr ng)=0, δ(0,0)=1, δ(0,1)=1, ắ

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

3. Otomat h u h n đ n đ nh ữ ạ ơ ị

3.4. Ví d : Xác đ nh Otomat đoán nh n s nh ậ ố ị ụ ị

phân

0

tr ngắ

1

*

0|1

tr ngắ

1

2

0

41

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

4.L p b phân tích t v ng ậ ộ ừ ự

c c a Otomat thông ướ ủ

i có thêm: ng l Ngoài các hình qui th ạ ườ

*

q

Tr ng thái k t thúc và tr lui ký t

ế v a đ c ự ừ ọ

ạ ả

42

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

4. L p b phân tích t v ng ậ ộ ừ ự

4.1. Ph ng pháp mô ph ng ươ ỏ

ỗ ạ ươ ứ ng ng v i m t đo n ớ ộ ạ

- M i tr ng thái: t ng trình ch ươ

ố ế ạ ạ

- N i ti p các tr ng thái: n i ti p 2 đo n ng ng ch ng trình t ố ế ươ ươ ứ

43

- L nh r nhánh ẽ ệ

L nh l p ệ ặ -

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

=

=

>

+

ss l n h n băng

công băng

ớ ơ

1 7

0

1

2

1 5

1 6

>

+

dich phai

tăng 1

4.L p b phân tích t v ng ậ ộ ừ ự ̀ ̣ ̀

3

1 8

*

*

khać

khać

công

̣ ̉

ss l n h n ớ ơ

1 9

4

=

-

=

<

tr băng

ừ

̣

2 0

2 1

ss nho h n băng ̉ ơ

5

6

-

<

giam 1

̀ ̀

2 2

dich trai

7

*

khać

*

trừ

khać

2 3

ss nho h n ̉ ơ

8

=

*

25

nhân băng̀

24

=

!

ss khać

9

10

*

khać

26

*

nhân

khać

11

phu đinh

̉ ̣ ́

=

=

=

/

28

chia băng̀

12

13

27

Ss b ng

ss không băng̀ ằ

*

khać

khać

29

* 44

chia

14

gań

%

30

chia lây d́ ư

̉ ̣

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

4.L p b phân tích t v ng ậ ộ ừ ự

ng pháp mô ph ng ươ ỏ

4.1. Ph const int ERROR_STATE=100;

typedef int state;// kieu cac trang thai

typedef unsigned char attri;// kieu cua thuoc tinh

typedef unsigned char token; //kieu cua tu to

unsigned char x;//xau vao x

unsigned int i=0;// vi tri cua ky tu doc trong xau x

unsigned char readchar(unsigned char x, unsigned int i){

//tra ve ky tu tiep theo

if(i
45

else return ('\0'); }

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

4.L p b phân tích t v ng ậ ộ ừ ự

ng pháp mô ph ng ỏ 4.1. Ph ươ attri attribute(state s) {

// tra ve thuoc tinh tuong ung voi trang thai ket thuc

char ch;

switch(s){

case 2: strcpy(ch,"so sanh lon hon bang");break;

case 3: strcpy(ch,"dich phai"); break;

case 4: strcpy(ch,"so sanh lon hon"); break;

case 6: strcpy(ch,"so sanh nho hon

bang");break;

46

case 7: strcpy(ch,"dich trai"); break;

case 8: strcpy(ch,"so sanh nho hon"); break;

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

4.L p b phân tích t v ng ậ ộ ừ ự

4.1. Ph ng pháp mô ph ng ươ ỏ

case 10: strcpy(ch,"so sanh khong bang"); break;

case 11: strcpy(ch,"phu dinh"); break;

case 13: strcpy(ch,"so sanh bang"); break;

case 14: strcpy(ch,"gan"); break;

case 17: strcpy(ch,"cong bang"); break;

case 18: strcpy(ch,"tang 1"); break;

case 19: strcpy(ch,"cong"); break;

case 21: strcpy(ch,"tru bang"); break;

case 22: strcpy(ch,"giam 1"); break;

47

case 23: strcpy(ch,"tru"); break;

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

4.L p b phân tích t v ng ậ ộ ừ ự

4.1. Ph ng pháp mô ph ng ươ

ỏ case 25: strcpy(ch,"nhan bang"); break;

case 26: strcpy(ch,"nhan"); break;

case 28: strcpy(ch,"chia bang"); break;

case 29: strcpy(ch,"chia"); break;

case 30: strcpy(ch,"chia lay du"); break;

default: strcpy(ch,"token ko duoc doan nhan(tt

ko dung \0");

}

return ch;

48

}

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

4.L p b phân tích t v ng ậ ộ ừ ự

ng pháp mô ph ng ươ ỏ

4.1. Ph int nostar_end_state(state s){

//kiem tra trang thai s co phai la trang thai ket thuc khong sao ?

switch(s){

case 2:

case 3:

case 6:

case 7:

case 10:

case 13:

49

case 17:

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

4.L p b phân tích t v ng ậ ộ ừ ự

4.1. Ph ng pháp mô ph ng ươ ỏ

case 18:

case 21:

case 22:

case 25:

case 28:

case 30: return 1;

default: return 0;

}

50

}

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

4.L p b phân tích t v ng ậ ộ ừ ự

4.1. Ph ng pháp mô ph ng ươ ỏ

int star_end_state(state s){

//kiem tra trang thai s co phai la trang thai ket thuc sao ?

switch(s){

case 4:

case 8:

case 11:

case 14:

case 19:

51

case 23:

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

4.L p b phân tích t v ng ậ ộ ừ ự

4.1. Ph ng pháp mô ph ng ươ ỏ

case 26:

case 29: return 1;

default: return 0;

}

}

52

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

4.L p b phân tích t v ng ậ ộ ừ ự

4.1. Ph ng pháp mô ph ng ươ ỏ

state start_state_otherbrand(state s){

state start;

switch(s){

case 0: start=15; break;

case 15: start=ERROR_STATE;

}

return start;

}

53

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

4.L p b phân tích t v ng ậ ộ ừ ự

4.1. Ph ng pháp mô ph ng ươ ỏ

int start_state(state s){

if ((s==0) || (s==15)) return 1; return 0;

}

void catchar_in_token (unsigned char c, token tk){

// ghep them ky tu c vao cho tu to tk

(tk+strlen(tk))=c;

(tk+strlen(tk)+1)='\0';

}

54

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

4.L p b phân tích t v ng ậ ộ ừ ự

ng pháp mô ph ng ươ ỏ

4.1. Ph token search_token (unsigned int i, attri tt){

// tra ve tri tu vung cua tu to bdau tu vi tri i, thuoc tinh tra ve cho tt

token tk;

state s=0;

int stop=0;

unsigned char c;

do {

c=readchar(x,i);

i=i+1;

55

} while ((c==' ')&&(i
ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

4.L p b phân tích t v ng ậ ộ ừ ự

4.1. Ph ng pháp mô ph ng ươ ỏ

while (i
switch(s){

case 0: if (c=='>') s=1;

else if (c=='<') s=5; else if (c=='!') s=9;

else if (c=='=') s=12;

else s=start_state_otherbrand(s);

break;

56

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

4.L p b phân tích t v ng ậ ộ ừ ự

4.1. Ph ng pháp mô ph ng ươ ỏ

case 1: if (c=='=') s=2;

else if (c=='>') s=3;

else s=4;

break;

case 5: if (c=='=') s=6;

else if (c=='<') s=7;

else s=8;

break;

57

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

4.L p b phân tích t v ng ậ ộ ừ ự

4.1. Ph ng pháp mô ph ng ươ ỏ

case 9: if (c=='=') s=10;

else s=11;

break;

case 12: if (c=='=') s=13;

else s=14;

break;

58

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

4.L p b phân tích t v ng ậ ộ ừ ự

4.1. Ph ng pháp mô ph ng ươ ỏ

case 15: if (c=='+') s=16;

else if (c=='-') s=20;

else if (c=='') s=24;

else if (c=='/') s=27;

else if (c=='%') s=30;

else s=start_state_otherbrand(s);

break;

59

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

4.L p b phân tích t v ng ậ ộ ừ ự

4.1. Ph ng pháp mô ph ng ươ ỏ

case 16: if (c=='=') s=17;

else if (c=='+') s=18;

else s=19;

break;

case 20: if (c=='=') s=21;

else if (c=='-') s=22;

else s=23;

break;

60

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

4.L p b phân tích t v ng ậ ộ ừ ự

4.1. Ph ng pháp mô ph ng ươ ỏ

case 24: if (c=='=') s=25;

else s=26;

break;

case 27: if (c=='=') s=28;

else s=29;

break;

default: stop=1;

}

61

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

4.L p b phân tích t v ng ậ ộ ừ ự

4.1. Ph ng pháp mô ph ng ươ ỏ

if (s==ERROR_STATE){

stop=1;

printf("loi tai ky tu thu %i",i);

tk='\0'; }

else if (start_state(s));

else if (nostar_end_state(s)) {

catchar_in_token(c,tk);

i=i+1; stop=1;

62

strcpy(tt,attribute(s));}

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

4.L p b phân tích t v ng ậ ộ ừ ự

4.1. Ph ng pháp mô ph ng ươ ỏ

else if (star_end_state(s)){

strcpy(tt,attribute(s)); stop=1;}

else {

catchar_in_token(c,tk);

i=i+1;

c=readchar(x,i);}

}

return tk;

63

}

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

4.L p b phân tích t v ng ậ ộ ừ ự

4.1. Ph ươ ỏ

ng pháp mô ph ng void save_token_and_attribute(token tk,attri a){

//luu tru tk,a vao danh sach

}

void lexical_analysis(){

token tk; attri a;

do {

tk=search_token(&i,a);

save_token_and_attribute(tk,a);

}while ((tk!='\0')&&(i
64

}

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

4.L p b phân tích t v ng ậ ộ ừ ự

ng pháp mô ph ng ươ ỏ

4.1. Ph main(){

//nhap xau vao x

i=0;

lexical_analysis();

//in danh sach tu to va thuoc tinh

}

65

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

4. L p b phân tích t v ng ậ ộ ừ ự

- Otomat phai chung môt trang thai băt đâu

4.2. Ph ng pháp đi u khi n b ng b ng ươ ề ể ả ằ

- Tao bang table biêu diên ham chuyên trang thai

̉ ̣ ̣ ́ ́ ̀

• Chi sô hang: trang thai q

˛ Q

̣ ̉ ̉ ̃ ̀ ̉ ̣ ́

̉ ́ ̀ ̣ ́

• Chi sô côt: ky hiêu vao a

d (q,a)=p

• Table[q][a]=p v i p ớ

˛ Q va ̀

66

˛ (cid:229) ̉ ́ ̣ ́ ̣ ̀

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

=

=

>

+

ss l n h n băng

công băng

ớ ơ

1 7

0

1

2

1 6

0

>

+

dich phai

tăng 1

4.L p b phân tích t v ng ậ ộ ừ ự ̀ ̣ ̀

3

1 8

*

*

khać

khać

công

̣ ̉

ss l n h n ớ ơ

1 9

4

=

-

=

<

tr băng

ừ

̣

2 0

2 1

ss nho h n băng ̉ ơ

5

6

-

<

giam 1

̀ ̀

2 2

dich trai

7

*

khać

*

trừ

khać

2 3

ss nho h n ̉ ơ

8

=

*

25

nhân băng̀

24

=

!

ss khać

9

10

*

khać

26

*

nhân

khać

11

phu đinh

̉ ̣ ́

=

=

=

/

28

chia băng̀

ss không băng̀

12

13

27

*

khać

khać

29

* 67

chia

14

gań

%

30

chia lây d́ ư

̉ ̣

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

4. L p b phân tích t v ng ậ ộ ừ ự

4.1. Ph ng pháp đi u khi n b ng b ng ươ ề ể ằ ả

...

>

=

<

!

1

12

5

9

0

3

2

4

4

1

100

100

100

100

2

...

Trang thai 100:Ko co ham chuyên trang thai

68

̣ ́ ́ ̀ ̉ ̣ ́

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

v ng ừ ự

4. L p b phân tích t ậ ộ int table[][MAX];

token search_token (unsigned int i, attri tt){

// tra ve tri tu vung cua tu to bdau tu vi tri i, thuoc tinh tra ve cho tt

token tk; unsigned char c;

state s=0, cs;

//c t ký t

tr ng b

ắ

ự ắ

ỏ

do {

c=readchar(x,i);

cs=table[s][c];

if (cs==ERROR_STATE){

69 printf(“loi tai vi tri %i”,i); tk=“”;break; }

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

4. L p b phân tích t v ng ậ ộ ừ ự

else if (star_end_state(cs)) {

strcpy(tt,attribute(cs));

break;

}

else if (nostar_end_state(cs)) {

catchar_in_token(c,tk);

i++;

strcpy(tt,attribute(cs));

break;

70

}

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

4. L p b phân tích t v ng ậ ộ ừ ự

else if (i>=(strlen(x)-1)) {

printf(“het xau vao, ko roi vao TT ket thuc”);

tk=“”; break;

}

else{

catchar_in_token(c,tk);

i++;

s=cs;}

}while(1);

return tk;

71

}

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

v ng ậ ộ

4. L p b phân tích t ừ ự void create_table(int table[][MAX]){

// tao bang chuyen trang thai table

}

void lexical_analysis(){

token tk; attri a;

create_table(table);

do {

tk=search_token(&i,a);

save_token_and_attribute(tk,a);

}while ((tk!='\0')&&(i
72

}

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

5. B ng cac t tô ́ ừ ả ́

G m các token và các thu c tính c a token ộ

Tr t

v ng

Ttính

ộ

ị ừ ự token

01

Num

02

45

Id

03

A

Id

04

B

05

Relation

06

<

Then

07

Then

73

operator

08

+

ủ Các thu c tính khác ồ Ch sỉ ố

ÂN TÍCH T V NG

CH

NG 2. PH

ƯƠ

Ừ Ự

tô 6. Các c u trúc d li u cho b ng các t ữ ệ ả ấ ừ ́

- T ch c tu n t : m ng, danh sách liên

ầ ự ả k t, danh sách móc n i ố ổ ứ ế

74

- T ch c cây tìm ki m nh phân ổ ứ ế ị

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

- M t s v n đ v ngôn ng ộ ố ấ ề ề ữ

- Văn ph m phi ng c nh ữ ả ạ

- Đ i c ng v phân tích cú pháp ạ ươ ề

75

- Các ph ng pháp phân tích cú pháp ươ

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

1. M t s v n đ v ngôn ng ộ ố ấ ề ề ữ

1.1. Xâu

- B ch (b ng ch ) là t p h p h u h n các ậ ợ ữ ạ ộ ữ ả ữ

ký hi uệ

Ví d :{0,1} b ch g m 2 ký hi u 0 và 1 ộ ữ ồ ụ ệ

{a,b,c,…,z} b ch g m các ký hi u a ộ ữ ồ ệ

z

76

T p các ch cái ti ng vi ữ ế ậ t ệ

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

1. M t s v n đ v ngôn ng ộ ố ấ ề ề ữ

1.1. Xâu

- Xâu trên b ch V là 1 dãy các ký hi u c a V ộ ữ ệ ủ

Ví d :ụ 0110 là xâu trên b ch {0,1} ộ ữ

a, ab, giathanh là xâu trên b ch ộ ữ

{a,b,…,z}

- Đ dài xâu là s các ký hi u trong xâu ố ộ ệ

77

đ dài xâu x là |x| Ký hi u:ệ ộ

Ví d :ụ |01110|=5

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

1. M t s v n đ v ngôn ng ộ ố ấ ề ề ữ

1.1. Xâu

- Xâu r ng là xâu có đ dài b ng 0 ỗ ộ ằ

e , |e |=0 Ký hi u: ệ

- T p t t c các xâu trên V là V

, {e }˝ V*

ậ ấ ả

V+ =V -{e }

V: t p vô h n đ m đ ế c ượ ậ

78

,a,b,aa,bb,ab,ba,…} ạ Ví d :ụ V={a,b}V={e

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

1. M t s v n đ v ngôn ng ộ ố ấ ề ề ữ

1.1. Xâu

- Các phép toán trên xâu

• Ghép ti p: cho 2 xâu x,y. Ghép ti p c a x, y ế

ế ủ c, r i đ n ồ ế ế ướ

là x.y hay xy là 1 xâu vi t x tr y sau ch không có d u cách. ấ ứ

Ví d :ụ x=01

79

y=0110

xy=010110

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

1. M t s v n đ v ngôn ng ộ ố ấ ề ề ữ

1.1. Xâu

c vi t theo ượ ế

ượ ng

r): xâu đ i c a xâu x

c l • Đ o ng c xâu x (x ả th t ứ ự ượ ạ ủ

Ví d : ụ x=0101 xr =1010

e Chú ý:

r= e

, 1r =1

- Xâu x mà x=xr thì x là xâu hình tháp (xâu

80

đ i x ng) ố ứ

Ví d : x=0110 xr=0110, x: xâu hình tháp ụ

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

1. M t s v n đ v ngôn ng ộ ố ấ ề ề ữ

1.2. Ngôn ngữ

- Ngôn ng L trên b ch V là t p h p các ậ ợ ộ ữ

ữ xâu trên V, L˝ V

- Các phép toán trên ngôn ngữ

81

• Vì ngôn ng là t p h p nên có các phép ậ ợ (giao), ¨ (h p), -(hi u, bù) ữ ậ ợ ˙ toán t p h p: ợ ệ

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

1. M t s v n đ v ngôn ng ộ ố ấ ề ề ữ

1.2. Ngôn ngữ

• Ghép ti p 2 ngôn ng ế ữ

ữ

ọ ế ộ ậ ợ

Cho 2 ngôn ng L1, L2. Ta g i ghép ti p L1.L2 (L1L2) c a L1 và L2 là m t t p h p ủ L1L2={xy/(x˛ L1) và (y˛ L2)}

82

x.x=x2; x.x.x=x3; x0=e ; xi=xi-1x L0={e }; Li=Li-1.L

- L=L0¨ L1¨ L2¨ …¨ ; L+=L1¨ L2¨ …¨

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

1. M t s v n đ v ngôn ng ộ ố ấ ề ề ữ

1.3. Bi u di n ngôn ng ễ ể ữ

 Ngôn ng đ n gi n ả ữ ơ

- Ph ng pháp li ố ệ

h u h n và có th xác đ nh đ c. ươ ữ ạ t kê: ngôn ng có s xâu là ữ ượ ể ị

ụ ố ự nhiên nh ỏ

Ví d : ngôn ng là các s t ữ h n 20 và l n h n 12 ớ ơ ơ

83

L={13, 14, 15, 16, 17, 18, 19}

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

1. M t s v n đ v ngôn ng ộ ố ấ ề ề ữ

1.3. Bi u di n ngôn ng ễ ể ữ

 Ngôn ng đ n gi n ả ữ ơ

- Ph ng pháp s d ng tân t ử ụ ừ

ng mà các xâu có cùng các đ c đi m. P(x): ngôn ể ặ ươ ữ

Ví d : ngôn ng là các s th c nh h n 5. ố ự ỏ ơ ụ

ữ L={x/ (x˛ R) và (x<5)}

 Ngôn ng ph c t p ữ ứ ạ

ạ

84 Văn ph m: c ch đ s n sinh ra ngôn ơ ế ể ả ngữ

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

2. Văn ph m phi ng c nh ữ ả ạ

2.1. Đ nh nghĩa: G=(Σ, Δ, s, p) trong đó: ị

Σ: t p h u h n các ký hi u k t thúc. ậ ữ ạ ệ ế

Δ: t p h u h n các ký hi u ch a k t ậ ữ ạ ư ế ệ

thúc.

s: ký hi u b t đ u; s ˛ Δ ắ ầ ệ

p: t p h u h n các s n xu t có d ng ậ ữ ạ ả ạ ấ

Aa v i Aớ ˛ Δ và

85

a ˛ (Σ¨ Δ)

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

2. Văn ph m phi ng c nh ữ ả ạ

2.2. Ví d : G=(Σ, Δ, s, p) trong đó: ụ

Σ: {0,1}

Δ: {S}

s: S

86

p: S0S | 1S | 0 | 1

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

2. Văn ph m phi ng c nh ữ ả ạ

 Qui c: ướ

c vi - Ký hi u k t thúc đ ệ ế ượ ế ằ t b ng ch ữ

th ngườ

- Ký hi u ch a k t thúc đ c vi ư ế ệ ượ ế ằ t b ng ch ữ

in

ư ế ủ ệ

87

- Ký hi u ch a k t thúc n m bên trái c a s n xu t đ u tiên là ký hi u b t đ u. ả ấ ầ ắ ầ ằ ệ

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

2. Văn ph m phi ng c nh ữ ả ạ

2.3. Các khái ni mệ

 Xâu (câu) và d ng câu: ạ

- a a g i là xâu khi ˛ Σ* ọ

88

- a a ˛ g i là d ng câu khi (Σ¨ Δ)* ọ ạ

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

2. Văn ph m phi ng c nh ữ ả ạ

2.3. Các khái ni mệ

 Quan h suy d n: ệ ẫ

a ệ ẫ ượ

A, có nghĩa là t - A có quan h suy d n ra ừ c suy đ A áp d ng các s n ả hay a ụ

d n t ẫ ừ xu t sinh ra đ ấ ượ a c

A áp d ng ệ ẫ ừ ụ

m t s n xu t sinh đ - Quan h suy d n tr c ti p: t ấ ự ế ượ a c ộ ả

89

(cid:222) a ˛ (Σ¨ Δ)* Ký hi u: Aệ v i Aớ ˛ Δ và a

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

2. Văn ph m phi ng c nh ữ ả ạ

2.3. Các khái ni mệ

 Quan h suy d n: ệ ẫ

A áp d ng ẫ ụ

- Quan h suy d n nhi u l n: t ề ầ nhi u s n xu t m i sinh đ ấ ệ ề ả ừ ượ a c ớ

+ a

(cid:222) ˛ (Σ¨ Δ)* Ký hi u: A ệ v i Aớ ˛ Δ và a

- Đ dài suy d n: s l n áp d ng các s n ố ầ ụ ẫ ả

90

ộ xu tấ

- Đ dài c a suy d n tr c ti p b ng 1 ẫ ự ế ủ ộ ằ

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

2. Văn ph m phi ng c nh ữ ả ạ

2.3. Các khái ni mệ

 Quan h suy d n: ệ ẫ

ệ

ẫ

91

ở ng t - N u luôn luôn thay th ký hi u ch a k t ư ế ế bên trái nh t g i là suy d n trái. ấ ọ ta có suy d n ph i ả ẫ ế thúc T ươ ự

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

2. Văn ph m phi ng c nh ạ

PHÂN TÍCH CÚ PHÁP ữ ả

2.3. Các khái ni mệ

 Cây suy d n: cây tho mãn các đi u ki n: ệ ề ả ẫ

- M i nút có 1 nhãn: ký hi u k t thúc ho c ệ ế ặ

ch a k t thúc ỗ ư ế

- Nhãn c a nút g c: ký hi u b t đ u ố ắ ầ ủ ệ

- Nhãn c a nút lá: ký hi u k t thúc ệ ế ủ

- N u m t nút có nhãn A có các nút con c a ủ ộ

92

trái sang ph i có nhãn x1, x2, x3, …xn ừ

ế nó t ả thì Ax1x2x3…xn ˛ p

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

2. Văn ph m phi ng c nh ạ

PHÂN TÍCH CÚ PHÁP ữ ả

2.3. Các khái ni mệ

 Cây suy d nẫ

- Suy d n trái t o cây suy d n trái. ạ ẫ ẫ

- Suy d n ph i t o cây suy d n ph i. ả ả ạ ẫ ẫ

- Ví d : cho văn ph m phi ng c nh sau: ạ ữ ả ụ

(1) (2) (3) (4) EE+E | EE | (E) | a

ẫ ả

V cây suy d n trái, ph i sinh xâu: 93 ẽ a+aa

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

2. Văn ph m phi ng c nh ạ

PHÂN TÍCH CÚ PHÁP ữ ả

2.3. Các khái ni mệ

 Văn ph m đ n nghĩa ạ ơ

ạ

ằ

ỉ

Văn ph m G=(Σ, Δ, s, p) s n sinh ra ả ˛ Σ}. Ta nói G là văn ế ậ ˛ L(G) ch có m t cây suy ộ i thì G là văn ph m ạ ạ

94

ngôn ng L(G)={w ữ ph m đ n nghĩa (không nh p nh ng) n u ơ ạ v i m i xâu w ớ ỗ d n duy nh t, trái l ấ ẫ nh p nh ng. ằ ậ

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

2. Văn ph m phi ng c nh ạ

PHÂN TÍCH CÚ PHÁP ữ ả

2.3. Các khái ni mệ

 Văn ph m t ng đ ng ạ ươ ươ

ng G1 ấ

95

ươ (cid:219) ng đ thì G2 cũng sinh ra đ ượ ọ ượ c và ng ươ ừ i Văn ph m G1 và G2 đ ạ b t kỳ xâu x đ ượ c g i là t c sinh ra t c l ượ ạ

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

2. Văn ph m phi ng c nh ạ

PHÂN TÍCH CÚ PHÁP ữ ả

2.3. Các khái ni mệ

 Văn ph m đ qui ạ ệ

ạ

+a Ab

˛ Δ mà thì A g i là ký hi u đ qui, G ệ ˛ , b (Σ¨ Δ) ớ $ A(cid:222) ệ ớ a g i là văn ph m đ qui. V i ạ ọ

ệ

96

Cho văn ph m PNC G, v i A ọ ệ - N u ế a =e : đ qui trái - N u ế b =e : đ qui ph i ả ệ

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

2. Văn ph m phi ng c nh ạ

PHÂN TÍCH CÚ PHÁP ữ ả

2.3. Các khái ni mệ

 Văn ph m đ qui ạ ệ

(1) (2) (3) (4) Ví d : Sụ S0 | S1 | 0 | 1

97

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

2. Văn ph m phi ng c nh ạ

PHÂN TÍCH CÚ PHÁP ữ ả

Bài t pậ

(1) Xác đ nh ngôn ng đ c s n sinh b i Văn ữ ượ ả ở

ị ph m:ạ a. SS(S)S | e

b. SaSb | bSa| e

98

c. S+ S S | * S S | a d. S0S1 | e

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

2. Văn ph m phi ng c nh ạ

PHÂN TÍCH CÚ PHÁP ữ ả

Bài t pậ

(2) Xây d ng văn ph m s n sinh ra ngôn ng : ữ ự ạ ả

a. S nh phân l ố ị ẻ

b. S nguyên k0 d u ố ấ

c. S nguyên có d u ố ấ

99

d. S th c, s nguyên k0 và có d u ố ự ố ấ

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

2. Văn ph m phi ng c nh ạ

PHÂN TÍCH CÚ PHÁP ữ ả

Bài t pậ

(2) Xây d ng văn ph m s n sinh ra ngôn ng : ữ ự ạ ả

a. S0S |1S |1

b. S0S| 1S|..|9S|0|..|9

c. NCD D S

D + | -

100

S0S| 1S|..|9S|0|..|9

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

2. Văn ph m phi ng c nh ạ

PHÂN TÍCH CÚ PHÁP ữ ả

Bài t pậ

(2) Xây d ng văn ph m s n sinh ra ngôn ng : ữ ự ả ạ

d. SONCD.S | S.S | S |NCD

NCD D S

D + | -

101

S0S| 1S|..|9S|0|..|9

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

3. Đ i c ng v phân tích cú pháp ạ ươ ề

3.1. M c đích ụ

Cho G=(Σ, Δ, s, p) t đúng cú pháp ế

x có vi c a văn ph m G? ủ ạ

102

M t xâu vào x ˛ Σ* ộ

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

3. Đ i c ng v phân tích cú pháp ạ ươ ề

3.2. Ph ng pháp gi ươ ả i quy t ế

ấ ể

 B t đ u t x: PTCP t S áp d ng các s n xu t đ tìm ả trên xu ng ắ ầ ừ ừ ụ ố

c x: x vi t đúng cú pháp c a - N u tìm đ ế ế ủ

ượ văn ph m Gạ

- N u k0 tìm đ t không đúng cú ế ượ ế

103

pháp c a văn ph m G ủ c x: x vi ạ

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

3. Đ i c ng v phân tích cú pháp ạ ươ ề

3.2. Ph ng pháp gi ươ ả i quy t ế

 B t đ u t c 1 ụ ượ

x áp d ng các suy d n ng i lên ắ ầ ừ s n xu t đ thu S: PTCP t ấ ể ả ẫ d ừ ướ

c S: x vi t dúng cú pháp c a ế ủ - N u thu đ ế

ượ văn ph m Gạ

c S: x vi t k0 đúng cú pháp ế

104

- N u k0 thu đ ạ ượ ế c a văn ph m G ủ

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

3. Đ i c ng v phân tích cú pháp ạ ươ ề

3.2. Ph ng pháp gi ươ ả i quy t ế

ụ ạ

Ví d : Cho văn ph m PNC G sau: (1) SB

(2) (3) BR | (B)

(4)

R E=E

(5) (6) (7) E a | b | (E+E)

105

Xâu x: (a=(b+a))

H i xâu x có vi t đúng cú pháp c a G ỏ ế ủ

k0?

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

3. Đ i c ng v phân tích cú pháp ạ ươ ề

3.2. Ph ng pháp gi ươ ả i quy t ế

Ví d :ụ

 Ph ng pháp t ố

ươ (1) trên xu ng (4)

(3)

ừ (2) S => B => (B) => (R) => (E=E)

(5)

(7) => (E=(E+E)) => (E=(E+a)) (6) (5) => (E=(b+a)) => (a=(b+a)) :xâu x

106

V y xâu x vi t đúng cú pháp c a G ậ ế ủ

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

3. Đ i c ng v phân tích cú pháp ạ ươ ề

3.2. Ph ng pháp gi ươ ả i quy t ế

Ví d :ụ

 Ph ng pháp t i lên ươ d ừ ướ

ạ

107

Cán a b a Sx dùng Ea Eb Ea

Stt (0) (1) (2) (3) D ng câu (a=(b+a)) (E=(b+a)) (E=(E+a)) (E=(E+E)) (E+E) E(E+E)

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

3. Đ i c ng v phân tích cú pháp ạ ươ ề

3.2. Ph ng pháp gi ươ ả i quy t ế

Ví d :ụ

 Ph ng pháp t i lên

E=E RE=E

R (B) B BR B(B) SB

108

ươ (4) (5) (6) (7) (8) V y xâu x vi d ừ ướ (E=E) (R) (B) B S t đúng cú pháp c a G ậ ủ ế

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

3. Đ i c ng v phân tích cú pháp ạ ươ ề

3.3. S đ chung gi i thu t PTCP t i lên ơ ồ ả ậ d ừ ướ

a

S

0

Bi t ế a

i tìm a

i-1

a a

i = g

i-1

A

g g ˛

iui (Σ¨ Δ);

i

ui

i

a ˛ Σ b

i

Ab

g

i’

g a

k=x

109

a

a ui i’b i =g k = x=uk; g 0 = S=g

k=e 0; u0=e

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

3. Đ i c ng v phân tích cú pháp ạ ươ ề

3.3. S đ chung gi i thu t PTCP t i lên ơ ồ ả ậ d ừ ướ

 Thu t toá n: ậ

S d ng: 1 stack và 1 Buffer ử ụ

Kh i t o: - stack: $ ở ạ

- Buffer: x$

L p: If (Stack là $S) và (Buffer là $) Then ặ

110

- x đúng cú pháp c a vp G ủ

- D ng vòng l p ặ ừ

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

3. Đ i c ng v phân tích cú pháp ạ ươ ề

3.3. S đ chung gi i thu t PTCP t i lên ơ ồ ả ậ d ừ ướ

 Thu t toá n: ậ

Else

If (cán b xu t hi n đ nh stack) Then ệ ở ỉ ấ

b - L y cán ấ ra kh i stack ỏ

111

- Đ y A vào stack v i A ẩ ớ b

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

3. Đ i c ng v phân tích cú pháp ạ ươ ề

3.3. S đ chung gi i thu t PTCP t i lên ơ ồ ả ậ d ừ ướ

 Thu t toá n: ậ

Else

If (Buffer<>$) Then

D/c k/h  Stack ở ỉ đ nh c a Buffer ủ

Else

112

-Báo l i x không đúng cú pháp VP G ỗ

-D ng vòng l p ừ ặ

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

3. Đ i c ng v phân tích cú pháp ạ ươ ề

3.3. S đ chung gi i thu t PTCP t i lên ơ ồ ả ậ d ừ ướ

 Ví d : ụ Sif DK then L ;

DK  true | false

L  write(ID) | read(ID)

ID a | b

113

Xâu x: if true then read(a); có đúng cú pháp vp trên?

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

3. Đ i c ng v phân tích cú pháp ạ ươ ề

3.3. S đ chung gi i thu t PTCP t i lên ơ ồ ả ậ d ừ ướ

 Ví d : ụ

Stt

Stack

Buffer

Hành đ ngộ

(0) $

if true then read(a); $

D/c

(1) $if

true then read(a);$

D/c

(2) $if true

then read(a);$ R/g DKtrue

(3) $if DK

then read(a);$

D/c

(4) $if DK then

read(a);$

D/c 114

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

3. Đ i c ng v phân tích cú pháp ạ ươ ề

3.3. S đ chung gi i thu t PTCP t i lên ơ ồ ả ậ d ừ ướ

 Ví d : ụ

Stt

Stack

Buffer

Hành đ ngộ

(5) $if DK then read

(a);$

D/c

(6) $if DK then read(

a);$

D/c

);$

(7) $if DK then read(a

R/g IDa

(8) $if DK then read(ID

);$

D/c

(9) $if DK then read(ID)

;$ R/g Lread(ID)

115

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

3. Đ i c ng v phân tích cú pháp ạ ươ ề

3.3. S đ chung gi i thu t PTCP t i lên ơ ồ ả ậ d ừ ướ

 Ví d : ụ

Stt

Stack

Buffer

Hành đ ngộ

(10) $if DK then L

;$

D/c

(11) $if DK then L;

$ R/g Sif DK then L;

(12) $S

$ Ch p nh n x đúng cp G

ậ

ấ

116

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

3. Đ i c

PHÂN TÍCH CÚ PHÁP ng v phân tích cú pháp

ạ ươ ề

3.4. S đ chung gi i thu t PTCP t trên xu ng ơ ồ ả ậ ừ ố

a

0

Bi t ế a

i tìm a

i+1

g

i

S ui

a g a

i

i = ui

A

Ab

g ˛ g

i (Σ¨ Δ);

i

i

’

b a

i+1

˛ Σ

g

i’

g a

k=x

117

a

k=e

a ui i =Ag i’ k = x=uk; g 0 = S=A=g

0;

g

0’=u0=e

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

3. Đ i c ng v phân tích cú pháp ạ ươ ề

3.4. S đ chung gi i thu t PTCP t trên xu ng ơ ồ ả ậ ừ ố

 Thu t toá n: ậ

S d ng: 1 stack và 1 buffer ử ụ

Kh i t o: - stack: S$ ở ạ

- Buffer: x$

L p: If (Stack là $) và (Buffer là $) Then ặ

118

- x đúng cú pháp c a VP G ủ

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

3. Đ i c ng v phân tích cú pháp ạ ươ ề

3.4. S đ chung gi i thu t PTCP t trên xu ng ơ ồ ả ậ ừ ố

 Thu t toá n: ậ

- D ng vòng l p ừ ặ

Else

If (A˛ Δ) xu t hi n đ nh Stack Then ấ

ọ

119

đ nh Stack ệ ở ỉ ợ b Ch n sx thích h p A ằ b Tri n khai A b ng ể ở ỉ

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

3. Đ i c ng v phân tích cú pháp ạ ươ ề

3.4. S đ chung gi i thu t PTCP t trên xu ng ơ ồ ả ậ ừ ố

 Thu t toá n: ậ

Else

If (a˛ Σ) xu t hi n đ nh Stack và ấ ệ ở ỉ

Buffer Then

L y a ra kh i Stack và Buffer {đ i ố ỏ ấ

120

sánh}

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

3. Đ i c ng v phân tích cú pháp ạ ươ ề

3.4. S đ chung gi i thu t PTCP t trên xu ng ơ ồ ả ậ ừ ố

 Thu t toá n: ậ

Else

- Báo l i x không đúng cú pháp c a G ỗ ủ

121

- D ng vòng l p ừ ặ

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

3. Đ i c ng v phân tích cú pháp ạ ươ ề

3.4. S đ chung gi i thu t PTCP t trên xu ng ơ ồ ả ậ ừ ố

 Ví d : ụ SaA

AbA | c

122

Xâu x: abbc có đúng cú pháp c a VP trên ? ủ

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

3. Đ i c ng v phân tích cú pháp ạ ươ ề

3.4. S đ chung gi i thu t PTCP t trên xu ng ơ ồ ả ậ ừ ố

 Ví d : ụ

Stt Stack Buffer Hành đ ngộ

(0) S$ abbc$ Tri n khai S aA ể

(1) aA$ abbc$ Đ i sánh ố

(2) A$ bA bbc$ Tri n khai A ể

123

(3) bA$ bbc$ Đ i sánh ố

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

3. Đ i c ng v phân tích cú pháp ạ ươ ề

3.4. S đ chung gi i thu t PTCP t trên xu ng ơ ồ ả ậ ừ ố

 Ví d : ụ

Stt Stack Buffer Hành đ ngộ

(4) A$ bA bc$ Tri n khai A ể

bc$ ố

c

(5) (6) (7) bA$ A$ c$ Đ i sánh c$ Tri n khai A ể Đ i sánh c$ ố

(8) $ $

124 Ch p nh n

ấ ậ

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP ng v phân tích cú pháp

3. Đ i c ề ạ ươ

Bài tập:

(1) Cho văn ph m G: S var ID:K;T ạ

ID a | b | c

K byte | integer | real

T  begin L end.

L  read(ID) | write(ID)

125

Xâu x: var a : byte; begin read(a) end.

Xâu x có đúng cp c a G? ch/m? ủ

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP ng v phân tích cú pháp

3. Đ i c ề ạ ươ

Bài tập:

(2) Cho văn ph m G: S aA | bA ạ

A cA | bA | d

Xâu x: abbcbd

126

Xâu x có đúng cp c a G? ch/m? ủ

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

4. Các ph ng pháp phân tích cú pháp ươ

4.1. T trên xu ng ừ ố

- Ph ng pháp tiên đoán ươ

127

- Ph ng pháp đ qui không quay lui ươ ệ

CH

ƯƠ

NG 3. CÁC V N Đ C B N V Ề

Ề Ơ Ả

Ấ

PHÂN TÍCH CÚ PHÁP

4. Các ph ng pháp phân tích cú pháp ươ

4.2. T d i lên ừ ướ

- Ph ng pháp u tiên toán t ươ ư ử

- Ph ng pháp th t y u ươ ứ ự ế

128

- Ph ng pháp LR(k) ươ

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.1. Ph ng pháp u tiên toán t ươ ư ử

 Văn ph m u tiên toán t ạ ư ử

Văn ph m phi ng c nh th a mãn các ĐK: ữ ả ỏ ạ

- Không có 2 s n xu t có cùng v ph i ả ế ả ấ

e - Không có v ph i là ế ả

- Không có 2 ký hi u ch a k t thúc đ ng ư ế ứ ệ

129

li n nhau ề

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.1. Ph ng pháp u tiên toán t ươ ư ử

 M i quan h u tiên gi a các ký hi u ệ ữ ố

ệ ư ˛ Σ có: V i a, b ớ

(cid:215) - a < b : a kém u tiên h n b ư ơ

(cid:215)

- a= b: a u tiên b ng b ư ằ

(cid:215) - a > b: a u tiên h n b ư ơ

130

- a và b : không có quan h u tiên ệ ư

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.1. Ph ng pháp u tiên toán t ươ ư ử

ắ ố

(1) $ ế . a=b

ả hay a aCbb

(2) $ a
ả hay B(cid:222) ế + bg

(3) $ a>b.

131

 Qui t c xác đ nh m i quan h ệ ị ạ a abb Sx mà v ph i có d ng ạ a aBb Sx mà v ph i có d ng +Cbg mà B(cid:222) ạ a Abb + g aC Sx mà v ph i có d ng ả ế + g a hay A(cid:222) mà A(cid:222)

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.1. Ph ng pháp u tiên toán t ươ ư ử

 Qui t c xác đ nh m i quan h ệ ị

ố +g aC (4) a >$.

ắ +g a hay S(cid:222) + ag S(cid:222) hay S(cid:222) hay S(cid:222)

+Cag

V i a, b ˛ Σ; A,B,C˛ Δ; a , b , g ˛ (Σ¨ Δ)* ớ

. .  L u ýư :- Cán:< >

. - a < b

132

a < c.

. b < c (Không có T/c b c ắ c u)ầ

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

1. Ph

PHÁP ng pháp phân tích cú pháp d

i lên ươ ướ

1.1. Ph ng pháp u tiên toán t ươ ư ử

 Thu t toá n ậ

S d ng: 1 stack và 1 Buffer ử ụ

- stack: $ Kh i t o: ở ạ

- Buffer: x$

L p: If (Stack là $S) và (Buffer là $) Then ặ

133

- x đúng cú pháp c a vp G ủ

- D ng vòng l p ặ ừ

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.1. Ph ng pháp u tiên toán t ươ ư ử

 Thu t toá n ậ

Else {gi s k/h k t thúc g n đ nh stack ả ử ế

ầ ỉ nh t là a và ấ

buffer là b} .

.

134

If (a>b) Then - Tìm cán b ở ỉ đ nh stack(v trí m cán <) ị ở

b - L y cán ấ

- Đ y A vào stack v i A ẩ ra kh i stack ỏ ớ b

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

1. Ph

PHÁP ng pháp phân tích cú pháp d

i lên ươ ướ

1.1. Ph ng pháp u tiên toán t ươ ư ử

 Thu t toá n ậ

Else

. . If (a
D/c b t Buffer  Stack ừ

Else

135

- Báo l i x không đúng cú pháp G ỗ

- D ng vòng l p ừ ặ

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.1. Ph ng pháp u tiên toán t ươ ư ử

 Ví d : ụ Sif DK then L ;

DK  true | false

L  write(ID) | read(ID)

ID a | b

136

Xâu x: if true then read(a); có đúng cú pháp vp trên?

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.1. Ph ng pháp u tiên toán t ươ ư ử

 Ví d :ụ

- Xác đ nh t ị ấ ả t c các m i quan h ố ệ

Xét v ph i c a t ng s n xu t ấ ả ủ ừ ế ả

137

- Phân tích

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

1. Ph

PHÁP ng pháp phân tích cú pháp d

i lên ươ ướ

1.1. Ph ng pháp u tiên toán t ươ ư ử

 Ví d :ụ

t c các m i quan h ố ệ ị

a ấ ả a C b b .

if = then (qt1) a - Xác đ nh t Sx(1):Sif DK then L; (cid:222) a B b

. if < true | false (qt2)

Sif DK then L; b g B b g true | false (cid:222) DK(cid:222) A b b

a

a

138

. S if DK then L; a g A g true | false (cid:222) DK(cid:222) true | false > then(qt3)

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.1. Ph ng pháp u tiên toán t ươ ư ử

 Ví d :ụ

ấ ả ệ

- Xác đ nh t t c các m i quan h ị ố a C b b a Sx(1):Sif DK then L; (cid:222) . then = ; (qt1)

T ươ : ự

ng t . then < write | read (qt2)

139

. ) > ; (qt3)

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

1. Ph

PHÁP ng pháp phân tích cú pháp d

i lên ươ ướ

1.1. Ph ng pháp u tiên toán t ươ ư ử

 Ví d :ụ

- Xác đ nh t ị ấ ả t c các m i quan h ố ệ

Sx(4|5): Lwrite(ID) | read(ID)

.

write | read = ( (qt1)

.

( = ) (qt1)

140

. ( < a | b (qt2)

. a |b > ) (qt3)

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.1. Ph ng pháp u tiên toán t ươ ư ử

 Ví d :ụ

t c các m i quan h ố ệ ị

g - Xác đ nh t (1) . S (cid:222) if | ; > $

141

ấ ả a if DK then L ; (cid:222) a g

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.1. Ph ng pháp u tiên toán t ươ ư ử

 Ví d :ụ

Stt

Stack

Buffer

H/đ ngộ

(0) $

if true then read(a);$

D/c

(1) $if

true then read(a);$

Q/h ệ . < . <

D/c

.

(2) $if true

then read(a);$

R/g DKtrue

. <

(3) $if DK

then read(a);$

> . =

D/c

142

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.1. Ph ng pháp u tiên toán t ươ ư ử

 Ví d :ụ

Stt

Stack

Buffer

Q/hệ

H/đ ngộ

(4) $if DK then

read(a);$

D/c

. <

(5) $if DK then read

(a);$

D/c

. =

(6) $if DK then read(

a);$

D/c

. <

. >

R/g IDa 143

(7) $if DK then read( a );$ . <

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.1. Ph ng pháp u tiên toán t ươ ư ử

 Ví d :ụ

Stack

Stt

Buffer Q/hệ

H/đ ngộ

(8)

$if DK then read(ID

);$

D/c

(9)

. = . >

;$

R/g Lread(ID)

$ if DK then read(ID) . <

(10) $ if DK then L

;$

D/c

. = . >

$

(11) $ if DK then L; . <

R/g Sif DK then L;

144

(12) $S

$

Ch p nh n

ấ

ậ

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

1. Ph

PHÁP ng pháp phân tích cú pháp d

i lên ươ ướ

1.1. Ph ng pháp u tiên toán t ươ ư ử

Bài tập:

(1) Cho văn ph m G: ạ

S C ; H H type ID=A;B

Cconst ID = N A  byte | real

IDa | b | c B var ID : A;

145

N  5

Xâu x: const a=5; type b=byte; var c:real;

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

1. Ph

PHÁP ng pháp phân tích cú pháp d

i lên ươ ướ

1.1. Ph ng pháp u tiên toán t ươ ư ử

Bài tập:

(2) Cho văn ph m G: ạ

S C ; H H type ID=A var B

Cconst ID = N A  byte; | real;

IDa | b | c B ID : A

146

N  5

Xâu x: const a=5; type b=byte; var c:real;

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

1. Ph

PHÁP ng pháp phân tích cú pháp d

i lên ươ ướ

1.1. Ph ng pháp u tiên toán t ươ ư ử

Bài tập:

(2) Các m i quan h : ệ ố

. . . 5 | = > ; ;|var| : |const > $

.

. =<5

; < type . const
147

. . const= = . type= = . a|b|c> = . a|b|c> = . = = var . ;>var var< :|a|b|c

. =< byte|real . . byte|real=; a|b|c> : :< byte|real

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.2. Ph ng pháp th t y u ươ ứ ự ế

ấ ạ

Buffer

 C u t o: Stack

…

xi

$

x1 x2

yi

…

y2

y1

$

K t quế

ả

B phân ộ tích

B ng S_R

ả

148

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.2. Ph ng pháp th t y u ươ ứ ự ế

 C u t o: ấ ạ

(Σ¨ Δ)

- Xi ˛ - yi ˛ Σ

- S_R: ma tr n có: ậ

˛ (Σ¨ Δ) • Ch s hàng xi ỉ ố

149

˛ Σ • Ch s c t yi ỉ ố ộ

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.2. Ph ng pháp th t y u ươ ứ ự ế

 C u t o: ấ ạ

• S_R[xi,yi]: có các giá trị

 S_R[xi,yi]=S

 S_R[xi,yi]=R

 S_R[xi,yi]=R*

150

 S_R[xi,yi]=r ngỗ

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.2. Ph ng pháp th t y u ươ ứ ự ế

 Ho t đ ng: ạ ộ

ở ỉ

ộ ộ

151

- T i m t th i đi m nào đó k/h đ nh c a ờ ể ủ ạ ộ (Σ¨ Δ), stack là Xi˛ ˛ Σ. đ nh buffer là yi ở ỉ B phân tích s xác đ nh hành đ ng thông ị ẽ qua b ng S_R: ả

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.2. Ph ng pháp th t y u ươ ứ ự ế

 Ho t đ ng: ạ ộ

• S_R[xi,yi]: xác đ nh hành đ ng ộ ị

 S_R[xi,yi]=S: d ch chuy n k/h đ nh ị ể ỉ

buffer  stack

 S_R[xi,yi]=R: rút g nọ

152

 S_R[xi,yi]=R: ch p nh n x đúng cp G ấ ậ

 S_R[xi,yi]=r ng: báo l i x k0 đúng cp ỗ ỗ

G

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

1. Ph

PHÁP ng pháp phân tích cú pháp d

i lên ươ ướ

1.2. Ph ng pháp th t y u ươ ứ ự ế

 Thu t toá n ậ

S d ng: 1 stack và 1 Buffer ử ụ

- stack: $ Kh i t o: ở ạ

- Buffer: x$

L p: ặ

153

đ nh stack là x, đ nh buffer ở ỉ ở ỉ

{g/s k/h ử là y}

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.1. Ph ng pháp th t y u ươ ứ ự ế

 Thu t toá n ậ

If (S_R[x,y]=R) Then

- x đúng cú pháp c a vp G ủ

- D ng vòng l p ừ ặ

Else If (S_R[x,y]=r ng) Then ỗ

154

Báo l i và d ng vòng l p ỗ ừ ặ

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

1. Ph

PHÁP ng pháp phân tích cú pháp d

i lên ươ ướ

1.1. Ph ng pháp th t y u ươ ứ ự ế

 Thu t toá n ậ

Else If (S_R[x,y]=S) then

D/c y t buffer stack ừ

Else {S_R[x,y]=R}

dài nh t đ nh stack) ấ ở ỉ

155

ả b If (Có v ph i ế then

- L y ấ b ra kh i stack ỏ

- Đ y A vào stack v i A ẩ ớ b

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

1. Ph

PHÁP ng pháp phân tích cú pháp d

i lên ươ ướ

1.2. Ph ng pháp th t y u ươ ứ ự ế

 Thu t toá n ậ

Else

156

- Báo l i và d ng vòng l p ỗ ặ ừ

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.2. Ph ng pháp th t y u ươ ứ ự ế

 Ví d : Cho G : S id=A ụ

AA+B | B

BBC | C

Cid | (A)

157

Xâu x: id=id+idid

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP B ng S_R ả

id

*

+

)

(

=

$

S

R*

S

S

A

R

R

S

R

B

R

R

R

R

C

R

R

R

R

id

S

R

S

*

S

S

+

S

S

(

S

R

R

R

)

R

S

=

S

158

$

S

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.1. Ph ng pháp th t y u ươ ứ ự ế

ắ ố

( 1 ) $ Sx mà v ph i có d ng  Qui t c xác đ nh m i quan h ệ ị ạ a xyb ế

ả .

.

159

˛ ,b (Σ¨ Δ)* - N u yế ˛ Σ thì: x = y - N u yế ˛ Δ thì: x < y (Σ¨ Δ); a V i xớ ˛

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP ng pháp phân tích cú pháp d

i lên 1. Ph ướ ươ

1.1. Ph ng pháp th t y u ươ ứ ự ế

ắ ố

( 2 ) $ Sx mà v ph i có d ng  Qui t c xác đ nh m i quan h ệ ị ạ a xAb

.

˛ ˛ ả ế + yg mà A(cid:222) (Σ¨ Δ); A˛ Δ; a thì: x < y ,b (Σ¨ Δ)* V i x,yớ

( 3 ) $ Sx mà v ph i có d ng

ế mà A(cid:222) ả + g x và B(cid:222) ,g ạ a ABb . + yq thì: x > y

160

˛ ˛ V i x,y,B ,b ,g (Σ¨ Δ)* ớ

(Σ¨ Δ); A˛ Δ; a ,q ˛ Σ thì y chính là B) (N u Bế

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.1. Ph ng pháp th t y u ươ ứ ự ế

 Qui t c xác đ nh m i quan h ệ ị ố ắ

161

(4) S(cid:222) +g x hay S(cid:222) +xg (Σ¨ Δ) ; g . thì x > $ (Σ¨ Δ)* ˛ V i xớ ˛

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.2. Ph ng pháp th t y u ươ ứ ự ế

 Xây d ng b ng S_R ự

ả . . - X < Y hay X=Y thì: S_R[X,Y]=S

. - X > Y thì: S_R[X,Y]=R

- Stack là $S và Buffer là $ thì: S_R[X,Y]=R*

- X và Y không có m i quan h thì: ố ệ

162

S_R[X,Y]=r ng ỗ

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.2. Ph ng pháp th t y u ươ ứ ự ế

 Ví d : cho G nh sau: ư ụ

SA C D A const ID=N;

C var ID: K; D begin L end.

L write(ID) |read(ID) ID a|b

N5 Kbyte|real

163

Xâu x: const a=5;var b:byte;begin read(b) end.

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.2. Ph ng pháp th t y u ươ ứ ự ế

.

. )>end

begin
Các m i quan h : ệ

ố

.

. A < C

. A < var

; > var

. C < D

.

.

.

C< begin

const|A>$

; > begin

. var < ID

. .|D > $ . ID = :

. : < K

. K = ;

.

.

. var < a|b

. a|b > :

:
byte|real>;

. write|read = (

. ID = )

.

.

.

( < a|b a|b > )

const
.

const
164

. = < N . = < 5 .

.

. N=; . 5 > ;

begin
. ( < ID . ID= = . a|b > = . L=end

end=.

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.2. Ph ng pháp th t y u ươ ứ ự ế

 Văn ph m th t y u ứ ự ế ạ

Văn ph m phi ng c nh th a mãn các ĐK: ữ ả ỏ ạ

- Không có 2 s n xu t có cùng v ph i ả ấ ế ả

e - Không có v ph i là ế ả

- Không có ph n t S_R[x,y] có c tr S và R ầ ử ả ị

165

- N u ế $ Ax1x2…xn và Bxixi+1…xn thì

không $ xi-1<=B

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.2. Ph ng pháp th t y u ươ ứ ự ế

 Văn ph m th t y u

ạ ứ ự ế xi-1<=B thì có nghĩa $

ư ậ ể ọ

ọ ồ ớ

ề

ế ế ấ ả

166

N u ế $ Cx1x2…xi- 1B và nh v y đ thu g n x1x2…xn, thì s ẽ thu g n xixi+1…xn v B r i m i thu g n ọ ề x1x2…xi-1B v C. Nh v y mâu thu n v i ẫ ớ ư ậ tính ch t luôn luôn thay th v ph i dài nh t. ấ

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.3. Ph ng pháp Simple LR (SLR) ươ

ấ ạ

Buffer

ai

 C u t o: Stack … Si-1 Xi-1

Si

…

a1

a0

$

$ S0 x0

K t quế

ả

B phân ộ tích

B ng SLR

ả

167

Action Goto

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.3. Ph ng pháp Simple LR (SLR) ươ

 C u t o: ấ ạ

- Stack: $s0x0 s1x1…si-1xi-1si

˛ (Σ¨ Δ) ạ st: tr ng thái; x

t

˛ Σ - Buffer: aiai-1…a0$ ; v i aớ t

168

- B ng SLR g m 2 ph n: action và goto ồ ầ ả

• Ch s hàng: tr ng thái S ỉ ố ạ

t

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.3. Ph ng pháp Simple LR (SLR) ươ

 C u t o: ấ ạ

• Ch s c t ỉ ố ộ

Ph n action: a ˛ Σ ầ

i

169

Ph n goto: X ˛ Δ ầ

(RJ) • Action[Si,ai]=Shift j (Sj) • Action[Si,ai]=Reduce Aa

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.3. Ph ng pháp Simple LR (SLR) ươ

 C u t o: ấ ạ

• Action[Si,ai]=Accept

• Action[Si,ai]=r ngỗ

170

• Goto[Si,X]=j

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

1. Ph

PHÁP ng pháp phân tích cú pháp d

i lên ươ ướ

1.3. Ph ng pháp Simple LR (SLR) ươ

 Ho t đ ng: ạ ộ

ờ ể

ở ỉ

ph n

T i m t th i đi m b phân tích đ c tr ng ạ ọ ộ ạ ộ đ nh đ nh stack và ký hi u vào a thái Si ở ỉ ệ i buffer và tra trong b ng SLR ở ầ ả Action m t giá tr . N u: ị ế ộ

- Action[Si,ai]=Shift j (Sj)

171

Buffer Stack ừ  D/c ai t

 Đ y j vào stack ẩ

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.3. Ph ng pháp Simple LR (SLR) ươ

 Ho t đ ng:

(RJ) - ạ ộ Action[Si,ai]=Reduce Aa

 L y 2r ph n t ra kh i stack. V i r=| ầ ử ỏ ớ

a ấ |

 Đ y A vào stack ẩ

 Đ y j vào stack v i j=goto[S ớ ẩ

i-r,A]

172

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.3. Ph ng pháp Simple LR (SLR) ươ

 Ho t đ ng: ạ ộ

- Action[Si,ai]=Accept

 Xâu x đúng cp c a vpG ủ

- Action[Si,ai]=r ngỗ

173

 Báo l i x không cú pháp c a vpG ỗ ủ

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

1. Ph

PHÁP ng pháp phân tích cú pháp d

i lên ươ ướ

1.3. Ph ng pháp Simple LR (SLR) ươ

 Thu t toán: ậ

S d ng: 1 stack, 1 buffer, b ng SLR ử ụ ả

- stack: $0 Kh i t o: ở ạ

- Buffer: x$

g/s đ nh stack là S } L p: {ặ ử ở ỉ ỉ

i, đ nh buffer là a

174

If (Action[Si,a]=accept) then

- x đúng cp và d ng vòng l p ừ ặ

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.3. Ph ng pháp Simple LR (SLR) ươ

 Thu t toán: ậ

Else If (Action[Si,a]=Sj) then

- D/c a t buffer  stack ừ

ẩ

175

) then - Đ y j vào stack Else IF (Action[Si,a]=Reduce Aa

- L y 2r ph n t ầ ử ấ ra kh i stack ỏ

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.3. Ph ng pháp Simple LR (SLR) ươ

 Thu t toán: ậ

- Đ y A vào stack ẩ

- Đ y j vào stack. V i j=goto[S ớ ẩ

i-r,A]

Else {Action[Si,a]=r ngỗ }

176

- Báo l i x không đúng cp c a G ỗ ủ

- D ng vòng l p ừ ặ

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.3. Ph ng pháp Simple LR (SLR) ươ

 Ví d : Cho vp G ụ

(1) (2) E  E + T | T (3) (4) T  T * F | F

(5) (6) F  (E) | id

177

Xâu x: id(id+id)

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.3. Ph ng pháp Simple LR (SLR) ươ

Action

Goto

T/ thái

id

+

(

)

$

E

T

F

0

S5

S4

1

2

3

1

S6

Accept

2

R2

S7

R2

R2

3

R4 R4

R4

R4

4

S5

S4

8

2

3

5

R6 R6

R6

R6

178

6

S5

S4

9

3

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.3. Ph ng pháp Simple LR (SLR) ươ

Action

Goto

T/ thái

id

+

*

(

)

$

E

T

F

7

S5

S4

10

8

S6

S11

9

R1

S7

R1

R1

10

R3 R3

R3

R3

11

R5 R5

R5

R5

179

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.3. Ph ng pháp Simple LR (SLR) ươ

Stack

Buffer

Hành đ ngộ

$0

0

id(id+id)$

S5

$0 id 5

1

(id+id)$

R6(Fid)

$0 F 3

2

(id+id)$

R4(TF)

$0 T 2

3

(id+id)$

S7

4

$0 T 2 * 7

(id+id)$

S4

180

5

$0 T 2 * 7 ( 4

id+id)$

S5

 Ví d :ụ Stt

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

Stack

Buffer

1.3. Ph ng pháp Simple LR (SLR) ươ

Hành đ ngộ

6

$0 T 2 * 7 ( 4 id 5

+id)$

R6(Fid)

7

$0 T 2 * 7 ( 4 F 3

+id)$

R4(TF)

8

$0 T 2 * 7 ( 4 T 2

+id)$

R2(ET)

9

$0 T 2 * 7 ( 4 E 8

+id)$

S6

10 $0 T 2 * 7 ( 4 E 8 + 6

id)$

S5

11 $0 T 2 * 7 ( 4 E 8 + 6 id 5

)$

181 R6(Fid)

 Ví d :ụ Stt

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.3. Ph ng pháp Simple LR (SLR) ươ

Stack

Buffer

Hành đ ngộ

12 $0 T 2 * 7 ( 4 E 8 + 6 F 3

)$

R4(TF)

13 $0 T 2 * 7 ( 4 E 8 + 6 T 9

)$

R1(EE+T)

14 $0 T 2 * 7 ( 4 E 8

)$

S11

15 $0 T 2 * 7 ( 4 E 8 ) 11

$

R5(F(E))

16 $0 T 2 * 7 F 10

$

R3(TTF)

17 $0 T 2

$

182 R2(ET)

 Ví d :ụ Stt

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.3. Ph ng pháp Simple LR (SLR) ươ

Stack

Buffer

Hành đ ngộ

18 $0 E 1

$

Accept

183

 Ví d :ụ Stt

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.3. Ph ng pháp Simple LR (SLR) ươ

 Xây d ng b ng SLR ự ả

- Văn ph m gia t G’ ạ ố

G’=G ¨ {S’S}

Ví d : ụ G: S  0S | 1S|0|1

G’: S’  S

184

S  0S | 1S|0|1

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.3. Ph ng pháp Simple LR (SLR) ươ

 Xây d ng b ng SLR ự ả

ự ấ ấ ở ấ b t kỳ v ị

- Th c th : Sx thêm d u ch m ả ể trí c a v ph i. ủ ế

Ví d : ụ A xyz

thì A .xyz Ax.yz Axy.z

185

A  xyz. là các th c thự ể

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.3. Ph ng pháp Simple LR (SLR) ươ

 Xây d ng b ng SLR ự ả

- Hàm tính bao đóng Closure(Ii): 2 qui t cắ

(1) Đ a t ư ấ ả t c các th c th trong I ự ể

i vào

closure(Ii)

(2) C m i th c th có d ng ể ạ

˛

thì thêm 186

Aa B.g ˇ ứ ỗ ự .Bb closure(Ii) mà Bg vào closure(Ii) v i Bớ .g closure(Ii)

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.3. Ph ng pháp Simple LR (SLR) ươ

 Ví d : Xac đinh tâp closure(I) cua VP G’ ụ ́ ̣ ̣ ̉

E’ E

E  E + T | T

T  T F | F

F  (E) | id

I={E’.E}

187

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.3. Ph ng pháp Simple LR (SLR) ươ

 Xây d ng b ng SLR ự ả

- Hàm tính goto

188

Goto(Ii,x)=closure({Aa x.b }) .xb } (cid:204) (Σ¨ Δ) v i {Aớ a Ii ; x˛

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.3. Ph ng pháp Simple LR (SLR) ươ

 Ví d : Tim tât ca cac tâp goto(I,X) co thê ̀ ́ ̉ ́ ̣ ́ ̉

̉

ụ cua VP G I={

E’.E

E.E+T

E’ E E  E + T | T T  T * F | F F  (E) | id

E.T

T.TF

}

Goto(I,E)=closure({E’E. ; EE.+T})

X: E, T

Goto(I,T)=closure({ET. 189 ; TT.F})

Goto(I,E) va Goto(I,T)

̀

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.3. Ph ng pháp Simple LR (SLR) ươ

 Xây d ng b ng SLR ự ả

- T p th c th LR(0) ự ể ậ

I0=closure({S’.S})

t c các t p - Tính t ủ ấ ả ậ

i,x) c a t c t p LR(0).

t c các goto(I ấ ả th c th ta s đ ể ẽ ượ ậ ự

i,x) mà không sinh đ

190

c Iượ i+1

- Tính h t goto(I ế thì d ng.ừ

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.3. Ph ng pháp Simple LR (SLR) ươ

 Xây d ng b ng SLR ự ả

ộ

( 1 ) $ - Qui t c xác đ nh hành đ ng ị ˛ ắ Aa Ii và goto(Ii,a)=Ij v i a ớ ˛ Σ

.ab thì: Action[i,a]= Sj

( 2 ) $ Aa .Xb ˛ ˛ Δ Ii và goto(Ii,X)=Ij v i X ớ

191

thì: goto[i,X]= j

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.3. Ph ng pháp Simple LR (SLR) ươ

 Xây d ng b ng SLR ự ả

- Qui t c xác đ nh hành đ ng ị ộ

( 3 ) $ ắ S’S. ˛

( 4 ) $ Aa . ˛ Ii thì: Action[i,$]= accept Ii thì Action[i,a]= Reduce Aa

Follow(A); A<>S’ v i aớ ˛

192

- Qui t c xác đ nh Follow Follow(A)={(t ˛ Σ|

ắ +a Atb )¨ ị (t=$|S(cid:222) S(cid:222)

+ a A)}

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.3. Ph ng pháp Simple LR (SLR) ươ

 Ví d : Cho vp G ụ

E  E + T | T

T  T * F | F

F  (E) | id

193

Xây d ng b ng SLR cho VP G ự ả

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.3. Ph ng pháp Simple LR (SLR) ươ

 Ví d : ụ

- Xác đ nh G’ ị

- T o t p th c th LR(0) ự ạ ậ ể

194

- Xác đ nh các hành đ ng ộ ị

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.3. Ph ng pháp Simple LR (SLR) ươ

 Ví d : ụ

- VP gia t G’ố

E’  E

E  E + T | T

T  T * F | F

195

F  (E) | id

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.3. Ph ng pháp Simple LR (SLR) ươ

 Ví d : ụ

ể

T.F

- T o t p th c th LR(0) ự ạ ậ I0=closure({E’.E})

F.(E)

E’.E

F.id

E.E+T

I1=goto(I0,E)

E.T

E’E.

196

T.TF

EE.+T

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.3. Ph ng pháp Simple LR (SLR) ươ

 Ví d : ụ

197

- Xác đ nh các hành đ ng ộ ị

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.3. Ph ng pháp Simple LR (SLR) ươ

Bài tập:

(1) cho VPG: A A or B | B

B  B and C | C

C  not C | (A) | true | false

H i xâu x: true and false or (not true) có đ c ỏ ượ

198

sinh ra t ừ VPG? c/m b ng PP SLR ằ

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.3. Ph ng pháp Simple LR (SLR) ươ

Bài tập:

(2) Cho VPG: S AS| b

A  SA| a

199

Xây d ng b ng SLR cho VP G? ự ả

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.4. Ph ng pháp Canonical LR (LR(1)) ươ

ỉ ả ở

ộ . - Trong PP SLR xung đ t ch x y ra ể a nh ng th c th A ự ữ

- Khi x y ra xung đ t ta có th s d ng PP ộ ể ử ụ

200

ả Canonical LR

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.4. Ph ng pháp Canonical LR (LR(1)) ươ

 C u t o: nh SLR ấ ạ ư

 Ho t đ ng: nh SLR ạ ộ ư

 Thu t toán: nh SLR ư ậ

201

 Xây d ng b ng Canonical LR ả ự

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.4. Ph ng pháp Canonical LR (LR(1)) ươ

 Xây d ng b ng Canonical LR ả ự

- Văn ph m gia t ạ ố : nh SLR ư

- Th c th : g m có 2 ph n ể ồ ự ầ

+ Ph n nhân: gi ng th c th trong SLR ự ố ể ầ

202

c: a ˛ Σ + Ký hi u nhìn tr ệ ướ

Ví d : Aụ X.YZ, a

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.4. Ph ng pháp Canonical LR (LR(1)) ươ

 Xây d ng b ng Canonical LR ả ự

- Hàm tính bao đóng closure(Ii): 2 qui t cắ

(1) Đ a t ư ấ ả t c các th c th trong I ự ể

i vào

closure(Ii)

(2) C th c th [A .Bb ứ ự ể a ,a]˛ closure(Ii) mà

203

Bg thì thêm [B.g , b] vào closure(Ii)

first(b a) v i [Bớ .g , b]ˇ closure(Ii) và b˛

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.4. Ph ng pháp Canonical LR (LR(1)) ươ

 Xây d ng b ng Canonical LR ả ự

a - Qui t c xác đ nh First( )

+e

(cid:222) (cid:222) ắ First(a ị )={(a˛ Σ|a

+ab )¨

(a=$|a )}

- Hàm tính goto(Ii,X)

, a}) v i ớ

204

Goto(Ii,X)=Closure({Aa X.b {Aa , a}(cid:204) .Xb (Σ¨ Δ) Ii và X˛

- I0=closure({S’.S, $})

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.4. Ph ng pháp Canonical LR (LR(1)) ươ

 Xây d ng b ng Canonical LR ả ự

G’: S’S

cho I={S’.S,$} va ̀

S AA

Tinh Closure(I)=? ́

A aA | d

A a

.Bb

, a Closure(I)={ S’.S, $

B g , b S.AA, $

A.aA, a|d

205

A.d, a|d }

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.4. Ph ng pháp Canonical LR (LR(1)) ươ

 Xây d ng b ng Canonical LR ả

ự I={ S’.S, $

G’: S’S

S.AA, $

S AA

A.aA, a|d

A aA | d

Goto(I,S)=closure({S’S.,$})

A.d, a|d }

Goto(I,A)=closure({SA.A,$})

X:{S, A, a, d}

Goto(I,a)=closure({Aa.A,a|d})

206

Goto(I,d)=closure({Ad., a|d})

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.3. Ph ng pháp Canonical LR (LR(1)) ươ

 Xây d ng b ng Canonical LR ả ự

ộ

( 1 ) $ - Qui t c xác đ nh hành đ ng ị ,b]˛ ắ [Aa Ii và goto(Ii,a)=Ij v i a ớ ˛ Σ

.ab thì: Action[i,a]= Sj

( 2 ) $ [Aa ,b] ˛ Ii và goto(Ii,X)=Ij v i X ớ

207

.Xb ˛ Δ thì: goto[i,X]= j

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.3. Ph ng pháp Canonical LR (LR(1)) ươ

 Xây d ng b ng Canonical LR ả ự

- Qui t c xác đ nh hành đ ng ị ộ ắ

( 3 ) $ [S’S.,$] ˛ Ii thì: Action[i,$]= accept

( 4 ) $ Ii thì Action[i,a]= Reduce

208

.,a]˛ v i A<>S’ Aa [Aa ớ

NG PHÁP PHÂN TÍCH CÚ

CH

NG 4. CÁC PH

ƯƠ

ƯƠ

1. Ph

PHÁP ng pháp phân tích cú pháp d

i lên ươ ướ

1.3. Ph ng pháp Canonical LR (LR(1)) ươ

 Xây d ng b ng Canonical LR ả ự

- Tr n các t p th c th ể ậ ự ộ

ậ ớ

ầ ướ i v i nhau đ đ ể ượ

V i các t p th c th có chung ph n nhân, ể ự c, ta có khác nhau ph n ký hi u nhìn tr ệ ầ th tr n chúng l c m t ộ ạ ớ t p th c th m i có: ể ớ ậ ể ộ ự

+ ph n nhân: ph n gi ng nhau ố ầ ầ

+ ký hi u nhìn tr ệ ướ

209 c: h p các k/h nhìn tr c ướ

ợ

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.4. Ph ng pháp Canonical LR (LR(1)) ươ

 Xây d ng b ng Canonical LR ả ự

Ví d : ụ S AA

A aA | d

- Xây d ng văn pham gia tô G’ ự ̣ ́

- Tinh I ́ ̀ ́ ̉ ́

0=closure({S’.S, $} va tât ca cac I

i

210

- Xac đinh hanh đông ́ ̣ ̀ ̣

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.4. Ph ng pháp Canonical LR (LR(1)) ươ

 Xây d ng b ng Canonical LR ả ự

Ví d : ụ S AA

A aA | d

211

I0=closure({S’.S, $}

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.4. Ph ng pháp Canonical LR (LR(1)) ươ

Action

Goto

a

d

$

S

A

0

S36

S47

1

2

1

Accept

2

S36

S47

5

36

S36

S47

89

47

R3

R3

R3

89

R2

R2

R2

212

5

R1

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.4. Ph ng pháp Canonical LR (LR(1)) ươ

Stt

Stack

Buffer

Hành đ ngộ

0

$0

aadad$

S36

1

$0 a 36

adad$

S36

2

$0 a 36 a 36

dad$

S47

3

$0 a 36 a 36 d 47

ad$

R3(Ad)

4

$0 a 36 a 36 A 89

ad$

R2(AaA)

5

$0 a 36 A 89

ad$

R2(AaA)

213

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.4. Ph ng pháp Canonical LR (LR(1)) ươ

Stt

Stack

Buffer

Hành đ ngộ

6

$0 A 2

ad$

S36

7

$0 A 2 a 36

d$

S47

8

$0 A 2 a 36 d 47

$

R3(Ad)

9

$0 A 2 a 36 A 89

$

R2(AaA)

10 $0 A 2 A 5

$

R1(SAA)

11 $0 S 1

$

Accept 214

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

1. Ph ng pháp phân tích cú pháp d i lên ươ ướ

1.4. Ph ng pháp Canonical LR (LR(1)) ươ

Bài tập: xây d ng b ng Canonical LR ự ả

SAS | b

A SA | a

̣ (I0I10) trôn I

2 va Ì

10, I3 va Ì

7, I8 va Ì

9

215

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

ế ằ

- PTCP t ả ố ề ặ

trên xu ng: thay v trái b ng v ế ừ ph i. M t v n đ đ t ra khi có 2 sx có v ế ộ ấ trái gi ng nhau thì ch n sx nào? ọ ố

- Ch n m t sx n u không đ c thì quay lui, ộ ế ượ

ch n sx khác ọ ọ

216

- H n ch văn ph m. ế ạ ạ

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.1. Văn ph m LL(1) ạ

- VP cho phép PTCP b ng cách tri n khai

ằ d n d n suy d n trái t trên xu ng. ầ ẫ ầ ừ ể ố

- Thăm dò xâu vào t ừ trái sang ph i ả

217

- Nhìn tr c 1 ký hi u ướ ệ

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.1. Văn ph m LL(1) ạ

 Đ nh nghĩa: ị

c g i là LL(1) VP PNC G=(Σ, Δ, S, p) đ

ề ế ỏ

( 1 ) "

b first(b j) = f ph i có first( j v i iớ „

ượ ọ n u nó th a mãn 2 đi u ki n sau: ệ b 1 | b 2 | b 3 |… | b n thì sx có d ng Aạ i) ˙ ả (2) A˛ Δ mà A(cid:222) first(A) ˙

+ e thì ph i có: ả follow(A)=f

218

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.1. Văn ph m LL(1) ạ

 Ví d :ụ

(1) SA | B

AaA | b

BaB | c

Xét: SA | B First(A)={a,b} First(B)={a,c}

219

f (vi ph m ĐK1) ạ

first(B)={a}„ First(A) ˙ nên vp trên không ph i là LL(1) ả

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.1. Văn ph m LL(1) ạ

 Ví d :ụ

(2) AAa

Aa | e

Xét: A˛ Δ mà A(cid:222)

+ e

có: first(A)={a,$}, follow(A)={a}

f follow(A)={a}„ (vi pham

220

nên first(A)˙ đk2)

VP trên không ph i là LL(1) ả

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.2. Vài phép bi n đ i v VP LL(1) ế ổ ề

 Kh đ qui trái: ử ệ

D ng (1): A ạ

D ng (2): A Aa Aa | b | e ạ

f )=first(b ) first(b )=first(b )„

221

Xét (1) có: first(Aa nên first(Aa )˙ (vi pham đk1)

VP đ qui trái không ph i là LL(1) ệ ả

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.2. Vài phép bi n đ i v VP LL(1) ế ổ ề

ử ệ

 Kh đ qui trái: Aa D ng (1): A | b ạ

D ng (2): A Aa | e ạ

có:

),

)=first(a ) nên

f follow(A)=first(a )„

Xét (2): A˛ Δ mà A(cid:222) + e first(A)=first(Aa follow(A)=first(a first(A)˙ đk2) VP đ qui trái không ph i là LL(1) (vi pham 222 ả ệ

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.2. Vài phép bi n đ i v VP LL(1) ế ổ ề

 Kh đ qui trái: ử ệ

| b D ng (1): ạ

AAa Ab A’ Thay b i: ở

A

A

A’a A’| e

A’

b

A

A’

a a

A

A’

223

a a

b e

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.2. Vài phép bi n đ i v VP LL(1) ế ổ ề

 Kh đ qui trái: ử ệ

D ng (2): ạ

| e AAa Aa A | e Thay b i: ở

A

A

A

A

a a

A

A

224

a a

e e

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.2. Vài phép bi n đ i v VP LL(1) ế ổ ề

 Đ t th a s chung: ừ ố ặ

b g a ạ

b g )=first(a

b g f | a )=first(a )˙ first(a ) )„ )=first(a

225

D ng (3): A Có: first(a nên first(a (vi ph m đk1) ạ

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.2. Vài phép bi n đ i v VP LL(1) ế ổ ề

 Đ t th a s chung: ừ ố ặ

b g D ng (3): | a ạ

Aa Aa A’ Thay b i: ở

226

A’b | g

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.2. Vài phép bi n đ i v VP LL(1) ế ổ ề

 Bài t p:ậ Bi n đ i các VP sau thành LL(1) ế ổ

(1) E  E + T | T

T  T F | F

F  (E) | id

(2) A A T | T

227

T 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.2. Vài phép bi n đ i v VP LL(1) ế ổ ề

 Bài tập: Bi n đ i các VP sau thành LL(1) ế ổ

(3) AA S | A C | C

C a

S  0

(4) Xây d ng VP LL(1) s n sinh ra tên bi n ế ả

228

ự ộ c a m t ngôn ng . ữ ủ

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.2. Vài phép bi n đ i v VP LL(1) ế ổ ề

 Bài tập: gi iả

(1) E  TE’

E’+TE’ | e

T  FT’

T’FT’ | e

229

F(E) | id

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.2. Vài phép bi n đ i v VP LL(1) ế ổ ề

 Bài t p:ậ gi iả

(2) A TA | T ATA’

T 0 | .. | 9 A’A |e

230

T 0|..|9

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.2. Vài phép bi n đ i v VP LL(1) ế ổ ề

 Bài t p:ậ gi iả

(3) Sx(1) và (2) bi n đ i: ế ổ

A AA’ A’S | C

ACA”

AAA’|C ACA” A’S | C A”A’A”|e

A”SA”

231

A’S|C Ca S0

C a A”CA”|e S 0 Ca S0

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.2. Vài phép bi n đ i v VP LL(1) ế ổ ề

 Bài t p:ậ gi iả

(4) ID  ID CC | ID CS |ID_ | CC| _ID|_CS

CC a | b

232

CS  0 | 1

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.2. Vài phép bi n đ i v VP LL(1) ế ổ ề

 Bài t p:ậ gi iả

(4) ACC A’ | _B

BCCA’ | CS A’| _B

A’CCA’| CSA’ | _A’| e

CCa

233

CS0

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.3. Ph ng pháp tiên đoán ươ

 C u t o: ấ ạ

Stack

xi … x2 x1 $

Buffer ai … a2

a1

$

K t quế

ả

B phân tích

ộ

B ng tiên đoán M

ả

234

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.3. Ph ng pháp tiên đoán ươ

ấ ạ

(Σ¨ Δ)

Σ  C u t o: - Stack: xixi-1…x0$ v i xớ t ˛ - Buffer: aiai-1…a0$ v i aớ t ˛

- B ng tiên đoán M: ả

˛  Ch s hàng: A Δ ỉ ố

235

˛ Σ

 Ch s c t: a ỉ ố ộ  M[A,a]: Aa ho c r ng ặ ỗ

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.3. Ph ng pháp tiên đoán ươ

 Ho t đ ng: T i m t th i đi m n u: ạ ộ ờ ể ạ ộ ế

- stack là $ và buffer là $: x đúng CP VPG Ở

- đ nh stack và buffer a Ở ỉ ˛ Σ: đ i sánh a ố

- đ nh stack là A Ở ỉ

˛ Δ thì n u: ế a : tri n khai A • M[A,a]=Aa đ nh ể ở ỉ

236

stack

• M[A,a]=r ng: xâu x không đúng CP VPG ỗ

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.3. Ph ng pháp tiên đoán ươ

 Gi i thu t: ả ậ

S d ng: 1 stack, 1 buffer và b ng tiên đoán ả

ử ụ M

- stack là S$ Kh i t o: ở ạ

- Buffer là x$

237

L p:ặ

If (stack là $) và (buffer là $) then

x đúng cp và d ng vòng l p ừ ặ

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.3. Ph ng pháp tiên đoán ươ

i thu t:  Gi

ả ậ Else if (a˛ Σ đ nh stack và buffer) then

ở ỉ đ i sánh a đ nh stack và buffer ố ở ỉ

Else if (A˛ Δ ở ỉ

đ nh stack) ở ỉ

và (a ˛ Σ if (M[A,a]=Aa

238

tri n khai A đ nh stack ể

đ nh buffer) then )then ở ỉ Else x k0 đúng CP VPG, d ng vòng l p ừ ặ

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.3. Ph ng pháp tiên đoán ươ

 Ví d :ụ SaA

AbA | c

239

Xâu x: abbc có đúng CP c a VP trên ? ủ

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.3. Ph ng pháp tiên đoán ươ

 Ví d :ụ

a b c $

SaA S

240

A AbA Ac

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.3. Ph ng pháp tiên đoán ươ

STT

Stack

Buffer

Hành đ ngộ

(0)

S$

abbc$

Tri n khai S

aA

ể

(1)

aA$

abbc$

Đ i sánh

ố

(2)

A$

bbc$

Tri n khai A

bA

ể

(3)

bA$

bbc$

Đ i sánh

ố

(4)

A$

bc$

Tri n khai A

ể

bA 241

 Ví d :ụ

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.3. Ph ng pháp tiên đoán ươ

STT

Stack

Buffer

Hành đ ngộ

(5)

bA$

Đ i sánh

bc$

ố

(6)

A$

Tri n khai A

c

c$

ể

(7)

c$

Đ i sánh

c$

ố

(8)

$

$ Ch p nh n x đúng cp ậ

ấ

242

 Ví d :ụ

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.3. Ph ng pháp tiên đoán ươ

 Xây d ng b ng tiên đoán M: 2 qui t c ắ

ả thì M[A,a]=Aa v i ớ

( 1 ) " a˛

a ự sx Aa first(a ) e „

( 2 ) " thì M[A,a]=Ae v i a ớ

243

˛ sx Ae follow(A)

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.3. Ph ng pháp tiên đoán ươ

 Xây d ng b ng tiên đoán M: ả ự

Ví d : xây d ng b ng tiên đoán M cho vp: ự ụ ả

(1)

E  TE’ (2) (3) E’+TE’ | e (4)

244

T  FT’

(5) (6) T’FT’ | e (7) (8) F(E) | id

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.3. Ph ng pháp tiên đoán ươ

 Xây d ng b ng tiên đoán M: ả ự

- Xet sx: E  TE’ co First(TE’)={ (, id } ́ ́

M[E,(]=M[E,id]=ETE’

- Xet sx: E’ +TE’ co First(+TE’)={+} ́ ́

M[E’,+]=E’+TE’

245

- Xet sx: T FT’ co First(FT’)={(, id} ́ ́

M[T,(]=M[T,id]=TFT’

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.3. Ph ng pháp tiên đoán ươ

 Xây d ng b ng tiên đoán M: ả ự

- Xet sx: T’ FT’ co First(FT’)={} ́ ́

M[T’,]=T’FT’

- Xet sx: F (E) co First((E))={(} ́ ́

M[F,(]=F(E)

246

- Xet sx: F id co First(id)={id} ́ ́

M[F,id]=Fid

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.3. Ph ng pháp tiên đoán ươ

ự

 Xây d ng b ng tiên đoán M: ả e - Xet sx: E’ co follow(E’)={), $} ́ ́

M[E’,)]=M[E’,$]=E’e e - Xet sx: T’ co follow(T’)={),$,+} ́ ́

M[T’,)]=M[T’,$]=M[T’,+]=T’e (T)(cid:222) F(cid:222) E(cid:222) TE’(cid:222) T(cid:222) FT’(cid:222)

(TE’)(cid:222)

(E)(cid:222)

(FT’)

247

E (cid:222)

TE’ (cid:222)

T+TE’ (cid:222)

FT’+TE’

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.3. Ph ng pháp tiên đoán ươ

+

id

(

)

$

ETE’ ETE’

E

E’ E’+TE’

E’ ε

E’ε

TFT’ TFT’

T

T’ ε

T’FT’

T’ ε

T’ ε

T’

Fid

F(E)

F

248

 Xây d ng b ng tiên đoán M: ả ự

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.3. Ph ng pháp tiên đoán ươ

 Xây d ng b ng tiên đoán M: ả ự

Bài t p: ậ

ả ự

ầ

249

xây d ng b ng tiên đoán M cho các vp LL(1) trong ph n vài phép bi n đ i v ế ổ ề LL(1). T cho xâu vào và phân tích theo PP ự tiên đoán

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.4. Ph ng pháp đ qui không quay lui ươ ệ

- V m t nguyên lý gi ng pp tiên đoán. ề ặ ố

ề ậ

ả đoán M mà mô ph ng tr c ti p. - Khác v l p trình: không tra b ng tiên ỏ ự ế

- Thay stack b ng s đ qui trong ch ng ự ệ ằ ươ

trình.

- M t k/h ch a k t thúc: bdi n b ng 1 bi u ư ế ể ễ ằ

250

đ cú pháp ộ ồ

- M t bi u đ cú pháp: bdi n b ng 1 CT ể ồ ễ ằ

ộ con

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.4. Ph ng pháp đ qui không quay lui ươ ệ

 Bi u đ cú pháp: ể ồ

• K/h k t thúc đ t: ế ặ

• K/h ch a k t thúc đ t: ư ế ặ

- Ví d : Eụ TE’

251

E: T E’

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.4. Ph ng pháp đ qui không quay lui ươ ệ

 CT con bi u di n cho bi u đ cú pháp: ể ồ ể ễ

ự ế ế ủ

ng ng.

(1) S k t ti p c a các nút: s k t ti p c a ươ ứ b ) ự ế ế ủ các đo n CT t ạ ví d : ụ b có đo n ct t( ạ

b b t(b

1) ; t(b

2)

1

2

252

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.4. Ph ng pháp đ qui không quay lui ươ ệ

 CT con bi u di n cho bi u đ cú pháp: ể ồ ể ễ

(2) S r nhánh t o thành c u trúc ch n ự ẽ ọ ạ ấ

b

If k/htiep˛

first(b

1

1) Then t(b

b

Elseif k/htiep˛

first(b

2

Elseif k/htiep˛

first(b

1) 2) Then t(b 2) 3) Then t(b

3)

b

3

Else baoloi;

253

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.4. Ph ng pháp đ qui không quay lui ươ ệ

 CT con bi u di n cho bi u đ cú pháp: ể ồ ể ễ

(3) L p ki m tra đk sau ể ặ

b

Repeat t(b )

Until k/htiepˇ

first(b )

(4) L p ki m tra đk tr ể ặ c ướ

While k/htiep˛

first(b ) do t(b )

254

b

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.4. Ph ng pháp đ qui không quay lui ươ ệ

 CT con bi u di n cho bi u đ cú pháp: ể ồ ể ễ

If k/htiep=a Then

a (5)

k/htiep=k/htieptheo trong xâu x

Else baoloi;

goi B //t(B);

255

B (6)

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.4. Ph ng pháp đ qui không quay lui ươ ệ

 Thu t toán: ậ

k/htiep: ký hi u k t thúc; ệ ế

function Dockh:ký hi u k t thúc; {đ c k/hi u ệ ế ọ ệ

ti p trong x} ế

ư

Procedure Baoloi; {đ a thông báo l Procedure b i, d ng} ỗ ừ ˛ Δ} ễ ể

I;{các Ctcon bi u di n A

256

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.4. Ph ng pháp đ qui không quay lui ươ ệ

 Thu t toán: ậ

Procedure PTCP;

Begin k/htiep:=Dockh;

S;

if k/htiep=$ then x đúng CP

257

else baoloi;

End.

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.4. Ph ng pháp đ qui không quay lui ươ ệ

Ví d :ụ

E  TE’ E’+TE’ | e

T  FT’

T’FT’ | e

258

F(E) | id

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.4. Ph ng pháp đ qui không quay lui ươ ệ

Ví d : Bi u đ cú pháp ể ồ ụ

E:

T

T’:

E’

*

F

T’

+

T

E’

E’:

T:

(

)

E

F

F:

T’

259

id

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.4. Ph ng pháp đ qui không quay lui ươ ệ

Ví d : gi i thu t các ctcon t ng ng ụ ả ậ ươ ứ

k/htiep: ký hi u k t thúc; ệ ế

function Dockh:ký hi u k t thúc; {đ c k/hi u ệ ế ọ ệ

ti p trong x} ế

260

Procedure Baoloi; {đ a thông báo l i, d ng} ư ỗ ừ

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.4. Ph ng pháp đ qui không quay lui ươ ệ

Ví d : gi i thu t các ctcon t ng ng ụ ả ậ ươ ứ

Procedure E;

Begin

T; Ephay;

261

End;

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.4. Ph ng pháp đ qui không quay lui ươ ệ

Ví d : gi i thu t các ctcon t ng ng ụ ả ậ ươ ứ

Procedure Ephay;

Begin

If k/htiep=+ Then

Begin k/htiep:=Dockh;

T;

Ephay;

End;

262

End;

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.4. Ph ng pháp đ qui không quay lui ươ ệ

Ví d : gi i thu t các ctcon t ng ng ụ ả ậ ươ ứ

Procedure T;

Begin

F;

Tphay;

263

End;

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.4. Ph ng pháp đ qui không quay lui ươ ệ

Ví d : gi i thu t các ctcon t ng ng ụ ả ậ ươ ứ

Procedure Tphay;

Begin

If k/htiep=* Then

Begin

k/htiep:=Dockh;

F;

Tphay;

End;

264

End;

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.4. Ph ng pháp đ qui không quay lui ươ ệ

Procedure F; Begin

If k/htiep=id Then k/htiep:=Dockh Else

If k/htiep=( Then

Begin

k/htiep:=Dockh; E; if k/htiep=) Then k/htiep:=Dock Else baoloi;

End

265

Else baoloi; End;

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.4. Ph ng pháp đ qui không quay lui ươ ệ

 Thu t toán: ậ

Procedure PTCP;

Begin k/htiep:=Dockh;

E;

if k/htiep=$ then x đúng CP

266

else baoloi;

End.

CH

NG 4. CÁC PH

NG PHÁP PHÂN TÍCH CÚ

ƯƠ

ƯƠ

PHÁP

2. Ph ng pháp phân tích cú pháp trên xu ng ươ ố

2.4. Ph ng pháp đ qui không quay lui ươ ệ

Bài t p: ậ

i thu t đ qui không quay lui ả

ậ

267

Xây d ng gi ậ ệ ự cho các VP LL(1) trong ph n bài t p vài ầ phép bi n đ i v VP LL(1) ế ổ ề