NGÔN NGỮ và PHƯƠNG PHÁP DỊCH - Chương 4: Phân tích ngữ nghĩa

ộ

« g m» } ặ

05/29/13

3

Cho văn ph m G = (V ạ

1. Gi

i thi u

ớ

ệ

Ví d 1ụ

L(G) =

ỏ

ỏ

ư ả

ỏ

Các câu đ u ề đúng ng pháp, ữ nh ng không ph i câu nào cũng đúng ng ữ nghĩa (có ý nghĩa)

« Bò vàng g m c non » ặ « Bò vàng g m c vàng » ặ « Bò non g m c non » ặ « Bò vàng g m bò non » ặ « C non g m bò vàng » ặ ỏ

05/29/13

4

…..

1. Gi

i thi u

ớ

ệ

Ví d 2ụ

(cid:222)

(cid:222)

(cid:222)

(cid:222)

Program Toto; Const N = 0; Begin

(cid:222)

N :=10; (cid:222)

(cid:222) End.

:= := N:= N:= N:= N:= N:= N:=10

Hoàn toàn đúng cú pháp c a KPL

ủ

S d ng sai ý nghĩa ban đ u (H ng s ) ố

ử ụ

ằ

ầ

05/29/13

5

(cid:222)

1. Gi

i thi u

ớ

ệ

Nh n xét ậ

• Không ph i m i câu văn ( ả ọ NNLT: câu l nhệ )

NNLT: cú pháp) đ u có giá đúng ng pháp ( ữ ề

tr s d ng ( ị ử ụ NNLT: th c hi n đ ự ệ ượ ) c

• B phân tích ng nghĩa nh m m c đích ki m ụ ữ ể ằ ộ

tra tính đúng đ n v m t ng nghĩa c a câu ề ặ ữ ủ ắ

05/29/13

6

văn (NNLT: câu l nh)ệ

1. Gi

i thi u

ớ

ệ

Nhi m v b phân tích ng nghĩa trong NNLT ụ ộ ữ ệ

– H ng, bi n, ki u t

ng trình con

ằ

ươ

ế

ả

ể

– Ph i đ – Ph i đ

ụ

• Gán giá tr cho h ng, tính toán trên ki u, th t c…

ướ c s d ng đúng m c đích ể

ả ượ ự ụ ằ

ủ ụ

ị – Đ m b o tính nh t quán

ấ

c khai báo ch m t l n trong ph m vi

ỉ ộ ầ

ả ả • Tên đ ượ • Các ph n t

trong ki u li

t kê (

ạ enum) là duy nh tấ

ầ ử

ể

ệ

ị c khi dùng • Qu n lý thông tin v các đ nh danh (tên) ị ề đ nh nghĩa, ch ể ự ị • Ki m tra vi c s d ng các đ nh danh ử ụ ệ c khai báo tr ả ượ

05/29/13

7

B ng ký hi u ệ ả

1. Gi

i thi u

ớ

ệ

Nhi m v b phân tích ng nghĩa trong NNLT ụ ộ ữ ệ

ử

ể ử ữ ệ

ỏ

• Ki m tra ki u d li u cho toán t ạ ủ

ể

ể

ể

ỉ ố ủ

ả

– Toán t ể – Có th yêu c u chuy n ki u b t bu c ( ắ ầ – Ch s c a m ng ph i nguyên ả ng ng gi a tham s th c s ự

ể % c a C đòi h i toán h ng ki u nguyên ộ int2real)

ng ng ki u

ự ươ ố ự ứ ữ ể

ố ươ

ứ

ể

ng tham s , t • Ki m tra ki u tr v c a hàm..

• Ki m tra s t và hình th cứ – S l ố ượ

ể

ủ

ứ

Các bi u th c ki u c a ngôn ng ữ ể B lu t đ đ nh ki u cho các c u trúc ể ộ ậ ể ị

ấ

05/29/13

8

ả ề ủ ể ể

Ch

ng 4: Phân tích ng nghĩa

ươ

ữ

1. Gi i thi u ớ ệ

2. B ng ký hi u ệ ả

3. Ch ng cú pháp ươ ng trình d ch đ nh h ị ị ướ

4. Ki m tra ki u ể ể

05/29/13

9

5. X lý sai sót ử

2. B ng ký hi u

ệ

ả

ụ

Phân tích t v ng ừ ự

ứ

ươ

Phân tích cú pháp

• M i ph n t

• B ng d li u mà các pha ữ ệ ả c a CTD đ u s/d ng ề ủ • Dùng ch a thông tin v ề các danh bi u (ể tên) xu t ấ ng trình hi n trong ch ệ ngu nồ ỗ

ầ ử ứ

ộ

M c đích ụ

B ng ả ký hi uệ

ng

ng v i m t ớ ườ

Phân tích ng nghĩa

ữ

ả

– Tr

Sinh mã

ủ –Bi n (ki u), h ng (giá tr )..

tên, g m 2 tr ồ – Tr ng tên ườ • Khóa c a b ng ủ ng thu c tính ộ ườ • Thu c tính c a tên ể

ộ ế

ằ

ị

05/29/13

10

2. B ng ký hi u

ệ

ả

M c đích ụ

ng trình ộ ặ ể ươ

ng ng vào b ng

ươ

ư

ứ

ả

ạ

Khi g p m t danh bi u trong ch • G p trong giai đo n khai báo ặ – Đ a tên và các thông tin t – Ví d : ụ Const Max = 10;

constant, giá tr là

10;

• Đ a ư Max vào b ng, v i ki u là

ớ ể

ả

ị

• G p trong câu l nh ệ

ụ

ữ

‹

ọ ể ử ụ • Phân tích ng nghĩa: S d ng đúng m c đích không? ử ụ Sai m c đích ụ

– Ví d : Max := 20; ụ • Sinh mã: Kích th

c b nh c p phát cho tên

ướ

ớ ấ 4 byte

ộ – Ví d : ụ int fi 2 bytes, float fi

05/29/13

11

ặ – Đ c thông tin ra đ s d ng

2. B ng ký hi u

ệ

ả

ả

Tên

Thu c tính ộ

m a x

n

gi

i

n t

A r

r a y

• Đ n gi n ơ • Nhanh • Đ dài tên b ị ộ i h n ớ ạ • Lãng phí nh ớ

(» 20%)

Tên

Thu c tính ộ

m a x eos n eos i n t A r

r

a

y eos

ệ

ả ơ

05/29/13

Hi u qu h n 12

L u tr tên ữ ư

2. B ng ký hi u

ệ

ả

Các yêu c u ph i có c a b ng ký hi u ủ ệ ả ầ ả

• Phát hi n m t tên cho tr c có trong b ng ệ ộ ướ ả

hay không

• Thêm m t tên vào b ng ả ộ

• L y thu c tính t ấ ộ ươ ng ng v i m t tên ớ ứ ộ

• Thêm các thông tin m i vào m t tên ộ ớ

05/29/13

13

• Xóa m t tên, nhóm tên ra kh i b ng ỏ ả ộ

2. B ng ký hi u

ệ

ả

Các c u trúc d li u cho b ng ký hi u ữ ệ ệ ả ấ

ch c b ng ký hi u khác nhau ệ ổ ề ứ

ơ • B ng băm

Nhi u cách t ả • Danh sách tuy n tính – Đ n gian, ch m ế ậ

ứ ạ

ả – Nhanh, ph c t p

ế ị

– M c đ ph c t p và t c đ v a ph i ả

ứ ạ

ộ ừ

ứ

i ch t l

ng c a ch ủ

ệ ả

ưở

B ng ký hi u nh h ớ ả trình d ch vì CTD làm vi c liên t c v i b ng ký hi u

ấ ượ ụ ớ ả

ng ươ ệ

ng t ệ

ị

05/29/13

14

• Cây nh phân tìm ki m ố ộ

2. B ng ký hi u

ệ

ả

Các CTDL cho b ng ký hi u ả

lãng phí)

