ความแตกต่างที่สำคัญระหว่างการแยกวิเคราะห์จากบนลงล่างและจากล่างขึ้นบนคือการแยกวิเคราะห์จากบนลงล่างทำการแยกวิเคราะห์จากสัญลักษณ์การจ้องมองไปยังสตริงอินพุต ในขณะที่การแยกวิเคราะห์จากล่างลงล่างจะทำการแยกวิเคราะห์จากสตริงอินพุตไปยังสัญลักษณ์เริ่มต้น นอกจากนี้ ความแตกต่างที่สำคัญอีกประการระหว่างการแยกวิเคราะห์จากบนลงล่างและการแยกวิเคราะห์จากล่างขึ้นบนคือการแยกวิเคราะห์จากบนลงล่างใช้การสืบทอดจากซ้ายสุด และการแยกวิเคราะห์จากล่างลงล่างใช้การสืบทอดสูงสุดที่ถูกต้อง
ภาษาระดับสูงช่วยเขียนโปรแกรมคอมพิวเตอร์ โปรแกรมเมอร์เข้าใจได้ง่ายกว่า แต่ไม่ใช่ด้วยคอมพิวเตอร์ ดังนั้นโปรแกรมระดับสูงจึงแปลงเป็นรหัสเครื่องงานของคอมไพเลอร์คือการแปลงซอร์สโค้ดที่มนุษย์อ่านได้เป็นโค้ดเครื่องที่เครื่องอ่านได้ โปรแกรมต้องผ่านหลายขั้นตอนเพื่อแปลงเป็นรหัสเครื่อง กระบวนการทั้งหมดนี้เรียกว่าระบบประมวลผลภาษา หนึ่งในนั้นคือการรวบรวม ตัววิเคราะห์ไวยากรณ์หรือ parser อยู่ในคอมไพเลอร์ และทำงานแยกวิเคราะห์
การแยกจากบนลงล่างคืออะไร
ภาษาการเขียนโปรแกรมทุกภาษามีชุดกฎเกณฑ์ที่ใช้แทนภาษานั้น ตัววิเคราะห์ไวยากรณ์หรือการแยกวิเคราะห์ใช้สตริงอินพุตและตรวจสอบว่าเป็นไปตามการผลิตไวยากรณ์หรือไม่ กล่าวอีกนัยหนึ่ง ไวยากรณ์ควรสร้างสตริงนั้นโดยใช้ parse tree
ในการแยกวิเคราะห์จากบนลงล่าง การแยกวิเคราะห์เกิดขึ้นจากสัญลักษณ์เริ่มต้น และจะไปถึงสตริงอินพุตที่กำหนด พิจารณากฎการผลิตไวยากรณ์ต่อไปนี้ สตริงอินพุต (w) คือ cad.
S -> cAd
A -> ab /a
ต้นไม้แยกวิเคราะห์หลังจากทำการแยกวิเคราะห์จากบนลงล่างมีดังต่อไปนี้
รูปที่ 01: Parse Tree 1 พร้อมการแยกวิเคราะห์จากบนลงล่าง
S ผลิต c A d และ A ผลิต a b สตริงคือ cabd ไม่ใช่สตริงที่จำเป็น ดังนั้นจึงจำเป็นต้องทำการย้อนรอย ซึ่งก็คือการใช้ทางเลือกอื่น
ในทำนองเดียวกัน S โปรดิวซ์ c A d. การใช้ตัวเลือกอื่นสำหรับ A จะทำให้ a ตอนนี้มันให้สตริงที่จำเป็น ดังนั้น parser ยอมรับสตริงอินพุตนี้ ต้นไม้แยกวิเคราะห์หลังจากทำการแยกวิเคราะห์จากบนลงล่างมีดังต่อไปนี้
รูปที่ 02: Parse Tree 2 พร้อมการแยกวิเคราะห์จากบนลงล่าง
เมื่อสตริงอินพุต (w) เป็น abbcde
พิจารณากฎการผลิตไวยากรณ์ต่อไปนี้
S -> aABe
A -> Abc/b
B -> d
ในการแยกวิเคราะห์จากบนลงล่าง
S -> aABe (แทนที่ A -> Abc)
S -> aAbcBe (แทน A -> b)
S -> abbcBe (แทน B->d)
S -> abbcde
การแทนที่เริ่มต้นด้วยตัวแปรซ้ายสุดก่อนจากนั้นไปยังตำแหน่งขวาถัดไปเป็นต้น ดังนั้นจึงเป็นไปตามวิธีการสืบทอดทางซ้ายสุด นอกจากนี้ สิ่งสำคัญคือต้องตัดสินใจว่าจะเลือกกฎการผลิตแบบใดเมื่อมีตัวแปร
Bottom Up Parsing คืออะไร
การแยกวิเคราะห์จากล่างขึ้นบนเกิดขึ้นในลักษณะอื่น การแยกวิเคราะห์เกิดขึ้นจากสตริงอินพุตไปยังสัญลักษณ์เริ่มต้น พิจารณากฎการผลิตไวยากรณ์ต่อไปนี้และให้สตริงอินพุตเป็น w ɛ cad
S -> cAd
A -> ab /a
ต้นไม้แยกวิเคราะห์หลังจากทำการแยกวิเคราะห์จากล่างขึ้นบนมีดังต่อไปนี้
รูปที่ 03: Parse Tree ที่มีการแยกวิเคราะห์จากล่างขึ้นบน
สตริงที่กำหนดคือ cad a ถูกสร้างโดย A โดย c, A และ d รวมกันเพื่อให้ได้สัญลักษณ์เริ่มต้น S.
เมื่อสตริงอินพุต (w) เป็น abbcde
พิจารณากฎการผลิตไวยากรณ์ต่อไปนี้
S -> aABe
A -> Abc/b
B -> d
ในการแยกวิเคราะห์จากล่างขึ้นบน
S -> aABe (แทน B->d)
S -> aAde (แทนที่ A -> Abc)
S -> aAbcde (แทนที่ A -> b)
S -> abbcde
การแทนที่เริ่มต้นด้วยตัวแปรขวาสุดก่อนจากนั้นจึงเลื่อนไปยังตำแหน่งซ้ายถัดไปเป็นต้น ดังนั้นมันจึงเป็นไปตามวิธีการมาจาก mot ซ้าย
ความแตกต่างระหว่างการแยกจากบนลงล่างและล่างขึ้นบนคืออะไร
การแยกวิเคราะห์จากบนลงล่างเป็นกลยุทธ์การแยกวิเคราะห์ที่พิจารณาระดับสูงสุดของทรี parse ก่อนแล้วจึงทำงานบน parse tree โดยใช้กฎของไวยากรณ์ที่เป็นทางการ การแยกวิเคราะห์จากล่างขึ้นบนเป็นกลยุทธ์การแยกวิเคราะห์ที่พิจารณาระดับต่ำสุดของแผนผังการแยกวิเคราะห์ก่อนแล้วจึงทำงานบนแผนผังการแยกวิเคราะห์โดยใช้กฎของไวยากรณ์ที่เป็นทางการการแยกวิเคราะห์เกิดขึ้นจากสัญลักษณ์เริ่มต้นไปยังสตริงอินพุต ในการแยกวิเคราะห์จากบนลงล่าง ในทางกลับกัน การแยกวิเคราะห์เกิดขึ้นจากสตริงอินพุตไปยังสัญลักษณ์เริ่มต้น โดยแยกวิเคราะห์จากล่างขึ้นบน
นอกจากนี้ การตัดสินใจหลักในการแยกวิเคราะห์จากบนลงล่างคือการเลือกกฎการผลิตที่จะใช้เพื่อสร้างสตริง ในขณะที่การตัดสินใจหลักในการแยกวิเคราะห์จากล่างลงล่างคือการเลือกว่าเมื่อใดควรใช้กฎการผลิตเพื่อลดสตริงเป็น รับสัญลักษณ์เริ่มต้น ยิ่งไปกว่านั้น การแยกวิเคราะห์จากบนลงล่างใช้ที่มาซ้ายสุด และการแยกวิเคราะห์จากล่างสุดใช้ที่มาขวาสุด
สรุป – การแยกจากบนลงล่างกับการแยกจากล่างขึ้นบน
ความแตกต่างระหว่างการแยกวิเคราะห์จากบนลงล่างและจากล่างขึ้นบนคือการแยกวิเคราะห์จากบนลงล่างทำการแยกวิเคราะห์จากสัญลักษณ์การจ้องมองไปยังสตริงอินพุต ในขณะที่การแยกวิเคราะห์จากล่างขึ้นล่างจะทำการแยกวิเคราะห์จากสตริงอินพุตไปยังสัญลักษณ์เริ่มต้น