TRƯỜNG ĐẠI HỌC NÔNG NGHIỆP HÀ NỘI
KHOA: CÔNG NGHỆ THÔNG TIN
Bài Tập Lớn:
Chương Trình Dịch
Đề Số 8
Giáo Viên Hướng Dẫn:
Nhóm Sinh Viên Thực Hiện: Phan Thị Chương
Bùi Thành Nam
Nguyễn Hồng Linh
Nguyễn Thị Xuân Mai
Hà Nôi, Tháng 12 năm 2012
Đề Tài 8:
Viết trình biên dịch dể dịch 1 doạn chuong trình gồm các phát biểu sau:
- Phát biểu gán, for 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 là các biểu thức số học và logic,
gồm các phép toán +, -
, *, / vàcác phép so sánh. Các toán hạng gồm các danh hiệu, hằng số thực,
nguyên, true,
false (kể cả biểu thức). Ðộ uu tiên các phép toán tuong tự Pascal.
- Thực hiện chuyển dổi kiểu từ nguyên sang thực khi cần thiết.
Thực Hiện
I. Phân Tích Từ Vựng
Token Lexeme Match Attribute
ID a1,d_e3c,ba2, (letter|’_’)(letter|digit|’_’)* vtrí BDB
ASG := ‘:=’
SEMI ; ‘;’
COLON : ‘:’
COMA , ‘,’
DOTDOT ‘ ’
VAR Var, var , (‘v’|’V’)(‘a’|’A’)(‘r’|’R’)

+
.digit
+
| digit
+
(.digit
+
|∈)(‘e’|’E’)
(‘+’|’- ‘|∈)digit
+
vtrí BDB
OP1 +,- ‘+’, ‘-‘ plus,minus
OP2 *,/ ‘*’,’/’ multiplication
,division
RELOP =, <, >, <=, >=, <> ‘=’, ’<’, ’>’, ’<=’, ’>=’, ’<>’
EQ, LT, GT,
LE,GE,NE
LƯỢC ĐỒ DỊCH
LƯỢC ĐỒ DỊCH
•
•
Sơ đồ dịch nhận dạng token relop:
Sơ đồ dịch nhận dạng token relop:
•
•
Sơ đồ dịch của id và từ khóa:
Sơ đồ dịch của id và từ khóa:
*
*
Start

>
other
=
=>
other
Start
letter | digit
|‘_’
letter | ‘_’
return(id, lookup(id))
other
2
6
2
7
28
*
•
•
Sơ đồ dịch nhận dạng hằng số:
Sơ đồ dịch nhận dạng hằng số:
II. Phân Tích Cú Pháp
A. Văn phạm gia tố:
S -> program
Program -> kbao body DOT
// var begin lenh end.
Kbao -> Var n_kbao
N_kbao -> kbkieu SEMI n_kbao // a:integer; b:real;
Kbkieu -> n_ID COLON TYPE SEMI //a:integer;
N_ID -> ID | ID COMA n_ID // a|a,b (truong hop nhieu bien co cung kieu)

3
3
digit
return(numreal,vtrí
bdb)
digit
other
3
8
8
other
*
*
‘E’
|’e’
Sta
rt
digit
3
0
digit
2
9
3
7
8
other
return(num,vtrí
bdb)
return(num,vtrí

18) NUM
29) NUMREAL
20) LPAR //(
21) RPAR //)
22) DOT
23) $
C. Ký hiệu không kết thúc:
1) Program
2) Kbao
3) Body
4) n_kbao
5) Kbkieu
6) n_ID
7) n_lenh
8) lenh
9) n_gan
10) l_for_do
11) r_body
12) exp
13) term
14) factor
D. FIRST của những kí hiệu chưa kết thúc:
1) FIRST(program) = FIRST(kbao) = {VAR}
3) FIRST(n_kbao)=FIRST(kbkieu) = FIRST(n_ID)={ ID}
4) FIRST (body) = {BEGIN, DOT}
5) FIRST (n_lenh)=FIRST (lenh) = {ID, BEGIN, FOR}
6) FIRST (l_gan) = {ID}
7) FIRST (l_for_do) = {FOR}
8) FIRST (exp)=FIRST(term)=FIRST(factor)= {D,NUM,
NUMREAL, LPAR, OP1}

