Chuong trinh dich

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (551.99 KB, 270 trang )

(1)<div class='page_container' data-page=1>

ĐẠI HỌC ĐÀ NẴNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA

KHOA CÔNG NGHỆ THÔNG TIN

</div>
(2)<div class='page_container' data-page=2>

Mục tiêu giáo trình

1. Cung cấp những kiến thức cơ bản về 
chương trình dịch

2. Cung cấp các phương pháp phân 
tích từ vựng, phân tích cú pháp.

3. Cơ sở cho việc tìm hiểu các ngơn ngữ 
lập trình.

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

</div>
(3)<div class='page_container' data-page=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

</div>
(4)<div class='page_container' data-page=4>

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

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

1. Các khái niệm cơ bản

2. Đặc trưng của ngơn ngữ lập trình (NNLT) bậc cao

3. Các qui tắc từ vựng và cú pháp

4. Các chức năng của một trình biên dịch

</div>
(5)<div class='page_container' data-page=5>

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

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

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

</div>
(6)<div class='page_container' data-page=6>

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

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

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

Chương 2
NN máy

(machine 
language)

Hợp ngữ 
(Assembly)

</div>
(7)<div class='page_container' data-page=7>

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

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

1. 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)

</div>
(8)<div class='page_container' data-page=8>

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

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

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

CT nguồn Trình biên

dịch CT đích

Máy tính

thực thi Kết quả

Thời gian 
dịch

Dữ liệu

</div>
(9)<div class='page_container' data-page=9>

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

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

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

</div>
(10)<div class='page_container' data-page=10>

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

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

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

</div>
(11)<div class='page_container' data-page=11>

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

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

2. Đặc trưng của NNLT bậc cao

- Tính tự nhiên
- Tính thích nghi

</div>
(12)<div class='page_container' data-page=12>

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

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

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

</div>
(13)<div class='page_container' data-page=13>

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

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

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

</div>
(14)<div class='page_container' data-page=14>

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

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

3. 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):

</div>
(15)<div class='page_container' data-page=15>

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

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

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

</div>
(16)<div class='page_container' data-page=16>

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

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

3. 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(‘\t’), dấu sang dòng(‘\n’)

</div>
(17)<div class='page_container' data-page=17>

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

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

3. 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ừ khố và tên,…

Ví dụ: program tenct;

- Khoảng trống không bắt buộc: số và các

phép tốn, tên biến và các phép tốn
Ví dụ: x:=x+3*3;

</div>
(18)<div class='page_container' data-page=18>

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

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

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

</div>
(19)<div class='page_container' data-page=19>

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

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

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

</div>
(20)<div class='page_container' data-page=20>

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

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

4. 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 đó.

</div>
(21)<div class='page_container' data-page=21>

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

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

4. 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 tố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

</div>
(22)<div class='page_container' data-page=22>

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

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

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

</div>
(23)<div class='page_container' data-page=23>

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

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

4. 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 ‘)’ )

</div>
(24)<div class='page_container' data-page=24>

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

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

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

</div>
(25)<div class='page_container' data-page=25>

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

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

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

</div>
(26)<div class='page_container' data-page=26>

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

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

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

</div>
(27)<div class='page_container' data-page=27>

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

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

4. Các chức năng của một chương trình biên dịch

Ví dụ:

a:=(b+c)*6
Bộ PTTV

id1:=(id2+id3)*Num4
Bộ PTCP

id1 := n2
*
n3
id2
Num4
id3
+
Bộ PTNN
n1

id1 := n2
*
n3
id2
Intoreal(6)
id3
+

Bộ sinh mã trung gian

Temp1:=intoreal(6)
Temp2:=id2+id3
Temp3:=temp2*temp1
Id1:=temp3

Bộ tối ưu sinh mã trung gian

Temp1:=id2+id3
Id1:=temp1*6.0

Bộ sinh mã đối tượng

</div>
(28)<div class='page_container' data-page=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

</div>
(29)<div class='page_container' data-page=29>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴ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.

</div>
(30)<div class='page_container' data-page=30>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴ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.

</div>
(31)<div class='page_container' data-page=31>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴ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

CT 
nguồn

Bộ

phân tích

từ vựng

Gửi token Bộ 
phân tích

cú pháp
Yêu cầu token

</div>
(32)<div class='page_container' data-page=32>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴ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ĩa là ở trạng thái q, đọc a, chuyển

</div>
(33)<div class='page_container' data-page=33>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴ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,

</div>
(34)<div class='page_container' data-page=34>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴ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

</div>
(35)<div class='page_container' data-page=35>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴ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 nối từ trạng thái q sang trạng thái p

</div>
(36)<div class='page_container' data-page=36>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴ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

1 a 2

b

</div>
(37)<div class='page_container' data-page=37>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴ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

</div>
(38)<div class='page_container' data-page=38>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴ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

</div>
(39)<div class='page_container' data-page=39>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴ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 đố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 đốn nhận.

