Chương trình dịch

Môc Lôc Lời Nói Đầu 7 Chương 1. Tổng Quan Về Chương Trình Dịch 9 1.1. Mở Đầu 9 1.2. Chương Trình Dịch 11 1.2.1. Các Khái Niệm 11 1.2.2. Mô Hình Phân Tích - Tổng Hợp Của Một Chương Trình Dịch 12 1.2.3. Môi Trường Của Chương Trình Dịch 13 ...

Mục tiêu: Chương 1 TỔNG QUAN VỀ CHƯƠNG TRÌNH DỊCH Giúp sinh viên có khả năng: - Hiểu được các khái niệm cơ bản: Chương trình dịch, hệ thống thông dịch, biên dịch. - Hiểu được môi trường của một chương trình dịch. - Hiểu được ...

Cấu trúc phân cấp của một chương trình thường được diễn tả bởi quy luật đệ quy. Ví dụ 1.4: 1. Định danh (tên hay danh biểu - identifier) là một biểu thức (expr). 2. Số (number) là một biểu thức. 3. Nếu expr1 và expr2 là các biểu thức ...

Mục tiêu: Chương 2 PHÂN TÍCH TỪ VỰNG Giúp sinh viên có khả năng: - Củng cố được một số kiến thức về văn phạm, ngôn ngữ và automat. - Hiểu được các khái niệm: thẻ từ, mẫu từ vựng, trị từ vựng. Biểu diễn và nhận biết ...

Cho Automat được biểu diễn bằng đồ thị hình 2.1. Tính: ε - CLOSURE(0). ε - CLOSURE(0) = {0, 1, 6, 2, 4, 7, 8} 2 a 3  Start 0  1   6  7  8 a 9 b 10 4 b  5   Suy ra: Hình 2.1. NFA với ε - dịch chuyển b) Hàm chuyển trạng thái mở rộng 1. ...

Biểu thức chính quy Token Trị thuộc tính ws - - if if - then then - else else - id id con trỏ trong bảng ký hiệu num num giá trị số relop LT (Less Than) relop LE (Less Or Equal) = relop EQ (Equal) relop NE (Not Equal) > relop GT (Greater Than) >= relop GE (Greater Or Equal) ...

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: ...

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};  ...

- 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 ...

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 * ) ...

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 ...

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 ...

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 ...

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 ...

- 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   ...

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ý ...

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 ...

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ó ...

Ðây là một văn phạm không nhập nhằng nhưng không phải là văn phạm SLR(1). Họ tập hợp các mục C bao gồm: I 0 : S → • S ; S → • L = R ; S → • R ; L → • * R ; L → • id ; R → • L I 1 : S → S • I 2 : S → L • = R ; R → L • ; I 3 : S → ...

Hãy sử dụng giải thuật phân tích cú pháp đẩy – thu để phân tích mỗi xâu vào w; sau đó xây dựng cây phân tích cú pháp của nó nếu có: 1) w = id - (id + id). 2) w = (id + id) / id. 3) w = (id + id)- (id. 4) w = id + * (id - id) / id. 5) w = (id + id) / (id + ...

5) Operator  +  -  *  /  6) delim  blank | tab | newline ; + ws  delim . 7) letter  A | B | .| Z | a | b |.| z ; digit  0 | 1 | .| 9 ; * id  (letter| _ ) (letter | digit | _ ) . b) Xây dựng sơ đồ chuyển để nhận biết mỗi tthẻ từ. Start ...

Ta có q  F = {6}  {6} = {6}   . Vậy automat đoán nhận được từ w = baaaabb$. + w = aabbbab$ Sử dụng giải thuật automat không đơn định đoán nhận w bằng bảng sau: Bước q =  (q, c) c khởi tạo 0 a 1 {3} a 2 {4} b 3 {3, 4, 5} b 4 {3, 4, 5, 6} b 5 ...

4 {2} a 5 {2} a 6 {2} $ Bảng BT 2.18b1 Ta có q  F = {2}  {2, 4} = {2}   . Vậy automat đoán nhận được từ w = bbbaaa$ 2) w = bbaaab$ Bước q =  -closure(  (q,c)) c khởi tạo {0, 1, 3} b 1 {1, 2, 3, 4} b 2 {1, 2, 3, 4} a 3 {2} a 4 {2} a 5 {2} b 6  $ Bảng BT ...

- r = (r ) + ; r = 0. 2 8 8 + Xây dựng r Start 0 0 1 - r = 0 3 Start 2 0 3 - r = 0 6 Start 4 1 5 - r = 1 7 - r = 0 Start 6 0 7 8 - r = r + r 5 6 7 0 ε 2 3 ε Start 8 9 ε 4 1 5 ε - r = (r ) * 4 5 ε 0 ε 2 3 Start 10  ε 8 9  11 ε 4 1 5 ε ε - r = r r 1 3 4 ε 0 Start 0 0 1  ε 2 3 ...

Q 22 và cung đi ra có nhãn là A đang nối với nút có nhãn là q 23 , không trùng với ký tự X nên quá trình duyệt chuyển sang cung đi ra khỏi q 22 tiếp theo mang nhãn là B, không trùng với ký tự X nên quá trình duyệt chuyển sang cung đi ra khỏi q 22 ...

A) w = abba b) w = aaaba S S a S 2 a S 2 B S 1 b B 1 A a S 1 S 1 a A S 1  b  a A 1 A a S 1  b  c) d) Hình BT 3.36. Cây phân tích cú pháp của các xâu được xây dựng từ trên xuống theo phương pháp đệ quy xuống 3.37. Lời giải tóm tắt a) Khử đệ quy ...

12 $ E T‟) E‟T‟ + id)$ 13 $ E T‟) E‟ + id)$ T‟   14 $ E T‟) E‟T+ + id)$ E‟  +TE‟ 15 $ E T‟) E‟T id)$ 16 $ E T‟) E‟T‟F id)$ T  FT‟ 17 $ E T‟) E‟T‟id id)$ F  id 18 $ E T‟) E‟T‟ )$ 19 $ E T‟) E‟ )$ T‟   20 $ E T‟) )$ E‟   ...

- Quá trình phân tích gặp lỗi vì Stack không chỉ chứa duy nhất ký tự bắt đầu E nên không có cây phân tích cú pháp. 3) w = id + * id + id - Quá trình phân tích cú pháp đẩy - thu xâu được trình bày trong bảng sau: Bước Ngăn xếp Xâu vào Hành ...