औपचारिक व्याकरण

औपचारिक भाषा सिद्धांत में, व्याकरण जब संदर्भ नहीं दिया जाता है, जिसे अक्सर स्पष्टता के लिए एक औपचारिक व्याकरण कहा जाता है) वर्णन करता है कि किसी भाषा के वर्णमाला से तार कैसे बनाये जाते हैं जो भाषा के वाक्य-विन्यास के अनुसार मान्य होते हैं। एक व्याकरण शब्दार्थ का वर्णन नहीं करता है बल्कि किसी भी संदर्भ में उनके साथ क्या किया जा सकता है - केवल उनका रूप का भी वर्णन करता है औपचारिक व्याकरण को औपचारिक भाषा में ऐसे तारों के उत्पादन नियमों के एक सेट के रूप में परिभाषित किया जाता है।

औपचारिक भाषा सिद्धांत, अनुशासन जो औपचारिक व्याकरण और भाषाओं का अध्ययन करता है, अनुप्रयुक्त गणित की एक शाखा है। इसके अनुप्रयोग सैद्धांतिक कंप्यूटर विज्ञान, सैद्धांतिक भाषाविज्ञान, औपचारिक शब्दार्थ (तर्क), गणितीय तर्क और अन्य क्षेत्रों में पाए जाते हैं।

औपचारिक व्याकरण स्ट्रिंग्स को फिर से लिखने के लिए नियमों का एक सेट है, साथ ही एक "स्टार्ट सिंबल" जिससे पुनर्लेखन शुरू होता है। इसलिए, व्याकरण को सामान्यतः भाषा जनरेटर के रूप में माना जाता है। चूँकि, इसे कभी-कभी एक पहचानकर्ता के आधार के रूप में भी इस्तेमाल किया जा सकता है - कंप्यूटिंग में एक फ़ंक्शन जो यह निर्धारित करता है कि दी गई स्ट्रिंग भाषा से संबंधित है या व्याकरणिक रूप से गलत है। ऐसे पहचानकर्ताओं का वर्णन करने के लिए, औपचारिक भाषा सिद्धांत अलग औपचारिकता का उपयोग करता है, जिसे ऑटोमेटा सिद्धांत के रूप में जाना जाता है। ऑटोमेटा सिद्धांत के मनोरंजक परिणामों में से एक यह है कि कुछ औपचारिक भाषाओं के लिए पहचानकर्ता को डिजाइन करना संभव नहीं है। पार्सिंग एक उच्चारण (प्राकृतिक भाषाओं में एक स्ट्रिंग) को प्रतीकों के एक सेट में तोड़कर और भाषा के व्याकरण के विरुद्ध प्रत्येक का विश्लेषण करके पहचानने की प्रक्रिया है।। अधिकांश भाषाओं में उनके कथनों के अर्थ उनके वाक्य-विन्यास के अनुसार संरचित होते हैं - एक अभ्यास जिसे रचनात्मक शब्दार्थ के रूप में जाना जाता है। परिणाम स्वरुप, भाषा में एक उच्चारण के अर्थ का वर्णन करने के लिए पहला कदम यह है कि इसे अलग-अलग हिस्सों में विभाजित किया जाए और इसके विश्लेषित रूप को देखा जाए (कंप्यूटर विज्ञान में इसके पार्स ट्री के रूप में जाना जाता है, और जनरेटिक व्याकरण में गहरी संरचना और सतह संरचना के रूप में जाना जाता है)।

इतिहास

Pāṇini' का ग्रंथ अष्टाध्यायी संस्कृत के औपचारिक व्याकरण का वर्णन करने के लिए औपचारिक उत्पादन नियम और परिभाषाएँ देता है। प्रपत्र और औपचारिकता के विभिन्न उपयोग हैं, जो समय के साथ बदल गए हैं, संबंधित लेखक के संपर्क में आने वाले क्षेत्रों के आधार पर। अवधारणा का एक ऐतिहासिक अवलोकन में दिया गया है

परिचयात्मक उदाहरण

