एलएल पार्सर

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

LL पार्सर को LL(k) पार्सर कहा जाता है यदि यह किसी वाक्य को पार्स करते समय पार्सिंग लुकहेड के K टोकन (पार्सर) का उपयोग करता है। इस प्रकार ग्रामर को LL ग्रामर या LL(k) ग्रामर कहा जाता है यदि उससे LL(k) पार्सर का निर्माण किया जा सकता है। औपचारिक लैंग्वेज को LL(k) लैंग्वेज कहा जाता है यदि उसमें LL(k) ग्रामर होते है। प्रत्येक k ≥0 के लिए LL(k) लैंग्वेज का सेट LL(k+1) लैंग्वेज में उचित रूप से समाहित है।^[1] इस प्रकार इसका परिणाम यह है कि सभी कांटेक्स्ट-फ्री लैंग्वेज को LL(k) पार्सर द्वारा पहचाना नहीं जा सकता है।

LL पार्सर को LL-रेगुलर (LLR) कहा जाता है यदि यह LL-रेगुलर लैंग्वेज को पार्स करता है।^[2]^[3]^[4] इस प्रकार LL-नियमित ग्रामर की कक्षा में प्रत्येक के के लिए प्रत्येक LL(k) ग्रामर सम्मिलित है। प्रत्येक LLR ग्रामर के लिए LLR पार्सर उपस्थित होता है जो ग्रामर को रैखिक समय में पार्स करता है।

दो नामकरण बाह्य पार्सर प्रकार LL(*) और LL(परिमित) हैं। पार्सर को LL(*)/LL(परिमित) कहा जाता है यदि वह LL(*)/LL(परिमित) पार्सिंग रणनीति का उपयोग करता है। ^[5]^[6] LL(*) और LL(परिमित) पार्सर कार्यात्मक रूप से पार्सिंग अभिव्यक्ति ग्रामर पार्सर के निकट हैं। LL (परिमित) पार्सर अनैतिक LL(k) ग्रामर को लुकहेड और लुकहेड तुलनाओं की मात्रा में अधिकतम रूप से पार्स कर सकता है। LL (*) रणनीति द्वारा पार्स करने योग्य ग्रामर के वर्ग में वाक्यात्मक और अर्थ संबंधी विधेय के उपयोग के कारण कुछ कांटेक्स्ट-संवेदनशील लैंग्वेज सम्मिलित हैं और उनकी पहचान नहीं की गई है। इस प्रकार यह सुझाव दिया गया है कि LL (*) पार्सर को ऊपर से नीचे पार्सिंग लैंग्वेज पार्सर के रूप में उत्तम माना जाता है।^[7]

लोकप्रिय गलत धारणा के विपरीत, LL (*) पार्सर सामान्यतः LLR नहीं होते हैं, और निर्माण द्वारा गारंटी दी जाती है कि वह औसतन व्यर्थ प्रदर्शन करेंगे (रैखिक समय के विरुद्ध सुपर-रैखिक) और सबसे व्यर्थ स्थिति में बहुत व्यर्थ (रैखिक समय के विरुद्ध घातीय) है।

LL ग्रामर, विशेष रूप से LL (1) ग्रामर, बहुत व्यावहारिक रुचि के हैं, क्योंकि इन ग्रामर के लिए पार्सर का निर्माण करना सरल है, और अनेक कंप्यूटर लैंग्वेज को इस कारण से LL (1) के रूप में डिज़ाइन किया गया है।^[8] इस प्रकार LL पार्सर टेबल-आधारित हो सकते हैं, अर्थात एलआर पार्सर के समान, किन्तु LL ग्रामर को रिकर्सन डिसेंट पार्सर द्वारा भी पार्स किया जा सकता है। वाइट और गूस (1984) के अनुसार,^[9] LL(k) ग्रामर स्टर्न्स और लुईस (1969) द्वारा प्रस्तुत किया गया था।^[10]

अवलोकन

किसी दिए गए कांटेक्स्ट-फ्री ग्रामर के लिए, पार्सर कांटेक्स्ट-फ्री ग्रामर व्युत्पन्न और सिंटेक्स ट्री को खोजने का प्रयास करता है। इस प्रकार $G$ ग्रामर का उदाहरण दिया गया है :

$S\to E$
$E\to (E+E)$
$E\to i$

$w=((i+i)+i)$ के लिए सबसे बाईं व्युत्पत्ति है:

S\ {\overset {(1)}{\Rightarrow }}\ E\ {\overset {(2)}{\Rightarrow }}\ (E+E)\ {\overset {(2)}{\Rightarrow }}\ ((E+E)+E)\ {\overset {(3)}{\Rightarrow }}\ ((i+E)+E)\ {\overset {(3)}{\Rightarrow }}\ ((i+i)+E)\ {\overset {(3)}{\Rightarrow }}\ ((i+i)+i)

सामान्यतः, सबसे बाएं गैर-टर्मिनल का विस्तार करने के लिए नियम का चयन करते समय अनेक संभावनाएं होती हैं। इस प्रकार पिछले उदाहरण के फेज 2 में, पार्सर को यह चुनना होगा कि नियम 2 या नियम 3 प्रयुक्त करना है :

S\ {\overset {(1)}{\Rightarrow }}\ E\ {\overset {(?)}{\Rightarrow }}\ ?

