CHƯƠNG TRÌNH DỊCH - CHƯƠNG 2

Chia sẻ: Nguyễn Nhi | Ngày: | Loại File: PDF | Số trang:22

Thêm vào BST

Báo xấu

94
lượt xem 9
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

PHÂN TÍCH TỪ VỰNG - Mục đích - Nội dung - Otomat hữu hạn đơn định - Bộ phân tích từ vựng - Bảng danh biểu

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: CHƯƠNG TRÌNH DỊCH - CHƯƠNG 2

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG - Mục đích - Nội dung - Otomat hữu hạn đơn định - Bộ phân tích từ vựng - Bảng danh biểu Giáo trình Kiến trúc máy tính và Hệ 30 điều hành
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG 1. Mục đích - Chia cắt xâu vào (CT nguồn) thành dãy các từ tố. - Hai cách cài đặt • Sử dụng một lượt cho việc phân tích từ vựng dãy các token phân tích cú pháp. • Phân tích từ vựng dùng chung một lượt với phân tích cú pháp. Một lần chỉ phát Giáo trình Kiến trúc máy tính và Hệ hiện 1 tokein hành i là từ tố tiếp đến. đ ều gọ 31
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG 2. Nội dung - Đọc xâu vào từng ký tự một gom lại thành token đến khi gặp ký tự không thể kết hợp thành token. - Luôn luôn đọc trước một ký tự. - Loại bỏ các ký tự trống và chú thích. - Chuyển những thông tin của những từ tố (văn bản, mã phân loại) vừa phát hiện cho bộ phân tích cú pháp. Giáo trình Kiến trúc máy tính và Hệ 32 điều hành - Phát hiện lỗi.
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG 2. Nội dung - Sự giao tiếp giữa bộ phân tích từ vựng và bộ phân tích cú pháp Gửi token Bộ Bộ CT phân tích phân tích Yêu cầu token nguồn cú pháp từ vựng Bảng danh biểu Giáo trình Kiến trúc máy tính và Hệ 33 điều hành
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG 3. Otomat hữu hạn đơn định 3.1. Định nghĩa: M(Σ, Q, δ, q0, F) Σ: bộ chữ vào Q: tập hữu hạn các trạng thái q0 ∈ Q: trạng thái đầu F ⊆ Q: tập các trạng thái kết thúc δ: hàm chuyển trạng thái có dạng δ(q,a)=p Với q,p ∈ Q, a ∈ Σ δ(q,a)=p: nghĩến trúc máy trạng thái q, đọc a, chuyển Giáo trình Ki a là ở tính và Hệ 34 sang trạng thái p điều hành
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG 3. Otomat hữu hạn đơn định 3.2. Biểu diễn các hàm chuyển trạng thái Dùng bảng: sử dụng ma trận δ có: - Chỉ số hàng: trạng thái - Chỉ số cột: ký hiệu vào - Giá trị tại hàng q, cột a là trạng thái p, sao cho δ(q,a)=p Giáo trình Kiến trúc máy tính và Hệ 35 điều hành
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG 3. Otomat hữu hạn đơn định 3.2. Biểu diễn các hàm chuyển trạng thái Dùng bảng: Ví dụ: có hàm chuyển của một Otomat như sau: δ(1,a)=2, δ(2,b)=2, δ(2,c)=2 δ a b c 1 2 2 2 2 Giáo trình Kiến trúc máy tính và Hệ 36 điều hành
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG 3. Otomat hữu hạn đơn định 3.2. Biểu diễn các hàm chuyển trạng thái Hình vẽ: - mỗi trạng thái q∈Q được đặt trong các vòng tròn. - Trạng thái bắt đầu q0 có thêm dấu ‘>’ ở đầu. - Trạng thái kết thúc q∈F được đặt trong vòng tròn kép. - Các cung trình Kiếtừ trạtính và thái q sang trạng37thái p Giáo nối n trúc máy ng Hệ có mang các niều hành a∈Σ, có nghĩa δ(q,a)=p đ hãn
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG 3. Otomat hữu hạn đơn định 3.2. Biểu diễn các hàm chuyển trạng thái Hình vẽ: Ví dụ: có hàm chuyển của một Otomat như sau: δ(1,a)=2, δ(2,b)=2, δ(2,c)=2 b a c 2 1 Giáo trình Kiến trúc máy tính và Hệ 38 điều hành
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG 3. Otomat hữu hạn đơn định 3.2. Biểu diễn các hàm chuyển trạng thái Nhận xét: - Biểu diễn hàm chuyển trạng thái bằng hình vẽ có ưu điểm hơn. Trong hình vẽ ta xác định đầy đủ tất cả các thành phần của Otomat. - Biểu diễn bằng bảng xác định hàm chuyển trạng thái, tập các trạng thái, bộ chữ Giáo trìnhnhnưng không phân biệt đượ39 vào Kiế trúc máy tính và Hệ c trạng thái đbuắt đầu và trạng thái kết thúc. iề hành
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG 3. Otomat hữu hạn đơn định 3.3. Hoạt động của Otomat - Đọc các ký hiệu của xâu vào từ trái sang phải, bắt đầu từ trạng thái q0. - Mỗi bước đọc một ký hiệu thì chuyển sang trạng thái theo δ. Có thể đọc xong hay không đọc xong xâu vào. Giáo trình Kiến trúc máy tính và Hệ 40 điều hành
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG 3. Otomat hữu hạn đơn định 3.3. Hoạt động của Otomat - Đọc xong xâu vào đến một trạng thái p∈F thì xâu vào được đoán nhận (xâu đúng). - Đọc xong xâu vào mà rơi vào trạng thái p∉F thì xâu vào không được đoán nhận. - Không đọc xong xâu vào (do δ rơi vào điểm không xác định) thì xâu vào không được đoán nhận. Giáo trình Kiến trúc máy tính và Hệ 41 điều hành
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG 3. Otomat hữu hạn đơn định 3.4. Ví dụ: Xác định Otomat đoán nhận số nhị phân. M(Σ, Q, δ, q0, F) Σ: {0, 1, trắng} Q: {0, 1, 2} q0: 0 F : {2} δ: δ(0,trắng)=0, δ(0,0)=1, δ(0,1)=1, Giáoδ(1,0)=1, δ(1,1)=1, δ(1,trắng)=2 trình Kiến trúc máy tính và Hệ 42 điều hành
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG 3. Otomat hữu hạn đơn định 3.4. Ví dụ: Xác định Otomat đoán nhận số nhị phân 0 trắng 1 0|1 trắng 1 2 0 Giáo trình Kiến trúc máy tính và Hệ 43 điều hành
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG 4.Lập bộ phân tích từ vựng Ngoài các hình qui ước của Otomat thông thường lại có thêm: * Trạng thái kết thúc và q trả lui ký tự vừa đọc Giáo trình Kiến trúc máy tính và Hệ 44 điều hành
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG 4. Lập bộ phân tích từ vựng 4.1. Phương pháp mô phỏng - Mỗi trạng thái: tương ứng với một đoạn chương trình - Nối tiếp các trạng thái: nối tiếp 2 đoạn chương trình tương ứng - Lệnh rẽ nhánh Giáo trình Kiến trúc máy tính và Hệ Lệnh lặp - 45 điều hành
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG 4.Lập bộ phân tích từ vựng 4.1. Phương pháp mô phỏng Max=10; {độ dài tối đa của 1 danh biểu} Procedure Tuvung(var ma:Loaituto;var x:xau); Type Var i:0..max; Loaikytu=(conso,cham, Ttu, trang, Ccai); Begin Loaituto=(nguyen,thuc,Toantu, For i:=1 to max do x[i]:=’’; Danhbieu); I:=0; Xau=Array[1..max] of char ; While loaikytu(kytutiep)=trang do Var Kytutiep:char; Dockytu(kytutiep); Procedure Dockytu(var c:char); Case loaikytu(kytutiep) of …{Đọc ký tự tiếp, ký tự này luôn luôn được Conso: Begin đọc trước} Repeat I:=i+1; Function LoaiKT(c:char):Loaikytu; x[i]:=kytutiep; …{Cho biết loại của ký tự c} Dockytu(kytutiep); Procedure Baoloi; Giáo trình Kiến trúc máy tính và Hệ Until Loaikytu(kytutiep)conso; 46 …{Cho một thông báo lỗi} điều hành Ma:=nguyen;
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG 4.Lập bộ phân tích từ vựng 4.1. Phương pháp mô phỏng If loaikytu(kytutiep)=cham then Ttu: begin I:=i+1; x[i]:=kytutiep; ma:=toantu; Dockytu(kytutiep); Begin Repeat I:=i+1; x[i]:=kytutiep; end; Dockytu(kytutiep); Ccai: begin Until loaikytu(kytutiep)Conso Repeat Ma:=thuc; If i
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG 4.Lập bộ phân tích từ vựng 4.1. Phương pháp điều khiển bằng bảng Var bangchuyen: array[1..6,loaikytu] of 0..6; Mảng này được nạp dữ liệu như sau: trang Conso Cham Ttu C cai 1 1 2 4 5 6 2 0 2 3 0 0 3 0 3 0 0 0 4 0 3 0 0 0 5 0 0 0 0 0 Giáo trình Kiến trúc máy tính và Hệ 48 6 0 điều hành 0 0 0 6
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG 4. Lập bộ phân tích từ vựng 4.1. Phương pháp điều khiển bằng bảng Procedure Tuvung(var ma:loaituto; var x:xau); Case trangthai of Begin 2: ma:=nguyen; trangthai:=1; 3: ma:=thuc; trangthaitiep:=bangchuyen[trangthai, 4: baoloi; loaikytu(kytutiep)]; 5:ma:=toantu; i:=0; 6: ma:=danhbieu; Repeat End;{case} i:=i+1; End; {Tuvung} x[i]:=kytutiep; trangthai:=trangthaitiep; Dockytu(kytutiep); trangthaitiep:= bangchuyen[trangthai, Giáo trình Kiến trúc máy tính và Hệ loaikytu(kytutiep)]; 49 điều hành Until trangthaitiep=0;