ố ị

ướ

– Kích th – Gi

i quy t: danh sách liên k t (hai) chi u

ả ư ả ớ fi c c đ nh (ph i l n ế

ề

ả • Ti

t ki m b nh

ế

ộ

ớ

ế ệ • Danh sách không s p x p

ế

ắ

g p trong c/ trình ngu n

ả

ứ ự ặ

ồ

)

Đ ph c t p: O(n) ứ ạ

ế

ậ

ộ

– Thêm tên vào b ng theo th t – T c đ tìm ki m ch m ( ố – Th

ộ ng dùng v i các ngôn ng nh , có ít danh bi u

ể

ỏ

ữ

ườ

ắ

ớ • Danh sách s p x p ứ ạ

ả

O(log(n))

ế

ố

ộ

VD t p t

)

ể

ậ

ị

ậ ừ

05/29/13

ế – Ph c t p khi thêm tên vào b ng – T c đ tìm ki m: – Dùng khi t p danh bi u xác đ nh (

khóa 15

ệ fi Danh sách • Dùng m t (ộ nhi uề ) m ng l u các tên trong c/trình

2. B ng ký hi u

ệ

ả

ệ fi Cây tìm ki mế ả

f

ủ

ủ

a

max

ị ả

ọ

ả

m

pi

Các CTDL cho b ng ký hi u • Các nút c a cây nh phân có – Khóa là tên c a b n ghi – 2 con tr Left và Right ỏ • M i nút ph i th a mãn ả ả ủ ủ

ả ớ • Th i gian tìm ki m O(Log

không t n t

n

i ồ ạ ỏ

05/29/13

ố ỗ fi – G c r ng – Trùng khóa g c ố fi th a mãn ỏ ơ fi – Nh h n i con trái Tìm t ạ ơ fi – L n h n i con ph i Tìm t ả ạ ớ

16

ờ ỏ – Khóa c a con trái ph i nh h n ỏ ơ – Khóa c a con ph i ph i l n h n ơ 2(n)) ế

2. B ng ký hi u

ệ

ả

n

cp

Các CTDL cho b ng ký hi u ả ệ fi B ng băm ả

ầ ử ả

ch a tên và các thu c tính c a tên

ủ

ộ i danh sách liên k t ế

05/29/13

17

ố – M i ph n t

B ng là danh sách N ph n t • S ph n t c đ nh ầ ử ố ị ỗ ứ ầ ử • Có th là con tr , tr t ể ỏ ỏ ớ • Đòi h i m t hàm băm ộ ỏ

2. B ng ký hi u

ệ

ả

Các CTDL cho b ng ký hi u ả ệ fi B ng băm ả

ồ ầ ử

h(a ) ˛ [0..N-1]

" a • H là b ng băm g m N ph n t ả • h: là hàm băm : là m t tên ộ

Gi

" Trùng tên: Tên đã khai báo

" Tên ch a khai báo

" e „ a & b fi ứ

ượ a c

ứ

ể

05/29/13

ộ ng ng đ ra đ ư Xung đ t. M t ô ch a 2 tên ộ ươ

18

Ho t đ ng ạ ộ ế b = H[h(a )] t thi ả fi b = a b = e fi b „ – Đi theo DSLK t

2. B ng ký hi u

ệ

ả

B ng ký hi u cho c u trúc kh i ố ệ ấ ả

ằ

ố

• Ngôn ng là có c u trúc kh i n u

– Ph m vi c a khai báo trong m i kh i là chính

ủ

ỗ

ố

kh i đó và các kh i n m trong nó

ố ằ

ạ ố

ấ ữ ố ế – M t kh i có th đ c n m trong kh i khác ể ượ ố ộ • Ví d : Trong Procedure có Procedure khác… ụ

ộ

ủ

ề ả ằ

ố

ố ầ

ộ

ủ ụ

ủ ụ

ộ

ủ ụ

ủ

ạ

05/29/13

– Cho phép nhi u khai báo c a cùng m t tên • Các tên ph i n m trong các kh i khác nhau – Khai báo có hi u l c thu c kh i g n nh t ấ ệ ự • Khi m t th t c n m trong th t c khác đ ượ ằ ừ 19

c g i, ọ các khai báo c a th t c bên ngoài t m d ng ho t ạ đ ngộ

• Lu t l ng nhau g n nh t ấ ậ ồ ầ

2. B ng ký hi u

ệ

ả

• Toán t

Lu t v ph m vi s d ng ậ ề ử ụ ạ

Insert) vào b ng ký hi u không đ

