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

Chia sẻ: Bananalachuoi | Ngày: | Loại File: PDF | Số trang:59

Thêm vào BST

Báo xấu

27
lượt xem 7
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục tiêu nghiên cứu đề tài là á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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đề 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

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