- Khơng đọc xong xâu vào (do δ rơi vào điểm

</div>
(40)<div class='page_container' data-page=40>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴ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,

</div>
(41)<div class='page_container' data-page=41>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴ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 0|1 1

0

1

trắng

2

</div>
(42)<div class='page_container' data-page=42>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

q

4.Lập bộ phân tích từ vựng

Ngồi các hình qui ước của Otomat thơng 
thường lại có thêm:

*

</div>
(43)<div class='page_container' data-page=43>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴ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

-

</div>
(44)<div class='page_container' data-page=44>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

4.Lập bộ phân tích từ vựng

0 1 =

3
>
khác
2
4 *
5 =
7
khác
6
8 *
<
<
9

! = 10

11
khác *

= = 13

14
khác *
1
5
+ 1
6
=
1
8
+
khác
1
7
1
9
*
2
0
=
2
2
khác

2
1
2
3
*

-24

* = 25

khác *

/ = 28

khác *
% 30

ss lớn hơn bằng

dịch phải

ss lớn hơn

ss nhỏ hơn bằng

dịch trái

ss nhỏ hơn
ss khác

phủ định

ss không bằng

gán

cộng bằng

tăng 1

cộng
trừ bằng

giảm 1
trừ
nhân bằng
nhân
chia bằng
chia
chia lấy dư

</div>
(45)<div class='page_container' data-page=45>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

4.Lập bộ phân tích từ vựng

4.1. Phương pháp mơ phỏng

const int ERROR_STATE=100;

typedef int state;// kieu cac trang thai

typedef unsigned char *attri;// kieu cua thuoc tinh
typedef unsigned char *token; //kieu cua tu to

unsigned char *x;//xau vao x

unsigned int i=0;// vi tri cua ky tu doc trong xau x

unsigned char readchar(unsigned char *x, unsigned int i){
//tra ve ky tu tiep theo

</div>
(46)<div class='page_container' data-page=46>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

4.Lập bộ phân tích từ vựng

4.1. Phương pháp mô phỏng

attri attribute(state s) {

// tra ve thuoc tinh tuong ung voi trang thai ket thuc
char *ch;

switch(s){

case 2: strcpy(ch,"so sanh lon hon bang");break;
case 3: strcpy(ch,"dich phai"); break;

case 4: strcpy(ch,"so sanh lon hon"); break;
case 6: strcpy(ch,"so sanh nho hon

bang");break;

case 7: strcpy(ch,"dich trai"); break;

</div>
(47)<div class='page_container' data-page=47>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

4.Lập bộ phân tích từ vựng

4.1. Phương pháp mơ phỏng

case 10: strcpy(ch,"so sanh khong bang");

break;

case 11: strcpy(ch,"phu dinh"); break;
case 13: strcpy(ch,"so sanh bang"); break;
case 14: strcpy(ch,"gan"); break;

case 17: strcpy(ch,"cong bang"); break;
case 18: strcpy(ch,"tang 1"); break;

case 19: strcpy(ch,"cong"); break;

</div>
(48)<div class='page_container' data-page=48>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

4.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 \0");

}

</div>
(49)<div class='page_container' data-page=49>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

4.Lập bộ phân tích từ vựng

4.1. Phương pháp mơ phỏng

int nostar_end_state(state s){

//kiem tra trang thai s co phai la trang thai ket thuc khong sao ?
switch(s){

</div>
(50)<div class='page_container' data-page=50>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

4.Lập bộ phân tích từ vựng

4.1. Phương pháp mơ phỏng

case 18:

case 21:
case 22:
case 25:
case 28:

case 30: return 1;
default: return 0;
}

</div>
(51)<div class='page_container' data-page=51>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

4.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){

</div>
(52)<div class='page_container' data-page=52>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

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

</div>
(53)<div class='page_container' data-page=53>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

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

</div>
(54)<div class='page_container' data-page=54>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

4.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)='\0';
}

int start_state(state s){

</div>
(55)<div class='page_container' data-page=55>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

4.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;

</div>
(56)<div class='page_container' data-page=56>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

4.Lập bộ phân tích từ vựng

4.1. Phương pháp mơ phỏng

while (*i<strlen(x)&&(!stop)){
switch(s){

case 0: if (c=='>') s=1;

else if (c=='<') s=5;

else if (c=='!') s=9;
else if (c=='=') s=12;

</div>
(57)<div class='page_container' data-page=57>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

4.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;

</div>
(58)<div class='page_container' data-page=58>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

4.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;

</div>
(59)<div class='page_container' data-page=59>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

4.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;

</div>
(60)<div class='page_container' data-page=60>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

4.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;

</div>
(61)<div class='page_container' data-page=61>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

4.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;

</div>
(62)<div class='page_container' data-page=62>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

4.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='\0'; }

else if (start_state(s));

else if (nostar_end_state(s)) {
catchar_in_token(c,tk);

*i=*i+1; stop=1;

</div>
(63)<div class='page_container' data-page=63>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

4.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);}
}

</div>
(64)<div class='page_container' data-page=64>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

4.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!='\0')&&(i<strlen(x)));

</div>
(65)<div class='page_container' data-page=65>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

4.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();

</div>
(66)<div class='page_container' data-page=66>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

4. 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 

</div>
(67)<div class='page_container' data-page=67>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

4.Lập bộ phân tích từ vựng

0 1 =

3
>
khác
2
4 *
5 =
7
khác
6
8 *
<
<
9

! = 10

11
khác *

= = 13

14
khác *

0 + 1

6
=
1
8
+
khác
1
7
1
9
*
2
0
=
2
2
khác
2
1
2
3
*

-24

* = 25

khác *

/ = 28

khác *
% 30

ss lớn hơn bằng

dịch phải

ss lớn hơn

ss nhỏ hơn bằng

dịch trái

ss nhỏ hơn
ss khác

phủ định

ss không bằng

gán

cộng bằng

tăng 1

cộng
trừ bằng

</div>
(68)<div class='page_container' data-page=68>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴ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

Trạng thái 100:Ko có hàm chuyển trạng thái

> = < ! ...

0 1 12 5 9

1 3 2 4 4

2 100 100 100 100

</div>
(69)<div class='page_container' data-page=69>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

4.int table[][MAX]; Lập bộ phân tích từ vự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; 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){

</div>
(70)<div class='page_container' data-page=70>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

4. 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;

</div>
(71)<div class='page_container' data-page=71>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

4. 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++;

</div>
(72)<div class='page_container' data-page=72>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

4. 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!='\0')&&(i<strlen(x)));