c

ử

ệ

ượ

thêm ( ghi đè nh ng khai báo tr

ữ

ả c ướ

• Toán t

ử

ệ

lookup) trong b ng ký hi u luôn ả luôn tham chi u lu t ph m vi g n nh t ấ ậ

tìm ki m ( ế ế

ầ

ạ

• Toán t

xóa (

delete) ch đ

ử

ỉ ượ

c xóa khai báo g n nh t ấ

ầ

• Gi

i pháp

ả

– Dùng stack đ l u tr d u v t c a các th t c l ng

ủ ụ ồ

ế ủ

ữ ấ

ể ư

nhau

– T o b ng ký hi u m i cho m i th t c ủ ụ

ệ

ạ

ả

ớ

ỗ

• Thêm m t đ nh danh m i, c n ch rõ b ng ký hi u c n thêm

ộ ị

ệ

ả

ầ

ầ

ớ

ỉ

05/29/13

20

2. B ng ký hi u

ệ

ả

readArr

Program Sort

Null

i

Variable

Tên

Ptr

Thu c tính ộ

Arr

Variable

qSort

Max

Constant

Variable

k

readArr

subProc

Variable

v

qSort

subProc

Partition

subProc

ng

ậ

ươ

), c n ầ

Partition

ươ

i

Variable

ộ ả ng trình con t • Khi k t thúc ( ế

j

Variable

ệ ươ ỏ ả

• Khi đoán nh n m t ch ộ i trình con m i (ớ g i t ọ ớ compileBlock() đ quy ệ t o m t b ng ký hi u cho ạ ng ng ch ứ ra kh i th t c ủ ụ compileblock() ), b ng ký hi u s b xóa ẽ ị

ệ 05/29/13

21

Dùng nhi u b ng ký hi u ề ệ ả

2. B ng ký hi u

ệ

ả

V trí thêm vào

ị

j

Variable

i

Variable

ặ

ể

Partition subProc

i

v

Variable

Khi g p danh bi u trong khai báo đ a ư vào đ nh c a stack

ủ

ỉ

k

Variable

m ế k m

ì t

qSort

subProc

ặ

ể

i

readArr

subProc

ệ

u ề h C

Max

constant

G p danh bi u trong câu l nh, tìm đ nh tr xu ng t ở ừ ỉ

ố

Arr

Variable

Đáy Stack

05/29/13

22

Dùng Stack

2. B ng ký hi u

ệ

ả

ệ

ả

t v trí c a đ nh stack

• Dùng stack làm b ng ký hi u • Dùng giá tr ị Tx cho bi

ế ị

ủ

ỉ

• Giá tr c a Tx không thay đ i trong compileBlock()

– Tx là tham trị c a ủ compileBlock()//compileBlock(int Tx) ổ

ị ủ

– Khi phân tích Block, th t c

ẽ ượ

ủ ụ compileBlock() có th g i ể ọ c k th a đ n chính nó, Tx s đ ế ừ ế • Khi đoán nh n th t c con, Tx s tăng d n lên khi g p các danh ẽ

ủ ụ

ặ

ầ

ng trình con

bi u c a ch ủ

ể

ậ ươ

ụ

ỏ

• Khi đoán nh n xong - thoát ra kh i compileBlock(), Tx khôi ph c )

c khi goi

l

ị ướ

ậ i giá tr cũ ( giá tr tr ị ạ – Nh ng khai báo bên trong m t kh i s b xóa đi

ố ẽ ị

ư

ộ

Ví d đ n gi n ụ ơ ả

– Ban đ u, danh sách r ng

compileBlock(0)

ầ

ỗ

05/29/13

23

fi

2. B ng ký hi u

ệ

ả

X

Variable

ả

AA

subProc

Z

Variable

X

Variable

Procedure AA; Var X: integer; Begin Z= X+Y*M End;

A

subProc

Y

constant

X

constant

M

Constant

Begin End; Procedure B; Var X, Y; Begin End;

Đáy Stack

Begin End. 05/29/13

24

Ví d đ n gi n ụ ơ Const M=10; Var X, Y: integer; Procedure A; Var X, Z: Integer;

2. B ng ký hi u

ệ

ả

ầ

ủ ụ

C n các th t c • Procedure Enter(char * Id, Object Type);

ộ

ả

ệ

– Đ a m t danh bi u vào b ng ký hi u ể

ể

ị ủ

ư • Giá tr c a danh bi u • Ki u danh bi u (constant, type, variable, procedure, function)

ể

ế

ệ

ỉ

ị

ể • Function Location(char * Id) : int; ả ủ không th y, tr v giá tr 0 ả ề

– Ch ra v trí c a danh bi u trong b ng ký hi u. N u ể ị

ấ

– Ki m tra tên (Id) đã đ

c khai báo trong ph m vi ch a

• Function checkIdent(char * Id) : Boolean; ạ

ượ

ư

ể

05/29/13

25

Ví d đ n gi n ụ ơ ả

2. B ng ký hi u

ệ

ả

[

]

Ví d đ n gi n ụ ơ

VAR

Number

ả fi Khai báo Ident

,

;

void compileBlock( ){

….. if(Token==VAR){ Token = getToken();

compileDeclareVariable (); while(Token == COMMA) { Token = getToken(); compileDeclareVariable ();

}; } ….

} 05/29/13

26

2. B ng ký hi u

ệ

ả

void compileDeclareVariable(void){

if(Token==IDENT){

if(CheckIdent(Id) == 0) Enter(Id,Variable); Else Error();//Trung ten Token = getToken(); if(Token == LBRACK){

……..

} }else Error(19);//Thieu ten bien

}

} 05/29/13

