JavaScript is required

Thuật toán bottom-up được xây dựng dựa trên ý tưởng

A.

Thử sai và quay lui về ký hiệu kết thúc của văn phạm

B.

Tham lam

C.

Sử dụng stack và quy lui

D.

Sử dụng stack và quy hoạch động

Trả lời:

Đáp án đúng: A


Thuật toán bottom-up (từ dưới lên) trong phân tích cú pháp (parsing) bắt đầu từ các ký hiệu kết thúc của văn phạm và cố gắng xây dựng cây cú pháp ngược lên đến ký hiệu bắt đầu. Quá trình này thường sử dụng một stack để lưu trữ các ký hiệu và quy tắc sinh (productions) đã được nhận diện. "Quy lui" ở đây ám chỉ việc giảm (reduce) một chuỗi các ký hiệu trên đỉnh stack thành một ký hiệu không kết thúc (non-terminal) theo một quy tắc sinh trong văn phạm. * **A. Thử sai và quay lui về ký hiệu kết thúc của văn phạm:** Không chính xác, bottom-up không phải là thử sai và quay lui, mặc dù có thể có backtracking trong một số trường hợp. * **B. Tham lam:** Thuật toán tham lam không phải là đặc điểm chính của bottom-up parsing. * **C. Sử dụng stack và quy lui:** Đây là đáp án chính xác. Stack được dùng để lưu trữ các ký hiệu, và "quy lui" (reduction) là bước quan trọng để xây dựng cây cú pháp. * **D. Sử dụng stack và quy hoạch động:** Quy hoạch động không phải là kỹ thuật chính được sử dụng trong bottom-up parsing, mặc dù có một số biến thể có thể sử dụng nó để tối ưu hóa. Vậy đáp án đúng là C

Câu hỏi liên quan