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 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.
Nội dung trích xuất từ tài liệu:
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) ...