कुशल होने के लिए, पार्सर को जब भी संभव हो, बिना पीछे हटे, इस विकल्प को निश्चित रूप से चुनने में सक्षम होना चाहिए। कुछ ग्रामर के लिए, यह अपठित इनपुट (बिना पढ़े) पर द्रष्टि डालकर ऐसा कर सकता है। हमारे उदाहरण में, यदि पार्सर जानता है कि FOLLOW अपठित प्रतीक है $($ एकमात्र सही नियम जिसका उपयोग किया जा सकता है वह 2 है।

सामान्यतः, A $LL(k)$ पार्सर आगे $k$ प्रतीकों को देख सकता है। चूँकि, ग्रामर को देखते हुए, यह निर्धारित करने की समस्या कि क्या कुछ $k$ के लिए $LL(k)$ पार्सर उपस्थित है जो इसे पहचानता है, अनिर्णीत है। प्रत्येक k के लिए, ऐसी लैंग्वेज होती है जिसे $LL(k)$ पार्सर द्वारा नहीं पहचाना जा सकता है, किन्तु $LL(k+1)$ द्वारा पहचाना जा सकता है

हम उपरोक्त विश्लेषण का उपयोग निम्नलिखित औपचारिक परिभाषा देने के लिए कर सकते हैं:

मान लीजिए $G$ कांटेक्स्ट-फ्री ग्रामर है और $k\geq 1$ हम कहते हैं कि $G$ $LL(k)$ है, यदि और केवल यदि किन्हीं दो सबसे बाईं व्युत्पत्तियों के लिए:

$S\ \Rightarrow \ \cdots \ \Rightarrow \ wA\alpha \ \Rightarrow \ \cdots \ \Rightarrow \ w\beta \alpha \ \Rightarrow \ \cdots \ \Rightarrow \ wu$
$S\ \Rightarrow \ \cdots \ \Rightarrow \ wA\alpha \ \Rightarrow \ \cdots \ \Rightarrow \ w\gamma \alpha \ \Rightarrow \ \cdots \ \Rightarrow \ wv$

निम्नलिखित नियम प्रयुक्त होती है: लंबाई $k$ की स्ट्रिंग $u$ का उपसर्ग लंबाई $k$ की स्ट्रिंग $v$ के उपसर्ग के सामान होता है। अर्थात $\beta \ =\ \gamma$

इस परिभाषा में, $S$ प्रारंभ प्रतीक है और $A$ कोई गैर-टर्मिनल है। पहले से व्युत्पन्न इनपुट $w$ , और अभी तक अपठित $u$ और $v$ टर्मिनलों के तार हैं। ग्रीक अक्षर $\alpha$ $\beta$ और $\gamma$ दोनों टर्मिनलों और गैर-टर्मिनलों (संभवतः रिक्त) की किसी भी स्ट्रिंग का प्रतिनिधित्व करते हैं। उपसर्ग की लंबाई लुकहेड बफ़र आकार से मेल खाती है, और परिभाषा कहती है कि यह बफ़र विभिन्न शब्दों के किन्हीं दो व्युत्पत्तियों के बीच अंतर करने के लिए पर्याप्त है।

पार्सर

$LL(k)$ पार्सर नियतात्मक पुशडाउन ऑटोमेटन है जिसमें बिना पढ़े अगले $k$ इनपुट प्रतीकों पर द्रष्टि डालने की क्षमता है। इस झलक क्षमता का अनुकरण परिमित स्थिति स्थान में लुकहेड बफर पदार्थ को संग्रहीत करके किया जा सकता है, इस प्रकार क्योंकि बफर और इनपुट अल्फाबेट दोनों आकार में सीमित हैं। परिणाम स्वरुप, यह ऑटोमेटन को अधिक शक्तिशाली नहीं बनाता है, किन्तु सुविधाजनक एब्स्ट्रेक्ट है।

स्टैक अल्फाबेट $\Gamma =N\cup \Sigma$ है, जहां:

$N$ गैर-टर्मिनलों का सेट है;
$\Sigma$ विशेष एंड-ऑफ-इनपुट (ईओआई) प्रतीक के साथ टर्मिनल (इनपुट) प्रतीकों का सेट $\$$ .

पार्सर स्टैक में प्रारंभ में EOI के ऊपर प्रारंभिक प्रतीक होता है: $[\ S\ \$\ ]$ । ऑपरेशन के समय, पार्सर अधिकांशतः स्टैक के शीर्ष पर प्रतीक $X$ को परिवर्तित कर देता है:

कुछ $\alpha$ के साथ यदि $X\in N$ और नियम $X\to \alpha$ है
$\epsilon$ के साथ (कुछ नोटेशन $\lambda$ में), अर्थात $X$ को स्टैक से हटा दिया जाता है, यदि $X\in \Sigma$ है। इस स्थिति में, इनपुट प्रतीक $x$ पढ़ा जाता है और यदि $x\neq X$ है, तो पार्सर इनपुट को अस्वीकार कर देता है।

यदि स्टैक से हटाया जाने वाला अंतिम प्रतीक ईओआई है, तो पार्सिंग सफल है; ऑटोमेटन रिक्त स्टैक के माध्यम से स्वीकार करता है।

अवस्थाएँ और संक्रमण फलन स्पष्ट रूप से नहीं दिए गए हैं; इसके अतिरिक्त उन्हें अधिक सुविधाजनक पार्स टेबल का उपयोग करके निर्दिष्ट (उत्पन्न) किया जाता है। टेबल निम्नलिखित मानचित्रण प्रदान करती है:

पंक्ति: शीर्ष-स्टैक प्रतीक $X$
कॉलम: $|w|\leq k$ लुकअहेड बफ़र पदार्थ
सेल: के लिए नियम संख्या $X\to \alpha$ या $\epsilon$

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

ठोस उदाहरण

सेट अप

LL(1) पार्सर की कार्यप्रणाली को समझाने के लिए हम निम्नलिखित छोटे LL(1) ग्रामर पर विचार करेंगे

S → F
S → ( S + F )
F → a

और निम्नलिखित इनपुट को पार्स करें:

( a + a )

ग्रामर के लिए LL(1) पार्सिंग टेबल में प्रत्येक गैर-टर्मिनल के लिए पंक्ति और प्रत्येक टर्मिनल के लिए कॉलम होता है (विशेष टर्मिनल सहित, जिसे यहां $ के रूप में दर्शाया गया है, जिसका उपयोग इनपुट स्ट्रीम के अंत को संकेत करने के लिए किया जाता है)।

टेबल की प्रत्येक सेल ग्रामर के अधिकतम नियम (उसकी संख्या से पहचानी गई) की ओर संकेत कर सकती है। उदाहरण के लिए, उपरोक्त ग्रामर के लिए पार्सिंग टेबल में, गैर-टर्मिनल 'S' और टर्मिनल '(' के लिए सेल नियम संख्या 2 की ओर संकेत करता है:

	(	)	a	+	$
S	2	—	1	—	—
F	—	—	3	—	—

पार्सिंग टेबल बनाने के लिए एल्गोरिदम का वर्णन पश्चात् के अनुभाग में किया गया है, इस प्रकार किन्तु पहले देखते हैं कि पार्सर अपने इनपुट को संसाधित करने के लिए पार्सिंग टेबल का उपयोग कैसे करता है।

पार्सिंग प्रक्रिया

प्रत्येक फेज में, पार्सर इनपुट स्ट्रीम से अगले-उपलब्ध प्रतीक को पढ़ता है, और स्टैक से सबसे ऊपरी प्रतीक को पढ़ता है। इस प्रकार यदि इनपुट प्रतीक और स्टैक-टॉप प्रतीक मेल खाते हैं, तो पार्सर उन दोनों को हटा देता है, इनपुट स्ट्रीम और स्टैक पर केवल बेजोड़ प्रतीकों को छोड़ देता है।

इस प्रकार, अपने पहले फेज में, पार्सर इनपुट प्रतीक '(और स्टैक-टॉप प्रतीक 'S' को पढ़ता है। पार्सिंग टेबल निर्देश इनपुट प्रतीक '(शीर्ष वाले कॉलम और स्टैक-टॉप प्रतीक 'S' के नेतृत्व वाली पंक्ति से आता है; इस सेल में '2' होता है, जो पार्सर को नियम (2) प्रयुक्त करने का निर्देश देता है। इस प्रकार पार्सर को 'S' को हटाकर स्टैक पर 'S' से '( S + F )' को फिर से लिखना होता है। 'F', '+', 'S',को स्टैक पर दाब, और यह आउटपुट पर नियम संख्या 2 लिखता है। स्टैक तब बन जाता है:

[ (, S, +, F, ), $ ]

दूसरे फेज में, पार्सर अपनी इनपुट स्ट्रीम और स्टैक से '(' को हटा देता है, क्योंकि वह अब मेल खाते हैं। स्टैक अब बन जाता है:

[ S, +, F, ), $ ]

अब पार्सर के इनपुट स्ट्रीम पर 'A' और स्टैक टॉप के रूप में 'S' है। पार्सिंग टेबल इसे ग्रामर से नियम (1) प्रयुक्त करने और आउटपुट स्ट्रीम में नियम संख्या 1 लिखने का निर्देश देती है। संग्रह बन जाता है:

[ F, +, F, ), $ ]