</div>
(73)<div class='page_container' data-page=73>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

5. Bảng các từ tố

Gồm các token và các thuộc tính của token

Chỉ số Ttính Trị từ vựng

token Các thuộc tính khác
01

02 Num 45

03 Id A

04 Id B

</div>
(74)<div class='page_container' data-page=74>

CHƯƠNG 2. PHÂN TÍCH TỪ VỰNG

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

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

</div>
(75)<div class='page_container' data-page=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

</div>
(76)<div class='page_container' data-page=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

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

</div>
(77)<div class='page_container' data-page=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

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

</div>
(78)<div class='page_container' data-page=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

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

</div>
(79)<div class='page_container' data-page=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

1. Một số vấn đề về ngơn ngữ

1.1. Xâu

- Các phép tố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

</div>
(80)<div class='page_container' data-page=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

1. 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)

</div>
(81)<div class='page_container' data-page=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

1. 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 tốn trên ngơn ngữ

• Vì ngơn ngữ là tập hợp nên có các phép toán

</div>
(82)<div class='page_container' data-page=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

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

</div>
(83)<div class='page_container' data-page=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

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

</div>
(84)<div class='page_container' data-page=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

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

</div>
(85)<div class='page_container' data-page=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

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

</div>
(86)<div class='page_container' data-page=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

2. Văn phạm phi ngữ cảnh

2.2. Ví dụ: G=(Σ, Δ, s, p) trong đó:
Σ: {0,1}

Δ: {S}
s: S

</div>
(87)<div class='page_container' data-page=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

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

</div>
(88)<div class='page_container' data-page=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

2. 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   Σ*

</div>
(89)<div class='page_container' data-page=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

2. 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 

</div>
(90)<div class='page_container' data-page=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

2. 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à (ΣΔ)*

</div>
(91)<div class='page_container' data-page=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

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

</div>
(92)<div class='page_container' data-page=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

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

</div>
(93)<div class='page_container' data-page=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

2. Văn phạm phi ngữ cảnh

2.3. Các khái niệm

 Cây suy dẫn

- Suy dẫn trái tạo cây suy dẫn trái.
- Suy dẫn phải tạo cây suy dẫn phải.

- Ví dụ: cho văn phạm phi ngữ cảnh sau:

EE+E | E*E | (E) | a

Vẽ cây suy dẫn trái, phải sinh xâu: a+a*a

</div>
(94)<div class='page_container' data-page=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

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

</div>
(95)<div class='page_container' data-page=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

2. 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ì

</div>
(96)<div class='page_container' data-page=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

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

</div>
(97)<div class='page_container' data-page=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

2. Văn phạm phi ngữ cảnh

2.3. Các khái niệm

 Văn phạm đệ qui

Ví dụ: SS0 | S1 | 0 | 1

</div>
(98)<div class='page_container' data-page=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

2. Văn phạm phi ngữ cảnh

Bài tập

(1) 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

</div>
(99)<div class='page_container' data-page=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

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

</div>
(100)<div class='page_container' data-page=100>

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

2. 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 + |

</div>
(101)<div class='page_container' data-page=101>

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

2. 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 + |

</div>
(102)<div class='page_container' data-page=102>

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

3. Đại cương về phân tích cú pháp

3.1. Mục đích

Cho G=(Σ, Δ, s, p) 
Một xâu vào xΣ*

</div>
(103)<div class='page_container' data-page=103>

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

3. Đạ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ú

</div>
(104)<div class='page_container' data-page=104>

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

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

</div>
(105)<div class='page_container' data-page=105>

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

3. Đại cương về phân tích cú pháp

3.2. Phương pháp giải quyết

Ví dụ: Cho văn phạm PNC G sau:

SB

BR | (B)

R E=E

E a | b | (E+E)

Xâu x: (a=(b+a))

Hỏi xâu x có viết đúng cú pháp của G k0?

(1)

(2) (3)
(4)

</div>
(106)<div class='page_container' data-page=106>

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

3. Đạ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ừ trên xuống

S => B => (B) => (R) => (E=E)
=> (E=(E+E)) => (E=(E+a))

=> (E=(b+a)) => (a=(b+a)) :xâu x
Vậy xâu x viết đúng cú pháp của G

(1) (3) (2) (4)

(7) (5)

</div>
(107)<div class='page_container' data-page=107>

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

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

Stt Dạng câu Cán Sx dùng
(0) (a=(b+a)) a Ea

(1) (E=(b+a)) b Eb

(2) (E=(E+a)) a Ea

</div>
(108)<div class='page_container' data-page=108>

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

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

(4) (E=E) E=E RE=E

(5) (R) R BR

(6) (B) (B) B(B)