एक व्याकरण मुख्य रूप से उत्पादन (कंप्यूटर विज्ञान) का एक सेट होता है, तारों को बदलने के लिए नियमों को फिर से लिखना। प्रत्येक नियम एक विशेष स्ट्रिंग (इसके बाएँ हाथ की ओर) को दूसरे (इसके दाएँ हाथ की ओर) के प्रतिस्थापन को निर्दिष्ट करता है। प्रत्येक स्ट्रिंग पर एक नियम लागू किया जा सकता है जिसमें इसकी बाईं ओर सम्मलित है और एक स्ट्रिंग उत्पन्न करता है जिसमें उस बाएं हाथ की घटना को उसके दाएं हाथ से बदल दिया गया है।

अर्ध-थू प्रणाली के विपरीत, जो पूरी तरह से इन नियमों द्वारा परिभाषित है, एक व्याकरण आगे दो प्रकार के प्रतीकों के बीच अंतर करता है: गैर-टर्मिनल और टर्मिनल प्रतीक; प्रत्येक बाईं ओर कम से कम एक गैर-टर्मिनल प्रतीक होना चाहिए। यह एक विशेष गैर-टर्मिनल प्रतीक को भी अलग करता है, जिसे प्रारंभ प्रतीक कहा जाता है।

व्याकरण द्वारा उत्पन्न भाषा को बिना किसी गैर-टर्मिनल प्रतीकों के सभी स्ट्रिंग्स के सेट के रूप में परिभाषित किया गया है, जो कि किसी भी तरह से अपने नियमों के अनुप्रयोग (संभावित रूप से दोहराए गए) द्वारा एकल प्रारंभ प्रतीक वाले स्ट्रिंग से उत्पन्न किया जा सकता है। यदि एक ही स्ट्रिंग को उत्पन्न करने के अनिवार्य रूप से अलग-अलग तरीके हैं, तो व्याकरण को अस्पष्ट व्याकरण कहा जाता है।

निम्नलिखित उदाहरणों में, टर्मिनल प्रतीक a और b हैं, और प्रारंभ प्रतीक S है।

उदाहरण 1

मान लीजिए कि हमारे पास निम्नलिखित उत्पादन नियम हैं:

1. $S\rightarrow aSb$

2. $S\rightarrow ba$

तो हम एस से शुरू करते हैं, और इसे लागू करने के लिए एक नियम चुन सकते हैं। यदि हम नियम 1 चुनते हैं, तो हमें स्ट्रिंग aSb प्राप्त होती है। यदि हम नियम 1 को फिर से चुनते हैं, तो हम S को aSb से बदल देते हैं और स्ट्रिंग aaSbb प्राप्त करते हैं। यदि अब हम नियम 2 चुनते हैं, तो हम S को ba से प्रतिस्थापित करते हैं और स्ट्रिंग प्राप्त करते हैंaababb, और कर दिए गए हैं। हम प्रतीकों का उपयोग करके विकल्पों की इस श्रृंखला को और संक्षेप में लिख सकते हैं: $S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aababb$.

व्याकरण की भाषा अनंत समुच्चय है $\{a^{n}bab^{n}\mid n\geq 0\}=\{ba,abab,aababb,aaababbb,\dotsc \}$, कहाँ $a^{k}$ है $a$ दोहराया गया $k$ टाइम्स (और $n$ विशेष रूप से यह दर्शाता है कि कितनी बार उत्पादन नियम 1 लागू किया गया है)। यह व्याकरण संदर्भ-मुक्त व्याकरण है | संदर्भ-मुक्त (केवल एकल गैर-टर्मिनल बाएं हाथ के रूप में दिखाई देते हैं) और असंदिग्ध।

उदाहरण 2 और 3

मान लीजिए नियम इसके बजाय ये हैं:

1. $S\rightarrow a$

2. $S\rightarrow SS$

3. $aSa\rightarrow b$

यह व्याकरण नियम 3 के कारण संदर्भ-मुक्त नहीं है और यह कई तरीकों के कारण अस्पष्ट है जिसमें नियम 2 का उपयोग क्रम उत्पन्न करने के लिए किया जा सकता है $S$एस।