पार्सर के पास अब इनपुट स्ट्रीम पर 'A' और स्टैक टॉप के रूप में 'F' है। पार्सिंग टेबल इसे ग्रामर से नियम (3) प्रयुक्त करने और आउटपुट स्ट्रीम में नियम संख्या 3 लिखने का निर्देश देती है। संग्रह बन जाता है:

[ a, +, F, ), $ ]

पार्सर में अब इनपुट स्ट्रीम पर 'a' है और इसके स्टैक टॉप पर 'a' है। क्योंकि वह समान हैं, इस प्रकार यह इसे इनपुट स्ट्रीम से हटा देता है और स्टैक के शीर्ष से पॉप कर देता है। पार्सर के पास इनपुट स्ट्रीम पर '+' होता है और '+' स्टैक के शीर्ष पर होता है, जिसका अर्थ है, 'A' की तरह, इसे स्टैक से पॉप किया जाता है और इनपुट स्ट्रीम से हटा दिया जाता है। इस में यह परिणाम:

[F, ), $ ]

अगले तीन फेजों में पार्सर स्टैक पर 'F' को 'A' से परिवर्तित कर देगा, आउटपुट स्ट्रीम में नियम संख्या 3 लिखेगा और स्टैक और इनपुट स्ट्रीम दोनों से 'A' और ')' को हटा देता है। इस प्रकार पार्सर अपने स्टैक और इनपुट स्ट्रीम दोनों पर '$' के साथ समाप्त होता है।

इस स्थिति में पार्सर रिपोर्ट करेगा कि उसने इनपुट स्ट्रिंग को स्वीकार कर लिया है और आउटपुट स्ट्रीम में नियम संख्याओं की निम्नलिखित सूची लिखेगा:

[2, 1, 3, 3 ]

यह वास्तव में इनपुट स्ट्रिंग के कांटेक्स्ट-फ्री ग्रामर व्युत्पत्ति और सिंटेक्स ट्री के लिए नियमों की सूची है, जो है:

S → ( S + F ) → ( F + F ) → ( a + F ) → ( a + a )

C++ में पार्सर कार्यान्वयन

उदाहरण लैंग्वेज के लिए टेबल-आधारित LL पार्सर का C++ कार्यान्वयन नीचे दिया गया है:

