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

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
* 2
Đề 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
* 3
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
* 4
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?”
* 5
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
* 6
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.
* 7
Đọ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)
* 8
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?
* 9
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’
* 10
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”
* 11
Biến trong chương trình
Danh sách liên kết
Mục
Trỏ Đầu
Trỏ Cuối
Từ
Số lần xuất hiên
Dách sách dòng
* 12
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
* 13
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 !?
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
* 2
Scanner
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.
Phân tích
từ vựng
Phân tích
cú pháp
Bảng ký hiệu
Chương
trình nguồn
Token
getToken()
* 3
Scanner
* 4
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)
* 5
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], ., :, ;, ‘, (, )
* 6
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)
* 7
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ự
| 1/198

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