Bài giảng Chương trình dịch: Bài giảng 5 - Nguyễn Phương Thái

Bài giảng 5 trình bày các phương pháp phân tích hiệu quả. Thông qua bài giảng này, người học có thể biết được các ưu và nhược điểm của phân tích Top-Down, Bottom-up; biết được các ưu và nhược điểm của phân tích tất định; nắm bắt được đặc điểm phân tích tất định;... Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Chương trình dịch: Bài giảng 5 - Nguyễn Phương TháiBàigiảng5–Cácphươngphápphântíchhiệuquả NguyễnPhươngThái BộmônKhoahọcMáytính http://www.coltech.vnu.vn/~thainp/ 1PhântíchTopDown,Bottomup Ưuđiểm:  Đơngiản  PhântíchđượcchotoànbộlớpVPPNC  Phântíchđượcngônngữnhậpnhằng Nhượcđiểm:  Quáchậm(cn)dophảiquaylui 2 HaìGiang Cao Bàò ng Lai Cháu Thaïi NguyãnTìmđường Sån La Laû ng Sån Haìnäüi Haíi Phoìng NamÂënh Thanh Hoaï Vinh Âäö ng Håïi Huãú ÂaìNàô ng Quaíng Ngaîi Qui Nhån NhaTrang Phan Rang Phan Thiãú t Tp HCM 3Phântíchhiệuquả(tấtđịnh)Hisinh(nhượcđiểm): LớpngônngữbéhơnPNC BắtbuộckhôngnhậpnhằngƯuđiểm: Rấtnhanh(cn) 4Đặcđiểmphântíchtấtđịnh Quétxâuvàotừphảisangtrái Quátrìnhphântíchlàhoàntoànxác định Khôngdùngquaylui Dựavàotrạngtháihiệntạivàkýhiệu kếtthúcđểxácđịnhluậtduynhất Cácluậtphảiđượcthiếtkếđặcbiệt 5Cáclớpvănphạm VănphạmLL(k)vănphạmchophépxây dựngcácbộphântíchlàmviệctấtđịnhnếu bộphântíchnàyđượcphépnhìnkkýhiệu vàonằmngayởbênphảicủavịtrívàohiện thời. VănphạmLR(k)vănphạmchophépxây dựngcácbộphântíchlàmviệctấtđịnhnếu bộphântíchnàyđượcphépnhìnkkýhiệu vàonằmvượtquávịtrívàohiệnthời. 6PhântíchLL Xáuvaìo c a + b $ Ngàn xãú p Âáöura Chæång trçnh phán X têch táú t âënh Y Z Baíng phán têch M[A,a] $ Mähçnhcuíabäüphántêchtáútâënh 7ChươngtrìnhđiềukhiểnXkýhiệuđỉnhngănxếp,akýhiệuvàohiệntại NếuX=a=$:dừngvàtuyênbốthànhcông (cảxâuvàolẫnngănxếpđềurỗng). NếuX=a $:lấyXkhỏingănxếp,dịchcon trỏvàosangkýhiệuvàotiếptheo(đãkhai triểnđếnlákhớpvớixâuvào). NếuXlàmộtbiến:xétôM[X,a].Nếu:  NếuM[X,a]={X UVW}thayXđangnằmtrên đỉnhngănxếpbằngWVU(Usẽnằmtrênđỉnh) (thựchiệnmộtphépmởrộngcây)  NếuM[X,a]=lỗi(vịtrílỗi),gọihàmkhôiphụclỗi. 8ThuậttoánĐặtcontrỏipchỉđếnkýtựđầutiêncủaxâuw$ repeat GiảsửXlàkýhiệuđỉnhcủangănxếpvàalàkýhiệuvàotiếptheo; ifXlàmộtkýhiệukếtthúchoặc$then ifX=athen popXtừđỉnhngănxếpvàloạibỏakhỏixâuvào else ERROR(); else {Xkhôngphảilàkýhiệukếtthúc} ifM[X,a]=X Y1Y2...Ykthenbegin popXtừngănxếp; pushYk,Yk1,...Y1vàongănxếp,vớiY1ởđỉnh; đưarasảnxuấtX Y1Y2...Yk end else ERROR(); untilX=$; {ngănxếprỗng} 9 HaìGiang Cao Bàò ng Lai Cháu Thaïi Nguyãn Sån La Laû ng Sån Tìmđường ...