चूँकि, यह जो भाषा उत्पन्न करता है, वह केवल सभी गैर-खाली तारों का समूह है $a$एस और/या $b$एस। यह देखना आसान है: उत्पन्न करने के लिए $b$ एक से $S$, जनरेट करने के लिए नियम 2 का दो बार उपयोग करें $SSS$, फिर नियम 1 दो बार और नियम 3 एक बार उत्पन्न करने के लिए $b$. इसका मतलब है कि हम मनमाने ढंग से गैर-खाली अनुक्रम उत्पन्न कर सकते हैं $S$s और फिर उनमें से प्रत्येक को इसके साथ बदलें $a$ या $b$ जैसा हम चाहते हैं।

वही भाषा वैकल्पिक रूप से एक संदर्भ-मुक्त, असंदिग्ध व्याकरण द्वारा उत्पन्न की जा सकती है; उदाहरण के लिए, #नियमित व्याकरण नियमों के साथ व्याकरण

1. $S\rightarrow aS$

2. $S\rightarrow bS$

3. $S\rightarrow a$

4. $S\rightarrow b$

औपचारिक परिभाषा

Main article: अप्रतिबंधित व्याकरण

व्याकरण का वाक्य-विन्यास

1950 के दशक में पहली बार नोम चौमस्की द्वारा प्रस्तावित जनरेटिव व्याकरण की क्लासिक औपचारिकता में, एक व्याकरण G में निम्नलिखित घटक होते हैं:

• गैर-टर्मिनल प्रतीकों का एक परिमित सेट N, जो कि G से बने स्ट्रिंग्स के साथ अलग करना सेट है।
• परिमित समुच्चय $\Sigma$ टर्मिनल प्रतीकों की संख्या जो N से विसंधित सेट है।
• उत्पादन नियमों का एक परिमित समुच्चय, प्रपत्र का प्रत्येक नियम

$(\Sigma \cup N)^{*}N(\Sigma \cup N)^{*}\rightarrow (\Sigma \cup N)^{*}$ :कहाँ ${*}$ क्लेन स्टार ऑपरेटर है और $\cup$ संघ (सेट सिद्धांत) को दर्शाता है। यही है, प्रत्येक उत्पादन नियम प्रतीकों की एक स्ट्रिंग से दूसरे में मैप करता है, जहां पहली स्ट्रिंग (सिर) में मनमाने ढंग से प्रतीकों की संख्या होती है, बशर्ते उनमें से कम से कम एक गैर-टर्मिनल हो। मामले में कि दूसरी स्ट्रिंग (शरीर) में केवल खाली स्ट्रिंग होती है- यानी, इसमें कोई प्रतीक नहीं होता है- इसे एक विशेष संकेतन के साथ दर्शाया जा सकता है (अक्सर $\Lambda$, ई या $\epsilon$) भ्रम से बचने के लिए।

• एक विशिष्ट प्रतीक $S\in N$ वह प्रारंभ चिह्न है, जिसे वाक्य चिह्न भी कहा जाता है।

एक व्याकरण को औपचारिक रूप से टपल के रूप में परिभाषित किया जाता है $(N,\Sigma ,P,S)$. इस तरह के एक औपचारिक व्याकरण को अक्सर साहित्य में पुनर्लेखन प्रणाली या वाक्यांश संरचना व्याकरण कहा जाता है।

औपचारिक व्याकरण के संबंध में कुछ गणितीय निर्माण

स्ट्रिंग्स पर संबंधों के संदर्भ में व्याकरण के संचालन को परिभाषित किया जा सकता है:

• एक व्याकरण दिया $G=(N,\Sigma ,P,S)$, द्विआधारी संबंध ${\underset {G}{\Rightarrow }}$ (उच्चारण जी के रूप में एक चरण में प्राप्त होता है) में तार पर $(\Sigma \cup N)^{*}$ द्वारा परिभाषित किया गया है:

  $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)$

