Báo cáo đề tài: Cú pháp và ngữ nghĩa trong ngôn ngữ lập trình

Trang 1 ĐẠI HỌC QUỐC GIA TP.HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
KHOA KHOA HỌC MÁY TÍNH
BÀI BÁO CÁO
p trình
 tài: Cú pháp và ng  ng lp trình

Giảng viên: Ths.Trnh Qu
Nhóm sinh viên:
Phm Qut MSSV:11520529
601

TP H Chí Minh 11/2013
Báo cáo đề tài: Cú pháp và ngữ nghĩa trong ngôn ngữ lập trình

Trang 1

Báo cáo đề tài: Cú pháp và ngữ nghĩa trong ngôn ngữ lập trình

Trang 2
Lời cảm ơn

Trên thực tế không có sự thành công nào mà không gắn liền với những sự hỗ trợ,
giúp đỡ dù ít hay nhiều, dù trực tiếp hay gián tiếp của người khác. Trong suốt thời
gian từ khi bắt đầu học tập ở giảng đường đại học đến nay chúng em đã nhận được rất
nhiều sự quan tâm, giúp đỡ của quý Thầy Cô, gia đình và bạn bè.
Với lòng biết ơn sâu sắc nhất, em xin gửi đến quý Thầy Cô ở Khoa Khoa Học Máy
Tính – Trường Đại Học Công Nghệ Thông Tin đã cùng với tri thức và tâm huyết của
mình để truyền đạt vốn kiến thức quý báu cho chúng em trong suốt thời gian học tập tại
trường. Và đặc biệt, trong học kỳ này, Khoa đã tổ chức cho chúng em được tiếp cận với
môn học mà theo em là rất hữu ích đối với sinh viên ngành Khoa Học Máy Tính cũng
như tất cả các sinh viên thuộc các chuyên ngành Khoa Học Kĩ Thuật khác. Đó là môn
học “Nguyên Lý và Phương pháp lập trình”.
Em xin chân thành cảm ơn thầy Ths.Trịnh Quốc Sơn đã tận tâm hướng dẫn chúng em
qua từng buổi học trên lớp cũng như những buổi nói chuyện, thảo luận về đề tài . Nếu
không có những lời hướng dẫn, dạy bảo của thầy thì em nghĩ đè tài này chúng em rất
khó có thể hoàn thiện được. Một lần nữa,chúng em xin chân thành cảm ơn thầy.

TP H Chí Minh 11/2013
(Nhóm sinh viên thực hiên)













.

.


Báo cáo đề tài: Cú pháp và ngữ nghĩa trong ngôn ngữ lập trình

Trang 4 I. CÚ PHÁP VÀ NGỮ NGHĨA
Ngôn ng lp trình là h thng gm các ký hiu và các qui tc kt hp các ký hiu
thành các c lp trình cung cp m
mô t mt thut toán mà máy tính có th hic nó.

Trang 5 Ví dụ 3: Ta xét biu thc sau
Biu thc 1=4
Biu thc 2=1+3
Biu thc 3=1+1+1+1
C 3 biu thu có cùng giá tr, tc là ging nhau v mt ngữ nghĩa tuy nhiên
chúng khác nhau v mt cú pháp
Ví dụ 4:
C: if (x > y) x = x-1; else y ;
Pascal: if x > y then x := x-1 else y := y-1;
Nhận xét:
 S khác nhau: du ngoc tròn  x > y, t then, = hoc :=, Du chm phc
else,
 V m mt ng ng nhau
Sự quan trọng của cú pháp:
 Cú pháp chính xác, rõ ràng là rt quan trng; Nu bn không nh
trình ca bn không th chy
 Trong mng; bn hc nó, bn sn
t thúc
 a mt ngôn ng có ng rt ln:
o Làm th  vit cách d dàng
o Làm th  c và hi dàng
o Tht d  to ra nhng li cú pháp khó hiu
Cú pháp là đánh máy (Syntax is typographical)
 Cú pháp mô t cách chúng ta vit chui ký t
 Cú pháp có th chính xác và chính thi BNF (Backus-Naur
Form)
 Mt ngôn ng ng là mt chui các ký t (hoc âm thanh) và

 Lit kê tt c các dng ca mi lp
