Các khái niệm cơ bản về Topdown, bottom up LL và LR
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (549.63 KB, 4 trang )
Câu 1
Cho văn phạm G = {E → EE*|EE+|a|b} ∑ = {a, b ,*,+} ∆= {E}
Chuỗi nào sau đây được sinh ra bởi G
A)
a++b*a
B)
aab++a
C)
a+bb*
D)
ab*bb+
Đáp án B
Câu 2
Cho văn phạm G = {E → EE*|EE+|a|b} ∑ = {a, b ,*,+} ∆= {E}
Chuỗi nào sau đây được sinh ra bởi G
A)
a++b*
B)
ab++a*
C)
ab+ba*
D)
không có xâu nào đúng
Đáp án D
Câu 3
Cho văn phạm G = {E → EE*|EE+|a|b} ∑ = {a, b ,*,+} ∆= {E}
Dãy dẫn xuất của chuỗi abb++a* trong G gồm bao nhiêu bước suy
dẫn (bao nhiêu lần áp dụng luật sinh)
A) 7
B) 8
C) 9
D) 10
Đáp án A
Câu 4
Cho văn phạm G = {E → EE*|EE+|a|b} ∑ = {a, b ,*,+} ∆= {E}
Dạng câu thứ 5 (tính dạng câu đầu tiên là E) trong dãy dẫn xuất trái
nhất của chuỗi abb++a* trong G la:
A)
abE+E*+
B)
aEE*+
C)
aEE+ +E*
D)
abb+E*+
Đáp án C
Câu 5
XXX
Câu 6
Cho văn phạm G = {S → aSb|bSa|SS|a|ε} ∑ = {a, b } ∆= {S}
Chuỗi nào sau đây được sinh ra bởi G:
A)
abbaa
B)
aaba
C)
bbaaaa
D)
Tất cả đều đúng
Đáp án D
Câu 7
Cho văn phạm G = {S → aSb|bSa|SS|a|ε} ∑ = {a, b } ∆= {S}
Chuỗi nào sau đây KHÔNG được sinh ra bởi G:
A)
abbaab
B)
baabab
C)
abbaabb
D)
babbaaa
Đáp án C
Câu 8
Văn phạm nào sau đây KHÔNG thực hiện được phân tích bằng
phương pháp phân tích topdown?
A)
G = { S → aaA|abA; A→bA | a}
B)
G = { S → Aa|b; A→Ab | Sa}
C)
G = { S → Aa|b; A→ aA | a}
D)
G = { S → Aa|b; A→bA | b}
Đáp án B
Câu 9
Văn phạm nào sau đây thực hiện phân tích được bằng phương pháp
phân tích LL(1)?
A)
G = { S → aaA|abA; A→bA | a}
B)
G = { S → Aa|b; A→Ab | Sa}
C)
G = { S → Aa|b; A→ aA | a}
D)
G = { S → Aa|b; A→bA | b}
Đáp án
B
Câu 10
Cho văn phạm G = {Σ, ∆, P, S}, phân tích xâu vào theo phương
pháp phân tích bottom-up, trạng thái thành công là:
A)
ngăn xếp: $S, Đầu vào: $
B)
ngăn xếp: $, Đầu vào: $
C)
ngăn xếp: $S, Đầu vào: S$
D)
ngăn xếp: $S, Đầu vào: a$
Đáp án A
Câu 11
Cho văn phạm G = {Σ, ∆, P, S}, phân tích xâu vào theo phương
pháp phân tích LL(1), trạng thái thành công là:
A)
ngăn xếp: $S, Đầu vào: $
B)
ngăn xếp: $, Đầu vào: $
C)
ngăn xếp: $S, Đầu vào: S$
D)
ngăn xếp: $S, Đầu vào: a$
Đáp án B
Câu 12
Luật sinh A → XYZ có thể tạo thành mấy mục?
A)
1
B)
2
C)
3
D)
4
Đáp án D
Câu 13
Cho văn phạm G ={S → Ab; A → aA|b} Văn phạm gia tố (mở
rộng) của G có bao nhiêu luật sinh?
A)
3
B)
4
C)
5
D)
6
Đáp án B
Câu 14
Cho văn phạm G ={S → AB; A → aA|b; B→ bB|a} Văn phạm gia
tố (mở rộng) của G có bao nhiêu luật sinh?
A)
4
B)
5
C)
6
D)
7
Đáp án C
Câu 15
Văn phạm nào dưới đây KHÔNG phân tích được theo phương
pháp phân tích bottom-up
A)
G = {S→ AB; A → A| aB|a; B→ bA|a}
B)
G = {S→ AB; A → aA| aB|a; B→ bA|a}
C)
G = {S→ AB; A → aA| a; B→ bA|a}
D)
G = {S→ AB; A → Aa| b; B→ bA|a}
Đáp án A
Câu 16
Văn phạm nào dưới đây phân tích được theo phương pháp phân
tích bottom-up
A)
G = {S→ AB; A → A| aB|a; B→ bA|a}
B)
G = {S→ AB; A → aA| aB|ε; B→ bA|a}
C)
G = {S→ AB; A → aA| a; B→ bA|ε}
D)
G = {S→ AB; A → Aa| b; B→ bA|a}
Đáp án D
Câu 17
Văn phạm nào dưới đây KHÔNG phân tích được theo phương
pháp phân tích LR
A)
G = {S→ AB; A → A| aB|a; B→ bA|a}
B)
G = {S→ AB; A → aA| aB|a; B→ bA|a}
C)
G = {S→ AB; A → aA| a; B→ bA|a}
D)
G = {S→ AB; A → Aa| b; B→ bA|a}
Đáp án A
Câu 18
Văn phạm nào dưới đây phân tích được theo phương pháp phân
tích LR(1)
A)
G = {S→ AB; A → A| aB|a; B→ bA|a}
B)
G = {S→ AB; A → aA| aB|ε; B→ bA|a}
C)
G = {S→ AB; A → aA| a; B→ bA|ε}
D)
G = {S→ AB; A → Aa| b; B→ bA|a}
Đáp án D
Câu 19
Văn phạm nào dưới đây phân tích được theo phương pháp phân
tích LR
A)
G = {S→ AB; A → A| aB|a; B→ bA|a}
B)
G = {S→ AB; A → aA| ε; B→ bA|a}
C)
G = {S→ AB; A → aA| a; B→ bA|ε}
D)
G = {S→ AB; A → Aa| b; B→ bA|a}
Đáp án A
