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

 CHƯƠNG TRÌNH DỊCH
Bài 8: Phân tích văn phạm bằng thuật 
 toán top-down
Nội dung
1. Ý tưởng & thuật toán
2. Ví dụ minh họa
3. Cài đặt top-down đơ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
 . Thử nghiệm
4. Đánh giá về top-down
5. Bài tập
 TRƯƠNG XUÂN NAM 2
Phần 1
Ý tưởng & thuật toán
 TRƯƠNG XUÂN NAM 3
Top-down: ý 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
. Tìm suy dẫn từ S thành W.
 S E + S ( S ) + S ( E + S ) + S ( 1 + S ) + S
 ( 1 + E + S ) + S ( 1 + 2 + S ) + S
 ( 1 + 2 + E ) + S ( 1 + 2 + ( S ) ) + S
 ( 1 + 2 + ( E + S ) ) + S ( 1 + 2 + ( 3 + S ) ) + S
 ( 1 + 2 + ( 3 + E ) ) + S ( 1 + 2 + ( 3 + 4 ) ) + S
 ( 1 + 2 + ( 3 + 4 ) ) + E ( 1 + 2 + ( 3 + 4 ) ) + 5
 TRƯƠNG XUÂN NAM 4
Top-down: ý tưởng
. Xét quá trình suy dẫn S W1 W2  W
. Wi luôn chứa ít nhất một non-terminal
. Xét X là non-terminal trái nhất của Wi:
 . W không chứa non-terminal nên X sẽ phải “biến mất”
 . Cách làm “biến mất” X chỉ có thể do sử dụng luật văn 
 phạm mà vế trái là X
. Nhận xét: trước sau gì X cũng sẽ “biến mất” bởi 
 một luật văn phạm có dạng X → α
 . Top-down sử dụng năng lực tính toán của máy tính để 
 tìm ra luật đó bằng phương pháp thử-sai-quay-lui
 TRƯƠNG XUÂN NAM 5
Top-down: ý tưởng
. Dò tìm quá trình suy dẫn S W1  W:
 . Với Wi, tìm non-terminal X
 . Tìm mọi luật X → α, áp dụng luật đó biến đổi Wi thành 
 Wi+1
 . Dừng nếu Wi+1 = W (tìm được phương án suy dẫn)
 . Thử tiếp với Wi+1 hoặc quay lui nếu không phù hợp
. Đặc điểm của Top-down:
 . Nếu Wi có chứa nhiều non-terminal thì chỉ cần thử với 
 non-terminal trái nhất
 . Trong số nhiều suy dẫn dạng S * W, thuật toán sẽ tìm 
 suy dẫn trái
 TRƯƠNG XUÂN NAM 6
Top-down: thuật toán
1. A = S
2. Với một chuỗi A đạt được trong quá trình suy dẫn:
 . Nếu A = W:
 • Kết luận: quá trình tìm kiếm thành công
 • Lưu lại quá trình biến đổi từ đầu để được A
 • Kết thúc ngay lập tức quá trình tìm kiếm
 . Nếu A ≠ W: tìm kí hiệu trung gian trái nhất X
 . Không tìm được X thì dừng, trở lại hàm gọi
 . Duyệt tất cả các luật sinh dạng X → α
 • Áp dụng luật đó trên A (ở vị trí X), ta được A’
 • Thử bước 2 với chuỗi A = A’
 TRƯƠNG XUÂN NAM 7
Phần 2
Ví dụ minh họa
 TRƯƠNG XUÂN NAM 8
Top-down: ví dụ
Phân tích W = aacbc với tập luật S → aSbS | aS | c
1. Xét A = aSbS
2. Tìm được kí hiệu S thứ 2 trong A là non-terminal
3. Thử áp dụng luật S → aSbS được A’ = aaSbSbS
 TRƯƠNG XUÂN NAM 9
Top-down: ví dụ
1. Xét A = aaSbSbS
2. Tìm được kí hiệu S thứ 3 trong A là non-terminal
 1. Thử áp dụng luật S → aSbS được A’ = aaaSbSbSbS
 2. Thử áp dụng luật S → aS được A’ = aaaSbSbS
 3. Thử áp dụng luật S → c được A’ = aacbSbS
 TRƯƠNG XUÂN NAM 10
Top-down: ví dụ
. Quá trình thử sai kết luận rằng A = aSbS không thể 
 áp dụng luật S → aSbS
. Quay lui về đến tình huống ban đầu ở hình (a)
. Thử phương án tiếp theo S → aS, được A’ = aaSbS
 TRƯƠNG XUÂN NAM 11
Top-down: ví dụ
. Quá trình thử sai tiếp tục và cuối cùng dừng ở 
 phương án được thể hiện ở hình (g)
. Khi nhận được chuỗi A = W = aacbc, ngay lập tức 
 thuật toán dừng và trả về quá trình áp dụng luật
 TRƯƠNG XUÂN NAM 12
Phần 3
Cài đặt top-down đơn giản
 TRƯƠNG XUÂN NAM 13
Cấu trúc một luật văn phạm
// Lớp chứa luật văn phạm, dạng left -> right
class Rule {
 public string left, right;
 public Rule(string l, string r) {
 left = l; right = r;
 }
 // chuyển đổi luật về dạng string (để in cho dễ nhìn)
 public string ToFineString() {
 string s = left + " -->";
 for (int i = 0; i < right.Length; i++)
 s += " " + right[i];
 return s;
 }
}
 TRƯƠNG XUÂN NAM 14
