ภาษาไม่พึ่งบริบทและพุชดาวน์ออโตมาตา

ไวยากรณ์ไม่พึ่งบริบทสร้างภาษาที่มีโครงสร้างแบบซ้อนและเรียกซ้ำ และพุชดาวน์ออโตมาตาสามารถจดจำภาษาเหล่านี้ได้อย่างแม่นยำโดยการเพิ่มสแตกที่ไม่จำกัดขนาดเข้าไปในการควบคุมแบบจำกัด

Definition

ภาษาไม่พึ่งบริบทถูกสร้างขึ้นโดยไวยากรณ์ที่มีกฎการเขียนซ้ำสัญลักษณ์ที่ไม่ใช่เทอร์มินัลเพียงตัวเดียวโดยไม่ขึ้นกับบริบท และถูกจดจำโดยพุชดาวน์ออโตมาตา ซึ่งเป็นออโตมาตาจำกัดที่ติดตั้งสแตกที่ให้หน่วยความจำแบบเข้าหลังออกก่อนที่มีความลึกไม่จำกัด

Scope

หัวข้อนี้ครอบคลุมไวยากรณ์ไม่พึ่งบริบทและการสร้างคำ, ผังการแยกวิเคราะห์และความกำกวม, ความสมมูลของไวยากรณ์ไม่พึ่งบริบทกับพุชดาวน์ออโตมาตา, รูปแบบมาตรฐาน เช่น รูปแบบมาตรฐานของชอมสกี, เลมมาการปั๊มสำหรับภาษาไม่พึ่งบริบท, และคุณสมบัติการปิดและการตัดสินใจที่แยกแยะคลาสนี้ออกจากภาษาปกติ

Core questions

• รูปแบบการซ้อนหรือการเรียกซ้ำแบบใดที่ต้องใช้สแตกแทนหน่วยความจำจำกัด?
• เหตุใดไวยากรณ์ไม่พึ่งบริบทและพุชดาวน์ออโตมาตาจึงมีพลังเทียบเท่ากัน?
• ไวยากรณ์จะกำกวมเมื่อใด และเหตุใดความกำกวมจึงมีความสำคัญต่อการแยกวิเคราะห์?
• ปัญหาการตัดสินใจใดบ้างสำหรับภาษาไม่พึ่งบริบทที่สามารถแก้ไขได้ และปัญหาใดบ้างที่ไม่สามารถแก้ไขได้?

Key theories

ความสมมูลของไวยากรณ์–ออโตมาตา

ภาษาจะเป็นภาษาไม่พึ่งบริบทก็ต่อเมื่อภาษานั้นถูกยอมรับโดยพุชดาวน์ออโตมาตาบางตัว ดังนั้นมุมมองของไวยากรณ์เชิงกำเนิดและมุมมองของเครื่องจักรแบบสแตกจึงอธิบายคลาสของภาษาเดียวกัน

รูปแบบมาตรฐานของชอมสกี

ไวยากรณ์ไม่พึ่งบริบททุกตัวสามารถเขียนใหม่ได้เพื่อให้แต่ละกฎสร้างได้ทั้งสองสัญลักษณ์ที่ไม่ใช่เทอร์มินัลหรือเทอร์มินัลเดี่ยว ซึ่งเป็นรูปแบบมาตรฐานที่เป็นพื้นฐานของอัลกอริทึมการแยกวิเคราะห์และการพิสูจน์แบบอุปนัยเกี่ยวกับคลาสนี้

เลมมาการปั๊มสำหรับภาษาไม่พึ่งบริบท

ทุกสตริงที่ยาวพอในภาษาไม่พึ่งบริบทสามารถแบ่งออกได้เพื่อให้ส่วนสองส่วนของมันถูกปั๊มเข้าด้วยกัน ซึ่งเป็นคุณสมบัติที่ล้มเหลวสำหรับภาษาที่ต้องการหน่วยความจำมากกว่าสแตก และดังนั้นจึงพิสูจน์ได้ว่าไม่ใช่ภาษาไม่พึ่งบริบท

Clinical relevance

ไวยากรณ์ไม่พึ่งบริบทระบุไวยากรณ์ของภาษาโปรแกรมเกือบทุกภาษาและรูปแบบข้อมูลจำนวนมาก และอัลกอริทึมการแยกวิเคราะห์แบบพุชดาวน์จะเปลี่ยนไวยากรณ์เหล่านี้ให้เป็นตัววิเคราะห์ไวยากรณ์ที่เป็นหัวใจสำคัญของคอมไพเลอร์และอินเทอร์พรีเตอร์ ทำให้หัวข้อนี้เป็นรากฐานทางทฤษฎีของการประมวลผลภาษาโปรแกรม

History

ชอมสกีได้นำเสนอไวยากรณ์ไม่พึ่งบริบทในช่วงปลายทศวรรษ 1950 ซึ่งเป็นส่วนหนึ่งของลำดับชั้นของเขา และแบกคัสกับนอร์ได้นำไปใช้โดยอิสระเพื่อกำหนดไวยากรณ์ของภาษาโปรแกรม ALGOL ความสมมูลกับพุชดาวน์ออโตมาตาและทฤษฎีโครงสร้างของคลาสนี้ได้รับการพัฒนาตลอดทศวรรษ 1960

Key figures

• Noam Chomsky
• John Backus
• Seymour Ginsburg
• Sheila Greibach

Seminal works

• sipser2013
• hopcroft2006

Frequently asked questions

เหตุใดการแยกวิเคราะห์ภาษาโปรแกรมจึงต้องใช้สแตก?

โปรแกรมประกอบด้วยโครงสร้างที่ซ้อนกัน เช่น วงเล็บ, บล็อก, และการเรียกฟังก์ชัน ซึ่งมีความลึกของการจับคู่ที่ไม่จำกัด สแตกจะบันทึกโครงสร้างที่ยังไม่เสร็จสิ้นแต่ละรายการและนำออกเมื่อปิด ซึ่งเป็นระเบียบวินัยของหน่วยความจำที่พุชดาวน์ออโตมาตามีให้และออโตมาตาจำกัดไม่มี

ไวยากรณ์กำกวมหมายความว่าอย่างไร?

ไวยากรณ์จะกำกวมเมื่อสตริงบางสตริงมีผังการแยกวิเคราะห์มากกว่าหนึ่งผัง ซึ่งหมายความว่าสามารถสร้างขึ้นได้ด้วยโครงสร้างที่แตกต่างกันอย่างแท้จริง ความกำกวมไม่เป็นที่พึงปรารถนาสำหรับภาษาโปรแกรมเนื่องจากทำให้ความหมายของโค้ดไม่ชัดเจน ดังนั้นผู้ออกแบบภาษาจึงแสวงหาไวยากรณ์ที่ไม่กำกวมหรือเพิ่มกฎการขจัดความกำกวม