27

Ví d đ n gi n ụ ơ ả fi Khai báo

2. B ng ký hi u

ệ

ả

Ví d đ n gi n ụ ơ ả fi S d ng ử ụ

:=

Expression

Ident

[

]

Expressio n void compileStatement(){

int p; if(Token == IDENT){ p = Position(Id); if(p < 0) Error(52); //Ten chua khai bao if(getKind(p) != Variable)

Error( );//Ve trai phai la mot bien

Token = getToken(); if(Token == LBRACK){

……..

}

}

05/29/13

28

Ch

ng 4: Phân tích ng nghĩa

ươ

ữ

1. Gi i thi u ớ ệ

2. B ng ký hi u ệ ả

3. Ch ng cú pháp ươ ng trình d ch đ nh h ị ị ướ

4. Ki m tra ki u ể ể

05/29/13

29

5. X lý sai sót ử

3. Ch

ng cú pháp

ị

ng cú pháp (Syntax directed definition)

ng trình d ch đ nh h ị ươ Đ nh nghĩa h ị

ướ ướ

ổ ạ

ỗ ộ ậ ộ

ế ừ

– Hai lo i thu c tính: T ng h p và k th a ộ – Thu c tính là khái ni m tr u t

ệ

ng b t kỳ: s , xâu, v trí trong b nh ..

ộ m t đ i l

ấ

ố

ớ

ng, bi u di n ể ừ ượ ị

ễ ộ

ộ ạ ượ

• Là d ng t ng quát c a VPPNC ủ • M i ký hi u VP liên k t v i m t t p thu c tính ế ớ ợ ổ ệ ạ

i m t nút trong cây đ

c

ộ

ượ

ổ ộ

ủ

• Thu c tính t ng h p ợ – Giá tr c a thu c tính t ạ ị ủ xác đ nh t ừ ị

– Giá tr c a thu c tính đ

c đ nh nghĩa d a vào

ượ

ộ

ị

giá tr nút cha và/ho c các nút anh em c a nó.

ộ

ộ giá tr c a các nút con c a nó. ị ủ • Thu c tính k th a ế ừ ị ủ ị

ặ

05/29/13

ự ủ 30

3. Ch

ng cú pháp

ướ

ị

ng cú pháp

ng trình d ch đ nh h ị ươ D ng c a đ nh nghĩa h ị ủ ạ

ướ

a

liên h v i m t t p lu t ậ

ộ ậ

ệ ớ

ấ ạ ạ

b= f (c1, c2, . . . . ., cn) trong đó f là

• M i s n xu t d ng A ng nghĩa có d ng m t hàm và b tho m t trong hai yêu c u sau:

ỗ ả ữ ộ

ả ộ

ầ

ộ

ộ

ủ

ợ

– b là m t thu c tính t ng h p c a A và c

ổ ế ớ

ệ

fi

a

1,.., cn là các thu c tính liên k t v i các ký hi u trong v ế ộ ph i s n xu t A ả ả

ấ

ộ

ộ

fi

ộ ệ

ấ

a

a

– b là m t thu c tính k th a m t trong nh ng ký ế ừ , và c1,.., cn là thu c tính ế

ả ả

ệ

ấ

ữ hi u xu t hi n trong ệ ộ c a các ký hi u trong v ph i s n xu t A ủ • T p lu t ng nghĩa dùng đ tính giá tr thu c tính c a

ủ

ữ

ể

ậ

ậ

ộ

ị

ký hi u Aệ

05/29/13

31

fi

3. Ch

ng cú pháp

ị

ng cú pháp

ng trình d ch đ nh h ị ươ Đ nh nghĩa h ị

ướ ướ

Quy t c ng nghĩa

fi Ví dụ ắ

S n xu t ấ

ả

ữ

E return E1+T T T1 * F F (E) digit

ợ val ợ lexval ( Đ c b ộ

ượ

ừ ự

ư

L fi E fi E fi T fi T fi F fi F fi •Các ký hi u ệ E, T, F có thu c tính t ng h p •T t phân tích t 05/29/13

Print (E.val) E.val = E1.val + T.val E.val = T.val T.val = T1.val * F.val T.val = F.val F.val = E.val F.val = digit.lexval ộ ổ ừ ố digit có thu c tính t ng h p ổ ộ v ng đ a ra )

32

3. Ch

ng trình d ch đ nh h ị

ướ

ị

ng cú pháp ươ Cây phân tích cú pháp có chú gi

iả

05/29/13

33

Cây có ch ra giá tr các thu c tính t ộ ỉ ị ạ i m i nút ỗ

3. Ch

ướ

ng trình d ch đ nh h ị

ộ

Quy t c ng nghĩa

ng cú pháp ị ươ ế ừ fi Ví dụ Thu c tính k th a S n xu t ấ

ả

ữ

ắ

T L ;

L.in := T.type

int

T.type = integer

D fi T fi T fi L fi

float L1 , Id

T.type := real L1.in := L.in addType(Id.entry, L.in)

Id

addType(Id.entry, L.in)

ộ

ổ

ệ

ợ type có giá tr ị

khóa

T L ; n ấ

ị

ậ

i ki u khai báo ấ ừ L, s truy n ki u c a ể ủ ụ addType() đ l u thu c tính

ủ L v i ớ ộ

ế

i v trí

ệ ạ ị

ủ

ả

L fi •Ký hi u không k t thúc T có thu c tính t ng h p ế int/float trong khai báo c xác đ nh b i t đ ở ừ ị ượ ấ D fi L.in := T.type g n v i s n xu t •Lu t ng nghĩa ớ ả ắ ữ ậ ủ L (L.in) t đ nh thu c tính k th a c a ớ ể ế ừ ộ •Lu t ng nghĩa g n v i s n xu t t ẽ ớ ả ắ ữ các khai báo ti p và dùng th t c ki u c a danh bi u vào b ng ký hi u t ể ể 05/29/13

ề ể ư Id.entry 34

3. Ch

ng trình d ch đ nh h ị

ướ

ị

ng cú pháp ươ Cây phân tích cú pháp có chú gi

iả

Ví d v i khai báo: float x, y, z ; ụ ớ

D

T.type = real L.in = real ;

L.in = real , Id2 real

L.in = real , Id2

05/29/13

35

Id1

3. Ch

ng cú pháp

ươ

ng trình d ch đ nh h ị

ị

ướ

ạ

ầ

ng trình bao t m d ng

• Văn ph m cho phép các ch – Khi b t đ u phân tích ch ươ ạ

ắ ầ ươ

c a ch ủ

ng trình con bao nhau ươ ng trình con, ph n khai báo ừ

– Dùng m t b ng ký hi u riêng co m i ch

ng trình con

ỗ

ươ

ệ

ạ

L u tr thông tin v ph m vi ư ữ ề ạ

D

D; D | id : T | proc id ; D ; S

ộ ả • Văn ph m c a khai báo này: ủ P fi D fi • Khi khai báo ch

D fi

ươ

ng trình con c phân tích thì các khai báo trong D1 đ

c l u

proc id D1; S ượ ư

ượ

đ trong b ng kí hi u m i. ớ

ệ

ả

05/29/13

36

3. Ch

ng cú pháp

ươ

ng trình d ch đ nh h ị

ị

ướ

//Ch

ng trình Quicksort

ươ

L u tr thông tin v ph m vi ư ữ ề ạ fi Ví dụ

1) Program sort; 2) Var a: array[0..10] of integer; 3) x: integer; 4) Procedure readarray; 5) Var i: integer; 6) Begin …… end {readarray}; 7) Procedure exchange(i, j: integer); 8) Begin {exchange} end; 9) Procedure quicksort(m, n: integer); 10) Var k, v: integer; 11) Function partition(y,z: integer): integer; 12) Begin ……exchange(i,j) end; {partition} 13) Begin … end; {quicksort} 14)Begin … end; {sort}