• रिश्ता ${\overset {*}{\underset {G}{\Rightarrow }}}$ (जी के रूप में उच्चारित शून्य या अधिक चरणों में होता है) को रिफ्लेक्सिव सकर्मक बंद होने के रूप में परिभाषित किया गया है ${\underset {G}{\Rightarrow }}$
• ए वाक्यात्मक रूप का सदस्य है $(\Sigma \cup N)^{*}$ जिसे स्टार्ट सिंबल से सीमित संख्या में चरणों में प्राप्त किया जा सकता है $S$; अर्थात्, एक वाक्यात्मक रूप का सदस्य है $\left\{w\in (\Sigma \cup N)^{*}\mid S{\overset {*}{\underset {G}{\Rightarrow }}}w\right\}$. एक वाक्यात्मक रूप जिसमें कोई गैर-टर्मिनल प्रतीक नहीं है (अर्थात इसका सदस्य है $\Sigma ^{*}$) वाक्य कहलाता है।
• की भाषा $G$, इस रूप में घोषित किया गया ${\boldsymbol {L}}(G)$, द्वारा निर्मित वाक्यों के सेट के रूप में परिभाषित किया गया है $G$.

ध्यान दें कि व्याकरण $G=(N,\Sigma ,P,S)$ प्रभावी रूप से अर्ध-थू प्रणाली है $(N\cup \Sigma ,P)$, ठीक उसी तरह से तार को फिर से लिखना; एकमात्र अंतर यह है कि हम विशिष्ट गैर-टर्मिनल प्रतीकों को अलग करते हैं, जिन्हें पुनर्लेखन नियमों में फिर से लिखा जाना चाहिए, और केवल निर्दिष्ट प्रारंभ प्रतीक से पुनर्लेखन में रुचि रखते हैं $S$ गैर-टर्मिनल प्रतीकों के बिना तार के लिए।

उदाहरण

इन उदाहरणों के लिए, सेट-बिल्डर नोटेशन का उपयोग करके औपचारिक भाषाएँ निर्दिष्ट की जाती हैं।

व्याकरण पर विचार करें $G$ कहाँ $N=\left\{S,B\right\}$, $\Sigma =\left\{a,b,c\right\}$, $S$ प्रारंभ प्रतीक है, और $P$ निम्नलिखित उत्पादन नियमों के होते हैं:

1. $S\rightarrow aBSc$

2. $S\rightarrow abc$

3. $Ba\rightarrow aB$

4. $Bb\rightarrow bb$

यह व्याकरण भाषा को परिभाषित करता है $L(G)=\left\{a^{n}b^{n}c^{n}\mid n\geq 1\right\}$ कहाँ $a^{n}$ लगातार n की एक स्ट्रिंग को दर्शाता है $a$'एस। इस प्रकार, भाषा तारों का समूह है जिसमें 1 या अधिक होते हैं $a$की, उसके बाद समान संख्या में $b$की, उसके बाद समान संख्या में $c$'एस।

स्ट्रिंग्स की व्युत्पत्ति के कुछ उदाहरण $L(G)$ हैं:

• ${\boldsymbol {S}}{\underset {2}{\Rightarrow }}{\boldsymbol {abc}}$
• ${\begin{aligned}{\boldsymbol {S}}&{\underset {1}{\Rightarrow }}{\boldsymbol {aBSc}}\\&{\underset {2}{\Rightarrow }}aB{\boldsymbol {abc}}c\\&{\underset {3}{\Rightarrow }}a{\boldsymbol {aB}}bcc\\&{\underset {4}{\Rightarrow }}aa{\boldsymbol {bb}}cc\end{aligned}}$
• ${\begin{aligned}{\boldsymbol {S}}&{\underset {1}{\Rightarrow }}{\boldsymbol {aBSc}}{\underset {1}{\Rightarrow }}aB{\boldsymbol {aBSc}}c\\&{\underset {2}{\Rightarrow }}aBaB{\boldsymbol {abc}}cc\\&{\underset {3}{\Rightarrow }}a{\boldsymbol {aB}}Babccc{\underset {3}{\Rightarrow }}aaB{\boldsymbol {aB}}bccc{\underset {3}{\Rightarrow }}aa{\boldsymbol {aB}}Bbccc\\&{\underset {4}{\Rightarrow }}aaaB{\boldsymbol {bb}}ccc{\underset {4}{\Rightarrow }}aaa{\boldsymbol {bb}}bccc\end{aligned}}$

(नोटेशन पर ध्यान दें: $P{\underset {i}{\Rightarrow }}Q$ स्ट्रिंग पढ़ता है P तार उत्पन्न करता है Q उत्पादन के माध्यम से i, और उत्पन्न भाग को हर बार बोल्ड टाइप में इंगित किया जाता है।)

