एलएल पार्सर

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

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

एक एलएल पार्सर को एलएल-रेगुलर (एलएलआर) कहा जाता है यदि यह एलएल-रेगुलर भाषा को पार्स करता है। एलएल-नियमित व्याकरण की कक्षा में प्रत्येक के के लिए प्रत्येक एलएल(के) व्याकरण शामिल है। प्रत्येक एलएलआर व्याकरण के लिए एलएलआर पार्सर मौजूद होता है जो व्याकरण को रैखिक समय में पार्स करता है।

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

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

सिंहावलोकन

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

1. $S\to E$
2. $E\to (E+E)$
3. $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 }}\ ?$

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

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

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

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

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

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

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

== पार्सर == $LL(k)$ h> पार्सर नियतात्मक पुशडाउन ऑटोमेटन है जिसमें अगले पर नज़र डालने की क्षमता होती है $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$

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

ठोस उदाहरण

सेट अप

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

1. एस → एफ
2. एस → ( एस + एफ )
3. एफ → ए

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

( ए + ए )

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

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

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

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

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

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

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

[(, एस, +, एफ, ), $ ]

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

[एस, +, एफ, ), $ ]

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

[एफ, +, एफ, ), $ ]

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

[ए, +, एफ, ), $ ]

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

[एफ, ), $ ]

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

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

[2, 1, 3, 3 ]

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

एस → (एस + एफ) → (एफ + एफ) → (ए + एफ) → (ए + ए)

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

टिप्पणियाँ

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

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

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

एक एलएल(1) पार्सिंग तालिका का निर्माण

पार्सिंग तालिका को भरने के लिए, हमें यह स्थापित करना होगा कि पार्सर को कौन सा व्याकरण नियम चुनना चाहिए यदि वह अपने स्टैक के शीर्ष पर नॉनटर्मिनल ए और अपने इनपुट स्ट्रीम पर प्रतीक देखता है। यह देखना आसान है कि ऐसा नियम A → w के रूप का होना चाहिए और w के अनुरूप भाषा में a से शुरू होने वाली कम से कम स्ट्रिंग होनी चाहिए। इस उद्देश्य के लिए हम w के पहले सेट को परिभाषित करते हैं, जिसे यहां 'Fi' (w) के रूप में लिखा गया है, टर्मिनलों के सेट के रूप में जो w में कुछ स्ट्रिंग की शुरुआत में पाया जा सकता है, प्लस ε यदि खाली स्ट्रिंग भी w से संबंधित है। नियम ए के साथ व्याकरण दिया गया₁ → डब्ल्यू₁, …, ए_n → डब्ल्यू_n, हम Fi(w की गणना कर सकते हैं_i) और Fi(ए_i) प्रत्येक नियम के लिए इस प्रकार है:

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

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

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

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

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

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

1. 'Fo'(S) को { '$' } और अन्य सभी 'Fo'(A) से प्रारंभ करें_i) खाली सेट के साथ
2. अगर फॉर्म ए का नियम है_j → वा_iw' , फिर
   • यदि टर्मिनल a 'Fi'(w' ) में है, तो 'फॉर्म'(A) में a जोड़ें_i)
   • यदि ε फ़ाइल में है, तो इसमें जोड़ें(एj) से फॉर्म(एi)
   • यदि a' की लंबाई 0 है, तो 'To'(A) जोड़ें_j) से फॉर्म(ए_i)
3. चरण 2 को तब तक दोहराएँ जब तक कि सभी फ़ो सेट समान न रहें।

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

• Fo(S) ⊇ {$}
• फॉर्म बी के प्रत्येक नियम के लिए 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) के लिए नियम A → w शामिल है ·Fo(ए).

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

एक एलएल(के) पार्सिंग तालिका का निर्माण

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

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

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

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

संघर्ष

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

शब्दावली

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

1. FIRST(B) जहां B कोई गैर-टर्मिनल है जो औपचारिक व्याकरण के दाईं ओर A के ठीक बाद आता है#व्याकरण का वाक्य-विन्यास।
2. अनुसरण करें(बी) जहां बी फॉर्म बी → डब्ल्यूए के नियम का कोई शीर्ष है।

एलएल(1) संघर्ष

एलएल(1) संघर्ष के दो मुख्य प्रकार हैं:

पहला/प्रथम संघर्ष

एक ही गैर-टर्मिनल प्रतिच्छेद के लिए दो अलग-अलग व्याकरण नियमों का पहला सेट। एलएल(1) प्रथम/प्रथम संघर्ष का उदाहरण:

एस -> ई | ई 'ए'
ई -> 'बी' | ε

FIRST(E) = {b, ε} और FIRST(E a) = {b, a}, इसलिए जब तालिका बनाई जाती है, तो उत्पादन नियम S के टर्मिनल b के तहत संघर्ष होता है।

विशेष मामला: बाईं पुनरावृत्ति

बायाँ प्रत्यावर्तन सभी विकल्पों के साथ प्रथम/प्रथम संघर्ष का कारण बनेगा।

ई -> ई '+' पद | alt1 | alt2

पहला/अनुसरण संघर्ष

व्याकरण नियम का पहला और अगला सेट ओवरलैप होता है। पहले सेट में खाली स्ट्रिंग (ε) के साथ, यह अज्ञात है कि कौन सा विकल्प चुनना है। एलएल(1) संघर्ष का उदाहरण:

एस -> ए 'ए' 'बी'
ए -> 'ए' | ε

A का पहला सेट {a, ε} है, और अगला सेट {a} है।

एलएल(1) संघर्षों का समाधान

वाम फैक्टरिंग

एक सामान्य वाम-कारक को दूर कर दिया गया है।

ए -> एक्स | एक्स वाई जेड

बन जाता है

ए -> एक्स बी
बी -> वाई जेड | ε

इसे तब लागू किया जा सकता है जब दो विकल्प ही प्रतीक से शुरू होते हैं जैसे FIRST/FIRST संघर्ष।

उपरोक्त FIRST/FIRST संघर्ष उदाहरण का उपयोग करते हुए और उदाहरण (अधिक जटिल):

एस -> ई | ई 'ए'
ई -> 'बी' | ε

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

एस -> 'बी' | ε | 'बी' 'ए' | 'ए'

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

एस -> 'बी' ई | इ
ई -> 'ए' | ε

प्रतिस्थापन

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

वाम पुनरावर्तन निष्कासन

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

ई -> ई '+' टी
ई -> टी

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

ई -> टी जेड
Z -> '+' T Z
जेड -> ε

अब कोई वाम पुनरावृत्ति नहीं है और किसी भी नियम पर कोई टकराव नहीं है।

हालाँकि, सभी संदर्भ-मुक्त व्याकरणों में समतुल्य LL(k)-व्याकरण नहीं होता है, उदाहरण के लिए:

एस -> ए | बी
ए -> 'ए' ए 'बी' | ε
बी -> 'ए' बी 'बी' 'बी' | ε

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

यह भी देखें

• पार्सर जनरेटर की तुलना
• पारस वृक्ष
• ऊपर से नीचे विश्लेषण
• नीचे से ऊपर की ओर पार्सिंग

बाहरी संबंध

• 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