05/29/13

37

3. Ch

ng cú pháp

ươ

ng trình d ch đ nh h ị

ị

ướ

• Các b ng ký hi u c a ch

ng trình sort

ủ

ệ

ả

ươ

05/29/13

38

L u tr thông tin v ph m vi ư ữ ề ạ fi Ví dụ

3. Ch

ng cú pháp

ươ

ng trình d ch đ nh h ị

ị

ướ

ộ ả

ạ

ả

ớ

• mktable(previous) – t o m t b ng kí hi u m i, b ng ả

ệ này có previous ch đ n b ng cha c a nó. ỉ ế

ủ

ng

ớ

ệ

ộ ố ượ c ch ra b i ở ỉ offset ng đ i là ố

ượ ỉ ươ

ị

ể ng t

• enter(table,name,type,offset) – thêm m t đ i t name vào b ng kí hi u đ ả type và đ a ch t ng ng. ứ

m i có tên table và đ t ki u là ặ vào các tr ươ ườ

• enterproc(table,name,newbtable) – t o m t ph n t

ầ ử

ạ

ộ name,

ớ

m i trong b ng ả newtable tr t ỏ ớ ả

ng trình con table cho ch ươ i b ng kí hi u c a CTC này. ủ ệ

ổ

• addwidth(table,width) – ghi t ng kích th ả

c c a t t ướ ủ ấ trong b ng kí hi u vào header c a b ng. ả ủ

c các p/t ả

ử

ệ

05/29/13

39

Quy t c ng nghĩa fi Các thao tác ữ ắ

3. Ch

ng cú pháp

ươ

ng trình d ch đ nh h ị

ị

ướ

Khai báo trong ch ươ

ng trình con Quy t c ng nghĩa ữ ắ

S n xu t ấ

ả MD

Pfi

addwidth(top(tblptr), top(offset)); pop(tblptr); pop(offset)

M fi

e

t:=mktable(null); push(t, tblptr); push(0, offset)

D fi D ; D D fi proc id; ND1;S

N fi

e

D fi

id : T

i b ng ký hi u

