Bài giảng Chương trình dịch - Bài 9: Phân tích văn phạm bằng thuật toán bottom-up - Trương Xuân Nam

CHƯƠNG TRÌNH DỊCH
Bài 9: Phân tích văn phạm bằng thuật 
toán bottom-up
Nội dung
1. Ý tưởng & thuật toán
2. Ví dụ minh họa
3. Cài đặt bottom-up đơn giản
 Cấu trúc một luật văn phạm
 Cấu trúc một suy diễn trực tiếp
 Máy phân tích: các hàm hỗ trợ
 Máy phân tích: các hàm chính
4. Đánh giá về bottom-up
5. Bài tập
TRƯƠNG XUÂN NAM 2
Ý tưởng & thuật toán
Phần 1
TRƯƠNG XUÂN NAM 3
Bottom-up: ý tưởng
 Cho văn phạm G với các luật sinh:
S → E + S | E
E → 1 | 2 | 3 | 4 | 5 | ( S )
 Xâu vào: W = (1 + 2 + (3 + 4)) + 5
 Thu gọn W thành S:
( 1 + 2 + ( 3 + 4 ) ) + 5  ( E + 2 + ( 3 + 4 ) ) + 5 
( E + E + ( 3 + 4 ) ) + 5  ( E + E + ( E + 4 ) ) + 5 
( E + E + ( E + E ) ) + 5  ( E + E + ( E + S ) ) + 5 
( E + E + ( S ) ) + 5  ( E + E + E ) + 5 
( E + E + S ) + 5  ( E + S ) + 5  ( S ) + 5 
E + 5  E + E  E + S  S
TRƯƠNG XUÂN NAM 4
Bottom-up: mục tiêu & ý tưởng
 Mục tiêu: trong số nhiều suy dẫn dạng S * w, 
thuật toán sẽ tìm suy dẫn phải
 Ý tưởng chính:
 Thử sai và quay lui bằng năng lực tính toán của máy tính
 Dò ngược quá trình suy dẫn w  wn-1    w1  S 
bằng kĩ thuật thu-gọn: tìm xem wi có chứa vế phải của 
luật hay không, nếu có thì thay thế phần vế phải đó bằng 
vế trái tương ứng
 Nếu một wi S thì chắc chắn nó cần phải được thu-gọn, 
nếu wi không chứa vế phải của luật nào đó thì nhánh thử 
sai này cần quay lui, ngược lại thì thu-gọn và thử tiếp
TRƯƠNG XUÂN NAM 5
Bottom-up: thuật toán
1. A = w
2. Với chuỗi A đạt được trong quá trình lần ngược:
 Nếu A = “S”:
• Kết luận: quá trình tìm kiếm thành công
• Lưu lại kết quả (chuỗi biến đổi từ đầu để được A)
• Kết thúc ngay lập tức quá trình tìm kiếm
 * Duyệt tất cả các luật sinh dạng x → α, nếu α là một 
chuỗi con trong A thì:
• Áp dụng thu-gọn: thế α trong A bằng x, ta được A’
• Thử bước 2 với chuỗi A = A’
 Nếu không có phương án thu gọn nào thì quay lui
TRƯƠNG XUÂN NAM 6
Ví dụ minh họa
Phần 2
TRƯƠNG XUÂN NAM 7
Bottom-up: ví dụ
Cho tập luật S → AB, A → ab, B → aba
Chỉ ra quá trình thu gọn chuỗi w = ababa
 
 Áp dụng luật A → ab, thu gọn ababa Aaba
 Chuỗi Aaba có 2 phương án thu gọn: Aaba AAa và 
Aaba AB
TRƯƠNG XUÂN NAM 8
Bottom-up: ví dụ
 Áp dụng luật A → ab, thu gọn Aaba AAa
 Đến đây nhánh này ngưng vì không thu gọn tiếp 
được nữa
 Áp dụng luật B → aba, thu gọn Aaba AB
TRƯƠNG XUÂN NAM 9
Bottom-up: ví dụ
 Áp dụng luật S → AB, thu gọn AB  S
 Đến đây điều kiện A = “S” xảy ra:
 Thuật toán dừng, kết luận thu gọn thành công
 Lưu lại quá trình suy dẫn ngược
TRƯƠNG XUÂN NAM 10
Cài đặt bottom-up đơn giản
Phần 3
TRƯƠNG XUÂN NAM 11
Cấu trúc một luật văn phạm
class Rule {
public string left, right;
public Rule(string l, string r) {
left = l;
right = r;
}
public string ToFineString() {
string s = left + " -->";
for (int i = 0; i < right.Length; i++) s += " " + right[i];
return s;
}
}
TRƯƠNG XUÂN NAM 12
Cấu trúc một suy diễn trực tiếp
class Step {
public int ruleNumber, position;
public Step(int r, int p) {
ruleNumber = r;
position = p;
}
}
Giải thích:
 Biến ruleNumber lưu số thứ tự của luật sẽ được dùng
 Biến position lưu vị trí sẽ áp dụng luật đó
