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

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

ไวยากรณ์เชิงรูปธรรมคือชุดของกฎสำหรับการเขียนสตริงใหม่ พร้อมด้วย "สัญลักษณ์เริ่มต้น" ซึ่งเป็นจุดเริ่มต้นของการเขียนใหม่ ดังนั้น ไวยากรณ์จึงมักถูกมองว่าเป็นตัวสร้างภาษา อย่างไรก็ตาม ไวยากรณ์ยังสามารถใช้เป็นพื้นฐานสำหรับตัวแยกวิเคราะห์ซึ่งเป็นฟังก์ชันในการคำนวณที่กำหนดว่าสตริงที่กำหนดนั้นอยู่ในภาษาหรือไม่ หรือไม่ถูกต้องตามหลักไวยากรณ์ ในการอธิบายตัวแยกวิเคราะห์ดังกล่าว ทฤษฎีภาษาเชิงรูปธรรมใช้รูปแบบที่แยกต่างหาก ซึ่งเรียกว่าทฤษฎีออโตมาตาผลลัพธ์ประการหนึ่งของทฤษฎีออโตมาตาคือ ไม่สามารถออกแบบตัวรับรู้สำหรับภาษาเชิงรูปธรรมบางภาษาได้^{[ 1 ]}

ภาษาหลายภาษามีโครงสร้างความหมายของสตริงตามไวยากรณ์ของภาษา ซึ่งเป็นแนวทางที่เรียกว่า ความหมายเชิงองค์ประกอบ ( compositional semantics ) ในกรณีเหล่านี้ ขั้นตอนแรกในการอธิบายความหมายของสตริงคือการแยกสตริงนั้นออกเป็นส่วนๆ และพิจารณารูปแบบที่วิเคราะห์แล้ว (ซึ่งในวิทยาการคอมพิวเตอร์เรียกว่า แผนผังการวิเคราะห์ (parse tree ) และ ใน ไวยากรณ์เชิงกำเนิด (generative grammar ) เรียกว่าโครงสร้างเชิงลึก (deep structure )

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

แตกต่างจากระบบกึ่งธู (semi-Thue system ) ซึ่งถูกกำหนดโดยกฎเหล่านี้ทั้งหมด ไวยากรณ์ยังแยกแยะความแตกต่างระหว่างสัญลักษณ์สองประเภท ได้แก่สัญลักษณ์ที่ไม่ใช่เทอร์มิ นัล (nonterminal symbols) และ สัญลักษณ์ เทอร์มินัล (terminal symbols ) โดยแต่ละด้านซ้ายมือจะต้องมีสัญลักษณ์ที่ไม่ใช่เทอร์มินัลอย่างน้อยหนึ่งตัว นอกจากนี้ยังมีการแยกแยะสัญลักษณ์ที่ไม่ใช่เทอร์มินัลพิเศษที่เรียกว่าสัญลักษณ์เริ่มต้น (start symbol ) ด้วย

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

ในตัวอย่างต่อไปนี้ สัญลักษณ์ปลายทางคือaและbและสัญลักษณ์เริ่มต้นคือ S

สมมติว่าเรามีกฎการผลิตดังต่อไปนี้:

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

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

จากนั้นเราเริ่มต้นด้วยSและสามารถเลือกกฎที่จะนำไปใช้กับมันได้ ถ้าเราเลือกกฎที่ 1 เราจะได้สตริงaSbถ้าเราเลือกกฎที่ 1 อีกครั้ง เราจะแทนที่Sด้วยaSbและได้สตริงaaSbbถ้าเราเลือกกฎที่ 2 เราจะแทนที่Sด้วยbaและได้สตริงaababbและเสร็จสิ้น เราสามารถเขียนลำดับการเลือกนี้ให้กระชับยิ่งขึ้นโดยใช้สัญลักษณ์: ${\displaystyle S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aababb}$

ภาษาของไวยากรณ์นี้คือเซตอนันต์โดยที่จะถูกทำซ้ำครั้ง (และโดยเฉพาะอย่างยิ่ง แสดงถึงจำนวนครั้งที่กฎการผลิตข้อที่ 1 ถูกนำมาใช้) ไวยากรณ์นี้เป็นไวยากรณ์ที่ไม่ขึ้นกับบริบท (มีเพียงสัญลักษณ์ที่ไม่ใช่เทอร์มินัลเดี่ยวๆ ปรากฏเป็นด้านซ้ายมือ) และไม่มีความกำกวม ${\displaystyle \{a^{n}bab^{n}\mid n\geq 0\}=\{ba,abab,aababb,aaababbb,\dotsc \}}$${\displaystyle a^{k}}$${\displaystyle a}$${\displaystyle k}$${\displaystyle n}$

สมมติว่ากฎเกณฑ์เปลี่ยนไปเป็นแบบนี้แทน:

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

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

3.${\displaystyle aSa\ลูกศรขวา b}$

ไวยากรณ์นี้ไม่ใช่ไวยากรณ์ที่ไม่ขึ้นกับบริบทเนื่องจากกฎข้อที่ 3 และมีความกำกวมเนื่องจากกฎข้อที่ 2 สามารถนำมาใช้สร้างลำดับของs ได้หลายวิธี${\displaystyle S}$

อย่างไรก็ตาม ภาษาที่สร้างขึ้นนั้นเป็นเพียงเซตของสตริงที่ไม่ว่างเปล่าทั้งหมดที่ประกอบด้วยs และ/หรือs ซึ่งเห็นได้ง่าย: ในการสร้าง a จาก an ให้ใช้กฎข้อ 2 สองครั้งเพื่อสร้างa จากนั้นใช้กฎข้อ 1 สองครั้งและกฎข้อ 3 หนึ่งครั้งเพื่อสร้าง a ซึ่งหมายความว่าเราสามารถสร้างลำดับของ s ที่ไม่ว่างเปล่าใดๆ ก็ได้แล้วแทนที่แต่ละลำดับด้วยa หรือ b ตามที่เราต้องการ ${\displaystyle a}$${\displaystyle b}$${\displaystyle b}$${\displaystyle S}$${\displaystyle SSS}$${\displaystyle b}$${\displaystyle S}$${\displaystyle a}$${\displaystyle b}$

ภาษาเดียวกันนั้นสามารถสร้างขึ้นได้อีกทางหนึ่งโดยใช้ไวยากรณ์ที่ไม่ขึ้นกับบริบทและไม่มีความกำกวม ตัวอย่างเช่น ไวยากรณ์ ปกติที่มีกฎเกณฑ์

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

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

3.${\displaystyle S\rightarrow a}$

4.${\displaystyle S\rightarrow b}$

ในการกำหนดรูปแบบไวยากรณ์เชิงกำเนิดแบบคลาสสิกที่เสนอครั้งแรกโดยNoam Chomskyในช่วงทศวรรษ 1950 ^{[ 2 ] [ 3 ]}ไวยากรณ์Gประกอบด้วยส่วนประกอบต่อไปนี้:

• เซตจำกัดNของสัญลักษณ์ที่ไม่ใช่เทอร์มินัลซึ่งไม่ซ้ำซ้อนกับสตริงที่สร้างขึ้นจากG
• เซตจำกัดของสัญลักษณ์ปลายทางที่ไม่ซ้อนทับกับN${\displaystyle \Sigma }$
• เซตจำกัดPของกฎการผลิตโดยแต่ละกฎมีรูปแบบดังนี้

${\displaystyle (\Sigma \cup N)^{*}N(\Sigma \cup N)^{*}\rightarrow (\Sigma \cup N)^{*}}$

โดยที่ตัวดำเนินการKleene starหมายถึงการรวมเซตนั่นคือ กฎการผลิตแต่ละข้อจะแมปจากสตริงสัญลักษณ์หนึ่งไปยังอีกสตริงหนึ่ง โดยที่สตริงแรก ("หัว") ประกอบด้วยสัญลักษณ์จำนวนเท่าใดก็ได้ ตราบใดที่อย่างน้อยหนึ่งสัญลักษณ์เป็นสัญลักษณ์ที่ไม่ใช่เทอร์มินัล ในกรณีที่สตริงที่สอง ("ตัว") ประกอบด้วยสตริงว่าง เพียงอย่างเดียว —กล่าวคือ ไม่มีสัญลักษณ์ใด ๆ เลย—อาจใช้สัญลักษณ์พิเศษ (มักจะเป็น, eหรือ) เพื่อหลีกเลี่ยงความสับสน กฎดังกล่าวเรียกว่า กฎ การลบ^{[ 4 ]}${\displaystyle {*}}$${\displaystyle \cup }$${\displaystyle \Lambda }$${\displaystyle \epsilon }$

• สัญลักษณ์ที่โดดเด่นซึ่งเรียกว่าสัญลักษณ์เริ่มต้นหรือเรียกอีกอย่างว่าสัญลักษณ์ประโยค${\displaystyle S\in N}$

ไวยากรณ์ได้รับการกำหนดอย่างเป็นทางการว่าเป็นทูเปิล ไวยากรณ์อย่างเป็นทางการดังกล่าวมักเรียกว่าระบบการเขียนใหม่หรือไวยากรณ์โครงสร้างวลีในเอกสาร^{[ 5 ] [ 6 ]}${\displaystyle (N,\Sigma ,P,S)}$

การทำงานของไวยากรณ์สามารถนิยามได้ในแง่ของความสัมพันธ์บนสตริง:

• เมื่อกำหนดไวยากรณ์แล้วความสัมพันธ์ทวิภาค(อ่านว่า "G ได้มาในหนึ่งขั้นตอน") บนสตริงในไวยากรณ์นั้นถูกกำหนดโดย: ${\displaystyle G=(N,\Sigma ,P,S)}$${\displaystyle {\underset {G}{\Rightarrow }}}$${\displaystyle (\Sigma \cup N)^{*}}$

  ${\displaystyle x{\underset {G}{\Rightarrow }}y\iff \exists u,v,p,q\in (\Sigma \cup N)^{*}:(x=upv)\wedge (p\rightarrow q\in P)\wedge (y=uqv)}$

• ความสัมพันธ์(ออกเสียงว่าG ซึ่งได้มาในขั้นตอนศูนย์หรือมากกว่า ) ถูกกำหนดให้เป็นการปิดแบบสะท้อนและถ่ายทอดของ${\displaystyle {\overset {*}{\underset {G}{\ลูกศรขวา }}}}$${\displaystyle {\underset {G}{\Rightarrow }}}$
• เอรูปแบบประโยคคือสมาชิกที่สามารถอนุมานได้ในจำนวนขั้นตอนที่จำกัดจากสัญลักษณ์เริ่มต้นกล่าวคือ รูปแบบประโยคเป็นสมาชิกของรูปแบบประโยคที่ไม่มีสัญลักษณ์ที่ไม่ใช่เทอร์มินัล (กล่าวคือ เป็นสมาชิกของ⁾เรียกว่าประโยค [ ^{7 ]}${\displaystyle (\Sigma \cup N)^{*}}$${\displaystyle S}$${\displaystyle \left\{w\in (\Sigma \cup N)^{*}\mid S{\overset {*}{\underset {G}{\Rightarrow }}}w\right\}}$${\displaystyle \Sigma ^{*}}$
• ภาษาของซึ่งแสดงด้วยสัญลักษณ์ ถูกกำหนดให้เป็นเซตของประโยคที่สร้างขึ้นโดย${\displaystyle G}$${\displaystyle {\boldสัญลักษณ์ {L}}(G)}$${\displaystyle G}$

ไวยากรณ์นี้โดยพื้นฐานแล้วคือระบบกึ่งธู (semi-Thue system)ซึ่งเขียนสตริงใหม่ในลักษณะเดียวกันทุกประการ ความแตกต่างเพียงอย่างเดียวคือเราแยกแยะ สัญลักษณ์ ที่ไม่ใช่เทอ ร์มินัลเฉพาะ ซึ่งจะต้องถูกแทนที่ในกฎการเขียนใหม่ และเราสนใจเฉพาะการเขียนใหม่จากสัญลักษณ์เริ่มต้นที่กำหนดไปยังสตริงที่ไม่มีสัญลักษณ์ที่ไม่ใช่เทอร์มินัลเท่านั้น ${\displaystyle G=(N,\Sigma ,P,S)}$${\displaystyle (N\cup \Sigma ,P)}$${\displaystyle S}$

สำหรับตัวอย่างเหล่านี้ ภาษาเชิงรูปธรรมจะถูกกำหนดโดยใช้ สั ญกรณ์การสร้างเซต

พิจารณาไวยากรณ์ที่, , เป็นสัญลักษณ์เริ่มต้น และประกอบด้วยกฎการผลิตดังต่อไปนี้: ${\displaystyle G}$${\displaystyle N=\left\{S,B\right\}}$${\displaystyle \Sigma =\left\{a,b,c\right\}}$${\displaystyle S}$${\displaystyle P}$

1.${\displaystyle S\ลูกศรขวา aBSc}$

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

3.${\displaystyle Ba\rightarrow aB}$

4.${\displaystyle Bb\rightarrow bb}$

ไวยากรณ์นี้กำหนดภาษาที่แทนสตริงของ'n ตัว เรียงกันดังนั้น ภาษานี้คือเซตของสตริงที่ประกอบด้วย'n ตัวขึ้นไป ตามด้วย 'n จำนวนเท่ากัน และตามด้วย 'n จำนวนเท่ากัน${\displaystyle L(G)=\left\{a^{n}b^{n}c^{n}\mid n\geq 1\right\}}$${\displaystyle a^{n}}$${\displaystyle a}$${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$

ตัวอย่างบางส่วนของการสร้างสตริงในภาษาโปรแกรมมีดังนี้: ${\displaystyle L(G)}$

(หมายเหตุ: อ่านว่า "สตริงPสร้างสตริงQโดยใช้กฎการผลิตi " และส่วนที่ถูกสร้างขึ้นจะถูกระบุด้วยตัวหนาในแต่ละครั้ง)${\displaystyle P{\underset {i}{\Rightarrow }}Q}$

เมื่อNoam Chomskyได้กำหนดรูปแบบไวยากรณ์เชิงกำเนิดอย่างเป็นทางการครั้งแรกในปี พ.ศ. 2499 ^{[ 2 ]}เขาได้จำแนกไวยากรณ์เหล่านี้ออกเป็นประเภทต่างๆ ซึ่งปัจจุบันรู้จักกันในชื่อลำดับชั้นของ Chomskyความแตกต่างระหว่างประเภทเหล่านี้คือ ไวยากรณ์เหล่านี้มีกฎการผลิตที่เข้มงวดมากขึ้นเรื่อยๆ และด้วยเหตุนี้จึงสามารถแสดงภาษาที่เป็นทางการได้น้อยลง ไวยากรณ์ที่สำคัญสองประเภทคือไวยากรณ์แบบไร้บริบท (ประเภท 2) และไวยากรณ์แบบปกติ (ประเภท 3) ภาษาที่สามารถอธิบายได้ด้วยไวยากรณ์ดังกล่าวเรียกว่าภาษาแบบไร้บริบทและภาษาแบบปกติตามลำดับ แม้ว่าจะมีประสิทธิภาพน้อยกว่าไวยากรณ์แบบไม่จำกัด (ประเภท 0) ซึ่งสามารถแสดงภาษาใดๆ ก็ได้ที่ เครื่องจักร Turingยอมรับได้แต่ไวยากรณ์แบบจำกัดสองประเภทนี้มักถูกใช้บ่อยที่สุด เนื่องจากสามารถนำตัวแยกวิเคราะห์มาใช้ได้อย่างมีประสิทธิภาพ^{[ 8 ]}ตัวอย่างเช่น ภาษาปกติทั้งหมดสามารถรับรู้ได้ด้วยเครื่องสถานะจำกัดและสำหรับชุดย่อยที่มีประโยชน์ของไวยากรณ์แบบไร้บริบท มีอัลกอริทึมที่รู้จักกันดีในการสร้างตัวแยกวิเคราะห์ LL ที่มีประสิทธิภาพ และตัวแยกวิเคราะห์ LRเพื่อรับรู้ภาษาที่สอดคล้องกับไวยากรณ์เหล่านั้น

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

ภาษาที่นิยามไว้ข้างต้นไม่ใช่ภาษาไร้บริบท และสามารถพิสูจน์ได้อย่างเคร่งครัดโดยใช้ทฤษฎีบทปั๊มสำหรับภาษาไร้บริบทแต่ตัวอย่างเช่น ภาษา(อย่างน้อย 1 ตามด้วย 's จำนวนเท่ากัน) เป็นภาษาไร้บริบท เนื่องจากสามารถนิยามได้ด้วยไวยากรณ์ที่มี, , สัญลักษณ์เริ่มต้น และกฎการผลิตต่อไปนี้: ${\displaystyle L(G)=\left\{a^{n}b^{n}c^{n}\mid n\geq 1\right\}}$${\displaystyle \left\{a^{n}b^{n}\mid n\geq 1\right\}}$${\displaystyle a}$${\displaystyle b}$${\displaystyle G_{2}}$${\displaystyle N=\left\{S\right\}}$${\displaystyle \Sigma =\left\{a,b\right\}}$${\displaystyle S}$

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

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

ภาษาที่ไม่ขึ้นกับบริบทสามารถรับรู้ได้ในเวลา ( ดูสัญกรณ์ Big O ) โดยอัลกอริทึมเช่นตัวรับรู้ของ Earleyและในเวลาต่ำกว่าลูกบาศก์โดยอัลกอริทึมการคูณเมทริกซ์ที่รวดเร็ว [ ^{9 ] กล่าว}คือ สำหรับทุกภาษาที่ไม่ขึ้นกับบริบท สามารถสร้างเครื่องจักรที่รับสตริงเป็นอินพุตและกำหนดได้ในเวลาว่าสตริงนั้นเป็นสมาชิกของภาษาหรือไม่ โดยที่คือความยาวของสตริง^{[ 10 ]}ภาษาที่ไม่ขึ้นกับบริบทแบบกำหนดได้คือเซตย่อยของภาษาที่ไม่ขึ้นกับบริบทที่สามารถรับรู้ได้ในเวลาเชิงเส้น^{[ 11 ]}มีอัลกอริทึมต่างๆ ที่กำหนดเป้าหมายไปที่เซตของภาษาเหล่านี้หรือเซตย่อยบางส่วนของมัน ${\displaystyle O(n^{3})}$${\displaystyle O(n^{3})}$${\displaystyle n}$

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

ภาษาที่กำหนดไว้ข้างต้นไม่ใช่ภาษาปกติ แต่ภาษา(อย่างน้อย 1 ตามด้วยอย่างน้อย 1 โดยที่ตัวเลขอาจแตกต่างกันได้) เป็นภาษาปกติ เนื่องจากสามารถกำหนดได้ด้วยไวยากรณ์ที่มี, , สัญลักษณ์เริ่มต้น และกฎการผลิตต่อไปนี้: ${\displaystyle \left\{a^{n}b^{n}\mid n\geq 1\right\}}$${\displaystyle \left\{a^{n}b^{m}\mid m,n\geq 1\right\}}$${\displaystyle a}$${\displaystyle b}$${\displaystyle G_{3}}$${\displaystyle N=\left\{S,A,B\right\}}$${\displaystyle \Sigma =\left\{a,b\right\}}$${\displaystyle S}$

1. ${\displaystyle S\rightarrow aA}$
2. ${\displaystyle A\rightarrow aA}$
3. ${\displaystyle A\rightarrow bB}$
4. ${\displaystyle B\rightarrow bB}$
5. ${\displaystyle B\rightarrow \epsilon }$

ภาษาทั้งหมดที่สร้างขึ้นโดยไวยากรณ์ปกติสามารถรับรู้ได้ในเวลาโดยเครื่องสถานะจำกัด แม้ว่าในทางปฏิบัติ ไวยากรณ์ปกติมักจะแสดงโดยใช้การแสดงออกปกติแต่การแสดงออกปกติบางรูปแบบที่ใช้ในทางปฏิบัติไม่ได้สร้างภาษาปกติอย่างเคร่งครัด และไม่แสดงประสิทธิภาพการรับรู้เชิงเส้นเนื่องจากความเบี่ยงเบนเหล่านั้น ${\displaystyle O(n)}$

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

• ไวยากรณ์ที่เชื่อมต่อต้นไม้ช่วยเพิ่มการแสดงออกของไวยากรณ์เชิงกำเนิดแบบดั้งเดิมโดยอนุญาตให้กฎการเขียนใหม่ทำงานบนต้นไม้การวิเคราะห์แทนที่จะเป็นเพียงสตริง^{[ 12 ]}
• ไวยากรณ์คำต่อท้าย^{[ 13 ]}และไวยากรณ์คุณลักษณะ^{[ 14 ] [ 15 ]}อนุญาตให้กฎการเขียนใหม่ได้รับการเสริมด้วยคุณลักษณะและการดำเนินการเชิงความหมาย ซึ่งมีประโยชน์ทั้งในการเพิ่มการแสดงออกของไวยากรณ์และการสร้างเครื่องมือแปลภาษาที่ใช้งานได้จริง

ไวยากรณ์แบบเรียกซ้ำคือไวยากรณ์ที่มีกฎการผลิตที่เรียกซ้ำได้ตัวอย่างเช่น ไวยากรณ์สำหรับภาษาอิสระบริบทจะเป็นแบบเรียกซ้ำซ้ายหากมีสัญลักษณ์ที่ไม่ใช่เทอร์มินัลAที่สามารถนำไปผ่านกฎการผลิตเพื่อสร้างสตริงที่มีAเป็นสัญลักษณ์ซ้ายสุด^{[ 16 ]}ตัวอย่างของไวยากรณ์แบบเรียกซ้ำคืออนุประโยคภายในประโยคที่คั่นด้วยเครื่องหมายจุลภาคสองตัว^{[ 17 ]}ไวยากรณ์ทุกประเภทในลำดับชั้นของ Chomskyสามารถเป็นแบบเรียกซ้ำได้

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

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

• ภาษาวิเคราะห์แบบบนลงล่าง (TDPL): รูปแบบไวยากรณ์เชิงวิเคราะห์ที่เรียบง่ายมากซึ่งพัฒนาขึ้นในช่วงต้นทศวรรษ 1970 เพื่อศึกษาพฤติกรรมของตัววิเคราะห์แบบบนลงล่าง^{[ 18 ]}
• ไวยากรณ์เชื่อมโยง : รูปแบบหนึ่งของไวยากรณ์เชิงวิเคราะห์ที่ออกแบบมาสำหรับภาษาศาสตร์ซึ่งได้โครงสร้างทางไวยากรณ์โดยการตรวจสอบความสัมพันธ์เชิงตำแหน่งระหว่างคู่คำ^{[ 19 ] [ 20 ]}
• ไวยากรณ์การแยกวิเคราะห์นิพจน์ (PEGs): การวางนัยทั่วไปของ TDPL ที่ทันสมัยกว่าซึ่งออกแบบมาเพื่อตอบสนอง ความต้องการ ในการแสดงออก เชิงปฏิบัติ ของผู้เขียนภาษาโปรแกรมและคอมไพเลอร์^{[ 21 ]}