Nguy n Ph ng Tháiễ ươ
B môn Khoa h c Máy tínhộ ọ
http://www.coltech.vnu.vn/~thainp/
Nội dung
Phân tích t v ng: t t , t v , m uừ ự ừ ố ừ ị ẫ
REs, FA (DFA, NFA)
Nâng cao: REs NFA; NFA DFA; DFA minimal-
state DFA
M t s bài t p ộ ố ậ
15/11/15 2
Nguy n Ph ng Thái - Coltech - Compiler 2009ễ ươ
Vai trò của hệ phân tích từ vựng
(scanner)
T t trong ngôn ng l p trình cũng gi ng nh t trong ừ ố ữ ậ ố ư ừ
ngôn ng t nhiênữ ự
H phân tích t v ng ho t đng nh m t th t c đc ệ ừ ự ạ ộ ư ộ ủ ụ ượ
g i b i h phân tích cú pháp khi nó c n m t t t m i ọ ở ệ ầ ộ ừ ố ớ
trong dòng vào
(t t )ừ ố
(l i t v ng)ỗ ừ ự
(mã ngu n)ồ
(cây cú pháp)
15/11/15 3
Nguy n Ph ng Thái - Coltech - Compiler 2009ễ ươ
Từ tố (token)
T t trong VC đc phân lo i nh sau:ừ ố ượ ạ ư
các đnh danh (vd sum, i, j)ị
các t khóa (vd int, if hay while)ừ
các toán t (vd “+” hay “ ”, “<=”)∗ử
các ký hi u phân tách (vd “{”, ‘}”, “;”)ệ
các h ng (nguyên, th c, logic, xâu)ằ ự
T p t t ph thu c vào ngôn ng l p trình: ch ng h n nh ậ ừ ố ụ ộ ữ ậ ẳ ạ ư
trong C toán t gán là = còn trong Pascal là :=ử
T ng t , trong ngôn ng t nhiên, các lo i t t : đng t , ươ ự ữ ự ạ ừ ố ộ ừ
danh t , tính t , v.v. T p các t ph thu c vào ngôn ng c ừ ừ ậ ừ ụ ộ ữ ụ
thể
15/11/15 4
Nguy n Ph ng Thái - Coltech - Compiler 2009ễ ươ
Từ vị (lexeme)
T v c a m t t t : chu i ký t t o thành t từ ị ủ ộ ừ ố ỗ ự ạ ừ ố
Ví d :ụ
15/11/15 5
Nguy n Ph ng Thái - Coltech - Compiler 2009ễ ươ