Chương trình dịch – Đề số 2

Giảng viên hướng dẫn: Phan Thị Thu Hồng
Nhóm 01:
1. Dương Thị Bích Phượng
2. Nguyễn Thị Yến
3. Phạm Minh Đức
Lớp: THC52
============================================================
Đề số 2
Viết trình biên dịch để dịch 1 đoạn chương trình gồm các phát
biểu sau:

Phát biểu gán, repeat until trong pascal

Các phát biểu kết thúc bằng dấu ;

Các biểu thức trong các phát biểu gồm các phép toán logic
Not, And, Or và các phép so sánh. Các toán hạng gồm các định
danh, hằng số thực, nguyên, true, false (kể cả biểu thức). Độ ưu
tiên các phép toán tương tự Pascal.

Thực hiện chuyển đổi kiểu từ nguyên sang thực khi cần thiết.
A. Tìm hiểu những nội dung liên quan đến yêu cầu đề bài
I. Phát biểu gán, repeat until trong pascal
1. Phát biểu gán (:=)
Một trong các lệnh đơn giản và cơ bản nhất của Pascal là lệnh gán. Mục đích của
lệnh này là gán cho một biến đã khai báo một giá trị nào đó cùng kiểu với biến.
* Cách viết:
<Tên_biến> := <biểu thức> ;


Chương trình dịch – Đề số 2

Mỗi số nguyên được biểu diễn trong máy dưới dạng một dãy các bít nhị phân. Số
kiểu Integer được biểu diễn bằng 16 bit. Ví dụ, số 1 và số 2 có biểu diễn trong máy
lần lượt là :
0000 0000 0000 0001
0000 0000 0000 0011
Phép lấy NOT một số nguyên sẽ đảo tất cả các bít biểu diễn số nguyên đó, tức
là 0 thành 1, còn 1 thành 0. Ví dụ:
NOT 1 = 1111 1111 1111 1110
NOT 2 = 1111 1111 1111 1100
Phép lấy AND, OR, XOR hai số nguyên được tiến hành bằng cách AND, OR,
XOR từng cặp bít tương ứng của hai số đó, ví dụ:
1 OR 2 = 0000 0000 0000 0011= 2
1 AND 2 = 0000 0000 0000 0001= 1
2. Các phép toán so sánh
Ký hiệu Ý nghĩa Ví dụ
= bằng nhau x=y
<> khác nhau x<>y
< nhỏ hơn x<y
<= nhỏ hơn hoặc bằng x<=y
> lớn hơn x>y
>= lớn hơn hoặc bằng x>=y
|

3
Nhóm 1 – Lớp THC52 – Khoa Công nghệ thông tin
Chương trình dịch – Đề số 2

B. Nội dung thực hiện

(‘B’|’b’)(‘O’|’o’)(‘L’|’l’)(‘E’|’e’)
(‘A’|’a’)(‘N’|’n’)
Integer
Real
Boolean
NUM 1,33,10,490,… digit(digit)* vtrí BDB
NUMREA
L
1.2, 2E-3 ,0.5e+4
digit
+
.digit
+
| digit
+
(.digit
+
|∈)(‘e’|’E’)
(‘+’|’- ‘|∈)digit
+
vtrí BDB
OP1 +,- ‘+’, ‘-‘ plus,minus
OP2 *,/ ‘*’,’/’ multiplicati
on,division
RELOP =, <, >, <=, >=, <> ‘=’, ’<’, ’>’, ’<=’, ’>=’, ’<>’
EQ, LT,
GT,
LE,GE,NE
RPAR ) ‘)’


• Ghi chú:

5
Nhóm 1 – Lớp THC52 – Khoa Công nghệ thông tin
Chương trình dịch – Đề số 2

- BDB: bảng danh biểu.
- Các từ khóa(keyword) được insert vào bảng danh biểu trước khi phân tích từ
vựng.
- Thứ tự ưu tiên của các phép toán trong Pascal (tương ứng với các phép toán đề
bài đưa ra):
+ Dấu ngoặc ( )
+ Phép toán một ngôi: NOT.
+ Phép toán *, /, AND.
+ Phép toán +, -, OR
+ Phép toán so sánh =, <, >, <=, >=, <>
2. LƯỢC ĐỒ DỊCH
2.1 Sơ đồ dịch của id và từ khóa:
2.2 Sơ đồ nhận dạng OP1:

