Bài giảng Chương trình dịch: Bài giảng 1 - Nguyễn Phương Thái

Bài giảng 1 giúp người học nắm bắt được một số nội dung cơ bản về môn học Chương trình dịch như: Chương trình dịch là gì? Các loại chương trình dịch; ngôn ngữ máy, hợp ngữ, và ngôn ngữ bậc cao; kiến trúc của một chương trình dịch; phân tích từ vựng; phân tích cú pháp;... Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Chương trình dịch: Bài giảng 1 - Nguyễn Phương Thái Nguyễn Phương Thái Bộ môn Khoa học Máy tính http://www.coltech.vnu.vn/~thainp/ Thông tin môn học Giảng viên Nguyễn Phương Thái Trang nhà: http://www.coltech.vnu.vn/~thainp/ Trợ giảng: Lê Minh Khôi (Bộ môn Khoa học Máy tính) Nguyễn Duy Khương (Phòng thí nghiệm Tương tác Người­ Máy) Môn học tiên quyết: lập trình (C/C++, Java), toán rời  rạc, cấu trúc dữ liệu và giải thuật 15/11/15 2 Thông tin môn học  Sách và tài liệu tham khảo ̉ [1] Bài giang Ly ́ thuyết và Thực hành Chương Trình Dịch. Lê  Anh Cường, Khoa Công nghệ, ĐHQG Hà Nội, 2004 [2] Giáo trình lý thuyết, thực hành môn học Chương trình dịch.  Phạm Hồng Nguyên, Khoa Công nghệ, ĐHQG Hà Nội, 1998 [3] Ngôn ngữ hình thức. Nguyễn Văn Ba, ĐHBK Hà Nội, 1994 [4] Thực hành kỹ thuật biên dịch. Nguyễn Văn Ba, ĐHBK Hà Nội,  1993 [5] Compiler: principles techniques and tools. A.V. Aho, Ravi Sethi,  D. Ulman, 1986  15/11/15 3 Thông tin môn học  Khóa học tương tự: http://www.cse.unsw.edu.au/~cs3131/   Trang web môn học (cho cả hai lớp K51CC và K51CD): http://www.coltech.vnu.vn/courses/ 15/11/15 4 Chương trình dịch là gì? Mã nguồn Mã đích Chương trình dịch Lỗi Nhận dạng chương trình hợp lệ (hay không) Sinh đúng (và hiệu quả) mã 15/11/15 5 Các loại chương trình dịch Trình biên dịch → Có nhiệm vụ dịch một chương trình từ ngôn ngữ này sang  ngôn ngữ khác (chương trình thực thi được) → Chương trình nên được cải tiến bằng cách này hay cách  khác Trình thông dịch → Đọc một chương trình và sinh ra kết quả thực thi chương  trình đó 15/11/15 6 Ngôn ngữ máy, hợp ngữ, và ngôn ngữ bậc cao 1. Ngôn ngữ máy  Đây là ngôn ngữ duy nhất máy tính có thể hiểu trực tiếp  “Ngôn ngữ tự nhiên” của máy tính  Được định nghĩa bằng cách thiết kế phần cứng  Phụ thuộc máy  Nói chung bao gồm các xâu của các số nhị phân  Ra lệnh cho máy tính thực hiện các phép toán cơ sở  Mỗi lần một lệnh  Khó hiểu với con người  Ví dụ: +1300042774 +1400593419 +1200274027 7 Ngôn ngữ máy, hợp ngữ, và ngôn ngữ bậc cao 2. Hợp ngữ  Sử dụng các từ viết tắt tiếng Anh để biểu diễn lệnh   Dễ hiểu hơn với con người  Nhưng lại không phải là “ngôn ngữ tự nhiên” của máy tính  Cần các trình biên dịch: hợp ngữ  ngôn ngữ máy  Ví dụ: LOAD BASEPAY ADD OVERPAY STORE GROSSPAY 8 Ngôn ngữ máy, hợp ngữ, và ngôn ngữ bậc cao 3. Các ngôn ngữ bậc cao   Tương tự tiếng Anh ngày nay, sử dụng các ký hiệu toán học  thông dụng  Một câu lệnh đơn có thể thực hiện một khối lượng công  việc đáng kể so với chương trình tương ứng viết bằng hợp  ngữ  Ví dụ: grossPay = basePay + overTimePay 9 Các nhiệm vụ của sinh viên Học các kỹ thuật, thuật toán, và công cụ của chương  trình dịch Học cách sử dụng chương trình dịch (và chương trình  gỡ rối) hiệu quả hơn Hiểu hơn về hành vi của chương trình Học cách xây dựng một hệ thống lớn và đáng tin cậy 15/11/15 10 Tri thức sinh viên cần đạt được Ôtômát hữu hạn trạng thái và quan hệ với biểu thức  chính qui Văn phạm phi ngữ cảnh và quan hệ với phân tích cú  pháp phi ngữ cảnh Các chiến lược đặc tả ngôn ngữ hình thức Phân tích từ dưới lên và từ trên xuống Văn phạm thuộc tính Kiểm tra kiểu Máy ảo Java 15/11/15 11 Kỹ năng sinh viên cần đạt được Có thể tự xây dựng các hệ phân tích từ tố, phân tích cú  pháp, phân tích ngữ nghĩa và sinh mã Có thể sử dụng các công cụ xây dựng chương trình  dịch: từ vựng và cú pháp Biết cách mô tả cú pháp và ngữ nghĩa của một ngôn ngữ Hiểu về sinh mã Hiểu về máy ảo, đặc biệt là JVM 15/11/15 12 Kiến trúc của một chương trình dịch Mã nguồn Phân tích từ tố (từ vựng) Phân tích cú pháp Phân tích ngữ nghĩa Sinh mã trung gian Tối ưu mã Sinh mã đích Mã đích 15/11/15 13 Phân tích từ vựng Nhiệm vụ Nhóm các ký tự thành các từ tố ­­ các đơn vị của cú pháp Ví dụ: position = initial + rate * 60 Sẽ được phân tích là: identifier position (tên) assignment operator = (toán tử gán) identifier initial (tên) plus sign (dấu trừ) multiplication sign (dấu nhân) interger constant 60 (hằng số nguyên) Xâu ký tự tạo thành từ tố gọi là từ vị 15/11/15 14 Phân tích cú pháp Nhiệm vụ của hệ phân tích cú pháp (parser) Nhóm các từ tố thành các cụm từ cú pháp Biểu diễn các cụm từ cú pháp thành các cây cú pháp trừu  tượng AST (abstract syntax tree) Sinh ra các thông báo lỗi đúng Cố gắng phát hiện và khôi phục lỗi Cú pháp của một ngôn ngữ lập trình thường được mô tả  bằng một văn phạm phi ngữ cảnh (context­free grammar  – CFG) 15/11/15 ...