HomeĐề thi môn Chương Trình Dịch
Thứ Năm, 17 tháng 7, 2014
Môn học chương trình dịch là môn học của ngành khoa học máy tính. Trong suốt thập niên 50, trình biên dịch được xem là cực kỳ khó viết. Ngày nay, việc viết một chương trình dịch trở nên đơn giản hơn cùng với sự hỗ trợ của các công cụ khác. Cùng với sự phát triển của các chuyên ngành lý thuyết ngôn ngữ hình thức và automat, lý thuyết thiết kế một trình biên dịch ngày một hoàn thiện hơn.
ĐỀ
THI
MÔN:
CHƯƠNG TRÌNH DỊCH
THỜI GIAN: 90
PHÚT
A.PHẦN
TRẮC NGHIỆM (khoanh tròn vào
phương án đúng) –
2 điểm
1.Bộ phân
tích từ vựng đưa ra
a.
Chương trình nguồn
b.Các
từ vựng
c.Các từ tố
d.Các
qui tắc ngữ pháp 2.Trong kiến trúc kỳ trước, kỳ sau kỳ sau gồm:
a.Tối ưu mã trung gian
b.Sinh mã trung gian, tối ưu mã trung gian,
sinh mã đích
c.Tối ưu mã trung gian,
sinh mã đích
d.Sinh mã đích
3.Xây dựng
bộ phân tích từ vựng trước hết
a.Phải xác định
trong ngôn ngữ lập trình có các từ tố nào.
b.Phải xác định trong ngôn ngữ lập trình có
các qui tắc ngữ pháp nào.
c.Phải xác định trong ngôn ngữ lập trình có
các phép toán nào.
d.Phải xác định trong ngôn ngữ lập trình có
các từ khoá nào.
4.Trong
biểu đồ chuyển chỉ được phép có trạng thái kết thúc:
a.Đúng
b.Sai
c.Tuỳ trong trường hợp
d.Chỉ đúng khi trạng thái kết thúc có dấu *.
5.Thuật
toán phân tích top – down quay lui đưa ra
a.Một phân tích trái đối với xâu vào.
b.Một phân tích phải đối với xâu vào.
c.Một phân tích trái đối với xâu vào nếu tồn
tại hoặc đưa ra thông báo sai.
d.Thông báo “Thành công”
6.Khi
chuyển hình trạng nếu thay i:=i-1tức là
a.Dịch biến trỏ trên xâu vào sang phải một ký
hiệu
b.Dịch biến trỏ trên
xâu vào sang trái một ký hiệu
c.Dịch biến trỏ trên danh sách đẩy xuống thứ
nhất D1 sang trái một ký hiệu
d.Dịch biến trỏ trên danh sách đẩy xuống thứ
hai D2 sang một ký hiệu.
8.Mỗi thành
phần trong bảng mà thuật toán CYK đưa ra là
a.Một tập các ký hiệu không
kết thúc.
b.Một tập các ký hiệu kết thúc.
c.Một ký hiệu không kết thúc.
d.Một ký hiệu kết thúc
9.Thuật
toán phân tích LL(1) nhận vào
a.Văn phạm G là
LL(1) với các sản xuất được đánh số từ 1 đến q.
b.Văn phạm G là LL(k) với các sản xuất được đánh
số từ 1 đến q.
c.Văn phạm G với các sản xuất được đánh số
thứ tự từ 1 đến q.
d.Văn phạm G là LL(k) không cần đánh số các
sản xuất.
10.Cho văn
phạm với các sản xuất: S->aAb| c; A->hSg. Thế thì FOLLOW(S) =?
a.{b}
b.{a}
c.{c}
d.{g}
B.PHẦN TỰ
LUẬN
Câu 1 (2 điểm): Trình bày về thuật toán phân tích
LL(1)
Câu 2 (1 điểm): Cho văn phạm sau:
S ->
AB
A ->
aA | e
B ->
bB | e
Hãy tính
First , Follow của các ký hiệu S, A, B
Câu 3 (2
điểm): Cho văn phạm
E -> T + E | T
T -> a * T | a | ( E )
Phân
tích theo thuật toán Bottom-up với xâu vào “a*a+a”
Câu 4 (3 điểm):
Cho văn phạm:
(1)
E -> E + T
(2) E ->
T
(3) T ->
T * F
(4) T ->
F
(5) F ->
( E )
(6) F ->
id
Giả sử chúng ta đã xây dựng
được bảng phân tích action và goto như sau:
chú ý:
các giá trị trong action được
ký hiệu như sau:
a)
si có nghĩa là shift i
b) rj có nghĩa là reduce theo luật
(j)
c) acc có nghĩa là accept
d) khoảng trống biểu thị lỗi
trạng thái
|
Action
|
goto
|
|||||||
id
|
+
|
*
|
(
|
)
|
$
|
E
|
T
|
F
|
|
0
|
s5
|
S4
|
1
|
2
|
3
|
||||
1
|
s6
|
acc
|
|||||||
2
|
r2
|
s7
|
r2
|
r2
|
|||||
3
|
r4
|
r4
|
r4
|
r4
|
|||||
4
|
s5
|
S4
|
8
|
2
|
3
|
||||
5
|
r6
|
r6
|
r6
|
r6
|
|||||
6
|
s5
|
S4
|
9
|
3
|
|||||
7
|
s5
|
S4
|
10
|
||||||
8
|
s6
|
s11
|
|||||||
9
|
r1
|
s7
|
r1
|
r1
|
|||||
10
|
r3
|
r3
|
r3
|
r3
|
|||||
11
|
r5
|
r5
|
r5
|
r5
|
|||||
Sử
dụng thuật toán LR để phân tích xâu vào
“id*id” đối với dữ liệu trên
Hà
nội ngày tháng năm 2015
Giáo
viên ra đề
Comments[ 0 ]
Đăng nhận xét