Chương trình dịch

1
CHƯƠNG TRÌNH DỊCH
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
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
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
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
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
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)
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
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
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.
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
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:*, /, +, -, …
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,…
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):
::=:=

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ó
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.
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ự
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
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.
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
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
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 đó.
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)
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
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


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.
27

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

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
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
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.
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.
31
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
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
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
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
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
36
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
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.
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.
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.
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
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
42
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
43
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
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
45
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
46
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
47
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
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;
}
49
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
50
CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
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:
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;
}
}
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
state start_state_otherbrand(state s){
state start;
switch(s){
case 0: start=15; break;
case 15: start=ERROR_STATE;
}
return start;
}
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
*(tk+strlen(tk))=c;
*(tk+strlen(tk)+1)=``;
}
int start_state(state s){
if ((s==0) || (s==15)) return 1; return 0;
}
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==` `)&&(*i56
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;

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;

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;

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;

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;

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;
}

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; stop=1;
strcpy(tt,attribute(s));}
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)); stop=1;}
else {
catchar_in_token(c,tk);
*i=*i+1;
c=readchar(x,*i);}
}
return tk;
}
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 }
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
}
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.2. 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
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
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
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;
//cắt ký tự trắng bỏ
do {
c=readchar(x,*i);
cs=table[s][c];
if (cs==ERROR_STATE){
printf(“loi tai vi tri %i”,*i); tk=“”;break;
}
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;
}
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;
}
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 }
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
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
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
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
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
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,…}
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
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
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ù)
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…
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}
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ữ
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à (ΣΔ)*
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
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.
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 (ΣΔ)*
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à (ΣΔ)*
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
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
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
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
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.
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
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
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
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 | 
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
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
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0S |1S |1
b. S0S| 1S|..|9S|0|..|9
c. NCD D S
D + | -
S0S| 1S|..|9S|0|..|9
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
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ữ:
d. SONCD.S | S.S | S |NCD
NCD D S
D + | -
S0S| 1S|..|9S|0|..|9

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
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
Đạ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
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
Đạ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
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
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
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
Đạ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

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.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
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
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:
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
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
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

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
Đạ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
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
Đạ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?
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
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
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
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
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:
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
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 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
120
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}
121
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
- Báo lỗi x không đúng cú pháp của G
- Dừng vòng lặp
122
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
Ví dụ: SaA
AbA | c
Xâu x: abbc có đúng cú pháp của VP trên ?
123
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
Ví dụ:
124
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
Ví dụ:
125
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
Bài tập:
Cho văn phạm G: S var ID:K;T
ID a | b | c
K byte | integer | real
T  begin L end.
L  read(ID) | write(ID)
Xâu x: var a : byte; begin read(a) end.
Xâu x có đúng cp của G? ch/m?
126
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
Bài tập:
Cho văn phạm G: S aA | bA
A cA | bA | d
Xâu x: abbcbd
Xâu x có đúng cp của G? ch/m?
127
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
Các phương pháp phân tích cú pháp
4.1. Từ trên xuống
Phương pháp tiên đoán
Phương pháp đệ qui không quay lui
128
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
Các phương pháp phân tích cú pháp
4.2. Từ dưới lên
Phương pháp ưu tiên toán tử
Phương pháp thứ tự yếu
Phương pháp LR(k)
129
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
Phương pháp phân tích cú pháp dưới lên
1.1. Phương pháp ưu tiên toán tử
Văn phạm ưu tiên toán tử
Văn phạm phi ngữ cảnh thỏa mãn các ĐK:
Không có 2 sản xuất có cùng vế phải
Không có vế phải là 
Không có 2 ký hiệu chưa kết thúc đứng liền nhau
130
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
131
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
132
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
133
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
Phương pháp phân tích cú pháp dưới lên
1.1. Phương pháp ưu tiên toán tử
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
134
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
135
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
136
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
Phương pháp phân tích cú pháp dưới lên
1.1. Phương pháp ưu tiên toán tử
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?
137
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
Phương pháp phân tích cú pháp dưới lên
1.1. Phương pháp ưu tiên toán tử
Ví dụ:
Xác định tất cả các mối quan hệ
Xét vế phải của từng sản xuất
Phân tích
138
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
139
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
140
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
Phương pháp phân tích cú pháp dưới lên
1.1. Phương pháp ưu tiên toán tử
Ví dụ:
Xác định tất cả các mối quan hệ
Sx(4|5): Lwrite(ID) | read(ID)
write | read = ( (qt1)
( = ) (qt1)
( < a | b (qt2)
a |b > ) (qt3)
141
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
142
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
143
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
144
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
145
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
Phương pháp phân tích cú pháp dưới lên
1.1. Phương pháp ưu tiên toán tử
Bài tập:
Cho văn phạm G:
S C ; H H type ID=A;B
Cconst ID = N A  byte | real
IDa | b | c B var ID : A;
N  5
Xâu x: const a=5; type b=byte; var c:real;
146
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
Phương pháp phân tích cú pháp dưới lên
1.1. Phương pháp ưu tiên toán tử
Bài tập:
Cho văn phạm G:
S C ; H H type ID=A var B
Cconst ID = N A  byte; | real;
IDa | b | c B ID : A
N  5
Xâu x: const a=5; type b=byte; var c:real;
147
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
148
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
Phương pháp phân tích cú pháp dưới lên
1.2. Phương pháp thứ tự yếu
Cấu tạo:
149
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
Phương pháp phân tích cú pháp dưới lên
1.2. Phương pháp thứ tự yếu
Cấu tạo:
Xi  (ΣΔ)
yi  Σ
S_R: ma trận có:
Chỉ số hàng xi  (ΣΔ)
Chỉ số cột yi  Σ
150
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Ẵ