ươ
ễ 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 Bi u th c ki u ể ứ H th ng ki u ể Lu t ng nghĩa ki m tra ki u ể
ắ
Giới thiệu Mô đun phân tích ng nghĩa: ki m tra tính đúng đ n v ề
ươ ể ng trình ngu n ữ m t ng nghĩa c a ch
ể
ả
ộ
ộ
ươ
ặ ệ ủ ượ ạ ồ c chia làm hai lo i:
ng trình đích
ể ể ch y)ạ
ữ Vi c ki m tra đ ể ki m tra tĩnh ki m tra đ ng (ki m tra đ ng x y ra lúc ch
Trong bài gi ng này ta ch xét m t s d ng c a ki m tra
ộ ố ạ ủ ể ả ỉ
tĩnh
ắ ủ
ể
ể
ể
ề
ể
ạ
Giới thiệu (tiếp) ki m tra ki u: ki m tra v tính đúng đ n c a các ki u toán h ng
ứ
ể trong bi u th c.
ể
ể
ể
ấ
ợ
ki m tra dòng đi u khi n: m t s đi u khi n ph i có c u trúc h p ộ ố ề
ữ
ộ
ả ả ằ
ụ ư ệ
break trong ngôn ng C ph i n m trong m t
ề lý, ví d nh l nh vòng l p.ặ
ấ
ượ ị
ộ ầ
ụ
ỉ
ấ
ả ượ
ầ ử
ướ
ki m tra tính nh t quán: có nh ng ng c nh mà trong đó m t đ i ộ ố ữ ả ữ ộ c đ nh nghĩa ch đúng m t l n. Ví d , trong Pascal, m t ả c khai báo duy nh t, các nhãn trong l nh case ph i ượ ặ c l p
ệ ng không đ
ể trong ki u vô h
ể ượ ng đ t tên ph i đ khác nhau, và các ph n t i.ạ l ể
ả
ấ
ộ
ki m tra quan h tên: Đôi khi m t tên ph i xu t hi n t
ộ
ng trình con có m t tên mà
ệ ở ầ
ụ ả
ấ
ươ
ươ ố ủ
ệ lên. Ví d , trong Assembly, m t ch chúng ph i xu t hi n
ở ầ ệ ừ hai l n tr ộ ng trình con này.
đ u và cu i c a ch
ữ ượ ị ở ể
Biểu thức kiểu Ki u c a m t c u trúc ngôn ng đ
c bi u th b i
ự
ừ
c xây d ng t
ể ơ ả các ki u c b n theo
ử
ể
ượ nào đó
ộ ấ ể ủ ể ứ ể “bi u th c ki u” M t bi u th c ki u có th là: ứ ể ộ ể m t ki u c b n ể ơ ả ộ ki u h p thành: đ ợ ể ộ ố m t s toán t
ệ ặ ể ả ề t dùng đ tr v
ộ ấ
ệ ặ ấ ị
ể t khác, bi u th các c u ư ệ
Kiểu cơ bản boolean, char, interger, real type_error : m t ki u c b n đ c bi ể ơ ả ộ ể ị ỗ i ki u m t c u trúc b l void: m t ki u c b n đ c bi ể ơ ả ể ộ ị ầ trúc không c n xác đ nh ki u nh câu l nh
ể
ộ ả ể
Kiểu hợp thành M ng.ả ứ ể
ộ ố ớ array(I,T) là m t ộ ầ ử ể T và ki u
ụ
ữ
ậ
ị ể
ủ ứ ể ể
ể N u ế T là m t bi u th c ki u thì ứ bi u th c ki u đ i v i m t m ng các ph n t ỉ ố I là t p các ch s . Ví d , trong ngôn ng Pascal khai báo: var A: array[1..10] of interger; ể ủ ẽ s xác đ nh ki u c a A là ộ ể ứ ể ề ế T1 ủ T1xT2
ể ứ ể ể ể ộ
array(1..10,interger) Tích c a bi u th c ki u là m t bi u th c ki u. N u ứ và T2 là các ki u bi u th c ki u thì tích Đ các c a là m t bi u th c ki u.
ộ ả ể ể
Kiểu hợp thành (tiếp) B n ghi ả ượ
ườ ứ . Ki u c a m t b n ghi chính là bi u th c ki u ợ ủ ng h p c a nó. ể ủ các ki u c a các tr đ
type row=record
address: interger; lexeme: array[1..15] of char;
ộ
ươ ứ
ế ủ
ứ
ể
ể
ớ
ộ
end; var table: array[1..101] of row; nh v y m t bi n c a row thì t
ng ng v i m t bi u th c ki u
ư ậ là: record((address x interger) x (lexeme x array(1..15,char)))
ể ủ ừ ự c xây d ng t Ví d (ngôn ng Pascal): ữ ụ
ứ ộ
Kiểu hợp thành (tiếp) Con trỏ. Gi ể ị
ể
Ví d (ngôn ng Pascal):
pointer(row)
ể ả ử T là m t bi u th c ki u thì pointer(T) là s ể ể ứ ể ị ộ m t bi u th m t bi u th c ki u xác đ nh ki u cho con ể T. ộ ố ượ tr c a m t đ i t ng ki u ữ
ộ ỏ ủ ụ var p: ^row ể thì p có ki u là
ộ ầ ử ủ ạ ừ ộ
c a m t ộ ể
các ph n t ể ộ ể
ư ậ ẽ ượ ệ ể ộ
Kiểu hợp thành (tiếp) Hàm. M t hàm là m t ánh x t ộ ộ ậ ư ậ ậ t p vào m t t p khác. Nh v y có th coi ki u m t hàm ạ ừ ộ ạ ể ề m t ki u mi n D vào m t ki u ph m vi R. là ánh x t ể ứ c ký hi u Bi u th c ki u cho m t hàm nh v y s đ là D>R. ụ
Ví d (ngôn ng Pascal), m t hàm khai báo nh sau:
ể
ề
ư ộ
interger x interger và ki u ph m vi là ị ể
ư ậ
ạ ể
ể ứ
ể
pointer(interger). Và nh v y bi u th c ki u xác đ nh ki u cho hàm đó là:
interger x interger > pointer(interger)
ữ function f(a,b:interger): ^interger; có ki u mi n là
ể ị
ươ
các ph n trong ch ể ậ ể ồ ụ ự ậ
Hệ thống kiểu H th ng ki u: là m t t p các lu t đ xác đ nh ki u cho ộ ậ ể ng trình ngu n B ki m tra ki u: làm nhi m v th c thi các lu t trong ệ
K thu t: cú pháp đi u khi n và l
ệ ố ầ ộ ể ể ệ ố h th ng ki u ậ ỹ ề ể ượ ồ ị c đ d ch
ộ ố ụ
Một số luật ngữ nghĩa kiểm tra kiểu Ta s xét m t s ví d ẽ Chú ý:
ể
ể
ị
đ i v i câu l nh không có giá tr , ta có th gán cho nó ki u
ệ
ệ
ố ớ ơ ở ặ c s đ c bi n u có l ế
c phát hi n trong câu l nh thì ta
ệ ệ void t ỗ ề ể ượ i v ki u đ ị ể
type_error
gán cho nó giá tr ki u là
Phần khai báo của chương trình D > id : T T > interger T > char T > ^ T T > array [num] of T
ậ
ậ Lu t cú pháp D > id : T
T > char T > interger T > ^T1 T > array [num] of T1
ữ Lu t ng nghĩa AddType(id.entry,T.type); D.type := void T.type := char T.type := interger T.type := pointer(T1.type) T.type := array(num.val,T1.type)
Biểu thức S > id := E E > E + E E > E mod E E > E1 [ E2 ] E > num E > id
ậ
ậ
ữ Lu t ng nghĩa
Lu t cú pháp S > id := E
E > E1 + E2
E > num E > id E > E1 mod E2
E > E1 [ E2 ]
S.type := if id.type=E.type then void else type_error ; AddType(id.entry,E.type) E.type:= if E1.type=interger and E2.type=interger then interger else if E1.type=interger and E2.type=real then real else if E1.type=real and E2.type=interger then real else if E1.type=real and E2.type=real then real else type_error E.type := interger E.type := GetType(id. entry) E.type := if E1.type=interger and E2.type=interger then interger else type_error E.type := if E2.type=interger and E1.type=array(s,t) then t else type_error
Câu lệnh S > if E then S S > while E do S S > S1 ; S2
ậ
ậ
Lu t cú pháp S > if E then S1
S > while E do S1
S > S1 ; S2
ữ Lu t ng nghĩa S.type := if E.type=boolean then S1.type else type_error S.type := if E.type=boolean then S1.type else type_error S.type := if S1.type=void and S2.type=void then void else type_error
Hàm
ể ệ ờ ọ
ậ
i g i hàm:
lu t cú pháp sau đây th hi n l E > E1 ( E2 ) Ví d :ụ
function f(a,b:char):^interger; begin . . .
end; var p:^interger; q:^char; x,y:interger; begin . . . p:=f(x,y);// đúng q:=f(x,y);// sai end;
ậ
ậ
Lu t cú pháp
ữ Lu t ng nghĩa
E > E1 ( E2 )
E.type := if E2.type=s and E1.type=s>t then t else type_error