Cấu trúc một suy diễn trực tiếp
// Lớp chứa một bước áp dụng luật suy diễn
// + ruleNumber: số thứ tự của luật sẽ được dùng
// + position: vị trí sẽ áp dụng luật đó
class Step {
 public int ruleNumber, position;
 public Step(int r, int p) {
 ruleNumber = r;
 position = p;
 }
}
 TRƯƠNG XUÂN NAM 15
Máy phân tích: các hàm hỗ trợ
class PTTD {
 public List rules = new List(); // bộ luật
 public List steps; // các bước suy diễn
 string w = null; // chuỗi W đích
 // thêm luật left --> right vào tập luật
 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 16
Máy phân tích: các hàm hỗ trợ
 public void PrintSteps() {
 Console.WriteLine("Doan nhan thanh cong sau...
 string w = "S";
 foreach (Step s in steps) {
 string w0 = DoStep(w, s);
 Console.WriteLine(" {0} => {1} (vi tri...
 w = w0;
 }
 }
 string DoStep(string w, Step s) {
 string w1 = w.Substring(0, s.position);
 string w2 = w.Substring(s.position + 1);
 return w1 + rules[s.ruleNumber].right + w2;
 }
 TRƯƠNG XUÂN NAM 17
Máy phân tích: các hàm chính
 public bool Process(string x) {
 steps = new List();
 w = x;
 return Try("S");
 }
 // tìm vị trí non-terminal trái nhất trong s
 // trả về -1 nếu không tìm được
 public int FindNonterminal(string s) {
 for (int i = 0; i < s.Length; i++) {
 if (i >= w.Length) return i;
 if (s[i] != w[i]) return i;
 }
 return -1;
 }
 TRƯƠNG XUÂN NAM 18
Máy phân tích: các hàm chính
 // hàm thử-sai-quay-lui với chuỗi s
 public bool Try(string s) {
 if (s == w) return true;
 int n = FindNonterminal(s);
 if (n != -1)
 for (int i = 0; i < rules.Count; i++)
 if (rules[i].left[0] == s[n]) {
 Step st = new Step(i, n);
 steps.Add(st);
 if (Try(DoStep(s, st))) return true;
 steps.RemoveAt(steps.Count - 1);
 }
 return false;
 }
 TRƯƠNG XUÂN NAM 19
Thử nghiệm
class Program {
 public static void Main() {
 PTTD parser = new PTTD();
 // nạp thử bộ luật
 parser.AddRule("S", "B");
 parser.AddRule("B", "R");
 parser.AddRule("B", "(B)");
 parser.AddRule("R", "E=E");
 ...
 parser.PrintAllRules();
 if (parser.Process("(a=(b+a))"))
 parser.PrintSteps();
 }
}
 TRƯƠNG XUÂN NAM 20
Phần 4
Đánh giá về top-down
 TRƯƠNG XUÂN NAM 21
Đánh giá về top-down
. Thuật toán đơn giản, sử dụng sức mạnh của máy 
 tính để tìm kiếm lời giải
. Thuật toán dạng thử-sai-quay-lui, không cắt nhánh, 
 độ phức tạp tính toán là hàm mũ (~ chậm)
. Thuật toán không vạn năng, không làm việc được 
 với các văn phạm có đệ quy trái
 . Lý do: vì không có cắt nhánh phù hợp, dẫn đến việc đi 
 mãi theo chiều sâu mà không quay lui
Câu hỏi: có thể sửa đổi thuật toán như thế nào để làm 
việc được với văn phạm có đệ quy trái?
 TRƯƠNG XUÂN NAM 22
Cải tiến top-down thế nào?
. Tăng tính vạn năng của thuật toán:
 . Xử lý tình huống đệ quy trái bằng ràng buộc phù hợp
 . Biến đổi văn phạm trước khi bắt đầu thử-sai-quay-lui
. Tăng tốc độ tính toán:
 . Tập trung vào việc cài đặt cắt nhánh (nhiều ý tưởng)
 • Cắt nhánh khi trong A có terminal không có trong w
 • Cắt nhánh khi số terminal trong A nhiều hơn trong w
 . Tính trước các bước không có “cơ hội về đích” để loại 
 bỏ bớt những tình huống thử-sai không cần thiết
 . Sử dụng lại những kết quả đã duyệt cũ
 TRƯƠNG XUÂN NAM 23
Phần 5
Bài tập
 TRƯƠNG XUÂN NAM 24
Bài tập
1. Chỉ ra quá trình thực hiện phân tích top-down của 
 chuỗi raid thuộc văn phạm G có tập luật:
 . S → r X d | r Z d
 . X → o a | e a
 . Z → a i
2. Chỉ ra quá trình thực hiện phân tích top-down của 
 chuỗi (a=(b+a)) thuộc văn phạm G có tập luật:
 . S → B
 . B → R | ( B )
 . R → E = E
 . E → a | b | ( E + E )
 TRƯƠNG XUÂN NAM 25
Bài tập
3. Có thể áp dụng thuật toán phân tích top-down cho 
 chuỗi (5+7)*3 thuộc văn phạm G dưới đây hay không? 
 Chỉ ra quá trình thực hiện nếu có thể
 . E → E + T | T
 . T → T * F | F
 . F → ( E ) | số
4. Tương tự câu trên, chỉ ra quá trình phân tích top-down 
 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 26
Bài tập
5. Chỉ ra quá trình thực hiện phân tích top-down 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. Chỉ ra quá trình thực hiện phân tích top-down của 
 chuỗi aaab thuộc văn phạm G có tập luật:
 . S → A B
 . A → a A | 
 . B → b | b B
 TRƯƠNG XUÂN NAM 27