Ngữ pháp (BNF) và Ký hiệu Ba Lan Reverse
Đã giới thiệu| English | Ý nghĩa |
|---|---|
| postfix/ˈpəʊstfɪks/ | postfix: hậu tố |
| precedence/ˈpresɪdəns/ | độ ưu tiên |
| grammar/ˈɡræmə/ | grammar: ngữ pháp |
| syntax diagram/ˈsɪntæks ˈdaɪəɡræm/ | Sơ đồ cú pháp |
| Reverse Polish Notation/rɪˈvɜːs ˈpəʊlɪʃ nəʊˈteɪʃn/ | Biểu diễn Ba Lan ngược |
| Backus-Naur Form/ˈbækəs nɔː fɔːm/ | Dạng Backus-Naur |
| production rules/prəˈdʌkʃn ruːlz/ | Luật sinh |
| terminal/ˈtɜːmɪnl/ | Ký hiệu kết thúc |
| non-terminal/nɒn ˈtɜːmɪnl/ | Ký hiệu không kết thúc |
| infix/ˈɪnfɪks/ | Cú pháp trung tố |
Ký hiệu không dùng ngoặc, hoàn toàn không gây nhầm lẫn
- Viết
3 + 4 * 2và bạn đang dựa vào quy ước: phép nhân có độ ưu tiên cao hơn phép cộng. Nếu thay đổi quy ước này, biểu thức sẽ mang ý nghĩa khác. - Một nhà logic người Ba Lan, Jan Łukasiewicz, đã chứng minh trong những năm 1920 rằng nếu đặt toán tử trước các toán hạng thì ngoặc trở nên không cần thiết. Đảo ngược lại, đặt toán tử sau, ta thu được dạng mà máy tính có thể xử lý chỉ bằng một cấu trúc dữ liệu gọi là ngăn xếp (stack).
- Đó là lý do tại sao Máy ảo Java (JVM) và hầu hết các bộ giải mã bytecode đều sử dụng hậu tố. Không cần bảng độ ưu tiên, không cần ngoặc, không có sự mơ hồ.
- Bài học này trình bày cách ngữ pháp của ngôn ngữ được ghi lại dưới dạng BNF và sơ đồ cú pháp, cũng như cách chuyển đổi và đánh giá Ký hiệu Ba Lan Reverse.
Dạng Backus-Naur
- Một ngữ pháp quy định những chuỗi token nào tạo thành chương trình hợp lệ. Dạng Backus-Naur (BNF) viết nó dưới dạng quy tắc sản xuất:
<symbol> ::= alternative1 | alternative2 | ...
- Một ký tự hữu hạn (terminal) là văn bản nguyên văn xuất hiện trong chương trình. Một ký tự phi hữu hạn (non-terminal) là tên của một quy tắc khác, được viết trong ngoặc nhọn.
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<letter> ::= a | b | c | … | z
<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>
Trong BNF, ký hiệu đầu ra là:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Các ký hiệu đầu ra là các tokenROOT; các ký hiệu phi đầu ra là tên của các quy tắc sản sinh khác.
Đệ quy là cách BNF thực hiện lặp lại
- BNF không có ký hiệu "lặp", vì vậy việc lặp lại được mô tả bằng cách định nghĩa một quy tắc dựa trên chính nó.
- Đọc
<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>như sau: một danh hiệu là một chữ cái đơn lẻ, hoặc một danh hiệu theo sau bởi một chữ cái, hoặc một danh hiệu theo sau bởi một chữ số. - Tổng hợp các phương án này có nghĩa là "một chữ cái theo sau bởi bất kỳ số lượng chữ cái hoặc chữ số nào", điều này cũng giải thích tại sao danh hiệu không thể bắt đầu bằng một chữ số: không có phương án nào cho phép điều đó.
- Một sơ đồ cú pháp, hay còn gọi là sơ đồ đường ray, biểu diễn cùng các quy tắc đó dưới dạng đồ thị, với vòng lặp tương ứng với phần đệ quy trong BNF. Hai ký hiệu này tương đương nhau.
Vòng lặp và đệ quy nói lên cùng một ý
Ghép nối mỗi thuật ngữ ngữ pháp/ký hiệu với ý nghĩa của nó.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
BNF xây dựng các quy tắc từ các ký hiệu đầu ra và phi đầu ra (đệ quy tạo ra sự lặp lại); RPN sắp xếp lại biểu thức để loại bỏ ngoặc.
Tại sao quy tắc
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Các phương án lựa chọn cùng nhau có nghĩa là một chữ cái theo sau bởi bất kỳ số lượng nào của chữ cái hoặc chữ số, và không có phương án nào cho phép bắt đầu bằng chữ số.
Ví dụ minh họa: kiểm tra một chuỗi theo ngữ pháp
- Sử dụng các quy tắc trên, trong số
count2,2countvàmy_var, cái nào là định danh hợp lệ? count2: hợp lệ. Xây dựng nó lên:clà một<letter>, vì vậy là một<identifier>; thêmo,u,n,ttheo phương án thứ hai; thêm2theo phương án thứ ba.2count: không hợp lệ. Mọi phương án đều bắt đầu từ một<letter>hoặc từ một<identifier>khác, và không có chuỗi nào có thể bắt đầu bằng chữ số.my_var: không hợp lệ, vì_không phải là ký tự kết thúc (terminal) trong bất kỳ quy tắc nào ở đây. Hãy nêu cụ thể quy tắc vi phạm, chứ không chỉ nói "nó trông sai".
Sử dụng các quy tắc đó, những chuỗi nào là danh định hợp lệ? Chọn tất cả các phương án phù hợp.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Một chữ cái đơn lẻ là một danh định theo phương án đầu tiên. 2count không thể bắt đầu bằng chữ số, và _ không phải là ký hiệu đầu ra trong bất kỳ quy tắc nào ở đây.
Phép toán trung tố và hậu tố
- Phép toán trung tố đặt toán tử giữa các toán hạng của nó, ví dụ
3 + 4 * 2, do đó cần quy tắc ưu tiên và dấu ngoặc để tránh mơ hồ. - Ký hiệu Ba Lan đảo ngược (Reverse Polish Notation), hay còn gọi là hậu tố, đặt toán tử sau các toán hạng: ví dụ
3 4 2 * +. Nó không cần cả hai yếu tố trên. - Thứ tự xuất hiện của các toán tử trong dạng hậu tố chính là thứ tự mà chúng được thực thi, điều này hoàn toàn phù hợp với những gì máy tính cần được hướng dẫn.
Chuyển đổi từ trung tố sang hậu tố
- Sử dụng một ngăn xếp toán tử. Quét từ trái sang phải: gửi trực tiếp một toán hạng đến đầu ra; đối với một toán tử, trước hết hãy loại bỏ (pop) ra đầu ra tất cả các toán tử đang nằm trên ngăn xếp có độ ưu tiên cao hơn hoặc bằng, sau đó đẩy toán tử đó vào.
- Đẩy một dấu ngoặc mở vào ngăn xếp. Khi gặp dấu ngoặc đóng, hãy loại bỏ (pop) ra đầu ra cho đến khi tìm thấy dấu ngoặc mở tương ứng, sau đó discard cặp ngoặc này.
- Ở cuối quá trình, hãy loại bỏ (pop) tất cả những gì còn sót lại trên ngăn xếp vào đầu ra.
Độ ưu tiên toán tử — điều mà RPN loại bỏ
Trong toán học infix thông thường, × và ÷ có độ liên kết chặt hơn + và −, vì vậy bạn phải áp dụng các quy tắc theo đúng thứ tự. Ký hiệu Ba Lan Reverse viết các toán hạng trước (3 4 2 × + 1 −), cố định thứ tự nên không cần quy tắc độ ưu tiên.
Dạng RPN (đuôi) của biểu thức infix (3 + 4) * 2 là gì?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Ngoặc buộc 3+4 thực hiện trước: 3 4 +, sau đó nhân với 2: 3 4 + 2 *.
Chuyển đổi (A + B) * (C - D) sang Ký hiệu Ba Lan Reverse, sử dụng * cho phép nhân.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Mỗi cặp ngoặc được chuyển đổi lần lượt và phép nhân bị loại bỏ cuối cùng, vì vậy nó xuất hiện ở cuối. Không có ngoặc nào tồn tại.
Ví dụ minh họa: chuyển đổi, sau đó tính toán
- Chuyển $(A + B) \times (C - D)$ sang RPN. Đẩy
(; đưaAra đầu ra; đẩy+; đưaBra đầu ra; khi gặp), hãy pop ngược về dấu ngoặc mở tương ứng(, thu đượcA B +. Đẩy×. Dấu ngoặc thứ hai hoạt động tương tự, tạo raC D -. Ở cuối, pop×. Kết quả:A B + C D - ×. - Bây giờ tính toán giá trị của nó cho $A=3, B=4, C=5, D=2$. Đẩy 3, đẩy 4;
+pop cả hai và push 7. Đẩy 5, đẩy 2;-pop cả hai và push 3.×pop 7 và 3 và push 21. - Toán tử luôn lấy hai phần tử trên cùng, và phần tử được pop ra trước sẽ là toán hạng bên phải. Điều này quan trọng đối với
-và/, nơi thứ tự thay đổi sẽ làm thay đổi kết quả.
Tính giá trị biểu thức RPN 3 4 2 * +.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Đẩy 3, 4, 2; * lấy ra 4 và 2 → 8; + lấy ra 3 và 8 → 11.
Ký hiệu Ba Lan Reverse không cần ngoặc hay quy tắc độ ưu tiên, và có thể được đánh giá trực tiếp bằng một ngăn xếp.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Đẩy các toán hạng; mỗi toán tử lấy ra các toán hạng của nó và đẩy kết quả — đó chính xác là cách máy chạy ngăn xếp hoạt động.
Tính toán với ngăn xếp, từng bước một
- Quét từ trái sang phải: đẩy (push) mỗi toán hạng; khi gặp một toán tử, hãy pop hai phần tử trên cùng, áp dụng toán tử, và đẩy kết quả lên ngăn xếp. Ở cuối, ngăn xếp chứa một giá trị duy nhất: đáp án.
| Token | Ngăn xếp sau khi xử lý |
|---|---|
3 |
3 |
4 |
3, 4 |
2 |
3, 4, 2 |
* |
3, 8 |
+ |
11 |
- Đây là máy stack: không có ngoặc, không có bảng ưu tiên, không có xem trước. Đó là cách JVM và nhiều trình giải mã bytecode đánh giá mọi biểu thức.
Khi đánh giá RPN, mục đầu tiên bị lấy ra khỏi ngăn xếp là toán hạng bên trái của toán tử.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Mục đầu tiên bị lấy ra là toán hạng bên phải. Điều này không quan trọng đối với + và *, nhưng đảo ngược nó sẽ phá hủy phép trừ và phép chia.
Sắp xếp các bước đánh giá 3 4 2 * + với ngăn xếp theo thứ tự.
Difficulty 3/5 · 200 coins + a small bonus on first completion today
Các toán hạng được đẩy lên, mỗi toán tử tiêu thụ hai mục trên cùng và để lại kết quả của nó. Không cần ngoặc và không cần bảng độ ưu tiên.
Điểm số dễ mất
- Một ký hiệu kết thúc (terminal) là văn bản gốc; một ký hiệu không kết thúc (non-terminal) tên của một quy tắc khác. Đừng hoán đổi chúng.
- BNF biểu diễn sự lặp lại bằng đệ quy. Nếu một quy tắc tham chiếu đến chính nó, hãy nêu rõ và giải thích ý nghĩa của nó.
- Trong quá trình đánh giá, toán tử lấy hai phần tử trên cùng, và phần tử bị loại bỏ đầu tiên là toán hạng phải. Nếu làm ngược lại sẽ gây sai sót trong phép trừ và chia.
- RPN không cần ngoặc. Việc viết ngoặc vào câu trả lời dạng hậu tố sẽ mất điểm vì đã phá vỡ cấu trúc đang được kiểm tra.
Bạn đã nắm vững
- BNF các quy tắc sản sinh kết hợp ký hiệu kết thúc (văn bản gốc) và ký hiệu không kết thúc (tên quy tắc), và biểu diễn sự lặp lại bằng đệ quy; một sơ đồ cú pháp là dạng đồ họa tương đương
- Kiểm tra một chuỗi bằng cách xây dựng nó từ các quy tắc, và đặt tên cho quy tắc thất bại khi chuỗi đó không hợp lệ
- infix cần độ ưu tiên và dấu ngoặc; RPN (postfix) đặt toán tử sau các toán hạng của nó và không cần cả hai
- chuyển đổi bằng một ngăn xếp toán tử, và đánh giá bằng cách đẩy các toán hạng vào và áp dụng mỗi toán tử cho hai phần tử trên cùng, phần tử bị loại đầu tiên là toán hạng bên phải