(7) B B SB

</div>
(109)<div class='page_container' data-page=109>

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

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

S
A

0
i-1
i

k=x

i ui

i’

A

Biết i tìm i-1
i = iui

i(ΣΔ)*; uiΣ*
i =i’

</div>
(110)<div class='page_container' data-page=110>

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

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

</div>
(111)<div class='page_container' data-page=111>

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

3. Đạ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

</div>
(112)<div class='page_container' data-page=112>

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

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

</div>
(113)<div class='page_container' data-page=113>

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

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

</div>
(114)<div class='page_container' data-page=114>

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

Stt Stack Buffer Hành động
(0) $ if true then read(a); $ D/c

(1) $if true then read(a);$ D/c

(2) $if true then read(a);$ R/g DKtrue

(3) $if DK then read(a);$ D/c
(4) $if DK then read(a);$ D/c

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

</div>
(115)<div class='page_container' data-page=115>

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

Stt Stack Buffer Hành động
(5) $if DK then read (a);$ D/c

(6) $if DK then read( a);$ D/c

(7) $if DK then read(a );$ R/g IDa

(8) $if DK then read(ID );$ D/c

(9) $if DK then read(ID) ;$ R/g Lread(ID)

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

</div>
(116)<div class='page_container' data-page=116>

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

Stt Stack Buffer Hành động
(10) $if DK then L ;$ D/c

(11) $if DK then L; $ R/g Sif DK then L;

(12) $S $ Chấp nhận x đúng cp G

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

</div>
(117)<div class='page_container' data-page=117>

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

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

Biết i tìm i+1
i = uii

i(ΣΔ)*; uiΣ*
i =Ai’

k = x=uk; k=
0 = S=A=0; 
0’=u0=

A

S

0

i

i+1

k=x

A

i

ui

i’


</div>
(118)<div class='page_container' data-page=118>

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

3. Đạ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$

</div>
(119)<div class='page_container' data-page=119>

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

3. Đạ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 tố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

</div>
(120)<div class='page_container' data-page=120>

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

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

</div>
(121)<div class='page_container' data-page=121>

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

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

</div>
(122)<div class='page_container' data-page=122>

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

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

</div>
(123)<div class='page_container' data-page=123>

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

3. Đạ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ụ:

Stt Stack Buffer Hành động

(0) S$ abbc$ Triển khai SaA

(1) aA$ abbc$ Đối sánh

(2) A$ bbc$ Triển khai AbA

</div>
(124)<div class='page_container' data-page=124>

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

3. Đạ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ụ:

Stt Stack Buffer Hành động

(4) A$ bc$ Triển khai AbA

(5) bA$ bc$ Đối sánh

(6) A$ c$ Triển khai Ac

(7) c$ c$ Đối sánh

</div>
(125)<div class='page_container' data-page=125>

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

3. Đại cương về phân tích cú pháp

Bài tập:

(1)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)

</div>
(126)<div class='page_container' data-page=126>

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

3. Đại cương về phân tích cú pháp

Bài tập:

(2)Cho văn phạm G: S aA | bA

A cA | bA | d

Xâu x: abbcbd

</div>
(127)<div class='page_container' data-page=127>

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

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

</div>
(128)<div class='page_container' data-page=128>

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

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

</div>
(129)<div class='page_container' data-page=129>

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

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

</div>
(130)<div class='page_container' data-page=130>

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

1. 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ử

 Mối quan hệ ưu tiên giữa các ký hiệu

Với a, b Σ có:

- a

- a= b: a ưu tiên bằng b
- a > b: a ưu tiên hơn b

- a và b : khơng có quan hệ ưu tiên




</div>
(131)<div class='page_container' data-page=131>

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

1. 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ử

 Qui tắc xác định mối quan hệ

(1)  Sx mà vế phải có dạng ab

hay aCb

(2)  Sx mà vế phải có dạng aB

mà B+ b hay B+Cb

(3)  Sx mà vế phải có dạng Ab

mà A+ a hay A+ aC

</div>
(132)<div class='page_container' data-page=132>

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

1. 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ử

 Qui tắc xác định mối quan hệ

(4) S+a hay S+aC

hay S+ a hay S+Ca

Với a, bΣ; A,B,CΔ; , ,   (ΣΔ)*

 Lưu ý:- Cán:< >

- a < b
b < c

a >$.

. .
.

. a < c.

</div>
(133)<div class='page_container' data-page=133>

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

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

</div>
(134)<div class='page_container' data-page=134>

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

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

Else {giả sử k/h kết thúc gần đỉnh stack 
nhất là a và

buffer là b}

If (a>b) Then

- Tìm cán  ở đỉnh stack(vị trí mở cán <)

- Lấy cán  ra khỏi stack

- Đẩy A vào stack với A

.

</div>
(135)<div class='page_container' data-page=135>

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

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

Else

If (a<b) or (a=b)Then

D/c b từ Buffer Stack

Else

- Báo lỗi x không đúng cú pháp G
 - Dừng vòng lặp

</div>
(136)<div class='page_container' data-page=136>

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

1. Phương pháp phân tích cú pháp dưới lên

1.1. Phương pháp ưu tiên tốn tử

 Ví dụ: Sif DK then L ;

DK  true | false

L  write(ID) | read(ID)

ID a | b

</div>
(137)<div class='page_container' data-page=137>

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

