Tổng hợp bài giảng môn Thực hành xây dựng chương trình dịch| Bài giảng môn Thực hành xây dựng chương trình dịch| Trường Đại học Bách Khoa Hà Nội
Đọc một tệp văn bản, hãy lập một bảng chỉ mục (index table) cho tệp văn bản đó.
Bảng chỉ dẫn liệt kê tất cả các từ xuất hiện trong văn bản theo quy cách
Mỗi từ được liệt kê một lần cùng với số lần xuất hiện trong văn bản và dòng xuất hiện từ đó.
Các từ phải được sắp xếp theo thứ tự từ điển
Môn: Thực hành xây dựng chương trình dịch 1 tài liệu
Trường: Đại học Bách Khoa Hà Nội 2.8 K tài liệu
Tác giả:
Preview text:
Thực hành CHƯƠNG TRÌNH DỊCH
Bài 1: Lập bảng chỉ mục Phạm Đăng Hải haipd@soict.hust.edu.vn Đề bài
• Đọc một tệp văn bản, hãy lập một bảng chỉ
mục (index table) cho tệp văn bản đó.
• Bảng chỉ dẫn liệt kê tất cả các từ xuất hiện
trong văn bản theo quy cách
– Mỗi từ được liệt kê một lần cùng với số lần xuất
hiện trong văn bản và dòng xuất hiện từ đó.
– Các từ phải được sắp xếp theo thứ tự từ điển * 2 Mô tả chi tiết • Tệp văn bản
– Đoạn văn bản tiếng Anh, định dạng ASCII
• Tệp mẫu “vanban.txt”
• Từ là những dãy chữ cái phân biệt bởi
– Khoảng trống/ Dấu phân cách
• Các ký tự không phải chữ cái (a..z, A..Z)
• Không phân biệt chữ hoa, chữ thường
– Khi đưa vào bảng chỉ mục phải chuyển tất cả các
ký tự thành chữ thường * 3 Mô tả chi tiết
• Không đưa vào bảng chỉ mục
– Những từ không có ý nghĩa để tra
• Ví dụ: for, the, an,…
• Những từ như vậy được lưu trong tệp: “stopw.txt”, mỗi từ một dòng. – Những danh từ riêng.
• Đó là những từ có chữ cái đầu là chữ hoa nhưng
không đứng sau dấu chấm câu.
– Ví dụ: “Will you visit Hanoi someday?” * 4 Tình bày kết quả
Trình bày kết quả theo dòng:
– Đầu tiên là từ, sau đó là phần dãy số.
– Số đầu tiên là số lần xuất hiện của từ,
– Các số tiếp theo là dòng mà từ đó xuất hiện. •Ví dụ answer 7,8,12,15 ant 2,4,6 baby 7,9,21 cruel 2,4,5 * 5
Thiết kế khung cho chương trình • Đọc một từ.
• Kiểm tra từ có nghĩa.
• Lưu từ vào danh sách được sắp xếp.
• Xác định các thông tin cho từ có nghĩa
– Số lần xuất hiện, chỉ số dòng. * 6 Đọc từ
• Đọc từng ký tự cho tới khi gặp ký tự kết thúc từ.
– Ký tự kết thúc từ:?
• Chữ số, dấu cách, dấu chấm câu, dấu xuống dòng..
• Không phải chữ cái a..zA..Z – Hàm int isalpha(char c); • Kỹ thuật:
– Xác định ký tự đầu tiên của từ?
– Ghép các ký tự thành một từ?
• Hàm ghép xâu. char * strcat(char * d, const char *s )?
– Chuyển ký tự về chữ thường? • Hàm int tolower(char c) * 7
Kiểm tra từ có nghĩa
•Loại bỏ nếu từ trong danh sách “stopw”,
•Loại bỏ nếu từ là danh từ riêng. •Kỹ thuật:
– Kiểm tra từ có trong danh sách • Hàm so sánh xâu.
– Hàm int strcmp(const char * s1, const char * s2)
– Kiểm tra từ có phải danh từ riêng
• Vấn đề: Nếu danh từ riêng đứng ở đầu câu? * 8
Chèn từ vào danh sách
• Nếu từ chưa có trong danh sách
→ thêm từ vào danh sách.
• Nếu từ đã có trong danh sách
→ Tăng số lần xuất hiện
→ Thêm chỉ số dòng (nếu chưa có) • Kỹ thuật:
– Sắp xếp danh sách theo thứ tự từ điển? • Hàm so sánh xâu
– Xác định chỉ số dòng?
• Ký tự xuống dòng: /n và /r
– Khác biệt giữa linux và window? → sử dụng ‘\n’ * 9
Biến trong chương trình
• Danh sách từ cho bảng chỉ mục → Sử dụng mảng
• Sắp xếp kiểu thêm dần
• Vấn đề: kích thước mảng !?
• Dach sách từ không có nghĩa tra cứu: → Sử dụng mảng. • Dãy các chỉ số dòng → Sử dụng xâu ký tự. Ví dụ “2, 5, 6, 7, 12” * 10
Biến trong chương trình Danh sách liên kết Trỏ Cuối Trỏ Đầu Mục Từ Số lần xuất hiên Dách sách dòng * 11
Kiến thức lập trình cần chú ý • Thao tác với tệp: – Mở, đóng tệp,
– Đọc ký tự (int fgetc(FILE * flot) )
• Thao tác với xâu ký tự: – So sánh xâu ký tự, – Thêm ký tự vào xâu, • Thao tác con trỏ
– Xin, giải phóng vùng nhớ
• Hàm malloc(int size), free(void *)..
– Chèn phần tử vào danh sách * 12 Quy cách nộp bài
• Nộp bài qua email: haipd@soict.hust.edu.vn
• Hạn nộp bài: 23h59m59s, Thứ sáu: 26/2/2021 • Quy cách nộp bài
– Một file nén duy nhất Ten_HoDem.zip
• File mã nguồn *.c và *.h
• File readme.txt (nếu cần) • Các file input • File ảnh kết quả • Bộ dịch: DEV C++ 5.11 • Sao chép bài !? * 13 Thực hành CHƯƠNG TRÌNH DỊCH
Bài 2: Phân tích từ vựng Phạm Đăng Hải haipd@soict.hut.edu.vn Scanner Token Chương Phân tích Phân tích trình nguồn từ vựng cú pháp getToken() Bảng ký hiệu
• Trong một chương trình dịch, thành phần
thực hiện chức năng phân tích từ vựng gọi là scanner. * 2 Scanner * 3
Nhiệm vụ của bộ scanner
• Bỏ qua các ký tự vô nghĩa
– Dấu cách, tab, ký tự xuống dòng, chú thích.
• Phát hiện các ký tự không hợp lệ • Phát hiện token
– Định danh (identifier) /Từ khóa (keyword)
– Số (number) /Hằng ký tự/xâu ký tự – Special character…
• Chuyển lần lượt các token cho bộ phân tích cú pháp (parser) * 4
Bảng chữ cái của KPL
•Chữ cái (letter): a-z, A-Z, ‘_’ •Chữ số (digit): 0-9
•Các ký hiệu đặc biệt +, -, *, /, >, <,!, =,
[space], [comma], ., :, ;, ‘, (, ) * 5
Các từ tố của ngôn ngữ KPL • Từ khóa
PROGRAM, CONST, TYPE, VAR, PROCEDURE,
FUNCTION, BEGIN, END, ARRAY, OF, INTEGER,
CHAR, CALL, IF, ELSE, WHILE, DO, FOR, TO • Toán tử
:= (assign), + (addition), - (subtraction), *
(multiplication), / (division), = (comparison of
equality), != (comparison of difference), >
(comparison of greaterness), < (comparison of
lessness), >= (comparison of greaterness or
equality), <= (comparison of lessness or equality) * 6
Các từ tố của ngôn ngữ KPL
• Ký hiệu đặc biệt
; (semicolon), . (period), : (colon), , (comma), ( (left
parenthesis), ) (right parenthesis), ‘ (singlequote) • Ký hiệu kép
(. và .) để đánh dấu chỉ mục của mảng
(* và *) để đánh dấu điểm bắt đầu và kết thúc của chú thích
• Các thành phần khác
Định danh, số, hằng ký tự * 7