program → kbao .body DOT
body → .BEGIN n_lenh END
I
3
= goto(I
0
, var):
kbao → var .n_kbao
n_kbao → .kbkieu SEMI n_kbao
kbaokieu → .n_ID COLON TYPE SEMI
n_ ID → .ID
n_ID → .ID COMA n_ID
I
4
= goto(I
2
, body):
program → kbao body .DOT
I
5
= goto(I
2
, BEGIN) = goto(I
5,
BEGIN) = goto(I
22,
BEGIN) = goto(I
49
,
BEGIN):

Kbkieu → n_ID .COLON TYPE SEMI
I
9
= goto(I
3
, ID) = goto(I
18
, ID) = goto(I
20
, ID)
N_ID → ID.
N_ID → ID .COMA n_ID
I
10
= goto(I
4
, DOT)
program → kbao body DOT.
I
11
= goto(I
5
, n_lenh)
body → BEGIN n_lenh .END
I
12
= goto(I
5
, lenh) = goto(I
22

22
, l_for_do) = goto(I
49
, l_for_do):
lenh → l_for_do.
I
16
= goto(I
5
, ID) = goto(I
21
, ID) = goto(I
17
, ID) = goto(I
49
, ID)
L_gan → ID .ASSGN exp SEMI
I
17
= goto(I
5,
FOR) = goto(I
22,
FOR) = goto(I
49
, FOR):
l_for_do → for .l_gan to ID do r_body
l_gan → .ID ASSGN exp SEMI
I
18

= goto(I
12
, SEMI)
N_lenh → lenh SEMI .n_lenh
N_lenh → lenh SEMI.
n_lenh → .lenh SEMI n_lenh
n_lenh → . lenh SEMI
lenh → .l_gan
lenh → .body
lenh → .l_for_do
l_gan → .ID ASSGN exp SEMI
body → .BEGIN n_lenh END
l_for_do → .for l_gan to ID do r_body
I
23
= goto(I
16
, ASSGN)
L_gan → ID ASSGN .exp SEMI
exp → .exp OP1 term
exp → .term
exp → .exp OP2 term
term → .factor
factor → .ID
factor → .NUM
factor → .NUMREAL
factor → .LPAR exp RPAR
factor → .OP1 factor
I
24

I
29
= goto(I
23
, term) = goto(I
34
, term)
exp → term.
I
30
= goto(I
23
, factor) = goto(I
34
, factor) = goto(I
38
, factor) = goto(I
39
,
factor)
term → factor.
I
31
= goto(I
23
, ID) = goto(I
34
, ID) = goto(I
35
, ID) = goto(I

NURREAL) = goto(I
38
, NURREAL) = goto(I
39
, NURREAL)
factor → NUMREAL.
I
34
= goto(I
23
, LPAR) = goto(I
34
, LPAR) = goto(I
35
, LPAR) = goto(I
38
,
LPAR) = goto(I
39
, LPAR):
factor → LPAR .exp RPAR
exp → .exp OP1 term
exp → .term
exp → .exp OP2 term
term → .factor
factor → .ID
factor → .NUM
factor → .NUMREAL
factor → .LPAR exp RPAR
factor → .OP1 factor

, SEMI)
L_gan → ID ASSGN exp SEMI.
I
38
= goto(I
28
, OP1) = goto(I
45
, OP1)
exp → exp OP1 .term
term → .factor
factor → .ID
factor → .NUM
factor → .NUMREAL
factor → .LPAR exp RPAR
factor → .OP1 factor
I
39
= goto(I
28
, OP2) = goto(I
45
, OP2)
exp → exp OP2 .term
term → .factor
factor → .ID
factor → .NUM
factor → .NUMREAL
factor → .LPAR exp RPAR
factor → .OP1 factor

, RPAR)
factor → LPAR exp RPAR.
I
45
= goto(I
40
,exp)
exp → exp .OP1 term
exp → exp .OP2 term
I
46
= goto(I
17
,l_gan)
l_for_do → for l_gan .to ID do r_body
I
47
= goto(I
46
,to)
l_for_do → for l_gan to .ID do r_body
I
48
= goto(I
47
,ID)
l_for_do → for l_gan to ID .do r_body
I
49
= goto(I