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