การวิเคราะห์ไวยากรณ์: ประเภทการแยกวิเคราะห์จากบนลงล่างและล่างขึ้นบนของคอมไพเลอร์

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

ทำไมคุณถึงต้องการตัววิเคราะห์ไวยากรณ์?

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

คำศัพท์เฉพาะตัววิเคราะห์ไวยากรณ์ที่สำคัญ

คำศัพท์สำคัญที่ใช้ในกระบวนการวิเคราะห์ไวยากรณ์:

• ประโยค: ประโยคคือกลุ่มของอักขระเหนือตัวอักษรบางตัว

• คำศัพท์: ศัพท์คือหน่วยวากยสัมพันธ์ระดับต่ำสุดของภาษา (เช่น ผลรวม เริ่มต้น)

• Token: โทเค็นเป็นเพียงหมวดหมู่ของคำศัพท์

• คำสำคัญและคำสงวน – เป็นตัวระบุที่ใช้เป็นส่วนคงที่ของไวยากรณ์ของคำสั่ง เป็นคำสงวนซึ่งคุณไม่สามารถใช้เป็นชื่อตัวแปรหรือตัวระบุได้

• คำพูดที่น่ารำคาญ – คำที่รบกวนเป็นตัวเลือกซึ่งจะแทรกลงในคำสั่งเพื่อให้อ่านประโยคได้ง่ายขึ้น

• ความคิดเห็น – เป็นส่วนสำคัญของเอกสาร ส่วนใหญ่จะแสดงด้วย /* */ หรือ//Blank (ช่องว่าง)

• ตัวคั่น – เป็นองค์ประกอบวากยสัมพันธ์ที่ทำเครื่องหมายจุดเริ่มต้นหรือจุดสิ้นสุดของหน่วยวากยสัมพันธ์บางหน่วย เช่นเดียวกับคำสั่งหรือสำนวน “begin”…”end” หรือ {}

• ชุดตัวอักษร – ASCII, ยูนิโค้ด

• ตัวบ่งชี้ – เป็นข้อจำกัดด้านความยาวซึ่งช่วยให้คุณลดความสามารถในการอ่านประโยคได้

• Operaสัญลักษณ์ทอร์ – + และ – ดำเนินการคำนวณพื้นฐานสองอย่าง
• องค์ประกอบทางวากยสัมพันธ์ของภาษา

ทำไมเราต้องแยกวิเคราะห์?

การแยกวิเคราะห์ยังตรวจสอบว่าสตริงอินพุตมีรูปแบบที่ถูกต้อง และหากไม่เป็นเช่นนั้น ให้ปฏิเสธ

ต่อไปนี้เป็นงานสำคัญที่ดำเนินการโดยตัววิเคราะห์ในการออกแบบคอมไพเลอร์:

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

เทคนิคการแยกวิเคราะห์

เทคนิคการแยกวิเคราะห์แบ่งออกเป็นสองกลุ่ม:

• การแยกวิเคราะห์จากบนลงล่าง
• การแยกวิเคราะห์จากล่างขึ้นบน

การแยกจากบนลงล่าง

ในโครงสร้างการแยกวิเคราะห์จากบนลงล่างของต้นไม้แยกเริ่มต้นที่รากแล้วดำเนินการต่อไปทางใบ

การแยกวิเคราะห์จากบนลงล่างสองประเภทคือ:

1. การแยกวิเคราะห์แบบคาดการณ์:

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

2. การแยกวิเคราะห์โคตรแบบเรียกซ้ำ:

เทคนิคการแยกวิเคราะห์นี้จะแยกวิเคราะห์อินพุตซ้ำเพื่อสร้างแผนผังคำสรรเสริญ ประกอบด้วยฟังก์ชันเล็กๆ หลายฟังก์ชัน หนึ่งฟังก์ชันสำหรับแต่ละ nonterminal ในไวยากรณ์

การแยกวิเคราะห์จากล่างขึ้นบน

ในการวิเคราะห์แบบ Bottom Up ในการออกแบบคอมไพเลอร์ การสร้าง Parse Tree จะเริ่มต้นด้วย Leave จากนั้นจึงประมวลผลไปยัง Root เรียกอีกอย่างว่าการวิเคราะห์แบบ Shift-Reduce การวิเคราะห์ประเภทนี้ในการออกแบบคอมไพเลอร์จะสร้างขึ้นด้วยความช่วยเหลือของการใช้บางอย่าง เครื่องมือซอฟต์แวร์.

ข้อผิดพลาด – วิธีการกู้คืน

ข้อผิดพลาดทั่วไปที่เกิดขึ้นในการแยกวิเคราะห์ซอฟต์แวร์ระบบ

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

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

การกู้คืนโหมดคำสั่ง

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

การกู้คืนโหมดตื่นตระหนก

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

การกู้คืนระดับวลี

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

ข้อผิดพลาดโปรดักชั่น

• การกู้คืนการผลิตข้อผิดพลาดจะขยายไวยากรณ์สำหรับภาษาที่สร้างโครงสร้างที่ผิดพลาด จากนั้นตัววิเคราะห์จะดำเนินการวินิจฉัยข้อผิดพลาดเกี่ยวกับโครงสร้างนั้น

การแก้ไขทั่วโลก

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

ไวยากรณ์

ไวยากรณ์คือชุดของกฎโครงสร้างที่อธิบายภาษา ไวยากรณ์กำหนดโครงสร้างของประโยค คำนี้ยังหมายถึงการศึกษากฎเหล่านี้ และไฟล์นี้รวมถึงสัณฐานวิทยา เสียงวิทยา และไวยากรณ์ สามารถอธิบายไวยากรณ์ได้หลายอย่าง การเขียนโปรแกรมภาษา.

