Pushdown Automata & Parsing

การแยกวิเคราะห์ใช้เพื่อสร้างสตริงโดยใช้กฎการผลิตของไวยากรณ์ ใช้เพื่อตรวจสอบความสามารถในการยอมรับของสตริง คอมไพเลอร์ใช้เพื่อตรวจสอบว่าสตริงถูกต้องตามหลักไวยากรณ์หรือไม่ ตัวแยกวิเคราะห์รับอินพุตและสร้างแผนผังการแยกวิเคราะห์

ตัวแยกวิเคราะห์สามารถมีได้สองประเภท -

Top-Down Parser - การแยกวิเคราะห์จากบนลงล่างเริ่มจากด้านบนด้วยสัญลักษณ์เริ่มต้นและหาสตริงโดยใช้โครงสร้างการแยกวิเคราะห์
Bottom-Up Parser - การแยกวิเคราะห์จากล่างขึ้นบนเริ่มจากด้านล่างด้วยสตริงและมาที่สัญลักษณ์เริ่มต้นโดยใช้โครงสร้างการแยกวิเคราะห์

การออกแบบ Parser จากบนลงล่าง

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

วาง non-terminal ทางด้านซ้ายมือของการผลิตที่ด้านบนสุดของสแต็กแล้วดันสตริงด้านขวามือ
หากสัญลักษณ์ด้านบนของสแต็กตรงกับสัญลักษณ์อินพุตที่กำลังอ่านอยู่ให้เปิดขึ้น
กดสัญลักษณ์เริ่ม 'S' เข้าไปในสแต็ก
หากสตริงอินพุตถูกอ่านอย่างสมบูรณ์และสแต็กว่างเปล่าให้ไปที่สถานะสุดท้าย 'F'

ตัวอย่าง

ออกแบบตัวแยกวิเคราะห์จากบนลงล่างสำหรับนิพจน์ "x + y * z" สำหรับไวยากรณ์ G โดยใช้กฎการผลิตดังต่อไปนี้ -

P: S → S + X | X, X → X * Y | Y, Y → (S) | id

Solution

ถ้า PDA คือ (Q, ∑, S, δ, q ₀ , I, F) ดังนั้นการแยกวิเคราะห์จากบนลงล่างคือ -

(x + y * z, I) ⊢ (x + y * z, SI) ⊢ (x + y * z, S + XI) ⊢ (x + y * z, X + XI)

⊢ (x + y * z, Y + XI) ⊢ (x + y * z, x + XI) ⊢ (+ y * z, + XI) ⊢ (y * z, XI)

⊢ (y * z, X * YI) ⊢ (y * z, y * YI) ⊢ (* z, * YI) ⊢ (z, YI) ⊢ (z, zI) ⊢ (ε, I)

การออกแบบตัวแยกวิเคราะห์ด้านล่าง

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

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