การวิเคราะห์เชิงคำศัพท์และเชิงวากยสัมพันธ์
การวิเคราะห์เชิงคำศัพท์และเชิงวากยสัมพันธ์เป็นส่วนหน้าของคอมไพเลอร์ โดยจะแยกข้อความต้นฉบับออกเป็นโทเค็นและจดจำโครงสร้างทางไวยากรณ์ในรูปของแผนผังการแยกวิเคราะห์หรือแผนผังวากยสัมพันธ์
Definition
การวิเคราะห์เชิงคำศัพท์เป็นขั้นตอนที่จัดกลุ่มอักขระอินพุตให้เป็นโทเค็น และการวิเคราะห์เชิงวากยสัมพันธ์ (การแยกวิเคราะห์) เป็นขั้นตอนที่พิจารณาว่าโทเค็นเหล่านั้นประกอบกันเป็นโปรแกรมที่ถูกต้องตามไวยากรณ์หรือไม่และอย่างไร โดยสร้างแผนผังวากยสัมพันธ์
Scope
หัวข้อนี้ครอบคลุมการวิเคราะห์เชิงคำศัพท์ ซึ่งแปลงกระแสอักขระให้เป็นโทเค็นโดยใช้ภาษาปกติและออโตมาตาจำกัด และการวิเคราะห์เชิงวากยสัมพันธ์ (การแยกวิเคราะห์) ซึ่งจดจำโครงสร้างวลีของโปรแกรมเทียบกับไวยากรณ์ปราศจากบริบท ซึ่งรวมถึงการแยกวิเคราะห์แบบบนลงล่าง (LL) และล่างขึ้นบน (LR) ตัวสร้างตัวแยกวิเคราะห์ ความกำกวมและการกู้คืนข้อผิดพลาด และการสร้างแผนผังวากยสัมพันธ์เชิงนามธรรม
Core questions
- ภาษาปกติและภาษาปราศจากบริบทถูกนำมาใช้อธิบายโครงสร้างโปรแกรมได้อย่างไร?
- ข้อดีข้อเสียของการแยกวิเคราะห์แบบ LL และ LR มีอะไรบ้าง?
- ความกำกวมและข้อผิดพลาดในการแยกวิเคราะห์ถูกตรวจจับและจัดการอย่างไร?
- แผนผังวากยสัมพันธ์เชิงนามธรรมถูกสร้างขึ้นจากกระแสโทเค็นได้อย่างไร?
Key theories
- การแยกวิเคราะห์แบบ LR
- Knuth ได้นำเสนอการแยกวิเคราะห์แบบ LR ซึ่งเป็นเทคนิคแบบล่างขึ้นบนที่แยกวิเคราะห์ไวยากรณ์ LR ในวงกว้างได้อย่างแม่นยำในเวลาเชิงเส้น ซึ่งเป็นพื้นฐานของตัวสร้างตัวแยกวิเคราะห์จำนวนมาก
- การแยกวิเคราะห์ปราศจากบริบททั่วไป
- อัลกอริทึมของ Earley แยกวิเคราะห์ไวยากรณ์ปราศจากบริบทแบบใดก็ได้ รวมถึงไวยากรณ์ที่มีความกำกวม ซึ่งเป็นวิธีการทั่วไปเมื่อตัวแยกวิเคราะห์แบบกำหนดที่จำกัดไม่เพียงพอ
- รากฐานของภาษาปกติและภาษาปราศจากบริบทของส่วนหน้า
- หนังสือ Dragon Book ได้จัดระบบการใช้ regular expressions และ finite automata สำหรับการสแกน และ context-free grammars สำหรับการแยกวิเคราะห์ รวมถึงอัลกอริทึมการสร้าง LL และ LR มาตรฐาน
Clinical relevance
การแยกคำศัพท์และการแยกวิเคราะห์เป็นพื้นฐานไม่เพียงแต่สำหรับคอมไพเลอร์เท่านั้น แต่ยังรวมถึงอินเทอร์พรีเตอร์, ลินเทอร์, ฟอร์แมตเตอร์, IDEs และตัวประมวลผลรูปแบบข้อมูลด้วย การแยกวิเคราะห์ที่แข็งแกร่งพร้อมการกู้คืนข้อผิดพลาดที่ดีเป็นสิ่งจำเป็นสำหรับประสบการณ์ของนักพัฒนาในการใช้เครื่องมือภาษาใดๆ
History
ลำดับชั้นของภาษาเชิงรูปนัยของ Chomsky ในช่วงปลายทศวรรษ 1950 ได้ให้ทฤษฎีของภาษาปกติและภาษาปราศจากบริบท Knuth ได้กำหนด LR parsing อย่างเป็นทางการในปี 1965 และ Earley ได้นำเสนออัลกอริทึมปราศจากบริบททั่วไปในปี 1970 ตัวสร้างตัวแยกวิเคราะห์เช่น yacc ทำให้ LR parsing สามารถนำไปใช้ได้จริง ในขณะที่งานวิจัยต่อมาได้สำรวจไวยากรณ์การแสดงออกของการแยกวิเคราะห์และตัวแยกวิเคราะห์แบบ combinator
Debates
- ตัวแยกวิเคราะห์ที่สร้างขึ้นเทียบกับตัวแยกวิเคราะห์ที่เขียนด้วยมือ
- ผู้ปฏิบัติงานถกเถียงกันเรื่องการใช้ตัวสร้างตัวแยกวิเคราะห์จากไวยากรณ์เชิงรูปนัย ซึ่งกระชับและตรวจสอบได้ เทียบกับตัวแยกวิเคราะห์แบบ recursive-descent ที่เขียนด้วยมือ ซึ่งมักจะให้ข้อความแสดงข้อผิดพลาดและการควบคุมที่ดีกว่า แต่ต้องแลกมาด้วยโค้ดที่มากขึ้น
Key figures
- Donald Knuth
- Jay Earley
- Alfred Aho
- Noam Chomsky
Related topics
Seminal works
- knuth1965
- earley1970
- aho2006
Frequently asked questions
- lexer และ parser แตกต่างกันอย่างไร?
- lexer จะจัดกลุ่มอักขระดิบให้เป็นโทเค็น เช่น ตัวระบุและตัวดำเนินการ ในขณะที่ parser จะจัดเรียงโทเค็นเหล่านั้นให้เป็นแผนผังวากยสัมพันธ์แบบลำดับชั้นตามไวยากรณ์ของภาษา
- การแยกวิเคราะห์แบบ LL และ LR แตกต่างกันอย่างไร?
- ตัวแยกวิเคราะห์แบบ LL ทำงานแบบบนลงล่าง โดยคาดการณ์การผลิตจากคำนำหน้าอินพุต ในขณะที่ตัวแยกวิเคราะห์แบบ LR ทำงานแบบล่างขึ้นบน โดยลดสตริงย่อยที่รู้จัก; LR จัดการไวยากรณ์ประเภทที่ใหญ่กว่าอย่างเคร่งครัด แต่มีความซับซ้อนในการสร้างมากกว่า