HomeLời giải đề thi môn Chương trình Dịch
Thứ Năm, 17 tháng 7, 2014
ĐỀ
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
7.Văn phạm
đệ qui trái là văn phạm có các sản xuất dạng
d.A->A ( đúng )
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)
Thuật toán phân tích LL(1)
Một bộ phân tích cú pháp LL(1) bao gồm: một vùng đệm
chứa xâu vào với cuối xâu là ký hiệu kết thúc xâu $; một ngăn xếp chứa các ký
hiệu văn phạm thể hiện quá trình phân tích; một bảng phân tích LL(1) và thành
phần chính điều khiển phân tích.
Mô hình của phân tích cú pháp LL
Tại thời
điểm hiện tại, giả sử X là ký hiệu trên đỉnh ngăn xếp và a là ký hiệu đầu vào.
Các hành động điều khiển được thực hiện như sau:
1. nếu X = a = $, quá trình phân
tích thành công
2. nếu X = a ¹ $, lấy X ra khỏi ngăn xếp và
dịch con trỏ đầu vào đến ký hiệu tiếp theo
3. nếu X là một ký hiệu không kết
thúc, xét mục M(X,a) trong bảng phân tích. Có hai trường hợp xảy ra:
a) nếu M(A,a) = X -> Y1.
. .Yk thì lấy X ra khỏi ngăn xếp và đẩy vào ngăn xếp Y1,
. . ., Yk theo thứ tự ngược lại (để ký hiệu được phân tích tiếp theo
trên đỉnh ngăn xếp phải là Y1, tạo ra dẫn xuất trái).
b) nếu M(A,a) là lỗi thì quá trình
phân tích gặp lỗi và gọi bộ khôi phục lỗi
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
Kết quả:
Fisrt(A)
= {a, e}
First(B)
= {b,e}
First(S)
= {a,b,e}
Follow(S)
= {$}
Follow(A)
= {b,$}
Follow(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”
STT
|
STACK
|
BUFFER
|
HÀNH ĐỘNG
|
0
|
$
|
a*a+a$
|
di chuyển
|
1
|
$ a
|
*a+a$
|
T->a
|
2
|
$T
|
*a+a$
|
di chuyển
|
3
|
$T*
|
a+a$
|
di chuyển
|
4
|
$T*a
|
+a$
|
T->T*a
|
5
|
$T
|
+a$
|
E->T
|
6
|
$E
|
+a$
|
di chuyển
|
7
|
$E+
|
a$
|
di chuyển
|
8
|
$E+a
|
$
|
T->a
|
9
|
$E+T
|
$
|
E->T+E
|
10
|
$E
|
$
|
Chấp nhận
xâu đúng cú pháp VP G
|
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
Trả lời:
Chúng
ta 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 như sau:
Ngăn xếp
|
Đầu vào
|
Hành động
|
0
|
id * id $
|
gạt
|
0
id 5
|
* id $
|
thu
gọn F->id
|
0
F 3
|
* id $
|
thu
gọn T->F
|
0
T 2
|
* id $
|
gạt
|
0
T 2 * 7
|
id $
|
gạt
|
0
T 2 * 7 id 5
|
$
|
thu
gọn F->id
|
0
T 2 * 7 F 10
|
$
|
thu
gọn T->T*F
|
0
T 2
|
$
|
thu
gọn E->T
|
0
E 1
|
$
|
chấp
nhận (accepted)
|
Hà
nội ngày tháng năm 2015
Giáo viên ra đề
Ths.Trần Thị Hiền
Comments[ 0 ]
Đăng nhận xét