चॉम्स्की पदानुक्रम

Main article: चॉम्स्की पदानुक्रम

जब नोम चॉम्स्की ने पहली बार 1956 में जनरेटिव व्याकरण को औपचारिक रूप दिया,उन्होंने उन्हें प्रकारों में वर्गीकृत किया जिसे अब चॉम्स्की पदानुक्रम के रूप में जाना जाता है। इन प्रकारों के बीच अंतर यह है कि उनके उत्पादन के सख्त नियम हैं और इसलिए वे कम औपचारिक भाषाओं को व्यक्त कर सकते हैं। दो महत्वपूर्ण प्रकार हैं संदर्भ-मुक्त व्याकरण (प्रकार 2) और नियमित व्याकरण (प्रकार 3)। ऐसे व्याकरण से जिन भाषाओं का वर्णन किया जा सकता है, उन्हें क्रमशः संदर्भ-मुक्त भाषाएँ और नियमित भाषाएँ कहा जाता है। हालांकि अप्रतिबंधित व्याकरण (टाइप 0) की तुलना में बहुत कम शक्तिशाली, जो वास्तव में किसी भी भाषा को व्यक्त कर सकता है जिसे ट्यूरिंग मशीन द्वारा स्वीकार किया जा सकता है, इन दो प्रतिबंधित प्रकार के व्याकरणों का सबसे अधिक उपयोग किया जाता है क्योंकि उनके लिए पारसर्स को कुशलता से लागू किया जा सकता है। उदाहरण के लिए, सभी नियमित भाषाओं को एक परिमित-राज्य मशीन द्वारा पहचाना जा सकता है, और संदर्भ-मुक्त व्याकरण के उपयोगी उपसमुच्चय के लिए कुशल एलएल पार्सर और एलआर पार्सर उत्पन्न करने के लिए जाने-माने एल्गोरिदम हैं जो व्याकरण उत्पन्न करने वाली संबंधित भाषाओं को पहचानते हैं।

प्रसंग-मुक्त व्याकरण

एक संदर्भ-मुक्त व्याकरण एक व्याकरण है जिसमें प्रत्येक उत्पादन नियम के बाईं ओर केवल एक गैर-टर्मिनल प्रतीक होता है। यह प्रतिबंध गैर-तुच्छ है; संदर्भ-मुक्त व्याकरण द्वारा सभी भाषाएँ उत्पन्न नहीं की जा सकतीं। जिन्हें संदर्भ-मुक्त भाषा कहा जा सकता है।