#include <iostream>
#include <map>
#include <stack>

enum Symbols {
	// the symbols:
	// Terminal symbols:
	TS_L_PARENS,	// (
	TS_R_PARENS,	// )
	TS_A,		// a
	TS_PLUS,	// +
	TS_EOS,		// $, in this case corresponds to '\0'
	TS_INVALID,	// invalid token

	// Non-terminal symbols:
	NTS_S,		// S
	NTS_F		// F
};

/*
Converts a valid token to the corresponding terminal symbol
*/
Symbols lexer(char c)
{
	switch (c)
	{
		case '(':  return TS_L_PARENS;
		case ')':  return TS_R_PARENS;
		case 'a':  return TS_A;
		case '+':  return TS_PLUS;
		case '\0': return TS_EOS; // end of stack: the $ terminal symbol
		default:   return TS_INVALID;
	}
}

int main(int argc, char **argv)
{
	using namespace std;

	if (argc < 2)
	{
		cout << "usage:\n\tll '(a+a)'" << endl;
		return 0;
	}

	// LL parser table, maps < non-terminal, terminal> pair to action
	map< Symbols, map<Symbols, int> > table;
	stack<Symbols>	ss;	// symbol stack
	char *p;	// input buffer

	// initialize the symbols stack
	ss.push(TS_EOS);	// terminal, $
	ss.push(NTS_S);		// non-terminal, S

	// initialize the symbol stream cursor
	p = &argv[1][0];

	// set up the parsing table
	table[NTS_S][TS_L_PARENS] = 2;
	table[NTS_S][TS_A] = 1;
	table[NTS_F][TS_A] = 3;

	while (ss.size() > 0)
	{
		if (lexer(*p) == ss.top())
		{
			cout << "Matched symbols: " << lexer(*p) << endl;
			p++;
			ss.pop();
		}
		else
		{
			cout << "Rule " << table[ss.top()][lexer(*p)] << endl;
			switch (table[ss.top()][lexer(*p)])
			{
				case 1:	// 1. S → F
					ss.pop();
					ss.push(NTS_F);	// F
					break;

				case 2:	// 2. S → ( S + F )
					ss.pop();
					ss.push(TS_R_PARENS);	// )
					ss.push(NTS_F);		// F
					ss.push(TS_PLUS);	// +
					ss.push(NTS_S);		// S
					ss.push(TS_L_PARENS);	// (
					break;

				case 3:	// 3. F → a
					ss.pop();
					ss.push(TS_A);	// a
					break;

				default:
					cout << "parsing table defaulted" << endl;
					return 0;
			}
		}
	}

	cout << "finished parsing" << endl;

	return 0;
}

पायथन में पार्सर कार्यान्वयन

# All constants are indexed from 0
TERM = 0
RULE = 1

# Terminals
T_LPAR = 0
T_RPAR = 1
T_A = 2
T_PLUS = 3
T_END = 4
T_INVALID = 5

# Non-Terminals
N_S = 0
N_F = 1

# Parse table
table = [[ 1, -1, 0, -1, -1, -1],
         [-1, -1, 2, -1, -1, -1]]

RULES = [[(RULE, N_F)],
         [(TERM, T_LPAR), (RULE, N_S), (TERM, T_PLUS), (RULE, N_F), (TERM, T_RPAR)],
         [(TERM, T_A)]]

stack = [(TERM, T_END), (RULE, N_S)]

def lexical_analysis(inputstring):
    print("Lexical analysis")
    tokens = []
    for c in inputstring:
        if c   == "+": tokens.append(T_PLUS)
        elif c == "(": tokens.append(T_LPAR)
        elif c == ")": tokens.append(T_RPAR)
        elif c == "a": tokens.append(T_A)
        else: tokens.append(T_INVALID)
    tokens.append(T_END)
    print(tokens)
    return tokens

def syntactic_analysis(tokens):
    print("Syntactic analysis")
    position = 0
    while len(stack) > 0:
        (stype, svalue) = stack.pop()
        token = tokens[position]
        if stype == TERM:
            if svalue == token:
                position += 1
                print("pop", svalue)
                if token == T_END:
                    print("input accepted")
            else:
                print("bad term on input:", token)
                break
        elif stype == RULE:
            print("svalue", svalue, "token", token)
            rule = table[svalue][token]
            print("rule", rule)
            for r in reversed(RULES[rule]):
                stack.append(r)
        print("stack", stack)

inputstring = "(a+a)"
syntactic_analysis(lexical_analysis(inputstring))

जैसा कि उदाहरण से देखा जा सकता है, पार्सर तीन प्रकार के फेज निष्पादित करता है जो इस बात पर निर्भर करता है कि स्टैक का शीर्ष नॉनटर्मिनल है, टर्मिनल है या विशेष प्रतीक $ है:

यदि शीर्ष नॉनटर्मिनल है तो पार्सर इस नॉनटर्मिनल और इनपुट स्ट्रीम पर प्रतीक के आधार पर पार्सिंग टेबल में देखता है कि उसे स्टैक पर नॉनटर्मिनल को परिवर्तित करने के लिए ग्रामर के किस नियम का उपयोग करना चाहिए। इस प्रकार नियम की संख्या आउटपुट स्ट्रीम पर लिखी जाती है। यदि पार्सिंग टेबल संकेत करती है कि ऐसा कोई नियम नहीं है तो पार्सर त्रुटि की रिपोर्ट करता है और रुक जाता है।
यदि शीर्ष टर्मिनल है तो पार्सर इसकी तुलना इनपुट स्ट्रीम पर प्रतीक से करता है और यदि वह सामान हैं तो वह दोनों हटा दिए जाते हैं। यदि वह समान नहीं हैं तो पार्सर त्रुटि की रिपोर्ट करता है और रुक जाता है।
यदि शीर्ष $ है और इनपुट स्ट्रीम पर भी $ है तो पार्सर रिपोर्ट करता है कि उसने इनपुट को सफलतापूर्वक पार्स कर लिया है, अन्यथा यह त्रुटि की रिपोर्ट करता है। दोनों ही स्थितियों में पार्सर संवर्त हो जाता है.

