Về mặt trực quan có thể giải thích cho việc làm ở luật sinh 2 như sau: Khi luật sinh A •B Closure(I), điều này có thể dẫn đến trong quá trình phân tích, bộ phân tích có thể gặp xâu con B . Nếu B P thì hy vọng có ...
2. reduce A→ β: thu gọn bằng luật sinh A→ β. 3. accept: Chấp nhận 4. error: Báo lỗi - Hàm goto lấy 2 tham số là một trạng thái và một ký hiệu văn phạm, nó sinh ra một trạng thái. Trong kỹ thuật này về cơ bản chương trình điều khiển ...
Thứ n -1 là γ . Quy luật trên cứ tiếp tục. Nếu ta có một dạng câu phải γ = S thì sự n-1 0 phân tích thành công. Ví dụ 3.21: Cho văn phạm: E → E + E | E * E | ( E ) | id Và xâu vào w = id1 + id2 * id3 , ta có các bước thu gọn xâu vào thành ký ...
- Xét luật sinh E TE: Tính FIRST(TE) = FIRST(T) = {(,id} M[E, id] và M[E,( ] chứa luật sinh E TE - Xét luật sinh E + TE : Tính FIRST(+TE) = FIRST(+) = {+} M[E, +] chứa E +TE - Xét luật sinh E : Vì FIRST(E) và FOLLOW(E) = { ), $ } E ...
Chương trình phân tích hoạt động theo nguyên tắc sau: - Con trỏ ip trỏ vào ký tự a trên xâu vào w. - Xét ký tự X trên đỉnh ngăn xếp, khi đó chương trình hành động như sau: + Nếu X = a = $ chương trình dừng, đưa ra thông báo quá trình phân ...
Trong ví dụ này, rò ràng là nếu đang ở nút của cây phân tích có nhãn và con trỏ đang trỏ vào ký tự „I‟ hoặc „W‟ hoặc „B‟ trên xâu vào thì có thể xác định được ngay cần sử dụng luật sinh nào trong 3 luật sinh trên. 2) Phân ...
1) Ý tưởng Ý tưởng cơ bản của kỹ thuật này là viết lại các A – luật sinh của văn phạm nhằm hoãn lại việc quyết định cho đến khi đủ thông tin cho một lựa chọn đúng với quá trình phân tích. Ví dụ 3.6: Xét văn phạm có các ...
2. Mỗi một lá có nhãn là một ký hiệu kết thúc hoặc ε. 3. Mỗi nút trong có nhãn là một ký hiệu chưa kết thúc. 4. Nếu A là một ký hiệu chưa kết thúc được dùng làm nhãn cho một nút trong nào đó và X 1 , ., X n là nhãn của các con của ...
2.22. Cho các biểu thức chính quy a) 0(0 + 1) * 0 + b) ((0+ 1) * 0(0 + 1)) + c) (1+ 0)00 (0 * + 1 + ) d) (a + ba + aab) * (ε + a) + Hãy xây dựng các NFAε tương đương với mỗi biểu thức trên. 2.23. Cho các biểu thức chính quy sau: a) ( a * + b + ) * b) ((ε + a) b * ) ...
- Xây dựng Automat đoán nhận r 5 =(r 7 ) * 2 a 3 Start 0 1 6 7 4 b 5 Hình 2.24. Automat đoán nhận r 5 = (a+b) * Thực hiện tương tự với r 6 = a; r 3 = r 5 r 6 ; r 4 = b; r 1 = r 3 r 4 ; r 2 = b; r = r 1 r 2 . Thu được kết quả như hình ...
Begin Q‟: = {q 0 }; ‟ := Hình 2.14 là sơ đồ khối của giải thuật xác định Q‟ và ‟. Giả sử ta đánh số các ký hiệu của ‟ là a 1 , a 2 ,., a n T Q‟ chưa đánh dấu s End đ s i n đ B:= (T, a i ) Q‟:= Q‟ {B}; ...
5 {2, 3} b 6 {2, 3} b 7 {2, 3} $ Bảng 2.5. Mô tả quá trình đoán nhận xâu Ta có q = {2, 3} F = {3} . Vậy automat trên đoán nhận được từ w = aaabbbb. 2.4.3. Giải thuật sử dụng NFA Input: NFA M và xâu vào w được kết thúc bởi $. Output: ...
Trang 112, Trang 113, Trang 114, Trang 115, Trang 116, Trang 117, Trang 118, Trang 119, Trang 120, Trang 121,