Xem mẫu
- ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG CĐ CÔNG NGHỆ THÔNG TIN
BÁO CÁO TỔNG KẾT
ĐỀ TÀI KHOA HỌC VÀ CÔNG NGHỆ
CẤP CƠ SỞ
NGHIÊN CỨU ỨNG DỤNG LEX/YACC TRONG TỰ
ĐỘNG PHÁT SINH MÃ NGUỒN
Mã số: T2016-07-04
Chủ nhiệm đề tài: ThS. Dương Thị Mai Nga
Đà Nẵng, 12/2016
1
- ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG CĐ CÔNG NGHỆ THÔNG TIN
BÁO CÁO TỔNG KẾT
ĐỀ TÀI KHOA HỌC VÀ CÔNG NGHỆ
CẤP CƠ SỞ
NGHIÊN CỨU ỨNG DỤNG LEX/YACC TRONG TỰ
ĐỘNG PHÁT SINH MÃ NGUỒN
Mã số: T2016-07-04
Xác nhận của cơ quan chủ trì đề tài Chủ nhiệm đề tài
Đà Nẵng, 12/2016
2
- MỤC LỤC
MỞ ĐẦU ........................................................................................................... 8
CHƯƠNG 1: TỔNG QUAN VỀ TRÌNH BIÊN DỊCH .................................... 9
1.1. KHÁI NIỆM TRÌNH BIÊN DỊCH.................................................................................. 9
1.2. PHÂN TÍCH CHƯƠNG TRÌNH NGUỒN ................................................................... 10
TỔNG KẾT CHƯƠNG 1 ........................................................................................................ 14
CHƯƠNG 2: CÔNG CỤ LEX/ YACC .......................................................... 15
2.1. GIỚI THIỆU VỀ LEX/YACC ............................................................................................. 15
2.2. LEX ............................................................................................................................... 17
2.3. YACC ............................................................................................................................ 21
2.4. CÀI ĐẶT CÁC ỨNG DỤNG ............................................................................................ 25
TỔNG KẾT CHƯƠNG 2 ........................................................................................................ 25
CHƯƠNG 3: XÂY DỰNG CÔNG CỤ SINH MÃ NGUỒN......................... 26
3.1. GIỚI THIỆU NGÔN NGỮ ĐẶC TẢ TTT .................................................................... 26
3.1.1. Cấu trúc cơ bản của một chương trình ............................................................ 26
3.1.2. Các lệnh của ngôn ngữ TTT............................................................................... 26
3.1.3. Các thành phần khác ........................................................................................ 27
3.2. XÂY DỰNG GIẢI PHÁP DỊCH NGÔN NGỮ TTT SANG NGÔN NGỮ C ...................... 29
3.3. XÂY DỰNG TRÌNH BIÊN DỊCH VÀ THỬ NGHIỆM ................................................... 35
KẾT LUẬN VÀ KIẾN NGHỊ ......................................................................... 38
TÀI LIỆU THAM KHẢO ............................................................................... 39
PHỤ LỤC ........................................................................................................ 40
3
- DANH MỤC BẢNG BIỂU
Số hiệu bảng Tên bảng Trang
Bảng 2.1 Mô tả cách biểu diễn các biểu thức chính quy 18
Bảng 2.2 Biểu diễn một số ví dụ của biểu thức chính quy 18
Bảng 2.3 Danh sách các macro, biến được định nghĩa trước của lex 20
Bảng 3.1 Thứ tự ưu tiên các phép toán 28
Bảng chuyển đổi từ vựng giữa ngôn ngữ TTT và ngôn ngữ
Bảng 3.2 29
C
Bảng chuyển đổi cú pháp giữa ngôn ngữ TTT và ngôn ngữ
Bảng 3.3 31
C
Chuyển đổi các phép toán CTT của ngôn ngữ TTT sang
Bảng 3.4 33
ngôn ngữ C
4
- DANH MỤC CÁC HÌNH
Số hiệu hình Tên hình Trang
Hình 1.1 Một trình biên dịch 9
Hình 1.2 Giao diện của bộ phân tích từ vựng trong trình biên dịch 11
Hình 1.3 Giao diện của bộ phân tích cú pháp trong trình biên dịch 12
Cây phân tích cú pháp cho câu lệnh:
Hình 1.4 13
position := initial + rate * 60
Hình 2.1 Ví dụ trình tự biên dịch đoạn mã nguồn a = b + c * d 15
Hình 2.2 Quy trình vận dụng và cách đặt tên với Lex, Yacc 16
5
- DANH MỤC CÁC TỪ VIẾT TẮT
Từ viết tắt/
Tiếng Anh Tiếng Việt
Thuật ngữ
TTT Task Tree Test Kiểm thử cây nhiệm vụ
CTT Concur Task Tree Cây nhiệm vụ tương tranh
BNF Backus-Naur Form Hình thức BNF
6
- ĐẠI HỌC ĐÀ NẴNG CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM
TRƯỜNG CĐ CÔNG NGHỆ THÔNG TIN Độc lập – Tự do – Hạnh phúc
THÔNG TIN KẾT QUẢ NGHIÊN CỨU
1. Thông tin chung:
- Tên đề tài: Nghiên cứu ứng dụng Lex/Yacc trong tự động phát sinh mã nguồn
- Mã số: T2016-07-04
- Chủ nhiệm: Dương Thị Mai Nga
- Cơ quan chủ trì: Trường CĐ Công nghệ Thông tin – Đại học Đà Nẵng
- Thời gian thực hiện: từ 1/2016 đến 12/2016
2. Mục tiêu:
Áp dụng lý thuyết vào xây dựng công cụ ứng dụng vào việc phát sinh mã
nguồn sang ngôn ngữ lập trình C nhằm tạo điều kiện để tiếp tục nghiên cứu và xây
dựng việc tự động phát sinh ca kiểm thử từ ngôn ngữ mô hình hóa.
3. Tính mới và sáng tạo:
Nghiên cứu và ứng dụng công cụ trong việc xây dựng trình biên dịch, giúp
quá trình này được nhanh hơn.
4. Tóm tắt kết quả nghiên cứu:
Đã nghiên cứu về trình biên dịch, các công cụ hỗ trợ xây dựng trình biên
dịch và xây dựng được trình biên dịch dựa trên những nghiên cứu đó.
5. Tên sản phẩm:
Công cụ chuyển mã nguồn từ ngôn ngữ đặc tả TTT sang ngôn ngữ C.
6. Hiệu quả, phương thức chuyển giao kết quả nghiên cứu và khả năng áp
dụng:
Có thể sử dụng nghiên cứu này và áp dụng vào quá trình tự động sinh ca
kiểm thử cho các ứng dụng tương tác được đặc tả bằng ngôn ngữ TTT.
Đà Nẵng, ngày 08 tháng 12 năm 2016
Cơ quan chủ trì Chủ nhiệm đề tài
7
- MỞ ĐẦU
Ngày nay song song với sự phát triển các thiết bị phần cứng là sự phát triển
các kĩ thuật phát triển phần mềm. Bài toán đặt ra là làm thế nào để lập trình nhanh,
hiệu quả và độ chính xác cao, một trong những kĩ thuật đảm bảo những yêu cầu trên
là kĩ thuật tự động phát sinh mã nguồn.
Phần mềm hiện nay được sử dụng rộng rãi trong đời sống, trong nhiều lĩnh
vực khoa học, kinh tế và xã hội. Vì vậy, việc xây dựng phần mềm đáp ứng mong
muốn của người sử dụng là đòi hỏi quan trọng. Đó là mong muốn về độ chính xác,
tính ổn định, tính tương thích và giá thành của các ứng dụng. Giá thành của ứng
dụng phụ thuộc vào chi phí trong quá trình phát triển, Làm thế nào để lập trình
nhanh và hiệu quả nhất cho một bài toán luôn là cơ sở để các phương pháp, kĩ thuật
và ngôn ngữ lập trình ra đời. Một trong những kĩ thuật ra đời sớm và phát triển là kĩ
thuật tự động phát sinh mã nguồn. Hiện nay có nhiều công cụ hỗ trợ phát sinh mã
nguồn như Lex/Yacc, Antlr…. Công cụ Lex/Yacc hỗ trợ tự động sinh ra mã nguồn
C hoặc Pascal, Antlr hỗ trợ việc tạo mã cho nhiều ngôn ngữ hơn bao gồm C++,
Java, Python, C#. Trong nghiên cứu của mình tác giả chọn công cụ Lex/Yacc và đề
xuất đề tài “Nghiên cứu ứng dụng Lex/Yacc trong tự động phát sinh mã nguồn”
nhằm rút ngắn thời gian sinh mã nguồn, dễ dàng trong việc bảo trì, từ đó góp phần
giảm giá thành sản phẩm.
Trong đề tài của mình, tác giả thực hiện nghiên cứu lý thuyết và áp dụng lý
thuyết vào xây dựng công cụ ứng dụng trong việc phát sinh mã nguồn trong ngôn
ngữ lập trình C nhằm tạo điều kiện để tiếp tục nghiên cứu và xây dựng việc tự động
phát sinh ca kiểm thử từ ngôn ngữ mô hình hóa. Trong nghiên cứu của mình tác giả
thực hiện những công việc sau: tìm hiểu văn phạm phi ngữ cảnh và ngôn ngữ lập
trình C; tìm hiểu công cụ Lex/Yacc; xây dựng cơ chế dịch ngôn ngữ; xây dụng công
cụ sinh mã nguồn trong ngôn ngữ lập trình C; kiểm tra, thử nghiệm và đưa ra nhận
xét, kết quả đạt được; viết báo cáo tổng kết đề tài.
8
- CHƯƠNG 1: TỔNG QUAN VỀ TRÌNH BIÊN DỊCH
Chương này tác giả trình bày về trình biên dịch, chức năng của trình biên dịch,
cấu trúc của trình biên dịch, môi trường hoạt động của trình biên dịch.
1.1. KHÁI NIỆM TRÌNH BIÊN DỊCH
Trình biên dịch, hay còn gọi là chương trình dịch, đơn giản là một chương
trình làm nhiệm vụ đọc một chương trình được viết bằng một ngôn ngữ (gọi là ngôn
ngữ nguồn) rồi dịch nó thành một chương trình tương đương ở một ngôn ngữ khác
(gọi là ngôn ngữ đích). Một phần quan trọng trong quá trình dịch là ghi nhận lại các
lỗi có trong chương trình nguồn để thông báo lại cho người viết chương trình.
Chương trình nguồn
Trình biên dịch Thông báo lỗi
Chương trình đích
Hình 1.1. Một trình biên dịch
Chỉ nhìn thoáng qua, số lượng trình biên dịch dường như quá nhiều. Có đến
hang ngàn ngôn ngữ nguồn, từ các ngôn ngữ lập trình truyền thống như Fortran và
C đến các ngôn ngữ chuyên dụng dành riêng cho từng lĩnh vực ứng dụng khác nhau.
Ngôn ngữ đích cũng đa dạng như thế; một ngôn ngữ đích có thể là một ngôn ngữ
lập trình khác, hoặc là một ngôn ngữ máy của một loại máy tính, từ máy tính PC
cho đến siêu máy tính. Trình biên dịch đôi khi cũng được phân thành các loại như
loại một lượt (single-pass), loại nhiều lượt (multi-pas), loại nạp và tiến hành (load-
and-go), loại gỡ rối (debugging) hoặc loại tối ưu hóa (optimizing), tùy vào cách
thức chúng ta xây dựng hoặc tùy vào chức năng mà chúng thực hiện. Mặc dù tính
chất phức tạp, nhiệm vụ cơ bản của mọi trình biên dịch đều như nhau. Nhờ hiểu rõ
được nhiệm vụ này mà chúng ta có thể xây dựng trình biên dịch cho rất nhiều loại
ngôn ngữ nguồn và ngôn ngữ đích bằng cách sử dụng các kỹ thuật cơ bản giống
nhau.
Hiểu biết của chúng ta về cách thức tổ chức và viết các trình biên dịch đã tiến
rất xa kể từ khi trình biên dịch đầu tiên xuất hiện vào đầu thập niên 50. Trong suốt
thập niên 50 đó, trình biên dịch đã được xem là những chương trình cực kỳ khó viết.
Từ đó chúng ta đã dần khám phá ra các kỹ thuật mang tính hệ thống để xử lý nhiều
nhiệm vụ quan trọng xảy ra trong quá trình biên dịch. Một số ngôn ngữ để cài đặt,
9
- các môi trường lập trình và các công cụ phần mềm cũng được phát triển. Với những
thành quả này, việc viết một trình biên dịch có chất lượng hiện đã dễ dàng hơn.
Công việc biên dịch có thể được chia thành hai phần: phân tích và tổng hợp.
Phần phân tích sẽ phân rã chương trình nguồn thành các phần cấu thành và tạo ra
một dạng biểu diễn trung gian cho chương trình nguồn. Phần tổng hợp sẽ xây dựng
ngôn ngữ đích từ dạng biểu diễn trung gian này.
1.2. PHÂN TÍCH CHƯƠNG TRÌNH NGUỒN
Khi biên dịch, quá trình phân tích bao gồm ba giai đoạn:
- Phân tích tuyến tính (linear analysis), trong đó các dòng ký tự tạo ra chương
trình nguồn sẽ được đọc từ trái sang phải và được nhóm lại thành các từ tố (thẻ từ -
token), đó là các chuỗi ký tự được hợp lại để tạo ra một nghĩa chung.
Phân tích cấu trúc phân cấp (hierarchical analysis), trong đó các ký tự hoặc
các thẻ từ được nhóm thành các nhóm lồng nhau theo kiểu phân cấp để tạo ra một
nghĩa chung.
Phân tích ngữ nghĩa (semantic analysis), trong đó thực hiện một số kiểm tra
để đảm bảo rằng các thành phần của chương trình kết lại với nhau một cách có
nghĩa.
Trong một trình biên dịch, phân tích tuyến tính được gọi là phân tích từ vựng
(lexical analysis) hay hành động quét nguyên liệu (scanning) là giai đoạn đầu tiên
của mọi trình biên dịch. Nhiệm vụ chủ yếu của nó là đọc các ký tự vào từ văn bản
chương trình nguồn và phân tích đưa ra danh sách các từ tố cùng một số thông tin
thuộc tính.
Đầu ra của bộ phân tích từ vựng là danh sách các từ tố và là đầu vào cho
phân tích cú pháp. Trên thực tế quá trình phân tích cú pháp sẽ gọi lần lượt mỗi từ tố
từ bộ phân tích từ vựng để xử lý, chứ không gọi một lúc toàn bộ danh sách từ tố của
cả chương trình nguồn.
Khi nhận được yêu cầu lấy một từ tố tiếp theo từ bộ phân tích cú pháp, bộ
phân tích từ vựng sẽ đọc ký tự vào cho đến khi đưa ra được một từ tố.
10
- Yêu cầu lấy từ
tố tiếp theo
Chương trình Bộ phân tích từ Bộ phân tích
nguồn vựng cú pháp
Từ tố
Bảng ký hiệu
Hình 1.2. Giao diện của bộ phân tích từ vựng trong trình biên dịch
Quá trình phân tích từ vựng gồm các giai đoạn sau:
- Xóa bỏ ký tự không có nghĩa (các chú thích, dòng trống, ký hiệu xuống
dòng, ký tự trống không cần thiết)
- Nhận dạng các ký hiệu: nhận dạng các từ tố.
- Số hóa các ký hiệu: do con số xử lý dễ dàng hơn các chuỗi ký tự
Trong phân tích từ vựng chúng ta quan tâm tới các khái niệm:
- Trị từ vựng (từ vị - lexeme): là một nhóm các ký tự kề nhau có thể tuân
theo một quy ước (mẫu hay luật) nào đó.
- Từ tố (token): là một thuật ngữ chỉ các từ vựng có cùng ý nghĩa cú pháp
(cùng một luật mô tả). Bộ phân tích cú pháp sẽ làm việc trên các từ tố. Một từ tố có
thể có các thuộc tính (các thông tin kết hợp với từ tố đó), trong thực tế một từ tố sẽ
chứa một con trỏ trỏ đến một vị trí trên bảng ký hiệu có chứa thông tin về nó.
Mẫu (luật mô tả - patter): để bộ phân tích từ vựng nhận dạng được các từ tố thì
đối với mỗi từ tố chúng ta phải mô tả đặc điểm để xác định một từ vựng có thuộc từ
tố đó không, mô tả đó được gọi là mẫu từ tố hay luật mô tả.
Chẳng hạn khi phân tích từ vựng, các ký tự của câu lệnh gán
position := initial + rate * 60
sẽ được nhóm lại thành các từ tố sau:
1.Định danh position
2. Ký hiệu gán :=
3. Định danh initial
4. Dấu cộng (+)
5. Định danh rate
6. Dấu nhân (*)
11
- 7. Số 60
Các khoảng trống (blank) phân cách các ký tự của những thẻ từ này sẽ được
loại bỏ trong quá trình phân tích từ vựng.
Phân tích cấu trúc phân cấp được gọi là phân tích cú pháp (syntax analysis
hay thường được gọi là parsing). Mỗi ngôn ngữ lập trình đều có các quy tắc diễn tả
cấu trúc cú pháp của các chương trình có định dạng đúng. Các cấu trúc cú pháp này
được mô tả bởi văn phạm phi ngữ cảnh. Bộ phân tích cú pháp có chức năng phân
tích cú pháp chương trình nguồn. Nhiệm vụ chủ yếu của nó là nhận các từ tố từ bộ
phân tích từ vựng và xác nhận rằng chuỗi này có thể được sinh ra từ văn phạm của
ngôn ngữ nguồn bằng cách tạo ra cây phân tích cú pháp cho chuỗi. Trên thực tế bộ
phân tích cú pháp còn một số nhiệm vụ thu thập thông tin về từ tố vào bảng ký hiệu.
Bộ phân tích cú pháp cũng có cơ chế ghi nhận các lỗi cú pháp và có khả năng phục
hồi được các lỗi thường gặp để có thể tiếp tục xử lý phần còn lại của chuỗi đầu vào.
Yêu cầu lấy từ
tố tiếp theo Cây phân
tích cú
Chương trình Bộ phân tích từ Bộ phân tích pháp
nguồn vựng cú pháp
Từ tố
Bảng ký hiệu
Hình 1.3. Giao diện của bộ phân tích cú pháp trong trình biên dịch
Một số vấn đề cần quan tâm trong phân tích cú pháp:
- Văn phạm phi ngữ cảnh: để xác định cú pháp của một ngôn ngữ, người ta
dùng văn phạm phi ngữ cảnh CFG (Context Free Grammar) hay còn gọi là văn
phạm BNF (Backus Naur Form). Văn phạm phi ngữ cảnh bao gồm bốn thành phần:
o Một tập hợp các từ tố (token) – các ký hiệu kết thúc (terminal
symbols)
o Một tập hợp các ký hiệu chưa kết thúc (nonterminal symbols)
o Một tập hợp các luật sinh (productions)
12
- o Một trong các ký hiệu chưa kết thúc được dùng làm ký hiệu bắt đầu
của văn phạm.
- Cây phân tích cú pháp: minh họa ký hiệu ban đầu của một văn phạm dẫn
đến một chuỗi trong ngôn ngữ. Cây phân tích cú pháp có các tính chất sau:
o Nút gốc có nhãn là ký hiệu bắt đầu.
o Mỗi một lá có nhãn là một ký hiệu kết thúc hoặc một .
o Mỗi nút trong có nhãn là một ký hiệu chưa kết thúc.
- Sự mơ hồ của văn phạm: một văn phạm có thể sinh ra nhiều hơn một cây
phân tích cú pháp cho cùng một chuỗi nhập thì gọi là văn phạm mơ hồ. Bởi vì một
chuỗi với nhiều cây phân tích cú pháp thường sẽ có nhiều nghĩa, do đó khi biên dịch
các chương trình ứng dụng, chúng ta cần thiết kế các văn phạm không có sự mơ hồ
hoặc cần bổ sung thêm các quy tắc cần thiết để giải quyết sự mơ hồ cho văn phạm.
Hình 1.4. trình bày cây phân tích cú pháp (parse tree) cho câu lệnh gán
position := initial + rate * 60.
assignment statement
identifier := expression
expression + expression
position
*
expression expression
identifier
identifier number
initial
rate 60
Hình 1.4. Cây phân tích cú pháp cho câu lệnh position := initial + rate * 60
Giai đoạn phân tích ngữ nghĩa sẽ kiểm tra các lỗi ngữ nghĩa của chương trình
nguồn và thu nhận các thông tin về kiểu cho giai đoạn tạo mã tiếp theo. Giai đoạn
này sử dụng cấu trúc phân cấp được xác định trong giai đoạn phân tích cú pháp để
xác định toán tử và toán hạng của các biểu thức và câu lệnh.
Một phần quan trọng trong giai đoạn phân tích ngữ nghĩa là kiểm tra kiểu
(tye checking). Ở đây trình biên dịch sẽ kiểm tra, dựa theo đặc tả của ngôn ngữ
13
- nguồn xem các toán hạng của một toán tử có hợp lệ hay không. Chẳng hạn nhiều
định nghĩa của các ngôn ngữ lập trình yêu cầu trình biên dịch ghi nhận lỗi mỗi khi
một số thực được sử dụng làm chỉ mục cho một mảng. Tuy nhiên đặc tả của ngôn
ngữ có thể cho phép việc áp đặt toán hạng (operand coercion), ví dụ như khi, một
toán tử số học hai ngôi (binary arithmetic operator) được áp dụng cho một số
nguyên và một số thực. Trong trường hợp này, trình biên dịch có thể phải chuyển số
nguyên thành số thực.
TỔNG KẾT CHƯƠNG 1
Trong chương này tác giả trình bày khái niệm chung về trình biên dịch, các
giai đoạn xây dựng trình biên dịch, các thành phần cấu thành trình biên dịch và mối
quan hệ giữa các thành phần đó. Từ đó có cái nhìn tổng quát về việc xây dựng và
vận hành trình biên dịch.
14
- CHƯƠNG 2: CÔNG CỤ LEX/ YACC
Chương này trình bày những nghiên cứu của tác giả về công cụ Lex/Yacc,
quy tắc sử dụng Lex/Yacc, mối quan hệ giữa chúng và các công cụ hỗ trợ. Trong
chương này tác giả cũng trình bày cách thức hoạt động của công cụ này trong việc
hỗ trợ tạo ra trình biên dịch.
2.1. GIỚI THIỆU VỀ LEX/YACC
Lex và Yacc là các công cụ dung để sinh bộ phân tích từ vựng và phân tích
cú pháp. Trước năm 1975 việc xây dựng mộ trình biên dịch là một quá trình tốn
nhiều công sức và thời gian. Sau đó Lesk và Johnson đã công bố tài liệu về Lex và
Yacc. Những công cụ này đã giúp ích rất nhiều trong việc xây dựng trình biên dịch.
mã nguồn a=b+c*d
Bộ phân tích từ vựng Lex Mẫu/ luật mô tả
từ tố id1 = id2 + id3* id4
Bộ phân tích cú pháp Yacc Cú pháp/văn
phạm
cây phân tích =
cú pháp
id1 +
id2 *
id3 id4
Sinh mã đích
load id3
mã đích mul id4
add id2
store id1
Hình 2.1. Ví dụ trình tự biên dịch đoạn mã nguồn a = b + c * d
15
- Mẫu/ luật mô tả ở hình trên là tập tin được tạo ra bằng trình soạn thảo bất kì.
Lex sẽ đọc những luật này và sinh ra mã C cho bộ phân tích từ vựng. Bộ phân tích
tích từ vựng này thực hiện việc so khớp chuỗi kí tự trong dữ liệu đầu vào với những
luật đã được mô tả và chuyển những chuối kí tự này thành các từ tố. Từ tố là sự số
hóa các chuỗi, giúp cho quá trình xử lý được dễ dàng hơn.
Khi các định danh trong dữ liệu vào được tìm thấy, bộ phân tích từ vựng sẽ
đưa chúng vào bảng ký hiệu. Bảng ký hiệu có thể chứa nhiều thông tin khác, ví dụ
như kiểu dữ liệu và vị trí mỗi biến rtong bộ nhớ.
Cú pháp/ văn phạm trong hình trên cũng là một tập tin văn bản được tạo ra
bởi trình soạn thảo bất kì. Yacc sẽ đọc cú pháp này và tạo ra mã C cho bộ phân tích
cú pháp. Bộ phân tích cú pháp sử dụng các luật cho phép phân tích các từ tố từ bộ
phân tích từ vựng và tạo ra cây cú pháp. Cây cú pháp biểu diễn một cấu trúc phân
cấp các từ tố.
Cuối cùng, chương trình đích sẽ được sinh ra từ cây cú pháp được cung cấp
bởi bộ phân tích cú pháp.
Quy trình chung để sử dụng Lex và Yacc khi phát sinh ứng dụng được thể
hiện qua Hình 2.2.
(yyparse) compile.c sourc
compile.y yacc
compile_tab.c e
compile_tab.h gcc compile.exe
lex.yy.c
compile.l lex Compiled
(yylex)
output
Hình 2.2. Quy trình vận dụng và cách đặt tên với Lex, Yacc
Ví dụ chúng ta muốn xây dựng một trình biên dịch. Đầu tiên, chúng ta cần
xây dựng mẫu/ luật mô tả cho Lex trong file compile.l, và văn phạm/ cú pháp cho
Yacc trong file compile.y. Các câu lệnh để tạo ra trình biên dịch, compile.exe, được
liệt kê dưới đây:
yacc -d compile.y # create y.tab.h, y.tab.c
lex compile.l # create lex.yy.c
cc lex.yy.c y.tab.c –o compile.exe # compile/link
16
- Yacc đọc mô tả cú pháp trong compile.y và phát sinh bộ phân tích cú pháp
(bộ phân tích), bao gồm hàm yyparse, trong tệp compile _tab.c. Trong tệp
compile.y còn bao gồm việc khai báo các từ tố, tùy chọn –d để phát sinh những
định nghĩa cho các từ tố này và đặt chúng trong tệp compile _tab.h.
Lex đọc mô tả các mẫu trong compile.l, cùng với tệp compile _tab.h để phát
sinh bộ phân tích từ vựng, bao gồm hàm yylex, trong tệp lex.yy.c.
Cuối cùng, bộ phân tích cú pháp và bộ phân tích từ vựng được biên dịch và
liên kết với nhau để tạo ra compile.exe có thể thực thi được. Trong hàm main, hàm
yyparse được gọi để chạy trình biên dịch. Hàm yyparse tự động gọi yylex để thu
được từ tố.
2.2. LEX
Trong giai đoạn đầu, trình biên dịch đọc những dòng ký tự đầu vào và
chuyển những dòng ký tự này thành các từ tố. Nhờ các biểu thức chính quy chúng ta
có thể chỉ ra các luật mô tả cho Lex, từ đó nó có thể sinh ra mã cho phép quét và so
khớp những dòng ký tự đầu vào. Mỗi một luật mô tả trong tập tin Lex (có đuôi mở
rộng là .l) thường có một hành động đi kèm. Lex dịch các biểu thức chính quy sang
chương trình máy bằng cách bắt chước máy trạng thái hữu hạn. Sử dụng ký tự vào
tiếp theo cùng trạng thái hiện tại, trạng thái tiếp theo được dễ dàng xác định căn cứ
vào bảng trạng thái.
Tuy nhiên Lex cũng có một số hạn chế. Ví dụ, Lex không thể sử dụng để
nhận biết các cấu trúc lồng nhau (như các dấu ngoặc đơn). Các cấu trúc lồng nhau
được quản lý bởi một ngăn xếp nhất định. Khi chúng ta gặp một dấu “(“ chúng ta
đẩy nó vào ngăn xếp, còn khi tìm thấy dấu “)” chúng ta so khớp với phần tử ở đỉnh
ngăn xếp và lấy phần tử đó ra khỏi ngăn xếp. Tuy nhiên Lex chỉ có các trạng thái và
các dịch chuyển giữa các trạng thái, Lex không có ngăn xếp nên nó không phù hợp
để phân tích các cấu trúc lồng nhau. Yacc sử dụng máy trạng thái hữu hạn cùng với
một ngăn xếp và có thể thực thi các cấu trúc lồng nhau một cách dễ dàng. Lex thích
hợp trong việc so khớp các mẫu còn Yacc thích hợp cho các vấn đề phức tạp hơn.
Khuôn dạng chung của nguồn Lex (Lex source) gồm ba phần như sau:
………. definitions ……….
%%
……….rules……….
%%
……….subroutines……….
17
- Phần định nghĩa (definitions): đặt ở phần đầu chương trình, dùng để định
nghĩa cú pháp các công thức, các biến, các kiểu, … Mã trong phần này sẽ được sao
chép tới đầu tập tin C và cần được đặt trong cặp dấu “%{“ và “%}”.
Phần luật (rules): phần này được đặt trong cặp dấu “%%”, trình bày nội dung
các luật. Mỗi luật gồm hai phần: một luật và một hành động tương ứng, ngăn cách
nhau bằng ký tự trắng. Bộ phân tích từ vựng mà lex tạo ra sẽ thực hiện hành động
khi nó nhận ra một luật. Những luật này chính là các biểu thức chính quy.
Phần chương trình con (subroutines): đặt ở phần cuối chương trình, trình bày
các hàm được viết bằng mã C. Lex sao chép những hàm này tới tập tin C sau khi
Lex thực hiện xong việc sinh mã.
Bảng 2.1. Mô tả cách biểu diễn các biểu thức chính quy
Ký tự Ý nghĩa
. Bất kỳ ký tự nào ngoại trừ ký tự xuống dòng
\n Xuống dòng
* Không hoặc nhiều bản sao của biểu thức phía trước
+ Một hoặc nhiều bản sao của biểu thức phía trước
? Không hoặc một bản sao của biểu thức phía trước
^ Bắt đầu một dòng
$ Kết thúc một dòng
a|b a hoặc b
(ab)+ Một hoặc nhiều bản sao của ab
“a+b” a+b
[] Nhóm các ký tự
Bảng 2.2. Biểu diễn một số ví dụ của biểu thức chính quy
Biểu thức Ý nghĩa
abc abc
abc* ab abc abcc abccc …
abc+ abc abcc abccc …
a(bc)+ abc abcbc abcbcbc ….
a(bc)? a abc
[abc] Một trong các ký tự a, b, c
[a-z] Bất kỳ ký tự nào từ a đến z
[a\-z] Một trong các ký tự a, -, z
[-az] Một trong các ký tự -, a, z
18
- [A-Za-z0-9]+ Một hoặc nhiều ký tự/ số
[ \t\n] Ký tự trắng
[^ab] Bất kỳ ký tự nào ngoại trừ a, b
[a^b] Một trong các ký tự a, ^, b
[a|b] Một trong các ký tự a, |, b
a|b Một trong các ký tự a, b
Nguồn Lex được chia thành 3 phần với ký hiệu %% ngăn cách giữa các
phần. Tại một thời điểm chỉ có một kí tự từ dữ liệu vào được sao chép qua dữ liệu
ra. Kí hiệu %% đầu tiên luôn cần phải có, tuy nhiên, nếu chúng ta không chỉ ra bất
kì luật nào thì một hành động mặc định là so khớp mọi thứ và sẽ sao chép toàn bộ
dữ liệu vào thành dữ liệu ra. Mặc định cho đầu vào và đầu ra là stdin và stdout.
Dưới đây là ví dụ với giá trị mặc định được mã hóa một cách rõ rang:
%%
/*match everything except newline*/
. ECHO;
/*match newline*/
\n ECHO;
%%
int yywrap(void){
return 1;
}
int main (void){
yylex();
return 0;
}
Có hai luật sinh được chỉ ra trong phần luật. Mỗi một luật sinh được bắt đầu
ở cột đầu tiên, theo sau là kí tự trắng (khoảng trắng, tab hoặc kí tự xuống xòng) và
một hành động tương ứng với luật sinh đó. Hành động này có thể là một hoặc nhiều
câu lệnh C (được đặt trong dấu ngoặc nhọn {}). Mọi thứ không được bắt đầu ở cột
một sẽ được sao chép tới tập tin C. Chúng ta cũng có thể thêm các ghi chú cho tập
tin nguồn lex. Trong ví dụ này có hai luật sinh, “.” và “\n” với hành động ECHO
tương ứng với các luật này. Có một số macro và một số biến được định nghĩa trước
bởi lex. ECHO là một macro được thực hiện khi luật được so khớp. Đây là hành
động mặc định cho bất kì chuỗi nào không được so khớp. ECHO được định nghĩa
như sau:
#define ECHO fwrite (yytext, yyleng, 1, yyout)
Biến yytextb là con trỏ trỏ tới chuỗi được so khớp và yyleng là độ dài của
chuỗi so khớp đó. Biến yyout là đầu ra, mặc định là stdout. Hàm yywrap được gọi
bởi lex khi đầu vào đã được xử lý hết, trả lại giá trị 1 nếu mọi việc đã kết thúc hoặc
19
- trả lại 0 nếu còn cần tới một vài xử lý khác. Mọi chương trình C đều cần một hàm
main. Trong trường hợp này chúng ta chỉ cần gọi hàm yylex, đây chính là điểm vào
của lex.
Bảng 2.3. Danh sách các macro, biến được định nghĩa trước của lex
Tên biến/hàm Chức năng
int yylex (void) Gọi bộ phân tích từ vựng, trả lại từ tố
char *yytext Con trỏ tới chuỗi được so khớp
yyleng Độ dài chuỗi được so khớp
int yywrap (void) Trả lại 1 nếu đầu vào đã được xử lý hết,
0 nếu chưa
FILE *yyout Tập tin kết quả
FILE *yyin Tập tin đầu vào
INITIAL Trạng thái bắt đầu
BEGIN Điều kiện chuyển trạng thái bắt đầu
ECHO Viết chuỗi được so khớp
Dưới đây là một chương trình nhưng không thực hiện bất kì công việc gì. Tất
cả đầu vào đều được so khớp nhưng không có bất kì hành động nào tương ứng với
các luật, vì thế sẽ không có đầu ra.
%%
.
\n
Ví dụ sau thực hiện thêm số dòng vào trước mỗi dòng trong tâp tin. Biến
yylineno dùng lưu trữ số dòng. Biến chưa tập tin vào cho lex là yyin và mặc định là
stdin.
%{
int yylineno;
%}
%%
^(.*)\n printf("%4d\t%s", ++yylineno, yytext);
%%
int main(int argc, char *argv[]) {
yyin = fopen(argv[1], "r");
yylex();
fclose(yyin);
}
Phần định nghĩa bao gồm các thay thế, mã và trạng thái bắt đầu. Mã trong
phần định nghĩa được sao chép vào đầu tập tin C và bắt buộc phải nằm trong cặp
dấu “%{“ và “%}”. Các thay thế chính là các luật mô tả. Ví dụ, chúng ta có thể xác
định số và chữ cái như sau:
digit [0-9]
letter [A-Za-z]
%{
20
nguon tai.lieu . vn