Xây dựng
CHƯƠNG TRÌNH DỊCH
Phạm Đăng Hải
[email protected]
2
04/02/14
Chương 2: Phân tích từ vựng
1. Nhiệm vụ của bộ phân tích từ vựng
2. Biểu diễn cấu trúc từ vựng
3. Phân tích từ vựng của ngôn ngữ KPL
3
04/02/14
Mục đích & Nhiệm vụ
•
Mục đích:
–
Tìm chuỗi dài nhất các ký tự đầu vào, bắt đầu từ ký tự
hiện tại tương ứng với một từ tố và trả về từ tố này
•
Nhiệm vụ
–
Duyệt từng ký tự của văn bản nguồn
•
Loại bỏ các ký tự không cần thiết như dấu cách, chú thích,
–
Xây dựng từ vựng từ những ký tự đọc được
–
Nhận dạng từ tố và gửi tới pha tiếp
Nhận biết từ tố gồm
–
Nhận biết các từ khóa, tên do người dùng định nghĩa

“pos”, “start”, “size”, “+”, “10”, “*”,”:=“, “;” là từ vựng
•
“pos”, “start”, “size”, → các từ vựng thuộc lớp từ tố
tên (ident)
•
”:=“→ từ vựng của từ tố gán (assign)
•
“10” → từ vựng của từ tố số nguyên (number)
•
“+” → từ vựng của từ tố cộng (plus)
•
“*” → từ vựng của từ tố nhân (times)
•
“;” → từ vựng của từ tố chấm phẩy (semicolone)
1. Nhiệm vụ của bộ phân tích
pos := start + 10 * size;
6
04/02/14
Từ tố→Chú ý
1. Nhiệm vụ của bộ phân tích
•
Các từ tố Ident, number, plus, assign, do người
viết trình dịch tự định nghĩa để dễ dàng cho việc mã
hóa chương trình. Đây là việc số hóa ký hiệu
•
Một từ tố có thể ứng với tập các từ vựng khác nhau
nên cần thêm một số thông tin khác để biết được
cụ thể đó là từ vựng nào
–
Các chuỗi “19”, “365” đều là chuỗi số, có từ tố “number”,

Chương
trình nguồn
Token
getToken()
8
04/02/14
Mẫu (Pattern)
•
Là luật để mô tả một từ tố nào đó
–
Cơ sở phân biệt & nhận dạng các từ tố khác nhau
•
Chuỗi ký tự cùng thỏa mãn một luật⇒có cùng một từ tố
•
Từ tố là tên riêng của một luật mô tả, từ vựng là một
trường hợp thỏa mãn luật
•
Ví dụ
–
Luật mô tả của từ tố Ident
•
Bắt đầu là một chữ cái
•
Tiếp theo là tổ hợp chữ cái, chữ số
–
Luật mô tả của từ tố assign
•
Bắt đầu bởi ký tự “:”, ngay sau đó là ký tự “=“
•
Dùng văn phạm chính quy để mô tả

Cho Σ ={a,b} một bảng chữ.
–
e
1
= a*+b* ⇒ L(e
1
)= {ε,a,aa,aaa,…,b,bb,bbb}
–
e
2
= a*b* ⇒ L(e
2
)= {ε,a,b,aa,ab,bb,aaa,aab, }
–
e
3
= a(a+b)* ⇒L(e
3
)={a,aa,ab,aaa,aab,aba,abb, }
•
Xâu dạng: bắt đầu là ký hiệu a, tiếp theo là tổ hợp bất
kỳ của các ký hiệu a, b
•
Nếu a là một chữ cái, b là chữ số
⇒
L(e
3
) là ngôn ngữ chứa các tên
⇒
e

–
Có một trạng thái đầu q
0
∈ Q
–
Có một tập trạng thái kết thúc F ⊆Q
•
Một bộ chữ vào Σ
•
Một tập các hàm dịch chuyển δ:(Q x Σ) → Q
Hoạt động
–
Ô-tô-mát xuất phát từ trạng thái đầu, đọc từng ký hiệu
của xâu vào, chuyển trạng thái dựa trên trạng thái hiện
thời và ký hiệu đọc được.
–
Sau khi đọc hết xâu vào mà ô-tô-mát ở trạng thái kết
thúc, xâu được gọi là được đoán nhận bởi ô-tô-mát
2. Biểu diễn cấu trúc từ vựng
14
04/02/14
Ô tô mát hữu hạn→Ví dụ
∀
Σ = {a,b,c}
•
Q = {q
0
, q
1
}

q
0
q
1
Xâu abcaabbc được đoán nhận
15
04/02/14
Ô tô mát hữu hạn→Biểu diễn
2. Biểu diễn cấu trúc từ vựng
Trạng thái
Trạng thái đầu Trạng thái kết thúc
p p
a
δ(p,a) = q
q
1
q
0
a
a
b
b
c
c
Xâu trên bộ chữ {a,b,c} có lẻ ký hiệu a
16
04/02/14
Ô tô mát hữu hạn→Ví dụ
2. Biểu diễn cấu trúc từ vựng
1

q
0
Chữ số
Chữ số
17
04/02/14
Chương 2: Phân tích từ vựng
1. Nhiệm vụ của bộ phân tích từ vựng
2. Biểu diễn cấu trúc từ vựng
3. Phân tích từ vựng của ngôn ngữ KPL
18
04/02/14
Các từ tố của KPL
•
Số nguyên
•
Định danh
•
Từ khóa: begin,end, if,then, while, do, call,
const, var, procedure, program, type, function,
of, integer, char, else, for, to, array
•
Hằng ký tự
•
Dấu phép toán:
–
số học: + - */
–
so sánh: = != < > <=
>=

21
04/02/14
Xây dựng từ vựng
//ch chứa ký tự đọc được từ văn bản nguồn bởi nextChar()
switch(Ch) {
case SPACE : while (Ch==SPACE) nextChar(); return;
case LETTER: nextChar();
while (Ch==LETTER || Ch==DIGIT) nextChar();
return Ident; //Cũng có thể là từ khóa →Phải kiểm tra
case DIGIT: while (Ch==DIGIT) nextChar(); return number;
case ‘+’: nextChar(); return plus;
case ‘>‘ : nextChar();
if(Ch == ‘=‘) { nextChar(); return Geq;}
else return Gtr;
…
}
3. Phân tích từ vựng của ngôn ngữ KPL
22
04/02/14
Nhận dạng từ tố
Xây dựng xong từ vựng, cần nhận dạng từ tố
–
Là tên trạng thái cuối cùng của Ô-tô-mát
–
Nếu Ô-tô-mát kết thúc ở trạng thái ident, cần kiểm
tra đây có phải là từ khóa
•
Dùng kỹ thuật bảng chuyển đổi
3. Phân tích từ vựng của ngôn ngữ KPL
BEGIN