Tin học: STGT CT dịch trong VT

Giáo trình Kiến trúc máy tính và Hệ điều hành
1
CHƯƠNG TRÌNH DỊCH
Giáo trình Kiến trúc máy tính và Hệ điều hành
2
Mục tiêu giáo trình
Cung cấp những kiến thức cơ bản về chương trình dịch
Cung cấp các phương pháp phân tích từ vựng, phân tích cú pháp.
Cơ sở cho việc tìm hiểu các ngôn ngữ lập trình.
Rèn luyện kỹ năng lập trình cho sinh viên
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Giới thiệu
Giáo trình Kiến trúc máy tính và Hệ điều hành
3
Nội dung giáo trình
CHƯƠNG 1. NHẬP MÔN CHƯƠNG TRÌNH DỊCH
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Giới thiệu
Giáo trình Kiến trúc máy tính và Hệ điều hành
4

CHƯƠNG 1. NHẬP MÔN CHƯƠNG TRÌNH DỊCH

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Các khái niệm cơ bản
Đặc trưng của ngôn ngữ lập trình (NNLT) bậc cao
Các qui tắc từ vựng và cú pháp
Các chức năng của một trình biên dịch
Giáo trình Kiến trúc máy tính và Hệ điều hành
5

CHƯƠNG 1. NHẬP MÔN CHƯƠNG TRÌNH DỊCH

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Các khái niệm cơ bản
1.1. Sự phát triển của ngôn ngữ lập trình
1.2. Khái niệm chương trình dịch
1.3. Phân loại chương trình dịch
1.4. Các ứng dụng khác của kỹ thuật dịch
Giáo trình Kiến trúc máy tính và Hệ điều hành
6

CHƯƠNG 1. NHẬP MÔN CHƯƠNG TRÌNH DỊCH

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Các khái niệm cơ bản
1.1. Sự phát triển của ngôn ngữ lập trình
Giáo trình Kiến trúc máy tính và Hệ điều hành
7

CHƯƠNG 1. NHẬP MÔN CHƯƠNG TRÌNH DỊCH

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Các khái niệm cơ bản
1.2. Khái niệm chương trình dịch
Chương trình dịch là chương trình dùng để dịch một chương trình (CT nguồn) viết trên NNLT nào đó (NN nguồn) sang một chương trình tương đương (CT đích) trên một NN khác (NN đích)
Giáo trình Kiến trúc máy tính và Hệ điều hành
8

CHƯƠNG 1. NHẬP MÔN CHƯƠNG TRÌNH DỊCH

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Các khái niệm cơ bản
1.3. Phân loại chương trình dịch
Trình biên dịch
Giáo trình Kiến trúc máy tính và Hệ điều hành
9

CHƯƠNG 1. NHẬP MÔN CHƯƠNG TRÌNH DỊCH

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Các khái niệm cơ bản
1.3. Phân loại chương trình dịch
Trình thông dịch
Giáo trình Kiến trúc máy tính và Hệ điều hành
10

CHƯƠNG 1. NHẬP MÔN CHƯƠNG TRÌNH DỊCH

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Các khái niệm cơ bản
1.4. Các ứng dụng khác của kỹ thuật dịch
Trong các hệ thống: phần giao tiếp giữa người và máy thông qua các câu lệnh.
Hệ thống xử lý NN tự nhiên: dịch thuật, tóm tắt văn bản.
Giáo trình Kiến trúc máy tính và Hệ điều hành
11

CHƯƠNG 1. NHẬP MÔN CHƯƠNG TRÌNH DỊCH

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Đặc trưng của NNLT bậc cao
Tính tự nhiên
Tính thích nghi
Tính hiệu quả
Tính đa dạng
Giáo trình Kiến trúc máy tính và Hệ điều hành
12

CHƯƠNG 1. NHẬP MÔN CHƯƠNG TRÌNH DỊCH

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Các qui tắc từ vựng và cú pháp
3.1. Bản chữ cái
Gồm những ký hiệu được phép sử dụng để viết chương trình
Số lượng, ý nghĩa sử dụng của các ký tự trong bản chữ cái của các NN là khác nhau.
Nhìn chung bản chữ cái của các NNLT:
+ 52 chữ cái: A Z, az
+ 10 chữ số: 0 9
+ Các ký hiệu khác:*, /, +, -, …
Giáo trình Kiến trúc máy tính và Hệ điều hành
13

CHƯƠNG 1. NHẬP MÔN CHƯƠNG TRÌNH DỊCH

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Các qui tắc từ vựng và cú pháp
3.2. Từ tố (Token)
Từ tố là đơn vị nhỏ nhất có nghĩa
Từ tố được xây dựng từ bản chữ cái
Ví dụ: hằng, biến, từ khoá, các phép toán,…
Giáo trình Kiến trúc máy tính và Hệ điều hành
14

