Bài 4 BNF và sơ đồ cú pháp

1

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 siêu cú

pháp để mô tả các ngôn ngữ lập trình

• BNF được sử dụng rộng rãi để mô tả văn phạm của các ngôn ngữ lập trình, tập lệnh và các giao thức truyền thông.

2

Ký pháp BNF

• Ký pháp BNF là một tập các luật ,vế trái của mỗi luật

là một cấu trúc cú pháp.

• Tên của cấu trúc cú pháp được gọi là ký 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ác ký hiệu kết thúc thường được phân cách bằng cặp

nháy đơn hoặc nháy kép

3

Ký pháp BNF

• Mỗi ký hiệu không kết thúc được định nghĩa bằng một

hay nhiều luật. • Các luật có dạng

N::=s

(N là ký hiệu không kết thúc, s là một xâu gồm 0 hay nhiều ký hiệu kế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 | )

4

Ví dụ về BNF : văn phạm sản sinh các số thực

::= |

'.’ | '.’< dãy chữ số > | 'e’

::=  | ‘+’ | ‘-‘ ::= ‘0’ | ::= ‘1’ | ‘2’ | ‘3’ | ‘4’ | ‘5’ | ‘6’ | ‘7’ | ‘8’ | ‘9’ < dãy chữ số > ::=  | < dãy chữ số > ::= ‘0’ | ‘1’ | ‘2’ | ‘3’ | ‘4’ | ‘5’ | ‘6’ | ‘7’ | ‘8’ | ‘9’ Văn phạm này được viết bằng BNF, một công cụ rất phổ biến để biểu diễn cú pháp ngôn ngữ lập trình

5

EBNF

• EBNF (Extended BNF ) được phát triển từ ký pháp BNF. EBNF có ký pháp tương tự BNF nhưng được đơn giản hoá bằng cách sử dụng một số ký hiệu đặc biệt : [] phần này là tuỳ chọn(có hoặc không) {} phần này có thể lặp lại một số lần tuỳ ý hoặc không xuất hiện lần nào (Nếu lặp lại m hay n lần , dùng n hay m là chỉ số trên hoặc dưới) Không cần dùng ‘’ cho ký hiệu kết thúc

6

So sánh BNF và EBNF

Ví dụ • Trong EBNF

::= IF THEN [ELSE ] • Trong BNF

::= ‘IF’ ‘THEN’ | ‘IF’ ‘THEN’ ‘ELSE’

7

Ví dụ: Một đoạn văn phạm Python trên EBNF compound_stmt: if_stmt | while_stmt | for_stmt | try_stmt | with_stmt | funcdef | classdef | decorated | async_stmt async_stmt: 'async' (funcdef | with_stmt | for_stmt) if_stmt: 'if' test ':' suite ('elif' test ':' suite)* ['else' ':' suite] while_stmt: 'while' test ':' suite ['else' ':' suite] for_stmt: 'for' exprlist 'in' testlist ':' suite ['else' ':' suite] try_stmt: ('try' ':' suite

((except_clause ':' suite)+ ['else' ':' suite] ['finally' ':' suite] | 'finally' ':' suite))

with_stmt: 'with' with_item (',' with_item)* ':' suite with_item: test ['as' expr]

8

Văn phạm KPL viết bằng BNF

01) ::= KW_PROGRAM TK_IDENT SB_SEMICOLON SB_PERIOD

02) ::= KW_CONST 03) ::=

04) ::= KW_TYPE 05) ::=

06) ::= KW_VAR 07) ::=

08) ::= | 09) ::= KW_BEGIN KW_END

10) ::= 11) ::= e 12) ::= TK_IDENT SB_EQUAL SB_SEMICOLON

13) ::= 14) ::= e 15) ::= TK_IDENT SB_EQUAL SB_SEMICOLON

16) ::= 17) ::= e 18) ::= TK_IDENT SB_COLON SB_SEMICOLON

9

Văn phạm KPL viết bằng BNF

19) ::= s 20) ::= s 21) ::= e

22) ::= KW_FUNCTION TK_IDENT SB_COLON

SB_SEMICOLON

SB_SEMICOLON

23) ::= KW_PROCEDURE TK_IDENT SB_SEMICOLON

SB_SEMICOLON

24) ::= SB_LPAR SB_RPAR 25) ::= e

26) ::= SB_SEMICOLON 27) ::= e

28) ::= TK_IDENT SB_COLON 29) ::= KW_VAR TK_IDENT SB_COLON

30) ::= KW_INTEGER 31) ::= KW_CHAR 32) ::= TK_IDENT 33) ::= KW_ARRAY SB_LSEL TK_NUMBER SB_RSEL KW_OF

10

Văn phạm KPL viết bằng BNF

34) ::= KW_INTEGER 35) ::= KW_CHAR

36) ::= TK_NUMBER 37) ::= TK_IDENT 38) ::= TK_CHAR

40) ::= SB_PLUS 41) ::= SB_MINUS 42) ::= 43) ::= TK_CHAR

44) ::= TK_IDENT 45) ::= TK_NUMBER

46) ::=

47) ::= SB_SEMICOLON 48) ::= e

11

Văn phạm KPL viết bằng BNF

49) ::= 50) ::= 51) ::= 52) ::= 53) ::= 54) ::= 55) ::= e 56) ::= SB_ASSIGN 57) ::= TK_IDENT SB_ASSIGN

58) ::= KW_CALL TK_IDENT

59) ::= KW_BEGIN KW_END

60) ::= KW_IF KW_THEN

61) ::= KW_ELSE 62) ::= e

63) ::= KW_WHILE KW_DO 64) ::= KW_FOR TK_IDENT SB_ASSIGN KW_TO KW_DO

12

Văn phạm KPL viết bằng BNF

65) ::= SB_LPAR SB_RPAR 66) ::= e

67) ::= SB_COMMA 68) ::= e

68) ::=

69) ::= SB_EQ 70) ::= SB_NEQ 71) ::= SB_LE 72) ::= SB_LT 73) ::= SB_GE 74) ::= SB_GT

13

Văn phạm KPL viết bằng BNF

75) ::= SB_PLUS 76) ::= SB_MINUS 77) ::=

78) ::=

79) ::= SB_PLUS 80) ::= SB_MINUS 81) ::= e

82) ::=

83) ::= SB_TIMES 84) ::= SB_SLASH 85) ::= e 86) ::= 87) ::= 88) ::= 89) ::= SB_LPAR SB_RPAR

90) ::= TK_IDENT 91) ::= TK_IDENT

14 92) ::= SB_LSEL SB_RSEL 93) ::= e

Sơ đồ cú pháp

• Là công cụ để mô tả cú pháp của ngôn ngữ lập

trình dưới dạng đồ thị

• Mỗi sơ đồ cú pháp là một đồ thị định hướng với

lối vào và lối ra xác định.

• Mỗi sơ đồ cú pháp có một tên duy nhất

15

Ví dụ một sơ đồ cú pháp

16

Sơ đồ cú pháp của KPL (Tổng thể CT)

17

Sơ đồ cú pháp của KPL (Khối)

18

Sơ đồ cú pháp của KPL (tham số, hằng không dấu)

19

Sơ đồ cú pháp của KPL (Khai báo)

20

Sơ đồ cú pháp của KPL (lệnh)

21

Sơ đồ cú pháp của KPL (biểu thức)

22

Sơ đồ cú pháp của KPL (thừa số,điều kiện)

23