บทนำไวยากรณ์แบบไม่มีบริบท
Definition - ไวยากรณ์ที่ไม่มีบริบท (CFG) ประกอบด้วยชุดกฎไวยากรณ์ที่ จำกัด เป็นสี่เท่า (N, T, P, S) ที่ไหน
N คือชุดของสัญลักษณ์ที่ไม่ใช่ขั้ว
T คือชุดของเทอร์มินัลที่ N ∩ T = NULL.
P เป็นชุดของกฎ P: N → (N ∪ T)*กล่าวคือด้านซ้ายมือของกฎการผลิต P มีบริบทที่ถูกต้องหรือบริบททางซ้าย
S คือสัญลักษณ์เริ่มต้น
Example
- ไวยากรณ์ ({A}, {a, b, c}, P, A), P: A → aA, A → abc
- ไวยากรณ์ ({S, a, b}, {a, b}, P, S), P: S → aSa, S → bSb, S →ε
- ไวยากรณ์ ({S, F}, {0, 1}, P, S), P: S → 00S | 11F, F → 00F | ε
การสร้างต้นไม้ที่มา
แผนภูมิรากศัพท์หรือต้นไม้แยกวิเคราะห์คือต้นไม้ที่ถูกรูทตามลำดับซึ่งแสดงถึงข้อมูลความหมายแบบกราฟิกซึ่งเป็นสตริงที่ได้มาจากไวยากรณ์ที่ไม่มีบริบท
เทคนิคการเป็นตัวแทน
Root vertex - ต้องติดป้ายสัญลักษณ์เริ่มต้น
Vertex - ติดป้ายกำกับด้วยสัญลักษณ์ที่ไม่ใช่ขั้ว
Leaves - กำกับด้วยสัญลักษณ์เทอร์มินัลหรือε
ถ้า S → x 1 x 2 …… x nเป็นกฎการผลิตใน CFG การแยกวิเคราะห์แผนภูมิ / โครงสร้างการหารากจะเป็นดังนี้ -
มีสองวิธีที่แตกต่างกันในการวาดต้นไม้ที่มา:
Top-down Approach −
เริ่มต้นด้วยสัญลักษณ์เริ่มต้น S
ลงไปที่ใบไม้ของต้นไม้โดยใช้การผลิต
Bottom-up Approach −
เริ่มจากใบไม้ของต้นไม้
เลื่อนขึ้นไปที่รูทซึ่งเป็นสัญลักษณ์เริ่มต้น S
การได้มาหรือผลผลิตของต้นไม้
รากศัพท์หรือผลผลิตของต้นไม้แยกวิเคราะห์คือสตริงสุดท้ายที่ได้จากการต่อป้ายชื่อใบของต้นไม้จากซ้ายไปขวาโดยไม่สนใจ Nulls อย่างไรก็ตามหากใบไม้ทั้งหมดเป็น Null รากศัพท์จะเป็น Null
Example
ให้ CFG {N, T, P, S} เป็น
N = {S}, T = {a, b}, สัญลักษณ์เริ่มต้น = S, P = S → SS | aSb | ε
หนึ่งที่มาจาก CFG ข้างต้นคือ "abaabb"
S → SS → aSbS → abS → abaSb → abaaSbb → abaabb
รูปแบบความรู้สึกและโครงสร้างการสืบพันธ์บางส่วน
ต้นไม้ที่ได้มาบางส่วนคือต้นไม้ย่อยของต้นไม้ต้นกำเนิด / ต้นไม้แยกวิเคราะห์ซึ่งลูกของมันทั้งหมดอยู่ในแผนผังย่อยหรือไม่มีเลยในแผนผังย่อย
Example
หาก CFG ใด ๆ โปรดักชั่นคือ -
S → AB, A → aaA | ε, B → Bb | ε
ต้นไม้ที่มาบางส่วนสามารถเป็นดังต่อไปนี้ -
ถ้าต้นไม้ที่มาบางส่วนมีราก S จะเรียกว่า a sentential form. แผนผังย่อยข้างต้นยังอยู่ในรูปแบบความรู้สึก
ซ้ายสุดและขวาสุดที่มาของสตริง
Leftmost derivation - ได้มาจากการใช้การผลิตกับตัวแปรซ้ายสุดในแต่ละขั้นตอน
Rightmost derivation - ได้มาจากการใช้การผลิตกับตัวแปรขวาสุดในแต่ละขั้นตอน
Example
ให้ชุดกฎการผลิตใด ๆ ใน CFG เป็น
X → X + X | X * X | X | ก
ทับตัวอักษร {a}
รากศัพท์ด้านซ้ายสุดสำหรับสตริง "a+a*a" อาจจะ -
X → X + X → a + X → a + X * X → a + a * X → a + a * ก
ที่มาทีละขั้นตอนของสตริงด้านบนแสดงดังต่อไปนี้ -
รากศัพท์ด้านขวาสุดสำหรับสตริงด้านบน "a+a*a" อาจจะ -
X → X * X → X * a → X + X * a → X + a * a → a + a * ก
ที่มาทีละขั้นตอนของสตริงด้านบนแสดงดังต่อไปนี้ -
ไวยากรณ์แบบวนซ้ำซ้ายและขวา
ในไวยากรณ์ที่ไม่มีบริบท Gหากมีการผลิตตามแบบ X → Xa ที่ไหน X เป็น non-terminal และ ‘a’ เป็นสตริงของเทอร์มินัลเรียกว่า left recursive production. ไวยากรณ์ที่มีการผลิตซ้ำด้านซ้ายเรียกว่าไฟล์left recursive grammar.
และถ้าอยู่ในไวยากรณ์ที่ไม่มีบริบท Gหากมีการผลิตอยู่ในรูปแบบ X → aX ที่ไหน X เป็น non-terminal และ ‘a’ เป็นสตริงของเทอร์มินัลเรียกว่า right recursive production. ไวยากรณ์ที่มีการผลิตซ้ำที่ถูกต้องเรียกว่าไฟล์right recursive grammar.