CHƯƠNG 1. NHẬP MÔN CHƯƠNG TRÌNH DỊCH

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Các qui tắc từ vựng và cú pháp
3.3. Phạm trù cú pháp
Phạm trù cú pháp là một dãy từ tố kết hợp theo một qui luật nào đó
Các cách biểu diễn cú pháp thông thường
+ BNF(Backus Naus Form):
::=:=

Giáo trình Kiến trúc máy tính và Hệ điều hành
15

CHƯƠNG 1. NHẬP MÔN CHƯƠNG TRÌNH DỊCH

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Các qui tắc từ vựng và cú pháp
3.3. Phạm trù cú pháp
+ Biểu đồ cú pháp:
Chương trìnhProgram Danh biểu Khối
Khối - var…
- procedure  Danh biểu Khối
- begin lệnh  end .
Mục tiêu của phạm trù cú pháp là việc định nghĩa được khái niệm chương trình đến mức độ tự có
Giáo trình Kiến trúc máy tính và Hệ điều hành
16

CHƯƠNG 1. NHẬP MÔN CHƯƠNG TRÌNH DỊCH

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Các qui tắc từ vựng và cú pháp
3.4. Các qui tắc từ vựng thông dụng
Cách sử dụng khoảng trống(dấu trắng), dấu tab(‘ ’), dấu sang dòng(‘ ’)
Đối với liên kết tự do, có thể sử dụng nhiều khoảng trống thay vì một khoảng trống.
Giáo trình Kiến trúc máy tính và Hệ điều hành
17

CHƯƠNG 1. NHẬP MÔN CHƯƠNG TRÌNH DỊCH

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Các qui tắc từ vựng và cú pháp
3.4. Các qui tắc từ vựng thông dụng
Một khoảng trống là bắt buộc giữa các từ tố: từ khoá và tên,…
Ví dụ: program tenct;
Khoảng trống không bắt buộc: số và các phép toán, tên biến và các phép toán
Ví dụ: x:=x+3*3;
Cách sử dụng chú thích và xâu ký tự
Giáo trình Kiến trúc máy tính và Hệ điều hành
18

CHƯƠNG 1. NHẬP MÔN CHƯƠNG TRÌNH DỊCH

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Các chức năng của một chương trình biên dịch
Phân tích từ vựng
Phân tích cú pháp
Phân tích ngữ nghĩa
Xử lý lỗi
Sinh mã trung gian
Tối ưu mã trung gian
Sinh mã đối tượng
Giáo trình Kiến trúc máy tính và Hệ điều hành
19

CHƯƠNG 1. NHẬP MÔN CHƯƠNG TRÌNH DỊCH

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Các chức năng của một chương trình biên dịch
4.1. Phân tích từ vựng
CT nguồn là một dãy các ký tự.
Phân tích từ vựng là phân tích CT nguồn thành các từ tố (Token).
Các Token này sẽ là dữ liệu đầu vào của phân tích cú pháp.
Giáo trình Kiến trúc máy tính và Hệ điều hành
20

CHƯƠNG 1. NHẬP MÔN CHƯƠNG TRÌNH DỊCH

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Các chức năng của một chương trình biên dịch
4.2. Phân tích cú pháp
Đầu vào sẽ là dãy các Token nối nhau bằng một qui tắc nào đó.
Phân tích xem các Token có tuân theo qui tắc cú pháp của ngôn ngữ không
Giáo trình Kiến trúc máy tính và Hệ điều hành
21

CHƯƠNG 1. NHẬP MÔN CHƯƠNG TRÌNH DỊCH

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Các chức năng của một chương trình biên dịch
4.3. Phân tích ngữ nghĩa
Kiểm tra tính hợp lệ của các phép toán và các phép xử lý
Ví dụ:
Biến phải khai báo trước khi sử dụng (Pascal)
Kiểm tra tính tương thích kiểu dữ liệu của biến và biểu thức
Giáo trình Kiến trúc máy tính và Hệ điều hành
22

CHƯƠNG 1. NHẬP MÔN CHƯƠNG TRÌNH DỊCH

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Các chức năng của một chương trình biên dịch
4.4. Xử lý lỗi
CT nguồn vẫn có thể xảy ra lỗi.
Phần xử lý lỗi sẽ thông báo lỗi cho NSD
Lỗi ở phần nào báo ở phần đó.
Giáo trình Kiến trúc máy tính và Hệ điều hành
23

