1
Bài gi ng 4 - Phân tích cú pháp ả
và các ph ng pháp phân tích c ươ ơ
b nả
Nguy n Ph ng Tháiễ ươ
B môn Khoa h c Máy tínhộ ọ
http://www.coltech.vnu.vn/~thainp/
2
Bài toán
Đu vào: câu vào ch a toàn các t tầ ứ ừ ố
Phân tách câu vào thành các ph n theo ầ
văn ph m và bi u di n c u trúc này ạ ể ễ ấ
b ng m t cây (g i là cây phân tích) ằ ộ ọ
ho c theo m t c u trúc nào đó t ng ặ ộ ấ ươ
đng v i cây.ươ ớ
3
Bài toán (ti p)ế
Phán têch
tæì væûng Phán têch
cuï phaïp
cáy
phán
têch Phán têch
ngæî
nghéa
Baíng kyï
hiãûu
yãu cáöu
láúy tæì täú
tæì täú
Chæång
trçnh
nguäön
4
Văn ph mạ
M i ngôn ng l p trình đu có các lu t mô t các ọ ữ ậ ề ậ ả
c u trúc cú pháp.ấ
M t ch ng trình ngu n vi t đúng ph i tuân theo các ộ ươ ồ ế ả
lu t mô t này - t c là vi t đúng văn ph m (hay đúng ậ ả ứ ế ạ
ng pháp). ữ
Văn ph m c a m t ngôn ng l p trình có c u trúc có ạ ủ ộ ữ ậ ấ
th mô t b ng ể ả ằ văn ph m phi ng c nhạ ữ ả và bi u ể
di n theo ký pháp BNF ho c đ th chuy n.ễ ặ ồ ị ể
5
Các ph ng pháp phân tíchươ
C s c a phân tích cú pháp đi v i l p ơ ở ủ ố ớ ớ
VPPNC là đnh lý Bài toán thành viên v i ị ớ
ngôn ng phi ng c nh. Ng i ta đã ch ng ữ ữ ả ườ ứ
minh đc đnh lý này b ng cách đa ra các ượ ị ằ ư
gi i thu t cài đt trên th c t , ví d nh :ả ậ ặ ự ế ụ ư
Thu t toán phân tích Top-Down.ậ
Thu t toán phân tích Bottom - Up.ậ
Thu t toán phân tích CYK (Coke-Younger-ậ
Kasami).
Thu t toán phân tích Earley.ậ