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

Bài giảng 2 cung cấp các nội dung liên quan đến phân tích từ vựng như: Phân tích từ vựng: từ tố, từ vị, mẫu; giới thiệu về REs, FA (DFA, NFA); nâng cao: REs đến NFA; NFA đến DFA; DFA đến minimal-state DFA;...và một số bài tập. 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 2 - Nguyễn Phương Thái NguyễnPhươngTháiBộmônKhoahọcMáytínhhttp://www.coltech.vnu.vn/~thainp/Nội dung Phântíchtừvựng:từtố,từvị,mẫu REs,FA(DFA,NFA) Nângcao:REsNFA;NFADFA;DFAminimal stateDFA Mộtsốbàitập15/11/15 NguyễnPhươngTháiColtechCompiler2009 2Vai trò của hệ phân tích từ vựng(scanner) (từtố) (câycúpháp) (mãnguồn) (lỗitừvựng) Từtốtrongngônngữlậptrìnhcũnggiốngnhưtừtrong ngônngữtựnhiên Hệphântíchtừvựnghoạtđộngnhưmộtthủtụcđược gọibởihệphântíchcúphápkhinócầnmộttừtốmới trongdòngvào15/11/15 NguyễnPhươngTháiColtechCompiler2009 3Từ tố (token) TừtốtrongVCđượcphânloạinhưsau:  cácđịnhdanh(vdsum,i,j)  cáctừkhóa(vdint,ifhaywhile)  cáctoántử(vd“+”hay“∗”,“Từ vị (lexeme) Từvịcủamộttừtố:chuỗikýtựtạothànhtừtố Vídụ:15/11/15 NguyễnPhươngTháiColtechCompiler2009 5Mẫu (từ tố)  Mẫu:luậtmôtảtậpcáctừvịmàcóthểbiểudiễnmộttừtốcụthể  Mẫukhớpvớimỗixâukýtựtrongtậpđó Loạitừtố Mẫu Từvị INTLITERAL astringofdecimaldigits 127,0 FLOATLITERAL fillaverbalspechereforC! 127.1,.1,1.1e2 ID astringofletters,digitsand sum,linenum underscoresbeginningwith aletterorunderscore + thecharacter‘+’ + while theletters‘w’,‘h’,‘i’,’l’,’e’ while  Biểudiễnhìnhthứcchotừtốlàcầnthiết⇒REs,NFA,DFA15/11/15 NguyễnPhươngTháiColtechCompiler2009 6Các biểu thức chính qui (REs)cho số nguyên và số thực trongC15/11/15 NguyễnPhươngTháiColtechCompiler2009 7Các máy hữu hạn trạng thái(FSMs) cho số nguyên và sốthực15/11/15 NguyễnPhươngTháiColtechCompiler2009 8Nội dung Phântíchtừvựng:từtố,từvị,mẫu REs,FA(DFA,NFA) Nângcao:REsNFA;NFADFA;DFAminimal stateDFA Mộtsốbàitập15/11/15 NguyễnPhươngTháiColtechCompiler2009 9REs, DFA và NFA ĐịnhnghĩaREs,DFAvàNFA REs⇒NFA(Thompson’sconstruction,Algorithm3.3, RedDragon/Algorithm3.23,PurpleDragon) NFA⇒DFA(subsetconstruction,Algorithm3.2,Red Dragon/Algorithm3.20,PurpleDragon) DFA⇒minimalstateDFA(stateminimisation,Algorithm 3.6,RedDragon/Algorithm3.39,PurpleDragon)15/11/15 NguyễnPhươngTháiColtechCompiler2009 10Ứng dụng của biểu thức chínhqui Bấtcứnơinàomàmẫuvănbảncầnđượcmôtả Hệthống,cơsởdữliệuvàquảntrịmạngUnix:grep, fgrep,egrep,sed,awk CácvănbảnHTML:JavascriptvàVBScript Perl:J.Friedl,MasteringRegularExpressions,O’reilly, 1997 Môtảtừtốchocácchươngtrìnhsinhhệphântíchtừ vựng(lex,JLex,v.v.) http://www.robotwisdom.com/net/regexres.html15/11/15 NguyễnPhươngTháiColtechCompiler2009 11Ứng dụng của ôtômát hữuhạn Thiếtkếphầncứng(tốithiểuhóatrạngthái⇒tốithiểu hóagiáthành) Lýthuyếtngônngữ Độphứctạptínhtoán Cácchươngtrìnhsinhhệphântíchtừvựng(lexand JLex) JCT://humboldt.sunyit.edu/JCT15/11/15 NguyễnPhươngTháiColtechCompiler2009 12Bộ chữ cái, xâu ký tự và ngônngữ Bộchữcái∑:tậphữuhạnkýhiệu Bộchữcáinhịphân{0,1}(chongônngữmáy) BộchữcáiASCII(chocácngônngữbậccao) Xâukýtự:chuỗihữuhạnkýhiệuthuộc∑ Độdài|s|củaxâus:sốlượngkýhiệutrongs ε:xâurỗng(|ε|=0) Ngônngữ:tậpcácxâutrên∑;haitrườnghợpđặcbiệt: ∅:tậprỗng {ε}15/11/15 NguyễnPhươngTháiColtechCompiler2009 13Ví dụ về ngôn ngữ ∑={0,1}–mỗixâulàmộtchỉthị TậpchỉthịcủaM68K TậpchỉthịcủaPentium TậpchỉthịcủaMIPS ∑=tậpASCII–mỗixâukýtựlàmộtchươngtrình TậpcácchươngtrìnhHaskell TậpcácchươngtrìnhC TậpcácchươngtrìnhVC15/11/15 NguyễnPhươngTháiColtechCompiler2009 14Các thuật ngữ về xâu ký tự(Figure 3.7 of Text) Thuậtngữ Địnhnghĩa Prefixofs(tiềntốcủas) astringobtainedbyremoving 0ormoretrailingsymbolsofs Suffixofs(hậutốcủas) ...