इन फेजों को तब तक दोहराया जाता है जब तक पार्सर संवर्त नहीं हो जाता है, और फिर यह या तो इनपुट को पूरी तरह से पार्स कर लेगा और आउटपुट स्ट्रीम में कांटेक्स्ट-फ्री ग्रामर व्युत्पत्ति और सिंटेक्स पेड़ लिखेगा या यह त्रुटि की सूचना देता है।

LL(1) पार्सिंग टेबल का निर्माण

पार्सिंग टेबल को भरने के लिए, हमें यह स्थापित करना होगा कि पार्सर को कौन सा ग्रामर नियम चुनना चाहिए यदि वह अपने स्टैक के शीर्ष पर नॉनटर्मिनल A और अपने इनपुट स्ट्रीम पर प्रतीक देखता है।

यह देखना सरल है कि ऐसा नियम A → w के रूप का होना चाहिए और w के अनुरूप लैंग्वेज में a से प्रारंभ होने वाली कम से कम स्ट्रिंग होनी चाहिए।

इस उद्देश्य के लिए हम w के पहले सेट को परिभाषित करते हैं, जिसे यहां 'Fi' (w) के रूप में लिखा गया है, टर्मिनलों के सेट के रूप में जो w में कुछ स्ट्रिंग की प्रारंभ में पाया जा सकता है, प्लस ε यदि रिक्त स्ट्रिंग भी w से संबंधित है।

नियमों A₁ → w₁,…, A_n → w_n के साथ ग्रामर को देखते हुए, हम प्रत्येक नियम के लिए Fi(w_i) और Fi(A_i) की गणना इस प्रकार कर सकते हैं:

