ความคลุมเครือในไวยากรณ์ที่ไม่มีบริบท

ถ้าบริบทปลอดไวยากรณ์ G มีโครงสร้างรากศัพท์มากกว่าหนึ่งรายการสำหรับสตริงบางตัว w ∈ L(G)เรียกว่า ambiguous grammar. มีรากศัพท์จากขวาสุดหรือซ้ายสุดหลายตัวสำหรับสตริงบางตัวที่สร้างจากไวยากรณ์นั้น

ปัญหา

ตรวจสอบว่าไวยากรณ์ G พร้อมกฎการผลิต -

X → X + X | X * X | X | ก

มีความคลุมเครือหรือไม่

วิธีการแก้

ลองหาต้นกำเนิดของสตริง "a + a * a" มันมีอนุพันธ์สองตัวซ้ายสุด

Derivation 1- X → X + X → a + X → a + X * X → a + a * X → a + a * ก

Parse tree 1 -

Derivation 2- X → X * X → X + X * X → a + X * X → a + a * X → a + a * ก

Parse tree 2 -

เนื่องจากมีต้นไม้แยกวิเคราะห์สองต้นสำหรับสตริงเดียว "a + a * a" จึงเป็นไวยากรณ์ G มีความคลุมเครือ