t:=top(tblpr); addwidth(t,top(offset)); pop(tblptr); pop(offset); enterproc(top(tblptr), id.name, t) t:=mktable(top(tblptr)); push(t,tblptr); push(0,offset); enter(top(tblptr),id.name,T.type, top(offset); top(offset):=top(offset) + T.width ỏ ỏ ớ ả

ệ

ứ ư

ữ

Tblptr: là Stack dùng ch a các con tr tr t Offset: Là Stack dùng l u tr các Offset 05/29/13

40

3. Ch

ng cú pháp

ươ

ng trình d ch đ nh h ị

ị

ướ

• S n xu t:

c th c hi n tr

c

ượ

ự

ệ

ướ

ch

ng trình

ệ cho ph m vi ngoài cùng (

ươ

ạ

ạ

ng trình con X lý các khai báo trong ch ươ

ệ mktable(nil) //Không có SymTab cha tblptr v i b ng ký hi u v a t o ra

ừ ạ

ệ

ớ ả

ặ

• S n xu t:

ớ mktable(top(tblptr))

ạ • Tham s ố top(tblptr) cho giá tr con tr t

ị

ỏ ớ ả

ả

ẩ

ử ấ Pfi MD : ả – Ho t đ ng c a cây con M đ ủ ạ ộ e : ấ M fi • S n xu t: ả – T o b ng ký hi u ả sort) b ng l nh ằ – Kh i t o stack ở ạ – Đ t offset = 0. e : ấ N fi ả – T o ra m t b ng m i ộ ả

ỉ offset M khi m t khai báo CTC xu t hi n

i b ng cha tblptr //push(t,tblptr) //push(0,Offset) ấ

ệ

ộ

05/29/13

– Thêm b ng m i vào đ nh stack ớ – 0 đ c đ y vào stack ượ ng t N đóng vai trò t ự ươ

41

3. Ch

ng cú pháp

ươ

ng trình d ch đ nh h ị

ị

ướ

X lý các khai báo trong ch ng trình con ử ươ

id: T

c t o ra cho

id trong b ng kí hi u ả

ệ

• V i m i khai báo ớ – m t ph n t hi n hành (

ỗ ộ ệ

c tăng lên b i

m i đ ầ ử ớ ượ ạ top(tblptr)) – Stack tblptr không đ i, ổ – Giá tr ị top(offset) đ ượ

ở T.width.

• Khi Dfi

– Kích th

t c các đ i t

ng d li u khai báo

ướ

ữ ệ

offset.

c c a t ẽ ằ c này đ

c l u tr b ng cách dùng Addwidth(),

ướ

ỉ – Kích th ượ ư – Các stack tblptr và offset b l y m t ph n t

trên cùng

proc id ; N D1 ; S di n ra ễ ố ượ ủ ấ ả trong D1 s n m trên đ nh stack ữ ằ ị ấ

ấ

ầ ử

(pop() )

– Thao tác th c hi n trên các khai báo c a ch

ng trình

ự

ủ

ệ

ươ

con.

05/29/13

42

Ch

ng 4: Phân tích ng nghĩa

ươ

ữ

1. Gi i thi u ớ ệ

2. B ng ký hi u ệ ả

3. Ch ng cú pháp ươ ng trình d ch đ nh h ị ị ướ

4. Ki m tra ki u ể ể

05/29/13

43

5. X lý sai sót ử

4. Ki m tra ki u

ể

ể

ể

ươ

ng pháp ki m tra ki u ể

• Có hai ph • Ki m tra tĩnh : áp d ng trong th i gian d ch ụ

ờ

ng

ể – Trong nhi u ngôn ng (C hay Pascal,..) ki m tra ki u là ươ

ị ể ắ

ủ

ề ượ c khi nó đ

c th c hi n

ể c dùng đ ki m tra tính đúng đ n c a ch ệ

ữ ể ể ươ

tĩnh và đ trình tr ướ

ự

ộ

ự

ờ ể ự

ể

ộ

ộ ố • int Tab[255], i; fi

khi th c hi n Tab[i] có th n m ngoài ph m vi

• Ki m tra đ ng : th c hi n trong th i gian th c thi ự ệ ể – M t s phép ki m tra chi có th th c hi n đ ng ự

ệ ể ằ

ệ

ạ

• B ki m tra ki u đ

c xây d ng d a trên

ự

ự

Ki m tra ki u ể ể

ể ứ

ể

ủ

ữ

ượ ộ ể – Các bi u th c ki u ể c a ngôn ng – B ộ lu t đ đ nh ki u ậ ể ị

ể cho các c u trúc

ấ

05/29/13

44

4. Ki m tra ki u

ể

ể

Bi u th c ki u (type expression) ứ ể ể

c xây d ng ộ ượ ự ẩ

ể

ứ

ể ki u. ể ấ

ậ

ơ ở ặ

ể

t: ệ i trong quá trình ki m tra ki u

ộ ỗ

ể

ể

ỉ

Ch p nh n các ki u c s đ c bi • type_error: ch ra m t l • void: cho phép ki m tra ki u đ i v i l nh.

ể

ể

Là m t ki u d li u chu n ho c đ ữ ệ t các ki u d li u khác b i c u trúc ki u ữ ệ ừ 1. Ki u c s ( ể ặ ể ở ấ ể ơ ở boolean, char, integer, real) là bi u th c

Tên là

ố ớ ệ c đ t tên ặ

ể

ể

ể ượ

1. Do bi u th c ki u có th đ ứ ể

bi u th c ki u ứ

ể

ự

ể ) vào

các bi u th c ki u t o ra bi u th c ki u

2. Áp d ng toán t ụ ể