भाषा $L(G)=\left\{a^{n}b^{n}c^{n}\mid n\geq 1\right\}$ ऊपर परिभाषित एक संदर्भ-मुक्त भाषा नहीं है, और इसे संदर्भ-मुक्त भाषाओं के लिए पम्पिंग लेम्मा का उपयोग करके सख्ती से सिद्ध किया जा सकता है, लेकिन उदाहरण के लिए भाषा $\left\{a^{n}b^{n}\mid n\geq 1\right\}$ (कम से कम 1 $a$ इसके बाद समान संख्या में $b$'एस) संदर्भ-मुक्त है, क्योंकि इसे व्याकरण द्वारा परिभाषित किया जा सकता है $G_{2}$ साथ $N=\left\{S\right\}$, $\Sigma =\left\{a,b\right\}$, $S$ प्रारंभ प्रतीक, और निम्नलिखित उत्पादन नियम:

1. $S\rightarrow aSb$

2. $S\rightarrow ab$

एक संदर्भ-मुक्त भाषा में पहचाना जा सकता है $O(n^{3})$ समय (बिग ओ नोटेशन देखें) एक एल्गोरिथम द्वारा जैसे कि अर्ली पार्सर # एल्गोरिथम | अर्ली का पहचानकर्ता। अर्थात्, प्रत्येक संदर्भ-मुक्त भाषा के लिए, एक मशीन बनाई जा सकती है जो एक स्ट्रिंग को इनपुट के रूप में लेती है और निर्धारित करती है $O(n^{3})$ समय क्या स्ट्रिंग भाषा का सदस्य है, कहाँ $n$ स्ट्रिंग की लंबाई है। नियतात्मक संदर्भ-मुक्त भाषाएँ संदर्भ-मुक्त भाषाओं का एक सबसेट है जिसे रैखिक समय में पहचाना जा सकता है। ऐसे कई एल्गोरिदम मौजूद हैं जो या तो भाषाओं के इस सेट या इसके कुछ सबसेट को लक्षित करते हैं।

नियमित व्याकरण

नियमित व्याकरण में, बाएं हाथ का पक्ष फिर से केवल एक गैर-टर्मिनल प्रतीक है, लेकिन अब दायां हाथ भी प्रतिबंधित है। दाईं ओर खाली स्ट्रिंग, या एक एकल टर्मिनल प्रतीक, या एक एकल टर्मिनल प्रतीक हो सकता है, जिसके बाद एक गैर-टर्मिनल प्रतीक हो सकता है, लेकिन कुछ और नहीं। (कभी-कभी एक व्यापक परिभाषा का उपयोग किया जाता है: कोई भी बिना किसी अन्य चीज के टर्मिनलों या एकल गैर-टर्मिनलों के लंबे तार की अनुमति दे सकता है, जिससे भाषाओं की एक ही श्रेणी को परिभाषित करते हुए भाषाओं को वाक्यात्मक चीनी बना दिया जाता है।)

भाषा $\left\{a^{n}b^{n}\mid n\geq 1\right\}$ ऊपर परिभाषित नियमित नहीं है, लेकिन भाषा है $\left\{a^{n}b^{m}\mid m,n\geq 1\right\}$ (कम से कम 1 $a$ उसके बाद कम से कम 1 $b$, जहां संख्या भिन्न हो सकती है) है, क्योंकि इसे व्याकरण द्वारा परिभाषित किया जा सकता है $G_{3}$ साथ $N=\left\{S,A,B\right\}$, $\Sigma =\left\{a,b\right\}$, $S$ प्रारंभ प्रतीक, और निम्नलिखित उत्पादन नियम:

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

एक नियमित व्याकरण द्वारा उत्पन्न सभी भाषाओं को पहचाना जा सकता है $O(n)$ एक परिमित-राज्य मशीन द्वारा समय। हालांकि अभ्यास में, नियमित व्याकरण सामान्यतः नियमित अभिव्यक्तियों का उपयोग करके व्यक्त किया जाता है, अभ्यास में उपयोग की जाने वाली नियमित अभिव्यक्ति के कुछ रूप नियमित रूप से नियमित भाषाओं को उत्पन्न नहीं करते हैं और उन विचलनों के कारण रैखिक मान्यतात्मक प्रदर्शन नहीं दिखाते हैं।

उत्पादक व्याकरण के अन्य रूप

चॉम्स्की के औपचारिक व्याकरण के मूल पदानुक्रम पर कई विस्तार और विविधताएं भाषाविदों और कंप्यूटर वैज्ञानिकों द्वारा विकसित की गई हैं, सामान्यतः या तो उनकी अभिव्यंजक शक्ति को बढ़ाने के लिए या उन्हें विश्लेषण या पार्स करना आसान बनाने के लिए। विकसित व्याकरण के कुछ रूपों में सम्मलित हैं:

• ट्री-आसन्न व्याकरण केवल स्ट्रिंग्स के बजाय पार्स ट्रीों पर पुनर्लेखन नियमों को संचालित करने की अनुमति देकर पारंपरिक जनरेटिव व्याकरण की अभिव्यक्ति को बढ़ाते हैं।
• प्रत्यय व्याकरण और विशेषता व्याकरण पुनर्लेखन नियमों को सिमेंटिक विशेषताओं और संचालन के साथ संवर्धित करने की अनुमति दें, व्याकरण की अभिव्यक्ति बढ़ाने और व्यावहारिक भाषा अनुवाद उपकरणों के निर्माण के लिए उपयोगी।

पुनरावर्ती व्याकरण

Not to be confused with पुनरावर्ती भाषा.

एक पुनरावर्ती व्याकरण एक व्याकरण है जिसमें पुनरावर्ती उत्पादन नियम होते हैं। उदाहरण के लिए, एक संदर्भ-मुक्त भाषा के लिए एक व्याकरण वाम-पुनरावर्ती है यदि कोई गैर-टर्मिनल प्रतीक ए मौजूद है जिसे उत्पादन नियमों के माध्यम से ए के साथ सबसे बाएं प्रतीक के रूप में एक स्ट्रिंग बनाने के लिए रखा जा सकता है। पुनरावर्ती व्याकरण का एक उदाहरण दो अल्पविरामों द्वारा अलग किए गए वाक्य के भीतर एक खंड है। ओकोए पदानुक्रम में सभी प्रकार के व्याकरण पुनरावर्ती हो सकते हैं।

विश्लेषणात्मक व्याकरण

यद्यपि पार्सिंग एल्गोरिदम पर साहित्य का एक अतिबृहत तत्व है, इनमें से अधिकांश एल्गोरिदम मानते हैं कि पार्स की जाने वाली भाषा को प्रारंभ में एक सामान्य औपचारिक व्याकरण के माध्यम से वर्णित किया गया है, और लक्ष्य इस उत्पादक व्याकरण को एक कार्यशील पार्सर में बदलना है। सही अर्थों में, एएक जनरेटिव व्याकरण किसी भाषा को पार्स करने के लिए उपयोग किए जाने वाले एल्गोरिदम के अनुरूप नहीं होता है, और विभिन्न एल्गोरिदम के उत्पादन नियमों के रूप में अलग-अलग प्रतिबंध होते हैं जिन्हें अच्छी तरह से गठित माना जाता है।एक वैकल्पिक दृष्टिकोण पहली जगह में एक विश्लेषणात्मक व्याकरण के संदर्भ में भाषा को औपचारिक रूप देना है, जो भाषा के लिए एक पार्सर की संरचना और शब्दार्थ से अधिक सीधे मेल खाता है। विश्लेषणात्मक व्याकरण औपचारिकताओं के उदाहरणों में निम्नलिखित सम्मलित हैं:

• लैंग्वेज मशीन अप्रतिबंधित विश्लेषणात्मक व्याकरण लागू करती है। प्रतिस्थापन नियमों का उपयोग आउटपुट और व्यवहार उत्पन्न करने के लिए एक इनपुट को बदलने के लिए किया जाता है।सिस्टम एलएम-आरेख भी उत्पन्न कर सकता है, जो दिखाता है कि क्या होता है जब एक अप्रतिबंधित विश्लेषणात्मक व्याकरण के नियमों को लागू किया जा रहा है।
• टॉप-डाउन पार्सिंग लैंग्वेज (टीडीपीएल): टॉप-डाउन पार्सर्स के व्यवहार का अध्ययन करने के लिए 1970 के दशक की शुरुआत में एक अत्यधिक न्यूनतम विश्लेषणात्मक व्याकरण औपचारिकता विकसित हुई।
• लिंक व्याकरण: भाषाविज्ञान के लिए डिज़ाइन किए गए विश्लेषणात्मक व्याकरण का एक रूप, जो शब्दों के जोड़े के बीच स्थितीय संबंधों की जांच करके वाक्य रचना संरचना प्राप्त करता है।
• पार्सिंग अभिव्यक्ति व्याकरण (पीईजी): प्रोग्रामिंग भाषा और संकलक राइटर्स की व्यावहारिक अभिव्यक्ति (कंप्यूटर विज्ञान) आवश्यकताओं के आसपास डिजाइन किए गए टीडीपीएल का एक और हालिया सामान्यीकरण।

यह भी देखें

• सार वाक्य रचना का पेड़
• अनुकूली व्याकरण
• अस्पष्ट व्याकरण
• बैकस-नौर फॉर्म | बैकस-नौर फॉर्म (बीएनएफ)
• श्रेणीबद्ध व्याकरण
• ठोस वाक्य रचना का पेड़
• विस्तारित बैकस-नौर फॉर्म | विस्तारित बैकस-नौर फॉर्म (ईबीएनएफ)
• व्याकरण की रूपरेखा
• एल प्रणाली
• लोज में
• पोस्ट कैनोनिकल सिस्टम
• आकार व्याकरण
• अच्छी तरह से गठित सूत्र