Cho văn phạm S → A hoặc S-> BCD; A → BBA hoặc A->EB; B → bEc hoặc B->BC hoặc B->BDc ; C → c ; D → a hoặc D-> BDb; E → a hoặc E->bE , Follow(E)=?
Trả lời:
Đáp án đúng: A
Để tìm Follow(E), ta cần xem xét các vị trí mà E xuất hiện ở vế phải của các luật sinh và những ký tự có thể theo sau E.
- Từ luật A → EB, ta thấy B theo sau E. Do đó, Follow(E) sẽ chứa First(B).
- First(B) = {b} (vì B → bEc, B ->BC, B->BDc).
- Tiếp theo, xét luật B → bEc. Sau c không có gì, nên cần xem xét Follow(B).
- Từ luật A → BBA, ta có B theo sau B.
- Từ luật S -> BCD, ta thấy CD theo sau B, do đó First(CD) = {c} thuộc Follow(B).
- Từ luật B -> BC, ta có C theo sau B, do đó First(C) = {c} thuộc Follow(B).
- Từ luật B -> BDc, ta có D theo sau B, do đó First(D) = {a} thuộc Follow(B).
- Từ luật B → bEc, ta có c theo sau E, do đó c thuộc Follow(E)
- A là ký tự đầu nên Dollar thuộc Follow(A), Do A -> EB nên Dollar thuộc Follow(E).
Vậy Follow(E) = {b,c,dollar}. Tuy nhiên, không có đáp án nào hoàn toàn khớp. Đáp án gần đúng nhất là A { a,b,c, dollar } nhưng có thêm 'a'. Kiểm tra lại các bước trên, 'a' có thể theo sau E không? Xem xét luật D ->BDb; Ta thấy First(D) = {a} và từ B ->BDc thì c thuộc Follow(D); Vậy không có luật nào cho thấy 'a' thuộc follow(E). Vậy câu này không có đáp án chính xác nhất.