JavaScript is required

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)=?

A.

{ a,b,c, dollar }

B.

{ b, dollar }

C.

{ c, dollar }

D.

{ dollar }

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.

Câu hỏi liên quan