Bài giảng Xây dựng chương trình dịch: Bài 4 - BNF và sơ đồ cú pháp

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:23

Thêm vào BST

Báo xấu

24
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Xây dựng chương trình dịch: Bài 4 - BNF và sơ đồ cú pháp" cung cấp cho người học các kiến thức: siêu ngữ Backus và các biến thể; ký pháp BNF; so sánh BNF và EBNF; văn phạm KPL viết bằng BNF; sơ đồ cú pháp của KPL;... Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Xây dựng chương trình dịch: Bài 4 - BNF và sơ đồ cú pháp

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 92) ::= SB_LSEL SB_RSEL 14 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