ห้อยลงมาอย่างอื่น
ประโยคelse ที่วางผิดตำแหน่งเป็นปัญหาในการเขียน โปรแกรม สร้างตัวแยกวิเคราะห์ซึ่งประโยค else ที่เป็นตัวเลือกใน คำสั่ง if–then(–else)อาจทำให้คำสั่งเงื่อนไขที่ซ้อนกันนั้นกำกวม ในทางทฤษฎีแล้ว ไวยากรณ์แบบบริบทอิสระ อ้างอิง ของภาษานั้นกำกวม หมายความว่ามีโครงสร้าง ต้นไม้การแยกวิเคราะห์ที่ถูกต้องมากกว่าหนึ่งแบบ
คำอธิบาย
ในภาษาโปรแกรม หลายภาษา เราสามารถเขียนโค้ดที่ทำงานโดยมีเงื่อนไขได้สองรูปแบบ คือ รูปแบบ if-then หรือรูปแบบ if-then-else (ส่วน else เป็นส่วนเสริม)
ถ้า a แล้ว s ถ้า b แล้ว s1 มิฉะนั้น s2
การตีความที่คลุมเครืออาจเกิดขึ้นได้เมื่อมีคำสั่งซ้อนกัน โดยเฉพาะอย่างยิ่งเมื่อรูปแบบ if-then-else เข้ามาแทนที่คำสั่งsภายในโครงสร้าง if-then ด้านบน:
ถ้า a แล้วถ้า b แล้ว s1 มิฉะนั้น s2
ในตัวอย่างนี้ คำs1สั่ง `if` จะถูกดำเนินการก็ต่อ เมื่อ `if` aเป็นจริงและb `if` เป็นจริงเท่านั้น แต่ถ้าเป็น `if` ล่ะs2? คนหนึ่งอาจมั่นใจว่าคำสั่ง `if` s2จะถูกดำเนินการเมื่อใดก็ตาม ที่ `if` เป็นเท็จ a(โดยการเพิ่ม ` else` ต่อท้าย `if`ตัวแรก) ในขณะที่อีกคนหนึ่งอาจมั่นใจว่า คำสั่ง `if` s2จะถูกดำเนินการก็ต่อเมื่อ `if` aเป็นจริงและb `if` เป็นเท็จเท่านั้น (โดยการเพิ่ม ` else` ต่อท้าย `if`ตัวที่สอง) กล่าวอีกนัยหนึ่ง ใครบางคนอาจตีความประโยคก่อนหน้านี้ว่าเทียบเท่ากับประโยคใดประโยคหนึ่งต่อไปนี้อย่างชัดเจน:
ถ้า a แล้ว { ถ้า b แล้ว s1 } มิฉะนั้น s2 ถ้า a แล้ว { ถ้า b แล้ว s1 มิฉะนั้น s2 }ปัญหา dangling-else ย้อนกลับไปถึงALGOL 60 [ 1 ]และภาษาที่ตามมาได้แก้ไขปัญหานี้ด้วยวิธีต่างๆ ในตัวแยกวิเคราะห์ LR นั้น dangling else เป็นตัวอย่างต้นแบบของ ความขัดแย้ง แบบshift-reduce
ตัวอย่าง
ตัวอย่างที่เป็นรูปธรรมมีดังต่อไปนี้
ซี
ในภาษาซีไวยากรณ์ระบุไว้บางส่วนดังนี้:
คำสั่ง = ... | คำสั่งเลือก คำสั่งเลือก = ... | คำสั่ง IF (นิพจน์) | คำสั่ง IF (นิพจน์) คำสั่ง ELSE
ดังนั้น โดยไม่ต้องมีกฎเกณฑ์เพิ่มเติม คำกล่าวนี้จึงเป็นดังนี้
ถ้า( a ) ถ้า( b ) s ; มิฉะนั้นs2 ;อาจตีความได้อย่างคลุมเครือราวกับว่าเป็นอย่างใดอย่างหนึ่งดังต่อไปนี้:
ถ้า( a ) { ถ้า( b ) s ; มิฉะนั้นs2 ; }หรือ:
ถ้า( a ) { ถ้า( b ) s ; } มิฉะนั้นs2 ;มาตรฐาน C ชี้แจงว่าelseบล็อกจะเชื่อมโยงกับบล็อกที่ใกล้ที่สุดif[ 2 ] ดังนั้นจึงเลือกต้นไม้แรก
แนวทางในการหลีกเลี่ยงปัญหา
หลีกเลี่ยงความกำกวมในขณะที่ยังคงรักษารูปแบบไวยากรณ์ไว้
ปัญหานี้มักเกิดขึ้นในการสร้างคอมไพเลอร์โดยเฉพาะอย่าง ยิ่ง การแยกวิเคราะห์แบบไร้สแกนเนอร์ ธรรมเนียมปฏิบัติเมื่อจัดการกับ else ที่ค้างอยู่คือการแนบ else เข้ากับคำสั่ง if ที่อยู่ใกล้เคียง[ 3 ] ซึ่งช่วยให้ไวยากรณ์แบบไร้บริบทมีความชัดเจนยิ่งขึ้น โดยเฉพาะอย่างยิ่ง ภาษาโปรแกรมเช่น Pascal [ 4 ] C [ 2 ]และ Java [ 5 ]ปฏิบัติตามธรรมเนียมนี้ ดังนั้นจึงไม่มีความกำกวมในความหมายของภาษาแม้ว่าการใช้ตัวสร้างตัวแยกวิเคราะห์อาจนำไปสู่ไวยากรณ์ ที่กำกวมได้ ในกรณีเหล่านี้ การจัดกลุ่มทางเลือกจะทำได้โดยบล็อกที่ชัดเจน เช่นbegin...endใน Pascal [ 6 ]และ{...}ใน C
วิธีการแก้ไขเพื่อหลีกเลี่ยงความกำกวมอาจแตกต่างกันไปขึ้นอยู่กับแนวทางการสร้างคอมไพเลอร์:
- หากตัวแยกวิเคราะห์ถูกสร้างขึ้นโดยตัวสร้างตัวแยกวิเคราะห์ SLR, LR(1) หรือ LALR LRโปรแกรมเมอร์มักจะอาศัยคุณสมบัติของตัวแยกวิเคราะห์ที่สร้างขึ้นโดยให้ความสำคัญกับการเลื่อนมากกว่าการลดเมื่อใดก็ตามที่มีความขัดแย้ง[ 3 ]หรืออีกทางหนึ่ง ไวยากรณ์สามารถเขียนใหม่เพื่อขจัดความขัดแย้งได้ โดยแลกกับการเพิ่มขนาดของไวยากรณ์ (ดูด้านล่าง )
- หากเขียนโปรแกรมแยกวิเคราะห์ด้วยมือ โปรแกรมเมอร์อาจใช้ ไวยากรณ์แบบ ไร้บริบทที่ไม่กำกวม หรืออาจใช้ไวยากรณ์แบบมีบริบท หรือไวยากรณ์นิพจน์การแยกวิเคราะห์ก็ได้
หลีกเลี่ยงความกำกวมโดยการเปลี่ยนไวยากรณ์
ปัญหานี้ยังสามารถแก้ไขได้โดยทำให้การเชื่อมโยงระหว่าง else และ if ชัดเจนขึ้นภายในไวยากรณ์ ซึ่งโดยปกติจะช่วยหลีกเลี่ยงข้อผิดพลาดของมนุษย์ได้[ 7 ]
แนวทางแก้ไขที่เป็นไปได้มีดังนี้:
- มีสัญลักษณ์ "end if" ที่ใช้กำหนดจุดสิ้นสุดของโครงสร้าง if ตัวอย่างของภาษาโปรแกรมดังกล่าว ได้แก่ALGOL 68 , Ada , Eiffel , PL/SQL , Visual Basic , Modula-2และAppleScript
- ไม่อนุญาตให้คำสั่งที่ตามหลัง "then" เป็น "if" เอง (อย่างไรก็ตาม อาจเป็นวงเล็บคำสั่งคู่หนึ่งที่มีเฉพาะข้อความ if-then เท่านั้น) การใช้งานALGOL 60 บางส่วน ใช้วิธีการนี้[ 8 ]
- ต้องใช้วงเล็บปีกกา (วงเล็บ) เมื่อ "else" ตามหลัง "if" [ 9 ]
- กำหนดให้ทุกเงื่อนไข "if" ต้องมีเงื่อนไข "else" ควบคู่ไปด้วย
- การใช้คีย์เวิร์ดที่แตกต่างกันสำหรับคำสั่ง "if" แบบทางเลือกเดียวและแบบสองทางเลือกS-algolใช้
if e do sสำหรับกรณีทางเลือกเดียวและif e1 then e2 else e3สำหรับกรณีทั่วไป[ 10 ] - กำหนดให้ต้องใช้เครื่องหมายวงเล็บปีกกาโดยไม่มีเงื่อนไข เช่นเดียวกับในSwiftและRustซึ่งในทางปฏิบัติแล้วก็เป็นเช่นนั้นในPythonเนื่องจากกฎการเยื้องของ Python จะกำหนดขอบเขตของทุกบล็อก ไม่ใช่เฉพาะบล็อกที่อยู่ในคำสั่ง "if" เท่านั้น
การหลีกเลี่ยงความขัดแย้งในตัวแยกวิเคราะห์ LR
ตัวอย่างข้างต้นสามารถเขียนใหม่ได้ดังนี้เพื่อขจัดความกำกวม :
แถลงการณ์: เปิดแถลงการณ์ | ปิดคำแถลง ; open_statement: IF '(' expression ')' statement | ถ้า '(' expression ')' closed_statement มิฉะนั้น open_statement ; คำสั่งปิด: ไม่ใช่คำสั่ง if | IF '(' expression ')' closed_statement ELSE closed_statement ; คำสั่งที่ไม่ใช่ if: ... ; กฎไวยากรณ์อื่นๆ ที่เกี่ยวข้องกับประโยคคำสั่ง อาจต้องทำซ้ำในลักษณะนี้เช่นกัน หากกฎเหล่านั้นอาจลงท้ายด้วย a statementหรือselection-statementอักขระที่ไม่ใช่เทอร์มินัล โดยตรงหรือโดยอ้อม
อย่างไรก็ตาม เราได้ให้ไวยากรณ์ที่รวมทั้งคำสั่ง if และ while ไว้ด้วย
แถลงการณ์: เปิดแถลงการณ์ | ปิดคำแถลง ; open_statement: IF '(' expression ')' statement | ถ้า '(' expression ')' closed_statement มิฉะนั้น open_statement | ในขณะที่ '(' นิพจน์ ')' เปิดคำสั่ง ; คำสั่งปิด: คำสั่งง่ายๆ | IF '(' expression ')' closed_statement ELSE closed_statement | ในขณะที่ '(' นิพจน์ ')' ปิดคำสั่ง ; คำสั่งง่ายๆ: ... ; สุดท้ายนี้ เราจะนำเสนอหลักไวยากรณ์ที่ห้ามใช้คำสั่ง IF ที่กำกวม
แถลงการณ์: เปิดแถลงการณ์ | ปิดคำแถลง ; open_statement: IF '(' expression ')' statement | ถ้า '(' expression ')' closed_statement มิฉะนั้น open_statement | ในขณะที่ '(' นิพจน์ ')' เปิดคำสั่ง ; คำสั่งปิด: คำสั่งง่ายๆ | IF '(' expression ')' closed_statement ELSE closed_statement | ในขณะที่ '(' นิพจน์ ')' ปิดคำสั่ง ; คำสั่งง่ายๆ: ... ; ด้วยไวยากรณ์นี้ ประโยคif (a) if (b) c else dสามารถแยกวิเคราะห์ได้เพียงวิธีเดียวเท่านั้น เพราะการตีความอีกแบบหนึ่ง ( if (a) {if (b) c} else d) จะเกิดขึ้นเป็น
คำแถลง แถลงการณ์เปิด ถ้า '(' expression ')' closed_statement มิฉะนั้น open_statement 'ถ้า' '(' 'a' ')' ปิดคำสั่ง 'มิฉะนั้น' 'd' จากนั้นการแยกวิเคราะห์ล้มเหลวเมื่อพยายามจับคู่closed_statementกับ "ถ้า (b) c" การลองใช้ก็closed_statementล้มเหลวในลักษณะเดียวกัน การแยกวิเคราะห์อื่น ๆif (a) {if (b) c else d}) สำเร็จ:
คำแถลง แถลงการณ์เปิด คำสั่ง IF '(' expression ')' IF '(' expression ')' closed_statement ถ้า '(' a ')' (ถ้า '(' expression ')' ปิดคำสั่ง มิฉะนั้น ปิดคำสั่ง) ถ้า '(' a ')' (ถ้า '(' b ')' c มิฉะนั้น 'd')