6
Nhóm 1 – Lớp THC52 – Khoa Công nghệ thông tin
Start
letter | digit
|‘_’
letter | ‘_’
return(id, lookup(id))
other
0 1
2

digit

‘+’|’-
‘
8
4
9
5
digit
‘E’
|’e’
5
2
7
3
digit
return(numreal,vtrí
Bbdb)
digit
other
6
8
8
other
*
*
‘E’
|’e’
Sta
rrrt

VAR
BEGIN
END.
*/8
Nhóm 1 – Lớp THC52 – Khoa Công nghệ thông tin
Start
0
<
1
=
2
return(relop, LE)
3
>
return(relop, NE)
other
4
return(relop, LT)
5
=
7
=
8
other
6
>
return(relop, GT)

Nhóm 1 – Lớp THC52 – Khoa Công nghệ thông tin
Chương trình dịch – Đề số 2

17) term -> factor
18)factor -> ID
19) factor -> NUM
20) factor -> NUMREAL
21) factor -> LPARA exp RPARA //a:=a * (c-d);
22) factor -> OP1 factor // a:= - b;
23) factor -> NOT factor //
24) factor -> TRUE // a:=true
25) factor -> FALSE //a:=false
1.2 Văn phạm sau khi loại bỏ đệ quy trái:
1)S -> ten kbao body DOT
2)ten -> PROGRAM ID
3)kbao -> Var n_kbao
4)n_kbao -> kbk SEMI n_kbao // a:integer; b:real;
5)kbk -> n_ID CONON TYPE SEMI //a:integer;
6)n_ID -> ID | ID COMA n_ID // a|a,b (truong hop nhieu bien co cung
kieu)
7)Body -> BEGIN n_lenh END
8)n_lenh -> lenh SEMI n_lenh | Ɛ // Thuc hien 1 hoac nhieu lenh | khong co
lenh nao
9)lenh -> l_gan
10)lenh -> body

10
Nhóm 1 – Lớp THC52 – Khoa Công nghệ thông tin
Chương trình dịch – Đề số 2


1) VAR
2) COLON
3) TYPE
4) SEMI //( ; )
5) ID
6) COMA //(,)
7) BEGIN
8) END
9) ASSGN //(:=)
13) AND
14) OR
15) NOT
16) RELOP
17) OP1
18) OP2
19) NUM

12
Nhóm 1 – Lớp THC52 – Khoa Công nghệ thông tin
Chương trình dịch – Đề số 2

20) NUMREAL
21) LPAR //(
22) RPAR //)
23) PROGRAM
24)TRUE
25)FALSE
26) $
3. Các ký hiệu chưa kết thúc
1) ten

LPARA, OP1, NOT, TRUE, FALSE)
9) FIRST(l_until) = (LPAR)
10) FIRST (lenh) = (ID, BEGIN,REPEAT)
11) FIRST (exp1)= (OP1,Ɛ)
12) FIRST (exp2)= (OP2,Ɛ)
5. Tính FOLLOW của những kí hiệu chưa kết thúc

14
Nhóm 1 – Lớp THC52 – Khoa Công nghệ thông tin
Chương trình dịch – Đề số 2

