BÀI TẬP LỚN
MÔN CHƯƠNG TRÌNH DỊCH

Sinh viên thực hiện : 1. Đỗ Thanh Mai
2. Đỗ Mỹ Hồng Nhung
3. Nguyễn Thị Thu Thủy
4. Bùi Thị Thu Ngân
Nhóm : 2
Lớp : Tin học 52C
GV hướng dẫn : Phan Thị Thu Hồng
Đề tài 6:
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, if then else 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). Độ ư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.
Yêu cầu:
• Viết chương trình bằng tay.
• Quá trình phân tích cú pháp được thực hiện theo phương pháp từ dưới lên
• Giai đoạn xử lý ngữ nghĩa sinh viên phải thực hiện bằng cách đặt các hành
vi ngữ nghĩa vào bản đặc tả cú pháp
I.
I.
PHÂN TÍCH TỪ VỰNG
PHÂN TÍCH TỪ VỰNG
1. Bảng Token
1. Bảng Token
Token Lexeme Match Attribute

LE,GE,NE
LPAR ( ‘(‘
RPAR ) ‘)’
TYPE Integer,
iNteger, …
Real, rEal, …
Boolean,
bOolean, …
(‘i’|’I’)(‘n’|’N’)(‘t’|’T’)(‘e’|’E’)
(‘g’|’G’)(‘e’|’E’) (‘r’|’R’) |
(‘r’|’R’)(‘e’|’E’)(‘a’|’A’)(‘l’|’L’) |
(‘b’|’B’)(‘o’|’O’)(‘o’|’O’)(‘l’|’L’)
(‘e’|’E’)(‘a’|’A’) (‘n’|’N’)
Integer
Real
Boolean
NUM 1,33,10,490,… digit(digit)*
NUMREAL 1.2, 2E-3 ,
0.5e+4
digit
+
.digit
+
| digit
+
(.digit
+
|∈)
(‘e’|’E’)(‘+’|’- ‘|∈)digit
+

Start
letter | digit
|‘_’
letter | ‘_’
return(id, lookup(id))
other
0 1
2
*
Start
0
3
4
+
-
return(OP1, minus)
return(OP1, plus)
Start
0 3
4
return(OP2, multiplication)
return(OP2, division)
*
/
2.5 Sơ đồ dịch nhận dạng token các toán tử quan hệ relop:
Start
0
<
1
=

8) n_lenh -> lenh SEMI n_lenh | Ɛ // Thuc hien 1 hoac nhieu lenh |khong co
lenh nao
9) lenh -> l_gan
10) lenh -> body
11) lenh -> l_if_then_else
12) l_gan -> ID ASSGN exp SEMI //a:=0;
13) l_if_then_else -> IF r_IF THEN r_body ELSE r_body
14) r_IF ->LPAR ID RELOP NUM RPAR | LPAR ID RELOP NUMREAL
RPAR | LPAR ID OP1 ID RELOP NUM RPAR | LPAR ID OP2 ID
RELOP NUM RPAR | LPAR ID OP1 ID RELOP NUMREAL RPAR |
LPAR ID OP2 ID RELOP NUMREAL RPAR RPAR //
(a<=1) | (a<=0.1) | (a+b> 2) | (a*b> 2) | (a+b>=2.2) | (a*b> =2.2)
15) r_body -> n_lenh SEMI
16) exp -> exp OP1 term |exp OP2 term |term
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;
2.Các ký hiệu kết thúc
1) VAR
2) COLON
3) TYPE
4) SEMI //( ; )
5) ID
6) COMA //(,)
7) BEGIN
8) END
9) ASSGN //(:=)

16) exp1
17) exp2
4.FIRST của những kí hiệu chưa kết thúc:
1) FIRST(program) = (VAR)
2) FIRST(kbao) = (VAR)
3) FIRST(n_kbao)=FIRST(kbkieu) = FIRST(n_ID)= ID
4) FIRST (body) = BEGIN
5) FIRST (n_lenh) =FIRST(l_if_then_else)= (ID, BEGIN,IF, Ɛ)
6) FIRST (l_gan) = (ID)
7) FIRST (l_if_then_else) = (IF)
8) FIRST (exp)=FIRST(term)=FIRST(factor)= (ID,NUM, NUMREAL,
LPARA, OP1)
9) FIRST(r_IF) = (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
1) FOLLOW (program) = FOLLOW (kbao)= FOLLOW (n_kbao)= ($)
2) FOLLOW (body) = (SEMI, END, DOT)
3) FOLLOW(kbk) = FOLLOW (lenh) = FOLLOW (l_gan)= FOLLOW
(l_if_then_else)= FOLLOW (r_IF)=(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
I
0
: S’ ->.S
S ->. program

1
= goto(I
0
,S):
S’->S.
I
2
= goto(I
0
,program):
S -> program.
I
3
= goto(I
0
,kbao):
Program -> kbao. body DOT
body ->.BEGIN n_lenh END
I
4
= goto(I
0
,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
I
5

l_gan -> .ID ASSGN exp SEMI
l_if_then_else -> . IF r_IF THEN r_body ELSE r_body
body ->.BEGIN n_lenh END
I
9
= goto (I
0
,lenh)
n_lenh -> lenh .SEMI n_lenh
I
10
= goto (I
0
, Ɛ)
n_lenh -> Ɛ.
I
11
= goto (I
0
,l_gan)
lenh ->l_gan.
I
12
= goto (I
0
, body)
lenh -> body.
I
13
= goto (I

factor -> .NUM
factor ->. NUMREAL
factor -> .LPARA exp RPARA
factor -> .OP1 factor
I
16
= goto (I
0
, n_lenh)
r_body -> n_lenh.
I
17
= goto (I
0
, exp)
exp ->exp. OP1 term
exp -> exp . OP2 term
I
18
=goto (I
0
, term)
exp ->term.
I
19
= goto (I
0
, factor)
term -> factor.
I

= goto (I
3
, BEGIN)
body -> BEGIN .n_lenh END
n_lenh -> .lenh SEMI n_lenh
n_lenh -> .Ɛ
lenh -> .l_gan
lenh -> .body
lenh ->.l_if_then_else
l_gan -> .ID ASSGN exp SEMI
l_if_then_else -> . IF r_IF THEN r_body ELSE r_body
Body ->.BEGIN n_lenh END
I
25
= goto (I
4
, n_kbao)
Kbao -> VAR n_kbao.
I
26
=goto (I
4
, kbk)
n_kbao -> kbk .SEMI n_kbao
I
27
=goto (I
4
, n_ID)
Kbk -> n_ID .COLON TYPE SEMI

body-> BEGIN n_lenh. END
I
33
= goto (I
8
, lenh) = I
9
I
34
= goto (I
8
, Ɛ) = I
10
I
35
=goto (I
8
, l_gan) = I
11
I
36
= goto (I
8
, body) = I
12
I
37
= goto (I
8
, l_if_then_else) =I

16
I
43
= goto (I
14
, lenh) = I
17
I
44
=goto (I
14
, Ɛ) = I
10
I
45
=goto (I
14
, l_gan) = I
11
I
46
= goto (I
14
, body) = I
12
I
47
= goto (I
14
, l_if_then_else) =I

18
I
53
= goto (I
15
, factor) = I
10
I
54
= goto (I
15
, ID)
factor -> ID.
I
55
= goto (I
15
, NUM) = I
20
I
56
= goto (I
15
, NUMREAL) = I
21
I
57
= goto (I
15
, factor)

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
I
62
= goto (I
20
, OP1)= I
22
I
63
= goto (I
20
, factor) =I
57
I
64
= goto (I
20
, ID) = I
54
I
65