Xem mẫu
- IT4073:NGÔN NGỮ và
PHƢƠNG PHÁP DỊCH
Phạm Đăng Hải
haipd@soict.hut.edu.vn
- Chƣơng 3: Phân tích cú pháp
1. Bài toán phân tích cú pháp
2. Phƣơng pháp phân tích cú pháp quay lui
3. Phƣơng pháp phân tích bảng
4. Phƣơng pháp phân tích cú pháp tất định
5. Phân tích cú pháp cho PL/0
10/24/2012 2
- 1. Bài toán phân tích cú pháp
Bài toán đặt ra
Cho
– Văn phạm phi ngữ cảnh G
G = (VT, VN, P, S) Trong chƣơng trình dịch,
xâu là chuỗi các token
– Xâu V*T thu đƣợc từ giai đoạn
Hỏi Program Vidu; trƣớc – phân tích từ vựng
Begin PROGRAM IDENT
– L(G)? SEMICOLON BEGIN IDENT
X := 10 ASSIGN NUMBER END
Nếu L(G) End. PERIOD
– Chỉ ra các sản xuất đã sử dụng để sinh ra
– Cấu trúc nên cây suy dẫn
10/24/2012 3
- 1. Bài toán phân tích cú pháp
Phƣơng pháp phân tích
• Kiểm tra xâu phân tích từ trái qua phải
– Kiểm tra ký hiệu trái nhất của xâu cần phân tích
– Tới ký hiệu tiếp,.. Cho tới ký hiệu cuối cùng
• Phƣơng pháp xây dựng cây phân tích
– Trên xuống (Top-down): S * ?
– Dƣới lên (Bottom-up): * S?
• Phƣơng pháp lựa chọn sản xuất (Aα1|…|αn)
– Quay lui (backtracking)
• Thử lần lƣợt các sản xuất
– Tất định (deterministic)
10/24/2012
• Xác định đƣợc duy nhất một sản xuất thích hợp 4
- 1. Bài toán phân tích cú pháp
Phân tích trái
• Phân tích trái của xâu a là dãy các sản xuất
đƣợc sử dụng trong suy dẫn trái từ S ra a
• Các sản xuất được đánh số thứ tự 1,..p
– Phân tích là danh sách các số từ 1 đến p
• Ví dụ cho văn phạm
1. E T+E Xét xâu a*(a+a)
2. E T E 2 T 3 F*T 6 a*T
3. T F* T 4 a*F 5a*(E)
4. T F 1 a*(T+E) 4 a*(F+E)
5. F (E) 6 a*(a+E) 2 a*(a+T)
6. F a 4 a*(a+F) 6 a*(a+a)
10/24/2012
Phân tích trái của xâu a*(a+a) là 23645146246 5
- Chƣơng 3: Phân tích cú pháp
1. Bài toán phân tích cú pháp
2. Phƣơng pháp phân tích cú pháp quay lui
3. Phƣơng pháp phân tích bảng
4. Phƣơng pháp phân tích cú pháp tất định
5. Phân tích cú pháp cho PL/0
10/24/2012 6
- 2. Phương pháp phân tích quay lui
Giới thiệu
• Tƣ tƣởng chủ yếu của giải thuật
– Xây dựng cây phân tích cú pháp (cây suy dẫn)
cho xâu
• Thuật toán Top-down
– Đi từ nút gốc tới nút lá
• Thuật toán Bottom –up
– Quá trình phân tích gạt thu gọn
10/24/2012 7
- 2. Phương pháp phân tích quay lui
Phân tích Top-down
Cho VPPNC G = (VT, VN, P, S)
sản xuất Aα1|…|αn đƣợc đánh số 1, 2,..
Xây dựng cây phân tích cho xâu :
1. Khởi tạo
- Xây dựng cây chỉ có một nút gốc S
- S (Start symbol): Ký hiệu khởi đầu
- Gọi ký hiệu cần phân tích là ký hiệu đầu tiên
của xâu
- Gọi S là nút hoạt động,
10/24/2012 8
- 2. Phương pháp phân tích quay lui
Phân tích Top-down
2. Tạo các nút con của cây (một cách đệ quy)
Nút hoạt động là ký hiệu không kết thúc A
– Chọn sản xuất đầu tiên của A chƣa đƣợc áp
dụng: A X1X2. . . .Xk (k 0)
– Tạo k con trực tiếp của A với nhãn X1, X2, ...Xk
– Nếu k > 0, Lấy X1 làm nút hoạt động
– Nếu k = 0, (sản xuất A e), lấy nút bên phải
(ngay sau) A là nút hoạt động
Tiếp tục thực hiện bước 2
10/24/2012 9
- 2. Phương pháp phân tích quay lui
Phân tích Top-down
2. Tạo các nút con của cây (một cách đệ quy)
Nút hoạt động là ký hiệu kết thúc a
- So sánh a với ký hiệu cần phân tích hiện tại
– Nếu trùng nhau
• Nút hoạt động là nút bên phải của a
• Ký hiệu cần phân tích là ký hiệu tiếp theo trên
xâu vào
– Nếu không trùng nhau
• Quay lại bƣớc đã sử dụng một sản xuất và
thử sản xuất tiếp.
– Nếu đã hết khả năng, quay lại bƣớc trƣớc
10/24/2012 10
- 2. Phương pháp phân tích quay lui
Phân tích Top-down
3. Điều kiện dừng
- Đã áp dụng hết khả năng mà không tạo
đƣợc cây Xâu không được đoán nhận
- Tạo ra cây suy dẫn cho xâu vào
10/24/2012 11
- 2. Phương pháp phân tích quay lui
Phân tích Top-down
Điều kiện áp dụng thuật toán
- Văn phạm không đệ quy trái
Chi phí (n = l(); C, K > 1 là các hằng số)
- Bộ nhớ C*n
- Thời gian Kn
10/24/2012 12
- 2. Phương pháp phân tích quay lui
Phân tích Top-down Ví dụ
Văn phạm S aSbS|aS|c, xâu = aacbc
Đánh số sản xuất a a c b c End
1. S aSbS
2. S aS S
3. S c
a S b S
Đánh số sản xuất
1. S c a S c
2. S aS
c
3. S aSbS
10/24/2012 13
- 2. Phương pháp phân tích quay lui
Phân tích Top-down Bài tập
Cho văn phạm
E T+E |T
T F*T |F
F (E) |a
Xây dựng cây suy dẫn cho xâu a+a
10/24/2012 14
- 2. Phương pháp phân tích quay lui
Giải thuật phân tích Top-down quay lui (1/8)
Vào
– Văn phạm phi ngữ cảnh không đệ quy trái
– xâu cần phân tích = a1...an, n 0
– Các sản xuất của G đƣợc đánh số 1,...,q
Ra
– Một phân tích trái cho (nếu có)
– Thông báo lỗi nếu ngƣợc lại
Quy ước
A VN , giả sử A a1 | a2 | . . . .| an
Coi các sản xuất trên là
A1 a1
....
10/24/2012 An an 15
- 2. Phương pháp phân tích quay lui
Giải thuật phân tích Top-down quay lui (2/8)
Phương pháp: Dùng 2 stack D1 và D2
– D1 ghi lại những lựa chọn đã sử dụng và những ký
hiệu vào đã được phân tích
• Đầu đọc đã đổi vị trí
– D2 biểu diễn dạng câu trái hiện tại có được bằng
cách thay thế các ký hiệu không kết thúc bởi vế
phải tương ứng.
• Đỉnh của D2 là nút hoạt động của cây tạo ra
10/24/2012 16
- 2. Phương pháp phân tích quay lui
Giải thuật phân tích Top-down quay lui (3/8)
Hình trạng của giải thuật
Bộ bốn (s, i, a, b)
s Q: Trạng thái hiện thời
– q: Trạng thái bình thƣờng
– b: Quay lui
– t: Kết thúc
i : Vị trí đầu đọc (# kết thúc xâu băng vào)
a: Nội dung stack thứ nhất, đỉnh ở bên phải
b: Nội dung stack thứ hai, đỉnh ở bên trái
Hình trạng ban đầu (q, 1, ε, S#)
10/24/2012 17
- 2. Phương pháp phân tích quay lui
Giải thuật phân tích Top-down quay lui (4/8)
Thực hiện giải thuật
– Bắt đầu từ hình trạng đầu, tính liên tiếp các
hình trạng tiếp theo cho đến khi không tính
đƣợc nữa.
– Ký hiệu | chỉ một thay đổi hình trạng
(q, i, a, b ) | (q‟, i‟, a‟, b‟)
– Giải thuật thực hiện theo các dịch chuyển
10/24/2012 18
- 2. Phương pháp phân tích quay lui
Giải thuật phân tích Top-down quay lui (5/8)
Mở rộng cây
(q, i, a, Ab ) | (q, i, aA, g1b)
AV và A g1là lựa chọn đầu tiên của A
Phù hợp ký hiệu vào
(q, i, a, ab ) | (q, i+1, aa, b)
Ký hiệu đỉnh D2 phù hợp ký hiệu vào
Chuyển sang D1 và dịch chuyển đầu đọc
Không phù hợp ký hiệu vào
(q, i, a, ab ) | (b, i, aa, b) //chuyển trạng thái
10/24/2012 19
- 2. Phương pháp phân tích quay lui
Giải thuật phân tích Top-down quay lui (6/8)
Quay lui trên xâu vào
(b, i, aa, b ) | (b, i-1, a, ab) aVT
Chuyển ký hiệu trên đỉnh D1 sang D2 và dịch đầu
đọc sang trái
Thử lựa chọn tiếp theo
(b, i, aAj, gjb ) |
• (q, i, aAj+1, gj+1b ) //gj+1 là lựa chọn tiếp của A
• Nếu là sản xuất cuối của A, quay lui tiếp
– Thay gj bởi A và loại bỏ Aj trên đỉnh của D1
– Nếu hết khả năng quay lui (i=1, A S): Không đoán nhận
10/24/2012 20
nguon tai.lieu . vn