CHƯƠNG 1. NHẬP MÔN CHƯƠNG TRÌNH DỊCH

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Các chức năng của một chương trình biên dịch
4.4. Xử lý lỗi
Có các loại lỗi:
Lỗi từ vựng (trong Pascal sử dụng biến mà chưa khai báo)
Lỗi cú pháp ((a+5; lỗi thiếu dấu ‘)’ )
Lỗi ngữ nghĩa (x=3.5; nhưng khai báo int x)
Lỗi thực hiện (phép chia 0)
Giáo trình Kiến trúc máy tính và Hệ điều hành
24

CHƯƠNG 1. NHẬP MÔN CHƯƠNG TRÌNH DỊCH

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Các chức năng của một chương trình biên dịch
4.5. sinh mã trung gian
Sau giai đoạn phân tích ngữ nghĩa
Mã trung gian là một dạng trung gian của CT nguồn có 2 đặc điểm:
Dễ được sinh ra
Dễ dịch sang ngôn ngữ đích
Giáo trình Kiến trúc máy tính và Hệ điều hành
25

CHƯƠNG 1. NHẬP MÔN CHƯƠNG TRÌNH DỊCH

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Các chức năng của một chương trình biên dịch
4.6. Tối ưu mã trung gian
Bỏ bớt các lệnh thừa.
Cải tiến lại mã trung gian để khi sinh mã đối tượng thì thời gian thực thi mã đối tượng sẽ ngắn hơn


Giáo trình Kiến trúc máy tính và Hệ điều hành
26

CHƯƠNG 1. NHẬP MÔN CHƯƠNG TRÌNH DỊCH

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Các chức năng của một chương trình biên dịch
4.7. Sinh mã đối tượng
Giai đoạn cuối của trình biên dịch.
Mã đối tượng có thể là mã máy, hợp ngữ hay một ngôn ngữ khác ngôn ngữ nguồn.
Các pha (giai đoạn) có thể thực hiện song hành
Một vài pha có thể ghép lại thành lượt (chuyến)
Một lượt sẽ đọc toàn bộ CT nguồn hay một dạng trung gian của CT nguồn, sau đó ghi kết quả để lượt sau đọc và xử lý tiếp.
Giáo trình Kiến trúc máy tính và Hệ điều hành
27

