Cho văn phạm với các luật sinh sau: E->TE; E’->+T E’; E’->epsilon; T->FT'; T'- >*FT’; T’->epsilon; F->(E); F->id; FOLLOW (E)=?
Trả lời:
Đáp án đúng: A
Để tìm FOLLOW(E), ta áp dụng các quy tắc sau:
1. **Quy tắc 1:** Đặt dấu $ (kết thúc chuỗi) vào FOLLOW(S), trong đó S là ký hiệu bắt đầu.
Trong trường hợp này, E là ký hiệu bắt đầu, vậy $ thuộc FOLLOW(E).
2. **Quy tắc 2:** Nếu có một luật sinh dạng A -> αBβ, thì mọi ký hiệu đầu cuối trong FIRST(β) (ngoại trừ ε) được thêm vào FOLLOW(B).
3. **Quy tắc 3:** Nếu có một luật sinh dạng A -> αB, hoặc một luật sinh dạng A -> αBβ, trong đó FIRST(β) chứa ε (tức là β có thể dẫn đến chuỗi rỗng), thì mọi ký hiệu trong FOLLOW(A) được thêm vào FOLLOW(B).
Áp dụng vào văn phạm đã cho:
* E -> TE'
* Theo quy tắc 3, FOLLOW(E) chứa FOLLOW(E').
* E' -> +T E' | ε
* Vì E' -> ε, theo quy tắc 3, FOLLOW(E') chứa FOLLOW(E).
* Vậy FOLLOW(E) và FOLLOW(E') chứa cùng các phần tử.
* F -> (E)
* Theo quy tắc 2, khi xét luật sinh F -> (E), thì ')' thuộc FOLLOW(E).
Kết hợp các yếu tố trên, FOLLOW(E) = {), $}.
