Cho văn phạm ang cường gồm các luật sinh E’->E; E-> E+T ; E-> T; T- >T*F; T-> F; F- > € ; F-> id. Nếu I là tập bao đóng của văn phạm và I = { E’->E.; E-> E .+T} Goto (I, +) =?

Để tìm Goto(I0, id), ta cần thực hiện các bước sau:

1. Xác định I0: I0 là closure của mục E' -> .E. Trong trường hợp này, I0 bao gồm các mục sau:

- E' -> .E

- E -> .E + T

- E -> .T

- T -> .T * F

- T -> .F

- F -> .(E)

- F -> .id

2. Tính Goto(I0, id): Goto(I0, id) là closure của tập các mục mà từ I0, ta "đi" được bằng cách đọc 'id'. Trong I0, mục duy nhất có thể "đi" bằng 'id' là F -> .id. Sau khi "đi" qua 'id', ta được F -> id.

3. Tính closure của F -> id.: Closure(F -> id.) chỉ bao gồm chính mục đó, vì không có ký hiệu không kết thúc nào sau dấu chấm.

Vậy, Goto(I0, id) = {F -> id.}.

Để tìm FOLLOW(F), ta cần xem xét các luật sinh có F ở vế phải:

1. T -> FT'
2. T' -> *FT'
3. F -> (E)
4. F -> id

Từ luật 1: T -> FT', FOLLOW(F) chứa FIRST(T'). FIRST(T') = {*, epsilon}. Vậy FOLLOW(F) chứa {*}. Nếu T' -> epsilon, thì FOLLOW(F) chứa FOLLOW(T').

Từ luật T'- >*FT’, FOLLOW(F) chứa FIRST(T'). FIRST(T') = {*, epsilon}. Vậy FOLLOW(F) chứa {*}. Nếu T' -> epsilon, thì FOLLOW(F) chứa FOLLOW(T').

Xét FOLLOW(T'):

Từ luật E -> TE', FOLLOW(T) chứa FIRST(E'). FIRST(E') = {+, epsilon}. Vậy FOLLOW(T) chứa {+}. Nếu E' -> epsilon, thì FOLLOW(T) chứa FOLLOW(E').

Từ luật E' -> +TE', FOLLOW(E') chứa FOLLOW(E). FOLLOW(E) = {)}. Vậy FOLLOW(E') chứa {)}.

Vậy FOLLOW(T) chứa {+, )}.

Từ T -> FT', FOLLOW(T') chứa FOLLOW(T). Vậy FOLLOW(T') chứa {+, )}. Do đó FOLLOW(F) cũng chứa {+, )}.

Kết hợp lại, FOLLOW(F) = {*, +, )}. Thêm ký tự kết thúc chuỗi (dollar) thì không đúng vì F không nằm ở cuối chuỗi bắt đầu (start symbol).

Vậy đáp án đúng là {*, +, )}.

Để tìm FOLLOW(E'), ta thực hiện theo các bước sau:

1. Vì E' xuất hiện ở vế phải của luật sinh E -> TE', nên FOLLOW(E') chứa tất cả các phần tử của FOLLOW(E).

2. Để tìm FOLLOW(E), ta xem E xuất hiện ở vế phải của luật sinh nào. Trong trường hợp này, E xuất hiện trong luật sinh F -> (E). Do đó, FOLLOW(E) chứa ")".

3. Vì E là ký hiệu bắt đầu (start symbol), FOLLOW(E) chứa "$" (ký hiệu kết thúc chuỗi).

4. Vậy FOLLOW(E) = {")", "$"}. Do đó, FOLLOW(E') cũng chứa {")", "$"}.

5. Vì E' -> epsilon (E' có thể dẫn đến chuỗi rỗng), nên FOLLOW(E') chứa tất cả các phần tử của FOLLOW(E), tức là {")", "$"}.

Vậy FOLLOW(E') = {")", "$"}.

Bộ phân tích từ vựng (lexical analyzer) hay còn gọi là trình quét (scanner) có nhiệm vụ đọc mã nguồn và chuyển đổi nó thành một chuỗi các từ tố (tokens). Mỗi từ tố đại diện cho một đơn vị cú pháp cơ bản như từ khóa, định danh, toán tử, hằng số, v.v.

• Đáp án A sai vì biểu thức chính quy được dùng để mô tả mẫu của các từ tố, không phải là đầu ra.


• Đáp án B sai vì cây cú pháp là đầu ra của bộ phân tích cú pháp (parser), giai đoạn sau của quá trình biên dịch.


• Đáp án C đúng vì đầu ra của bộ phân tích từ vựng là một chuỗi các từ tố (tokens).


• Đáp án D sai vì chuỗi ký tự là đầu vào, không phải đầu ra của bộ phân tích từ vựng.