TAILIEUCHUNG - Tài liệu trình biên dịch C (ĐH Cần Thơ) part 9

PHÂN TÍCH CÚ PHÁP TỪ TRÊN XUỐNG Trong mục này, chúng ta giới thiệu các ý niệm cơ bản về phương pháp phân tích cú pháp từ trên xuống (Top Down Parsing) và trình bày một dạng không quay lui hiệu quả của phương pháp phân tích từ trên xuống, gọi là phương pháp phân tích dự đoán (predictive parser). Chúng ta định nghĩa một lớp văn phạm LL(1) (viết tắt của Left-to-right parse, Leftmost-derivation, 1-symbol lockahead ), trong đó phân tích dự đoán có thể xây dựng một cách tự động. 1. Phân tích cú pháp đệ qui. | III. PHÂN TÍCH CÚ PHÁP TỪ TRÊN XUỐNG Trong mục này chúng ta giới thiệu các ý niệm cơ bản về phương pháp phân tích cú pháp từ trên xuống Top Down Parsing và trình bày một dạng không quay lui hiệu quả của phương pháp phân tích từ trên xuống gọi là phương pháp phân tích dự đoán predictive parser . Chúng ta định nghĩa một lớp văn phạm LL 1 viết tắt của Left-to-right parse Leftmost-derivation 1-symbol lockahead trong đó phân tích dự đoán có thể xây dựng một cách tự động. 1. Phân tích cú pháp đệ qui lùi Recursive Descent Parsing Phân tích cú pháp từ trên xuống có thể được xem như một nỗ lực tìm kiếm một dẫn xuất trái nhất cho chuỗi nhập. Nó cũng có thể xem như một nỗ lực xây dựng cây phân tích cú pháp bắt đầu từ nút gốc và phát sinh dần xuống lá. Một dạng tổng quát của kỹ thuật phân tích từ trên xuống gọi là phân tích cú pháp đệ quy lùi có thể quay lui để 72 quét lại chuỗi nhập. Tuy nhiên dạng này thường rất ít gặp. Lý do là với các kết cấu ngôn ngữ lập trình chúng ta hiếm khi dùng đến nó. 2. Bộ phân tích cú pháp dự đoán Predictive Parser Trong nhiều trường hợp bằng cách viết văn phạm một cách cẩn thận loại bỏ đệ qui trái ra khỏi văn phạm rồi tạo ra yếu tố trái chúng ta có thể thu được một văn phạm mà một bộ phân tích cú pháp đệ quy lùi phân tích được nhưng không cần quay lui gọi là phân tích cú pháp dự đoán. Xây dựng sơ đồ dịch cho bộ phân tích dự đoán Để xây dựng sơ đồ dịch cho phương pháp phân tích xuống trước hết loại bỏ đệ qui trái tạo yếu tố trái cho văn phạm. Sau đó thực hiện các bước sau cho mỗi ký hiệu chưa kết thúc A 1. Tạo một trạng thái khởi đầu và một trạng thái kết thúc. 2. Với mỗi luật sinh A X1X2 . Xn tạo một đường đi từ trạng thái khởi đầu đến trạng thái kết thúc bằng các cạnh có nhãn X1X2 . Xn Một cách cụ thể sơ đồ dịch được vẽ theo các nguyên tắc sau 1. Mỗi ký hiệu chưa kết thúc tương ứng với một sơ đồ dịch trong đó nhãn cho các cạnh là token hoặc ký hiệu chưa kết thúc. 2. Mỗi token tương ứng với việc đoán nhận token đó và đọc token kế tiếp x x 3. Mỗi

• Kỹ thuật lập trình
• trình biên dịch c
• thủ thuật lập trình
• lập trình c
• tài liệu trình biên dịch
• biên dịch c