xây d ng ki u ( ử ể ạ

ể c u trúc ki u ể ể

ấ ứ

ứ

05/29/13

45

(cid:222)

4. Ki m tra ki u

ể

ể

C u trúc ki u ể ấ

ể

Array): • M ng ( ả

– N u ế T là bi u th c ki u thì array(I,T) là bi u th c ứ ể ể ầ ử ể T ki u ớ ễ

ể ỉ ố

ể ư ki u bi u di n m t m ng v i các ph n t ả ộ ề I và ch s trong mi n • Khai báo: array [10] of integer • có ki u: array(1..10,int); //

array(10,int)

ể • Tích Descarter:

– N u ế T1 và T2 là các bi u th c ki u thì tích

Descarter T1× T2 là bi u th c ki u

ể ể

ứ ứ

ể ể

05/29/13

46

4. Ki m tra ki u

ể

ể

C u trúc ki u ể ấ

• B n ghi ( Record):

ng bên

ủ

ể

ườ

trong – Ví d :ụ

ả – Là tích descarter các ki u c a các tr

struct{

double r; int i;

}

05/29/13

47

Có ki u ((r x double) x (i x int)) ể

4. Ki m tra ki u

ể

ể

C u trúc ki u ể ấ

pointer(T) là bi u th c

– Nêu T là bi u th c ki u thì ể

ứ

ể

ứ

ể

ki u ể

• Con tr :ỏ

– N u D là mi n xác đ nh và ề

c bi u di n là

• Hàm ế

ị ủ R.

D fi

ủ

ề ễ

ượ

R là mi n giá tr c a ể

ị hàm thì ki u c a nó đ ể Ví d ụ • int f(char a, char b) fi Có ki u: ể char × char fi • int * f(int a, int b) fi

có ki u int x int

int. pointer(int)

ể

05/29/13

48

fi

4. Ki m tra ki u

ể

ể

H th ng ki u ệ ố ể

• T p các lu t đ n đ nh các bi u th c ki u ị ậ ể ấ ứ ể ể ậ

vào các ph n khác nhau c a ch ng trình ủ ầ ươ

• B ki m tra ki u th c hi n m t h th ng ki u ộ ệ ố ộ ể ự ệ ể ể

• Đ c đ nh nghĩa thông qua đ nh nghĩa t a cú ượ ự ị ị

05/29/13

49

pháp

4. Ki m tra ki u

ể

ể

B ki m tra ki u đ n gi n ộ ể ể ả ơ

D → D;D | id : T

T → char | int | array[num] of T | ↑T

E → literal | num | id | E mod E | E[E] | E↑

Xét văn ph mạ P → D;E

ươ ở

1

–Gi

thi

Văn pham sinh ra ch ng trình b t đ u b i các ắ ầ khai báo D và sau đó là m t bi u th c ứ E ộ

ỉ ố ả

ả

ế

05/29/13

50

ể t ch s m ng b t đ u t ắ ầ ừ

ể B ki m tra ki u c a đ nh danh

4. Ki m tra ki u ể ộ ể

ể ủ

ị

Quy t c ng nghĩa

ữ

ắ

S n xu t ấ

addType(Id.entry, T.type) T.type = char T.type = integer T.type = pointer(T1.type)

ả D ; E D ; D Id : T char integer › T1

T.Type = array(1..num.val,T1.type)

ể

ị

ượ

ề

ướ

ệ

c khai c khi bi u ể

P fi D fi D fi T fi T fi T fi T fi array[num] of T1 Do P fi báo đ u đ th c ứ E đ ượ

D ; E nên ki u c a các đ nh danh đ ủ c l u trong b ng ký hi u tr ả ượ ư c ki m tra ki u ể

ể

05/29/13

51

ể B ki m tra ki u c a bi u th c

4. Ki m tra ki u ể ộ ể

ể ủ

ứ

ể

Hàm lookup(idx) tr v ki u trong b ng ký hi u t

i v trí

idx

ả

05/29/13

ả ề ể

ệ ạ ị 52

ể B ki m tra ki u c a câu l nh

4. Ki m tra ki u ể ộ ể

ể ủ

ệ

• V i các câu l nh không có giá tr (

ị

l nh gán, l nh g p,.. ệ ệ

ộ

) s ẽ

ớ

ệ ơ ở void có ki u c s

ể

ủ ệ

ể

ệ

D; S

• L i trong câu l nh thì ki u c a l nh là: ỗ • M t ch ộ

ng trình hoàn ch nh có thêm lu t ỉ

type_error ậ P fi

ươ

05/29/13

53

ể B ki m tra ki u c a hàm

4. Ki m tra ki u ể ộ ể

ể ủ

Quy t c ng nghĩa

ữ

S n xu t ấ

ả Id : T

D fi

ắ addType(Id.entry, T.type) D.type = T.type D.type = D1.type x D2.type

D1 ; D2

T.type)

