Bài giảng Chương trình dịch - Chương 3: Phân tích cú pháp

Nội dung bài giảng chương 3 giúp người học: Nắm được vai trò của giai đoạn phân tích cú pháp; văn phạm phi ngữ cảnh (context- free grammar),cách phân tích cú pháp từ dưới lên- từ trên xuống (top-down and bottom-up parsing); bộ phân tích cú pháp LR. 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 - Chương 3: Phân tích cú pháp CHƯƠNGIII PhântíchcúphápMụctiêu:NắmđượcvaitròcủagiaiđoạnphântíchcúphápVănphạmphingữcảnh(contextfreegrammar),cáchphântíchcúpháptừdướilêntừtrênxuống(topdownandbottomupparsing)BộphântíchcúphápLR 1 Vaitròcủabộphântíchcú pháp• Đâylàgiaiđoạnthứ2củaquátrìnhbiêndịch• Nhiệmvụchính:Nhậnchuỗicáctokentừbộ phântíchtừvựngvàxácđịnhchuỗiđócó đượcsinhrabởivănphạmcủangônngữ nguồnkhôngSource Lexical Token Parser Parse Rest ofprogram analyzer tree front end Get next token Symbol table 2• Cácphươngphápphântíchcúpháp (PTCP)chialàmhailoại:Phântíchtừtrên xuống(topdownparsing)vàphântíchtừ dướilên(bottomupparsing)• Trongquátrìnhbiêndịchxuấthiệnnhiều lỗitronggiaiđoạnPTCPdođóbộphân tíchcúphápphảipháthiệnvàthôngbáo lỗichínhxácchongườilậptrìnhđồngthơi khônglàmchậmnhữngchươngtrình đượcviếtđúng 3Vănphạmphingữcảnh• Đểđịnhnghĩacấutrúccủangônngữlập trìnhtadùngvănphạmphingữcảnh (Contextfreegrammars)haygọitắtlà mộtvănphạm• Mộtvănphạmbaogồm: Cáckíhiệukếtthúc(terminals):Chínhlàcác token Cáckíhiệuchưakếtthúc(nonterminals):Là cácbiếnkíhiệutậpcácxâukítự Cácluậtsinh(productions):Xácđịnhcách thứchìnhthànhcácxâutừcáckíhiệukếtthúc vàchưakếtthúc 4Vídụ3.1:Vănphạmsauđịnhnghĩacác biểuthứcsốhọcđơngiản E EAE|(E)|E|id A +||*|/| TrongđóE,Alàcáckítựchưakếtthúc(E cònlàkítựbắtđầu),cáckítựcònlạilà cáckítựkếtthúc 5• Dẫnxuất(derivation):Tanói A nếuA làmộtluậtsinh( đọclàdẫn xuấthoặcsuyra)• Nếu 1 2 ...... nthìtanóirằng 1 dẫnxuất n• Kíhiệu: *làdẫnxuất 0bước, làdẫn + xuất 1bước• ChovănphạmGvớikítựbắtđầulàS, L(G)làngônngữđượcsinhbởiG.Mọi xâutrongL(G)chỉchứacáckíhiệukết thúccủaG 6• Tanóimộtxâuw L(G)nếuvàchỉnếuS + w,wđượcgọilàmộtcâu(sentence)củavăn phạmG• Mộtngônngữđượcsinhbởivănphạmphi ngữcảnhđượcgọilàngônngữphingữcảnh (contextfreelanguage)• Haivănphạmđượcgọilàtươngđươngnếu sinhracùngmộtngônngữ• NếuS * ( cóthểchứakíhiệuchưakết thúc)thítanói làmộtdạngcâu(sentence form)củaG.Mộtcâulàmộtdạngcâukhông chứakíhiệuchưakếtthúc 7Vídụ3.2:Xâu–(id+id)làmộtcâucủavăn phạmtrongvídụ3.1vì E E (E) (E+E) (id+E) (id+id)• Mộtdẫnxuấtđượcgọilàtráinhất (leftmost)nếutạimỗibướckíhiệuchưa kếtthúcngoàicùngbêntráiđượcthay thế,kíhiệu lm.NếuS *lm thì được gọilàdạngcâutrái• Tươngtựtacódẫnxuấtphảinhất (rightmost)haycòngọilàdẫnxuấtchính tắc,kíhiệu rm 8• Câyphântíchcúpháp(parsetree)là dạngbiểudiễnhìnhhọccủadẫnxuất.Ví dụparsetreechobiểuthức–(id+id)là: E - E ( E ) E + E | | id id 9• Tínhmơhồcủavănphạm(ambiguity): Mộtvănphạmsinhranhiềuhơnmột parsetreechomộtcâuđượcgọilàvăn phạmmơhồ.Nóicáchkhácmộtvăn phạmmơhồsẽsinhranhiềuhơnmột dẫnxuấttráinhấthoặcdẫnxuấtphải nhấtchocùngmộtcâu.• Loạibỏsựmơhồcủavănphạm:Taxét vídụvănphạmsau Stmt ifexprthenstmt|ifexprthenstmtelsestmt|other 10• Vănphạmtrênlàmơhồvìvớicùngmộtcâu lệnhifE1thenifE2thenS1elseS2sẽ cóhaiparsetree: 11• Ðểloạibỏsựmơhồnàytađưaraquitắc Khớpmỗielsevớimộtthenchưakhớpgần nhấttrướcđó.Vớiquitắcnày,taviết ...