1. Phương pháp phân tích cú pháp dưới lên

1.1. Phương pháp ưu tiên tố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

</div>
(138)<div class='page_container' data-page=138>

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

1. Phương pháp phân tích cú pháp dưới lên

1.1. Phương pháp ưu tiên tốn tử

 Ví dụ:

- Xác định tất cả các mối quan hệ

Sx(1):Sif DK then L;  if = then (qt1)

Sif DK then L;

DK true | false  if < true | false (qt2)

S if DK then L;

DK true | false  true | false > then(qt3)

.

 a C b 
 a B 

B b  b 
 A b 

A  a  a

</div>
(139)<div class='page_container' data-page=139>

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

1. Phương pháp phân tích cú pháp dưới lên

1.1. Phương pháp ưu tiên tốn tử

 Ví dụ:

- Xác định tất cả các mối quan hệ

Sx(1):Sif DK then L;  then = ; (qt1)

Tương tự:

then < write | read (qt2)
) > ; (qt3)

.

 a C b 

</div>
(140)<div class='page_container' data-page=140>

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

1. Phương pháp phân tích cú pháp dưới lên

1.1. Phương pháp ưu tiên tố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)
.

.
.

</div>
(141)<div class='page_container' data-page=141>

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

1. 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ệ

S  if DK then L ;  if | ; > $

a 

 a

</div>
(142)<div class='page_container' data-page=142>

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

Stt Stack Buffer Q/hệ H/động

(0) $ if true then read(a);$ < D/c

(1) $if true then read(a);$ < D/c

(2) $if true then read(a);$ > R/g DKtrue

(3) $if DK then read(a);$ = D/c

1. 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ụ:

.
.

</div>
(143)<div class='page_container' data-page=143>

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

Stt Stack Buffer Q/hệ H/động

(4) $if DK then read(a);$ < D/c

(5) $if DK then read (a);$ = D/c

(6) $if DK then read( a);$ < D/c

(7) $if DK then read( a );$ > R/g IDa

1. Phương pháp phân tích cú pháp dưới lên

1.1. Phương pháp ưu tiên tốn tử

 Ví dụ:

.
.
.

.

</div>
(144)<div class='page_container' data-page=144>

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

Stt Stack Buffer Q/hệ H/động

(8) $if DK then read(ID );$ = D/c

(9) $ if DK then

read(ID) ;$ > Lread(ID)R/g

(10) $ if DK then L ;$ = D/c

(11) $ if DK then L; $ > R/g Sif

DK then L;

(12) $S $ Chấp nhận

1. Phương pháp phân tích cú pháp dưới lên

1.1. Phương pháp ưu tiên tốn tử

 Ví dụ:

.
.
.

.

</div>
(145)<div class='page_container' data-page=145>

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

1. Phương pháp phân tích cú pháp dưới lên

1.1. Phương pháp ưu tiên tốn tử
Bài tập:

(1)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

</div>
(146)<div class='page_container' data-page=146>

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

1. Phương pháp phân tích cú pháp dưới lên

1.1. Phương pháp ưu tiên tốn tử
Bài tập:

(2)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

</div>
(147)<div class='page_container' data-page=147>

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

1. 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:

(2) Các mối quan hệ:

5 | = > ; ; < type ;|var| : |const > $
const= = const <a|b|c a|b|c> = =<5
type= = type< a|b|c = = var

a|b|c> = =< byte|real ;>var var< :|a|b|c
byte|real=; a|b|c> : :< byte|real

</div>
(148)<div class='page_container' data-page=148>

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

1. 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:

Stack

$ x1 x2 … xi yi … y2 y1 $

Buffer

Kết quả
Bộ phân

</div>
(149)<div class='page_container' data-page=149>

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

1. 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ó:

</div>
(150)<div class='page_container' data-page=150>

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ẴNG

1. 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:

• S_R[xi,yi]: có các giá trị

</div>
(151)<div class='page_container' data-page=151>

151

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

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

 Hoạt động:

- Tại một thời điểm nào đó k/h ở đỉnh của

stack là Xi(ΣΔ), ở đỉnh buffer là yiΣ. Bộ

</div>
(152)<div class='page_container' data-page=152>

152

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

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

 Hoạt động:

• S_R[xi,yi]: xác định hành động

 S_R[xi,yi]=S: dịch chuyển k/h đỉnh

buffer  stack

 S_R[xi,yi]=R: rút gọn

</div>
(153)<div class='page_container' data-page=153>

153

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

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

 Thuật toán

Sử dụng: 1 stack và 1 Buffer
Khởi tạo: - stack: $

- Buffer: x$
Lặp:

</div>
(154)<div class='page_container' data-page=154>

154

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

1. Phương pháp phân tích cú pháp dưới lên

1.1. Phương pháp thứ tự yếu

 Thuật toán

If (S_R[x,y]=R*) Then

- x đúng cú pháp của vp G
- Dừng vòng lặp

Else If (S_R[x,y]=rỗng) Then

</div>
(155)<div class='page_container' data-page=155>

155

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

1. Phương pháp phân tích cú pháp dưới lên

1.1. Phương pháp thứ tự yếu

 Thuật toán

Else If (S_R[x,y]=S) then

D/c y từ buffer stack

Else {S_R[x,y]=R}

If (Có vế phải  dài nhất ở đỉnh stack) then

- Lấy  ra khỏi stack