Ví dụ:
-Lớp cú pháp
C Hng (constant)
O Toán t(operator)
E Biu thc (expression)
-Dạng cú pháp
E ::= C | E O E | ( E ) Ví dụ: cú pháp lp trng cho ngôn ng PASCAL. Các ký hiu cho lp cú pháp
B hng
O toán t
I danh hiu
L biu thc v trái
literal
Operater
identifier
l-expression
Báo cáo đề tài: Cú pháp và ngữ nghĩa trong ngôn ngữ lập trình

Trang 7 E biu thc
K biu thc 
T biu thc kiu
P thông s hình thc

C lnh

P::=I:I | var I:I
D::=const I=K; l type I=T;| var I:T; |
Procedure Ifunction I
) | C;C |
If E then C l if E then C else C |
end |
While E do C l repeat C until E |
For I:=E to E do C | for I:=E downto E do C |
With L do begin C end | begin C end
M::=program I

Ưu điểm: ca cú pháp trn, cho thy mt cách nhìn khái quát v cu
trúc cú pháp ca ngôn ng
Nhược điểm:không  cn ký hiu ca ngôn ng mà nó mô t, vi cú pháp tru
ng chúng ta không th c mt chui ký hiu có phi là m
hp l u trúc ca s kt hp các kí hiu trong chui
2.2 Cú pháp cụ thể (concrete syntax)
Báo cáo đề tài: Cú pháp và ngữ nghĩa trong ngôn ngữ lập trình

Trang 8 Cú pháp c th khc phc các m ca cú pháp trng.Nó cho
nh cu trúc kt hp ca chui ký hiu và cho bit chui ký hip l
hay không
m phi ng cnh( Context Free Grammars)
 i Noam Chomsky gi
 Language generators : miêu t
 V w

 Các ch in hoa A, B, C, D, E, và S ký hiu các bic dùng làm
ký hiu bu ).
 Các ch nh a, b, c, d, e, ; các chsvà mt s ký hiu khác ký hiu cho các ký
hiu kt thúc.
 Các ch in hoa X, Y, Z là các ký hiu có th là ký hiu kt thúc hoc bin.
 Các ch Hi-lu din cho chui các ký hiu kt thúc và bin.

Ta s biu dim mt cách tóm tt bng cách chlit kê các lut sinh ca nó.
Nt sinh ca bim nào
 ghi ngn g

Ví dụ 2: m trong Ví d.1 trên có th vit gn là :




Chúng ta qui ước:
 Mô t m bng cách lit kê các lut sinh.
 Lut sinh cha ký hiu bu s c liu tiên.
 Nu có nhiu lut sinh có cùng v trái thì nhóm li thành mt lut sinh duy nht,
 phi cách nhau bi ký hi

Ví dụ: t biu thc s hc (expression) bao gm các danh biu
(identifier) tham gia vào các phép toán +, * hoc biu thc con lng trong du ngo
, ta vit :
<expression> ::= <expression> + <expression> <expression> ::= <expression> *
<expression> <expression> ::= (<expression> )
<expression> ::= <identifier>


S aAS aSbAS aabAS aabbaS aabbaa

Ví dụ : xây dng cây phân tích cú pháp t dn xut.
E -E - (E) - (E + E) - (id + E) - (id + id)
Báo cáo đề tài: Cú pháp và ngữ nghĩa trong ngôn ngữ lập trình

Trang 11
Cây phân tích cú pháp minh ha ký hiu ca mm dn mt chui
trong ngôn ng.
 Nu ký hit thúc A có lu
th có mt nút trong có nhãn A ng t trái qua phi
là X, Y,Z
 Cây cú pháp (syntax - tree) là dng rút gn ca cây phân tích cú pháp 
