Page 1
21/1/2010 Nội dung Bài 10 Những vấn đề ngữ nghĩa Kiểm tra kiểu (Type checking) Phân tích ngPhân tích ngữữ nghnghĩĩaa
HHệệ ththốống king kiểểuu trong ngôn ngtrong ngôn ngữữ llậậpp trìnhtrình
Đặc tả một bộ kiểm tra kiểu
Chuyển đổi kiểu Bảng ký hiệu
Luật về phạm vi ảnh hưởng của biến
Các sơ đồ dịch để xây dựng bảng ký hiệu Phân tích ngữ nghĩa Khái niệm kiểm tra kiểu Tìm ra các lỗi sau giai đoạn phân tích cú pháp Kiểm tra xem chương trình có tuân theo
Kiểm tra sự tương ứng về kiểu các luật về kiểu của ngôn ngữ không
Kiểm tra sự tương ứng giữa việc sử dụng hàm, biến Trình biên dTrình biên dịịch quch quảản lý thông tin vn lý thông tin vềề kikiểểuu vớới kh i bái khai báo củủa chúhúng
Xác định phạm vi ảnh hưởng của các biến trong Việc kiểm tra kiểu được thực hiện bởi bộ chương trình kiểm tra kiểu (type checker), một bộ phận Phân tích ngữ nghĩa thường sử dụng cây cú của trình biên dịch pháp goupee.com fb.com/groups/goupee 1
Page 2
21/1/2010 Ví dụ về kiểm tra kiểu Kiểm tra kiểu Có hai phương pháp tĩnh và động Toán tử % của C chỉ thực hiện khi các Phương pháp áp dụng trong thời gian dịch là toán hạng là số nguyên tĩnh Trong các ngôn ngữ như C hay Pascal, kiểm tra ChChỉỉ có mcó mảảng mng mớới có chi có chỉỉ ssốố và kivà kiểểu cu củủa cha chỉỉ kikiểểu là tu là tĩĩnh vành và đượđược dùngc dùng đểđể kikiểểm tra tínhm tra tính đđúngúng số phải nguyên đắn của chương trình trước khi nó đươc thực hiện Một hàm phải có một số lượng tham số Kiểm tra kiểu tĩnh cũng được sử dụng khi xác nhất định và các tham số phải đúng kiểu định dung lượng bộ nhớ cần thiết cho các biến Bộ kiểm tra kiểu được xây dựng dựa trên
Các biểu thức kiểu của ngôn ngữ
Bộ luật để định kiểu cho các cấu trúc Biểu thức kiểu (Type Expression) Cấu trúc kiểu Biểu diễn kiểu của một cấu trúc ngôn ngữ (a)Mảng (Array).Nếu T là biểu thưc kiểu thì array(I,T) là biểu thức kiểu biểu Một biểu thức kiểu là một kiểu dữ liệu chuẩn diễn một mảng với các phần tử kiểu T và chỉ số trong miền I hoặc được xây dựng từ các kiểu dữ liệu khác Ví dụ : array [10] of integer có kiểu array(1..10,int); bởi cấu trúc kiểu (Type Constructor) (b) Tích Descarter N(b) Tích Descarter Nếếu Tu T11và Tvà T22 là các bilà các biểểu thu thứứcc kikiểểu thì tích Descarter T1u thì tích Descarter T1×× T2T2 là biểu thức kiểu (c) Bản ghi (Record) Tương tự như tích Descarter nhưng chứa các tên khác 1.Kiểu dữ liệu chuẩn (int, real, boolean, char) là biểu nhau cho các kiểu khác nhau, thức kiểu Ví dụ struct 2.Biểu thức kiểu có thể liên hệ với một tên. Tên kiểu là { biểu thức double r; int i; 3. Cấu trúc kiểu được ứng dụng vào các biểu thức kiểu } tạo ra biểu thức kiểu Có kiểu ((r x int) x (i x char)) goupee.com fb.com/groups/goupee 2
Page 3
21/1/2010 Cấu trúc kiểu (tiếp) Hệ thống kiểu (Type System) (d) Con trỏ: Nêu T là biểu thức kiểu thì pointer(T) Tập các luật để xây dựng các biểu thức là biểu thức kiểu (e) Hàm Nếu D là miền xác định và R là miền giá kiểu trong những phần khác nhau của trị của hàm thì kiểu của nó được biểu diễn là chương trình biểu_ thức : D : R. Được định nghĩa thông qua định nghĩa tựa cú pháp Ví dụ hàm của C Bộ kiểm tra kiểu thực hiện một hệ thống int f(char a, b) kiểu Có kiểu: char × char : int. Ngôn ngữ định kiểu mạnh: Chương trình dịch kiểm soát được hết các lỗi về kiểu Đặc tả một bộ kiểm tra kiểu Thuộc tính Ngôn ngữ đơn giản với mỗi tên được liên kết với một kiểu Thuộc tính là khái niệm trừu tượng biểu diễn một đại lượng bất kỳ , chẳng hạn một số, một xâu, một vị trí VVăăn phn phạạm thum thuộộc tínhc tính đểđể khaikhai báo bibáo biểểuu trongg bộộ nhớ . . . . thức Thuộc tính được gọi là tổng hợp nếu giá trị của nó tại P → D;E một nút trong cây được xác định từ giá trị của các nút D → D;D | id : T con của nó. T → char | int | array[num] of T | ↑T E → literal | num | id | E mod E | E[E] | E↑ Thuộc tính kế thừa là thuộc tính tại một nút mà giá trị của nó được định nghĩa dựa vào giá trị nút cha và/hoặc các nút anh em của nó. goupee.com fb.com/groups/goupee 3
Page 4
21/1/2010 Định nghĩa tựa cú pháp (syntax directed definition) Ví dụ Định nghĩa tựa cú pháp là dạng tổng quát của văn phạm phi ngữ Sản xuất Quy tắc ngữ nghĩa cảnh để đặc tả cú pháp của ngôn ngữ vào. Mỗi ký hiệu của văn phạm liên kết với một tập thuộc tính , L → E return Print (E.val) Mỗi sản xuất A → α liên hệ với một tập các quy tắc ngữ nghĩa để E → E1+T E.val = E1.val + T.val tính giá trị thuộc tính liên kết với những ký hiệu xuất hiện trong sản xuất. Tập các quy tắc ngữ nghĩa có dạng E → T E.val = T.val b= f (c1, c2, . . . . ., cn) T → T1 * F T.val = T1.val * F.val f là một hàm và b thoả một trong hai yêu cầu sau: T → F T.val = F.val F → (E) F.val = E.val
b là một thuộc tính tổng hợp của A và c1 , . . . , cn là các thuộc tính liên kết với các ký hiệu trong vế phải sản xuất A → α F → digit F.val = digit.Lexval • Các ký hiệu E, T, F liên hệ với thuộc tính tổng hợp val
b là một thuộc tính thừa kế một trong những ký hiệu xuất hiện •Từ tố digit có thuộc tính tổng hợp lexval ( Được bộ phân trong α, và c1 , . . . , cn là thuộc tính của các ký hiệu trong vế phải sản xuất A → α tích từ vựng đưa ra ) Cây phân tích cú pháp có chú giải Ví dụ Cây cú pháp có chỉ ra giá ttrịị cáác ththuộộc tí htính t itại mỗỗii nút được gọi là cây cú pháp có chú giải. goupee.com fb.com/groups/goupee 4
Page 5
21/1/2010 Bộ kiểm tra kiểu của định danh Bộ kiểm tra kiểu của biểu thức Bộ kiểm tra kiểu của lệnh Bộ kiểm tra kiểu của hàm goupee.com fb.com/groups/goupee 5
Page 6
21/1/2010 Hàm kiểm tra biểu thức kiểu Chuyển đổi kiểu tương đương Kiểu của x+i với function sequiv(s, t): boolean; begin x kiểu real if s và t là cùng kiểu dữ liệu chuẩn then return true; i kiểu int else if s = array(y(s1, s2)) and t = array(y(t1, t2)) then return sequiv(s1, t1) and sequiv(s2, t2) Khi dịch sang lệnh máy, phép cộng với else if s = s1 x s2 and t = t1 x t2) then return sequiv(s1, t1) and sequiv(s2, t2) kiểu real và kiểu int có mã lệnh khác nhau else if s = pointer(s1) and t = pointer(t1) then return sequiv(s1, t1) Tùy ngôn ngữ và bộ luật chuyển đổi sẽ else if s = s1→ s2 and t = t1→ t2 then return sequiv(s1, t1) and sequiv(s2, t2) quy đổi các toán hạng về một trong hai else return false; kiểu end; Áp đặt kiểu trong biểu thức Bảng ký hiệu Lưu trữ thông tin về tên, kiểu, phạm vi và kích cỡ bộ nhớ cần phân phối Bổ sungg dữ liệu và tìm kiếm nhanh chóngg Thích hợp với các cấu trúc dữ liệu động
Thường dùng danh sách tuyến tính và bảng băm
Mỗi lối vào có dạng bản ghi với một trường cho mỗi loại thông tin goupee.com fb.com/groups/goupee 6
Page 7
21/1/2010 Lưu trữ tên Bảng ký hiệu và các luật về phạm vi sử dụng Khối trong ngôn ngữ lập trình là tập các cấu trúc ngôn ngữ có chứa khai báo Một ngôn ngữ là có cấu trúc khối nếu
CáCác khkhốốii đđược llồồng bêbên ttrong nhhữững khkhốối khái khác
Phạm vi của khai báo trong mỗi khối là chính khối đó và các khối chứa trong nó Luật lồng nhau gần nhất
Cho nhiều khai báo của cùng một tên. Khai báo có hiệu lực là khai báo nằm trong khối gần nhất Giải pháp nhiều bảng ký hiệu Các luật về phạm vi lồng nhau Các bảng cần được kết nối từ phạm vi trong ra phạm vi ngoài và ngược lại Toán tử insert vào bảng ký hiệu không được ghi đè những khai báo trước Toán tử lookup vào bảng ký hiệu luôn luôn tham chichiếếu luu luậật pht phạạm vi gm vi gầần nhn nhấấtt Toán tử delete chỉ được xóa khai báo gần nhất Bảng ký hiệu hoạt động như một stack goupee.com fb.com/groups/goupee 7
Page 8
21/1/2010 Xây dựng trong giai đoạn phân tích Tính địa chỉ biến toàn cục offset cú pháp Chỉ có thể bắt đầu nhập thông tin vào bảng ký hiệu từ khi phân tích từ vựng nếu ngôn ngữ lập trình không cho khai báo tên trùng nhau. Nếếu cho phép các phạm vi, bộ phân tích từ vựng chỉ trả ra tên của định danh cùng với token
Định danh được thêm vào bảng ký hiệu khi vai trò cú pháp của định danh được phát hiện Địa chỉ liên quan Biến toàn cục offset lưu vết của địa chỉ còn rỗi tiếp theo Địa chỉ liên quan: Thông tin về phân phối Trước khai báo đầu tiên, offset được gán bộ nhớ logic giá trị 0. Mỗỗi khi tìm thấấy một định danh, offset được tăng lên goupee.com fb.com/groups/goupee 8
Page 9
21/1/2010 Lưu trữ thông tin về các phạm vi Xử lý các khai báo trong thủ tục lồng nhau lồng nhau Xét các thủ tục lồng nhau: Khi một thủ tục nằm trong thủ tục khác được gọi, các khai báo của thủ tục bên ngoài tạm dừng hoạt động Dùng stack đểể lưu trữ dấấu vếết của các thủ tục lồng nhau Tạo bảng ký hiệu mới cho mỗi thủ tục
Khi thêm một định danh mới vào bảng ký hiệu, cần chỉ rõ bảng ký hiệu cần thêm Lưu trữ dấu vết của các phạm vi mktable(previous) Tạo một bảng ký hiệu mới và trả lại con trỏ của bảng ký hiệu đó. Tham số previous là con trỏ tới thủ tục chứa nó. Stack tblptr chứa con trỏ tới các bảng ký hiệu và các thủ tục chứa nó. Stack offset chứa dấu vết các địịa chỉ tươngg ứngg ở mức lồồng nhau nào đó enter(table,name,type,offset) tạo một lối vào mới cho định danh name trong bảng ký hiệu mà table trỏ tới , đồng thồi chỉ ra các thuộc tính type và offset. addwidth(table,width) ghi giá trị width của mỗi lối vào trong table vào header của bảng ký hiệu enterproc(table,name,newtable) Tạo một lối vào mới cho thủ tục name trong bảng ký hiệu chỉ bởi table. Tham số newtable chỉ tới bảng ký hiệu cho thủ tục name. goupee.com fb.com/groups/goupee 9
Showing the first 9 pages. Download the document to see it all.
Comments (0)
No comments yet. Be the first!