</div>
(156)<div class='page_container' data-page=156>

156

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

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

 Thuật toán

Else

</div>
(157)<div class='page_container' data-page=157>

157

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

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

 Ví dụ: Cho G : Sid=A

AA+B | B

BB*C | C

Cid | (A)

</div>
(158)<div class='page_container' data-page=158>

158

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

Bảng S_R

id * + ( ) = $

S R*

A S S R

B S R R R

C R R R R

id R R R S R

* S S

+ S S

( S S

) R R R R

= S S

</div>
(159)<div class='page_container' data-page=159>

159

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

1. Phương pháp phân tích cú pháp dưới lên

1.1. Phương pháp thứ tự yếu

 Qui tắc xác định mối quan hệ 
(1) Sx mà vế phải có dạng xy

- Nếu yΣ thì: x = y

- Nếu yΔ thì: x < y

Với x(ΣΔ); ,(ΣΔ)*

</div>
(160)<div class='page_container' data-page=160>

160

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

1. Phương pháp phân tích cú pháp dưới lên

1.1. Phương pháp thứ tự yếu

 Qui tắc xác định mối quan hệ 
(2) Sx mà vế phải có dạng xA

mà A+ y thì: x < y

Với x,y(ΣΔ); AΔ; ,,(ΣΔ)*
(3) Sx mà vế phải có dạng AB

mà A+ x và B+ y thì: x > y

Với x,y,B(ΣΔ); AΔ; ,,,(ΣΔ)*

(Nếu BΣ thì y chính là B)

.

</div>
(161)<div class='page_container' data-page=161>

161

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

1. Phương pháp phân tích cú pháp dưới lên

1.1. Phương pháp thứ tự yếu

 Qui tắc xác định mối quan hệ

(4)S+x hay S+x thì x > $

Với x (ΣΔ) ;   (ΣΔ)*

</div>
(162)<div class='page_container' data-page=162>

162

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

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

 Xây dựng bảng S_R

- X < Y hay X=Y thì: S_R[X,Y]=S
- X > Y thì: S_R[X,Y]=R

- Stack là $S và Buffer là $ thì: S_R[X,Y]=R*
- X và Y khơng có mối quan hệ thì:

S_R[X,Y]=rỗng 
.

.

</div>
(163)<div class='page_container' data-page=163>

163

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

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

 Ví dụ: cho G như sau:

SA C D A const ID=N;

C var ID: K; D begin L end.

L write(ID) |read(ID) ID a|b

N5 Kbyte|real

</div>
(164)<div class='page_container' data-page=164>

164

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

1. 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ác mối quan hệ: begin<write|read )>end

A < C A < var ; > var C < D

C< begin .|D > $ const|A>$ ; > begin
var < ID ID = : : < K K = ;

( < a|b a|b > ) const <ID ID= = = < N
N=; const <a|b a|b > = = < 5
5 > ; begin<L L=end end=.

</div>
(165)<div class='page_container' data-page=165>

165

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

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

 Văn phạm thứ tự yếu

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ó phần tử S_R[x,y] có cả trị S và R

- Nếu Ax1x2…xn và Bxixi+1…xn thì

</div>
(166)<div class='page_container' data-page=166>

166

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

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

 Văn phạm thứ tự yếu

Nếu  xi-1<=B thì có nghĩa  C

</div>
(167)<div class='page_container' data-page=167>

167

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

1. Phương pháp phân tích cú pháp dưới lên

1.3. Phương pháp Simple LR (SLR)

 Cấu tạo:

Kết quả

$
a0
a1

…
ai

Buffer

Bộ phân 
tích
Stack

$ S0 x0 … Si-1 Xi-1 Si

</div>
(168)<div class='page_container' data-page=168>

168

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

1. Phương pháp phân tích cú pháp dưới lên

1.3. Phương pháp Simple LR (SLR)

 Cấu tạo:

- Stack: $s0x0 s1x1…si-1xi-1si
st: trạng thái; xt(ΣΔ)

- Buffer: aiai-1…a0$ ; với at Σ

- Bảng SLR gồm 2 phần: action và goto

</div>
(169)<div class='page_container' data-page=169>

169

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

1. Phương pháp phân tích cú pháp dưới lên

1.3. Phương pháp Simple LR (SLR)

 Cấu tạo:

• Chỉ số cột

Phần action: aiΣ

Phần goto: XΔ

• Action[Si,ai]=Shift j (Sj)

</div>
(170)<div class='page_container' data-page=170>

170

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

1. Phương pháp phân tích cú pháp dưới lên

1.3. Phương pháp Simple LR (SLR)

 Cấu tạo:

• Action[Si,ai]=Accept

• Action[Si,ai]=rỗng

</div>
(171)<div class='page_container' data-page=171>

171

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

1. Phương pháp phân tích cú pháp dưới lên

1.3. Phương pháp Simple LR (SLR)

 Hoạt động:

Tại một thời điểm bộ phân tích đọc trạng 
thái Si ở đỉnh stack và ký hiệu vào ai ở đỉnh 
buffer và tra trong bảng SLR ở phần Action 
một giá trị. Nếu:

- Action[Si,ai]=Shift j (Sj)

</div>
(172)<div class='page_container' data-page=172>

172

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

1. Phương pháp phân tích cú pháp dưới lên

1.3. Phương pháp Simple LR (SLR)

 Hoạt động:

