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

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

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

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

इतिहास

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

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

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

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

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

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

उदाहरण 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$एस।

यह देखना आसान है: $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$''s) संदर्भ-मुक्त है, क्योंकि इसे व्याकरण द्वारा परिभाषित किया जा सकता है $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 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 के दशक की प्रारंभिक में एक अत्यधिक न्यूनतम विश्लेषणात्मक व्याकरण औपचारिकता विकसित हुई।
• लिंक व्याकरण: भाषाविज्ञान के लिए डिज़ाइन किए गए विश्लेषणात्मक व्याकरण का एक रूप, जो शब्दों के जोड़े के बीच स्थितीय संबंधों की जांच करके वाक्य रचना संरचना प्राप्त करता है।
• पार्सिंग अभिव्यक्ति व्याकरण (पीईजी): प्रोग्रामिंग भाषा और संकलक राइटर्स की व्यावहारिक अभिव्यक्ति (कंप्यूटर विज्ञान) आवश्यकताओं के आसपास डिजाइन किए गए टीडीपीएल का एक और हालिया सामान्यीकरण।
  

यह भी देखें

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