1) FOLLOW (ten) = FOLLOW (kbao)= FOLLOW (n_kbao)= ($)
2) FOLLOW (body) = (SEMI, END, DOT)
3) FOLLOW(kbk) = FOLLOW (lenh) = FOLLOW (l_gan)= FOLLOW
(l_repeat_until)= FOLLOW (r_until)=(SEMI)
4) FOLLOW (n_ID) = (COMAN)
5) FOLLOW (n_lenh)= ( END, SEMI)
6) FOLLOW (exp)= =(RPARA, SEMI)
7) FOLLOW(term) = FOLLOW(factor) = (LPAR, SEMI, OP1, OP2)
6. Tính action, goto
/* Các luật:
1)S -> Ten kbao body DOT
2)Ten -> PROGRAM ID
3)kbao -> VAR n_kbao
4) n_kbao -> kbk SEMI n_kbao
5) kbk -> n_ID CONON TYPE SEMI
6) n_ID -> ID
7) n_ID ->ID COMA n_ID
8) Body -> BEGIN n_lenh END
9) n_lenh ->.lenh SEMI n_lenh

Chương trình dịch – Đề số 2

30) factor -> OP1 factor
31) factor -> NOT factor
32) exp ->term
33) factor -> TRUE
34) factor -> FALSE
I0:
S’ ->.S
S ->. Ten kbao body DOT
Ten -> .PROGRAM ID
kbao -> .VAR n_kbao
n_kbao -> .kbk SEMI n_kbao
kbk ->. n_ID CONON TYPE SEMI
n_ID ->. ID
n_ID ->. ID COMA n_ID
Body ->. BEGIN n_lenh END
n_lenh ->. lenh SEMI n_lenh | Ɛ
lenh ->. l_gan
lenh ->.body
lenh ->. l_repeat_until
l_gan ->. ID ASSGN exp SEMI

17
Nhóm 1 – Lớp THC52 – Khoa Công nghệ thông tin
Chương trình dịch – Đề số 2

l_repeat_until ->. Repeat r_body UNTIL r_until
r_until ->.LPAR ID RELOP NUM RPAR
r_until ->.LPAR ID RELOP NUMREAL RPAR

*
I021’=goto(I02,kbao)
S -> ten kbao. body DOT
body ->.BEGIN n_lenh END
*
I04=goto(I0,VAR)
Kbao ->VAR .n_kbao
N_kbao ->.kbk SEMI n_kbao
Kbk -> .n_ID CONON TYPE SEMI
N_ID -> .ID
N_ID ->. ID COMA n_ID
*
I05 =goto(I0,kbk)
N_kbao ->kbk. SEMI n_kbao
*

19
Nhóm 1 – Lớp THC52 – Khoa Công nghệ thông tin
Chương trình dịch – Đề số 2

I06= goto (I0, n_ID)
Kbk ->n_ID .COMA n_ID
*
I07 = goto (I0, ID)
n_ID ->ID.
N_ID -> ID. COMA n_ID
L_gan -> ID. ASSGN exp SEMI
Factor -> ID.
*
I08= goto (I0, BEGIN)

I014 = goto (I0, REPEAT)
L_repeat_until -> REPEAT. r_body UNTIL r_until
R_body ->.n_lenh
N_lenh -> .lenh SEMI n_lenh
N_lenh -> .Ɛ
Lenh -> .l_gan
Lenh -> .body

21
Nhóm 1 – Lớp THC52 – Khoa Công nghệ thông tin
Chương trình dịch – Đề số 2

Lenh ->.l_repeat_until
L_gan -> .ID ASSGN exp SEMI
L_repeat_until -> .REPEAT r_body UNTIL r_until
Body ->.BEGIN n_lenh END
*
I015 = goto (I0, LPAR)
R_until -> LPAR .
Factor -> LPAR . exp RPAR
exp -> .exp OP1 term
exp -> .exp OP2 term
exp ->.term
term ->. factor
factor -> .ID
factor -> .NUM
factor ->. NUMREAL
factor -> .LPARA exp RPARA
factor -> .OP1 factor
*

Nhóm 1 – Lớp THC52 – Khoa Công nghệ thông tin
Chương trình dịch – Đề số 2

factor -> .NUMREAL
factor -> .LPAR exp RPAR
factor ->. OP1 factor
*
I023 =goto (I0, NOT)
Factor -> NOT . factor
factor ->. ID
factor -> .NUM
factor -> .NUMREAL
factor -> .LPAR exp RPAR
factor ->. OP1 factor
*
I024 =goto (I0, FALSE)
Factor -> FALSE.
*
I024 =goto (I0, TRUE)
Factor -> TRUE.
*
I31 = goto (I03, body)
Program -> kbao body .DOT

24
Nhóm 1 – Lớp THC52 – Khoa Công nghệ thông tin
Chương trình dịch – Đề số 2

*
I32 = goto (I03, BEGIN)