Báo cáo Nghiên cứu ứng dụng LEX/YACC trong tự động phát sinh mã nguồn

59 trang thiennha21 14/04/2022 5900

Download

Bạn đang xem 20 trang mẫu của tài liệu "Báo cáo Nghiên cứu ứng dụng LEX/YACC trong tự động phát sinh mã nguồn", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

bao_cao_nghien_cuu_ung_dung_lexyacc_trong_tu_dong_phat_sinh.pdf

Nội dung text: Báo cáo Nghiên cứu ứng dụng LEX/YACC trong tự động phát sinh mã nguồn

ĐẠ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 expression identifier := 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.y yacc compile.c sourc 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
int count; %} %% /* match identifier */ {letter}({letter}|{digit})* count++; %% int main(void) { yylex(); printf("number of identifiers = %d\n", count); return 0; } Phần luật và biểu thức đi kèm được ngăn cách bằng khoảng trắng. Việc liên kết tới phần thay thế trong phần luật được bao quanh bởi dấu ngoặc nhọn ({letter}) để phân biệt với chữ. Khi chúng ta có một sự so khớp trong phần luật thì mã C tương ứng được thực hiện. Dưới đây là ví vụ thực hiện đếm số kí tự, số từ, số dòng trong một tập tin. %{ int nchar, nword, nline; %} %% \n { nline++; nchar++; } [^ \t\n]+ { nword++, nchar += yyleng; } . { nchar++; } %% int main(void) { yylex(); printf("%d\t%d\t%d\n", nchar, nword, nline); return 0; } 2.3. YACC Sau khi dữ liệu vào được phân chia thành các từ tố, chúng ta cần thiết lập mối quan hệ giữa các từ tố đó. Một trình biên dịch C cần tìm ra các biểu thức, câu lệnh, khai báo, khối lệnh, các hàm trong chương trình. Bài toán này được gọi là phân tích cú pháp và danh sách các luật định nghĩa mối quan hệ sao cho chương trình hiểu được gọi là văn phạm. Yacc chứa mô tả văn phạm ngắn gọn và sinh ra mã C để có thể phân tích văn phạm. Bộ phân tích Yacc tự động nhận biết khi nào một dãy các từ tố khớp với một luật trong văn phạm và khi nào không. Tương tự như nguồn Lex, nguồn Yacc được chia thành ba phần như sau: . definitions . %% .rules . %% .subroutines . Phần định nghĩa (definitions): chứa khai báo các từ tố mong muốn được nhận từ bộ phân tích từ vựng và mã C, được đặt trong cặp dấu “%{“ và “%}”. Mặc 21
dù Yacc chấp nhận bất kỳ tên đúng nào theo quy tắc đặt tên của C tuy nhiên người dùng thường viết hoa các từ tố và viết thường các thành phần còn lại. Phần luật (rules): chứa văn phạm cho Yacc (được mô tả bằng cách sử dụng dạng chuẩn BNF – Backus Naur Form), phần này được đặt trong cặp dấu “%%”. Văn phạm là một tập hợp các luật. Mỗi luật gồm: dấu “:”, một tên nằm bên trái dấu “:” (gọi là phía bên trái), một danh sách các ký hiệu và mã thực thi nằm bên phải dấu “:” (gọi là phía bên phải) và dấu “;” để kết thúc một luật. Mặc định luật đầu tiên là luật quan trọng nhất. Bộ phân tích sẽ cố gắng tìm danh sách từ tố sao cho khớp với luật ban đầu này. Danh sách các ký hiệu ở phía bên phải là danh sách các tên (không hoặc nhiều tên). Ký hiệu ở phía bên trái luật này có thể được dùng như là từ tố trong các luật khác. Với các luật có nhiều phần bên phải, chúng ta ngăn cách chúng bằng dấu “|” (được hiểu là phép “hoặc”). Mã thực thi của một luật là khối lệnh C nằm trong cặp dấu “{“ và “}”, bộ phân tích cú pháp thực thi đoạn mã này nếu luật luật đó được so khớp. Phần chương trình con (subroutines): bắt đầu sau cặp dấu “%%”, trình bày các chương trình con của người dùng, được viết bằng mã C. Trong đó main() là hàm quan trọng nhất, nó lặp đi lặp lại việc gọi hàm yyparse() cho đến khi nguồn Lex thực hiện xong. Hàm yyparse() là bộ phân tích cú pháp được tạo ra bởi Yacc, vì vậy chương trình chính của chúng ta sẽ lặp lại việc phân tích cho tới khi dữ liệu vào được phân tích hết. Dòng chú thích được bao bởi cặp /* */ giống như trong C. Yacc duy trì hai ngăn xếp trong bộ nhớ, một ngăn xếp phân tích và một ngăn xếp giá trị. Ngăn xếp phân tích chứa các ký tự kết thúc và chưa kết thúc (phần bên trái và bên phải của dạng thức BNF). Ngăn xếp giá trị chứa giá trị tương ứng của các phần tử trong ngăn xếp phân tích. Ví dụ khi Lex trả về từ tố INTEGER, Yacc sẽ chuyển từ tố này vào ngăn xếp phân tích. Cùng lúc đó, giá trị tương ứng của phần tử này sẽ được đưa vào ngăn xếp giá trị. Ngăn xếp phân tích và ngăn xếp giá trị luôn đồng bộ với nhau nên việc tìm giá trị của từng từ tố được thực hiện dễ dàng. Văn phạm cho yacc được mô tả bằng cách sử dụng dạng chuẩn BNF (Backus Naur Form). Kĩ thuật này được tiên phong bởi John Backus và Peter Naur, đã từng được sử dụng để mô tả ALGOL60. Một văn phạm BNF có thể được sử dụng để biểu diễn ngôn ngữ phi ngữ cảnh. Phần lớn cấu trúc trong các ngôn ngữ lập trình hiện đại đều có thể được biểu diễn bằng cách sử dụng BNF. Ví dụ, văn phạm cho biểu thức thực hiện việc nhân và cộng các số như sau: E -> E + E E -> E * E 22
E -> id Ở đây có ba luật sinh được chỉ ra. Phần xuất hiện bên trái (left-hand side) mỗi luật sinh, ví dụ E (expression) là chưa kết thúc. Phần kết thúc (từ tố được trả lại bởi lex), ví dụ id (identifier) chỉ xuất hiện ở bên phải (right-hand side) mỗi luật sinh. Văn phạm này chỉ ra rằng một biểu thức có thể là tổng của hai biểu thức, tích của hai biểu thức hoặc là một định danh. Chúng ta có thể sử dụng văn phạm này để sinh ra các biểu thức: E -> E * E (r2) -> E * z (r3) -> E + E * z (r1) -> E + y * z (r3) -> x + y * z (r3) Ở mỗi bước chúng ta mở rộng và thay thế phần bên trái mỗi luật bằng một phần bên phải tương ứng. Chữ số nằm bên phải cho biết luật nào được áp dụng. Để phân tích cú pháp một biểu thức chúng ta cần thực hiện thao tác ngược lại. Thay vì bắt đầu với một kí hiệu chưa kết thúc (kí hiệu bắt đầu) và sinh ra một biểu thức từ văn phạm, chúng ta cần điều chỉnh biểu thức tới một kí hiệu chưa kết thúc. Kĩ thuật này gọi là phân tích từ dưới lên và sử dụng ngăn xếp để lưu trữ. Ví dụ sau thực hiện công việc tương tự nhưng theo thứ tự ngược lại: 1 . x + y * z chuyển 2 x . + y * z điều chỉnh(r3) 3 E . + y * z chuyển 4 E + . y * z chuyển 5 E + y . * z điều chỉnh (r3) 6 E + E . * z chuyển 7 E + E * . z chuyển 8 E + E * z . điều chỉnh (r3) 9 E + E * E . điều chỉnh (r2) thực hiện phép nhân 10 E + E . điều chỉnh (r1) thực hiện phép cộng 11 E . chấp nhận Phần bên trái dấu chấm được lưu trữ trong ngăn xếp, trong khi phần còn lại của đầu vào nằm bên phải dấu chấm. Chúng ta bắt đầu chuyển các từ tố vào ngăn xếp. Một khi đỉnh của ngăn xếp trùng khớp với phần bên trái của một luật chúng ta thay thế từ tố được so khớp đó ở trong ngăn xếp bởi phần bên trái của luật. Nói cách khác từ tố so khớp được lấy ra khỏi ngăn xếp và thay vào đó là phần bên trái của luật. Quá trình này tiếp tục cho tới khi chúng ta chuyển tất cả đầu vào vào ngăn xếp và chỉ còn kí hiệu chưa kết thúc đầu tiên trong ngăn xếp. Ở bước 1 chúng ta chuyển x vào ngăn xếp. Bước 2 sử dụng luật thứ 3 và thay thế x bằng E. Chúng ta tiếp tục chuyển và điều chỉnh như thấy cho tới khi chỉ còn lại kí hiệu chưa kết thúc đầu tiên trong ngăn xếp. Ở bước 9, khi chúng ta thực hiện điều chỉnh sử dụng luật thứ 2, 23
chúng ta thực hiện nhân. Tương tự thao tác cộng ở bước 10, bởi vì phép nhân có độ ưu tiên cao hơn phép cộng. Ở bước 6, thay vì thực hiện việc chuyển, chúng ta có thể thực hiện điều chỉnh và áp dụng luật thứ 1. Điều này sẽ làm cho phép cộng có độ ưu tiên cao hơn phép nhân. Điều này được xem là sự xung đột giữa việc chuyển và điều chỉnh. Văn phạm của chúng ta đang nhập nhằng, không rõ rang vì có nhiều hơn một phương án có thể thực hiện. Trong trường hợp này quyền ưu tiên bị ảnh hưởng. Yacc sẽ thực hiện thao tác mặc định khi có sự xung đột. Yacc sẽ thực hiện việc chuyển khi có sự xung đột giữa chuyển và điều chỉnh, với xung đột giữa điều chỉnh và điều chỉnh, yacc luôn sử dụng luật đầu tiên trong danh sách luật. Yacc cũng đưa ra cảnh báo mỗi khi có sự xung đột trong văn phạm. Dưới đây là một vi dụ nguồn yacc: %{ #include int yylex(void); void yyerror(char *); %} %token INTEGER %% program: program expr '\n' { printf("%d\n", $2); } | ; expr: INTEGER { $$ = $1; } | expr '+' expr { $$ = $1 + $3; } | expr '-' expr { $$ = $1 - $3; } ; %% void yyerror(char *s) { fprintf(stderr, "%s\n", s); } int main(void) { yyparse(); return 0; } Trong phần luật chúng ta chỉ ra rằng một chương trình có thể gồm nhiều biểu thức hoặc không chứa biểu thức nào. Mỗi biểu thức kết thúc bằng kí hiệu sang dòng mới. Mỗi lần gặp kí hiệu sang dòng mới chúng ta in giá trị của biểu thức đó. Khi áp dụng luật: expr: expr '+' expr { $$ = $1 + $3; } Chúng ta thực hiện thay thế phần bên phải của luật trong ngăn xếp bằng phần bên trái của chính luật đó. Trong trường hợp này chúng ta lấy “expr ‘+’ expr” ra và 24
đưa “expr” vào ngăn xếp. Chúng ta đã thực hiện điều chỉnh ngăn xếp bằng cách lấy ba giá trị ra khỏi ngăn xếp và thay vào đó một giá trị. Chúng ta liên kết vị trí trong ngăn xếp giá trị bằng cách chỉ ra “$1” cho phần đầu tiên của bên phải luật, “$2” cho phần thứ hai và tiếp tục như vậy. “$$” chính là đỉnh ngăn xếp sau khi ta đã thực hiện điều chỉnh. Hành động trên thêm giá trị tương ứng với hai biểu thức, lấy ba giá trị ra khỏi ngăn xếp giá trị và thêm vào một giá trị tổng. Và đó là cách ngăn xếp phân tích và ngăn xếp giá trị được đồng bộ. Giá trị số được đưa ngay vào ngăn xếp khi ta thực hiện điều chỉnh từ INTERGER sang expr. Sau khi INTERGER được chuyển tới ngăn xếp, chúng ta áp dụng luật: expr: INTEGER { $$ = $1; } Từ tố INTERGER được lấy ra khỏi ngăn xếp phân tích và thay vào đó là expr. Với ngăn xếp giá trị, chúng ta lấy giá trị số nguyên ra khỏi ngăn xếp và thêm nó vào lại ngăn xếp. Nói cách khác là chúng ta chẳng thay đổi gì cả. Cuối cùng, khi kí hiệu sang dòng mới được tìm thấy, giá trị tương ứng của biểu thức được in ra. Trường hợp phát hiện lỗi cú pháp, yacc sẽ gọi hàm yyerror. Nếu cần thay đổi cách hiển thị của hàm yyerror chúng ta hãy điều chỉnh các tập tin đi kèm của yacc. Hàm cuối cùng của yacc là hàm main. Văn phạm trong ví dụ trên vẫn còn mơ hồ. Mặc dù yacc sẽ cảnh báo về sự nhập nhằng hay, tuy nhiên nó sẽ vẫn thực hiện văn phạm sử dụng việc chuyển như là thao tác mặc định. 2.4. CÀI ĐẶT CÁC ỨNG DỤNG Để sử dụng Lex và Yacc chúng ta cần cài đặt các công cụ hỗ trợ biên dịch và phát sinh mã nguồn tương ứng với từng giai đoạn. Hiện tại có nhiều ứng dụng hỗ trợ xử lý cho Lex và Yacc, tuy nhiên trong thử nghiệm của mình tác giả đã cài đặt các công cụ sau: - Bison: bộ phân tích cú pháp theo tiêu chuẩn đặc tả của Yacc. Nó sẽ phát sinh tự động một chương trình xử lý tương ứng với các tập tin đầu vào thiết kế cho Yacc. - Flex: công cụ để tạo ra các bộ kiểm tra nhằm công nhận các mẫu từ vựng trong tập tin đầu vào được đặc tả theo tiêu chuẩn của Flex. - DevC++: môi trường phát triển tích hợp (IDE) khá đầy đủ tính năng dành cho các ngôn ngữ lập trình C/C++. TỔNG KẾT CHƯƠNG 2 Chương này tác giả nghiên cứu về lex và yacc, tổng quan về mỗi công cụ, mối liên hệ giữa chúng, cách sử dụng, vận hành các công cụ này. Ngoài ra, tác giả cũng tìm hiểu thêm các ứng dụng giúp việc sử dụng các công cụ này được dễ dàng hơn. 25
CHƯƠNG 3: XÂY DỰNG CÔNG CỤ SINH MÃ NGUỒN 3.1. GIỚI THIỆU NGÔN NGỮ ĐẶC TẢ TTT Các phương pháp kiểm thử ứng dụng tương tác hiện nay sử dụng nhiều ký hiệu khác nhau để xây dựng các mô hình kiểm thử làm cho việc mô hình hóa các thuộc tính và các quá trình trở nên khó khăn. Trong các nghiên cứu [2, 5] đã đề xuất ngôn ngữ mô hình hóa TTT (Task Tree Test) để mô hình hóa kiểm thử các ứng dụng tương tác. Đặc điểm của ngôn ngữ TTT gồm đặc tả các phép toán trên cây nhiệm vụ tương tranh (ConcurTaskTree – CTT) với bổ sung xác suất có điều kiện, lưu lại lịch sử hành vi của người dùng và hỗ trợ các điều kiện cho hành vi người dùng dựa trên lịch sử hành vi này. Trong [2,5] đã đề xuất ngôn ngữ mô hình hóa kiểm thử TTT để biểu diễn nhất quán các thuộc tính và các quá trình này. 3.1.1. Cấu trúc cơ bản của một chương trình Ngôn ngữ TTT gồm một khối TESTCTT và một hoặc nhiều khối FUNCTION. Cấu trúc khối TESTCTT gồm: một mệnh đề TESTCTT dùng để khai báo tên của khối; mệnh đề var nhằm khai báo các biến trạng thái và các biến khác; khối lệnh nằm trong begin và end. ::= + ::= ::= TESTCTT ; ::= var + ::= begin + end ::= : ; ::= | , Khối FUNCTION bao gồm: mệnh đề FUNCTION dùng để khai báo tên hàm, tham số đầu ra của hàm; mệnh đề VAR để khai báo các biến dữ liệu cục bộ và khối lệnh nằm trong begin và end; ::= ::= FUNCTION () returns ( ); ::= var + Hàm trả về dữ liệu trong kí hiệu và được định nghĩa như sau: ::= : 3.1.2. Các lệnh của ngôn ngữ TTT Có 5 loại lệnh trong ngôn ngữ TTT đó là: các lệnh nhóm, các lệnh vào/ra dữ liệu, lệnh gán, các lệnh SQL và các cấu trúc điều khiển (cấu trúc lựa chọn và cấu trúc 26
lặp). Các lệnh này nhằm đặc tả các phép toán CTT, lưu trữ hành vi người dùng và xây dựng kịch bản kiểm thử. ::= | | | | | Lệnh nhóm là khối lệnh nằm trong begin và end: ::= begin + end Lệnh vào/ ra dữ liệu bắt đầu bằng output/ input tương ứng và theo sau là tên các biến, hàm, ::=output ( );|input( ); Lệnh gán gồm phép gán, phần bên trái và bên phải phép gán. Phép gán bao gồm phép =, +=, -=, *= và /=. ::= = ; | += ;| -= ; | *= ;| /= ; Câu lệnh SQL kế thừa ngôn ngữ SQL và sử dụng chúng để lưu trữ, thao tác dữ liệu về lịch sử tương tác của người dùng đối với ứng dụng. ::= | | | | | ::= create table ( ) ::= drop table ifsql exists act ::= insert into ( ) values ( ) ::=update set where ::=delete from [where ]? ::= select from [where ]? ::= | , Cấu trúc điều khiển gồm cấu trúc lựa chọn và cấu trúc lặp. Cấu trúc lựa chọn là câu lệnh if, cấu trúc lặp gồm vòng lặp do while và while. ::= | ::= | ::=if ( ) ::=if ( ) else ::= do while ( ) ::=while ( ) 3.1.3. Các thành phần khác 27
Ngôn ngữ TTT còn định nghĩa các kiểu dữ liệu cơ bản, các biểu thức, các phép toán CTT, phép toán số học, phép toán logic, biến, hằng, Cú pháp các thành phần còn lại của ngôn ngữ TTT được trình bày như sau: Ngôn ngữ TTT gồm bốn kiểu dữ liệu cơ bản: bool, interger, char và float. ::= bool | interger| char | float Biến trong ngôn ngữ TTT bắt đầu bằng một chữ cái hoặc dấu gạch dưới “_”, theo sau là chữ cái hoặc chữ số bất kỳ. ::= | | ::= ‘A’ | |’Z’|’a’| |’z’|’_’ ::= ‘0’ | | ‘9’ Biểu thức trong ngông ngữ TTT gồm biểu thức với các toán tử CTT, biểu thức số học và biểu thức logic. Thứ tự ưu tiên các toán tử số học và logic thể hiện ở Bảng 3.1 theo thứ tự từ thấp đến cao. Bảng 3.1. Thứ tự ưu tiên các phép toán Thứ tự Toán tử Mô tả Cách kết hợp 1 , =, ::= | | ::= | ::= | ::= |not | ::= - | ::= ( ) | | () | | | | ::=’ ’ | ‘>=’ | ‘ ::=’+’ | ‘-‘ ::= ‘*’ | ‘/’ ::= and | or ::= | ::= . ::=’1’| |’9’ ::=” ” 28
::=’ ’|’ ’|’-‘ ::= ‘A’ | |’Z’|’a’| |’z’|’0’| |’9’|’_’|’+’|’*’|’:’|’=’|’ ‘|’-‘ ::=‘A’ | |’Z’|’a’| |’z’ Các phép toán CTT có bổ sung xác suất có điều kiện giúp tự động sinh dữ liệu thử cho ứng dụng tương tác và được định nghĩa như sau: ::= | | | | | | ::= choice( , , , , , , ) ::= concur( , , , , , , ) ::= indepen ( , , , , , , ) ::= deact ( , , ) ::= suspend ( , , ) ::= option ( , , ) ::=enabling( , ) Các nhóm lệnh nêu trên của ngôn ngữ TTT được sử dụng nhằm mục đích đặc tả kiểm thử ứng dụng tương tác. Các kịch bản kiểm thử mô tả các hành vi tương tác của người dùng và ứng dụng. Các hành vi này được lưu trữ lại trong cơ sở dữ liệu làm cơ sở để xây dựng các điều kiện trong các phép toán CTT và làm cơ sở để sinh dữ liệu thử cho ứng dụng tương tác. 3.2. XÂY DỰNG GIẢI PHÁP DỊCH NGÔN NGỮ TTT SANG NGÔN NGỮ C Quá trình biên dịch ngôn ngữ TTT sang ngôn ngữ C được thực hiện bởi thuật toán sau: Đầu vào: Mô hình TESTCTT viết bằng ngôn ngữ TTT. Đầu ra: Chương trình viết bằng ngôn ngữ C. Thuật toán: Bước 1: Chuyển đổi các từ vựng Gọi TokenTTT là các từ khóa trong ngôn ngữ TTT, TokenC là các từ khóa trong ngôn ngữ C, phép chuyển đổi TokenTTT sang TokenC được thể hiện như trong Bảng 3.2. Bảng 3.2. Bảng chuyển đổi từ vựng giữa ngôn ngữ TTT và ngôn ngữ C 29
TokenTTT TokenC Ghi chú TESTCTT name void main() begin { end } return return integer int char char bool int float float if if else else do do while while input scanf output printf > > = >= != So sánh không bằng = = Phép gán + + - - * * / / += += -= -= *= *= /= /= and && or || not ! Bước 2: Biến đổi cú pháp 30
Gọi StatementTTT là các lệnh trong ngôn ngữ TTT, StatementC là các lệnh trong ngôn ngữ C, phép chuyển đổi StatementTTT sang StatementC được thể hiện như trong Bảng 3.3. Bảng 3.3. Bảng chuyển đổi cú pháp giữa ngôn ngữ TTT và ngôn ngữ C StatementTTT StatementC begin { StatementTTT StatementTTT end } if (điều_kiện) if (điều_kiện) begin { StatementTTT StatementC end } if (điều_kiện) if (điều_kiện) begin { StatementTTT StatementC end } else else begin { StatementTTT StatementC end } while (điều_kiện) while (điều_kiện) begin { StatementTTT StatementC end } do do begin { StatementTTT StatementTTT end } while (điều_kiện) while (điều_kiện) var danh_sach_bien: kieu_du_lieuTTT kieu_du_lieuC danh_sach_bien input (ten_bien) scanf(“%k”, &ten_bien) //trong đó k là kiểu dữ liệu của ten_bien output(ten_bien) printf(“%k”, ten_bien) //trong đó k là kiểu dữ liệu của ten_bien ten_bien = bieu_thuc ten_bien = bieu_thuc 31
ten_bien += bieu_thuc ten_bien += bieu_thuc ten_bien -= bieu_thuc ten_bien -= bieu_thuc ten_bien *= bieu_thuc ten_bien *= bieu_thuc ten_bien /= bieu_thuc ten_bien /= bieu_thuc DROP TABLE IFSQL EXISTS ACT mysql_query(conn, "DROP TABLE IF EXISTS U_ACTIONS") //conn: quản lý việc kết nối với mysql CREATE TABLE U_ACTIONS(INPUT, mysql_query(conn, “CREATE TABLE OUTPUT) U_ACTIONS(INPUT VARCHAR(10),OUTPUT VARCHAR(10))”) INSERT INTO U_ACTIONS(INPUT) sprintf(msg," INSERT INTO VALUES(T) U_ACTIONS(INPUT) VALUES('%c')", T) mysql_query(conn, msg) //T chứa giá trị cần được thêm vào //msg là xâu ký tự INSERT INTO U_ACTIONS(INPUT, sprintf(msg," INSERT INTO OUTPUT) VALUES(T, Tout) U_ACTIONS(INPUT, OUTPUT) VALUES('%c', ‘%c’)", T, Tout); mysql_query(conn, msg) //T, Tout chứa giá trị cần được thêm vào SELECT * FROM U_ACTIONS WHERE sprintf(msg, "SELECT * FROM INPUT=T U_ACTIONS WHERE INPUT=’%c’", T); mysql_query(conn, msg) //T chứa giá trị cần được thêm vào UPDATE U_ACTIONS sprintf(msg, "UPDATE U_ACTIONS SET INPUT = Told, OUTPUT = Tout SET INPUT=’%c’, OUTPUT=’%c’ WHERE INPUT = Tnew; WHERE INPUT=’%c’", Told, Tout, Tnew); mysql_query(conn, msg) //Told, Tout, Tnew chứa giá trị cần được thêm vào DELETE FROM U_ACTIONS mysql_query(conn, “DELETE FROM //xóa toàn bộ dữ liệu trong bảng U_ACTIONS”); //U_ACTIONS DELETE FROM U_ACTIONS sprintf(msg, " DELETE FROM WHERE INPUT = T U_ACTIONS WHERE INPUT=’%c’", //bản ghi nào thỏa mãn điều kiện trong T); //WHERE thì nó sẽ bị xóa mysql_query(conn, msg) //T chứa giá trị cần được thêm vào Bước 3: Chuyển đổi ngữ nghĩa 32
Ngữ nghĩa của lệnh trong TTT và C là tương đương. Tuy nhiên có một số lệnh được chuyển tùy thuộc vào thông tin của ngữ cảnh. - Lệnh output(i) trong TTT có thể được dịch sang C các lệnh printf(“%d”, i) hoặc printf(“%c”, i) hoặc printf(“%f”, i) phụ thuộc vào kiểu dữ liệu của biến i. - Lệnh input(i) trong TTT có thể được dịch sang C các lệnh scanf(“%d”, &i) hoặc scanf(“%c”, &i) hoặc scanf(“%f”, &i) tùy thuộc vào kiểu dữ liệu của biến i. Bước 4: Chuyển đổi các phép toán CTT Các phép toán CTT phải được chuyển thành các cấu trúc có mức độ cụ thể hơn trong ngôn ngữ C. Bảng 4.3. trình bày việc chuyển đổi các phép toán CTT của ngôn ngữ TTT sang ngôn ngữ C. Bảng 3.4. Chuyển đổi các phép toán CTT của ngôn ngữ TTT sang ngôn ngữ C OperatorCTT StatementC choice( char choice (char A, char B, float PA0, int cond1, float PA1, char A, int cond2, float PA2) char B, { float PA0, int n; int cond1, char C; float PA1, n = randn(100)/100; int cond2, if (cond1 !=0) float PA2 if (n<= PA1) C= A; else C= B; ) else if (cond2 != 0) if (n<= PA2) C= A; else C= B; else if (n<= PA0) C= A; else C= B; return C; } concur( char concur (char A, char B, float PA0, int cond1, float PA1, char A, int cond2, float PA2) char B, { float PA0, int n; int cond1, char C; float PA1, n = randn(100)/100; 33
int cond2, if (cond1 !=0) float PA2 if (n<= PA1) C= A; else C= B; ) else if (cond2 != 0) if (n<= PA2) C= A; else C= B; else if (n<= PA0) C= A; else C= B; return C; } indepen( char indepen char A, (char A, char B, float PA0, int cond1, float PA1, int cond2, char B, float PA2) float PA0, { int cond1, int n; float PA1, char C; int cond2, n = randn(100)/100; float PA2 if (cond1 !=0) ) if (n<= PA1) C= A; else C= B; else if (cond2 != 0) if (n<= PA2) C= A; else C= B; else if (n<= PA0) C= A; else C= B; return C; } deact( char deact (char A, char B, float PA0) char A, { char B, int n; float PA0) char C; n = randn(100)/100; C = A; if (n <PA0) C = B; return C; 34
} suspend( char suspend (char A, char B, float PA0) char A, { char B, int n; float PA0) char C; n = randn(100)/100; C = A; if (n <PA0) C = B; return C; } option( char option (char A, char B, float PA0) char A, { char B, int n; float PA0) char C; n = randn(100)/100; C = A; if (n <PA0) C = B; return C; } enabling( char enabling (char A, char B) char A, { char B, int n; ) char C; C = A; if (finish(A)) C = B; return C; } 3.3. XÂY DỰNG TRÌNH BIÊN DỊCH VÀ THỬ NGHIỆM Với mục đích xây dựng bộ chuyển đổi thực hiện dịch mô hình TESTCTT được viết bằng ngôn ngữ TTT sang chương trình C, tác giả sử dụng công cụ Lex và Yacc để phân tích từ vựng và phân tích cú pháp. Vì vậy, để xây dựng trình biên dịch chúng ta cần xây dựng luật mô tả (trong tập tin compile.l) theo ngôn ngữ đặc tả Lex, văn phạm (trong tập tin compile.y) theo ngôn ngữ đặc tả Yacc cho ngôn ngữ nguồn (đã được trình bày ở mục 3.1) và cơ 35
chế chuyển đổi từ ngôn ngữ nguồn sang ngôn ngữ đích (trong tập tin compile.c) đã được trình bày trong mục 3.2. Sau khi đã tập tin mô tả văn phạm, luật mô tả và cơ chế chuyển đổi, chúng ta sao chép vào chung một thư mục và tạo tập tin compile.bat với nội dung như sau: bison -d compile.y flex compile.l C:\Dev-Cpp\bin\gcc compile_tab.c lex.yy.c compile.c -o compile.exe Đồng thời sao chép vào thư mục này công cụ Bison và Flex như đã giới thiệu ở trên. Tạo một tập tin chứa mã nguồn ngôn ngữ nguồn TTT với nội dung sau: 1. TESTCTT VNNEWS; 2. var q0, q1, q2, q3: bool; 3. T, Tout: char; 4. begin 5. do 6. begin 7. q0 = (T 'D'); 8. q1 = (Tout == 'D'); 9. q2 = (Tout == 'G' and T == 'g'); 10. q3 = (Tout == 'R' and T == 'r') or (Tout == 'S' and T == 's'); 11. if (q0) 12. begin 13. T = choice ('c', '-', 0.8, newsLetter() == 0, 1, newsLetter() >=5, 0.1); 14. insert into U_ACTIONS (INPUT) values (T); 15. end 16. if (q1) 17. begin 18. T = choice ('g', 'r', 0.8, newsLetter() == 0, 1, newsLetter() >=5, 0.1); 19. insert into U_ACTIONS (INPUT) values (T); 20. end 21. if (q2) 22. begin 23. T = choice ('s', 'r', 0.2, newsLetter() == 0, 0, newsLetter() >=5, 0.1); 24. insert into U_ACTIONS (INPUT) values (T); 25. end 26. if (q3) 27. begin 28. T = choice ('c', '-', 0.8, newsLetter() == 0, 1, newsLetter() >= 5, 0.1); 29. insert into U_ACTIONS (INPUT) values (T); 36
30. end 31. Tout = call_VNNews(T); 32. insert into U_ACTIONS (OUTPUT) values (Tout); 33. T = deact('V', 'E', 0.9); 34. end 35. while (T<>'E'); 36. end 37. FUNCTION newsLetter() returns (result: int); 38. var get_news, remove_news: int; 39. begin 40. get_news = select count (*) from U_ACTIONS where INPUT = 'g'; 41. remove_news = select count (*) from U_ACTIONS where INPUT = 'r'; 42. result = get_news - remove_news; 43. end Sau đó điều chỉnh tên tập tin nguồn và tên tập tin chứa ngôn ngữ đích trong tập tin yacc. Sau đó thực thi tập tin compile.bat chúng ta sẽ có được trình biên dịch compile.exe. Thực thi compile.exe chúng ta sẽ thu được tập tin chứa ngôn ngữ đích. 37
KẾT LUẬN VÀ KIẾN NGHỊ Trong đề tài của mình, tác giả đã nghiên cứu về trình biên dịch, các thành phần cấu thành trình biên dịch, quy trình xây dựng trình biên dịch. Bên cạnh đó, tác giả cũng tìm hiểu các công cụ có thể hỗ trợ việc giúp xây dựng trình biên dịch được nhanh, hiệu quả. Trong các công cụ hiện nay đang có, tác giả chọn bộ công cụ Lex/Yacc để hỗ trợ việc xây dựng trình biên dịch của mình. Cuối cùng, với những nghiên cứu ở trên, tác giả đã tạo ra được trình biên dịch thực hiện biên dịch mã nguồn ngôn ngữ TTT sang mã nguồn C. Tuy nhiên hiện tại, trình biên dịch mới chỉ làm việc tốt với đoạn mã nguồn với các câu lệnh đơn giản, chưa biên dịch đúng với những mã nguồn có chứa câu lệnh truy vấn cơ sở dữ liệu. Ứng dụng này có thể sử dụng trong kiểm thử tự động, nó là một phần trong quá trình tự động sinh ca kiểm thử từ các ứng dụng tương tác khi chúng ta đặc tả ứng dụng tương tác cần kiểm thử bằng ngôn ngữ TTT. Tác giả sẽ tiếp tục hoàn thiện trình biên dịch để có thể biên dịch được mã nguồn TTT chứa câu lệnh làm việc với cơ sở dữ liệu, đồng thời nghiên cứu công cụ khác để có thể biên dịch ra được nhiều ngôn ngữ đích hơn. 38
TÀI LIỆU THAM KHẢO [1] Trần Văn Khánh. “Nghiên cứu ứng dụng lex/yacc để hỗ trợ phát sinh mã nguồn trong lập trình ứng dụng”, Luận văn thạc sĩ kỹ thuật Đại học Đà Nẵng, Chuyên ngành Khoa học máy tính, Mã số 60.48.01. [2] Long LT., Binh NT, Parissis I., “TTT: A Test Modeling Language for Interactive Applications Based on Task Trees”, Kỹ yếu Hội thảo quốc gia Một số vấn đề chọn lọc của công nghệ thông tin và truyền thông lần thứ XVI tại Đà Nẵng, Nhà xuất bản Khoa học và kỹ thuật. Trang. 333-338, 2013. [3] Khoa Công nghệ Thông tin, Đại học Thái Nguyên, “Giáo trình chương trình dịch”. [4] Alfred V.Aho, Ravi Sethi, Jeffrey D. Ullman, Trần Đức Quang dịch, “Trình biên dịch, nguyên lý và công cụ”, tập 1, Nhà xuất bản Thống kê. [5] L. du Bousquet, F. Ouabdesselam, I. Parissis, J. L. Richier, and N. Zuanon. “Lutess : a testing environment for synchronous software”. In Tool Support for System Specification, Development and Verification, pages 48–61. Advances in Computer Science. Springer Verlag, June 1998. 39
PHỤ LỤC Phụ lục 1. Nội dung tập tin compile.l %{ #include #include #include "compile.h" #include "compile_tab.h" void yyerror(char *); %} %% [0-9]+ { yylval.iValue = atoi(yytext); return INTEGER; } [-() =" return GE; " " return NE; 40
"+=" return ADD; "*=" return MUL; "/=" return DIV; "-=" return DEC; "begin" return 123; "end" return 125; "and" return AND; "or" return OR; "not" return NOT; [a-zA-Z_][a-zA-z0-9_+]+ { yylval.sVal = (char *) strdup(yytext); return(VAR); } [a-zA-Z] { yylval.sVal = (char *) strdup(yytext); return(VAR); } ['][a-zA-Z0-9-]['] { yylval.sVal = (char *) strdup(yytext); return(KT); } ["][a-zA-z0-9_+*:= -]+["] { yylval.sVal = (char *) strdup(yytext); return(STR); } "CREATE TABLE U_ACTIONS"[a-zA-Z0-9(),_ \t\n]+");" { yylval.sVal = (char *) strdup(yytext); return(CR_TABLE); } "docudtt("["]"udtt.txt"["]",conn,row,T)" { yylval.sVal = (char *) strdup(yytext); return(DOCUDTT); } [ \t\n]+ ; /* ignore whitespace */ . yyerror("Unknown character"); %% int yywrap(void) { return 1; } Phụ lục 2. Nội dung tập tin compile.y %{ #include #include #include #include #include "compile.h" extern int yylex(); 41
extern FILE *yyin; extern FILE *yyout; /* prototypes */ nodeType *opr(int oper, int nops, ); void push(nodeType *node); nodeType *var(char *v); nodeType *pushfunc(nodeType *p); nodeType *freefunc(); nodeType *pushretu(nodeType* name); nodeType *setkieu(char c); nodeType *newvar(char *v); nodeType *con(int value); nodeType *ktu(char *a); void putvar(char type, char *s); varNodeType *getvar(char *s); nodeType *savevar(nodeType *p, char k); void freeNode(nodeType *p); void freeVar(); void prtab(int n); void fprtab(int n); int ex(nodeType *p); int yylex(void); varNodeType *root=NULL; /* luu bien */ dsvarNode *dsvar=NULL; nodeType *funct=NULL; nodeType *retu=NULL; void yyerror(char *s); %} %union { int iValue; /* integer value */ char *sVal; /* string */ nodeType *nPtr; /* node pointer */ }; %token INTEGER %token VAR KT STR CR_TABLE DOCUDTT %token TESTCTT VNAME FUNC RETU %token INT CHAR BOOL FLOAT %token DO WHILE IF OUTPUT INPUT %token CHOICE INSERT DROP MODAL %nonassoc IFX INTO ACT VALUE TESTR DEACT %nonassoc ELSE TABLE IFSQL EXISTS %left GE LE EQ NE '>' '<' %left '+' '-' %left '*' '/' %left ADD DEC MUL DIV %left AND OR NOT %nonassoc UMINUS 42
%type stmt expr stmt_list list_var init_var %% program: function { freeVar(); getch(); exit(0); } ; function: function stmt { ex($2); freeNode($2);} | /* NULL */ ; stmt: ';' { $$ = opr(';', 2, NULL, NULL); } | expr ';' { $$ = $1; } | TESTCTT VAR ';' { $$ = opr(TESTCTT, 1, NULL); } | FUNC VAR '(' ')' {$$ = pushfunc(opr(FUNC, 1, newvar($2))); } | init_var ';' { push($1); $$ = opr(';', 2, NULL, NULL); } | RETU '(' init_var ')' ';' { push($3); $$ = opr(RETU, 2, pushretu($3), freefunc()); } | VNAME { $$ = opr(';', 2, NULL, NULL); } | OUTPUT '(' VAR ')' ';' { $$ = opr(OUTPUT, 1, var($3)); } | OUTPUT '(' STR ')' ';' { $$ = opr(OUTPUT, 1, ktu($3)); } | INPUT '(' VAR ')' ';' { $$ = opr(INPUT, 1, var($3)); } | VAR '=' expr ';' { $$ = opr('=', 2, var($1), $3); } | VAR ADD expr ';' { $$ = opr(ADD, 2, var($1), $3); } | VAR DEC expr ';' { $$ = opr(DEC, 2, var($1), $3); } | VAR MUL expr ';' { $$ = opr(MUL, 2, var($1), $3); } | VAR DIV expr ';' { $$ = opr(DIV, 2, var($1), $3); } | DROP TABLE IFSQL EXISTS ACT ';'{ $$ = opr(DROP, 1, NULL); } | INSERT INTO ACT '(' VAR ')' VALUE '(' VAR ')' ';' { $$ = opr(INSERT, 4, NULL, newvar($5), NULL, var($9)); } | INSERT INTO ACT '(' list_var VAR ')' VALUE '(' list_var VAR ')' ';' { $$ = opr(INSERT, 4, $5, newvar($6), $10, var($11)); } | MODAL '(' VAR ',' VAR ',' VAR ',' VAR ',' INTEGER ',' INTEGER ',' INTEGER ')' ';' { $$ = opr(MODAL, 7, var($3), var($5), var($7), var($9), con($11), con($13), con($15)); } | CR_TABLE { $$ = opr(CR_TABLE, 1, ktu($1)); } | DOCUDTT ';' { $$ = opr(DOCUDTT, 1, NULL); } | WHILE '(' expr ')' stmt { $$ = opr(WHILE, 2, $3, $5); } | DO stmt WHILE '(' expr ')' { $$ = opr(DO, 2, $2, $5);} | IF '(' expr ')' stmt %prec IFX { $$ = opr(IF, 2, $3, $5); } | IF '(' expr ')' stmt ELSE stmt { $$ = opr(IF, 3, $3, $5, $7);} | '{' stmt_list '}' { $$ = opr('{', 1, $2); } ; stmt_list: stmt { $$ = $1; } | stmt_list stmt { $$ = opr(';', 2, $1, $2); } ; 43
list_var: VAR ',' { $$ = opr(',', 1, newvar($1)); } | list_var VAR ',' { $$ = opr(';', 2, $1, opr(',', 1, newvar($2)));} ; init_var: VAR ':' INT { $$ = opr(INT, 2, savevar(newvar($1), 'd'), NULL);} | VAR ':' CHAR { $$ = opr(CHAR, 2, savevar(newvar($1), 'c'), NULL); } | VAR ':' BOOL { $$ = opr(INT, 2, savevar(newvar($1), 'd'), NULL); } | VAR ':' FLOAT { $$ = opr(FLOAT, 2, savevar(newvar($1), 'f'), NULL); } | list_var VAR ':' INT { $$ = opr(INT, 2, savevar($1, 'd'), savevar(newvar($2), 'd')); } | list_var VAR ':' CHAR { $$ = opr(CHAR, 2, savevar($1, 'c'), savevar(newvar($2), 'd')); } | list_var VAR ':' BOOL { $$ = opr(INT, 2, savevar($1, 'd'), savevar(newvar($2), 'd')); } | list_var VAR ':' FLOAT { $$ = opr(FLOAT, 2, savevar($1, 'f'), savevar(newvar($2), 'd')); } ; expr: INTEGER { $$ = con($1); } | VAR { $$ = var($1); } | VAR '(' ')' { $$ = opr(FUNC, 1, newvar($1)); } | KT { $$ = ktu($1); } | STR { $$ = ktu($1); } | INTEGER '.' INTEGER { $$ = opr('.', 2, con($1), con($3)) } | '-' expr %prec UMINUS { $$ = opr(UMINUS, 1, $2); } | CHOICE '(' expr ',' expr ',' expr ',' expr ',' expr ',' expr ',' expr ')' { $$ = opr(CHOICE,7,$3,$5,$7,$9,$11,$13,$15); } | DEACT '(' expr ',' expr ',' expr ')' { $$ = opr(DEACT, 3, $3, $5, $7); } | TESTR '(' expr ',' expr ',' expr ')' { $$ = opr(TESTR, 3, $3, $5, $7); } | expr '+' expr { $$ = opr('+', 2, $1, $3); } | expr '-' expr { $$ = opr('-', 2, $1, $3); } | expr '*' expr { $$ = opr('*', 2, $1, $3); } | expr '/' expr { $$ = opr('/', 2, $1, $3); } | expr ' ' expr { $$ = opr('>', 2, $1, $3); } | expr GE expr { $$ = opr(GE, 2, $1, $3); } | expr LE expr { $$ = opr(LE, 2, $1, $3); } | expr NE expr { $$ = opr(NE, 2, $1, $3); } | expr EQ expr { $$ = opr(EQ, 2, $1, $3); } | expr AND expr { $$ = opr(AND, 2, $1, $3); } | expr OR expr { $$ = opr(OR, 2, $1, $3); } | NOT expr { $$ = opr(NOT, 1, $2); } | '(' expr ')' { $$ = opr('(', 1, $2); } ; 44
%% #define SIZEOF_NODETYPE ((char *)&p->con - (char *)p) void push(nodeType *node){ /* Luu khai bao bien */ dsvarNode *t; // Cap phat vung nho t = (dsvarNode*) malloc(sizeof(dsvarNode)); t->nt = node; t->link=NULL; // Them bien vao cuoi dslk if(dsvar==NULL) dsvar=t; else { dsvarNode *u; u=dsvar; while (u->link!=NULL) u=u->link; u->link=t; } } nodeType *pushfunc(nodeType *p){ /* Luu khai bao ham */ funct = p; return NULL; } nodeType *freefunc(){ /* Lay ham da luu va free */ nodeType *t; t = funct; funct = NULL; return t; } nodeType *pushretu(nodeType* name){ /* Luu return */ nodeType *p; size_t nodeSize; // Cap phat vung nho nodeSize = SIZEOF_NODETYPE + sizeof(oprNodeType) + 1 * sizeof(nodeType*); if ((p = malloc(nodeSize)) == NULL) yyerror("out of memory1"); // Gan kieu va gia tri p->type = name->type; p->opr.oper = name->opr.oper; p->opr.nops = 1; p->opr.op[0] = var(name->opr.op[0]->var->gt); retu = p->opr.op[0]; return p; } void putvar(char type, char *s){ /* Day bien vao danh sach lien ket */ varNodeType *v; varNodeType *tmp; v = (varNodeType*) malloc(sizeof(varNodeType)); v->type=type; 45
v->gt = (char*) malloc(sizeof(s)+1); strcpy(v->gt, s); v->link=NULL; if(root== NULL) root=v; else { tmp=root; while(tmp->link!= NULL) tmp=tmp->link; tmp->link=v; } } varNodeType* getvar(char *s){ /* Lay bien tu dslk*/ varNodeType *tmp; for( tmp = root; tmp!=NULL; tmp = tmp->link) if(strcmp (tmp->gt,s)==0) return tmp; return NULL; } nodeType *savevar(nodeType *p, char k){ /* Luu bien */ if(p->type == typeVar) putvar(k, p->var->gt); else if(p->type == typeOpr){ savevar(p->opr.op[0], k); if(p->opr.oper == ';') savevar(p->opr.op[1], k); } return p; } nodeType *con(int value) { /* Luu so */ nodeType *p; size_t nodeSize; /* allocate node */ nodeSize = SIZEOF_NODETYPE + sizeof(conNodeType); if ((p = malloc(nodeSize)) == NULL) yyerror("out of memory5"); /* copy information */ p->type = typeCon; p->con.value = value; return p; } nodeType *var(char *v) { /* Lay gia tri bien */ nodeType *p; size_t nodeSize; /* allocate node */ nodeSize = SIZEOF_NODETYPE + sizeof(varNodeType); if ((p = malloc(nodeSize)) == NULL) yyerror("out of memory4"); p->type = typeVar; p->var = getvar(v); return p; } 46
nodeType *ktu(char *a) { /* khai bao kieu ki tu va chuoi */ nodeType *p; size_t nodeSize; /* allocate node */ nodeSize = SIZEOF_NODETYPE + sizeof(ktNodeType); if ((p = malloc(nodeSize)) == NULL) yyerror("out of memory3"); p->type = typeKt; p->kt.gt = (char*) malloc(sizeof(a)+1); strcpy(p->kt.gt, a); return p; } nodeType *newvar(char *name) /* Cap phat bien moi */ { if(getvar(name) != NULL) return var(name); else{ nodeType *p; p = (nodeType*) malloc(sizeof(nodeType)); if (p == NULL) yyerror("out of memory2"); p->type = typeVar; p->var = (varNodeType*) malloc(sizeof(varNodeType)); p->var->gt = (char*) malloc(sizeof(name)+1); strcpy(p->var->gt, name); return p; } } nodeType *opr(int oper, int nops, ) { /* Luu nodeType */ va_list ap; nodeType *p; size_t nodeSize; int i; /* allocate node */ nodeSize = SIZEOF_NODETYPE + sizeof(oprNodeType) + (nops - 1) * sizeof(nodeType*); if ((p = malloc(nodeSize)) == NULL) yyerror("out of memory1"); /* copy information */ p->type = typeOpr; p->opr.oper = oper; p->opr.nops = nops; va_start(ap, nops); for (i = 0; i opr.op[i] = va_arg(ap, nodeType*); va_end(ap); return p; } 47
void freeNode(nodeType *p) { /* giai phong nodeType */ int i; if (p==NULL) return; if (p->type == typeOpr) { for (i = 0; i opr.nops; i++) freeNode(p->opr.op[i]); } else{ if(p->type == typeKt){ free(p->kt.gt); } else{ if(p->type == typeVar){ return; } } } free(p); } void freeVar(){ /* Giai phong dslk luu bien */ for(;root!=NULL;){ varNodeType *tmp = root; root=tmp->link; free(tmp->gt); free(tmp); } } void prtab(int n){ /* in tab */ int i; for(i=0; i<n; i++) printf("\t"); } void fprtab(int n){ /* in tab ghi vao file */ int i; for(i=0; i<n; i++) fprintf(yyout,"\t"); } void yyerror(char *s) { /* thong bao loi */ fprintf(stdout, "%s\n", s); } int main() { FILE *out = fopen("result.c","w");; FILE *in = fopen("reserve.txt", "r"); if (!in) { printf("Khong tim thay file"); return -1; } yyin = in; yyout = out; yyparse(); fclose(in); fclose(out); return 0; 48
} Phụ lục 3. Nội dung tập tin compile.c #include #include "compile.h" #include "compile_tab.h" static int lbl, tab; int ex(nodeType *p) { if (!p) return 0; switch(p->type) { case typeCon: printf("%d", p->con.value); break; case typeVar: printf("%s", p->var->gt); break; case typeKt: printf("%s", p->kt.gt); break; case typeOpr: switch(p->opr.oper) { case TESTCTT: printf("#include \n"); printf("void main()\n"); break; case RETU: switch (p->opr.op[0]->opr.oper){ case INT: printf("int ");break; case CHAR: printf("char ");break; case FLOAT: printf("float ");break; default: printf("void "); } ex(p->opr.op[1]); break; case FUNC: ex(p->opr.op[0]); printf("()"); break; case INT: prtab(tab); printf("int "); ex(p->opr.op[0]); ex(p->opr.op[1]); printf(";\n"); break; case CHAR: prtab(tab); printf("char "); ex(p->opr.op[0]); ex(p->opr.op[1]); 49
printf(";\n"); break; case FLOAT: prtab(tab); printf("float "); ex(p->opr.op[0]); ex(p->opr.op[1]); printf(";\n"); break; case WHILE: prtab(tab); printf("while ("); ex(p->opr.op[0]); printf(")\n"); ex(p->opr.op[1]); break; case DO: prtab(tab); printf("do\n"); ex(p->opr.op[0]); prtab(tab); printf("while ("); ex(p->opr.op[1]); printf(");\n"); break; case IF: prtab(tab); printf("if ("); ex(p->opr.op[0]); printf(")\n"); if (p->opr.nops > 2) { /* if else */ ex(p->opr.op[1]); prtab(tab); printf("else\n"); ex(p->opr.op[2]); } else { /* if */ ex(p->opr.op[1]); } break; case '{': if (funct != NULL){printf("void ");ex(funct);freeNode(funct);funct=NULL;} prtab(tab++); printf("{\n"); while(dsvar!=NULL){ dsvarNode *tmp; tmp=dsvar; ex(tmp->nt); dsvar=dsvar->link; freeNode(tmp->nt); free(tmp); } 50
if(retu!=NULL){ nodeType *tmp; tmp = retu; retu=NULL; ex(p->opr.op[0]); prtab(tab); printf("return "); ex(tmp); printf(";\n"); freeNode(tmp); } else ex(p->opr.op[0]); prtab( tab); printf("}\n"); break; case INPUT: prtab(tab); printf("scanf(\"%%%c\", &", p->opr.op[0]->var->type); ex(p->opr.op[0]); printf(");\n"); break; case OUTPUT: prtab(tab); if (p->opr.op[0]->type == typeVar){ printf("printf(\"%%%c\", ", p->opr.op[0]->var->type); } else { printf("printf("); } ex(p->opr.op[0]); printf(");\n"); break; case CHOICE: printf("choice("); ex(p->opr.op[0]); printf(", "); ex(p->opr.op[1]); printf(", "); ex(p->opr.op[2]); printf(", "); ex(p->opr.op[3]); printf(", "); ex(p->opr.op[4]); printf(", "); ex(p->opr.op[5]); printf(", "); ex(p->opr.op[6]); printf(")"); break; case DROP: prtab(tab); printf("(mysql_query(conn, \"DROP TABLE IF EXISTS U_ACTIONS\"))\n"); prtab(tab); 51
printf("{ fprintf(stderr, \"%%s \\n\", mysql_error(conn));}\n"); break; case INSERT: prtab(tab); printf("sprintf(msg,\"insert into U_ACTIONS("); ex(p->opr.op[0]); ex(p->opr.op[1]); printf(") values("); ex1(p->opr.op[2]); printf("'%%%c')\", ", p->opr.op[3]->var->type); ex(p->opr.op[2]); ex(p->opr.op[3]); printf(");\n"); prtab(tab); printf("if(mysql_query(conn, msg))\n"); prtab(tab); printf("\t printf(stderr, \"%%s \\n\", mysql_error(conn));\n"); break; case MODAL: prtab(tab); printf("Modalities("); ex(p->opr.op[0]); printf(", &"); ex(p->opr.op[1]); printf(", &"); ex(p->opr.op[2]); printf(", &"); ex(p->opr.op[3]); printf(", "); ex(p->opr.op[4]); printf(", "); ex(p->opr.op[5]); printf(", "); ex(p->opr.op[6]); printf(");\n"); break; case CR_TABLE: prtab(tab); printf("if(mysql_query(conn, \""); ex(p->opr.op[0]); printf("\")){\n"); prtab(tab); printf("\tfprintf(stderr, \"%%s \\n\", mysql_error(conn));\n"); prtab(tab); printf("}\n"); break; case DOCUDTT: prtab(tab); printf("docudtt(\"udtt.txt\",conn,row,T);\n"); break; case DEACT: 52
printf("deact("); ex(p->opr.op[0]); printf(", "); ex(p->opr.op[1]); printf(", "); ex(p->opr.op[2]); printf(")"); break; case TESTR: printf("TestR_E("); ex(p->opr.op[0]); printf(", "); ex(p->opr.op[1]); printf(", "); ex(p->opr.op[2]); printf(")"); break; case '=': prtab(tab); ex(p->opr.op[0]); printf(" = "); ex(p->opr.op[1]); printf(";\n"); break; case ADD: prtab(tab); ex(p->opr.op[0]); printf(" += "); ex(p->opr.op[1]); printf(";\n"); break; case DEC: prtab(tab); ex(p->opr.op[0]); printf(" -= "); ex(p->opr.op[1]); printf(";\n"); break; case MUL: prtab(tab); ex(p->opr.op[0]); printf(" *= "); ex(p->opr.op[1]); printf(";\n"); break; case DIV: prtab(tab); ex(p->opr.op[0]); printf(" /= "); ex(p->opr.op[1]); printf(";\n"); break; case UMINUS: printf("-"); 53
ex(p->opr.op[0]); break; case NOT: printf("!"); ex(p->opr.op[0]); break; case ',': ex(p->opr.op[0]); printf(", "); break; case '.': ex(p->opr.op[0]); printf("."); ex(p->opr.op[1]); break; case '(': printf("("); ex(p->opr.op[0]); printf(")"); break; default: ex(p->opr.op[0]); switch(p->opr.oper) { case '+': printf("+"); break; case '-': printf("-"); break; case '*': printf("*"); break; case '/': printf("/"); break; case ' ': printf(">"); break; case GE: printf(">="); break; case LE: printf(" opr.op[1]); } } return 0; system("pause"); } int ex1(nodeType *p){ if (!p) return 0; switch(p->type) { case typeVar: printf("'%%%c'", p->var->type); break; case typeOpr: ex1(p->opr.op[0]); printf(", "); break; } 54
return 0; } Phụ lục 4. Nội dung chương trình C được tạo ra sau khi biên dịch mô hình TESTCTT ở mục 3.3. #include #include #include #include #include static char *opt_host_name = "localhost"; //server host (mac dinh :'localhost') static char *opt_user_name = "root"; // tai khoan (mac dinh 'root') static char *opt_password = ""; //mat khau (mac dinh 'null') static unsigned int opt_port_num = 3306; // Cong ket noi (mac dinh : 3306) static char *opt_socket_name = NULL; /* socket name (use built-in value) */ static char *opt_db_name = "DBTest"; // ten Database static unsigned int opt_flags = 0; /* connection flags (none) */ int randn(int n) { return rand()%n + 1; } char deact(char A, char B, float PA0) { int n; char C; n= randn(100); C=A; if (n< PA0) C= B; return C; } char choice(char A,char B,float PA0,int cond1,float PA1,int cond2,float PA2) { float n; char C; 55
//randomize(); //n= random(100) n= randn(100)/100; if (cond1 !=0) if (n<= PA1) C= A; else C= B; else if (cond2 != 0) if (n<= PA2) C= A; else C= B; else if (n<= PA0) C= A; else C= B; return C; } int newsLetter() { int get_news, remove_news,result ; //get_news = select count (*) from U_ACTIONS where INPUT = 'g'; //remove_news = select count (*) from U_ACTIONS where INPUT = 'r'; //result = get_news - remove_news; result =0; char msgG[255],msgR[255]; sprintf(msgG,"SELECT count(*) FROM U_ACTIONS WHERE INPUT='g'"); sprintf(msgR,"SELECT count(*) FROM U_ACTIONS WHERE INPUT='r'"); printf("\n"); if (mysql_query(conn, msgG)) { fprintf(stderr, "%s \n", mysql_error(conn)); system("pause");} else MYSQL_RES *resultG = mysql_store_result(conn); if (mysql_query(conn, msgR)) { fprintf(stderr, "%s \n", mysql_error(conn)); system("pause");} else MYSQL_RES *resultR = mysql_store_result(conn); nb = *resultG - *resultR; printf("\n G= %d , R = %d, nb =%d", resultG, resultR,result); mysql_free_result(resultG); mysql_free_result(resultR); return result; } 56
void createTable(MYSQL *conn,MYSQL_ROW row) { if (mysql_query(conn, "DROP TABLE IF EXISTS U_ACTIONS")) { fprintf(stderr, "%s \n", mysql_error(conn));} if (mysql_query(conn, "CREATE TABLE U_ACTIONS(INPUT VARCHAR(10),OUTPUT VARCHAR(10))")) { fprintf(stderr, "%s \n", mysql_error(conn));} } int main () { MYSQL *conn; /* pointer to connection handler */ MYSQL_RES *res; /* holds the result set */ MYSQL_ROW row0, row1, row, row2; /* Cai dat tac vu ket noi */ conn = mysql_init (NULL); /* Ham ket noi den server */ mysql_real_connect (conn, opt_host_name, opt_user_name, opt_password, opt_db_name, opt_port_num, opt_socket_name, opt_flags); createTable(conn,row); int q0, q1, q2, q3, q4; char T, Tout; char msg[255]; do { q0 = (T != 'c' and Tout != 'D'); q1 = (Tout == 'D'); q2 = (Tout == 'G' && T == 'g'); q3 = (Tout == 'R' && T == 'r') || (Tout == 'S' && T == 's'); if (q0){ T = choice ('c', '-', 0.8, newsLetter() = 0, 1, newsLetter() >=5, 0.1); Tout = call_VNNews(T); sprintf(msg,"INSERT INTO U_ACTIONS (INPUT, OUTPUT) VALUES('%c', '%c')",T, Tout); } if (q1){ 57
T = choice ('g', 'r', 0.8, newsLetter() = 0, 1, newsLetter() >=5, 0.1); Tout = call_VNNews(T); sprintf(msg,"INSERT INTO U_ACTIONS (INPUT, OUTPUT) VALUES('%c', '%c')",T, Tout); } if (q2){ T = choice ('s', 'r', 0.2, newsLetter() = 0, 0, newsLetter() >=5, 0.1); Tout = call_VNNews(T); sprintf(msg,"INSERT INTO U_ACTIONS (INPUT, OUTPUT) VALUES('%c', '%c')",T, Tout); } if (q3){ T = choice ('c', '-', 0.8, newsLetter() = 0, 1, newsLetter() >= 5, 0.1); Tout = call_VNNews(T); sprintf(msg,"INSERT INTO U_ACTIONS (INPUT, OUTPUT) VALUES('%c', '%c')",T, Tout); } T = deact('V', 'E', 0.9); //V - use VNNews, E - Exit while (T != 'E')//E = exit VNNews //print test data if (mysql_query(conn, "SELECT * FROM U_ACTIONS ")) { fprintf(stderr, "%s \n", mysql_error(conn)); } MYSQL_RES *result = mysql_store_result(conn); if (result == NULL){ fprintf(stderr, "%s \n", mysql_error(conn)); } FILE *f1; char c; f1= fopen("C:\sinhdl.txt","w"); int num_fields = mysql_num_fields(result); fprintf (f1, " INPUT | OUTPUT |\n"); fprintf (f1, "\n===\n\n"); while ((row = mysql_fetch_row(result))) { for(int i = 0; i < num_fields; i++) { 58
fprintf(f1,"%s ", row[i]); } fprintf(f1,"\n"); } fclose(f1); mysql_free_result(result); } Bản sao Thuyết minh đề tài đã được phê duyệt; Bản photo Hợp đồng triển khai thực hiện; Minh chứng sản phẩm của đề tài; 59