กฎของแบบฟอร์มไวยากรณ์

• สัญลักษณ์ที่ไม่ใช่เทอร์มินัลควรปรากฏทางด้านซ้ายของการผลิตอย่างน้อยหนึ่งรายการ
• ไม่ควรแสดงสัญลักษณ์เป้าหมายที่ด้านขวาของ ::= ของการผลิตใดๆ
• กฎจะเกิดซ้ำหาก LHS ปรากฏใน RHS

อนุสัญญาสัญกรณ์

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

เป็นทางเลือกทางเลือกซึ่งอาจใช้สัญลักษณ์ภายในกฎข้อเดียว อาจอยู่ในวงเล็บ ([,] ) เมื่อจำเป็น

เทอร์มินัลพื้นที่การประชุมเชิงสัญลักษณ์สองประเภทและเทอร์มินัลที่ไม่ใช่เทอร์มินัล

1.ขั้ว:

• ตัวอักษรตัวพิมพ์เล็กในตัวอักษรเช่น a, b, c,
• Operaสัญลักษณ์ทอร์ เช่น +,-, * เป็นต้น
• สัญลักษณ์เครื่องหมายวรรคตอน เช่น วงเล็บ, แฮช, ลูกน้ำ
• 0, 1, …, 9 หลัก
• สตริงตัวหนา เช่น id หรือ if อะไรก็ตามที่แสดงถึงสัญลักษณ์เทอร์มินัลเดียว

2. ไม่ใช่เทอร์มินัล:

• ตัวอักษรตัวพิมพ์ใหญ่ เช่น A, B, C
• ชื่อตัวเอียงตัวพิมพ์เล็ก: สำนวนหรือบางส่วน

ไวยากรณ์ฟรีตามบริบท

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

expression -> expression -+ term
expression -> expression – term 
expression-> term
term  -> term * factor
term -> expression/ factor
term  -> factor factor
factor ->  ( expression )
factor -> id

ที่มาของไวยากรณ์

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

อนุพันธ์ซ้ายสุด

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

รากศัพท์ขวาสุด

การสแกนแหล่งที่มาทางขวาสุดและแทนที่อินพุตด้วยกฎการผลิตจากขวาไปซ้ายตามลำดับ เรียกว่ารากขวาสุด รูปแบบประโยคที่ได้มาจากรากขวาสุดเรียกว่ารูปแบบประโยคที่ถูกต้อง

ไวยากรณ์กับตัววิเคราะห์คำศัพท์

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

ข้อเสียของการใช้ตัววิเคราะห์ไวยากรณ์

• มันจะไม่ตัดสินว่าโทเค็นนั้นถูกต้องหรือไม่
• ไม่ช่วยให้คุณกำหนดได้ว่าการดำเนินการที่ดำเนินการกับประเภทโทเค็นนั้นถูกต้องหรือไม่
• คุณไม่สามารถตัดสินใจได้ว่าโทเค็นจะถูกประกาศและเตรียมใช้งานก่อนที่จะใช้งาน

สรุป

• การวิเคราะห์ไวยากรณ์เป็นขั้นตอนที่สองของกระบวนการออกแบบคอมไพเลอร์ที่มาหลังจากการวิเคราะห์คำศัพท์
• ตัววิเคราะห์วากยสัมพันธ์ช่วยให้คุณใช้กฎกับโค้ดได้
• Sentence, Lexeme, Token, คำสำคัญและคำสงวน, คำที่รบกวน, ความคิดเห็น, ตัวคั่น, ชุดอักขระ, ตัวระบุ เป็นคำศัพท์สำคัญบางคำที่ใช้ในการวิเคราะห์ไวยากรณ์ในการสร้างคอมไพเลอร์
• แยกวิเคราะห์จะตรวจสอบว่าสตริงอินพุตมีรูปแบบที่ถูกต้อง และหากไม่เป็นเช่นนั้น ให้ปฏิเสธ
• เทคนิคการแยกวิเคราะห์แบ่งออกเป็นสองกลุ่ม: การแยกจากบนลงล่าง และจากล่างขึ้นบน
• คำศัพท์ วากยสัมพันธ์ ความหมาย และตรรกะเป็นข้อผิดพลาดทั่วไปบางประการที่เกิดขึ้นระหว่างวิธีการแยกวิเคราะห์
• ไวยากรณ์คือชุดของกฎโครงสร้างที่อธิบายภาษา
• สัญลักษณ์ของข้อตกลงทางสัญลักษณ์อาจระบุได้โดยการใส่องค์ประกอบไว้ในวงเล็บเหลี่ยม
• CFG เป็นไวยากรณ์แบบเรียกซ้ำด้านซ้ายซึ่งมีการผลิตประเภทนี้อย่างน้อยหนึ่งรายการ
• ที่มาของไวยากรณ์คือลำดับของกฎไวยากรณ์ที่แปลงสัญลักษณ์เริ่มต้นให้เป็นสตริง
• ตัววิเคราะห์ไวยากรณ์ส่วนใหญ่เกี่ยวข้องกับโครงสร้างแบบเรียกซ้ำของภาษาในขณะที่ตัววิเคราะห์คำศัพท์ทำให้งานของตัววิเคราะห์ไวยากรณ์ง่ายขึ้น DBMS
• ข้อเสียเปรียบของวิธีวิเคราะห์ไวยากรณ์ก็คือ จะไม่มีทางตัดสินได้ว่าโทเค็นนั้นถูกต้องหรือไม่