biu din cu trúc ngôn ng.
 Trong cây cú pháp các toán t và t khóa không phi là nút lá mà là các nút trong.
Ví dụ: vi luc biu din bi cây cú pháp:

Mt kiu rút gn khác ca cây cú pháp là chui các luc rút gn li. Chng
hn ta có:

Sự mơ hồ (hay sự nhập nhằng) của văn phạm
Khái niệm: mm phi ng cc gm nhp nhng hay
còn g (ambiguity) nu nó có nhit cây dn xut cho cùng mt chui

Hoc
var x,y: real;
Begin


 Báo cáo đề tài: Cú pháp và ngữ nghĩa trong ngôn ngữ lập trình

Trang 13 Hic tha nhn r nh nhng ràng
buc v ng cc dit mt cách không hình thc.
vic mô t không hình th và không chính xác.
III.NGỮ NGHĨA
Ng 
  ca biu thc, câu la cu trúc trong mt ngôn
ngc vit bi ngôn ng 
 Ng  cho mi th,bn làm trong ngôn ng
 Cú pháp ch  mô t ng 
 a 1 ngôn ng lu so va cú pháp
 Ng  t ch cu trúc cú pháp (maps
syntactical) cho mô hình tính toán
Ng  Mô hình tính toán (computational model)
Cách tiếp cận này gọi là ngữ nghĩa theo cú pháp
Ngữ nghĩa mức độ thấp (Low level semantics)
Ngữ nghĩa có thể ảnh hưởng đến mọi thứ ở mức rất thấp:
Ví dụ:

 S dng ngôn ng sai
Vai trò của ngữ nghĩa ngôn ngữ lập trình (The Role of Programming Language
Semantics)

Báo cáo đề tài: Cú pháp và ngữ nghĩa trong ngôn ngữ lập trình

Trang 15
 Nhng li th c
chch xác nh thành 1 hành vi chính thc
 i vi ng ng hoàn toàn
 Nhip cy và nhii không hiu rõ và không s
dng ph bin
u thú v là ng ng sau thc t mt ngôn ng hoc có th không
áp dng cho toàn b ngôn ng (ng hp v HTML và SGML)
 a mt ngôn ng lp trình rõ ràng và chính xác, ng a ngôn
ng lc mô t mt cách hình thc.Ng c không ch là
 cho vic chn c
thit k và thc hin ngôn ng lp trình
Một số ngữ nghĩa phổ biến bao gồm: ngữ nghĩa tĩnh (Static semantic) và ngữ nghĩa
động (Dynamic semantic)
Synthesized attributes
Attribute grammars
Natural semantics

Static semantic

Operational semantics

o M  ph thuc vào máy
 La chn tng máy tính hoàn chnh
 Quá trình:
o Xây dng mt máy dch(dch mã ngun ti mã máy ca 1 máy tính lý
ng)
o Xây dng mt gi lng Máy rút gọn (reduction machine)

B u khin rút gn m tr ng a nó.
( 3 + 4 ) * 5 (7) * 5
7 * 5
35

Lut rút gn
















8)
  
   

9)
  
   

10)
  
   

11)
  
   

12)
  
   

13)
  
  

14)
    
  





-list
stmt--

letter Cú pháp trừu tượng



1

2



1

2
| E
1
-





Env&{I = n} : thêm 1 ràng buc mng
(Env&{I=n})(J)=



Luật cho biểu thức
Báo cáo đề tài: Cú pháp và ngữ nghĩa trong ngôn ngữ lập trình

Trang 19 < E | Env > : biu thng Env
i các lut rút gn dùng dng biu din có chng Đánh giá ngữ nghĩa tác vụ:
o Tt nu s dng 1 cách không chính thng dn s dng ngôn ng
o Phc tp nu s dng 1 cách chính thc

5.2. Ngữ nghĩa biểu thị( Denotational semantics):

Báo cáo đề tài: Cú pháp và ngữ nghĩa trong ngôn ngữ lập trình

