ความแตกต่างระหว่าง Top-down และ Bottom-up Parsing

ในโพสต์นี้ เราจะทำความเข้าใจความแตกต่างระหว่าง top-down และ bottom-up parsing -

Top-down parsing และ bottom-up parsing เป็นเทคนิคต่างกันในการ parse ต้นไม้ (parse tree) เพื่อไปถึงรากของต้นไม้ สามารถทำได้ 2 วิธี ดังนี้ -

Top-down Parsing

• เทคนิค parsing ที่ดู highest level ของ parse tree ก่อน แล้วค่อยลงมาที่ parse tree
• ใช้ grammar rules
• ใช้ left most derivation
• พยายามหา left most derivations สำหรับ input string
• Parsing จาก top-most สู่ leaf node แบบ top-down
• ตัดสินใจหลักคือเลือก production rule ที่ใช้สร้าง string

Bottom-up Parsing

• ตรงข้ามกับ top-down ดู lowest level ของ parse tree ก่อน แล้วค่อยขึ้นไป
• ใช้ grammar rules
• ใช้ right most derivation technique
• พยายามหา right most derivations สำหรับ input string
• พยายาม reduce input string ให้กลายเป็น start symbol ของ grammar
• ทำได้โดยใช้ production rule ที่ reduce string ให้กลายเป็น starting symbol