- Action[Si,ai]=Reduce A (RJ)

 Lấy 2*r phần tử ra khỏi stack. Với r=||
 Đẩy A vào stack

</div>
(173)<div class='page_container' data-page=173>

173

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

1. Phương pháp phân tích cú pháp dưới lên

1.3. Phương pháp Simple LR (SLR)

 Hoạt động:

- Action[Si,ai]=Accept

 Xâu x đúng cp của vpG

- Action[Si,ai]=rỗng

</div>
(174)<div class='page_container' data-page=174>

174

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

1. Phương pháp phân tích cú pháp dưới lên

1.3. Phương pháp Simple LR (SLR)

 Thuật toán:

Sử dụng: 1 stack, 1 buffer, bảng SLR
Khởi tạo: - stack: $0

- Buffer: x$

Lặp: {g/sử ở đỉnh stack là Si, đỉnh buffer là a} 
If (Action[Si,a]=accept) then

</div>
(175)<div class='page_container' data-page=175>

175

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

1. Phương pháp phân tích cú pháp dưới lên

1.3. Phương pháp Simple LR (SLR)

 Thuật toán:

Else If (Action[Si,a]=Sj) then

- D/c a từ buffer  stack
- Đẩy j vào stack

Else IF (Action[Si,a]=Reduce A) then

</div>
(176)<div class='page_container' data-page=176>

176

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

1. Phương pháp phân tích cú pháp dưới lên

1.3. Phương pháp Simple LR (SLR)

 Thuật toán:

- Đẩy A vào stack

- Đẩy j vào stack. Với j=goto[Si-r,A]
Else {Action[Si,a]=rỗng}

- Báo lỗi x không đúng cp của G

</div>
(177)<div class='page_container' data-page=177>

177

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

1. Phương pháp phân tích cú pháp dưới lên

1.3. Phương pháp Simple LR (SLR)

 Ví dụ: Cho vp G

E  E + T | T

T  T * F | F

F  (E) | id

Xâu x: id*(id+id)

</div>
(178)<div class='page_container' data-page=178>

178

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

1. Phương pháp phân tích cú pháp dưới lên

1.3. Phương pháp Simple LR (SLR)

T/

thái id + * Action( ) $ E GotoT F

0 S5 S4 1 2 3

1 S6 Accept

2 R2 S7 R2 R2

3 R4 R4 R4 R4

4 S5 S4 8 2 3

5 R6 R6 R6 R6

</div>
(179)<div class='page_container' data-page=179>

179

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

1. Phương pháp phân tích cú pháp dưới lên

1.3. Phương pháp Simple LR (SLR)

T/

7 S5 S4 10

8 S6 S11

9 R1 S7 R1 R1

10 R3 R3 R3 R3

</div>
(180)<div class='page_container' data-page=180>

180

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

1. Phương pháp phân tích cú pháp dưới lên

1.3. Phương pháp Simple LR (SLR)

 Ví dụ:

Stt Stack Buffer Hành động
0 $0 id*(id+id)$ S5
1 $0 id 5 *(id+id)$ R6(Fid)

2 $0 F 3 *(id+id)$ R4(TF)

</div>
(181)<div class='page_container' data-page=181>

181

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

1. Phương pháp phân tích cú pháp dưới lên

1.3. Phương pháp Simple LR (SLR)

 Ví dụ:

Stt Stack Buffer Hành động
6 $0 T 2 * 7 ( 4 id 5 +id)$ R6(Fid)

7 $0 T 2 * 7 ( 4 F 3 +id)$ R4(TF)

8 $0 T 2 * 7 ( 4 T 2 +id)$ R2(ET)

</div>
(182)<div class='page_container' data-page=182>

182

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

1. Phương pháp phân tích cú pháp dưới lên

1.3. Phương pháp Simple LR (SLR)

 Ví dụ:

Stt Stack Buffer Hành động
12 $0 T 2 * 7 ( 4 E 8 + 6 F 3 )$ R4(TF)

13 $0 T 2 * 7 ( 4 E 8 + 6 T 9 )$ R1(EE+T)

14 $0 T 2 * 7 ( 4 E 8 )$ S11
15 $0 T 2 * 7 ( 4 E 8 ) 11 $ R5(F(E))

16 $0 T 2 * 7 F 10 $ R3(TT*F)

</div>
(183)<div class='page_container' data-page=183>

183

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

1. Phương pháp phân tích cú pháp dưới lên

1.3. Phương pháp Simple LR (SLR)

 Ví dụ:

Stt Stack Buffer Hành động

</div>
(184)<div class='page_container' data-page=184>

184

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

1. Phương pháp phân tích cú pháp dưới lên

1.3. Phương pháp Simple LR (SLR)

 Xây dựng bảng SLR

- Văn phạm gia tố G’

G’=G  {S’S}

Ví dụ: G: S  0S | 1S|0|1

G’: S’  S

</div>
(185)<div class='page_container' data-page=185>

185

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

1. Phương pháp phân tích cú pháp dưới lên

1.3. Phương pháp Simple LR (SLR)

 Xây dựng bảng SLR

- Thực thể: Sx thêm dấu chấm ở bất kỳ vị trí

của vế phải.

Ví dụ: A xyz

thì A .xyz Ax.yz Axy.z

</div>
(186)<div class='page_container' data-page=186>

186

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

1. Phương pháp phân tích cú pháp dưới lên