Trang 20 N [[101]] = 2* N [[10]] +1=2*2* N [[1]]+1 = 2*2*1+1=5
Ngôn ngữ lập trình đơn giản
 n hóa v ta ch xét mt ngôn ng li n. Ngôn
ng này gm hai h, các du ngoc tròn
Hai phép toán:
 mt toán h-
 Hai toán hng là: 
Các lnh ca ngôn ng gm lnh rng (null ) , lnh gán, các cu khi
bn (tun tu kin và lp), và lnh gi th tc (call). Th tng
lnh gán thân th tc vào các tê th tc. Tt c các danh hiu là
toàn ct danh hiu nhp- xut. D liu nhp c
khng cho danh hiu nhp-xut sau khi thc hi liu xut
c

Ví dụa ngôn ng ln
Program (x);
Begin
y:=x;
p:=(procedure x:=x+1)
if x=y then x:=x+(-1) else x:=0;
call p
end

Vi d liu nhp là mt s bt k, d li  liu nhp lun lý s
gây ra l





 Kí hiu:


Mô t phép thc hi i v

Có tt c ba hàm ng  a biu thc, hàm ng a câu
lnh, và hàm ng a 
Hàm ng a biu thc din dt biu thc ()
 ) , hàm ng E s cho giá tr ng ca biu thc
Hàm ng a câu lnh: cho bit lnh  , kt qu ca hàm
ng  mi
Hàm ng  và giá tr nhp
, Hàm ng  cho kt qu ct giá tr n)

Bảng Ngôn ngữ lập trình đơn giản

Cú pháp trừu tượng
I  Ide
E  Exp
C  Com
M  Pro

Danh hiu
Biu thc
Phát biu



Qui ước
E : Exp (S c vit là E : Exp S E
D i s ca hàm ng 










Nu s là1 ánh xthì 













 


Cú pháp ca ngôn ng c b sung thêm hai dt câu lnh m
sau:
D  Def
D var I = E | const I = E
C  | with D do C
Báo cáo đề tài: Cú pháp và ngữ nghĩa trong ngôn ngữ lập trình

Trang 23 Ví dụ:
x := 1;
with var x = 2 do begin
y := x+1;
x := 3;
end;

x1
x2
x 2, y 3
x 3, y 3
x 1, y 3 Ng  ca ngôn ng vc trình bày  b

Bảng ngữ nghĩa của ngôn ngữ với môi trường

(6) E [[E1=E2]] u s = (e1?T and e2?T) or (e1?Z and e2?Z) e1=e2, error
where ei = E [[Ei]] u s for i=1,2
(7) E [[I]] u s= d ? L s(d), d ? R d, error where d = u [[I]]
(8) E [[procedure C]] u s = C [[C]] u
(9) E [[(E)]] u s = E [[E]] u s
(10) D [[var I = E]] u s = e ? R and kL:s(k) = unused
(u[I e]), (u,error)
where e = E [[E]] u s
(11) D [[const I = E]] u s = e ? R (u[I e],s),(u,error) where e = E [[E]] u s
(12) C [[null] u s = s
(13) C [[I:=E]] u s = d ? L and e ? R s[d e], error
where d = u[[I]] and e = E [[E]] u s
(14) C [[call E]] u s = e ? P e(s), errorwhere e = E [[E]] u s
(15) C [[C1;C2]] u s = g ? S C [[C2]] u g, error where g = C [[C1]] u s
Báo cáo đề tài: Cú pháp và ngữ nghĩa trong ngôn ngữ lập trình

Trang 24 (16) C [[if E then C1 else C2]]s = E [[E]] u s C [[C1]] u s, C [[C2]] u s

(g?S 
(18) C [[with D do C]] u s = g ? S C [[C
(19) C [[begin C end]] u s = C [[C]]u s
(20) M [[program (I); C]]b = g?S and g(k)?B g(k), error
where g = C [[C]](u [I s[k 


and k is any location


u kin P2 gọi là yếu hơn P1 nếu P1=> P2. Tiu kin  c t ca phát biu
càng yu, ng a phát biu càng rõ.
Ví dụ: