ความรู้เบื้องต้นเกี่ยวกับไวยากรณ์

n ความหมายทางวรรณกรรมของศัพท์ไวยากรณ์แสดงถึงกฎวากยสัมพันธ์สำหรับการสนทนาในภาษาธรรมชาติ ภาษาศาสตร์ได้พยายามกำหนดไวยากรณ์ตั้งแต่เริ่มใช้ภาษาธรรมชาติเช่นอังกฤษสันสกฤตจีนกลางเป็นต้น

ทฤษฎีของภาษาที่เป็นทางการพบว่าสามารถนำไปใช้ได้อย่างกว้างขวางในสาขาวิทยาศาสตร์คอมพิวเตอร์ Noam Chomsky ให้แบบจำลองทางคณิตศาสตร์ของไวยากรณ์ในปีพ. ศ. 2499 ซึ่งมีผลบังคับใช้สำหรับการเขียนภาษาคอมพิวเตอร์

ไวยากรณ์

ไวยากรณ์ G สามารถเขียนอย่างเป็นทางการเป็น 4-tuple (N, T, S, P) โดยที่ -

N หรือ V_N คือชุดของตัวแปรหรือสัญลักษณ์ที่ไม่ใช่ขั้ว
T หรือ ∑ คือชุดสัญลักษณ์ Terminal
S เป็นตัวแปรพิเศษที่เรียกว่าสัญลักษณ์ Start, S ∈ N
Pคือกฎการผลิตสำหรับเทอร์มินัลและไม่ใช่เทอร์มินัล กฎการผลิตมีรูปแบบα→βที่αและβสตริงวี_N ∪Σและอย่างน้อยหนึ่งสัญลักษณ์ของαเป็น V N

ตัวอย่าง

ไวยากรณ์ G1 -

({S, A, B}, {a, b}, S, {S → AB, A → a, B → b})

ที่นี่

S, A, และ B เป็นสัญลักษณ์ที่ไม่ใช่ขั้ว
a และ b คือสัญลักษณ์ Terminal
S คือสัญลักษณ์เริ่ม S ∈ N
โปรดักชั่น, P : S → AB, A → a, B → b

ตัวอย่าง

ไวยากรณ์ G2 -

(({S, A}, {a, b}, S, {S → aAb, aA → aaAb, A →ε})

ที่นี่

S และ A เป็นสัญลักษณ์ที่ไม่ใช่ขั้ว
a และ b คือสัญลักษณ์ Terminal
ε เป็นสตริงว่าง
S คือสัญลักษณ์เริ่ม S ∈ N
การผลิต P : S → aAb, aA → aaAb, A → ε

รากศัพท์จากไวยากรณ์

สตริงอาจมาจากสตริงอื่นโดยใช้การผลิตในไวยากรณ์ ถ้าเป็นไวยากรณ์G มีการผลิต α → βเราสามารถพูดได้ว่า x α y เกิดขึ้น x β y ใน G. รากศัพท์นี้เขียนว่า -

x α y ⇒G x β y