ไวยากรณ์ (BNF) และสัญชาตญาณ reverse polish
| English | ไทย |
|---|---|
| postfix/ˈpəʊstfɪks/ | postfix notation |
| precedence/ˈpresɪdəns/ | ลำดับความสำคัญ |
| grammar/ˈɡræmə/ | ไวยากรณ์ |
| syntax diagram/ˈsɪntæks ˈdaɪəɡræm/ | แผนภาพไวยากรณ์ |
| Reverse Polish Notation/rɪˈvɜːs ˈpəʊlɪʃ nəʊˈteɪʃn/ | Reverse Polish Notation |
| Backus-Naur Form/ˈbækəs nɔː fɔːm/ | Backus-Naur Form |
| production rules/prəˈdʌkʃn ruːlz/ | กฎการผลิต |
| terminal/ˈtɜːmɪnl/ | terminal |
| non-terminal/nɒn ˈtɜːmɪnl/ | non-terminal symbol |
| infix/ˈɪnfɪks/ | infix notation |
เครื่องหมายProgrammingแบบไม่มีวงเล็บ และไม่มีปัญหาความกำกวม
- เขียน
3 + 4 * 2แล้วคุณกำลังพึ่งพาข้อตกลง: ว่าคูณมีลำดับความสำคัญสูงกว่าบวก หากเปลี่ยนข้อตกลงนี้ ความหมายของนิพจน์จะเปลี่ยนไป - นักตรรกศาสตร์ชาวโปแลนด์ Jan Łukasiewicz แสดงให้เห็นในปี 1920s ว่าหากคุณวาง ตัวดำเนินการอยู่หน้า ตัว operand วงเล็บจะไม่จำเป็น หากกลับด้าน โดยวางตัวดำเนินการ ไว้หลัง จะได้รูปแบบที่เครื่องสามารถประเมินผลได้ด้วยใช้แค่สแต็กเท่านั้น
- นั่นคือเหตุผลว่าทำไม Java Virtual Machine และ interpreter bytecode ส่วนใหญ่จึงทำงานแบบ postfix ไม่มีตารางลำดับความสำคัญ ไม่มีวงเล็บ ไม่มีความกำกวม
- บทเรียนนี้คือวิธีการเขียน ไวยากรณ์ ของภาษาใน BNF และเป็นแผนภาพไวยากรณ์以及如何แปลงและประเมินผล Reverse Polish Notation
Backus-Naur Form
- ไวยากรณ์ (grammar) บอกว่าลำดับใดของทोकènเป็นโปรแกรมที่ถูกต้อง Backus-Naur Form- (BNF) เขียนมันออกมาเป็น กฎการผลิต (production rules):
<symbol> ::= alternative1 | alternative2 | ...
- สัญลักษณ์ เทอมินอล (terminal symbol) คือข้อความจริงที่ปรากฏในโปรแกรม สัญลักษณ์ นอน-เทอมินอล (non-terminal symbol) คือชื่อของกฎอื่น ๆ ที่เขียนไว้ในเครื่องหมายมุม
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<letter> ::= a | b | c | … | z
<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>
ใน BNF สัญลักษณ์ terminal คือ:
Terminal เป็นtoken literal; non-terminal เป็นชื่อของกฎการผลิตอื่น ๆ
Recursion คือวิธีที่ BNF ทำซ้ำ
- BNF ไม่มีสัญลักษณ์ "ทำซ้ำ" ดังนั้นการทำซ้ำจึงเขียนโดยการกำหนดกฎ โดยอ้างอิงถึงตัวเอง
- อ่าน
<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>เป็น: ตัวระบุชื่อ (identifier) คือตัวอักษรเดียว, หรือ ตัวระบุชื่อตามด้วยตัวอักษร, หรือ ตัวระบุชื่อตามด้วยเลข - ทางเลือกเหล่านี้รวมกันหมายถึง "ตัวอักษรตามด้วยตัวอักษรหรือตัวเลขจำนวนเท่าใดก็ได้" ซึ่งอธิบายได้ด้วยว่าทำไมชื่อตัวแปรจึงไม่สามารถ เริ่มต้น ด้วยตัวเลขได้: เพราะไม่มีทางเลือกใดที่อนุญาตให้ทำเช่นนั้น
- แผนภาพไวยากรณ์ (syntax diagram), หรือแผนภาพรถไฟ, แสดงกฎเดียวกันในรูปแบบกราฟิก โดยมีวงวนแทนการใช้ recursion ใน BNF ทั้งสองรูปแบบนี้ เทียบเท่ากัน
วงวนและการ recursion บอกสิ่งเดียวกัน
จับคู่แต่ละพจน์ไวยากรณ์/สัญชาตญาณกับความหมาย
BNF สร้างกฎจาก terminal และ non-terminal (recursion ทำให้เกิดซ้ำ); RPN จัดเรียงใหม่ใน-expression เพื่อลบวงเล็บออก
ทำไมกฎ
ทางเลือกทั้งหมดรวมกันหมายถึงตัวอักษรตามด้วยตัวอักษรหรือเลขจำนวนเท่าใดก็ได้ และไม่มีทางเลือกใดที่อนุญาตให้เริ่มต้นด้วยเลข
ตัวอย่างฝึกหัด: ทดสอบสตริงกับไวยากรณ์
- ใช้กฎข้างต้น, ข้อใดของ
count2,2countและmy_varเป็นตัวระบุชื่อที่ถูกต้อง? count2: ถูกต้อง. สร้างขึ้นทีละส่วน:cเป็น<letter>, ดังนั้นเป็น<identifier>; เพิ่มo,u,n,tโดยใช้ทางเลือกที่สอง; เพิ่ม2โดยใช้ทางเลือกที่สาม2count: ไม่ถูกต้อง. ทุกทางเลือกเริ่มต้นจาก<letter>หรือจาก<identifier>อื่นๆ และไม่มีลำดับใดสามารถเริ่มต้นด้วยเลขmy_var: ไม่ถูกต้อง, เพราะ_ไม่ใช่เทอมินอลในกฎใด ๆ ที่นี่ ให้ระบุกฎที่ล้มเหลว ไม่ใช่แค่บอกว่า "ดูผิด"
ใช้กฎเหล่านั้น ข้อความใดเป็นชื่อตัวแปรที่ถูกต้อง? เลือก ทุก ข้อที่ใช้ได้
ตัวอักษรเดียวเป็นชื่อตัวแปรตามทางเลือกแรก 2count ไม่สามารถเริ่มด้วยเลข และ _ ไม่ใช่ terminal ในกฎใดๆ在这里
Infix และ postfix
- Infix วางตัวดำเนินการระหว่าง operand ของมัน,
3 + 4 * 2, และดังนั้นจึงต้องการ กฎลำดับความสำคัญและวงเล็บ เพื่อให้ไม่มีความกำกวม - Reverse Polish Notation, หรือ postfix, วางตัวดำเนินการ ไว้หลัง operand ของมัน:
3 4 2 * +. มันไม่ต้องการทั้งสองอย่าง - ลำดับที่ตัวดำเนินการปรากฏในรูปแบบ postfix คือ ลำดับที่จะถูกนำไปใช้, وهوสิ่งที่เครื่องต้องการทราบเป๊ะๆ
การแปลง infix เป็น postfix
- ใช้ สแต็กของตัวดำเนินการ (operator stack). สแกนจากซ้ายไปขวา: ส่ง operand ไปยังเอาต์พุตโดยตรง; สำหรับ ตัวดำเนินการ, ให้ pop ตัวดำเนินการที่จัดเรียงในสแต็กที่มี ลำดับความสำคัญสูงกว่าหรือเท่ากัน ไปยังเอาต์พุตก่อน, จากนั้น push ตัวมันเองเข้าไป
- Push วงเล็บเปิด เมื่อเจอวงเล็บปิด ให้ pop ไปยังเอาต์พุตจนกว่าจะเจอวงเล็บเปิดที่จับคู่กัน, จากนั้นทิ้งคู่ของวงเล็บนั้นออก
- ที่ท้ายที่สุด pop สิ่งที่เหลืออยู่ในสแต็กทั้งหมดไปยังเอาต์พุต
ลำดับความสำคัญของการดำเนินการ — สิ่งที่ RPN กำจัดออก
ในการคำนวณ infix ปกติ × และ ÷ มีน้ำหนักมากกว่า + และ − ดังนั้นต้องปฏิบัติตามกฎตามลำดับที่ถูกต้อง สัญชาตญาณ reverse polish เขียนตัวถูกนำหน้า (3 4 2 × + 1 −) ซึ่งกำหนดลำดับให้ชัดเจนโดยไม่ต้องใช้กฎลำดับความสำคัญ
รูปแบบ RPN (postfix) ของนิพจน์ infix (3 + 4) * 2 คืออะไร?
วงบังคับให้ 3+4 ก่อน: 3 4 +, จากนั้นคูณด้วย 2: 3 4 + 2 *
แปลง (A + B) * (C - D) เป็น Reverse Polish Notation โดยใช้ * สำหรับการคูณ
แต่ละวงเล็บถูกแปลงทีละส่วน และการคูณจะถูกดึงออกมา最后是所以它出现在末尾。没有括号幸存下来。
ตัวอย่างฝึกหัด: แปลง, แล้วประเมินผล
- แปลง $(A + B) \times (C - D)$ เป็น RPN. Push
(; outputA; push+; outputB; บน)pop กลับไปที่(ที่จับคู่กัน, ให้ผลลัพธ์A B +. Push×. วงเล็บที่สองทำงานเหมือนกัน, ให้ผลลัพธ์C D -. ที่ท้ายที่สุด pop×. ผลลัพธ์:A B + C D - ×. - ตอนนี้ประเมินผลสำหรับ $A=3, B=4, C=5, D=2$. Push 3, push 4;
+pop ทั้งสองและpush 7. Push 5, push 2;-pop ทั้งสองและpush 3.×pop 7 และ 3 และpush 21 - ตัวดำเนินการจะดึง สองรายการบนสุด เสมอ, และรายการแรกที่ถูกpopคือ operand ฝั่งขวา สิ่งนี้สำคัญสำหรับ
-และ/, حيثลำดับเปลี่ยนคำตอบ
ประเมินนิพจน์ RPN 3 4 2 * +
ดัน 3, 4, 2; * ดึง 4 และ 2 → 8; + ดึง 3 และ 8 → 11
Reverse Polish Notation ไม่ต้องใช้วงเล็บหรือกฎลำดับความสำคัญ และสามารถประเมินโดยตรงด้วย stack
ดันตัวถูก; ตัวดำเนินการแต่ละตัวดึงตัวถูกและดันผลลัพธ์ — ซึ่งตรงกับวิธีการทำงานของเครื่อง stack
การประเมินผลด้วยสแต็ก, ขั้นต่อขั้น
- สแกนจากซ้ายไปขวา: pushแต่ละ operand; บน ตัวดำเนินการ, pop สองรายการบนสุด, นำไปใช้, และ push ผลลัพธ์ ที่ท้ายที่สุดสแต็กจะมีค่าหนึ่งค่า: คำตอบ
| Token | Stack after |
|---|---|
3 |
3 |
4 |
3, 4 |
2 |
3, 4, 2 |
* |
3, 8 |
+ |
11 |
- นี่คือ เครื่องสแต็ก: ไม่มีวงเล็บ, ไม่มีตารางลำดับความสำคัญ, ไม่มีการมองahead. นี่คือวิธีที่ JVM และ interpreter bytecode หลายชนิดประเมินทุกนิพจน์
เมื่อประเมิน RPN รายการแรกที่ถูกดึงออกจาก stack คือตัวถูกด้านซ้ายของตัวดำเนินการ
รายการที่ถูกดึงออกครั้งแรกคือตัวถูกด้านขวา มันไม่สำคัญสำหรับ + และ *, แต่การกลับข้างจะทำให้การลบและการหารผิด
วางขั้นตอนการประเมิน 3 4 2 * + ด้วย stack ให้เป็นลำดับ
ตัวถูกถูกดัน, ตัวดำเนินการแต่ละตัวกินสองด้านบนสุดและปล่อยผลลัพธ์ของมัน ไม่ต้องมีวงเล็บหรือตารางลำดับความสำคัญ
คะแนนที่หลุดหายไป
- เทอมินอล คือข้อความจริง; นอน-เทอมินอล ชื่อกฎอื่น อย่าสลับกัน
- BNF แสดงการทำซ้ำโดย recursion. หากกฎอ้างอิงถึงตัวเอง ให้บอกและอธิบายความหมายของมัน
- ในการประเมินผล ตัวดำเนินการดึง สองรายการบนสุด, และรายการแรกที่ถูกpopคือ operand ฝั่งขวา การสลับสิ่งนี้จะทำให้การลบและการหารผิดพลาด
- RPN ต้องการ ไม่มีวงเล็บ การใส่วงเล็บลงในคำตอบ postfix จะทำให้เสียคะแนนในการทดสอบ
คุณเข้าใจแล้ว
- BNF กฎการผลิตรวม เทอมินอล (ข้อความจริง) และ นอน-เทอมินอล (ชื่อกฎ), และแสดงการทำซ้ำโดย recursion; แผนภาพไวยากรณ์ هوรูปแบบกราฟิกที่เทียบเท่ากัน
- ทดสอบสตริงโดยการสร้างมันจากกฎ, และตั้งชื่อกฎที่ล้มเหลวเมื่อมันไม่ถูกต้อง
- infix ต้องใช้ลำดับความสำคัญและวงเล็บ; RPN (postfix) วางตัวดำเนินการไว้หลัง operand และไม่ต้องการสิ่งเหล่านี้
- แปลงด้วย stack ของตัวดำเนินการ และประเมินผลโดยการดัน operand เข้าไปและใช้แต่ละตัวดำเนินการกับ สองค่าบนสุด โดยค่าที่ถูกดึงออกก่อนเป็น operand ด้านขวา