ตัวสร้างพาร์เซอร์ก็สร้างข้อความผิดพลาดที่ดีได้เช่นกัน

คำแปลของบทความที่ Russ Cox นักพัฒนาภาษา Go โพสต์ไว้ในปี 2010.

• เคยมีความเชื่อผิด ๆ แพร่หลายอยู่ว่าตัวสร้างไวยากรณ์อย่าง yacc ไม่สามารถสร้างข้อความผิดพลาดทางไวยากรณ์ที่ดีได้

• แต่ปัญหานี้เป็นปัญหาที่ Clinton Jeffery แก้ไปแล้วตั้งแต่ปี 2003 และไม่ใช่ปัญหาที่ต้องเขียนพาร์เซอร์ด้วยมือเพื่อแก้ไข

• หากค้นหาเนื้อหาที่ตรงกับสถานะและโทเค็นอินพุตในตาราง ก็สามารถใช้ข้อความผิดพลาดที่ดีกว่าข้อความไวยากรณ์ผิดพลาดแบบธรรมดาได้

[lifthrasiir]

(ต่อไปนี้คือการเรียบเรียงเนื้อหาที่เขียนไว้ในเซิร์ฟเวอร์ Discord ของ Rust เกาหลี)

ปัญหาใหญ่ที่สุดของบทความนี้ก็คือ แล้ว Go ใช้ parser generator อยู่ตอนนี้หรือเปล่า คำตอบคือไม่ ยังไง parser หลักของ Go ก็ยังเขียนด้วยมืออยู่เหมือนเดิม ผมเองก็ไม่ค่อยแน่ใจเหตุผลนัก แต่มีความเป็นไปได้สูงว่า ต่อให้ rsc จะโอเค นักพัฒนา Go คนอื่น ๆ ก็ไม่ได้คิดว่าโอเคตาม

ถ้าจะเทียบกับคอมไพเลอร์ ไอเดียของ Jeffrey ก็พอจะเทียบได้กับ peephole optimizer ก่อนจะปล่อย machine code ออกมา มันจะเก็บคำสั่ง machine code ที่เพิ่งปล่อยล่าสุดไว้จำนวนคงที่จำนวนหนึ่ง (เพราะมันแอบมองหน้าต่างนั้นผ่านรู peep hole จึงได้ชื่อนี้) แล้วถ้าเห็นแพตเทิร์นบางอย่างก็จะแทนที่คำสั่งนั้นตรงจุดนั้นด้วยคำสั่งที่เร็วกว่า peephole optimizer เป็นเครื่องมือที่สะดวกและใช้ร่วมกับ optimization pass ทั่วไปแบบอื่นได้ แต่ต่อให้มีแค่ peephole optimizer อย่างเดียว ก็ไม่สามารถทำ optimization ทุกชนิดที่คอมไพเลอร์ต้องการได้ เช่นเดียวกัน วิธีสร้างข้อผิดพลาดจากโทเค็นล่าสุดก็ไม่สามารถครอบคลุม parsing error ได้ทั้งหมด ยิ่งไปกว่านั้น นี่เป็นแนวทางอิสระที่นำไปประยุกต์ใช้ได้แม้ไม่ใช่ parser generator ดังนั้นการอ้างว่าเพียงเพราะมีแนวทางนี้อยู่ ปัญหาของ parser generator จึงหายไปแล้ว จึงไม่ถูกต้อง

โดยส่วนตัว ผมไม่ได้คิดว่าแนวคิดของ parser generator นั้นแย่ แต่คิดว่าปัญหาอยู่ที่แนวคิดที่ parser generator "บังคับ" ให้ต้องตามมากกว่า เวลาเขียน parser ไม่ว่าจะสร้างด้วย generator หรือเขียนด้วยมือ เราก็ต้องคำนึงถึง left recursion และ right recursion อยู่ดี และไม่สามารถนำไวยากรณ์ที่ "เป็นธรรมชาติ" มาแปลงเป็นโค้ดได้ตรง ๆ แต่การเขียนด้วยมือคือการยอมรับข้อจำกัดนั้นตั้งแต่แรก ทว่าถ้าใช้ parser generator แล้วก็ยังต้องเขียนให้ตรงกับส่วนย่อยของ "ไวยากรณ์" ที่ผูกติดกับอัลกอริทึมการ parse แบบเฉพาะอย่าง LL/LR ข้อดีของ generator ก็จะลดลงไปมาก (อัลกอริทึมอย่าง GLR ช่วยให้หายใจคล่องขึ้นบ้าง แต่ก็ยังมีข้อจำกัดอยู่) ที่ปัจจุบันภาษาในระดับ production ส่วนใหญ่ไม่ใช้ parser generator หรือบางครั้งก็ใช้แนวทางอย่าง PEG ซึ่งถึงจะเป็น parser generator แต่ก็ แทบไม่ได้ ใช้ข้อดีแบบทั่วไปของ generator เลยนั้น ล้วนมีเหตุผลทั้งสิ้น

[dynalloc]

ผมเข้าใจได้ว่าบางคนไม่ใช้ parser generator เพราะไม่อยากผูกติดกับไวยากรณ์ที่มันจำกัดไว้ แต่การอ้างว่า parser generator กำลังบังคับให้ผู้ใช้ต้องใช้ไวยากรณ์แบบใดแบบหนึ่งก็ดูแปลกอยู่ดี

parser generator เกิดขึ้นมาเพื่อช่วยแก้ปัญหาที่การสร้างตารางพาร์สสำหรับไวยากรณ์แบบ LR ซึ่งมีข้อดีคือพาร์สได้ในเวลาเชิงเส้นนั้นยากมาก ไม่ได้มีไว้เพื่อสร้างตัวพาร์สสำหรับไวยากรณ์แบบ context-sensitive ที่การพาร์สไม่เป็นแบบกำหนดแน่นอน หรือสร้างตัวพาร์สแบบเรียกซ้ำที่ไม่รู้ด้วยซ้ำว่าจะจบการพาร์สเมื่อไร ซึ่งคงไม่ใช่สิ่งที่นักวิจัยหรือนักพัฒนา parser generator สนใจนัก

ดังนั้นผมคิดว่า parser generator ไม่ใช่โปรแกรมที่ยึดติดกับไวยากรณ์แบบ LR หรือ LALR ที่ไม่เป็นธรรมชาติแล้วนำมาบังคับใช้ แต่กำลังทำหน้าที่ของมันได้ดีในฐานะเครื่องมือสำหรับแก้ปัญหาที่ยากมากอย่างการพาร์สแบบเวลาเชิงเส้นและการสร้างตารางพาร์สเพื่อสิ่งนั้น

[lifthrasiir]

ภาษาแทบทุกภาษาที่พบได้ในโลกความเป็นจริงมีไวยากรณ์แบบ LL(1) จึงสามารถพาร์สแบบเวลาเชิงเส้นได้โดยไม่ต้องใช้ LR parser (ไม่ได้หมายความว่าไวยากรณ์ที่นิยมใช้กับภาษานั้นจะเป็น LL(1)) ดังนั้นคำกล่าวที่ว่าจำเป็นต้องใช้ LR parser เพื่อให้พาร์สแบบเวลาเชิงเส้นได้ แต่สร้าง parsing table ได้ยากจึงต้องมีตัวสร้าง จึงเป็นการสลับลำดับเหตุและผล อีกทั้งกระบวนการสร้าง parsing table เองก็ไม่ได้ซับซ้อนโดยเนื้อแท้ (สิ่งที่ยากคือการพิสูจน์อัลกอริทึม)