Trong bài này, bạn sẽ học về các cấu trúc ngôn ngữ (language constructs) của ngôn ngữ lập trình C. Các cấu trúc này là các cấu trúc cơ bản của lập trình cấu trúc (structural programming): cấu trúc if-then-else, vòng lặp for, vòng lặp while, do-while, ... Trước khi trình bày các cấu trúc ngôn ngữ của ngôn ngữ C, ta sẽ tìm hiểu định nghĩa tổng quát của ngôn ngữ, ngôn ngữ lập trình và cấu trúc của ngôn ngữ lập trình. Phần định nghĩa tổng quát có thể khó hiểu ở lần đầu mới đọc, nhưng khi bạn đã hiểu bạn có thể lý giải các cấu trúc của tất cả các ngôn ngữ lập trình, không chỉ riêng ngôn ngữ C.
1. Ngôn ngữ và văn phạm:
1.1. Ngôn ngữ là gì?
Ngôn ngữ (language) là một tập hợp các câu (sentences), mỗi câu được cấu tạo từ một tập hợp các từ (tokens, words). Ví dụ, ngôn ngữ Tiếng Việt là một ngôn ngữ (ngôn ngữ con người, hay gọi là ngôn ngữ tự nhiên); trong Tiếng Việt, ta có các tiếng (morpheme, ví dụ: "lụng"), một hay nhiều tiếng làm thành từ (word, ví dụ: "làm lụng"), các từ ghép với nhau theo một quy tắc nào đó tạo thành câu
. Tập hợp các từ tạo thành ngôn ngữ gọi là "bảng chữ cái" (alphabet) của ngôn ngữ đó (chú ý: định nghĩa bảng chữ cái ở đây khác với bảng chữ cái a,b,c thông thường).
Ngôn ngữ được chia ra làm 2 loại chính: ngôn ngữ tự nhiên (natural language) và ngôn ngữ hình thức (formal language). Ngôn ngữ tự nhiên ví dụ như Tiếng Việt, Tiếng Anh, ... Ngôn ngữ hình thức ví dụ như ngôn ngữ lập trình C, ngôn ngữ lập trình Pascal, hay ngôn ngữ đánh dấu siêu văn bản (HTML)...
1.2. Văn phạm là gì?
Ta đã biết ở phần trên, ngôn ngữ là tập hợp các câu, mỗi câu lại được cấu thành bởi các từ theo một tập hợp quy tắc nhất định. Tập hợp quy tắc đó gọi là văn phạm (grammar) hay cú pháp (syntax) của ngôn ngữ.
Ví dụ, một tập hợp nhỏ các quy tắc trong tiếng Anh là:
1.1. Ngôn ngữ là gì?
Ngôn ngữ (language) là một tập hợp các câu (sentences), mỗi câu được cấu tạo từ một tập hợp các từ (tokens, words). Ví dụ, ngôn ngữ Tiếng Việt là một ngôn ngữ (ngôn ngữ con người, hay gọi là ngôn ngữ tự nhiên); trong Tiếng Việt, ta có các tiếng (morpheme, ví dụ: "lụng"), một hay nhiều tiếng làm thành từ (word, ví dụ: "làm lụng"), các từ ghép với nhau theo một quy tắc nào đó tạo thành câu
. Tập hợp các từ tạo thành ngôn ngữ gọi là "bảng chữ cái" (alphabet) của ngôn ngữ đó (chú ý: định nghĩa bảng chữ cái ở đây khác với bảng chữ cái a,b,c thông thường).
Ngôn ngữ được chia ra làm 2 loại chính: ngôn ngữ tự nhiên (natural language) và ngôn ngữ hình thức (formal language). Ngôn ngữ tự nhiên ví dụ như Tiếng Việt, Tiếng Anh, ... Ngôn ngữ hình thức ví dụ như ngôn ngữ lập trình C, ngôn ngữ lập trình Pascal, hay ngôn ngữ đánh dấu siêu văn bản (HTML)...
1.2. Văn phạm là gì?
Ta đã biết ở phần trên, ngôn ngữ là tập hợp các câu, mỗi câu lại được cấu thành bởi các từ theo một tập hợp quy tắc nhất định. Tập hợp quy tắc đó gọi là văn phạm (grammar) hay cú pháp (syntax) của ngôn ngữ.
Ví dụ, một tập hợp nhỏ các quy tắc trong tiếng Anh là:
(2) NP -> N
(3) NP -> Det N
(4) NP -> N PP
(5) VP -> V NP
(6) VP -> VP PP
(7) PP -> P NP
(8) Det -> a
(9) N -> John
(10) N -> Mary
(11) N -> telescope
(12) V -> saw
(13) P -> with
trong đó, S là Sentence, N: noun, NP: noun phrase, V: verb, VP: verp phrase, PP: preposition phrase, P: preposition, Det: determiner
Các quy tắc trên được hiểu như sau: ký hiệu phía bên trái mũi tên có thể được thay thế bởi dãy ký hiệu phía bên phải. "S -> NP VP" có nghĩa là câu (sentence) được cấu tạo bởi cụm danh từ (noun phrase) và cụm động từ (verb phrase). Cụm danh từ (NP) lại được cấu tạo bởi Determiner và Noun (ví dụ "the dog"), ...
Các quy tắc trên gọi là quy tắc sinh của văn phạm (production rule). Dựa vào quy tắc sinh, ta có thể xét xem một câu có đúng ngữ pháp hay không. Ví dụ, câu "John saw Mary with a telescope" là một câu đúng, vì ta có thể sinh ra nó từ ký hiệu S (sentence) và áp dụng các rule (1), (2), (5), (4), ... như hình vẽ dưới đây:
Các quy tắc trên được hiểu như sau: ký hiệu phía bên trái mũi tên có thể được thay thế bởi dãy ký hiệu phía bên phải. "S -> NP VP" có nghĩa là câu (sentence) được cấu tạo bởi cụm danh từ (noun phrase) và cụm động từ (verb phrase). Cụm danh từ (NP) lại được cấu tạo bởi Determiner và Noun (ví dụ "the dog"), ...
Các quy tắc trên gọi là quy tắc sinh của văn phạm (production rule). Dựa vào quy tắc sinh, ta có thể xét xem một câu có đúng ngữ pháp hay không. Ví dụ, câu "John saw Mary with a telescope" là một câu đúng, vì ta có thể sinh ra nó từ ký hiệu S (sentence) và áp dụng các rule (1), (2), (5), (4), ... như hình vẽ dưới đây:
Ngược lại, câu "John Mary telescope saw" không phải là một câu đúng (theo tập quy tắc sinh ở trên) vì câu này không thể được dẫn ra từ ký hiệu S (sentence).
1.3. Cây cú pháp (syntax tree) :
Cây cú pháp biểu diễn cách dẫn xuất ra câu bằng cách áp dụng các quy tắc sinh của văn phạm. Hình vẽ trên chính là một cây cú pháp cho câu "John saw Mary with a telescope".
1.4. Ngữ nghĩa (semantics):
Với một ngôn ngữ, ta thường chú ý đến 3 khía cạnh của nó, đó là cú pháp (syntactics) hay văn phạm (ngữ pháp), ngữ nghĩa (semantics) và cách dùng (pragmatics).
Ngữ nghĩa của ngôn ngữ quy định cách hiểu ý nghĩa của ngôn ngữ đó. Nếu chỉ biết cú pháp mà không hiểu ý nghĩa của ngôn ngữ thì ta không thể dùng ngôn ngữ đó. Ví dụ, bạn có thể sửa câu "I be a student" thành cú pháp đúng là "I am a student" nhưng bạn không hiểu ý nghĩa của nó là gì nếu không biết ý nghĩa của từ "student".
Các ngôn ngữ hình thức thường cố gắng quy định rõ ràng ý nghĩa của nó. Ngôn ngữ lập trình C cũng vậy, nó quy định ý nghĩa của các câu (lệnh) rất rõ ràng. Việc quy định ý nghĩa cho các ngôn ngữ tự nhiên rất phức tạp vì nhiều khi ý nghĩa của câu còn tùy thuộc vào ngữ cảnh (context).
1.5. Văn phạm phi ngữ cảnh (context free grammar) và BNF:
Văn phạm phi ngữ cảnh là một loại văn phạm có các quy tắc sinh thành (production rules) kiểu như sau: A -> B1B2...Bn. Ở bên trái của dấu mũi tên chỉ có một ký hiệu duy nhất, ở bên phải có thể có một hoặc nhiều ký hiệu. Các ký hiệu có mặt ở bên trái của một rule được gọi là ký hiệu không kết thúc (non terminal symbol), các ký còn lại là các ký hiệu kết thúc (terminal). Ví dụ, tập quy tắc ở phần (1.2) là một văn phạm phi ngữ cảnh, các ký hiệu không kết thúc gồm S, NP, VP, N, V, PP, P, Det, các ký hiệu kết thúc gồm: a, John, Mary, telescope, saw, with. Các câu chỉ bao gồm các ký hiệu kết thúc (ví dụ: John saw Mary with a telescope).
BNF (Backus Naur Form) là một dạng công thức để ký hiệu quy tắc sinh thành của văn phạm phi ngữ cảnh. Nó bao gồm ký hiệu không kết thúc ở bên trái, dấu :: (tương ứng với dấu mũi tên) ở ví dụ trong phần (1.2) và các ký hiệu ở bên phải. Ví dụ,
S ::= NP VP
là một quy tắc viết theo kiểu BNF.
Để thuận tiện cho việc ký hiệu, ta quy ước dùng các ký hiệu như sau:
1.3. Cây cú pháp (syntax tree) :
Cây cú pháp biểu diễn cách dẫn xuất ra câu bằng cách áp dụng các quy tắc sinh của văn phạm. Hình vẽ trên chính là một cây cú pháp cho câu "John saw Mary with a telescope".
1.4. Ngữ nghĩa (semantics):
Với một ngôn ngữ, ta thường chú ý đến 3 khía cạnh của nó, đó là cú pháp (syntactics) hay văn phạm (ngữ pháp), ngữ nghĩa (semantics) và cách dùng (pragmatics).
Ngữ nghĩa của ngôn ngữ quy định cách hiểu ý nghĩa của ngôn ngữ đó. Nếu chỉ biết cú pháp mà không hiểu ý nghĩa của ngôn ngữ thì ta không thể dùng ngôn ngữ đó. Ví dụ, bạn có thể sửa câu "I be a student" thành cú pháp đúng là "I am a student" nhưng bạn không hiểu ý nghĩa của nó là gì nếu không biết ý nghĩa của từ "student".
Các ngôn ngữ hình thức thường cố gắng quy định rõ ràng ý nghĩa của nó. Ngôn ngữ lập trình C cũng vậy, nó quy định ý nghĩa của các câu (lệnh) rất rõ ràng. Việc quy định ý nghĩa cho các ngôn ngữ tự nhiên rất phức tạp vì nhiều khi ý nghĩa của câu còn tùy thuộc vào ngữ cảnh (context).
1.5. Văn phạm phi ngữ cảnh (context free grammar) và BNF:
Văn phạm phi ngữ cảnh là một loại văn phạm có các quy tắc sinh thành (production rules) kiểu như sau: A -> B1B2...Bn. Ở bên trái của dấu mũi tên chỉ có một ký hiệu duy nhất, ở bên phải có thể có một hoặc nhiều ký hiệu. Các ký hiệu có mặt ở bên trái của một rule được gọi là ký hiệu không kết thúc (non terminal symbol), các ký còn lại là các ký hiệu kết thúc (terminal). Ví dụ, tập quy tắc ở phần (1.2) là một văn phạm phi ngữ cảnh, các ký hiệu không kết thúc gồm S, NP, VP, N, V, PP, P, Det, các ký hiệu kết thúc gồm: a, John, Mary, telescope, saw, with. Các câu chỉ bao gồm các ký hiệu kết thúc (ví dụ: John saw Mary with a telescope).
BNF (Backus Naur Form) là một dạng công thức để ký hiệu quy tắc sinh thành của văn phạm phi ngữ cảnh. Nó bao gồm ký hiệu không kết thúc ở bên trái, dấu :: (tương ứng với dấu mũi tên) ở ví dụ trong phần (1.2) và các ký hiệu ở bên phải. Ví dụ,
S ::= NP VP
là một quy tắc viết theo kiểu BNF.
Để thuận tiện cho việc ký hiệu, ta quy ước dùng các ký hiệu như sau:
- * (dấu sao) có nghĩa là "lặp lại 0 lần trở lên" (ví dụ, N* = <empty>, N, NN, NNN, NNNNN, ....; (ab)* = abababab, ab, <empty>)
- ? (dấu chấm hỏi) có nghĩa là "có thể có hoặc không" (ví dụ a? = <empty> hay a, (abc)? = empty hay abc)
- | (dấu sổ đứng) có nghĩa là hoặc (lựa chọn các trường hợp) (ví dụ: (a|b|c) = a hay b hay c; (a|bc)* có thể là abcbcabc hay aaaabcbcbcbc hay abcabc
- % (dấu phần trăm) có nghĩa là một list (danh sách, dãy) phân cách bởi dấu phảy "," (ví dụ: a% = a | a, a | a, a, a ...)
Ví dụ, sau đây là 1 quy tắc BNF của ngôn ngữ C:
assignment-expression ::= ( unary-expression ("=" | "*=" | "/=" | "%=" | "+=" | "-=") )* conditional-expression
Quy tắc BNF trên có nghĩa là: biểu thức gán trong C là biểu thức đơn (unary-expression) và 1 trong các toán tử gán (=, +=, -=, ...) lặp đi lặp lại 0 lần trở lên theo sau là một biểu thức điều kiện.
Các câu văn sau đây thỏa mãn quy tắc sinh trên (tức là có thể được sinh ra bằng cách áp dụng quy tắc trên):
x = 1 (unary-expression: x, dấu =, và conditional-expression: 1)
5 + 6 (vì lặp đi lặp lại 0 lần trở lên của unary-expression và toán tử gán nên ta có thể cho lặp lại 0 lần (tức empty) và đến ngay conditional-expression: 5 + 6)
x += y = 5 + 6 (bạn thử giải thích xem tại sao câu này lại có thể sinh từ luật trên?).
assignment-expression ::= ( unary-expression ("=" | "*=" | "/=" | "%=" | "+=" | "-=") )* conditional-expression
Quy tắc BNF trên có nghĩa là: biểu thức gán trong C là biểu thức đơn (unary-expression) và 1 trong các toán tử gán (=, +=, -=, ...) lặp đi lặp lại 0 lần trở lên theo sau là một biểu thức điều kiện.
Các câu văn sau đây thỏa mãn quy tắc sinh trên (tức là có thể được sinh ra bằng cách áp dụng quy tắc trên):
x = 1 (unary-expression: x, dấu =, và conditional-expression: 1)
5 + 6 (vì lặp đi lặp lại 0 lần trở lên của unary-expression và toán tử gán nên ta có thể cho lặp lại 0 lần (tức empty) và đến ngay conditional-expression: 5 + 6)
x += y = 5 + 6 (bạn thử giải thích xem tại sao câu này lại có thể sinh từ luật trên?).
2.Văn phạm của ngôn ngữ lập trình C và cách quy định ý nghĩa:
2.1. Khái quát về văn phạm và ngữ nghĩa của C:
Như bạn đã biết, ngôn ngữ lập trình C là một ngôn ngữ hình thức (formal language), không phải là ngôn ngữ tự nhiên (natural language). Văn phạm của ngôn ngữ C vì thế đơn giản hơn rất nhiều so với ngữ pháp tiếng Anh hay tiếng Việt. Quan trọng hơn nữa, văn phạm ấy được quy định rõ ràng bởi người thiết kế ngôn ngữ lập trình C và ý nghĩa của ngôn ngữ cũng được quy định một cách rõ ràng, không nhập nhằng (unambiguous).
Văn phạm của ngôn ngữ C là một dạng của văn phạm phi ngữ cảnh (context free grammar, CFG). Một khi bạn nắm được văn phạm của ngôn ngữ C, bạn có thể viết các chương trình C một cách đúng ngữ pháp (tức là trình biên dịch sẽ cho qua, không báo lỗi khi biên dịch). Tuy nhiên, bạn cần phải hiểu ý nghĩa của chương trình bạn viết, chính vì thế, bạn phải hiểu ngữ nghĩa của ngôn ngữ C.
Có nhiều cách để quy định ý nghĩa của một ngôn ngữ. Trong bài này chúng ta sẽ chỉ đề cập đến "ý nghĩa thao tác" (operational semantics) của ngôn ngữ lập trình C.
Để quy định ý nghĩa của ngôn ngữ lập trình C, ta giả sử trạng thái của bộ nhớ là M (tức toàn bộ bộ nhớ của máy tính hiện thời, bạn có thể xem M như là một ánh xạ từ tập địa chỉ bộ nhớ vào nội dung được lưu ở địa chỉ đó). Ở một trạng thái bộ nhớ M nhất định, ta có thể đánh giá (evaluate) xem một biểu thức có giá trị bằng bao nhiêu. Ví dụ, ở trạng thái M1 { x = 2, y = 6 }, ta có thể evaluate giá trị của biểu thức (x + 1) là 3 (hãy nhớ lại rằng, biến số là sự trừu tượng hóa của bộ nhớ, và trạng thái bộ nhớ là ánh xạ từ địa chỉ vào giá trị (kiểu x = 2)). Tuy nhiên, vì sao (x + 1) lại được evaluate thành 3 ở trạng thái bộ nhớ M1 đó?. Bạn có thể đánh giá ngay lập tức x + 1 = 3 vì bạn biết ý nghĩa của phép cộng trong Toán học là lấy 2 toán hạng cộng vào với nhau, và bạn cũng biết khi x cộng với 1 thì cho kết quả là số tự nhiên đứng ngay sau x trong dãy số tự nhiên. Vì x = 2 nên bạn suy ra x + 1 = 3, và bạn đánh giá biểu thức x + 1 bằng 3.
Rất tiếc, với các phép toán phức tạp hơn (ví dụ "(*pX >> 5) % y++") thì bạn không thể hiểu ngay được ý nghĩa của nó là gì. Chính vì thế người thiết kế ngôn ngữ C phải quy định ý nghĩa rõ ràng của các câu lệnh trong ngôn ngữ C dựa trên các quy định ý nghĩa đã biết sẵn trong Toán học (ví dụ quy định toán tử cộng (+) của C có ý nghĩa giống như phép cộng trong Toán học).
Sau khi có trạng thái của bộ nhớ, ta sẽ quy định các quy tắc suy luận (inference rule) để suy luận xem từ trạng thái ban đầu, sau khi thi hành (execute) một lệnh ta sẽ đến được trạng thái nào và giá trị của biểu thức cần đánh giá là bao nhiêu?. Ví dụ,
<x, M1> --> n0 <y, M1> --> n1
-----------------------------------------------------------------
<x + y, M1> --> n0 plus n1
Quy tắc suy luận có 2 phần: giả thiết là kết luận. Giả thiết được viết ở phía trên, kết luận viết ở phía dưới, phân cách nhau bởi dòng kẻ ngang. Quy tắc ví dụ trên có thể hiểu như sau: nếu ở trạng thái bộ nhớ M1, biến số x được evaluate bằng số n0 (lưu ý: n0 là một số tự nhiên trong Toán học, đã biết rõ ý nghĩa), biến số y được evaluate bằng n1 thì ở trạng thái bộ nhớ đó, biểu thức (x+y) sẽ được evaluate bằng tổng (trong Toán học) của 2 số n0 và n1. Sở dĩ phải viết "n0 plus n1" là do chúng ta đang đi định nghĩa toán tử cộng (+) trong ngôn ngữ C, nếu ta sử dụng "n0 + n1" sẽ rất dễ gây nhầm lẫn: không biết đâu là toán tử của ngôn ngữ C (cái mà ta chưa biết ý nghĩa, và ta đang phải đi quy định) với toán tử cộng (phép cộng) trong Toán học (cái mà ta đã biết rõ ý nghĩa).
2.2. Cấu trúc ngôn ngữ:
Cấu trúc ngôn ngữ (language construct) của một ngôn ngữ lập trình là các câu văn (câu lệnh) mà ngôn ngữ đó hiểu. Ví dụ, ngôn ngữ lập trình C cho phép bạn sử dụng câu lệnh if-then-else, khi đó ta nói if-then-else là một language construct của C.
Cấu trúc ngôn ngữ có 2 khía cạnh quan trọng, đó là cú pháp (syntax) và ý nghĩa (semantics). Biết được cú pháp của một cấu trúc ngôn ngữ, bạn có thể viết chương trình chứa cấu trúc đó một cách đúng cú pháp, không bị lỗi biên dịch. Hiểu được ý nghĩa của cấu trúc bạn sẽ biết cách dùng cấu trúc đó vào các trường hợp cụ thể.
2.3. Cú pháp của biểu thức trong ngôn ngữ lập trình C:
Biểu thức là một khái niệm quan trọng của bất kỳ ngôn ngữ lập trình nào. Bạn tính toán các công thức chủ yếu dựa trên định nghĩa biểu thức. Trong các bài trước, bạn đã có khái niệm thế nào là biểu thức của ngôn ngữ C (hãy đọc lại bài 2b nếu bạn quên). Trong mục này, chúng ta sẽ hiểu được định nghĩa biểu thức trong ngôn ngữ C.
a) Cú pháp của biểu thức:
expression ::= assignment-expression%
assignment-expression ::= ( unary-expression ( "=" | "*=" | "/=" | "%=" | "+=" | "-=" | "<<=" | ">>=" | "&=" | "^=" | "|=" ) )* conditional-expression
conditional-expression ::= logical-OR-expression ( "?" expression ":" conditional-expression )?
constant-expression ::= conditional-expression
logical-OR-expression ::= logical-AND-expression ( "||" logical-AND-expression )*
....
Còn rất nhiều rule để định nghĩa toàn bộ cú pháp của biểu thức, bạn có thể tìm thấy các rule đó ở đây: expr.html
Có quá nhiều rule và quá khó hiểu phải không?. Nếu bạn nhìn vào các rule và không hiểu ý nghĩa của các thành phần của nó thì rất khó hiểu, nhưng một khi ta đã hiểu ý nghĩa các thành phần thì có thể hiểu được các rule. Ví dụ, rule "logical-OR-expression ::= logical-AND-expression ( "||" logical-AND-expression )* nói rằng: biểu thức hoặc (logic) có thể là một biểu thức và (logical AND) hay cũng có thể là hai hay nhiều biểu thức và kết hợp bởi toán tử "||".
Đến đây chắc bạn đã hiểu phần nào ý nghĩa của rule trên: (x && y) là 1 logical-AND-expression, vì thế nó cũng là 1 logical-OR-expression. (z && t) là một logical-AND-expression, vì thế ((x && y) || (z && t)) là một logical-OR-expression.
Để hiểu tại sao (x && y) lại là 1 logical-AND-expression, bạn cần phải đi tiếp sâu xuống các rule sau (rule cho AND, unary, cast, ...).
Dựa vào tập rule này, ta có thể chứng minh "1" là một expression. Thật vậy, hãy nhìn từ rule cuối cùng trong file expr.html, bạn thấy 1 là một constant, vì nó là integer-constant, nhìn tiếp rule gần cuối bạn nhận ra 1 sẽ quy về là một postfix-expression vì trong định nghĩa của postfix-expression có trường hợp chỉ có 1 constant đứng một mình. Sau đó ta tiếp tục áp dụng các rule ở phía trên để lần lượt suy ra 1 là một unary-expression, cast-expression, ... và cuối cùng là conditional-expression và expression!.
Như vậy, sau một hồi suy luận ta đã chứng minh được "1" là một biểu thức trong C.
Như vậy ta có thể biết được một dòng chữ bất kỳ có phải là 1 expression của C hay không.
b) Ý nghĩa (ngữ nghĩa) của biểu thức:
Việc định nghĩa ý nghĩa của biểu thức chủ yếu là ánh xạ ý nghĩa các toán tử của C thành ý nghĩa Toán học (giống như ví dụ về toán tử cộng ở trên).
Ví dụ, cho đến bây giờ bạn chưa biết toán tử << (dịch trái) có nghĩa là gì, ta có thể định nghĩa ý nghĩa toán tử đó như sau:
<x, M> --> n0
-----------------------------------------------------------------------------------------------------------------------------------------
<(x << k), M > --> số n1 sao cho các bit của n1 là các bit của n0 dịch sang bên trái k vị trí, điền 0 vào cuối trong hệ nhị phân (tức n1 = x * 2k)
Ví dụ, trong hệ nhị phân số 3 biểu diễn là 11, khi dịch đi 1 vị trí sang trái nó thành 110, là số 6. Trong C, (3 << 1)
* Ý nghĩa của biểu thức gán: x = A
Trước hết, ta định nghĩa "thay thế" (substitution) [x/A] của một trạng thái bộ nhớ M là trạng thái bộ nhớ M1, trong đó giá trị của ô nhớ đại diện cho x là A (tức x được thay thế bởi A). Ta viết như sau:
2.1. Khái quát về văn phạm và ngữ nghĩa của C:
Như bạn đã biết, ngôn ngữ lập trình C là một ngôn ngữ hình thức (formal language), không phải là ngôn ngữ tự nhiên (natural language). Văn phạm của ngôn ngữ C vì thế đơn giản hơn rất nhiều so với ngữ pháp tiếng Anh hay tiếng Việt. Quan trọng hơn nữa, văn phạm ấy được quy định rõ ràng bởi người thiết kế ngôn ngữ lập trình C và ý nghĩa của ngôn ngữ cũng được quy định một cách rõ ràng, không nhập nhằng (unambiguous).
Văn phạm của ngôn ngữ C là một dạng của văn phạm phi ngữ cảnh (context free grammar, CFG). Một khi bạn nắm được văn phạm của ngôn ngữ C, bạn có thể viết các chương trình C một cách đúng ngữ pháp (tức là trình biên dịch sẽ cho qua, không báo lỗi khi biên dịch). Tuy nhiên, bạn cần phải hiểu ý nghĩa của chương trình bạn viết, chính vì thế, bạn phải hiểu ngữ nghĩa của ngôn ngữ C.
Có nhiều cách để quy định ý nghĩa của một ngôn ngữ. Trong bài này chúng ta sẽ chỉ đề cập đến "ý nghĩa thao tác" (operational semantics) của ngôn ngữ lập trình C.
Để quy định ý nghĩa của ngôn ngữ lập trình C, ta giả sử trạng thái của bộ nhớ là M (tức toàn bộ bộ nhớ của máy tính hiện thời, bạn có thể xem M như là một ánh xạ từ tập địa chỉ bộ nhớ vào nội dung được lưu ở địa chỉ đó). Ở một trạng thái bộ nhớ M nhất định, ta có thể đánh giá (evaluate) xem một biểu thức có giá trị bằng bao nhiêu. Ví dụ, ở trạng thái M1 { x = 2, y = 6 }, ta có thể evaluate giá trị của biểu thức (x + 1) là 3 (hãy nhớ lại rằng, biến số là sự trừu tượng hóa của bộ nhớ, và trạng thái bộ nhớ là ánh xạ từ địa chỉ vào giá trị (kiểu x = 2)). Tuy nhiên, vì sao (x + 1) lại được evaluate thành 3 ở trạng thái bộ nhớ M1 đó?. Bạn có thể đánh giá ngay lập tức x + 1 = 3 vì bạn biết ý nghĩa của phép cộng trong Toán học là lấy 2 toán hạng cộng vào với nhau, và bạn cũng biết khi x cộng với 1 thì cho kết quả là số tự nhiên đứng ngay sau x trong dãy số tự nhiên. Vì x = 2 nên bạn suy ra x + 1 = 3, và bạn đánh giá biểu thức x + 1 bằng 3.
Rất tiếc, với các phép toán phức tạp hơn (ví dụ "(*pX >> 5) % y++") thì bạn không thể hiểu ngay được ý nghĩa của nó là gì. Chính vì thế người thiết kế ngôn ngữ C phải quy định ý nghĩa rõ ràng của các câu lệnh trong ngôn ngữ C dựa trên các quy định ý nghĩa đã biết sẵn trong Toán học (ví dụ quy định toán tử cộng (+) của C có ý nghĩa giống như phép cộng trong Toán học).
Sau khi có trạng thái của bộ nhớ, ta sẽ quy định các quy tắc suy luận (inference rule) để suy luận xem từ trạng thái ban đầu, sau khi thi hành (execute) một lệnh ta sẽ đến được trạng thái nào và giá trị của biểu thức cần đánh giá là bao nhiêu?. Ví dụ,
<x, M1> --> n0 <y, M1> --> n1
-----------------------------------------------------------------
<x + y, M1> --> n0 plus n1
Quy tắc suy luận có 2 phần: giả thiết là kết luận. Giả thiết được viết ở phía trên, kết luận viết ở phía dưới, phân cách nhau bởi dòng kẻ ngang. Quy tắc ví dụ trên có thể hiểu như sau: nếu ở trạng thái bộ nhớ M1, biến số x được evaluate bằng số n0 (lưu ý: n0 là một số tự nhiên trong Toán học, đã biết rõ ý nghĩa), biến số y được evaluate bằng n1 thì ở trạng thái bộ nhớ đó, biểu thức (x+y) sẽ được evaluate bằng tổng (trong Toán học) của 2 số n0 và n1. Sở dĩ phải viết "n0 plus n1" là do chúng ta đang đi định nghĩa toán tử cộng (+) trong ngôn ngữ C, nếu ta sử dụng "n0 + n1" sẽ rất dễ gây nhầm lẫn: không biết đâu là toán tử của ngôn ngữ C (cái mà ta chưa biết ý nghĩa, và ta đang phải đi quy định) với toán tử cộng (phép cộng) trong Toán học (cái mà ta đã biết rõ ý nghĩa).
2.2. Cấu trúc ngôn ngữ:
Cấu trúc ngôn ngữ (language construct) của một ngôn ngữ lập trình là các câu văn (câu lệnh) mà ngôn ngữ đó hiểu. Ví dụ, ngôn ngữ lập trình C cho phép bạn sử dụng câu lệnh if-then-else, khi đó ta nói if-then-else là một language construct của C.
Cấu trúc ngôn ngữ có 2 khía cạnh quan trọng, đó là cú pháp (syntax) và ý nghĩa (semantics). Biết được cú pháp của một cấu trúc ngôn ngữ, bạn có thể viết chương trình chứa cấu trúc đó một cách đúng cú pháp, không bị lỗi biên dịch. Hiểu được ý nghĩa của cấu trúc bạn sẽ biết cách dùng cấu trúc đó vào các trường hợp cụ thể.
2.3. Cú pháp của biểu thức trong ngôn ngữ lập trình C:
Biểu thức là một khái niệm quan trọng của bất kỳ ngôn ngữ lập trình nào. Bạn tính toán các công thức chủ yếu dựa trên định nghĩa biểu thức. Trong các bài trước, bạn đã có khái niệm thế nào là biểu thức của ngôn ngữ C (hãy đọc lại bài 2b nếu bạn quên). Trong mục này, chúng ta sẽ hiểu được định nghĩa biểu thức trong ngôn ngữ C.
a) Cú pháp của biểu thức:
expression ::= assignment-expression%
assignment-expression ::= ( unary-expression ( "=" | "*=" | "/=" | "%=" | "+=" | "-=" | "<<=" | ">>=" | "&=" | "^=" | "|=" ) )* conditional-expression
conditional-expression ::= logical-OR-expression ( "?" expression ":" conditional-expression )?
constant-expression ::= conditional-expression
logical-OR-expression ::= logical-AND-expression ( "||" logical-AND-expression )*
....
Còn rất nhiều rule để định nghĩa toàn bộ cú pháp của biểu thức, bạn có thể tìm thấy các rule đó ở đây: expr.html
Có quá nhiều rule và quá khó hiểu phải không?. Nếu bạn nhìn vào các rule và không hiểu ý nghĩa của các thành phần của nó thì rất khó hiểu, nhưng một khi ta đã hiểu ý nghĩa các thành phần thì có thể hiểu được các rule. Ví dụ, rule "logical-OR-expression ::= logical-AND-expression ( "||" logical-AND-expression )* nói rằng: biểu thức hoặc (logic) có thể là một biểu thức và (logical AND) hay cũng có thể là hai hay nhiều biểu thức và kết hợp bởi toán tử "||".
Đến đây chắc bạn đã hiểu phần nào ý nghĩa của rule trên: (x && y) là 1 logical-AND-expression, vì thế nó cũng là 1 logical-OR-expression. (z && t) là một logical-AND-expression, vì thế ((x && y) || (z && t)) là một logical-OR-expression.
Để hiểu tại sao (x && y) lại là 1 logical-AND-expression, bạn cần phải đi tiếp sâu xuống các rule sau (rule cho AND, unary, cast, ...).
Dựa vào tập rule này, ta có thể chứng minh "1" là một expression. Thật vậy, hãy nhìn từ rule cuối cùng trong file expr.html, bạn thấy 1 là một constant, vì nó là integer-constant, nhìn tiếp rule gần cuối bạn nhận ra 1 sẽ quy về là một postfix-expression vì trong định nghĩa của postfix-expression có trường hợp chỉ có 1 constant đứng một mình. Sau đó ta tiếp tục áp dụng các rule ở phía trên để lần lượt suy ra 1 là một unary-expression, cast-expression, ... và cuối cùng là conditional-expression và expression!.
Như vậy, sau một hồi suy luận ta đã chứng minh được "1" là một biểu thức trong C.
Như vậy ta có thể biết được một dòng chữ bất kỳ có phải là 1 expression của C hay không.
b) Ý nghĩa (ngữ nghĩa) của biểu thức:
Việc định nghĩa ý nghĩa của biểu thức chủ yếu là ánh xạ ý nghĩa các toán tử của C thành ý nghĩa Toán học (giống như ví dụ về toán tử cộng ở trên).
Ví dụ, cho đến bây giờ bạn chưa biết toán tử << (dịch trái) có nghĩa là gì, ta có thể định nghĩa ý nghĩa toán tử đó như sau:
<x, M> --> n0
-----------------------------------------------------------------------------------------------------------------------------------------
<(x << k), M > --> số n1 sao cho các bit của n1 là các bit của n0 dịch sang bên trái k vị trí, điền 0 vào cuối trong hệ nhị phân (tức n1 = x * 2k)
Ví dụ, trong hệ nhị phân số 3 biểu diễn là 11, khi dịch đi 1 vị trí sang trái nó thành 110, là số 6. Trong C, (3 << 1)
== 6, (3 << 2) == 12, .., x << k == x * 2k* Ý nghĩa của biểu thức gán: x = A
Trước hết, ta định nghĩa "thay thế" (substitution) [x/A] của một trạng thái bộ nhớ M là trạng thái bộ nhớ M1, trong đó giá trị của ô nhớ đại diện cho x là A (tức x được thay thế bởi A). Ta viết như sau:
Ví dụ, [x / 5] { x = 9, y = 7 } sẽ là { x = 5, y = 7 }
Từ đó, ý nghĩa của toán tử gán là:
<A, M> --> n0 [x/n0]M = M' (chú ý: phần điều kiện có 2 điều kiện xảy ra đồng thời)
-----------------------------------------------------
M "x = A;" M'
Giả sử ta có trạng thái M = {x = 9, y = 7}, vì M' = { x = 5, y = 7 } = [x/5]{ x = 9, y = 7 } và <5, M> --> 5 (vì 5 là hằng số) nên ta suy ra cả 2 điều kiện của quy tắc suy luận trên đều thỏa mãn. Ta có thể đi đến kết luận sau:
{ x = 9, y = 7 } " x = 5; " { x = 5, y = 7 }
Có nghĩa là, ban đầu x có giá trị 9 và y có giá trị 7, sau khi thực hiện phép gán x = 5 thì ta có trạng thái bộ nhớ x có giá trị 5 và y có giá trị 7.
2.5. Cú pháp và ý nghĩa của cấu trúc if-then-else:
a) Cú pháp:
if_statement ::= "if" "(" expression ")" statement ("else" statement)?
Có nghĩa là, lệnh if được cấu tạo bởi: từ khóa "if", đi theo sau bởi dấu mở ngoặc "(", tiếp theo là 1 biểu thức, và dấu đóng ngoặc ")", sau đó đến 1 câu lệnh, rồi phần "else" statement có thể có hoặc không.
Như vậy, các câu lệnh sau đây là câu lệnh đúng trong C:
Như vậy, các câu lệnh sau đây là câu lệnh đúng trong C:
if ( 1 + 1 == 2 ) printf( "abc" );
if ( 1 > 5 ) printf( "def" );
else printf( "ghi" );
Hãy dựa vào quy tắc sinh thành ở trên, chứng minh rằng 2 câu lệnh trên là 2 câu lệnh if đúng cú pháp.
b) Ý nghĩa:
Ý nghĩa của lệnh if như sau:
b) Ý nghĩa:
Ý nghĩa của lệnh if như sau:
<A, M> --> true M B M' M C M''
--------------------------------------------------------------
M "if A then B else C" M'
<A, M> --> false M B M' M C M''
--------------------------------------------------------------
M "if A then B else C" M''
Có nghĩa là, lệnh if sẽ thực hiện nhánh B nếu A là biểu thức đúng, ngược lại, nó sẽ thực hiện nhánh C (vì thế "if A then B else C" hoàn toàn tương đương với C khi A được evaluate là false). (chú ý: để đơn giản ta giả sử A là 1 biểu thức thuần (kiểu 1 + 1 == 2), không gây tác dụng phụ (như in gì đó ra màn hình hay gán...)).
Ý nghĩa thực tiễn của lệnh if là: lệnh if sẽ evaluate biểu thức A, nếu A đúng thì nó thi hành các câu lệnh trong phần B, ngược lại nó thi hành các câu lệnh trong phần C. Nếu không có phần C, thì lệnh if sẽ chỉ evaluate biểu thức A rồi kết thúc nếu A trả về false. Ví dụ:
/*
File: if_demo0.c
usage of if statement
*/
#include<stdio.h>
int main(){
double a, b, c;
double d;
double z;
a = 3.0;
b = 4.5;
c = 5.6;
d = b * b - 4 * a * c;
if ( d >= 0 ) { // the expression "d >= 0" will be evaluated first, then printf will be executed if (d >= 0) is true
printf( "exist solution(s)!" );
}
return 0;
}/*
File: if_demo1.c
usage of if statement
*/
#include<stdio.h>
int main(){
double a, b, c;
double d;
double z;
a = 3.0;
b = 4.5;
c = 5.6;
d = b * b - 4 * a * c;
if ( d >= 0 ) { // the expression "d >= 0" will be evaluated first, then one of the if-branches will be executed
printf( "exist solution(s)!" );
} else {
printf( "solution does not exist" );
}
return 0;
}/*
File: if_demo2.c
Note: you need to link to math library to get execution file like this: $ gcc -o if_demo2 -lm if_demo2.c
*/
#include<stdio.h>
#include<math.h> // math.h contains mathematical functions: sin, cos, sqrt, ...
int main(){
double a, b, c;
double d;
double z;
a = 3.0;
b = 4.5;
c = 5.6;
// note that assignment is also an expression and has return value!
if ( (d = b * b - 4 * a * c) >= 0 ) { // d is assigned value here and the expression becomes (d >= 0)
if ( d > 0 ) {
printf( "two solutions: x1 = %lf, x2 = %lf\n", (-b - sqrt(d))/(2*a), (-b + sqrt(d))/(2*a) );
}else{
printf( "unique solution: x = %lf\n", -b/(2*a) );
}
} else {
printf( "solution does not exist" );
}
return 0;
}2.6. Cú pháp và ý nghĩa của vòng lặp for:
a) Cú pháp:
for_stmt ::= "for" "(" expression_list1 ";" expression_list2 ";" expression_list3 ")" statement
expression_list ::= <empty> | expression ("," expression)*
Nói một cách dễ hiểu, lệnh for được bắt đầu bằng từ khóa "for", theo sau bởi dấu mở ngoặc đơn "(", tiếp theo là 3 danh sách (dãy) các biểu thức phân cách bởi dấu chấm phảy ";", tiếp theo là dấu đóng ngoặc ")" và cuối cùng là câu lệnh (statement).
Một danh sách biểu thức (expression_list) là một dãy các biểu thức (expression) được phân cách nhau bởi dấu phảy ",". Ví dụ,
x = 1, y = 2
là một danh sách biểu thức gồm 2 biểu thức gán.
x++, y = x, z++
là một danh sách biểu thức gồm 3 biểu thức.
x < 5, y >= 0
là một danh sách biểu thức gồm 2 biểu thức điều kiện.
Ví dụ sau đây là các câu lệnh for đúng (x, y, z là các biến int đã khai báo):
Ví dụ sau đây là các câu lệnh for đúng (x, y, z là các biến int đã khai báo):
for( x = 0; x < 100; x++ ) printf( "x = %d\n", x );
for( x = 2, y = 1; y < 4x; x++, y = x * x ) {
printf( "x = %d, y = %d\n", x, y );
}
z = 0;
for( x = 1; x < (1 << 10); x *= 2 ) {
for( y = x; y < 2 * x; y++ ) {
z += y;
}
}
b) Ý nghĩa của lệnh for:
Lệnh for sẽ làm việc sau:
- 1. Khởi tạo: evaluate các biểu thức ở trong expression_list1
- 2. Kiểm tra điều kiện kết thúc: evaluate các biểu thức ở trong expression_list2, nếu 1 trong các biểu thức trả về false, kết thúc lệnh for
- 3. Thực hiện statement (câu lệnh bên trong vòng for)
- 4. Update các biến liên quan: evaluate các biểu thức trong expression_list3 (ví dụ x += 2, y++)
- 5. Quay lại bước 2.
Như vậy, ý nghĩa của lệnh for là lặp đi lặp lại việc kiểm tra điều kiện kết thúc, nếu chưa kết thúc, thực hiện statement (câu lệnh trong vòng for) rồi update các biến liên quan.
Nhờ việc update các biến liên quan (bước 4) mà hiệu ứng khi thực hiện statement (lệnh trong vòng for) thay đổi qua mỗi lần lặp, mặc dù bản thân statement là không đổi. Điều này tạo ra một hiệu ứng lý thú.
Ví dụ, ta có thể hiển thị các số từ 1 đến 100 ra màn hình bằng chương trình sau:
Nhờ việc update các biến liên quan (bước 4) mà hiệu ứng khi thực hiện statement (lệnh trong vòng for) thay đổi qua mỗi lần lặp, mặc dù bản thân statement là không đổi. Điều này tạo ra một hiệu ứng lý thú.
Ví dụ, ta có thể hiển thị các số từ 1 đến 100 ra màn hình bằng chương trình sau:
/*
File: for_demo1.c
*/
#include<stdio.h>
int main(){
int i;
for( i = 1; i < 100; i++ ) {
printf( "i = %d\n", i );
}
return 0;
}Ở chương trình trên, thay vì phải viết printf( "i = 1\n" ); printf( "i = 2\n" ), ... ta chỉ cần dùng 1 lệnh printf duy nhất: printf( "i = %d\n" ); và dựa vào hiệu ứng update biến số (bước 4) để in ra màn hình từ 1 đến 100. Khi thực hiện, lệnh for trên sẽ khởi tạo cho i = 1 (chỉ khởi tạo 1 lần duy nhất, không lặp), sau đó nó kiểm tra điều kiện ( i < 100), khi điều kiện này đúng, nó thực hiện lệnh printf và sau đó update biến i bằng cách thực hiện nốt lệnh i++. Sau 1 vòng lặp như vậy, lệnh này lại tiếp tục quay lại bước kiểm tra điều kiện, nếu điều kiện sai, lệnh for sẽ được kết thúc.
Như bạn đã biết, expression_list có thể empty, khi đó sẽ không có biểu thức nào trong expression_list ấy được evaluate. Ví dụ, lệnh sau tương đương với lệnh for ở ví dụ trên:
i = 1;
for( ; i < 100; i++ ) printf( "i = %d\n", i );
Lệnh for này khuyết expression_list1, tuy nhiên do ta đã gán i = 1; ở đầu nên i sẽ bắt đầu từ 1.
Sau đây là một vòng for vô hạn:
Sau đây là một vòng for vô hạn:
for( ; ; ) ;
Vòng for này khuyết tất cả các expression_list, vì vậy không có điều kiện kết thúc. Hơn nữa, statement cũng khuyết luôn! (tức vòng for này cứ lặp vô hạn và không làm gì!).
Việc định nghĩa ý nghĩa của lệnh for dựa trên operational semantics rất phức tạp nên ta không đề cập ở đây.
2.7. Cú pháp và ý nghĩa của vòng lặp while:
a) Cú pháp:
Việc định nghĩa ý nghĩa của lệnh for dựa trên operational semantics rất phức tạp nên ta không đề cập ở đây.
2.7. Cú pháp và ý nghĩa của vòng lặp while:
a) Cú pháp:
while_statement ::= "while" "(" expression ")" statement
b) Ý nghĩa:
Để đơn giản, ta giả sử A là một biểu thức thuần (không gây tác dụng phụ như hiển thị ra màn hình hay gán các biến số làm thay đổi giá trị). Ví dụ x+2 là một biểu thức thuần (x là biến nguyên).
Khi đó, ý nghĩa của câu lệnh while như sau:
Để đơn giản, ta giả sử A là một biểu thức thuần (không gây tác dụng phụ như hiển thị ra màn hình hay gán các biến số làm thay đổi giá trị). Ví dụ x+2 là một biểu thức thuần (x là biến nguyên).
Khi đó, ý nghĩa của câu lệnh while như sau:
<A, M> --> false <A, M> --> true M B M' M' "while (A) B;" M''
---------------------------------- --------------------------------------------------------------------------
M "while ( A ) B;" M M "while ( A ) B;" M''
Phát biểu ý nghĩa: lệnh while sẽ evaluate biểu thức trong ngoặc (expression), nếu true thì thực hiện statement, nếu false thì kết thúc, sau đó lặp đi lặp lại quá trình trên.
Ở quy tắc suy luận thứ 2 (khi A = true), ta đã dùng chính ý nghĩa của câu lệnh while để định nghĩa ý nghĩa của câu lệnh while. Việc dùng chính định nghĩa của một thứ trong lúc định nghĩa nó gọi là phép đệ quy (recursion). Ví dụ, ta có thể định nghĩa phép giai thừa của một số nguyên dương như sau:
n giai thừa sẽ bằng 1 nếu n = 0, ngược lại n giai thừa sẽ bằng n nhân với (n-1) giai thừa.
Trong định nghĩa trên, ta sử dụng khái niệm giai thừa để định nghĩa chính nó, vì vậy phép định nghĩa đó là một phép đệ quy.
Quy tắc thứ 2 của lệnh while ở trên cũng vậy, ta đã dùng chính ý nghĩa của lệnh while (M' "while (A) B;" M'') trong phần giả thiết để suy ra ý nghĩa trong phần kết luận.
Việc định nghĩa này có vẻ như vô lý, nhưng thực ra nó lại có lý như phần định nghĩa giai thừa, vì đến một lúc nào đó A sẽ trở thành false và quy tắc thứ nhất (không có đệ quy) sẽ được áp dụng (cũng giống như trong định nghĩa giai thừa, khi n = 0 thì không còn đệ quy nữa).
Ví dụ:
Ở quy tắc suy luận thứ 2 (khi A = true), ta đã dùng chính ý nghĩa của câu lệnh while để định nghĩa ý nghĩa của câu lệnh while. Việc dùng chính định nghĩa của một thứ trong lúc định nghĩa nó gọi là phép đệ quy (recursion). Ví dụ, ta có thể định nghĩa phép giai thừa của một số nguyên dương như sau:
n giai thừa sẽ bằng 1 nếu n = 0, ngược lại n giai thừa sẽ bằng n nhân với (n-1) giai thừa.
Trong định nghĩa trên, ta sử dụng khái niệm giai thừa để định nghĩa chính nó, vì vậy phép định nghĩa đó là một phép đệ quy.
Quy tắc thứ 2 của lệnh while ở trên cũng vậy, ta đã dùng chính ý nghĩa của lệnh while (M' "while (A) B;" M'') trong phần giả thiết để suy ra ý nghĩa trong phần kết luận.
Việc định nghĩa này có vẻ như vô lý, nhưng thực ra nó lại có lý như phần định nghĩa giai thừa, vì đến một lúc nào đó A sẽ trở thành false và quy tắc thứ nhất (không có đệ quy) sẽ được áp dụng (cũng giống như trong định nghĩa giai thừa, khi n = 0 thì không còn đệ quy nữa).
Ví dụ:
/*
File: while_demo1.c
*/
#include<stdio.h>
int main(){
int i;
i = 1;
while( i < 100 ) {
printf( "i = %d\n", i );
i++
}
return 0;
}Khác với lệnh for, lệnh while không tự update các biến (bước 4 của lệnh for) cho bạn, vì thế bạn phải tự update các biến số, nếu không vòng while sẽ lặp vô hạn (vì điều kiện trong expression có thể mãi mãi không thay đổi).
Ví dụ, sau đây là một vòng while vô hạn:
while( 1 ) printf( "abc" );
Ta có thể dùng 2 quy tắc suy luận về ý nghĩa của lệnh while ở trên để chứng minh rằng chương trình sau sẽ cho ra kết quả s = 3.
s = 0;
i = 2;
while( i > 0 )
s += i--;
Chứng minh: ban đầu M = { s = 0, i = 2 }, áp dụng quy tắc (2) (khi A = true), ta có thể suy ra chương trình sẽ làm cho trạng thái bộ nhớ trở thành M'' là trạng thái thu được từ M' sau khi thực hiện lệnh while. Hơn nữa, M' là trạng thái sau khi thực hiện lệnh "s += i--;" từ M, tức là M' = { s = 2, i = 1 }. Tiếp tục áp dụng quy tắc 2, ta suy ra từ M', chương trình sẽ đi đến trạng thái M''' là trạng thái thu được từ M'' sau khi thực hiện lệnh while, còn M'' là trạng thái thu được từ M' sau khi thực hiện lệnh "s += i--;" tức là M'' = { s = 3, i = 0}. Áp dụng quy tắc 1 ta suy ra M'' = M''' (vì lúc này A = false). Vậy trạng thái cuối cùng là M''' = { s = 3, i = 0 }. Ở trạng thái này ta có s = 3 (đpcm).
2.8. Câu lệnh rẽ nhánh switch:
2.8. Câu lệnh rẽ nhánh switch:
switch_statement ::= "switch" "(" expression ")" statement
Trong statement của lệnh switch, ta có thể có các nhãn khác nhau để khi expression trả về giá trị đúng bằng giá trị của nhãn thì các lệnh bắt đầu từ nhãn đó được thực hiện. Nhãn được gán bởi
label ::= ("case" expression | "default") ":"
Các expression ở label phải có giá trị là hằng số (ví dụ 1, 2, 'a', ...), không được chứa biến số.
Muốn ra dừng việc thực hiện lệnh trong lệnh switch, ta dùng lệnh "break"
Ví dụ, hàm số sau hiển thị cách đọc của các số 1, 2, 3:
Muốn ra dừng việc thực hiện lệnh trong lệnh switch, ta dùng lệnh "break"
Ví dụ, hàm số sau hiển thị cách đọc của các số 1, 2, 3:
/*
File: switch_demo1.c
*/
void number_name(int n){
switch( n ) {
case 1 :
printf( "one\n" );
break;
case 2 :
printf( "two\n" );
break;
case 3 :
printf( "three\n" );
break;
default: // reach here if the above not matched
printf( "don't know!\n" );
break;
}
}2.9. Câu lệnh do-while:
a) Cú pháp:
do_while_statement ::= "do" statement "while" "(" expression ")" ";"
Chú ý là lệnh này kết thúc bởi dấu chấm phảy (";").
b) Ý nghĩa:
Giống như khi định nghĩa ý nghĩa của lệnh while, ta giả sử A là một biểu thức thuần. Khi đó ý nghĩa của lệnh do-while như sau:
b) Ý nghĩa:
Giống như khi định nghĩa ý nghĩa của lệnh while, ta giả sử A là một biểu thức thuần. Khi đó ý nghĩa của lệnh do-while như sau:
<A, M'> --> false M B M'
---------------------------------------------------
M "do B while( A );" M'
<A, M'> --> true M B M' M' "do B while(A);" M''
-------------------------------------------------------------------------------------------------
M "do B while( A );" M''
Như vậy, lệnh do-while sẽ thực hiện statement B ít nhất một lần, sau đó mới kiểm tra điều kiện A, nếu A đúng lặp lại việc thực hiện B, nếu sai thì kết thúc lệnh do-while.
2.10. Cú pháp của câu lệnh trong C:
Trong phần này chúng ta sẽ chính thức định nghĩa statement (câu lệnh trong C). Sau khi biết định nghĩa này, bạn sẽ lý giải được tại sao kết thúc lệnh (hàm) printf lại phải có dấu chấm phảy, trong khi kết thúc lệnh for thì không cần dấu chấm phảy.
Trước hết, khái niệm tên định danh (identifier) là một khái niệm bạn vẫn dùng để định nghĩa tên hàm, tên biến, ... Ví dụ x, y, add_two_int_numbers là những tên định danh.
Tên định danh được bắt đầu bằng 1 ký tự chữ (letter), theo sau bởi 0 hoặc nhiều hơn dãy các ký tự hoặc chữ số (letter | digit)*, ví dụ x3, y5ab6, _abc, $y là những tên định danh đúng. Tuy nhiên, 3x không phải là tên định danh vì nó không bắt đầu bắng chữ (3 là số).
Cú pháp của câu lệnh trong C như sau:
2.10. Cú pháp của câu lệnh trong C:
Trong phần này chúng ta sẽ chính thức định nghĩa statement (câu lệnh trong C). Sau khi biết định nghĩa này, bạn sẽ lý giải được tại sao kết thúc lệnh (hàm) printf lại phải có dấu chấm phảy, trong khi kết thúc lệnh for thì không cần dấu chấm phảy.
Trước hết, khái niệm tên định danh (identifier) là một khái niệm bạn vẫn dùng để định nghĩa tên hàm, tên biến, ... Ví dụ x, y, add_two_int_numbers là những tên định danh.
Tên định danh được bắt đầu bằng 1 ký tự chữ (letter), theo sau bởi 0 hoặc nhiều hơn dãy các ký tự hoặc chữ số (letter | digit)*, ví dụ x3, y5ab6, _abc, $y là những tên định danh đúng. Tuy nhiên, 3x không phải là tên định danh vì nó không bắt đầu bắng chữ (3 là số).
Cú pháp của câu lệnh trong C như sau:
identifier ::= letter (letter | digit)*
label_declaration ::= (identifier | "case" constant-expression | "default") ":"
statement ::= label_declaration*
( expression? ";"
| block
| if_statement
| for_statement
| while_statement
| do_while_statement
| "goto" identifier ";"
| "continue" ";"
| "break" ";"
| "return" expression? ";" )
block ::=
"{"
declaration*
statement*
"}"
Có nghĩa là, câu lệnh của C bao gồm 2 phần: phần 1 là phần khai báo nhãn (label_declaration), phần 2 là phần các câu lệnh mà bạn đã học (for, while, return, ...).
Phần khai báo nhãn có thể có hoặc không, hơn nữa các nhãn có thể xếp hàng cạnh nhau (vì thế cú pháp là label_declaration*).
Block là một khái niệm quan trọng: nó nhóm các lệnh và các khai báo lại thành một khối. Block bắt đầu bởi dấu "{", kết thúc bởi "}". Hơn nữa, block cũng là một statement!. Vì thế, ví dụ, câu lệnh while sau đây là đúng cú pháp:
while( x > 1 ) {
printf( "x = %d\n", x-- );
}
và câu lệnh while sau đây cũng là đúng cú pháp:
while( x > 1 )
printf( "x = %d\n", x-- );
Ở trường hợp thứ nhất, statement của lệnh while là một khối (block), trong khi ở trường hợp thứ 2, statement của lệnh while không phải là một khối, mà là một biểu thức (printf là một lời gọi hàm, vì thế nó là một biểu thức - expression). Theo định nghĩa của statement ở trên, biểu thức đi theo sau bởi dấu chấm phảy cũng là một statement, vì thế câu lệnh while thứ 2 cũng đúng cú pháp:
while_statement ::= "while" "(" expression ")" statement
2.11. Ý nghĩa của các lệnh goto, break và continue:
- Lệnh goto nhảy đến nhãn (label) xác định bởi identifier (hãy nhìn cú pháp của lệnh goto và cú pháp của label_declaration)
- Lệnh break làm kết thúc việc thực hiện lệnh trong các câu lệnh switch, while, for, do-while
- Lệnh continue kết thúc việc thực hiện một lần lặp của các vòng lặp for, while, do-while và chuyển qua lần lặp mới
Ví dụ, chương trình sau dùng lệnh goto để hiển thị ra màn hình các số từ 1 đến 100 mà không cần dùng vòng lặp:
/*
File: goto_demo1.c
*/
int main(){
int i;
i = 1;
begin_print: // begin_print is a label, you can put any name you like here (e.g, "my_cute_cat")
printf( "i = %d\n", i );
i++;
if( i <= 100 )
goto begin_print;
else
goto end_print;
end_print:
printf( "done!\n" );
return 0;
}Bạn có thể coi "begin_print", "end_print" như các cột mốc và lệnh "goto cột_mốc" sẽ nhảy đến thực hiện các lệnh từ cột mốc đó trở đi. Vì thế lệnh goto gọi là lệnh nhảy vô điều kiện (unconditional jump)
Ví dụ tiếp theo là về lệnh break:
/*
File: while_demo2.c
*/
#include<stdio.h>
int main(){
int i;
i = 1;
while( 1 ) {
printf( "i = %d\n", i );
i++
if( i > 100 ) break;
}
return 0;
}Nếu không có lệnh break để thoát khỏi vòng lặp, vòng lặp while trên sẽ lặp vô hạn (vì điều kiện "1" luôn đúng).
Ví dụ tiếp theo là về lệnh continue, ta sẽ dùng lệnh này để hiển thị các số chẵn trong phạm vi 1 đến 100:
/*
File: while_demo3.c
*/
#include<stdio.h>
int main(){
int i;
i = 0;
while( i <= 100 ) {
i++
if( i % 2 != 0 ) continue;
printf( "i = %d\n", i );
}
return 0;
}Trong ví dụ trên, khi điều kiện (i % 2 != 0) (tức i là số lẻ) đúng thì lệnh continue sẽ được thực hiện, làm cho vòng lặp quay lên đầu và không thực hiện lệnh printf. Ngược lại, khi i là số chẵn thì lệnh continue không được thực hiện và điều khiển sẽ chuyển đến lệnh printf.
3. Thứ tự đánh giá biểu thức, câu lệnh:
Thứ tự đánh giá biểu thức và câu lệnh có ý nghĩa rất quan trọng vì nó cho biết thứ tự thực hiện khi có nhiều biểu thức, câu lệnh khác nhau.
3.1. Thứ tự đánh giá biểu thức:
Trong biểu thức, thứ tự đánh giá (evaluation) biểu thức phụ thuộc vào độ ưu tiên của toán tử. Ví dụ, phép nhân luôn được thực hiện trước phép cộng.
Trong lời gọi hàm, tham số của hàm luôn được đánh giá trước, sau đó lệnh gọi hàm mới được thực hiện. Vì thế, khi các hàm gọi lồng nhau thì hàm ở phía trong luôn được gọi trước.
Ví dụ:
int func1( int a )
{
printf( "func1 called: a = %d\n", a );
return a + 1;
}
int func2( int b, int c )
{
printf( "func2 called, b = %d, c = %d\n", b, c );
return b + c;
}
int main()
{
int x;
x = func2( func1( 5 ) + func1( 6 ) * func1( 7 ), func1( 8 ) );
printf( "x = %d\n", x );
return 0;
}
Khi đó, trên màn hình sẽ hiển thị các lệnh gọi hàm theo thứ tự sau:
func1 called: a = 8
func1 called: a = 5
func1 called: a = 6
func1 called: a = 7
func2 called, b = 62, c = 9
x = 71
Có nghĩa là, các tham số của hàm func2 được evaluate trước tiên (nhưng thứ tự evaluate các tham số không phải từ phải qua trái, cũng không phải từ trái qua phải mà là một thứ tự bất kỳ (phụ thuộc vào sự tối ưu hóa của compiler)), sau đó đánh giá tiếp đến func2.
3.2. Đánh giá bộ phận (partial evaluation):
Một trong những tối ưu hóa của trình biên dịch là việc đánh giá bộ phận. Đánh giá bộ phận xảy ra khi ta đã biết chắc chắn giá trị trả về của một biểu thức cho dù các phần còn lại của biểu thức có giá trị thế nào. Ví dụ:
3.2. Đánh giá bộ phận (partial evaluation):
Một trong những tối ưu hóa của trình biên dịch là việc đánh giá bộ phận. Đánh giá bộ phận xảy ra khi ta đã biết chắc chắn giá trị trả về của một biểu thức cho dù các phần còn lại của biểu thức có giá trị thế nào. Ví dụ:
x = 5;
if( (x > 4) || ( x * x < 12 ) ) printf( "%d\n", x );
Ta biết rõ biểu thức logic "(x > 4) || ( x * x < 12 )" có kết quả true ngay sau khi evaluate biểu thức (x > 4) bởi vì x = 5 luôn thỏa mãn (x > 4) mà phép OR logic trả về true khi chỉ cần 1 toán hạng là true. Vì thế, ta không cần evaluate biểu thức phía sau "(x * x < 12)" nữa, mà trả về ngay true cho điều kiện của lệnh if.
Tương tự, nếu ta có biểu thức
Tương tự, nếu ta có biểu thức
#include <stdio.h>
int my_func()
{
printf( "my_func called\n" );
return 1;
}
int main(){
int x, y;
x = 2;
y = ((x > 5) && (my_func() < 2));
printf( "%d\n", y );
}
Thì hàm my_func thực chất sẽ không được gọi (và câu "my_func called" sẽ không được hiển thị ra màn hình) vì điều kiện thứ nhất (x > 5) đã sai nên cả biểu thức AND logic cũng sai và ta không cần evaluate biểu thức sau đó.
Các biểu thức logic trong C luôn được đánh giá theo cách này!. Vì thế, nếu trong biểu thức logic có lời gọi hàm mang tác dụng phụ (hiển thị gì đó ra màn hình, gán, ...) bạn phải hết sức cẩn thận.
Ví dụ, chương trình sau sẽ không tính đúng giá trị của delta, vì thế nó cho kết quả sai:
Các biểu thức logic trong C luôn được đánh giá theo cách này!. Vì thế, nếu trong biểu thức logic có lời gọi hàm mang tác dụng phụ (hiển thị gì đó ra màn hình, gán, ...) bạn phải hết sức cẩn thận.
Ví dụ, chương trình sau sẽ không tính đúng giá trị của delta, vì thế nó cho kết quả sai:
// file: if_bug_demo.c : you need to link to math library to when compile & link:
// $ gcc -o if_bug_demo if_bug_demo.c -lm
#include <stdio.h>
#include <math.h>
void solve_quadratic_eq( double a, double b, double c)
{
double delta;
delta = -1.0;
if( a != 0 ) {
if( (b == 0) && ( (delta = (b * b - 4 * a * c)) > 0) ) {
printf( "Two solutions: x1 = %lf, x2 = %lf\n",
-sqrt( -c / a ),
sqrt( -c / a ) );
else {
if( delta < 0 ) printf( "No solution" );
if( delta == 0 ) printf( "Unique solution: %lf\n", -b / (2 * a) );
if( delta > 0 ) {
printf( "Two solutions: x1 = %lf, x2 = %lf\n",
-b - sqrt(delta) / (2 * a),
-b + sqrt(delta) / (2 * a) );
}
}
} else {
printf( "linear equation!\n" );
}
}
int main()
{
solve_quadratic_eq( 1, -3, 2 );
return 0;
}
Như bạn thấy, chương trình trên có vẻ đúng, nhưng thực chất lại sai,vì khi b khác 0 thì biểu thức điều kiện của lệnh if đầu tiên chỉ được đánh giá bộ phận và delta sẽ không được gán, vì thế delta vẫn bằng -1.0 (gây ra câu trả lời phương trình vô nghiệm!)
Câu hỏi ôn tập:
1. Nêu định nghĩa toán học ngôn ngữ dựa trên lý thuyết tập hợp?
2. Văn phạm là gì?
3. Văn phạm phi ngữ cảnh là gì?
4. Cây cú pháp (syntax tree) là gì?
5. Hãy vẽ cây cú pháp của câu tiếng Anh sau, dựa trên các quy tắc sinh thành đã nêu ở phần 1.2 (cho biết thêm 2 rule sau: N -> cake, V -> ate):
Câu hỏi ôn tập:
1. Nêu định nghĩa toán học ngôn ngữ dựa trên lý thuyết tập hợp?
2. Văn phạm là gì?
3. Văn phạm phi ngữ cảnh là gì?
4. Cây cú pháp (syntax tree) là gì?
5. Hãy vẽ cây cú pháp của câu tiếng Anh sau, dựa trên các quy tắc sinh thành đã nêu ở phần 1.2 (cho biết thêm 2 rule sau: N -> cake, V -> ate):
John ate a cake
6. Ta có thể quy định ngữ nghĩa của tiếng Anh bằng cách quy định ngữ nghĩa của từng quy tắc sinh thành. Một trong các cách định nghĩa của quy tắc
VP --> VP PP
là "cụm giới từ PP bổ nghĩa cho động từ chính của cụm động từ VP ở phía trước nó". Tức là VP --> (saw Mary), PP --> (with a telescope) có nghĩa là cụm "with a telescope" bổ nghĩa cho động từ "saw" chứ không phải bổ nghĩa cho danh từ "Mary". Vì thế, ý nghĩa toàn bộ câu "John saw Mary with a telescope" là "John dùng một cái kính viễn vọng để nhìn Mary".
Tuy nhiên, dựa theo các quy tắc sinh thành ở phần 1.2, ta có thể dẫn ra một cây cú pháp khác, với ý nghĩa hoàn toàn khác cho câu văn này. Ý nghĩa sau khi được dẫn ra là "John nhìn thấy Mary cầm một cái kính viễn vọng". Hãy vẽ cây cú pháp ứng với ý nghĩa này?.
7. Xét các biểu thức số học đơn giản chỉ gồm phép cộng, trừ và nhân chia các số nguyên, ví dụ (1 + 2), (5 + 6) * 7 - 3, ...
Ta ký hiệu nhân tử (factor) là F, số hạng là T (term), biểu thức là E (expression) và một số nguyên bất kỳ ký hiệu là i. Khi đó biểu thức có thể định nghĩa như sau:
Tuy nhiên, dựa theo các quy tắc sinh thành ở phần 1.2, ta có thể dẫn ra một cây cú pháp khác, với ý nghĩa hoàn toàn khác cho câu văn này. Ý nghĩa sau khi được dẫn ra là "John nhìn thấy Mary cầm một cái kính viễn vọng". Hãy vẽ cây cú pháp ứng với ý nghĩa này?.
7. Xét các biểu thức số học đơn giản chỉ gồm phép cộng, trừ và nhân chia các số nguyên, ví dụ (1 + 2), (5 + 6) * 7 - 3, ...
Ta ký hiệu nhân tử (factor) là F, số hạng là T (term), biểu thức là E (expression) và một số nguyên bất kỳ ký hiệu là i. Khi đó biểu thức có thể định nghĩa như sau:
E ::= T | E + T | E - T
T ::= F | T * F | T / F
F ::= i | "(" E ")"
a) Dẫn ra cây cú pháp của biểu thức 1 + 2, dựa trên các quy tắc sinh thành trên.
b) Dẫn ra cây cú pháp của biểu thức 1 * 2
c) Dẫn ra cây cú pháp của biểu thức (1 + 2) * 3
d) Dẫn ra cây cú pháp của biểu thức (1 + 2) * 3 + (4 + 5) * 6
e) Gải sửa ta không sử dụng bộ quy tắc trên, mà sử dụng bộ quy tắc sau:
b) Dẫn ra cây cú pháp của biểu thức 1 * 2
c) Dẫn ra cây cú pháp của biểu thức (1 + 2) * 3
d) Dẫn ra cây cú pháp của biểu thức (1 + 2) * 3 + (4 + 5) * 6
e) Gải sửa ta không sử dụng bộ quy tắc trên, mà sử dụng bộ quy tắc sau:
E ::= E + E
| E - E
| E * E
| E / E
| (E)
| i
Khi đó, dẫn ra 2 cây cú pháp khác nhau của biểu thức 1 + 2 * 5, từ đó suy ra rằng các quy tắc trên gây ra sự nhập nhằng cú pháp (tức cùng 1 biểu thức mà có 2 cây cú pháp khác nhau)
f) Evaluate 2 cây cú pháp khác nhau được dẫn ra ở câu (e) để thu được kết quả cuối cùng của biểu thức.
g) (*) Nhận xét quan hệ giữa độ ưu tiên của toán tử với quan hệ cha - con của ký hiệu trong cây cú pháp (trong một cây, nếu 2 nút có liên kết thì nút đứng ở gần gốc hơn (nút xuất hiện trước) là cha)
gốc của cây là cha của tất cả các nút khác và cây chỉ có 1 gốc duy nhất). Ví dụ, khi toán tử nhân có độ ưu tiên cao hơn toán tử cộng thì ký hiệu chứa toán tử nhân là cha hay con của ký hiệu chứa toán tử cộng? (gợi ý: để ý cách quy định rule để toán tử nhân được ưu tiên hơn toán tử cộng ở tập rule thứ nhất, so sánh xem tại sao tập rule thứ 2 không làm được điều đó (nên gây ra nhập nhằng cú pháp) )
8. Trong ngôn ngữ lập trình C, các biểu thức như ở câu 7 được định nghĩa như sau:
f) Evaluate 2 cây cú pháp khác nhau được dẫn ra ở câu (e) để thu được kết quả cuối cùng của biểu thức.
g) (*) Nhận xét quan hệ giữa độ ưu tiên của toán tử với quan hệ cha - con của ký hiệu trong cây cú pháp (trong một cây, nếu 2 nút có liên kết thì nút đứng ở gần gốc hơn (nút xuất hiện trước) là cha)
gốc của cây là cha của tất cả các nút khác và cây chỉ có 1 gốc duy nhất). Ví dụ, khi toán tử nhân có độ ưu tiên cao hơn toán tử cộng thì ký hiệu chứa toán tử nhân là cha hay con của ký hiệu chứa toán tử cộng? (gợi ý: để ý cách quy định rule để toán tử nhân được ưu tiên hơn toán tử cộng ở tập rule thứ nhất, so sánh xem tại sao tập rule thứ 2 không làm được điều đó (nên gây ra nhập nhằng cú pháp) )
8. Trong ngôn ngữ lập trình C, các biểu thức như ở câu 7 được định nghĩa như sau:
additive-expression ::= multiplicative-expression ( ("+" | "-") multiplicative-expression )*
multiplicative-expression ::= cast-expression ( ("*" | "/" | "%") cast-expression )*
cast-expression ::= integer-constant | "(" additive-expression ")"
(chú ý: rule 3 không phải rule của C, rule của C phức tạp hơn).
a) Dẫn ra cây cú pháp của biểu thức (1 + 2) * 3 + (4 + 5) * 6
b) Dẫn ra cây cú pháp của biểu thức 1 + 2 - 5. Có thể có 2 cây cú pháp khác nhau cho biểu thức này không?
c) Hãy tìm 2 rule đầu (additive-expression và multiplicative-expression) trong file expr.html xem nó ở vị trí nào?
d) (*) Dẫn ra cây cú pháp cho biểu thức 1 + 2 - 5 dựa vào các rule có trong file expr.html.
9. Cú pháp của ngôn ngữ lập trình C dựa trên văn phạm gì?
10. Ý nghĩa (ngữ nghĩa) của ngôn ngữ lập trình C được quy định bằng cách nào?
11. Cho biết ý nghĩa của toán tử <<= trong ngôn ngữ C được quy định như sau:
a) Dẫn ra cây cú pháp của biểu thức (1 + 2) * 3 + (4 + 5) * 6
b) Dẫn ra cây cú pháp của biểu thức 1 + 2 - 5. Có thể có 2 cây cú pháp khác nhau cho biểu thức này không?
c) Hãy tìm 2 rule đầu (additive-expression và multiplicative-expression) trong file expr.html xem nó ở vị trí nào?
d) (*) Dẫn ra cây cú pháp cho biểu thức 1 + 2 - 5 dựa vào các rule có trong file expr.html.
9. Cú pháp của ngôn ngữ lập trình C dựa trên văn phạm gì?
10. Ý nghĩa (ngữ nghĩa) của ngôn ngữ lập trình C được quy định bằng cách nào?
11. Cho biết ý nghĩa của toán tử <<= trong ngôn ngữ C được quy định như sau:
<x << y, M> --> n0 [x/n0]M = M'
----------------------------------------------------------------
M "x <<= y" M'
Trong đó, ý nghĩa của toán tử dịch phải (<<) đã được quy định sẵn như ở phần (2.3.b).
Hãy phát biểu bằng lời ý nghĩa của toán tử <<=
12. Nêu cú pháp và ý nghĩa của câu lệnh if.
13. Chứng minh rằng sau khi thực hiện đoạn chương trình sau thì s = 3, giả sử trạng thái bộ nhớ trước lệnh if là M = { s = 1, i = 1 }.
Hãy phát biểu bằng lời ý nghĩa của toán tử <<=
12. Nêu cú pháp và ý nghĩa của câu lệnh if.
13. Chứng minh rằng sau khi thực hiện đoạn chương trình sau thì s = 3, giả sử trạng thái bộ nhớ trước lệnh if là M = { s = 1, i = 1 }.
if( i > 0 )
s += 2;
else
s -= 2;
14. Hãy viết chương trình giải phương trình bậc nhất ax + b = 0, xét cả trường hợp a = 0, b = 0, ... (vô nghiệm, vô định, nghiệm duy nhất). Cho biết a, b, x là các số thực.
15. Hãy viết chương trình giải phương trình bậc hai ax2 + bx + c = 0, xét cả trường hợp a = 0 (quy về phương trình bậc nhất), b = 0, c = 0 (vô nghiệm, vô định, ...).
16. Nếu cú pháp của lệnh for và phát biểu ý nghĩa (bằng lời) của nó.
17. Hãy viết một hàm số trả về giá trị int để tính tổng S = 1 + 2 + 3 + .. + n, trong đó n là một tham số nguyên. Hãy viết chương trình gọi hàm trên để tính tổng của 1 + .. + 100
18. Hãy dùng lệnh for để hiển thị ra màn hình các số lẻ trong khoảng từ 1 đến 100.
19. Nêu cú pháp và ý nghĩa của vòng lặp while?
20. Chứng minh rằng sau khi thực hiện đoạn chương trình sau thì s = 6, giả sử ban đầu trạng thái bộ nhớ là M = { i = 1, s = 1 }
15. Hãy viết chương trình giải phương trình bậc hai ax2 + bx + c = 0, xét cả trường hợp a = 0 (quy về phương trình bậc nhất), b = 0, c = 0 (vô nghiệm, vô định, ...).
16. Nếu cú pháp của lệnh for và phát biểu ý nghĩa (bằng lời) của nó.
17. Hãy viết một hàm số trả về giá trị int để tính tổng S = 1 + 2 + 3 + .. + n, trong đó n là một tham số nguyên. Hãy viết chương trình gọi hàm trên để tính tổng của 1 + .. + 100
18. Hãy dùng lệnh for để hiển thị ra màn hình các số lẻ trong khoảng từ 1 đến 100.
19. Nêu cú pháp và ý nghĩa của vòng lặp while?
20. Chứng minh rằng sau khi thực hiện đoạn chương trình sau thì s = 6, giả sử ban đầu trạng thái bộ nhớ là M = { i = 1, s = 1 }
while( i < 4 )
s *= i++;
21. Hãy viết một hàm để kiểm tra xem một số có phải là số nguyên tố hay không? Nếu có, hãy trả lại giá trị true (1), nếu không, trả lại false (0).
Sau đó, hãy viết một chương trình để hiển thị các số nguyên tố từ 1 đến 100.
22. Nêu cú pháp và của lệnh switch?. Phát biểu ý nghĩa (bằng lời) của lệnh đó?
23. Hãy viết một hàm để hiển thị cách đọc tên tháng bằng tiếng Anh khi đối số của hàm là số thứ tự của tháng (ví dụ 1 --> January). Nếu tham số là một số nằm ngoài khoảng từ 1..12 thì hiển thị: "Error: invalid month".
24. Nêu cú pháp và ý nghĩa của lệnh do-while?
25. Chứng minh rằng sau khi thực hiện đoạn chương trình sau thì s = 6, cho biết trạng thái bộ nhớ ban đầu M = { i = 3, s = 0 }
do
s += i--;
while( i > 0 );
Hãy viết một chương trình sử dụng đoạn mã lệnh trên và cuối cùng hiển thị s ra màn hình để chứng tỏ điều bạn vừa chứng minh là đúng
26. Chương trình sau đúng cú pháp hay sai cú pháp, tại sao
26. Chương trình sau đúng cú pháp hay sai cú pháp, tại sao
#include <stdio.h>
int main() {
int s, i;
s = 0;
i = 3;
do
s += i;
i--;
while( i > 0 );
return 0;
}
27. Hai chương trình sau đây có ý nghĩa giống nhau hay khác nhau, tại sao?
(chú ý: phím Ctrl + C ở terminal (Cygwin) là để cưỡng chế chương trình đang chạy kết thúc).
(chú ý: phím Ctrl + C ở terminal (Cygwin) là để cưỡng chế chương trình đang chạy kết thúc).
// file: while3.c
#include <stdio.h>
int main() {
int s, i;
s = 0;
i = 3;
while( i > 0 )
s += i;
i--;
printf( "%d\n", s );
return 0;
}
----------------------------------------------------------
// file: while4.c
#include <stdio.h>
int main() {
int s, i;
s = 0;
i = 3;
while( i > 0 ) {
s += i;
i--;
}
printf( "%d\n", s );
return 0;
}
28. Hãy nêu cú pháp của câu lệnh (statement) của C. Hãy chỉ ra những câu lệnh nào cần có dấu chấm phảy ở cuối, câu lệnh nào không cần?
29. Không dùng máy tính, hãy cho biết chương trình sau hiển thị ra màn hình kết quả gì?.
29. Không dùng máy tính, hãy cho biết chương trình sau hiển thị ra màn hình kết quả gì?.
// file: while5.c
#include <stdio.h>
int main() {
int s, i;
s = 0;
i = 9;
while( i > 0 ) {
i--;
if( i % 2 == 0 ) continue;
s += i;
if( s == i * 5 ) break;
}
printf( "s = %d,i = %d\n", s, i );
return 0;
}
Hãy copy & paste (hoặc gõ lại) đoạn chương trình trên rồi compile & run xem phán đoán của bạn có đúng không?
30. a) Partial evaluation là gì?. Các biểu thức loại nào được evaluate theo chiến lược này?
b) Hãy cho biết 2 chương trình sau có tương đương không, vì sao?
(Chú ý: nếu khi chạy chương trình bị lặp vô hạn, bạn có thể thoát bằng cách bấm Ctrl + C).
30. a) Partial evaluation là gì?. Các biểu thức loại nào được evaluate theo chiến lược này?
b) Hãy cho biết 2 chương trình sau có tương đương không, vì sao?
(Chú ý: nếu khi chạy chương trình bị lặp vô hạn, bạn có thể thoát bằng cách bấm Ctrl + C).
// file: while6.c
#include<stdio.h>
int main()
{
int x, y, s;
x = 5;
y = 6;
s = 0;
while( (y-- > 0) || (x-- > 1) )
{
s += x * y;
printf( "x = %d, y = %d\n", x, y );
}
printf( "s = %d\n", s );
return 0;
}
// file: while7.c
#include<stdio.h>
int main()
{
int x, y, s;
x = 5;
y = 6;
s = 0;
while( (x-- > 1) || (y-- > 0) )
{
s += x * y;
printf( "x = %d, y = %d\n", x, y );
}
printf( "s = %d\n", s );
return 0;
}
31. Ta có thể giải phương trình nghiệm nguyên 3x - 4y = z * (x*y - 1) (cho biết x, y, z nằm trong khoảng 1..100) bằng cách liệt kê tất cả các tổ hợp giá trị của x, y, z rồi thử. Cách tốt nhất để làm việc này là dùng vòng for (lồng nhau 3 lần). Hãy viết chương trình giải phương trình nghiệm nguyên 3x - 4y = z * (x*y - 1).
32. Sau đây là cú pháp đầy đủ của ngôn ngữ lập trình C: cgrammar.html.
a) "printf" có phải là một identifier (tên định danh) không, vì sao?
b) Hãy chứng tỏ rằng 'printf( "abc" )' (không có dấu chấm phảy ở cuối) là một postfix-expression (biết rằng: "abc" là một string).
c) Hãy chứng tỏ rằng 'printf( "abc" );' (có dấu chấm phảy ở cuối) là một statement (câu lệnh).
d) Giải thích vì sao khi bạn viết chương trình lại cần thêm dấu chấm phảy vào cuối khi thực hiện lệnh printf.
33. Khi bạn muốn gán giá trị của biến số thực (double) cho biến số nguyên (int), bạn phải "ép kiểu" (type casting) số thực thành số nguyên.
Ví dụ, đoạn mã sau đây là đúng:
32. Sau đây là cú pháp đầy đủ của ngôn ngữ lập trình C: cgrammar.html.
a) "printf" có phải là một identifier (tên định danh) không, vì sao?
b) Hãy chứng tỏ rằng 'printf( "abc" )' (không có dấu chấm phảy ở cuối) là một postfix-expression (biết rằng: "abc" là một string).
c) Hãy chứng tỏ rằng 'printf( "abc" );' (có dấu chấm phảy ở cuối) là một statement (câu lệnh).
d) Giải thích vì sao khi bạn viết chương trình lại cần thêm dấu chấm phảy vào cuối khi thực hiện lệnh printf.
33. Khi bạn muốn gán giá trị của biến số thực (double) cho biến số nguyên (int), bạn phải "ép kiểu" (type casting) số thực thành số nguyên.
Ví dụ, đoạn mã sau đây là đúng:
int x;
double y;
y = 3.3;
x = (int)y; // type casting: use (int)y to "cast" y into integer.
printf( "x = %d, y = %lf\n", x, y );
a) Hãy viết đầy đủ và chạy đoạn chương trình trên để xem giá trị của x bằng mấy?
b) Hãy đặt y = 3.9 và xem x bằng bao nhiêu?
c) Hãy tìm định nghĩa của "cast-expression" trong file cgrammar.html để hiểu rõ cú pháp của biểu thức ép kiểu.
34. Toán tử hoặc bit (inclusive-OR) ký hiệu là "|". Toán tử này trả về giá trị là phép hoặc bit của 2 toán hạng. Ví dụ a = 10010 (trong hệ nhị phân), b = 10100 thì
b) Hãy đặt y = 3.9 và xem x bằng bao nhiêu?
c) Hãy tìm định nghĩa của "cast-expression" trong file cgrammar.html để hiểu rõ cú pháp của biểu thức ép kiểu.
34. Toán tử hoặc bit (inclusive-OR) ký hiệu là "|". Toán tử này trả về giá trị là phép hoặc bit của 2 toán hạng. Ví dụ a = 10010 (trong hệ nhị phân), b = 10100 thì
x = (a | b) = (10010 | 10100) = 10110
(lưu ý: 1 | 0 = 0 | 1 = 1 | 1 = 1, 0 | 0 = 0).
a) Hãy phân biệt cú pháp của phép hoặc bit và phép hoặc bình thường.
b) Định nghĩa ý nghĩa của phép hoặc thông thường (logical-OR-expression) dựa trên operational semantics.
c) Định nghĩa ý nghĩa của phép hoặc bit dựa trên operational semantics.
d) Hãy tìm hiểu điều tương tự với phép AND-bit, XOR-bit, dựa vào file cú pháp cgrammar.html.
35.(***) Hãy định nghĩa operational semantics của lệnh for.
36. (**) Cho biết vì sao việc định nghĩa semantics của lệnh goto rất khó khăn?
37.(Optional) Một nhà khoa học máy tính lỗi lạc đã có bài viết "Goto statement considered harmful".
a)Hãy google xem ông là ai?
b)(**)Hãy đọc và hiểu bài viết của ông
38. (Optional) Nhà khoa học máy tính ở câu 37 cũng có một câu văn vần nổi tiếng khác: "Two or more, use a for".
Hãy đọc tiểu sử của ông trên Wikipedia để biết ý nghĩa của câu văn trên.
a) Hãy phân biệt cú pháp của phép hoặc bit và phép hoặc bình thường.
b) Định nghĩa ý nghĩa của phép hoặc thông thường (logical-OR-expression) dựa trên operational semantics.
c) Định nghĩa ý nghĩa của phép hoặc bit dựa trên operational semantics.
d) Hãy tìm hiểu điều tương tự với phép AND-bit, XOR-bit, dựa vào file cú pháp cgrammar.html.
35.(***) Hãy định nghĩa operational semantics của lệnh for.
36. (**) Cho biết vì sao việc định nghĩa semantics của lệnh goto rất khó khăn?
37.(Optional) Một nhà khoa học máy tính lỗi lạc đã có bài viết "Goto statement considered harmful".
a)Hãy google xem ông là ai?
b)(**)Hãy đọc và hiểu bài viết của ông
38. (Optional) Nhà khoa học máy tính ở câu 37 cũng có một câu văn vần nổi tiếng khác: "Two or more, use a for".
Hãy đọc tiểu sử của ông trên Wikipedia để biết ý nghĩa của câu văn trên.
Nội Quy Khi Gửi Bình Luận:
- - Vui lòng gõ có dấu khi sử dụng tiếng việt.
- - Nghiêm cấm spam link khác.
- - Sử dụng ngôn ngữ có văn hóa khi comment.
- - Chèn hình ảnh bằng code Link hình ảnh
- - Chèn video bằng code [iframe] Link nhúng video [/iframe]
- - Ngoài ra bạn có thể thêm những smile bên dưới vào bình luận để thêm sinh động
Biểu Tượng VuiBiểu Tượng Vui