प्रत्येक Fi(A_i) को रिक्त सेट के साथ प्रारंभ करें
प्रत्येक नियम A_i → w_i के लिए Fi(w_i) को Fi(A_i) में जोड़ें, जहां Fi को इस प्रकार परिभाषित किया गया है:
- प्रत्येक टर्मिनल A के लिए Fi(aw') = { a }
- प्रत्येक नॉनटर्मिनल A के लिए Fi(Aw') = 'Fi'(A) जिसमें ε 'Fi'(A) में नहीं है
- Fi(Aw' ) = ('Fi'(A) \ { ε }) ∪ Fi(w' ) 'Fi'(A) में ε के साथ प्रत्येक नॉनटर्मिनल A के लिए
- Fi(ε) = { ε }
प्रत्येक नियम A_i → w_i के लिए Fi(w_i) को Fi(A_i) में जोड़ें
फेज 2 और 3 तब तक करें जब तक कि सभी Fi सेट समान न रहें।

परिणाम निम्नलिखित प्रणाली के लिए सबसे कम निश्चित बिंदु समाधान है:

Fi(A) ⊇ Fi(w) प्रत्येक नियम A के लिए → w
Fi(a) ⊇ { a }, प्रत्येक टर्मिनल a के लिए
Fi(w₀ w₁) ⊇ Fi('w₀) · Fi(w₁), सभी शब्दों के लिए w₀ और w₁
Fi(ε) ⊇ {ε}

जहां, U और V शब्दों के सेट के लिए, काटे गए उत्पाद को $U\cdot V=\{(uv):1\mid u\in U,v\in V\}$ द्वारा परिभाषित किया गया है, और w:1 यदि w की लंबाई 0 या 1 है, तो लंबाई 2 या अधिक वाले शब्दों के प्रारंभिक लंबाई-1 उपसर्ग या स्वयं w को दर्शाता है।

सामान्यतः, FIRST-सेट पार्सिंग तालिका की गणना करने के लिए पर्याप्त नहीं हैं। ऐसा इसलिए है क्योंकि किसी नियम का दाहिना भाग w अंततः रिक्त स्ट्रिंग पर फिर से लिखा जा सकता है। इसलिए पार्सर को नियम A → w का भी उपयोग करना चाहिए यदि ε Fi(w) में है और यह इनपुट स्ट्रीम पर प्रतीक देखता है जो A का अनुसरण कर सकता है। इसलिए, हमें A के फॉलो-सेट की भी आवश्यकता है, जिसे Fo(A) के रूप में लिखा गया है ) यहां, जिसे टर्मिनलों के सेट के रूप में परिभाषित किया गया है, जैसे कि प्रतीकों αAaβ की स्ट्रिंग है जिसे प्रारंभ प्रतीक से प्राप्त किया जा सकता है। इस प्रकार हम $ को विशेष टर्मिनल के रूप में उपयोग करते हैं जो इनपुट स्ट्रीम के अंत को दर्शाता है, और S को प्रारंभ प्रतीक के रूप में उपयोग करता है।

ग्रामर में नॉनटर्मिनलों के लिए फॉलो-सेट की गणना निम्नानुसार की जा सकती है:

Fo(S) को { $ } से प्रारंभ करें और अन्य सभी Fo(A_i) को रिक्त सेट के साथ प्रारंभ करें
यदि A_j → wA_iw' रूप का कोई नियम है, तो
- यदि टर्मिनल a if(w' ) में है तो toDo(A_i) जोड़ें
- यदि ε if(w' ) में है, तो Do(Ai) में To(Aj) जोड़ें
- यदि w' की लंबाई 0 है, तो Fo(Ai) में Fo(Aj) जोड़ें
फेज 2 को तब तक दोहराएँ जब तक कि सभी फ़ो सेट समान न रहें।

यह निम्नलिखित प्रणाली को न्यूनतम निश्चित बिंदु समाधान प्रदान करता है:

Fo(S) ⊇ {$}
फॉर्म B के प्रत्येक नियम के लिए Fo(A) ⊇ Fi(w)·Fo(B) → ... A w

अब हम स्पष्ट रूप से परिभाषित कर सकते हैं कि पार्सिंग टेबल में कौन से नियम कहाँ दिखाई देंगे। यदि T[A, a] नॉनटर्मिनल A और टर्मिनल a के लिए टेबल में प्रविष्टि को दर्शाता है, तो

T[A,a] में नियम A → w सम्मिलित है यदि और केवल यदि

a Fi(w) या में है

ε Fi(w) में है और a Fo(A) में है।

समान रूप से: T[A, a] में प्रत्येक a ∈ Fi(w)·Fo(A) के लिए नियम A → w सम्मिलित है।

यदि टेबल में प्रत्येक कक्ष में अधिकतम नियम है, तो पार्सर को सदैव पता रहेगा कि उसे किस नियम का उपयोग करना है और इसलिए वह बिना बैकट्रैकिंग के स्ट्रिंग को पार्स कर सकता है। ठीक इसी स्थिति में ग्रामर को LL(1) ग्रामर कहा जाता है।

LL(k) पार्सिंग टेबल का निर्माण

LL(1) पार्सर के निर्माण को निम्नलिखित संशोधनों के साथ के > 1 के लिए LL(k) में अनुकूलित किया जा सकता है:

काटे गए उत्पाद को परिभाषित किया गया है $U\cdot V=\{(uv):k\mid u\in U,v\in V\}$ , जहां w:k लंबाई > k, या w, वाले शब्दों की प्रारंभिक लंबाई-k उपसर्ग को दर्शाता है, यदि w की लंबाई k या उससे कम है,
Fo(S) = {$^k}
LL(1) के लिए दिए गए Fi निर्माण के चरण 2 में Fi(αβ) = Fi(α)\cdot Fi(β) भी प्रयुक्त करें।
Fo निर्माण के चरण 2 में, A_j → wA_iw' के लिए बस Fo(A_j) में Fi(w')\cdot Fo(A_i) जोड़ें।

जहां k लुकअहेड कांटेक्स्ट को पूरी तरह से ध्यान में रखने के लिए, इनपुट को k एंड-मार्कर '$' द्वारा प्रत्यय दिया जाता है। यह दृष्टिकोण ε के लिए विशेष स्थितियों को समाप्त करता है, और LL (1) स्थिति में समान रूप से प्रयुक्त किया जा सकता है।

1990 के दशक के मध्य तक, यह व्यापक रूप से माना जाता था कि LL(k) पार्सिंग (k > 1 के लिए) अव्यावहारिक थी, चूंकि सबसे व्यर्थ स्थिति में पार्सर टेबल में k में घातीय फ़ंक्शन आकार होता है। यह धारणा 1992 के आसपास पर्ड्यू कंपाइलर कंस्ट्रक्शन टूल सेट के जारी होने के पश्चात् धीरे-धीरे परिवर्तित कर गई, जब यह प्रदर्शित किया गया कि अनेक प्रोग्रामिंग लैंग्वेज को पार्सर के सबसे व्यर्थ स्थिति वाले व्यवहार को ट्रिगर किए बिना LL(k) पार्सर द्वारा कुशलतापूर्वक पार्स किया जा सकता है। इसके अतिरिक्त, कुछ स्थितियों में LL पार्सिंग असीमित लुकहेड के साथ भी संभव है। इसके विपरीत, yacc जैसे पारंपरिक पार्सर जनरेटर निश्चित वन-टोकन लुकहेड के साथ प्रतिबंधित LR पार्सर का निर्माण करने के लिए LALR पार्सर या LALR(1) पार्सर टेबलओं का उपयोग करते हैं।

कॉन्फ्लिक्ट

जैसा कि परिचय में बताया गया है, LL(1) पार्सर उन लैंग्वेज को पहचानते हैं जिनमें LL(1) ग्रामर होते हैं, इस प्रकार जो कांटेक्स्ट-फ्री ग्रामर का विशेष स्थिति है; इस प्रकार LL(1) पार्सर सभी कांटेक्स्ट-फ्री लैंग्वेज को नहीं पहचान सकते है। LL(1) लैंग्वेज एलआर(1) लैंग्वेज का उचित उपसमूह हैं, जो परिवर्तन में सभी कांटेक्स्ट-फ्री लैंग्वेज का उचित उपसमूह हैं। कांटेक्स्ट-फ्री ग्रामर को LL(1) ग्रामर बनाने के लिए, कुछ विरोध उत्पन्न नहीं होने चाहिए, जिनका वर्णन हम इस खंड में करते हैं।

शब्दावली

मान लीजिए A गैर-टर्मिनल है। FIRST(A) टर्मिनलों का सेट (परिभाषित) है जो A से प्राप्त किसी भी स्ट्रिंग की पहली स्थिति में दिखाई दे सकता है। FOLLOW(A) यूनियन ओवर है:^[11]

FIRST(B) जहां B कोई गैर-टर्मिनल है जो प्रोडक्सन नियम के दाईं ओर A का तुरंत अनुसरण करता है।
FOLLOW(B) जहां B फॉर्म B → wA के नियम का कोई शीर्ष है।

LL(1) कॉन्फ्लिक्ट

LL(1) कॉन्फ्लिक्ट के दो मुख्य प्रकार हैं:

FIRST/FIRST कॉन्फ्लिक्ट

ही गैर-टर्मिनल प्रतिच्छेद के लिए दो अलग-अलग ग्रामर नियमों का FIRST सेट LL(1) FIRST/FIRST कॉन्फ्लिक्ट का उदाहरण:

S -> E | E 'a'
E -> 'b' | ε

FIRST(E) = {b, ε} और FIRST(E a) = {b, a}, इसलिए जब टेबल बनाई जाती है, तो प्रोडक्सन नियम S के टर्मिनल b के अनुसार कॉन्फ्लिक्ट होता है।

विशेष स्थिति: बाईं रिकर्सन

बायाँ प्रत्यावर्तन सभी विकल्पों के साथ FIRST/FIRST कॉन्फ्लिक्ट का कारण होता है।

E -> E '+' term | alt1 | alt2

FIRST/अनुसरण कॉन्फ्लिक्ट

ग्रामर नियम का FIRST और FOLLOW सेट ओवरलैप होता है। पहले सेट में रिक्त स्ट्रिंग (ε) के साथ, यह अज्ञात है कि कौन सा विकल्प चुनना है। LL(1) कॉन्फ्लिक्ट का उदाहरण:

S -> A 'a' 'b'
A -> 'a' | ε

A का FIRST सेट {a, ε} है, और FOLLOW सेट {a} है।

LL(1) कॉन्फ्लिक्टों का समाधान

बाईं फैक्टरिंग

सामान्य बाईं-कारक को दूर कर दिया गया है।

A -> X | X Y Z

बन जाता है

A -> X B
B -> Y Z | ε

इसे तब प्रयुक्त किया जा सकता है जब दो विकल्प ही प्रतीक से प्रारंभ होते हैं जैसे FIRST/FIRST कॉन्फ्लिक्ट है। उपरोक्त FIRST/FIRST कॉन्फ्लिक्ट उदाहरण का उपयोग करते हुए और उदाहरण (अधिक काम्प्लेक्स):

S -> E | E 'a'
E -> 'b' | ε

बन जाता है (एकल गैर-टर्मिनल में विलय)

S -> 'b' | ε | 'b' 'a' | 'a'

फिर बाईं-फैक्टरिंग के माध्यम से, बन जाता है

S -> 'b' E | E
E -> 'a' | ε

प्रतिस्थापन

अप्रत्यक्ष या FIRST/FOLLOW विरोधों को दूर करने के लिए नियम को दूसरे नियम में प्रतिस्थापित करता है। ध्यान दें कि इससे FIRST/FIRST विरोध उत्पन्न हो सकता है।

बाईं पुनरावर्तन निष्कासन

देखना ^[12] सामान्य विधि के लिए, बायाँ प्रत्यावर्तन बायाँ प्रत्यावर्तन हटाना देखें।

बाएँ पुनरावर्तन को हटाने का सरल उदाहरण है: निम्नलिखित प्रोडक्सन नियम ने E पर रिकर्सन छोड़ दिया है

E -> E '+' T
E -> T

यह नियम और कुछ नहीं किन्तु '+' से अलग की गई Ts की सूची है। रेगुलर फॉर्म T ('+' T)* में अतः नियम को इस प्रकार पुनः लिखा जा सकता है

E -> T Z                                                             
Z -> '+' T Z                                                                                                              
Z -> ε

अब कोई बाईं रिकर्सन नहीं है और किसी भी नियम पर कोई कोलिसन नहीं है। चूँकि, सभी कांटेक्स्ट-फ्री ग्रामर में समतुल्य LL(k)-ग्रामर नहीं होता है, उदाहरण के लिए:

S -> A | B
A -> 'a' A 'b' | ε
B -> 'a' B 'b' 'b' | ε

यह दिखाया जा सकता है कि इस ग्रामर द्वारा उत्पन्न लैंग्वेज को स्वीकार करने वाला कोई LL(k)-ग्रामर उपस्थित नहीं है।

यह भी देखें

पार्सर जनरेटर की तुलना
पार्सर ट्री
ऊपर से नीचे पार्सिंग
नीचे से ऊपर की ओर पार्सिंग

↑ Rosenkrantz, D. J.; Stearns, R. E. (1970). "नियतिवादी टॉप डाउन व्याकरण के गुण". Information and Control. 17 (3): 226–256. doi:10.1016/s0019-9958(70)90446-8.
↑ Jarzabek, Stanislav; Krawczyk, Tomasz (1974). "एलएल-नियमित व्याकरण". Instytutu Maszyn Matematycznych: 107–119.
↑ Jarzabek, Stanislav; Krawczyk, Tomasz (Nov 1975). "एलएल-नियमित व्याकरण". Information Processing Letters. 4 (2): 31–37. doi:10.1016/0020-0190(75)90009-5.
↑ David A. Poplawski (Aug 1977). एलएल-नियमित भाषाओं के गुण (Technical Report). Purdue University, Department of Computer Science.
↑ Parr, Terence and Fisher, Kathleen (2011). "एलएल (*) एएनटीएलआर पार्सर जनरेटर की नींव". ACM SIGPLAN Notices. 46 (6): 425–436. doi:10.1145/1993316.1993548.{{cite journal}}: CS1 maint: multiple names: authors list (link)
↑ Belcak, Peter (2020). "इष्टतम एलएल(के) पार्सिंग के लिए एलएल(परिमित) पार्सिंग रणनीति". arXiv:2010.07874 [cs.PL].
↑ Ford, Bryan (2004). "Parsing Expression Grammars: A Recognition-Based Syntactic Foundation". ACM SIGPLAN Notices. doi:10.1145/982962.964011.
↑ Pat Terry (2005). C# और Java के साथ संकलन. Pearson Education. pp. 159–164. ISBN 9780321263605.
↑ William M. Waite and Gerhard Goos (1984). संकलक निर्माण. Texts and Monographs in Computer Science. Heidelberg: Springer. ISBN 978-3-540-90821-0. Here: Sect. 5.3.2, p. 121-127; in particular, p. 123.
↑ Richard E. Stearns and P.M. Lewis (1969). "संपत्ति व्याकरण और तालिका मशीनें". Information and Control. 14 (6): 524–549. doi:10.1016/S0019-9958(69)90312-X.
↑ "एलएल व्याकरण" (PDF). Archived (PDF) from the original on 2010-06-18. Retrieved 2010-05-11.
↑ Modern Compiler Design, Grune, Bal, Jacobs and Langendoen

बाहरी संबंध

A tutorial on implementing LL(1) parsers in C# (archived)
Parsing Simulator This simulator is used to generate parsing tables LL(1) and to resolve the exercises of the book.
LL(1) DSL PEG parser (toolkit framework)
Language theoretic comparison of LL and LR grammars
LL(k) Parsing Theory

[1] Rosenkrantz, D. J.; Stearns, R. E. (1970). "नियतिवादी टॉप डाउन व्याकरण के गुण". Information and Control. 17 (3): 226–256. doi:10.1016/s0019-9958(70)90446-8.

[2] Jarzabek, Stanislav; Krawczyk, Tomasz (1974). "एलएल-नियमित व्याकरण". Instytutu Maszyn Matematycznych: 107–119.

[3] Jarzabek, Stanislav; Krawczyk, Tomasz (Nov 1975). "एलएल-नियमित व्याकरण". Information Processing Letters. 4 (2): 31–37. doi:10.1016/0020-0190(75)90009-5.

[4] David A. Poplawski (Aug 1977). एलएल-नियमित भाषाओं के गुण (Technical Report). Purdue University, Department of Computer Science.

[5] Parr, Terence and Fisher, Kathleen (2011). "एलएल (*) एएनटीएलआर पार्सर जनरेटर की नींव". ACM SIGPLAN Notices. 46 (6): 425–436. doi:10.1145/1993316.1993548.{{cite journal}}: CS1 maint: multiple names: authors list (link)

[6] Belcak, Peter (2020). "इष्टतम एलएल(के) पार्सिंग के लिए एलएल(परिमित) पार्सिंग रणनीति". arXiv:2010.07874 [cs.PL].

[7] Ford, Bryan (2004). "Parsing Expression Grammars: A Recognition-Based Syntactic Foundation". ACM SIGPLAN Notices. doi:10.1145/982962.964011.

[8] Pat Terry (2005). C# और Java के साथ संकलन. Pearson Education. pp. 159–164. ISBN 9780321263605.

[9] William M. Waite and Gerhard Goos (1984). संकलक निर्माण. Texts and Monographs in Computer Science. Heidelberg: Springer. ISBN 978-3-540-90821-0. Here: Sect. 5.3.2, p. 121-127; in particular, p. 123.

[10] Richard E. Stearns and P.M. Lewis (1969). "संपत्ति व्याकरण और तालिका मशीनें". Information and Control. 14 (6): 524–549. doi:10.1016/S0019-9958(69)90312-X.

[11] "एलएल व्याकरण" (PDF). Archived (PDF) from the original on 2010-06-18. Retrieved 2010-05-11.

[12] Modern Compiler Design, Grune, Bal, Jacobs and Langendoen

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

Anonymous

Search

एलएल पार्सर

Namespaces

More

Page actions

Contents

अवलोकन

पार्सर

ठोस उदाहरण

सेट अप

पार्सिंग प्रक्रिया

C++ में पार्सर कार्यान्वयन

पायथन में पार्सर कार्यान्वयन

टिप्पणियाँ

LL(1) पार्सिंग टेबल का निर्माण

LL(k) पार्सिंग टेबल का निर्माण

कॉन्फ्लिक्ट

शब्दावली

LL(1) कॉन्फ्लिक्ट

FIRST/FIRST कॉन्फ्लिक्ट

विशेष स्थिति: बाईं रिकर्सन

FIRST/अनुसरण कॉन्फ्लिक्ट

LL(1) कॉन्फ्लिक्टों का समाधान

बाईं फैक्टरिंग

प्रतिस्थापन

बाईं पुनरावर्तन निष्कासन

यह भी देखें

टिप्पणियाँ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

एलएल पार्सर

अवलोकन

पार्सर

ठोस उदाहरण

सेट अप

पार्सिंग प्रक्रिया

C++ में पार्सर कार्यान्वयन

पायथन में पार्सर कार्यान्वयन

टिप्पणियाँ

LL(1) पार्सिंग टेबल का निर्माण

LL(k) पार्सिंग टेबल का निर्माण

कॉन्फ्लिक्ट

शब्दावली

LL(1) कॉन्फ्लिक्ट

FIRST/FIRST कॉन्फ्लिक्ट

विशेष स्थिति: बाईं रिकर्सन

FIRST/अनुसरण कॉन्फ्लिक्ट

LL(1) कॉन्फ्लिक्टों का समाधान

बाईं फैक्टरिंग

प्रतिस्थापन

बाईं पुनरावर्तन निष्कासन

यह भी देखें

टिप्पणियाँ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories