ในวิทยาการคอมพิวเตอร์กฎการผลิตหรือกฎการสร้างคือกฎการเขียนใหม่ที่แทนที่สัญลักษณ์บางอย่างด้วยสัญลักษณ์อื่น^{[ 1 ]}ชุดการผลิตที่จำกัดเป็นองค์ประกอบหลักในการกำหนดไวยากรณ์ที่เป็นทางการ (โดยเฉพาะไวยากรณ์เชิงกำเนิด ) ${\displaystyle P}$

ในไวยากรณ์ประเภทนี้ เซตของกฎการผลิตเป็นกรณีพิเศษของความสัมพันธ์บนเซตของสตริง(โดยที่คือ ตัวดำเนินการ ดาวคลีน ) เหนือเซตจำกัดของสัญลักษณ์ที่เรียกว่าคำศัพท์ซึ่งกำหนดว่าสตริงที่ไม่ว่างเปล่าใดบ้างที่สามารถแทนที่ด้วยสตริงอื่นได้ ดังนั้น เซตของกฎการผลิตจึงเป็นเซตย่อยชนิดพิเศษ ${\displaystyle V^{*}}$${\displaystyle {}^{*}}$${\displaystyle V}$

${\displaystyle P\เซตย่อย V^{*}\คูณ V^{*}}$

และกฎการผลิตจะถูกเขียนในรูปแบบที่หมายความว่า(ไม่ควรสับสนกับการใช้เป็นสัญลักษณ์ฟังก์ชัน เนื่องจากอาจมีกฎหลายข้อสำหรับสิ่งเดียวกัน) เมื่อกำหนดเซตย่อยสองเซตกฎการผลิตสามารถจำกัดให้เป็นไปตามเงื่อนไขซึ่งในกรณีนี้ กฎการผลิตจะเรียกว่า "อยู่ในรูปแบบ" การเลือกและการสร้างที่แตกต่างกันของจะนำไปสู่ไวยากรณ์ประเภทต่างๆ โดยทั่วไป กฎการผลิตใดๆ ที่อยู่ในรูปแบบ ${\displaystyle u\to v}$${\displaystyle (u,v)\in P}$${\displaystyle \to }$${\displaystyle u}$${\displaystyle A,B\subset V^{*}}$${\displaystyle P\subset A\times B}$${\displaystyle A\to B}$${\displaystyle A,B}$

${\displaystyle u\to \epsilon ,}$

โดยที่สตริงว่าง (บางครั้งอาจใช้สัญลักษณ์) เรียกว่ากฎการลบในขณะที่กฎการผลิตที่สร้างสตริงขึ้นมาโดยไม่มีที่มาที่ไป กล่าวคือในรูปแบบ ${\displaystyle \epsilon }$${\displaystyle \lambda }$

${\displaystyle \epsilon \ถึง v,}$

ไม่ได้รับอนุญาตอย่างเด็ดขาด

เพื่อให้กฎการผลิตสามารถสร้างประโยคที่มีความหมายได้ คำศัพท์จึงถูกแบ่งออกเป็นชุด ( ที่ไม่ซ้ำกัน ) และกำหนดบทบาทที่แตกต่างกันสองบทบาท: ${\displaystyle \Sigma }$${\displaystyle N}$

• ${\displaystyle \Sigma }$หมายถึงสัญลักษณ์ปลายทางที่เรียกว่าตัวอักษรซึ่งประกอบด้วยสัญลักษณ์ที่อนุญาตให้ใช้ในประโยค
• ${\displaystyle N}$หมายถึงสัญลักษณ์ที่ไม่ใช่เทอร์มินัลซึ่งประกอบด้วยสัญลักษณ์เริ่มต้น ที่โดดเด่น ซึ่งจำเป็นต้องใช้ร่วมกับกฎการผลิตเพื่อกำหนดวิธีการสร้างประโยค${\displaystyle S\in N}$

ในกรณีทั่วไปที่สุดของไวยากรณ์แบบไม่จำกัด กฎการผลิตสามารถแปลงสตริงใดๆและไปเป็น(เทอร์มินัลและนอนเทอร์มินัล) ได้ ตราบใดที่ไม่ว่างเปล่า ดังนั้นไวยากรณ์แบบไม่จำกัดจึงมีกฎการผลิตในรูปแบบ ${\displaystyle u\to v}$${\displaystyle u}$${\displaystyle v}$${\displaystyle V}$${\displaystyle u}$

${\displaystyle V^{*}\setminus \{\epsilon \}\ถึง V^{*}}$

หรือหากเราต้องการไม่อนุญาตให้แก้ไขประโยคที่เขียนเสร็จแล้ว

${\displaystyle V^{*}NV^{*}=(V^{*}\setminus \Sigma ^{*})\ถึง V^{*}}$,

โดยที่แสดงถึงการต่อกันและบังคับให้สัญลักษณ์ที่ไม่ใช่เทอร์มินัลปรากฏอยู่ทางด้านซ้ายมือของกฎการผลิตเสมอ และแสดงถึงเซตลบหรือเซตผลต่างหากเราไม่อนุญาตให้สัญลักษณ์เริ่มต้นปรากฏใน(คำทางด้านขวามือ) เราต้องแทนที่ด้วยทางด้านขวามือ^{[ 2 ]}${\displaystyle V^{*}NV^{*}}$${\displaystyle \setminus }$${\displaystyle v}$${\displaystyle V^{*}}$${\displaystyle (V\setminus \{S\})^{*}}$

ไวยากรณ์เชิงรูปธรรมประเภทอื่นๆ ในลำดับชั้นของชอมสกีกำหนดข้อจำกัดเพิ่มเติมเกี่ยวกับสิ่งที่ประกอบขึ้นเป็นกฎการผลิต โดยเฉพาะอย่างยิ่งในไวยากรณ์แบบไร้บริบทด้านซ้ายของกฎการผลิตจะต้องเป็นสัญลักษณ์ที่ไม่ใช่เทอร์มินัลเพียงตัวเดียว ดังนั้นกฎการผลิตจึงมีรูปแบบดังนี้:

${\displaystyle N\to V^{*}}$

ในการสร้างสตริงในภาษาดังกล่าว เริ่มต้นด้วยสตริงที่ประกอบด้วยสัญลักษณ์เริ่มต้น เพียงตัวเดียว จากนั้นจึงใช้กฎต่างๆ (กี่ครั้งก็ได้ ในลำดับใดก็ได้) เพื่อเขียนสตริงนี้ใหม่ กระบวนการนี้จะหยุดเมื่อได้สตริงที่ประกอบด้วยสัญลักษณ์ปลายทางเท่านั้น ภาษาประกอบด้วยสตริงทั้งหมดที่สามารถสร้างขึ้นได้ด้วยวิธีนี้ ลำดับการเลือกที่ถูกต้องใดๆ ที่เกิดขึ้นระหว่างกระบวนการเขียนใหม่นี้ จะให้สตริงเฉพาะหนึ่งสตริงในภาษา หากมีหลายวิธีที่แตกต่างกันในการสร้างสตริงเดียวกันนี้ ไวยากรณ์นั้นจะเรียกว่า กำกวม

ตัวอย่างเช่น สมมติว่าตัวอักษรประกอบด้วยและโดยมีสัญลักษณ์เริ่มต้นคือ และเรามีกฎดังต่อไปนี้: ${\displaystyle a}$${\displaystyle b}$${\displaystyle S}$

1.${\displaystyle S\rightarrow aSb}$

2.${\displaystyle S\rightarrow ba}$

จากนั้นเราเริ่มต้นด้วยและสามารถเลือกกฎที่จะนำไปใช้กับมันได้ ถ้าเราเลือกกฎที่ 1 เราจะแทนที่ด้วยและได้สตริงถ้าเราเลือกกฎที่ 1 อีกครั้ง เราจะแทนที่ด้วยและได้สตริงกระบวนการนี้จะทำซ้ำไปเรื่อยๆ จนกว่าเราจะมีเฉพาะสัญลักษณ์จากตัวอักษร (เช่นและ) ถ้าตอนนี้เราเลือกกฎที่ 2 เราจะแทนที่ด้วยและได้สตริงและเสร็จสิ้น เราสามารถเขียนลำดับการเลือกนี้ให้สั้นลงได้โดยใช้สัญลักษณ์: ภาษาของไวยากรณ์คือเซตของสตริงทั้งหมดที่สามารถสร้างได้โดยใช้กระบวนการนี้: ${\displaystyle S}$${\displaystyle S}$${\displaystyle aSb}$${\displaystyle aSb}$${\displaystyle S}$${\displaystyle aSb}$${\displaystyle aaSbb}$${\displaystyle a}$${\displaystyle b}$${\displaystyle S}$${\displaystyle ba}$${\displaystyle aababb}$${\displaystyle S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aababb}$${\displaystyle \{ba,abab,aababb,aaababbb,\dotsc \}}$

• ไวยากรณ์เชิงทางการ
• ออโตมาตาจำกัด
• ไวยากรณ์เชิงกำเนิด
• ระบบ L
• กฎการเขียนใหม่
• รูปแบบแบคคัส-เนาเออร์ (รูปแบบกระชับสำหรับการเขียนกฎการผลิตของไวยากรณ์แบบไร้บริบท)
• กฎโครงสร้างวลี
• ระบบโพสต์แคนอนิก (ระบบการผลิตของเอมิล โพสต์ - แบบจำลองการคำนวณ)