Ðịnh nghĩa cú pháp chương trình

ðịnh nghĩa cú pháp chương trình 1 Cú pháp và ngữ nghĩa
Cú pháp của ngôn ngữ lập trình: cấu trúc hình thức của chương trình như thế nào? – Cú pháp ñược ñịnh nghĩa bằng một văn phạm hình thức 2
Ngữ nghĩa của ngôn ngữ lập trình: chương trình làm gì, hoạt ñộng như thế nào? – Ngữ nghĩa chương trình khó ñịnh nghĩa hơn cú pháp. Nội dung
Văn phạm và ví dụ về cây cú pháp
BNF và ñịnh nghĩa cây cú pháp
Xây dựng văn phạm 3
Cấu trúc câu và từ vựng
Các dạng văn phạm khác Văn phạm tiếng Anh Một câu là một cấu trúc: danh ngữ + ñộng từ + danh ngữ. Một danh ngữ là ... ::= ::= 4 Một ñộng từ là Một mạo từ là Một danh từ là ... ::= loves | hates|eats ::= a | the ::= dog | cat | rat Văn phạm hoạt ñộng như thế nào
Văn phạm là một tập hợp các qui tắc chỉ ra cách thức xác ñịnh một cây cú pháp
Cho là gốc của cây
Văn phạm xác ñịnh cách thức mà các nút 5 con có thể ñược thêm vào cây
Như vậy, qui tắc cho biết có thể thêm , , và , theo trật tự trên làm các nút con của ::= Cây cú pháp loves 6 the dog the cat Văn phạm ngôn ngữ lập trình Một biểu thức có thể là tổng của hai biểu ::= + | * | ( ) | a | b | c 7
thức, hoặc tích của hai biểu thức, hoặc một biểu thức trong cặp ngoặc ñơn
Hoặc có thể là một trong các biến a, b hay c Cây cú pháp ( ) * ((a+b)*c) 8 + ( ) a b c Tổng quan
Văn phạm và ví dụ cây cú pháp
BNF và ñịnh nghĩa cây cú pháp
Xây dựng văn phạm 9
Cấu trúc câu và từ vựng
Các dạng văn phạm khác ::= ::= Ký hiệu bắt ñầu Một luật sinh 10 ::= loves | hates|eats ::= a | the ::= dog | cat | rat tokens Các ký hiệu không kết thúc ðịnh nghĩa văn phạm BNF
Một văn phạm BNF gồm có 4 phần: – Mộ tập hợp các tokens – Một tập hợp các ký hiệu không kết thúc – Một ký hiệu bắt ñầu 11 – Một tập các luật sinh (productions) ðịnh nghĩa văn phạm BNF
Các tokens là những ñơn vị nhỏ nhất của cú pháp: – Token có thể là một chuỗi gồm một hay nhiều ký tự – Token là nguyên tố: không phân tách nhỏ hơn 12
Các ký hiệu không kết thúc: – Các ký hiệu không kết thúc là các chuỗi trong cặp ngoặc , chẳng hạn – Văn phạm xác ñịnh cách thức mở rộng các ký hiệu không kết thúc thành các token ðịnh nghĩa văn phạm BNF
Ký hiệu bắt ñầu là một ký hiệu không kết thúc ñặc biệt, dùng làm nút gốc của cây phân tích
Các luật sinh là các luật xây dựng cây cú pháp 13
Mỗi luật sinh có một phần bên trái, một bộ tách ::=, và một phần bên phải – Phần bên trái là một ñơn ký hiệu không kết thúc ðịnh nghĩa văn phạm BNF – Phần bên phải là một dãy, mỗi thành phần của dãy này có thể là một token hay một ký hiệu không kết thúc
Mỗi luật sinh xác ñịnh một khả năng ñể xây dựng cây cú pháp. 14 ðịnh nghĩa văn phạm BNF
Khi có nhiều hơn một luật sinh có cùng một phần bên trái giống nhau thì có thể dùng dạng thu gọn
Văn phạm BNF có thể ñặt phần bên trái, bộ tách ::=, và một danh sách các phần bên 15 phải – mỗi thành phần trong danh sách ñó cách nhau bởi ký hiệu | Ví dụ Chú ý rằng có 6 luật sinh trong văn phạm trên Văn phạm trên tương ñương với: ::= + | * | ( ) | a | b | c 16 ::= + ::= * ::= ( ) ::= a ::= b ::= c Empty
Ký hiệu không kết thúc ñặc biệt ñược dùng ñể chỉ ra là văn phạm không sản sinh bất cứ gì ở vị trí nó xuất hiện Ví dụ, văn phạm sau ñịnh nghĩa một cấu 17
trúc if-then với một phần else tùy chọn: ::= if then ::= else | Cây cú pháp
ðể xây dựng một cây cú pháp, thiết lập ký hiệu bắt ñầu ở nút gốc
Thêm các ký hiệu không kết thúc vào, dựa trên các luật sinh trong văn phạm 18
Kết thúc khi tất cả các nút lá là token
ðọc các nút lá từ trái sang phải, ñây chính là chuỗi phát sinh từ cây cú pháp Ứng dụng Vẽ cây phân tích cú pháp cho các chuỗi sau: ::= + | * | ( ) | a | b | c 19 a+b a*b+c (a+b) (a+(b)) ðịnh nghĩa ngôn ngữ
Văn phạm ñược dùng ñể ñịnh nghĩa cú pháp của các ngôn ngữ lập trình
Ngôn ngữ ñược ñịnh nghĩa bằng một văn phạm là một tập các chuỗi có thể phát sinh từ một cây cú pháp nào ñó của văn phạm 20 Nội dung
Văn phạm và ví dụ cây cú pháp
BNF và ñịnh nghĩa cây cú pháp
Xây dựng văn phạm 21
Cấu trúc câu và từ vựng
Các dạng văn phạm khác Xây dựng văn phạm
Ví dụ: các khai báo trong ngôn ngữ Java: tên kiểu, danh sách các biến cách nhau bởi dấu phẩy, và một dấu chấm phẩy 22
Mỗi biến có thể ñược theo sau bởi một bộ khởi tạo: float a; boolean a,b,c; int a=1, b, c=1+2; Ví dụ (tiếp theo)
Nếu chưa kể ñến bộ khởi tạo:
Các kiểu dữ liệu cơ bản: ::= ; 23 ::= boolean | byte | short | int | long | char | float | double ::= | , ::= | = Nội dung
Văn phạm và ví dụ cây cú pháp
BNF và ñịnh nghĩa cây cú pháp
Xây dựng văn phạm 24
Cấu trúc câu và từ vựng
Các dạng văn phạm khác Token
Các token là những mẫu văn bản trong chương trình mà chúng không thể ñược chia nhỏ hơn nữa
ðịnh danh (count), từ khóa (if), toán tử Chapter Two Modern Programming Languages 25 (==), hằng số (123.4), etc.
Chương trình máy tính là một dãy các ký tự
Làm thế nào một dãy các ký tự có thể phân tích thành các token? Cấu trúc từ vựng và cấu trúc câu
Văn phạm ñịnh nghĩa cấu trúc câu: chương trình ñược xây dựng như thế nào từ một chuỗi các token Văn phạm cũng ñịnh nghĩa cấu trúc từ 26
vựng: một tập tin văn bản ñược phân tách thành các token như thế nào? Một văn phạm cho cấu trúc từ vựng và cấu trúc câu
Theo quan ñiểm này, sử dụng một văn phạm chung cho cấu trúc câu và cấu trúc từ
Không hiệu quả trong thực tế: các khoảng trắng hay các ghi chú làm cho văn phạm 27 khó ñọc và rườm rà ::= if then ::= else | Hai văn phạm tách biệt
Thông thường, các ngôn ngữ sử dụng hai văn phạm tách biệt – Một văn phạm chỉ ra cách thức cấu trúc các token từ một văn bản các ký tự 28 – Một văn phạm chỉ ra cách xây dựng cây cú pháp từ một dãy các token ::= | ::= | | ::= | | ::= | | | Lưu ý
Các ngôn ngữ lập trình trước ñây thường không tách bạch cấu trúc từ vựng với cấu trúc câu Trong các thế hệ Fortran và Algol ñầu tiên, 29 – khoảng trắng có thể ở bất kỳ vị trí nào, ngay cả ở giữa một từ khóa – Các ngôn ngữ khác như PL/I cho phép các từ khóa ñược dùng làm các ñịnh danh Lưu ý
Một số ngôn ngữ có ñịnh dạng cố ñịnh cho cấu trúc từ vựng – theo các vị trí cột – Mỗi dòng một phát biểu – Một vài cột ñầu tiên dành cho nhãn của phát 30 biểu
Ví dụ: một vài thế hệ ñầu của Fortran, Cobol, và Basic
Hầu hết các ngôn ngữ lập trình hiện nay có ñịnh dạng tự do cho cấu trúc từ vựng Nội dung
Văn phạm và ví dụ cây cú pháp
BNF và ñịnh nghĩa cây cú pháp
Xây dựng văn phạm 31
Cấu trúc câu và từ vựng
Các dạng văn phạm khác Các dạng văn phạm khác
Các biến thể của BNF
Các biến thể của EBNF
Các sơ ñồ cú pháp 32 Các biến thể của BNF
Một số dùng → hay = thay vì ::=
Một số cho phép dùng cặp dấu nháy ñơn bao các tokens, ví dụ phân biệt ‘|’ như là một token với | như là meta-symbol 33 Các biến thể của BNF
Cú pháp bổ sung cho BNF: – {x} nghĩa là không hay lặp lại x nhiều lần – [x] có nghĩa x là tùy chọn (i.e. x | ) – () cho nhóm 34 – | chọn một trong số các chọn lựa – Cặp dấu ngoặc kép bao ký hiệu ñể phân biệt với các meta-symbols EBNF Examples ::= { ;} ::= if then [else ] ::= { ( | ) ;} 35
Các mở rộng của BNF ñược gọi là Extended BNF: EBNF
Có nhiều biến thể của BNF Các sơ ñồ cú pháp
Văn phạm EBNF
Một luật sinh ñơn giản là một chuỗi các ký hiệu kết thúc và không kết thúc: 36 if then elseexpr stmt stmt if-stmt ::= if then else ðường vòng 37 if then elseexpr stmt stmt if-stmt ::= if then [else ] Rẽ nhánh exp + exp exp * exp ::= + | * | ( ) | a | b | c 38 exp ( exp ) a b c Vòng lặp ::= {+ } 39 exp addend + Ví dụ WhileStatement: while ( Expression ) Statement DoStatement: do Statement while ( Expression ) ; 40 ForStatement: for ( ForInitopt ; Expressionopt ; ForUpdateopt) Statement [The Java™ Language Specification, James Gosling et. al.]