fun id(D):T; B addType(id.entry,D.type fi

D fi Fun fi B fi S fi

{ S } Id(EList)

t2 AND

S.type = if lookup(Id.entry)= t1fi EList.type=t1 then t2 else type_error

EList fi EList fi

EList.type = E.type EList.type = EList1.type x E.type

05/29/13

E Elist1 , E

54

4. Ki m tra ki u

ể

ể

ể

ể

ứ

ẩ then return true;

ể

ữ ệ

s2 and t = t1fi

t2 then

05/29/13

//s và t là các bi u th c ki u function sequiv(s, t): boolean; begin if s và t có cùng ki u d li u chu n else if s = array(s1, s2) and t = array(t1, t2) then return sequiv(s1, t1) and sequiv(s2, t2) else if s = s1 x s2 and t = t1 x t2 then return sequiv(s1, t1) and sequiv(s2, t2) else if s = pointer(s1) and t = pointer(t1) then return sequiv(s1, t1) else if s = s1fi return sequiv(s1, t1) and sequiv(s2, t2) else return false; end;

55

ng đ ng Ki m tra bi u th c ki u t ể ể ươ ứ ể ươ

4. Ki m tra ki u

ể

ể

ể

Quy đ i v m t ki u ổ ề ộ

ể

05/29/13

56

Chuy n ki u ể float x; int n; x + n fi

Ch

ng 4: Phân tích ng nghĩa

ươ

ữ

1. Gi i thi u ớ ệ

2. B ng ký hi u ệ ả

3. Ki m tra ki u ể ể

4. Ch ng cú pháp ươ ng trình d ch đ nh h ị ị ướ

05/29/13

57

5. X lý sai sót ử

5. X lý sai sót

ử

Gi i thi u ớ ệ

i ặ ỗ ế

Phân tích cú pháp n u g p l • G i t

ể

i th t c ọ ớ – Thông báo ki u c a l ủ ụ Error(…) đ báo l ủ ỗ i ỗ i i và v trí c a l ủ ỗ ể ị

i ng ng quá trình d ch l i ạ ỗ

– B i văn b n ngu n không kh p v i d đoán

fi

ươ

ị ớ ớ ự t đi theo h ừ ồ ng trình d ch không bi ị

ng nào ướ t đi nhánh

ặ

• Sau khi báo l ả ở Ch • VD: g p statement

ế (X):=10; s không bi ẽ

ế

nào

– Ch

ng trình d ch có

n l

ị

c n ầ n+1 l n d ch

ầ

ị

i ỗ fi

ươ • T n kém ố • C n đi u ch nh đ CTD có th h i ph c sau khi g p

ể ồ

ụ

ề

ể

ặ

05/29/13

ỉ

58

ầ iỗ l

5. X lý sai sót

ử

Ph ng pháp ươ

ồ ả

ắ

ượ

• V t b m t đo n trên văn b n ngu n cho t i ạ ớ t c m t t i cho phép n m b t l ộ ừ ố ắ ạ ng trình và có th ti p t c ể ế ụ ươ ự ế

ấ

ị ỏ

• Các t c c u trúc là ắ ượ ấ

i, ít khi b b xót

theo sau c u trúc đang phân tích t c u trúc đã b b qua ế ấ ủ ấ

ị ỏ

ượ ỏ ộ khi tìm đ ượ c c u trúc ch đ ấ làm vi c theo d ki n ệ cho phép n m b t đ t ắ ừ ố ừ . Có th làể các ký hi u ng ng ệ – Các t t ừ ố • Khi g p, cho bi ặ • Là FOLLOW() c a c u trúc

ệ

ấ trong c u trúc hi n t t ệ ạ ừ ố • Đ c goi là Các ký hi u ch t ố • Th khóa c a c u trúc hi n t ng là t ấ ủ ừ

– Các t ượ ườ

i ệ ạ

05/29/13

59

5. X lý sai sót

ử

Ph ng pháp ươ fi Ví dụ

ỗ ở ể

thi u ế

L i toán h ng ho c d u ‘(‘

bi u th c (Term) ( ứ ) ặ ạ

ấ

if max > a + * 10 then

ế Condition

ỏ

đã b qua h t i (coi nh đã tri n khai xong Condition)

• Sau Condition (Expression) là Then, Do,.. • Khi g p KW_THEN ư

ậ ỗ

ể

ặ • Ghi nh n l • Có th ti p t c tri n khai

fi

Statement

ể ế ụ

ể

05/29/13

60

5. X lý sai sót

ử

Ph ng pháp ươ fi Ví dụ

ỗ ở

Condition

if max > a + 10 Min then

L i if : (thi u t

Statement, nhánh Then ) khóa

ế ừ

t ph i b c

i khi

ế

ả ỏ ả statement cho t

ớ

• Sau Statement là End ; . • Không nh t thi ấ g p ặ End ; .

• Khi đ n ế Then là có th b t đ u phân tích ti p

ể ắ ầ

ế

05/29/13

61

5. X lý sai sót

ử

Ph ng pháp ươ fi Th c hi n ệ ự

ầ ể ự

ụ ể ồ ừ ữ

ủ ụ

ấ

ộ

đang phân tích

ệ

ộ

ụ ế

• Đ th c hi n, c n cho bi t các th t c phân ủ ụ ế ệ tích cú pháp (dùng đ tri n khai m t đích, ví ộ ể ể d compileBlock(), compileStatement(),.. ) có nh ng ký hi u ng ng nào th h i ph c ệ – Các ký hi u ch t thu c chính c u trúc mà th t c ố ụ ở ệ

IF, ký hi u theo sau là

THEN, còn

ọ

– Các ký hi u theo sau c u trúc (ph thu c ch g i) ỗ ọ ấ c Ví d :ụ Đang phân tích Condition, n u Condition đ ượ g i trong nhánh ệ trong nhánh WHILE, ký hi u theo sau là

DO

ệ

c k th a t

ượ

ế ừ ừ

các c u trúc ấ

– Các ký hi u ng ng đ ừ ệ (th t củ ụ ) bên trên

05/29/13

62

5. X lý sai sót

ử

Ph ng pháp ghi nh n l ươ i ậ ỗ

• Khi l c không c n v t ỗ ượ

ế

ấ ; ho c ặ End trong statement

ng trình ngu n t đ ế ượ ươ ầ ồ

i có th đoán bi ể quá m t đo n trong ch ạ ộ – Ví d , l i thi u d u ụ ỗ • Có th s a l i s đ và vi ể ử ạ ơ ồ t l ế ạ i theo s đ ơ ồ

Begin

End

Statement

Statement

m iớ

;

05/29/13

63

5. X lý sai sót

ử

if (token == BEGIN){

getToken(); compileStatement(); while (token ˛ [Semicolon]¨ FIRST(Statement) do{

Ph ng pháp ghi nh n l ươ i ậ ỗ

ế

ấ

if(Token == Semicolon) getToken(); else addError(« Thi u d u ‘;’ »); compileStatement();

addError() ch ỉ ghi nh n m t ộ ậ i, ỗ thông báo l không d ng ừ ng trình ch

ươ

} if (token == END) getToken(); else addError(« Thi u t

khóa End »);

ế ừ

} 05/29/13

64