TRƯƠNG XUÂN NAM 13
Máy phân tích: các hàm hỗ trợ
class PTBU {
public List rules = new List();
public List steps;
string word = null;
public void AddRule(string left, string right) {
rules.Add(new Rule(left, right));
}
public void PrintAllRules() {
Console.WriteLine("");
foreach (Rule r in rules)
Console.WriteLine(" " + r.ToFineString());
}
TRƯƠNG XUÂN NAM 14
Máy phân tích: các hàm hỗ trợ
public void PrintSteps() {
Console.WriteLine("Doan nhan thanh cong sau...
string w = word;
foreach (Step s in steps) {
string x = DoBackStep(w, s);
...
}
}
string DoBackStep(string w, Step s) {
string w1 = w.Substring(0, s.position);
string w2 = w.Substring(s.position +
rules[s.ruleNumber].right.Length);
return w1 + rules[s.ruleNumber].left + w2;
}
TRƯƠNG XUÂN NAM 15
Máy phân tích: các hàm chính
public bool Process(string x) {
steps = new List();
word = x;
return BottomUp(x);
}
// áp dụng được luật k ở vị trí i của chuỗi w?
bool CanApplyHere(string w, int i, int k) {
string s = w.Substring(i);
if (s.Length > rules[k].right.Length)
s = s.Substring(0, rules[k].right.Length);
return (s == rules[k].right);
}
TRƯƠNG XUÂN NAM 16
Máy phân tích: các hàm chính
public bool BottomUp(string w) {
if ("S" == w) return true;
for (int i = 0; i < w.Length; i++)
for (int k = 0; k < rules.Count; k++)
if (CanApplyHere(w, i, k)) {
Step st = new Step(k, i);
steps.Add(st);
if (BottomUp(DoBackStep(w, st))) return true;
steps.RemoveAt(steps.Count - 1);
}
return false;
}
TRƯƠNG XUÂN NAM 17
Thử nghiệm
class Program {
public static void Main() {
PTBU parser = new PTBU();
parser.AddRule("S", "AB");
parser.AddRule("A", "ab");
parser.AddRule("B", "aba");
parser.PrintAllRules();
if (parser.Process("ababa"))
parser.PrintSteps();
}
}
TRƯƠNG XUÂN NAM 18
Đánh giá về bottom-up
Phần 4
TRƯƠNG XUÂN NAM 19
Đánh giá về bottom-up
 Đặc trưng:
 Dễ hiểu: cài đặt đơn giản
 Chậm: duyệt toàn bộ, không có các bước cắt nhánh
 Không vạn năng: không làm việc với văn phạm có suy 
dẫn rỗng (A → ) hoặc đệ quy (A + A)
 Không dễ loại bỏ những kết quả trùng lặp (trường hợp 
muốn tìm mọi phương án suy dẫn)
 Ý tưởng cải tiến:
 * Quy hoạch động: sử dụng lại những kết quả duyệt cũ
 * Cắt nhánh sớm: dựa trên đặc trưng của một số luật để 
loại bỏ các phương án không có tương lai
TRƯƠNG XUÂN NAM 20
Bài tập
Phần 5
TRƯƠNG XUÂN NAM 21
Bài tập
1. Chỉ ra quá trình thu gọn theo phân tích bottom-up của 
chuỗi raid thuộc văn phạm G sau:
 S→ r X d | r Z d
 X→ o a | e a
 Z→ a i
2. Chỉ ra quá trình thu gọn theo phân tích bottom-up của 
chuỗi (a=(b+a)) thuộc văn phạm G sau:
 S→ B
 B→ R | ( B )
 R→ E = E
 E→ a | b | ( E + E )
TRƯƠNG XUÂN NAM 22
Bài tập
3. Chỉ ra quá trình thu gọn theo phân tích bottom-up cho 
chuỗi (5+7)*3 thuộc văn phạm G sau:
 E→ E + T | T
 T→ T * F | F
 F→ ( E ) | số
4. Chỉ ra quá trình thu gọn theo phân tích bottom-up của 
chuỗi true and not false với tập luật:
 E→ E and T | T
 T→ T or F | F
 F→ not F | ( E ) | true | false
TRƯƠNG XUÂN NAM 23
Bài tập
5. Chỉ ra quá trình thu gọn theo phân tích bottom-up của 
chuỗi abbcbd thuộc văn phạm G có tập luật:
 S→ a A | b A
 A→ c A | b A | d
6. Có thể thực hiện phân tích bottom-up chuỗi aaab thuộc 
văn phạm G dưới đây hay không? Chỉ ra phương án xử 
lý nếu có.
 S→ A B
 A→ a A | 
 B→ b | b B
TRƯƠNG XUÂN NAM 24
Bài tập (lập trình)
1. Hãy chỉnh sửa thuật toán top-down và bottom-up để 
chúng có thể chỉ ra mọi phương án suy dẫn từ kí hiệu 
bắt đầu S thành chuỗi đích w
2. * Mã nguồn minh họa cả hai thuật toán top-down và 
bottom-up đều dựa trên đệ quy, hãy chuyển đổi chúng 
thành dạng không đệ quy (gợi ý: sử dụng một stack 
lưu lại trạng thái của các chuỗi trung gian trong quá 
trình thử-sai các luật sinh)
3. Hãy xây dựng thuật toán chuyển đổi từ suy dẫn trả về 
bởi thuật toán top-down (bottom-up) thành cây phân 
tích cú pháp tương ứng
TRƯƠNG XUÂN NAM 25
Bài tập (lập trình)
4. * Hãy điều chỉnh thuât toán top-down (bottom-up) để 
chúng trả về mọi cây phân tích cú pháp khác nhau 
(dùng cho văn phạm có nhập nhằng)
5. Nếu văn phạm G đệ quy phải, thì thuật toán top-down 
hay bottom-up sẽ trả về kết quả nhanh hơn trong các 
tính huống:
 Chuỗi w không thuộc văn phạm G
 Chuỗi w có nhiều cây phân tích cú pháp
TRƯƠNG XUÂN NAM 26