Tìm hiểu về bộ phân tích cú pháp Bison | Bài báo cáo học phần Chương trình dịch | Trường Đại học Phenikaa

TRƯỜNG ĐẠI HỌC PHENIKAA
KHOA CÔNG NGHỆ THÔNG TIN
BÁO CÁO CHƯƠNG TRÌNH DỊCH
TÌM HIỂU VỀ BỘ PHÂN TÍCH CÚ PHÁP BISON Hoàng Văn Phú 21010654
21010654@st.phenikaauni.eud.vn Nguyễn Thế 21012898
21012898@st.phenikaauni.edu.vn Toại Hoàng Anh 21012902
21012902@st.phenikaauni.edu.vn Tuấn
Giảng viên hướng dẫn: Hà Thị Kim Dung 1 lOMoARcPSD|48045915 Họ và tên MSSV Điểm bằng số Điểm bằng chữ Hoàng Văn Phú Hoàng Anh Tuấn Nguyễn Thế Toại 2 MỤC LỤC
1. Giới thiệu ............................................................................................................... 3 1.1 Đặt
vấn ề .......................................................................................................................... 6 1.2 Giới thiệu ề tài
.................................................................................................................. 6 2. Nội
dung ................................................................................................................ 8 2.1 Tìm hiểu về
bộ sinh PTCP Bison ....................................................................................... 8
2.1.1 Giới thiệu về bộ phân tích cú pháp ................................................................................ 8
2.1.2 Vai trò trong chương trình dịch ................................................................................... 14
2.1.3 Nêu ặc iểm/ yêu cầu của bộ phân tích cú pháp ........................................................ 19
2.1.4 Giới thiệu bộ phân tích cú pháp Bison ......................................................................... 24
2.1.5 Hướng dẫn cài ặt. ....................................................................................................... 29
2.1.6 Phân tích bộ phân tích cú pháp Bison .......................................................................... 34
2.1.7 Xây dựng chương trình minh họa ................................................................................ 53
2.1.8 Tổng kết vấn ề ........................................................................................................... 66
2.2 Xác ịnh cách tự ộng tạo biểu ồ máy tự ộng LALR từ ngữ pháp. ............................. 66
2.2.1 Tổng quan về LALR. ................................................................................................... 67
2.2.2 Tạo biểu ồ chuyển LALR với Bison. ......................................................................... 67
2.2.3 Xây dựng biểu ồ LALR vẽ tay. .................................................................................. 86
2.2.4 So sánh hai phiên bản vẽ tay và ược tạo bởi Bison. .................................................. 92
2.2.5 Tổng kết ....................................................................................................................... 94 3. Kết
luận ............................................................................................................... 95 3.1.1 Kết quả
thực hiện ......................................................................................................... 95 3.1.2 Kinh nghiệm thu ược sau
khi hoàn thành báo cáo ..................................................... 95
Danh mục hình ảnh Hình 1:Hình ảnh nhận diện của BisonLỗi! Thẻ đánh dấu không được xác định.
Hình 2:Cây cú pháp biểu diễn cấu trúc toán học ................................................................... 14
Hình 3:Kiểm tra lỗi trong Python .......................................................................................... 15
Hình 4: Bên trong thư mục bin .............................................................................................. 27
Hình 5:Tìm kiếm với từ khóa ................................................................................................ 28
Hình 6:Nhấn chọn Environment Variables ............................................................................ 29
Hình 7: Lựa chọn Path tại user variables ............................................................................... 30
Hình 8: Thêm biến môi trường mới trong giao diện này ....................................................... 31
Hình 9:Ứng dụng ược cài thành công .................................................................................... 32
Hình 10:Chạy câu lệnh flex .\lexer.l ...................................................................................... 48
Hình 11: Chạy lệnh bison -d -t .\parser.y ể tạo ra hai file parser.tab.c và parser.tab.h ......... 49
Hình 12: file parser.y chưa phân tích cú pháp ....................................................................... 49
Hình 13:Mã phân tích từ vựng ............................................................................................... 51 3 lOMoARcPSD|48045915
Hình 14: Chạy lệnh flex .\lexer.l ............................................................................................ 53
Hình 15: HÌnh ảnh output của file lex.yy.c ............................................................................ 53
Hình 16: Xây dựng oạn mã phân tích cú pháp ....................................................................... 54
Hình 17: Xây dựng oạn mã phân tích cú pháp (tiếp) ............................................................. 54
Hình 18:Chạy lệnh bison -d .\parser.y ................................................................................... 59
Hình 19: Ouput sau câu lệnh bison -d .\parser.y .................................................................... 60
Hình 20: Hình ảnh cho file parser.tab.h ................................................................................. 60
Hình 21: Chạy lệnh gcc .\lex.yy.c .\parser.tab.c ..................................................................... 61
Hình 22:Nhập lệnh .\a.exe ể cho ứng dụng hoạt ộng ............................................................. 62
Hình 23: Thử nhiệm với phép tính ơn giản ............................................................................ 62
Hình 24: Thử nhiệm với phép tính ơn giản (tiếp) .................................................................. 62
Hình 25: Thử nhiệm với phép tính rắc rối hơn (tiếp)............................................................. 62
Hình 26:Thử nghiệm với lỗi sai ............................................................................................. 63
Hình 27:Thử nhiệm với lỗi sai (tiếp) ..................................................................................... 63
Hình 28:Giao diện tải xuống của trang web .......................................................................... 65
Hình 29:Giao diện ban ầu của Graphviz setup ...................................................................... 66
Hình 30: Giao diện iều khoản người dùng ............................................................................. 66
Hình 31: Giao diện Install option ........................................................................................... 67
Hình 32:Giao diện chọn vị trí cài ặt ....................................................................................... 68
Hình 33:Ví dụ ường dẫn ến folder bin ................................................................................... 68
Hình 34:Lựa chọn nút bấm Enviroment Variables ................................................................. 69
Hình 35:Thêm biến môi trường ở cả hai phần, cách làm tương tự nhau ............................... 70
Hình 36: Hiển thị cho thấy ứng dụng ược cài ặt thành công ................................................. 71
Hình 37:Thuật toán tìm kiếm các closure cho một văn phạm ............................................... 85
Hình 38:Thuật toán xây dựng LR(1) ...................................................................................... 87
Danh mục bảng biểu
Table 1:Bảng phân công công việc trong nhóm .......................................................... 5 4 1. Giới thiệu 1.1 Mở ầu
Đây là báo cáo với ề tài ‘Tìm hiểu về bộ phân tích cú pháp Bison’ thuộc học phần
Chương trình dịch. Được thực hiện bởi nhóm chúng tôi gồm ba thành viên là Hoàng Văn Phú,
Nguyễn Thế Toại và Hoàng Anh Tuấn. Dưới ây là bảng phân công nhiệm vụ thành viên trong nhóm:
Table 1:Bảng phân công công việc trong nhóm Tên thành viên MSSV
Nhiệm vụ thực hiện thực hiện Hoàng Anh Tuấn 21012902
2.1.1 Giới thiệu về bộ phân tích cú pháp
2.1.2 Vai trò trong chương trình dịch
2.1.3 Nêu ặc iểm, yêu cầu của bộ phân tích cú pháp Hoàng Văn Phú 21010654
2.1.4 Giới thiệu bộ phân tích cú pháp Bison
2.1.5 Hướng dẫn cài ặt
2.1.6 Phân tích bộ phân tích cú pháp Bison
2.1.7 Xây dựng chương trình minh họa
2.1.8 Tổng kết vấn ề Rà soát
Nguyễn Thế Toại 21012898 1. Giới thiệu 3. Kết luận
2.1.1.1 Lịch sử phát triển của bộ phân tích cú pháp
2.2 Xây dựng biểu ồ LALR từ ngữ pháp
bằng Bison và so sánh với bản vẽ tay Lên nội dung. Cấu hình lại văn bản. 1.2 Đặt vấn ề
Để nói về lịch sử của những bộ phân tích cú pháp, phải nói các bộ phân tích cú pháp
ã xuất hiện gắn liền với những chiếc máy tính ầu tiên của thế giới. Vào giai oạn trước ó, con
người ra lệnh cho máy móc bằng các thao tác như nút bấm, cần gạt, công tắc. Khi tạo ra máy
tính, việc cung cấp dữ liệu và iều khiển không chỉ ơn giản như vậy, cần có một ngôn ngữ
nào ấy mới ủ ể ra lệnh và truyền tải thông tin. 5 lOMoARcPSD|48045915
Ngôn ngữ của máy tính lại thường quá phức tạp và khó hiểu. Nhưng với máy tính, ngôn ngữ
của con người cũng lại rất khó hiểu và mập mở, dài dòng. Vậy nên, con người ã sáng tạo ra
những ngôn ngữ trung gian, ơn giản mà chặt chẽ, một câu nói chỉ mang tới một ý nghĩa, rõ
ràng hơn so với ngôn ngữ tự nhiên hàng ngày và cũng phải thật ơn giản ể qua ó mà tương
tác với máy tính. Các ngôn ngữ lập trình cũng từ ó mà ra ời. Nhưng máy tính cũng không
hiểu ược các ngôn ngữ trung gian, nên con người ã tạo ra một công cụ có thể nói là người
phiên dịch hay còn ược gọi là chương trình dịch ể làm thứ tương tác giữa con người và máy móc.
Điều cơ bản và cần thiết cho mọi chương trình dịch ó là chức năng phân tích cú pháp. Nhờ
có chức năng này, các giai oạn sau của một chương trình dịch mới có thể hoạt ộng chính xác,
hợp lý. Có bộ phân tích cú pháp càng mạnh, thì việc giao tiếp giữa con người và máy tính
lại càng ược nâng cao. Chính vì vậy có rất nhiều bộ phân tích cú pháp ược sinh ra trong suốt
quá trình phát triển của máy tính. Các bộ phân tích cú pháp này không ngừng ược cải tiến
theo những thuật toán, công thức mới và tối tân nhất.
Ngày nay, các bộ phân tích cú pháp nổi tiếng và ược ứng dụng rộng rãi như ANTLR,
Bison,… vẫn là những công cụ giúp công việc phân tích cú pháp tốt và áp ứng gần như các
yêu cầu của một bộ phân tích cú pháp cần có.
1.3 Giới thiệu về Bison.
Bison (hay GNU Bison) nổi lên như là một công cụ hữu hiệu và áng tin cậy cho việc
phân tích cú pháp. Bison là một trình sinh cú pháp LALR (Look-Ahead LR) mã nguồn mở,
ược sử dụng rộng rãi trong các dự án lớn như trình biên dịch GCC và trình dịch cho nhiều ngôn ngữ khác nhau.
Với khả năng xử lý cú pháp phức tạp, Bison cung cấp một cách tiếp cận linh hoạt và
mạnh mẽ ể xây dựng các bộ phân tích cú pháp. Nó cho phép lập trình viên ịnh nghĩa các quy
tắc cú pháp trong một tệp nguồn dễ ọc, sau ó Bison sẽ tự ộng tạo ra mã nguồn C thực hiện
việc phân tích cú pháp theo các quy tắc ã ịnh nghĩa.
Với sự linh hoạt và hiệu quả của mình, Bison trở thành lựa chọn hàng ầu cho việc
phát triển chương trình dịch hiện ại, giúp áp ứng các yêu cầu ngày càng phức tạp của các
ngôn ngữ lập trình mới. Bằng cách sử dụng Bison, các nhà phát triển có thể tập trung vào
việc xây dựng các tính năng và công cụ mới, trong khi vẫn ảm bảo tính chính xác và hiệu
quả trong quá trình phân tích cú pháp.
Với sự lâu ời, phổ biến trong cộng ồng chương trình dịch, Bison vẫn chưa ược phổ
biến trong các học liệu của Việt Nam, vậy nên ể tìm hiểu về Bison, ề tài này ược sinh ra
với mục ích tìm hiểu về bộ phân tích cú pháp Bison. 6
Nội dung chính của báo cáo bao gồm hai phần, phần ầu tiên là tìm hiểu về bộ phân
tích cú pháp nói chung (ý nghĩa, ặc iểm) và i sâu vào phân tích bộ phân tích cú pháp Bison,
thông qua phân tích cú pháp, sẽ tạo ra một chương trình mẫu ể thử nghiệm các tính năng,
ưu iểm của Bison. Phần hai là so sánh Bison với bộ phân tích mà Bison ã dựa vào: LALR,
qua ó, tìm hiểu các iểm khác biệt, iểm nổi bật của Bison so với LALR.
Hình 1:Hình ảnh nhận diện của Bison 2. Nội dung
2.1 Tìm hiểu về bộ sinh PTCP Bison
Để bắt ầu tìm hiểu về bộ phân tích cú pháp Bison, trước hết phải hiểu ược bộ phân tích
cú pháp là gì ? Tại sao các bộ phân tích cú pháp lại ược sinh ra và sinh ra với mục ích phục 7 lOMoARcPSD|48045915
vụ cho iều gì. Vai trò của chúng trong ngành chương trình dịch hiện nay. Yêu cầu cơ bản cho
một bộ phân tích cú pháp ể gọi là tốt trong thời ại hiện nay.
2.1.1 Giới thiệu về bộ phân tích cú pháp
2.1.1.1 Lịch sử phát triển của bộ phân tích cú pháp
Sự phát triển của bộ phân tích cú pháp gần như i liền với chương trình dịch, tức là bộ
phân tích cú pháp cũng gắn liền với sự ra ời của chiếc máy tính ầu tiên. Trong những năm từ
1940 ến 1950, khi máy tính ược ra ời với nhiều hạn chế và chỉ có những tập oàn, cơ quan lớn
mới có thể sử dụng. Những nhà khoa học khi ấy ã nhận ra tiềm năng to lớn của chiếc máy
tính và ã tìm hiểu cách ể mà cho con người có thể giao tiếp với máy tính. Đó chính là lúc mà
bộ phân tích cú pháp ra ời.
Trong giai oạn ầu tiên, vào khoảng những năm 1950, trong những ngày ầu của máy
tính. Trình biên dịch ầu tiên ược thiết kế ể dịch các chương trình viết bằng Fortran sang mã
máy. Sự xuất hiện của Fortran là cột mốc trong ngành máy tính, vì nó cho phép người dùng
viết chương trình bằng ngôn ngữ cấp cao thay vì mã máy giúp viết và duy trì các chương
trình dễ dàng hơn. Trong giai oạn này, bộ phân tích cú pháp ược i cùng với các trình biên dịch.
Trong giai oạn kế tiếp, trong khoảng từ 1960 ến 1970, khi máy tính ã tiếp cận ược
nhiều ối tượng hơn. Nhu cầu về trình biên dịch lại càng ngày càng tăng lên, nhờ ó mà các
trình biên dịch mới phức tạp và hiệu quả hơn. Vì vậy các bộ phân tích cú pháp mạnh mẽ cũng
dần xuất hiện. Các thuật toán phân tích cú pháp trong giai oạn này chính là nền móng quan
trọng trong sự phát triển của lĩnh vực xử lý ngôn ngữ tự nhiên và thiết kế trình biên dịch.
Chúng trở thành cơ sở lý thuyết và thực tiễn cho nhiều công nghệ ngôn ngữ sau này. Có thể
nói ến các thuật toán như CYK ược phát minh bởi John Cocke, Daniel Younger và Tadao
Kasami, thuật toán này ã trở thành một trong những thuật toán cơ bản nhất trong phân tích
cú pháp. Thuật toán Earley ược phát minh bở Jay Earley vào năm 1968, là một thuật toán
phân tích cú pháp quan trọng nhất cho ngữ pháp phi ngữ cảnh với các trường hợp ngữ pháp
có tính a nghĩa cao. Hay bộ phân tích cú pháp Yacc ược phát triển bởi Stephen C.Johnson xây
dựng trên thuật toán LALR và trở thành công cụ phổ biến trong việc xây dựng trình biên dịch.
Trong giai oạn tiếp theo khoảng từ 1980 ến 2000, một hướng lập trình mới mà ến nay
vẫn cần phải học và em ến nhiều ích lợi ó chính là lập trình hướng ối tượng OOP mà ngôn
ngữ lập trình tiêu biểu ó chính là Java và C/ C++. Việc xuất hiện mô hình lập trình này ã em
ến những thay ổi áng kể trong thiết kế trình biên dịch. Mà trong ó các trình biên dịch i cùng
bộ phân tích cú pháp bao gồm trình biên dịch C sử dụng bộ phân tích ANTLR hoặc Bison.
Trình biên dịch Java sử dụng bộ phân tích JavaCup ể tạo bộ phân tích cú pháp LALR cho Java. 8
Trong giai oạn từ 2000 ến hiện nay, các trình biên dịch vẫn tiếp tục ược cải thiện và
nhờ ó, các bộ phân tích cú pháp lại tiếp tục ược phát triển và cải thiện nhằm tối ưu cho các trình biên dịch.
2.1.1.2 Hoạt ộng của một bộ Phân tích cú pháp
Về cơ bản, các bộ phân tích cú pháp ều có chung về cách hoạt ộng, nếu i sâu vào chi
tiết hơn sẽ thấy sự khác biệt trong việc phân tích (về thuật toán). Dưới ây là những iểm chung
về cách hoạt ộng và cấu trúc trong các bộ phân tích cú pháp:
Thứ nhất, tách từ (Tokenization) Quá trình này bắt ầu bằng việc chia chuỗi ký tự ầu
vào thành các phần tử cơ bản, gọi là "token". Tách từ thường bao gồm việc loại bỏ các ký tự
không mong muốn như dấu cách, tab, và dấu xuống dòng, cũng như phân biệt giữa các từ
vựng, dấu câu, và các thành phần khác trong ngôn ngữ. Các token tạo ra từ quá trình này sẽ
là ầu vào cho bước tiếp theo của quá trình phân tích cú pháp.
Thứ hai, phân tích cú pháp, Trong bước này, bộ phân tích cú pháp sử dụng các quy tắc
ngữ pháp ã ược ịnh nghĩa trước ể phân tích cú pháp của các token. Bộ phân tích kiểm tra xem
các token có tuân theo cú pháp của ngôn ngữ không và xác ịnh cấu trúc ngữ pháp của chuỗi
ký tự dựa trên các quy tắc này. Nếu chuỗi ký tự không tuân theo bất kỳ quy tắc nào, bộ phân
tích sẽ phát hiện và báo cáo lỗi cú pháp.
Thứ ba, xây dựng cấu trúc dữ liệu Sau khi phân tích cú pháp hoàn tất, bộ phân tích tạo
ra một biểu diễn cấu trúc dữ liệu cho cấu trúc ngữ pháp của mã nguồn. Cây cú pháp (AST)
là một biểu diễn phổ biến, trong ó mỗi nút trong cây ại diện cho một phần của cấu trúc ngữ
pháp, và mỗi cặp nút cha-con ại diện cho mối quan hệ giữa các thành phần của ngôn ngữ.
Thứ tư, các bộ phân tích ều có quy tắc ngữ pháp Các bộ phân tích cú pháp ều sử dụng
một tập hợp các quy tắc ngữ pháp ược ịnh nghĩa trước ể phân tích cú pháp của chuỗi ký tự
ầu vào. Quy tắc ngữ pháp này thường ược biểu diễn dưới dạng ngữ pháp hình thức hoặc ngữ
pháp miền phẳng, và xác ịnh cấu trúc ngữ pháp của ngôn ngữ.
Thứ năm, về khả năng xác ịnh cấu trúc ngữ pháp Một iểm chung khác là bộ phân tích
cú pháp xác ịnh cấu trúc ngữ pháp của chuỗi ký tự ầu vào, giúp hiểu cách các thành phần
trong ngôn ngữ ược tổ chức và tương tác với nhau. Cấu trúc ngữ pháp này thường ược biểu
diễn bằng cách sử dụng các biểu diễn dữ liệu như cây cú pháp (AST), giúp cho việc xử lý và
phân tích tiếp theo trở nên dễ dàng hơn.
Thứ sáu, khả năng phát hiện và báo cáo lỗi: Nếu có lỗi cú pháp trong chuỗi ký tự ầu
vào, các bộ phân tích cú pháp ều có khả năng phát hiện và báo cáo lỗi. Thông báo lỗi cú pháp
giúp cho người lập trình có thể sửa chữa các lỗi và cải thiện chất lượng của mã nguồn.
2.1.1.3 Tác ộng của bộ phân tích cú pháp ến việc biên dịch 9 lOMoARcPSD|48045915
Tác ộng của bộ phân tích cú pháp ến quá trình biên dịch trong ngành phần mềm là
không thể phủ nhận. Dưới ây là một số iểm chi tiết về tác ộng này:
Thứ nhất, xác ịnh cấu trúc cú pháp: Bộ phân tích cú pháp giúp xác ịnh cấu trúc ngữ
pháp của mã nguồn. Bằng cách phân tích các oạn mã, nó xác ịnh các thành phần như biến,
hàm, câu lệnh và cấu trúc iều khiển. Điều này quan trọng ể biên dịch có thể hiểu và xử lý mã úng cách.
Thứ hai, phát hiện và báo cáo lỗi cú pháp: Bộ phân tích cú pháp giúp phát hiện các lỗi
cú pháp trong mã nguồn. Nếu có lỗi ược phát hiện, nó sẽ cung cấp thông báo lỗi chi tiết giúp
người lập trình dễ dàng xác ịnh và sửa chữa lỗi.
Thứ ba, tạo ra biểu diễn cấu trúc: Sau khi phân tích cú pháp, bộ phân tích tạo ra một
biểu diễn cấu trúc của mã, thường là một cây cú pháp hoặc một biểu diễn dữ liệu tương ương.
Biểu diễn này là cơ sở cho các bước xử lý tiếp theo trong quá trình biên dịch.
Thứ tư, hỗ trợ phân tích ngữ nghĩa: Một số bộ phân tích cú pháp cũng có khả năng hỗ
trợ phân tích ngữ nghĩa, bao gồm kiểm tra tính hợp lệ của cấu trúc ngữ pháp và gắn thông
tin ngữ nghĩa vào cây cú pháp. Điều này ảm bảo rằng mã nguồn ược biên dịch úng cách và
tuân thủ ngữ cảnh của ngôn ngữ.
Thứ năm, tạo mã ối tượng hoặc mã máy: Bộ phân tích cú pháp có thể tạo ra ầu ra tương
ương như mã trung gian hoặc mã máy sau khi ã phân tích cú pháp.
Điều này là bước quan trọng ể tiếp tục quá trình biên dịch và thực thi mã.
Tóm lại, bộ phân tích cú pháp óng vai trò quan trọng trong quá trình biên dịch và có
ảnh hưởng sâu rộng ến hiệu suất và chất lượng của các công cụ biên dịch trong ngành công nghiệp phần mềm.
2.1.1.4 Các bộ phân tích cú pháp phổ biến
Các bộ phân tích cú pháp phổ biến ngày nay bao gồm Bison, ANTLR, Yacc, và
LLParser. Mỗi loại có ưu iểm và nhược iểm riêng: Bison
Bison là một công cụ phân tích cú pháp ược sử dụng rộng rãi trong việc tạo ra trình
biên dịch và trình thông dịch. Nó sử dụng ngôn ngữ ặc biệt gọi là Bison Declaration File
(yacc) ể mô tả cú pháp của ngôn ngữ. 10
Ưu iểm: Thứ nhất, Bison ược sử dụng rộng rãi và có sẵn cho nhiều hệ thống vận hành
khác nhau. Có khả năng sinh mã bằng ngôn ngữ C, C++, hoặc Java, làm cho nó phù hợp với
nhiều dự án khác nhau.Thứ hai, cung cấp khả năng tùy biến cao cho người dùng, giúp tạo ra
các bộ phân tích cú pháp a dạng và mạnh mẽ.
Nhược iểm: Cú pháp của Bison không linh hoạt bằng một số công cụ phân tích cú
pháp khác, ặc biệt là trong việc xử lý các ngôn ngữ không phải là ngôn ngữ chính thống như Python hay JavaScript.
ANTLR (ANother Tool for Language Recognition):
ANTLR là một công cụ phân tích cú pháp và tạo ra trình biên dịch có thể tái sử dụng
cho nhiều ngôn ngữ khác nhau. Nó sử dụng một cú pháp ặc biệt ể mô tả ngữ pháp của ngôn ngữ.
Ưu iểm: Hỗ trợ nhiều ngôn ngữ ích, bao gồm Java, C#, Python và JavaScript. Cung
cấp cách tiếp cận ơn giản và mạnh mẽ cho việc xử lý cú pháp và ngữ nghĩa. Hỗ trợ tái sử
dụng mã và kỹ thuật tái sử dụng ngôn ngữ.
Nhược iểm: Cú pháp của ANTLR có thể phức tạp và khó hiểu hơn so với một số công
cụ khác. Hiệu suất của ANTLR có thể không cao như Bison trong một số trường hợp sử dụng.
Yacc (Yet Another Compiler Compiler):
Yacc là một công cụ phân tích cú pháp dùng ể tạo ra trình biên dịch hoặc trình thông
dịch cho các ngôn ngữ lập trình. Nó sử dụng một cú pháp ặc biệt ể mô tả cú pháp của ngôn ngữ.
Ưu iểm: Được sử dụng rộng rãi từ thập niên 1970 và có thư viện phong phú. Đơn giản
và dễ hiểu, ặc biệt là cho các dự án với yêu cầu cú pháp không quá phức tạp. Hỗ trợ cho nhiều
ngôn ngữ lập trình như C và C++.
Nhược iểm: Yacc không cung cấp tính linh hoạt và mở rộng như Bison hoặc ANTLR.
Cú pháp của Yacc có thể khá cứng nhắc và không ủ mạnh mẽ cho các ngôn ngữ ngày nay.
LLParser (Top-down Parser):
LLParser là một công cụ phân tích cú pháp thường ược sử dụng cho việc phân tích cú
pháp của ngôn ngữ có cấu trúc ơn giản. Nó hoạt ộng dựa trên phương pháp top-down parsing. 11 lOMoARcPSD|48045915
Ưu iểm: Thường ược sử dụng cho việc phân tích cú pháp của ngôn ngữ có cấu trúc ơn
giản. Dễ hiểu và dễ triển khai. Thích hợp cho việc xây dựng các bộ phân tích cú pháp nhỏ và nhẹ.
Nhược iểm: Không phù hợp cho việc xử lý các ngôn ngữ có cấu trúc phức tạp. Không
ủ mạnh mẽ ể xử lý các ngôn ngữ với ặc iểm ộng và linh hoạt.
2.1.1.5 Những yêu cầu cần có của một bộ phân tích cú pháp hiện ại Phân Tích
Ngữ Nghĩa (Semantic Analysis):
Ngoài việc ảm bảo tính hợp lệ của cú pháp, phân tích ngữ nghĩa còn kiểm tra tính hợp
lệ của cấu trúc ngữ pháp và gắn thông tin ngữ nghĩa vào cây cú pháp. Điều này bao gồm kiểm
tra kiểu dữ liệu, phạm vi biến, và tính úng ắn của cấu trúc ngữ pháp.
Ví dụ: Xác ịnh xem một biến có ược sử dụng trong phạm vi hiện tại hay không. Kiểm
tra xem một phương thức có ược gọi với các ối số úng kiểu hay không.
Tạo Mã Trung Gian (Intermediate Code Generation):
Sau khi phân tích cú pháp, bộ phân tích có thể tạo ra mã trung gian, là một biểu diễn
dữ liệu tương ương của mã nguồn. Mã trung gian này thường dùng cho các bước xử lý tiếp
theo như tối ưu hóa hoặc tạo mã máy.
Ví dụ: Chuyển ổi oạn mã từ ngôn ngữ nguồn sang ngôn ngữ trung gian như mã
bytecode Java hoặc mã trung gian LLVM.
Tối Ưu Hóa (Optimization):
Tối ưu hóa mã nguồn ể cải thiện hiệu suất thực thi và tối ưu sử dụng tài nguyên.
Ví dụ: Loại bỏ mã không sử dụng, tối ưu hóa vòng lặp, hoặc biến ổi mã ể giảm ộ phức tạp thời gian thực thi.
Xác Định Cấu Trúc (Structural Analysis):
Phân tích và hiểu cấu trúc của hệ thống phần mềm, từ các phần tử cơ bản như biến và
hàm ến các ối tượng lớn hơn như modules, classes, hoặc packages. 12
Ví dụ: Xác ịnh các quan hệ giữa các lớp và modules trong một ứng dụng lớn, phân
tích cấu trúc của một dự án phần mềm ể xác ịnh các thành phần chính và mối quan hệ giữa chúng.
Hỗ Trợ Kiểm Tra Lỗi (Error Checking):
Phát hiện và báo cáo các loại lỗi trong mã nguồn, bao gồm cả lỗi cú pháp, lỗi ngữ
nghĩa, và lỗi luồng iều khiển.
Ví dụ: Báo lỗi khi gặp một cú pháp không hợp lệ, một biến chưa ược khai báo, hoặc
một lệnh gây ra xung ột tên.
2.1.2 Vai trò trong chương trình dịch
2.1.2.1 Vai trò, ý nghĩa Phân Tích Cú Pháp:
Bộ phân tích cú pháp chịu trách nhiệm phân tích cú pháp của mã nguồn, tức là quá
trình phân tích và kiểm tra tính hợp lệ của cú pháp theo quy tắc ã ược ịnh nghĩa trước ó. Nó
giúp xác ịnh cấu trúc ngữ pháp của chương trình, từ ó ảm bảo rằng mã nguồn tuân theo cấu
trúc và quy tắc của ngôn ngữ ích.
Bộ phân tích cú pháp là bước ầu tiên và quan trọng nhất trong quá trình dịch. Nó ảm
bảo rằng mã nguồn ược viết theo cú pháp úng của ngôn ngữ, giúp máy tính hiểu ược ý nghĩa
của mã nguồn và thực hiện các tác vụ mong muốn.
Trong chương trình dịch Python, bộ phân tích cú pháp phân tích cú pháp của mỗi dòng
mã nguồn. Ví dụ, khi gặp câu lệnh for i in range(5):, bộ phân tích cú pháp xác ịnh rằng ây là
một vòng lặp for với biến i chạy từ 0 ến 4. Điều này giúp chương trình dịch hiểu ược cấu trúc
của vòng lặp và thực hiện các lệnh bên trong úng cách.
Xây Dựng Cây Cú Pháp:
Sau khi phân tích cú pháp, bộ phân tích tạo ra một cây cú pháp hoặc một biểu diễn dữ
liệu tương ương. Cấu trúc này giúp biểu diễn rõ ràng và hiểu rõ hơn cấu trúc của chương
trình, tạo iều kiện thuận lợi cho các bước xử lý tiếp theo như phân tích ngữ nghĩa và tạo mã. 13 lOMoARcPSD|48045915
Tác dụng của việc xây dựng cây cú pháp: Thứ nhất, giúp hiểu rõ cấu trúc của ngôn
ngữ: Cây cú pháp giúp biểu diễn cấu trúc ngữ pháp của mã nguồn một cách rõ ràng và logic.
Nó thể hiện cách mà các yếu tố ngữ pháp ược tổ chức và tương tác với nhau trong mã
nguồn.Thứ hai, dễ dàng cho các bước xử lý tiếp theo: Cây cú pháp cung cấp một cấu trúc dữ
liệu tương ương cho mã nguồn, giúp cho các bước xử lý tiếp theo trong quá trình dịch có thể
ược thực hiện một cách dễ dàng và hiệu quả hơn. Tại sao việc xây dựng cây cú pháp quan trọng:
Đảm bảo tính úng ắn: Việc xây dựng cây cú pháp ảm bảo rằng cấu trúc của mã nguồn
ược hiểu và biểu diễn úng ắn. Điều này là quan trọng ể ảm bảo chương trình dịch có thể hiểu
và thực hiện mã nguồn một cách chính xác.
Hỗ trợ cho các pha xử lý tiếp theo: Cấu trúc dữ liệu của cây cú pháp cung cấp cơ sở
cho các bước xử lý ngữ nghĩa, tạo mã trung gian, hoặc sinh mã máy. Việc có cây cú pháp úng
ắn là bước quan trọng ể tiếp tục các bước xử lý tiếp theo một cách chính xác.
Ví dụ về việc xây dựng cây cú pháp:
Trong ngôn ngữ lập trình C, cây cú pháp có thể biểu diễn cấu trúc của một biểu thức toán học.
Hình 2:Cây cú pháp biểu diễn cấu trúc toán học Kiểm Tra Lỗi:
Bộ phân tích cú pháp kiểm tra lỗi cú pháp trong mã nguồn và cung cấp thông báo lỗi cụ thể
nếu có. Qua ó, nó giúp tăng tính áng tin cậy và chính xác của chương trình dịch, ồng thời
giúp người lập trình phát hiện và sửa chữa lỗi một cách dễ dàng và nhanh chóng.
Tác dụng của việc kiểm tra lỗi: 14
Thứ nhất, ảm bảo tính úng ắn: Việc kiểm tra lỗi cú pháp giúp ảm bảo rằng mã nguồn
tuân theo cú pháp của ngôn ngữ ược ịnh nghĩa trước ó. Điều này ảm bảo rằng chương trình
có thể ược biên dịch hoặc dịch một cách chính xác.
Thứ hai, phát hiện và sửa chữa lỗi: Việc phát hiện và báo cáo lỗi cú pháp giúp cho
người lập trình có thể xác ịnh và sửa chữa các vấn ề cú pháp trong mã nguồn của họ một cách
nhanh chóng và hiệu quả.
Tại sao việc kiểm tra lỗi quan trọng:
Thứ nhất, ngăn chặn lỗi trước khi chương trình thực thi: Việc phát hiện và sửa chữa
lỗi cú pháp trước khi chương trình ược thực thi là cực kỳ quan trọng ể tránh các vấn ề không
mong muốn xảy ra khi chương trình ang hoạt ộng.
Thứ hai, tăng tính áng tin cậy của chương trình: Một chương trình không có lỗi cú
pháp sẽ hoạt ộng một cách áng tin cậy hơn, giảm thiểu nguy cơ phát sinh lỗi và tăng khả năng
mở rộng và bảo trì của chương trình.
Ví dụ về việc kiểm tra lỗi: Trong ngôn ngữ lập trình Python, nếu một dòng mã kết thúc
mà thiếu dấu ngoặc óng, bộ phân tích cú pháp sẽ phát hiện lỗi và thông báo như sau:
Hình 3:Kiểm tra lỗi trong Python
Tạo Đầu Ra Tương Đương:
Khi hoàn thành quá trình phân tích cú pháp, bộ phân tích có thể tạo ra ầu ra tương
ương như mã trung gian hoặc mã máy. Điều này là bước quan trọng ể tiếp tục quá trình dịch
và thực thi chương trình.
Tác dụng của Tạo ầu ra tương ương :
Sau khi bộ phân tích cú pháp ã phân tích và xác ịnh cú pháp của mã nguồn, nhiệm vụ
tiếp theo là tạo ra ầu ra tương ương, thường là một biểu diễn cấu trúc dữ liệu tương ương hoặc mã trung gian. 15 lOMoARcPSD|48045915
Đầu ra này sẽ bao gồm thông tin về cấu trúc và ý nghĩa của oạn mã, giúp cho các bước
xử lý tiếp theo có thể ược thực hiện.
Tại sao nó lại quan trọng:
Đầu ra tương ương từ bộ phân tích cú pháp là cầu nối giữa việc phân tích cú pháp và
các bước xử lý tiếp theo trong quá trình biên dịch hoặc dịch.
Nó cung cấp thông tin cần thiết về cấu trúc ngữ pháp của mã nguồn, giúp cho việc xử
lý ngữ nghĩa và tạo ra mã nguồn ược thực hiện một cách dễ dàng hơn.
Ví dụ về vai trò này: Trong một trình biên dịch ngôn ngữ lập trình, sau khi bộ phân
tích cú pháp ã phân tích cú pháp của mã nguồn, nó có thể tạo ra ầu ra tương ương dưới dạng
cây cú pháp hoặc mã trung gian. Ví dụ, ối với mã nguồn C, ầu ra tương ương có thể là mã
trung gian trong dạng mã Assembly hoặc mã trung gian trong dạng bytecode tùy thuộc vào
trình biên dịch cụ thể.
Hỗ Trợ Xử Lý Ngữ Nghĩa:
Một số loại bộ phân tích cú pháp còn hỗ trợ phân tích ngữ nghĩa bằng cách kiểm tra
tính hợp lệ của cấu trúc ngữ pháp và gắn thông tin ngữ nghĩa vào cây cú pháp.
Điều này óng vai trò quan trọng trong việc hiểu rõ hơn ý nghĩa của mã nguồn. Tác dụng:
Một trong những nhiệm vụ quan trọng của bộ phân tích cú pháp là hỗ trợ xử lý ngữ nghĩa của mã nguồn.
Sau khi ã phân tích cú pháp, bộ phân tích này có thể cung cấp thông tin về cấu trúc
ngữ pháp và giúp xác ịnh ý nghĩa của các thành phần trong mã nguồn, chẳng hạn như kiểu
dữ liệu, phạm vi biến, hoặc các quy tắc ngữ pháp ặc biệt của ngôn ngữ.
Tại sao lại quan trọng: Xử lý ngữ nghĩa là bước tiếp theo quan trọng sau khi ã phân
tích cú pháp, giúp ảm bảo rằng các biến, hàm, hoặc các thành phần khác của chương trình
ược sử dụng một cách úng ắn và hợp lệ theo ngữ cảnh của ngôn ngữ. Việc này ảm bảo tính
úng ắn và hiệu quả của chương trình.
Ví dụ về vai trò: Trong một trình biên dịch ngôn ngữ lập trình, sau khi bộ phân tích cú
pháp ã phân tích cú pháp của mã nguồn, hỗ trợ xử lý ngữ nghĩa sẽ giúp xác ịnh và kiểm tra
tính hợp lệ của các biến, hàm, hoặc các thành phần khác trong mã nguồn. Ví dụ, nó có thể 16
kiểm tra việc sử dụng biến trong phạm vi của chúng, kiểm tra tính hợp lệ của các phép gán,
hoặc kiểm tra sự phù hợp giữa các kiểu dữ liệu.
Hỗ Trợ Tạo Trình Bản Dịch:
Bộ phân tích cú pháp thường là một phần của trình biên dịch hoàn chỉnh, cung cấp dữ
liệu cần thiết cho các phần khác của chương trình như trình tạo mã và trình tạo mã nguồn. Tác dụng:
Một trong những vai trò quan trọng của bộ phân tích cú pháp là hỗ trợ trong việc tạo
ra trình biên dịch hoặc trình dịch hoàn chỉnh.
Sau khi ã phân tích cú pháp và xử lý ngữ nghĩa của mã nguồn, bộ phân tích này cung
cấp dữ liệu cần thiết cho các phần khác của chương trình, như trình tạo mã và trình tạo mã nguồn. Tại sao lại quan trọng:
Quá trình biên dịch hoặc dịch một ngôn ngữ lập trình òi hỏi sự hỗ trợ từ bộ phân tích
cú pháp ể xác ịnh cấu trúc và ý nghĩa của mã nguồn.
Việc có một bộ phân tích cú pháp mạnh mẽ và hiệu quả giúp tạo ra trình biên dịch
hoặc dịch hoàn chỉnh có thể xử lý ược mã nguồn một cách chính xác và hiệu quả.
Ví dụ về vai trò này: Trong quá trình biên dịch một ngôn ngữ lập trình, sau khi ã phân
tích cú pháp và xử lý ngữ nghĩa, bộ phân tích cú pháp cung cấp dữ liệu về cấu trúc và ý nghĩa
của mã nguồn cho trình biên dịch hoặc dịch. Trình biên dịch hoặc dịch sẽ sử dụng thông tin
này ể tạo ra mã trung gian hoặc mã máy tương ứng, từ ó thực hiện các bước tiếp theo của quá
trình biên dịch hoặc dịch.
2.1.3 Nêu ặc iểm/ yêu cầu của bộ phân tích cú pháp
2.1.3.1 Đặc iểm của một bộ phân tích cú pháp Quy ịnh ngữ
pháp (Grammar Specification):
Bộ phân tích cú pháp cần có khả năng ọc và hiểu các quy tắc ngữ pháp ược ặc tả trước.
Điều này bao gồm việc phân tích cú pháp từ các quy tắc ngữ pháp chính xác, ược viết bằng
các ngôn ngữ như BNF (Backus-Naur Form) hoặc EBNF (Extended Backus-Naur Form). 17 lOMoARcPSD|48045915
Bộ phân tích cú pháp cần ọc và hiểu các quy tắc ngữ pháp ược ặc tả trước ể phân tích
cú pháp từ các quy tắc này, ảm bảo tính chính xác và ầy ủ của quá trình phân tích.
Ví dụ: Nếu không có quy ịnh ngữ pháp, bộ phân tích có thể không hiểu ược cú pháp
của mã nguồn và dẫn ến lỗi phân tích.
Nhận dạng cấu trúc (Structure Recognition):
Bộ phân tích cú pháp phải có khả năng nhận dạng cấu trúc cú pháp của mã nguồn.
Điều này òi hỏi nó phải có thể phân tích và hiểu cú pháp của các thành phần trong ngôn ngữ,
như biểu thức, lệnh và khai báo.
Bộ phân tích cú pháp cần nhận dạng cấu trúc cú pháp của mã nguồn ể hiểu cú pháp
của các thành phần trong ngôn ngữ, như biểu thức, lệnh và khai báo.
Ví dụ: Nếu không nhận dạng ược cấu trúc, bộ phân tích có thể không thể hiểu ược ý
nghĩa của mã và dẫn ến lỗi phân tích.
Xử lý Token (Tokenization):
Đầu vào của bộ phân tích cú pháp thường là một dãy các token hoặc từ vựng ược tạo
ra từ quá trình từ vựng hóa (lexical analysis). Bộ phân tích cú pháp cần phải có khả năng
nhận dạng và xử lý các token này ể xác ịnh cấu trúc cú pháp của ngôn ngữ.
Bộ phân tích cú pháp cần xử lý và nhận dạng các token từ mã nguồn ể xác ịnh cấu trúc cú pháp của ngôn ngữ.
Ví dụ: Nếu không xử lý ược token, bộ phân tích không thể hiểu ược cấu trúc của mã
và dẫn ến lỗi phân tích.
Xây dựng cấu trúc dữ liệu (Data Structure Building):
Sau khi phân tích cú pháp, bộ phân tích cú pháp cần phải tạo ra một cấu trúc dữ liệu
phù hợp ể biểu diễn cấu trúc của mã nguồn. Cấu trúc này thường ược biểu diễn dưới dạng
cây cú pháp hoặc các biểu diễn dữ liệu khác phù hợp với quá trình dịch tiếp theo.
Sau khi phân tích cú pháp, cần tạo ra một cấu trúc dữ liệu phù hợp ể biểu diễn cấu trúc của mã nguồn. 18
Ví dụ: Nếu không xây dựng ược cấu trúc dữ liệu, không thể tiếp tục quá trình dịch
hoặc tạo ra mã dịch không úng cú pháp.
Kiểm tra lỗi (Error Checking):
Bộ phân tích cú pháp cần kiểm tra lỗi cú pháp trong mã nguồn và cung cấp thông báo
lỗi cụ thể nếu có bất kỳ lỗi nào ược phát hiện. Điều này ảm bảo tính áng tin cậy và chính xác của quá trình dịch.
Đảm bảo tính áng tin cậy và chính xác của quá trình dịch bằng cách kiểm tra lỗi cú pháp trong mã nguồn.
Ví dụ: Nếu không kiểm tra ược lỗi, có thể dẫn ến việc dịch ra mã không hợp lệ hoặc có lỗi.
Tạo ra ầu ra tương ương (Equivalent Output Generation):
Một trong những nhiệm vụ chính của bộ phân tích cú pháp là tạo ra ầu ra tương ương
từ cấu trúc cú pháp của mã nguồn. Đầu ra này có thể là mã trung gian hoặc mã máy, tùy thuộc
vào quá trình dịch cụ thể.
Tạo ra ầu ra tương ương từ cấu trúc cú pháp của mã nguồn ể tiếp tục quá trình dịch.
Ví dụ: Nếu không tạo ra ầu ra tương ương, không thể tiếp tục quá trình dịch hoặc tạo
ra mã dịch không tương ương với mã nguồn.
Hỗ trợ xử lý ngữ nghĩa (Semantic Processing Support):
Một số bộ phân tích cú pháp cung cấp hỗ trợ cho việc phân tích ngữ nghĩa. Điều này
bao gồm kiểm tra tính hợp lệ của cấu trúc ngữ pháp và gắn thông tin ngữ nghĩa vào cấu trúc cú pháp.
Cung cấp hỗ trợ cho việc phân tích ngữ nghĩa, kiểm tra tính hợp lệ của cấu trúc ngữ
pháp và gắn thông tin ngữ nghĩa vào cấu trúc cú pháp.
Ví dụ: Hỗ trợ xử lý ngữ nghĩa giúp loại bỏ các lỗi hoặc không rõ ràng trong cú pháp.
Đa dạng hóa (Versatility): 19 lOMoARcPSD|48045915
Bộ phân tích cú pháp cần phải có khả năng hỗ trợ nhiều loại ngôn ngữ khác nhau và
có thể ược tùy chỉnh ể làm việc với các quy tắc ngữ pháp cụ thể của từng ngôn ngữ. Điều này
ảm bảo tính linh hoạt và mở rộng của bộ phân tích.
Bộ phân tích cú pháp cần linh hoạt và có thể ược tùy chỉnh ể làm việc với nhiều loại
ngôn ngữ và quy tắc ngữ pháp.
Ví dụ: Khả năng a dạng hóa giúp bộ phân tích cú pháp có thể sử dụng cho nhiều dự
án và môi trường lập trình khác nhau.
2.1.3.2 Yêu cầu Độ chính xác:
Xác ịnh chính xác cú pháp: Bộ phân tích cú pháp cần có khả năng xác ịnh úng và chính
xác cú pháp của mã nguồn. Điều này ảm bảo rằng mã nguồn sẽ ược phân tích theo úng cú
pháp của ngôn ngữ, không bỏ sót hay hiểu nhầm các cú pháp không hợp lệ.
Nhận diện lỗi: Nếu có lỗi cú pháp, bộ phân tích cú pháp cần phải nhận diện và báo cáo
cho người dùng biết ể có thể sửa chữa. Thông báo lỗi cần ược ưa ra một cách rõ ràng và ủ
thông tin ể người lập trình có thể hiểu và sửa ổi.
Tính thông minh: Bộ phân tích cú pháp cần có khả năng xử lý cú pháp phức tạp của
các ngôn ngữ lập trình và hiểu biết ngữ nghĩa phức tạp. Điều này ảm bảo rằng nó có thể phân
tích và diễn giải úng ý nghĩa của oạn mã.
Tại sao cần có iều này: Độ chính xác là một yếu tố quan trọng ể ảm bảo rằng bộ phân
tích cú pháp có thể xử lý mã nguồn một cách chính xác, tránh lỗi trong quá trình biên dịch hoặc dịch.
Ví dụ: Nếu bộ phân tích cú pháp không chính xác trong việc xác ịnh cú pháp của lệnh
iều kiện trong một ngôn ngữ lập trình, có thể dẫn ến việc mã ược biên dịch không úng và dẫn
ến lỗi hoặc hành vi không mong muốn trong chương trình kết quả. Hiệu suất:
Tốc ộ xử lý: Bộ phân tích cú pháp cần phải xử lý mã nguồn một cách nhanh chóng và
hiệu quả ể không làm chậm quá trình biên dịch hoặc dịch.
Tiêu tốn ít tài nguyên: Việc xử lý cú pháp cần tiêu tốn ít tài nguyên máy tính nhất có
thể ể tăng hiệu suất và tiết kiệm năng lượng. 20