21/1/2010
1
Bài 4
BNF v
à
sơ
đồ
cú
p
h
áp
1
BNF
và
sơ
đồ
cú
pháp
Công thức siêu ngữ Backus và các biến thể
Siêu ngữ(metalanguage ):Ngôn ngữsử
dụng các lệnh để mô tảngôn ngữkhác
BNF
(Backus
Naur
Form)
là
dạng
cú
2
BNF
(Backus
Naur
Form)
là
dạng
cú
pháp để mô tảcác ngôn ngữlậptrình
BNF đượcsửdụng rộng rãi để mô tảvăn
phạmcủa các ngôn ngữlập trình, tậplệnh
và các giao thứctruyền thông.
Các biến thể của công thức siêu
ngữ Backus
Ký pháp BNF là mộttậpcácluật,vếtrái
củamỗiluậtlàmộtcấu trúc cú pháp.
Tên củacấutrúccúphápđượcgọilàký
hiệu
không
kết
thúc
3
hiệu
không
kết
thúc
.
Các ký hiệu không kết thúc thường được
bao trong cặp <>.
Cáckýhiệukết thúc thường được phân
cách bằng cặp nháy đơnhoặc nháy kép
Công thức siêu ngữ Backus và
các biến thể
Mỗikýhiệu không kết thúc đượcđịnh
nghĩabằng một hay nhiềuluật.
Các luậtcódạng
4
N::=s
(N là ký hiệu không kếtthúc,slàmộtxâu
gồm 0 hay nhiềukýhiệukết thúc và không
kết thúc. Các luật có chung vếtrái được
phân cách bằng | )
21/1/2010
2
Ví dụ về BNF
<Số>::=’-’<Sốthập phân>|<sốthập phân>
<Sốthập phân>::=<Dãy chữsố>|<Dãy
chữsố>’.’<Dãy chữsố>
5
<Dãy chữsố>::=<Chữsố>|<Chữsố><Dãy
chữsố>
<Chữsố>::=’0’|’1’|’2’|’3’|’4’|’5’|’6’|’7’|’8’|’9’
EBNF
EBNF (Extended BNF ) đượcpháttriểntừký
pháp BNF. EBNF có ký pháp tương tựBNF
nhưng đượcđơngiảnhoábằng cách sửdụng
một
số
ký
hiệu
đặc
biệt
:
6
một
số
ký
hiệu
đặc
biệt
:
[] phần này là tuỳchọn(có hoặc không)
{} phầnnàycóthểlặplạimộtsốlầntuỳýhoặc
không xuấthiệnlầnnào(Nếulặplạimhaynlần
, dùng n hay m là chỉsốtrên hoặcdưới)
Không cần dùng ‘’ cho ký hiệukết thúc
So sánh BNF và EBNF
Ví dụ
Trong EBNF
<Lệnh
if>
::
=
IF
<Biểu
thức>
THEN
<Lệnh>
7
<Lệnh
if>
::
=
IF
<Biểu
thức>
THEN
<Lệnh>
[ELSE <Lệnh>]
Trong BNF
<Lệnh if>::= ‘IF’ <Biểuthức> ‘THEN’
<Lệnh>| ‘IF’ <Biểuthức> THEN <Lệnh>
‘ELSE’ <Lệnh>
Sơ đồ cú pháp
Là công cụđểmô tảcú pháp của ngôn
ngữlậptrìnhdướidạng đồ thị
8
Mỗisơđồcú pháp là mộtđồ thịđịnh
hướng vớilốivàovàlốiraxácđịnh.
Mỗisơđồcú pháp có một tên duy nhất
21/1/2010
3
Ví dụ một sơ đồ cú pháp
9
Sơ đồ cú pháp của KPL (Tổng thể CT)
1 0
Sơ đồ cú pháp của KPL (Khối)
1 1
Sơ đồ cú pháp của KPL
(tham số, hằng không dấu)
1 2
21/1/2010
4
Sơ đồ cú pháp của KPL (Khai
báo)
1 3
Sơ đồ cú pháp của KPL
(lệnh)
1 4
Sơ đồ cú pháp của KPL (biể
u
thức)
1 5
Sơ đồ cú pháp của KPL
(thừa số,điều kiện)
1 6
21/1/2010
5
Sơ đồ cú pháp của KPL(tên, số)
1 7