1.3. Phương pháp Simple LR (SLR)

 Xây dựng bảng SLR

- Hàm tính bao đóng Closure(Ii): 2 qui tắc

(1) Đưa tất cả các thực thể trong Ii vào closure(Ii)

(2) Cứ mỗi thực thể có dạng A.Bclosure(Ii)

mà B thì thêm B. vào closure(Ii) với

</div>
(187)<div class='page_container' data-page=187>

187

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

1. Phương pháp phân tích cú pháp dưới lên

1.3. Phương pháp Simple LR (SLR)

 Ví dụ: Xác định tập closure(I) của VP G’

E’ E

E  E + T | T

T  T * F | F

F  (E) | id

</div>
(188)<div class='page_container' data-page=188>

188

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

1. Phương pháp phân tích cú pháp dưới lên

1.3. Phương pháp Simple LR (SLR)

 Xây dựng bảng SLR

- Hàm tính goto

Goto(Ii,x)=closure({Ax.})

</div>
(189)<div class='page_container' data-page=189>

189

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

1. Phương pháp phân tích cú pháp dưới lên

1.3. Phương pháp Simple LR (SLR)

 Ví dụ: Tìm tất cả các tập goto(I,X) có thể

của VP G

I={ E’.E

E.E+T

E.T

T.T*F }

X: E, T

Goto(I,E) và Goto(I,T)

E’ E

E  E + T | T

T  T * F | F

F  (E) | id

Goto(I,E)=closure({E’E.

; EE.+T})

Goto(I,T)=closure({ET.

</div>
(190)<div class='page_container' data-page=190>

190

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

1. Phương pháp phân tích cú pháp dưới lên

1.3. Phương pháp Simple LR (SLR)

 Xây dựng bảng SLR

- Tập thực thể LR(0)

I0=closure({S’.S})

- Tính tất cả các goto(Ii,x) của tất cả các tập 
thực thể ta sẽ được tập LR(0).

</div>
(191)<div class='page_container' data-page=191>

191

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

1. Phương pháp phân tích cú pháp dưới lên

1.3. Phương pháp Simple LR (SLR)

 Xây dựng bảng SLR

- Qui tắc xác định hành động

(1) A.a  Ii và goto(Ii,a)=Ij với a Σ

thì: Action[i,a]= Sj

(2) A.X  Ii và goto(Ii,X)=Ij với X Δ

</div>
(192)<div class='page_container' data-page=192>

192

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

1. Phương pháp phân tích cú pháp dưới lên

1.3. Phương pháp Simple LR (SLR)

 Xây dựng bảng SLR

- Qui tắc xác định hành động

(3) S’S.  Ii thì: Action[i,$]= accept

(4) A.  Ii thì Action[i,a]= Reduce A

với a Follow(A); A<>S’

- Qui tắc xác định Follow Follow(A)={(tΣ|

</div>
(193)<div class='page_container' data-page=193>

193

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

1. Phương pháp phân tích cú pháp dưới lên

1.3. Phương pháp Simple LR (SLR)

 Ví dụ: Cho vp G

E  E + T | T

T  T * F | F

F  (E) | id

</div>
(194)<div class='page_container' data-page=194>

194

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

1. Phương pháp phân tích cú pháp dưới lên

1.3. Phương pháp Simple LR (SLR)

 Ví dụ:

- Xác định G’

- Tạo tập thực thể LR(0)

</div>
(195)<div class='page_container' data-page=195>

195

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

1. Phương pháp phân tích cú pháp dưới lên

1.3. Phương pháp Simple LR (SLR)

 Ví dụ:

- VP gia tố G’

E’  E

E  E + T | T

T  T * F | F

</div>
(196)<div class='page_container' data-page=196>

196

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

1. Phương pháp phân tích cú pháp dưới lên

1.3. Phương pháp Simple LR (SLR)

 Ví dụ:

- Tạo tập thực thể LR(0)

I0=closure({E’.E})

E’.E

E.E+T

E.T

T.T*F

T.F

F.(E)

F.id

I1=goto(I0,E)
E’E.

</div>
(197)<div class='page_container' data-page=197>

197

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

1. Phương pháp phân tích cú pháp dưới lên

1.3. Phương pháp Simple LR (SLR)

 Ví dụ:

</div>
(198)<div class='page_container' data-page=198>

198

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

1. Phương pháp phân tích cú pháp dưới lên

1.3. Phương pháp Simple LR (SLR)
Bài tập:

(1)cho VPG: A A or B | B

B  B and C | C

C  not C | (A) | true | false

</div>
(199)<div class='page_container' data-page=199>

199

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

1. Phương pháp phân tích cú pháp dưới lên

1.3. Phương pháp Simple LR (SLR)
Bài tập:

(2)Cho VPG: S AS| b

A  SA| a

</div>
(200)<div class='page_container' data-page=200>

200

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

1. Phương pháp phân tích cú pháp dưới lên

1.4. Phương pháp Canonical LR (LR(1))

- Trong PP SLR xung đột chỉ xảy ra ở những

thực thể A .

- Khi xảy ra xung đột ta có thể sử dụng PP

</div>

Chuong trinh dich

<b>Mục tiêu giáo trình</b>

<b>Nội dung giáo trình</b>

<b>.</b>

<b>δ</b>

a

b

c

1

2

Tài liệu liên quan

Tài liệu bạn tìm kiếm đã sẵn sàng tải về