IT4073:NGÔN NGỮvà
PHƯƠNG PHÁP DỊCH
PhạmĐăng Hải
haipd@soict.hut.edu.vn
29/18/2012
Chương 2: Phân tích từvựng
1. Nhiệmvụcủabộphân tích từvựng
2. Biểuthức chính quy
3. Ô tô mát hữuhạn
4. Phân tích từvựng củangôn ngữPL/0
39/18/2012
Mụcđích & Nhiệmvụ
•Mụcđích:
– Tìm chuỗidài nhấtcáckýtựđầuvào, bắtđầutừký tự
hiệntạitương ứng vớimộttừtốvà trảvềtừtốnày
•Nhiệmvụ
–Duyệttừng ký tựcủavănbảnnguồn
•Loạibỏcáckýtựkhông cầnthiếtnhưdấu cách, chú thích,..
–Xâydựng từvựng từnhững ký tựđọcđược
–Nhậndạng từtốvà gửitới pha tiếp
Nhậnbiếttừtốgồm
–Nhậnbiếtcáctừkhóa, tên do ngườidùngđịnh nghĩa
–Nhậnbiết các con số, hằng chuỗi, hằng ký tự
–Nhậnbiếtcáckýtựđặcbiệt (+,*,..), ký hiệu kép (:=,!=,..)
1. Nhiệmvụcủabộphân tích
49/18/2012
Từvựng và Từtố
•Từvựng (Lexeme)
–Làđơnvịnhỏnhất trong ngôn ngữlậptrình
•Được coi là ký hiệucủamộtbảng chữcủa ngôn ngữ
–Đượcxâydựng từcáckýtựASCII
•Từtố(Token)
–Làthuậtngữdùng chỉcác từvựng có cùng ý
nghĩa cú pháp
•Cóthểcoi từvựng là những từcụthểtrong từđiển:
“hôm nay”, “trời”, “đẹp”; còn từtốlà loạitừ: “trạng từ”,
“danh từ”, “tính từ”,..
1. Nhiệmvụcủabộphân tích
59/18/2012
Từtố→Ví dụ
•“pos”, “start”, “size”, “+”, “10”, “*”,”:=“, “;”làtừvựng
•“
pos”, “start”, “size”, →các từvựng thuộclớptừtố
tên (ident)
•”
:=“→từvựng củatừtốgán (assign)
•“
10”→từvựng củatừtốsốnguyên (number)
•“
+”→từvựng củatừtốcộng (plus)
•“
*”→từvựng củatừtốnhân (times)
•“
;”→từvựng củatừtốchấmphẩy(semicolon)
1. Nhiệmvụcủabộphân tích
pos := start + 10 * size;
69/18/2012
Từtố→Chú ý
1. Nhiệmvụcủabộphân tích
•CáctừtốIdent, number, plus, assign,... do người
viếttrìnhdịch tựđịnh nghĩađể dễdàng cho việcmã
hóa chương trình. Đây là việcsốhóa ký hiệu
•Mộttừtốcó thểứng vớitậpcáctừvựng khác nhau
nên cầnthêmmộtsốthông tin khác để biếtđược
cụthểđólàtừvựng nào
–Cácchuỗi“
19”, “365”đềulàchuỗisố, có từtố“number”,
nhưngkhisinhmãcầnphảibiếtrõgiátrịlà 19 hay 365
•Bộphân tích từvựng không chỉnhậndạng được
các từtốmà còn phảibiếtthuộc tính tương ứng
–Từtốtác động đếnbộphân tích cú pháp
–Thuộctínhsửdụng trong bộsinh mã
79/18/2012
Thựchiện
•Thựchiệnlặpdựavàoyêucầutừbộptcp
–Bộptcp khi cầnmộttừtốsẽgọigetToken()
–Nhậnđượcy/cầu, bộpttv sẽđọccáckýtựcho tớikhixây
dựng xong từvựng và nhậnratừtốhoặcgặplỗi
•Thường bộpttv được chia thành 2 phầnchính
–Đọckýtự
–Xâydựng từvựng và nhậndạng từtố
1. Nhiệmvụcủabộphân tích
Phân tích
từvựng
Phân tích
cú pháp
Bảng ký hiệu
Chương
trình nguồn
Token
getToken()
89/18/2012
Mẫu (Pattern)
•Làluậtđể mô tảmộttừtốnào đó
–Cơsởphân biệt& nhậndạng các từtốkhác nhau
•Chuỗikýtựcùng thỏamãnmộtluật⇒có cùng mộttừtố
•Từtốlà tên riêng củamộtluậtmôtả, từvựng là một
trường hợpthỏamãnluật
•Vídụ
–LuậtmôtảcủatừtốIdent
•Bắtđầulàmộtchữcái
•Tiếp theo là tổhợpchữcái, chữsố
–Luậtmôtảcủatừtốassign
•Bắtđầubởikýtự“:”, ngay sau đólàkýtự“=“
•Luậtđượcmôtảbởibiểuthức chính quy
1. Nhiệmvụcủabộphân tích
99/18/2012
Chương 2: Phân tích từvựng
1. Nhiệmvụcủabộphân tích từvựng
2. Biểuthức chính quy
3. Ô tô mát hữuhạn
4. Phân tích từvựng củangôn ngữPL/0
109/18/2012
Giớithiệu
2. Biểuthức chính quy
•Ngôn ngữ:Tậphợpcủacáccâu/ xâu(string)
•Câu: Dãy hữuhạncủacáctừ/ký hiệu(
symbol)
•Từ:Đượctạo nên từmộtbộchữhữuhạn
Ví dụ:
–NgônngữC là tậpcáccâulệnh tạo nên các chương
trình C hợplệ
–Bộchữcho ngôn ngữC là tậpcácchữcái ASCII
•Một ngôn ngữcó thểlà vô hạn, hoặchữuhạn
•Một ngôn ngữ(có thểvô hạn) có thểđượcmôtả
hữuhạnnhờsửdụng biểuthức chính quy :
–Mỗibiểuthứcđặctrưng cho mộttập câu/xâu
–Chỉxét xâu có thuộc ngôn ngữkhông, chưa xét ý nghĩa
củaxâu
119/18/2012
Biểuthức chính quy (regular expression)
Cho Σlà mộtbảng chữcủamột ngôn ngữ.
–∅là biểuthức chính quy biểudiễn ngôn ngữ∅
–εlà biểuthức chính quy biểudiễn ngôn ngữ{ε}
–∀a ∈Σ, a là biểuthức chính quy biểudiễntập{a}
–Nếurvà slà các biểuthức chính quy biểudiễn
các tậpxâuRvà Stương ứng thì (r + s), (r.s), (r*)
là các biểuthức chính quy biểudiễncáctậpxâu
R
∪
S, RS và R* tương ứng.
Ngôn ngữđược xác định bởibiểuthức chính
quy e, ký hiệulàL(e) là ngôn ngữchính quy
2. Biểuthức chính quy
129/18/2012
Biểuthức chính quy→Ghi chú
•Biểuthức(r + s) có thểđượcviết(r |s);
•Biểuthức(r.s) thành (rs)
•Cóthểbỏqua ký hiệuε
–( a | ) ⇔(a | ε) // cũng có thểviếta?
•Cóthểbỏngoặcđơnbởiđịnh nghĩathứtự
ưutiên
– Phép đóng Kleene (*) ưutiênhơn phép ghép(.)
– Phép ghép(.) ưutiênhơn phép hoặc (+)
•Quyước
– [abcd] ⇔(a|b|c|d)
– [a-f] ⇔[abcdef]
–[a-fA-F] ⇔[abcdefABCDEF]
2. Biểuthức chính quy
139/18/2012
Biểuthức chính quy→Ví dụ
Cho Σ={a,b} mộtbảng chữ.
–e1= a*+b* ⇒L(e1) = {ε,a,aa,aaa,…,b,bb,..}
–e2= a*b* ⇒L(e2) = {ε,a,b,aa,ab,bb,aaa,..}
–e3= a(a+b)*
⇒L(e3)={a,aa,ab,aaa,aab,aba,abb,..}
• Xâu có dạng: bắtđầulàkýhiệu a, tiếptheolàtổ
hợpbấtkỳcủa các ký hiệua, b
•Nếua làmộtchữcái, b là chữsố
⇒L(e3) là ngôn ngữchứacáctên
⇒e3biểuthức chính quy sinh mô tảmộttên
2. Biểuthức chính quy
149/18/2012
Tính chấtđạisốcủabtcq
•2 biểuthức chính quy là tương đương nếu
cùng xác định một ngôn ngữ
•Nếu r, s, t là các biểuthức chính quy
– r + s = s + r r + r = r
– ( r + s) + t = r + s + t = r + (s + t)
– (r.s).t = r. s. t = r. (s. t)
–r.ε= ε.r = r
–r + ∅= ∅+ r = r
– r(s+t) = rs + ts (r+s)t = rt + st
– r + r* = r* ; (r + ε)* = r* ; (r*)* = r*
– rr* = r*r = r+
– (r+s)* =(r*s*)*
2. Biểuthức chính quy
159/18/2012
Vănphạm chính quy và Ngôn ngữchính quy
•Vănphạm chính quy
–Vănphạmmàmọisảnxuấtcódạng
A→a|aB hoặcA→a|Ba
– Dùng diễntảtừvựng của NNLT
<Tên>→<Chữcái>|<Tên> <Chữcái>|<Tên><Chữsố>
<Tên>→“a” |”b” |”c” |….|”z”|”A”|”B”|…|”Z”
<Chữsố> →”0” | ”1” | ”2” | ”3” |”4” | ”5” |”6” | ”7” |”8” |”9”
–Vănphạm chính quy sinh ra ngôn ngữchính quy
•Ngôn ngữchính quy
–Đượcbiểudiễn(
mô tả) bởibiểuthức chính quy
–Đoán nhậnbởi các Otomat hữuhạn
2. Biểuthức chính quy
169/18/2012
Ngôn ngữchính quy →Vănphạm chính quy
r là biểuthức chính qui cầnchuyển
1. Thêm ký hiệukhởiđầuSvà tạosan xuấtS →r
2. Loạibỏkhỏivănphạm các siêu ký hiệucủar
•∀SX dạng A →r1.r2: Thêm ký hiệu không
kết thúc B và thay thành 2 SX:
A →r1B& B →r2
•∀SX dạng A →r1+r2: Thay bởiA →r1|r2
•∀SX dạng A →r1* r2: Thêm ký hiệu không
kết thúc B và thay thành 4 sảnxuất
A →r1B& A →r2& B →r1B& B →r2
2. Biểuthức chính quy
179/18/2012
Ví dụ
Chuyểnđổibiểuthứce = a(a+b)*
1. Thêm S và sảnxuấtS→a(a+b)*
2. Loạibỏcáckýhiệu không thuộcbộchữ
– Xét r = a(a+b)* //r1=a; r2 = (a+b)*
Thêm A và các SX S→aA & A →(a+b)*
– Xét A →(a+b)* // r1= a+b ; r2= ε
Thêm B và các SX
A→(a+b)B & A →ε &B→(a+b) & B →ε
–Ápdụng luật phân phốiphải
A→aB+bB & A →ε & B→aB+bB & B →ε
A →aB|bB| εvà B →aB|bB| ε
2. Biểuthức chính quy
189/18/2012
Ví dụ
Chuyểnđổibiểuthứce = a(a+b)* (tiếp)
–Loạibỏký hiệuεbởitạoraxâumới
B →aB|bB| εthành B →aB|bB| a | b
A →aB|bB| εthành A →aB|bB| a | b
Vai trò củaA vàB làtương đương. Thay ký
hiệuB bằng A và loạibỏB
Kếtquả: Vănphạmcuối
S →a |aA
A →aA | bA | a | b
2. Biểuthức chính quy
199/18/2012
Chương 2: Phân tích từvựng
1. Nhiệmvụcủabộphân tích từvựng
2. Biểuthức chính quy
3. Ô tô mát hữuhạn
4. Phân tích từvựng củangôn ngữPL/0
209/18/2012
Mô tả
•Gồmmộttậpcáctrạng thái Q
–Cómộttrạng thái đầuq0∈Q
–Cómộttậptrạng thái kếtthúc F ⊆Q
•Mộtbộchữvào Σ
•Mộttập các hàm dịch chuyểnδ:(Q x Σ) →Q
Hoạtđộng
–Ô-tô-mátxuấtpháttừtrạng thái đầu, đọctừng ký hiệu
của xâu vào, chuyểntrạng thái dựatrên trạng thái hiện
thờivàkýhiệuđọcđược.
–Saukhiđọchếtxâuvàomàô-tô-mátởtrạng thái kết
thúc, xâu đượcgọilàđượcđoán nhậnbởiô-tô-mát
3. Ô tô mát hữuhạn