CHƯƠNG 1. NHẬP MÔN CHƯƠNG TRÌNH DỊCH

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Giáo trình Kiến trúc máy tính và Hệ điều hành
28
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴ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ệ điều hành
29
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
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 hiện 1 token gọi là từ tố tiếp đến.
Giáo trình Kiến trúc máy tính và Hệ điều hành
30
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
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.
Phát hiện lỗi.
Giáo trình Kiến trúc máy tính và Hệ điều hành
31
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Giáo trình Kiến trúc máy tính và Hệ điều hành
32
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
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ĩa là ở trạng thái q, đọc a, chuyển sang trạng thái p
Giáo trình Kiến trúc máy tính và Hệ điều hành
33
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
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ệ điều hành
34
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
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
Giáo trình Kiến trúc máy tính và Hệ điều hành
35
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
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 nối từ trạng thái q sang trạng thái p có mang các nhãn aΣ, có nghĩa δ(q,a)=p
Giáo trình Kiến trúc máy tính và Hệ điều hành
36
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Giáo trình Kiến trúc máy tính và Hệ điều hành
37
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
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ữ vào nhưng không phân biệt được trạng thái bắt đầu và trạng thái kết thúc.
Giáo trình Kiến trúc máy tính và Hệ điều hành
38
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
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ệ điều hành
39
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
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ệ điều hành
40
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
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, δ(1,0)=1, δ(1,1)=1, δ(1,trắng)=2
Giáo trình Kiến trúc máy tính và Hệ điều hành
41
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Otomat hữu hạn đơn định
3.4. Ví dụ: Xác định Otomat đoán nhận số nhị phân
Giáo trình Kiến trúc máy tính và Hệ điều hành
42
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Giáo trình Kiến trúc máy tính và Hệ điều hành
43
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Giáo trình Kiến trúc máy tính và Hệ điều hành
44
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Lập bộ phân tích từ vựng
Giáo trình Kiến trúc máy tính và Hệ điều hành
45
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Giáo trình Kiến trúc máy tính và Hệ điều hành
46
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Giáo trình Kiến trúc máy tính và Hệ điều hành
47
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Giáo trình Kiến trúc máy tính và Hệ điều hành
48
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Lập bộ phân tích từ vựng
4.1. Phương pháp mô phỏng
case 25: strcpy(ch,"nhan bang"); break;
case 26: strcpy(ch,"nhan"); break;
case 28: strcpy(ch,"chia bang"); break;
case 29: strcpy(ch,"chia"); break;
case 30: strcpy(ch,"chia lay du"); break;
default: strcpy(ch,"token ko duoc doan nhan(tt ko dung ");
}
return ch;
}
Giáo trình Kiến trúc máy tính và Hệ điều hành
49
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Giáo trình Kiến trúc máy tính và Hệ điều hành
50
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Giáo trình Kiến trúc máy tính và Hệ điều hành
51
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Lập bộ phân tích từ vựng
4.1. Phương pháp mô phỏng
int star_end_state(state s){
//kiem tra trang thai s co phai la trang thai ket thuc sao ?
switch(s){
case 4:
case 8:
case 11:
case 14:
case 19:
case 23:
Giáo trình Kiến trúc máy tính và Hệ điều hành
52
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Lập bộ phân tích từ vựng
4.1. Phương pháp mô phỏng
case 26:
case 29: return 1;
default: return 0;
}
}
Giáo trình Kiến trúc máy tính và Hệ điều hành
53
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Lập bộ phân tích từ vựng
4.1. Phương pháp mô phỏng
int start_state_otherbrand(state s){
state start;
switch(s){
case 0: start=15; break;
case 15: start=ERROR_STATE;
}
return start;
}
Giáo trình Kiến trúc máy tính và Hệ điều hành
54
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Lập bộ phân tích từ vựng
4.1. Phương pháp mô phỏng
void catchar_in_token (unsigned char c, token tk){
// ghep them ky tu c vao cho tu to tk
unsigned char *tam;
*tam=c; //*(tk+strlen(tk-1))=c;
*(tam+1)=``; //*(tk+strlen(tk))=``;
strcat(tk,tam);
}
int start_state(state s){
if ((s==0) || (s==15)) return 1; else return 0;
}
Giáo trình Kiến trúc máy tính và Hệ điều hành
55
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Lập bộ phân tích từ vựng
4.1. Phương pháp mô phỏng
token search_token (unsigned int *i, attri tt){
// tra ve tri tu vung cua tu to bdau tu vi tri i, thuoc tinh tra ve cho tt
token tk;
state s=0;
int stop=0;
unsigned char c;
do {
c=readchar(x,*i);
*i=*i+1;
} while ((c==` `)&&(*iGiáo trình Kiến trúc máy tính và Hệ điều hành
56
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Lập bộ phân tích từ vựng
4.1. Phương pháp mô phỏng
while (*i switch(s){
case 0: if (c==`>`) s=1;
else if (c==`<`) s=5; else if (c==`!`) s=9;
else if (c==`=`) s=12;
else s=start_state_otherbrand(s);
break;

Giáo trình Kiến trúc máy tính và Hệ điều hành
57
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Lập bộ phân tích từ vựng
4.1. Phương pháp mô phỏng
case 1: if (c==`=`) s=2;
else if (c==`>`) s=3;
else s=4;
break;
case 5: if (c==`=`) s=6;
else if (c==`<`) s=7;
else s=8;
break;

Giáo trình Kiến trúc máy tính và Hệ điều hành
58
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Lập bộ phân tích từ vựng
4.1. Phương pháp mô phỏng
case 9: if (c==`=`) s=10;
else s=11;
break;
case 12: if (c==`=`) s=13;
else s=14;
break;

Giáo trình Kiến trúc máy tính và Hệ điều hành
59
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Lập bộ phân tích từ vựng
4.1. Phương pháp mô phỏng
case 15: if (c==`+`) s=16;
else if (c==`-`) s=20;
else if (c==`*`) s=24;
else if (c==`/`) s=27;
else if (c==`%`) s=30;
else s=start_state_otherbrand(s);
break;

Giáo trình Kiến trúc máy tính và Hệ điều hành
60
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Lập bộ phân tích từ vựng
4.1. Phương pháp mô phỏng
case 16: if (c==`=`) s=17;
else if (c==`+`) s=18;
else s=19;
break;
case 20: if (c==`=`) s=21;
else if (c==`-`) s=22;
else s=23;
break;

Giáo trình Kiến trúc máy tính và Hệ điều hành
61
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Lập bộ phân tích từ vựng
4.1. Phương pháp mô phỏng
case 24: if (c==`=`) s=25;
else s=26;
break;
case 27: if (c==`=`) s=28;
else s=29;
break;
default: stop=1;
}

Giáo trình Kiến trúc máy tính và Hệ điều hành
62
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Lập bộ phân tích từ vựng
4.1. Phương pháp mô phỏng
if (s==ERROR_STATE){
stop=1;
printf("loi tai ky tu thu %i",*i);
*tk=``; }
else if (start_state(s));
else if (nostar_end_state(s)) {
catchar_in_token(c,tk);
*i=*i+1;
strcpy(tt,attribute(s));}
Giáo trình Kiến trúc máy tính và Hệ điều hành
63
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Lập bộ phân tích từ vựng
4.1. Phương pháp mô phỏng
else if (star_end_state(s))
strcpy(tt,attribute(s));
else {
catchar_in_token(c,tk);
*i=*i+1;
c=readchar(x,*i);}
}
return tk;
}
Giáo trình Kiến trúc máy tính và Hệ điều hành
64
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Lập bộ phân tích từ vựng
4.1. Phương pháp mô phỏng
void save_token_and_attribute(token tk,attri a){
//luu tru tk,a vao danh sach
}
void lexical_analysis(){
token tk; attri a;
do {
tk=search_token(&i,a);
save_token_and_attribute(tk,a);
}while ((*tk!=``)&&(i }
Giáo trình Kiến trúc máy tính và Hệ điều hành
65
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Lập bộ phân tích từ vựng
4.1. Phương pháp mô phỏng
main(){
//nhap xau vao x
i=0;
lexical_analysis();
//in danh sach tu to va thuoc tinh
}
Giáo trình Kiến trúc máy tính và Hệ điều hành
66
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Lập bộ phân tích từ vựng
4.1. Phương pháp điều khiển bằng bảng
Otomat phải chung một trạng thái bắt đầu
Tạo bảng table biểu diễn hàm chuyển trạng thái
Chỉ số hàng: trạng thái q Q
Chỉ số cột: ký hiệu vào a 
Table[q][a]=p với p Q và (q,a)=p
Giáo trình Kiến trúc máy tính và Hệ điều hành
67
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Lập bộ phân tích từ vựng
Giáo trình Kiến trúc máy tính và Hệ điều hành
68
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Lập bộ phân tích từ vựng
4.1. Phương pháp điều khiển bằng bảng





Trạng thái 100:Ko có hàm chuyển trạng thái
Giáo trình Kiến trúc máy tính và Hệ điều hành
69
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Lập bộ phân tích từ vựng
int table[][MAX];
token search_token (unsigned int *i, attri tt){
// tra ve tri tu vung cua tu to bdau tu vi tri i, thuoc tinh tra ve cho tt
token tk; unsigned char c;
state s=0, cs;
do {
c=readchar(x,*i);
cs=table[s][c];
if (cs==ERROR_STATE){
printf(“loi tai vi tri %i”,*i); tk=“”;break;
}
Giáo trình Kiến trúc máy tính và Hệ điều hành
70
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Lập bộ phân tích từ vựng
if (star_end_state(cs)) {
strcpy(tt,attribute(cs));
break;
}
if (nostar_end_state(cs)) {
catchar_in_token(c,tk);
*i++;
strcpy(tt,attribute(cs));
break;
}
Giáo trình Kiến trúc máy tính và Hệ điều hành
71
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Lập bộ phân tích từ vựng
if (*i>=(strlen(x)-1)) {
printf(“het xau vao, ko roi vao TT ket thuc”);
tk=“”; break;
}
catchar_in_token(c,tk);
*i++;
s=cs;
}while(1);
return tk;
}
Giáo trình Kiến trúc máy tính và Hệ điều hành
72
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Lập bộ phân tích từ vựng
void create_table(int table[][MAX]){
// tao bang chuyen trang thai table
}
void lexical_analysis(){
token tk; attri a;
create_table(table);
do {
tk=search_token(&i,a);
save_token_and_attribute(tk,a);
}while ((*tk!=``)&&(i }
Giáo trình Kiến trúc máy tính và Hệ điều hành
73
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Bảng các từ tố
Gồm các token và các thuộc tính của token
Giáo trình Kiến trúc máy tính và Hệ điều hành
74
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Các cấu trúc dữ liệu cho bảng các từ tố
Tổ chức tuần tự: mảng, danh sách liên kết, danh sách móc nối
Tổ chức cây tìm kiếm nhị phân
Giáo trình Kiến trúc máy tính và Hệ điều hành
75
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Một số vấn đề về ngôn ngữ
Văn phạm phi ngữ cảnh
Đại cương về phân tích cú pháp
Các phương pháp phân tích cú pháp
Giáo trình Kiến trúc máy tính và Hệ điều hành
76
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Một số vấn đề về ngôn ngữ
1.1. Xâu
Bộ chữ (bảng chữ) là tập hợp hữu hạn các ký hiệu
Ví dụ:{0,1} bộ chữ gồm 2 ký hiệu 0 và 1
{a,b,c,…,z} bộ chữ gồm các ký hiệu a z
Tập các chữ cái tiếng việt
Giáo trình Kiến trúc máy tính và Hệ điều hành
77
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Một số vấn đề về ngôn ngữ
1.1. Xâu
Xâu trên bộ chữ V là 1 dãy các ký hiệu của V
Ví dụ: 0110 là xâu trên bộ chữ {0,1}
a, ab, giathanh là xâu trên bộ chữ {a,b,…,z}
Độ dài xâu là số các ký hiệu trong xâu
Ký hiệu: độ dài xâu x là |x|
Ví dụ: |01110|=5
Giáo trình Kiến trúc máy tính và Hệ điều hành
78
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Một số vấn đề về ngôn ngữ
1.1. Xâu
Xâu rỗng là xâu có độ dài bằng 0
Ký hiệu: , ||=0
Tập tất cả các xâu trên V là V*, {}V*
V+ =V *-{}
V*: tập vô hạn đếm được
Ví dụ: V={a,b}V*={,a,b,aa,bb,ab,ba,…}
Giáo trình Kiến trúc máy tính và Hệ điều hành
79
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Một số vấn đề về ngôn ngữ
1.1. Xâu
Các phép toán trên xâu
Ghép tiếp: cho 2 xâu x,y. Ghép tiếp của x, y là x.y hay xy là 1 xâu viết x trước, rồi đến y sau chứ không có dấu cách.
Ví dụ: x=01
y=0110
xy=010110
Giáo trình Kiến trúc máy tính và Hệ điều hành
80
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Một số vấn đề về ngôn ngữ
1.1. Xâu
Đảo ngược xâu x (xr): xâu được viết theo thứ tự ngược lại của xâu x
Ví dụ: x=0101 xr =1010
Chú ý: r= , 1r =1
Xâu x mà x=xr thì x là xâu hình tháp (xâu đối xứng)
Ví dụ: x=0110 xr=0110, x: xâu hình tháp
Giáo trình Kiến trúc máy tính và Hệ điều hành
81
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Một số vấn đề về ngôn ngữ
1.2. Ngôn ngữ
Ngôn ngữ L trên bộ chữ V là tập hợp các xâu trên V, LV*
Các phép toán trên ngôn ngữ
Vì ngôn ngữ là tập hợp nên có các phép toán tập hợp: (giao), (hợp), -(hiệu, bù)
Giáo trình Kiến trúc máy tính và Hệ điều hành
82
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Một số vấn đề về ngôn ngữ
1.2. Ngôn ngữ
Ghép tiếp 2 ngôn ngữ
Cho 2 ngôn ngữ L1, L2. Ta gọi ghép tiếp L1.L2 (L1L2) của L1 và L2 là một tập hợp L1L2={xy/(xL1) và (yL2)}
x.x=x2; x.x.x=x3; x0=; xi=xi-1x
L0={}; Li=Li-1.L
L*=L0L1L2…; L+=L1L2…
Giáo trình Kiến trúc máy tính và Hệ điều hành
83
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Một số vấn đề về ngôn ngữ
1.3. Biểu diễn ngôn ngữ
Ngôn ngữ đơn giản
Phương pháp liệt kê: ngôn ngữ có số xâu là hữu hạn và có thể xác định được.
Ví dụ: ngôn ngữ là các số tự nhiên nhỏ hơn 20 và lớn hơn 12
L={13, 14, 15, 16, 17, 18, 19}
Giáo trình Kiến trúc máy tính và Hệ điều hành
84
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Một số vấn đề về ngôn ngữ
1.3. Biểu diễn ngôn ngữ
Ngôn ngữ đơn giản
Phương pháp sử dụng tân từ P(x): ngôn ngữ mà các xâu có cùng các đặc điểm.
Ví dụ: ngôn ngữ là các số thực nhỏ hơn 5.
L={x/ (x R) và (x<5)}
Ngôn ngữ phức tạp
Văn phạm: cơ chế để sản sinh ra ngôn ngữ
Giáo trình Kiến trúc máy tính và Hệ điều hành
85
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Văn phạm phi ngữ cảnh
2.1. Định nghĩa: G=(Σ, Δ, s, p) trong đó:
Σ: tập hữu hạn các ký hiệu kết thúc.
Δ: tập hữu hạn các ký hiệu chưa kết thúc.
s: ký hiệu bắt đầu; sΔ
p: tập hữu hạn các sản xuất có dạng A với AΔ và (ΣΔ)*
Giáo trình Kiến trúc máy tính và Hệ điều hành
86
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Văn phạm phi ngữ cảnh
2.2. Ví dụ: G=(Σ, Δ, s, p) trong đó:
Σ: {0,1}
Δ: {S}
s: S
p: S0S | 1S | 0 | 1
Giáo trình Kiến trúc máy tính và Hệ điều hành
87
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Văn phạm phi ngữ cảnh
Qui ước:
Ký hiệu kết thúc được viết bằng chữ thường
Ký hiệu chưa kết thúc được viết bằng chữ in
Ký hiệu chưa kết thúc nằm bên trái của sản xuất đầu tiên là ký hiệu bắt đầu.
Giáo trình Kiến trúc máy tính và Hệ điều hành
88
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Văn phạm phi ngữ cảnh
2.3. Các khái niệm
Xâu (câu) và dạng câu:
 gọi là xâu khi   Σ*
 gọi là dạng câu khi (ΣΔ)*
Giáo trình Kiến trúc máy tính và Hệ điều hành
89
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Văn phạm phi ngữ cảnh
2.3. Các khái niệm
Quan hệ suy dẫn:
A có quan hệ suy dẫn ra  hay  được suy dẫn từ A, có nghĩa là từ A áp dụng các sản xuất sinh ra được 
Quan hệ suy dẫn trực tiếp: từ A áp dụng một sản xuất sinh được 
Ký hiệu: A với AΔ và (ΣΔ)*
Giáo trình Kiến trúc máy tính và Hệ điều hành
90
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Văn phạm phi ngữ cảnh
2.3. Các khái niệm
Quan hệ suy dẫn:
Quan hệ suy dẫn nhiều lần: từ A áp dụng nhiều sản xuất mới sinh được 
Ký hiệu: A +  với AΔ và (ΣΔ)*
Độ dài suy dẫn: số lần áp dụng các sản xuất
Độ dài của suy dẫn trực tiếp bằng 1
Giáo trình Kiến trúc máy tính và Hệ điều hành
91
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Văn phạm phi ngữ cảnh
2.3. Các khái niệm
Quan hệ suy dẫn:
Nếu luôn luôn thay thế ký hiệu chưa kết thúc ở bên trái nhất gọi là suy dẫn trái. Tương tự ta có suy dẫn phải
Giáo trình Kiến trúc máy tính và Hệ điều hành
92
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Văn phạm phi ngữ cảnh
2.3. Các khái niệm
Cây suy dẫn: cây thoả mãn các điều kiện:
Mỗi nút có 1 nhãn: ký hiệu kết thúc hoặc chưa kết thúc
Nhãn của nút gốc: ký hiệu bắt đầu
Nhãn của nút lá: ký hiệu kết thúc
Nếu một nút có nhãn A có các nút con của nó từ trái sang phải có nhãn x1, x2, x3, …xn thì Ax1x2x3…xn  p
Giáo trình Kiến trúc máy tính và Hệ điều hành
93
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Giáo trình Kiến trúc máy tính và Hệ điều hành
94
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Văn phạm phi ngữ cảnh
2.3. Các khái niệm
Văn phạm đơn nghĩa
Văn phạm G=(Σ, Δ, s, p) sản sinh ra ngôn ngữ L(G)={wΣ*}. Ta nói G là văn phạm đơn nghĩa (không nhập nhằng) nếu với mỗi xâu wL(G) chỉ có một cây suy dẫn duy nhất, trái lại thì G là văn phạm nhập nhằng.
Giáo trình Kiến trúc máy tính và Hệ điều hành
95
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Văn phạm phi ngữ cảnh
2.3. Các khái niệm
Văn phạm tương đương
Văn phạm G1 và G2 được gọi là tương đương  bất kỳ xâu x được sinh ra từ G1 thì G2 cũng sinh ra được và ngược lại
Giáo trình Kiến trúc máy tính và Hệ điều hành
96
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Văn phạm phi ngữ cảnh
2.3. Các khái niệm
Văn phạm đệ qui
Cho văn phạm PNC G, với A Δ mà A+A thì A gọi là ký hiệu đệ qui, G gọi là văn phạm đệ qui. Với ,   (ΣΔ)*
Nếu =: đệ qui trái
Nếu =: đệ qui phải
Giáo trình Kiến trúc máy tính và Hệ điều hành
97
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Giáo trình Kiến trúc máy tính và Hệ điều hành
98
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Văn phạm phi ngữ cảnh
Bài tập
Xác định ngôn ngữ được sản sinh bởi Văn phạm:
a. SS(S)S | 
b. SaSb | bSa| 
c. S+ S S | * S S | a
d. S0S1 | 
Giáo trình Kiến trúc máy tính và Hệ điều hành
99
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Văn phạm phi ngữ cảnh
Bài tập
(2) Xây dựng văn phạm sản sinh ra ngôn ngữ:
a. Số nhị phân lẻ
b. Số nguyên k0 dấu
c. Số nguyên có dấu
d. Số thực, số nguyên k0 và có dấu
Giáo trình Kiến trúc máy tính và Hệ điều hành
100
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Giáo trình Kiến trúc máy tính và Hệ điều hành
101
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Đại cương về phân tích cú pháp
3.2. Phương pháp giải quyết
Bắt đầu từ S áp dụng các sản xuất để tìm x: PTCP từ trên xuống
Nếu tìm được x: x viết đúng cú pháp của văn phạm G
Nếu k0 tìm được x: x viết không đúng cú pháp của văn phạm G
Giáo trình Kiến trúc máy tính và Hệ điều hành
102
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Đại cương về phân tích cú pháp
3.2. Phương pháp giải quyết
Bắt đầu từ x áp dụng các suy dẫn ngược 1 sản xuất để thu S: PTCP từ dưới lên
Nếu thu được S: x viết dúng cú pháp của văn phạm G
Nếu k0 thu được S: x viết k0 đúng cú pháp của văn phạm G
Giáo trình Kiến trúc máy tính và Hệ điều hành
103
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Giáo trình Kiến trúc máy tính và Hệ điều hành
104
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Giáo trình Kiến trúc máy tính và Hệ điều hành
105
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Đại cương về phân tích cú pháp
3.2. Phương pháp giải quyết
Ví dụ:
Phương pháp từ dưới lên

Giáo trình Kiến trúc máy tính và Hệ điều hành
106
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Đại cương về phân tích cú pháp
3.2. Phương pháp giải quyết
Ví dụ:
Phương pháp từ dưới lên



Vậy xâu x viết đúng cú pháp của G
Giáo trình Kiến trúc máy tính và Hệ điều hành
107
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Giáo trình Kiến trúc máy tính và Hệ điều hành
108
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Đại cương về phân tích cú pháp
3.3. Sơ đồ chung giải thuật PTCP từ dưới lên
Thuật toán:
Sử dụng: 1 stack và 1 Buffer
Khởi tạo: - stack: $
- Buffer: x$
Lặp: If (Stack là $S) và (Buffer là $) Then
- x đúng cú pháp của vp G
- Dừng vòng lặp
Giáo trình Kiến trúc máy tính và Hệ điều hành
109
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Đại cương về phân tích cú pháp
3.3. Sơ đồ chung giải thuật PTCP từ dưới lên
Thuật toán:
Else
If (cán  xuất hiện ở đỉnh stack) Then
- Lấy cán  ra khỏi stack
- Đẩy A vào stack với A

Giáo trình Kiến trúc máy tính và Hệ điều hành
110
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Đại cương về phân tích cú pháp
3.3. Sơ đồ chung giải thuật PTCP từ dưới lên
Thuật toán:
Else
If (Buffer<>$) Then
D/c k/h ở đỉnh của Buffer Stack
Else
-Báo lỗi x không đúng cú pháp VP G
-Dừng vòng lặp
Giáo trình Kiến trúc máy tính và Hệ điều hành
111
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Đại cương về phân tích cú pháp
3.3. Sơ đồ chung giải thuật PTCP từ dưới lên
Ví dụ: Sif DK then L ;
DK  true | false
L  write(ID) | read(ID)
ID a | b
Xâu x: if true then read(a); có đúng cú pháp vp trên?
Giáo trình Kiến trúc máy tính và Hệ điều hành
112
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Giáo trình Kiến trúc máy tính và Hệ điều hành
113
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Giáo trình Kiến trúc máy tính và Hệ điều hành
114
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Giáo trình Kiến trúc máy tính và Hệ điều hành
115
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Giáo trình Kiến trúc máy tính và Hệ điều hành
116
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Đại cương về phân tích cú pháp
3.4. Sơ đồ chung giải thuật PTCP từ trên xuống
Thuật toán:
Sử dụng: 1 stack và 1 buffer
Khởi tạo: - stack: S$
- Buffer: x$
Lặp: If (Stack là $) và (Buffer là $) Then
- x đúng cú pháp của VP G
Giáo trình Kiến trúc máy tính và Hệ điều hành
117
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Đại cương về phân tích cú pháp
3.4. Sơ đồ chung giải thuật PTCP từ trên xuống
Thuật toán:
- Dừng vòng lặp
Else
If (AΔ) xuất hiện ở đỉnh Stack Then
Chọn sx thích hợp A
Triển khai A bằng  ở đỉnh Stack
Giáo trình Kiến trúc máy tính và Hệ điều hành
118
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Đại cương về phân tích cú pháp
3.4. Sơ đồ chung giải thuật PTCP từ trên xuống
Thuật toán:
Else
If (aΣ) xuất hiện ở đỉnh Stack và Buffer Then
Lấy a ra khỏi Stack và Buffer {đối sánh}
Giáo trình Kiến trúc máy tính và Hệ điều hành
119
CHƯƠNG 3. CÁC VẤN ĐỀ CƠ BẢN VỀ PHÂN TÍCH CÚ PHÁP
TRƯỜNG ĐẠI HỌC BÁCH