मैं लिखने वाले कंपाइलर्स के साथ चारों ओर घूम रहा हूं और सिंटैक्स विश्लेषण के पीछे सिद्धांत के बारे में सीख रहा हूं। मैंने पाया है कि भले ही यह मान्यता एल्गोरिदम को समझने के लिए एक महत्वपूर्ण अवधारणा है, नेट पर इसके बारे में जानकारी काफी खराब है। ऐसा लगता है कि इस समस्या को ठीक करने के लिए StackOverflow एक अद्वितीय स्थिति में है।लुकहेड सेट की सटीक परिभाषा क्या है?
व्याकरण के लिए लुकहेड सेट को प्रत्येक गैर-टर्मिनल के लिए लुकहेड सेट के संदर्भ में परिभाषित किया जाता है, जो बदले में प्रत्येक उत्पादन के लिए लुकहेड सेट पर निर्भर करता है। लुकहेड सेट निर्धारित करने से हमें यह निर्धारित करने में मदद मिल सकती है कि व्याकरण एलएल (1) है, और यदि यह है, तो इसके लिए हमें एक रिकर्सिव-डेसेंट पार्सर बनाने के लिए कौन सी जानकारी की आवश्यकता है।
परिभाषा:अग्रावलोकन (एक्स -> α) और अग्रावलोकन (एक्स):
LOOKAHEAD(X -> α) = FIRST(α) U FOLLOW(X), if NULLABLE(α)
LOOKAHEAD(X -> α) = FIRST(α), if not NULLABLE(α)
LOOKAHEAD(X) = LOOKAHEAD(X -> α) U LOOKAHEAD(X -> β) U LOOKAHEAD(X -> γ)
जहां पहले (α) टर्मिनलों कि α के साथ शुरू कर सकते हैं का एक समूह है, FOLLOW (X) टर्मिनल का सेट है जो व्याकरण में कहीं भी एक्स के बाद आ सकता है, और NULLABLE (α) यह है कि α एक खाली अनुक्रम प्राप्त कर सकता है या नहीं टर्मिनलों का प्रतीक (निर्दिष्ट ε)। निम्नलिखित परिभाषाएं टोरबेन मोगेन्सन की मुफ्त पुस्तक, Basics of Compiler Design से ली गई हैं। उदाहरण के लिए नीचे देखें।
परिभाषा:नल (एक्स):
NULLABLE(ε) = true
NULLABLE(x) = false, if x is a terminal
NULLABLE(αβ) = NULLABLE(α) and NULLABLE(β)
NULLABLE(P) = NULLABLE(α_1) or NULLABLE(α_2) or ... or NULLABLE(α_n),
if P is a non-terminal and the right-hand-sides
of all its productions are α_1, α_2, ..., α_n.
परिभाषा:पहले (एक्स):
FIRST(ε) = Ø
FIRST(x) = {x}, assuming x is a terminal
FIRST(αβ) = FIRST(α) U FIRST(β), if NULLABLE(α)
= FIRST(α), if not NULLABLE(α)
FIRST(P) = FIRST(α_1) U FIRST(α_2) U ... U FIRST(α_n),
if P is a non-terminal and the right-hand-sides
of all its productions are α_1, α_2, ..., α_n.
परिभाषा:का पालन करें (एक्स):
एक टर्मिनल प्रतीक एक का पालन करें (एक्स) में है अगर और तभी शुरू प्रतीक व्याकरण ऐसी है कि एस ⇒ αX aβ के एस, जहां α और β संभवतः कर रहे हैं (से एक व्युत्पत्ति है खाली) व्याकरण प्रतीकों के अनुक्रम।
अंतर्ज्ञान:का पालन करें (एक्स): जहां एक्स व्याकरण में होता है पर
देखो। सभी टर्मिनल जो का पालन कर सकते हैं (सीधे या किसी भी स्तर पर रिकर्सन) FOLLOW (X) में है। साथ ही, यदि एक्स एक उत्पादन (जैसे
A -> foo X) के अंत में होता है, या कुछ और के द्वारा पीछा किया जाता है कि ε को कम कर सकते हैं (उदाहरण के लिएA -> foo X BऔरB -> ε), तो जो कुछ भी एक द्वारा पीछा किया जा सकता है, एक्स कर सकते हैं इसके बाद भी (यानीFOLLOW(A) ⊆ FOLLOW(X))।
टॉर्बेन की पुस्तक में का पालन करें (एक्स) और बस से नीचे का एक प्रदर्शन को निर्धारित करने के लिए विधि देखें।
एक उदाहरण:
E -> n A
A -> E B
A -> ε
B -> + A
B -> * A
पहले, नल और पहले और निर्धारित कर रहे हैं:
NULLABLE(E) = NULLABLE(n A) = NULLABLE(n) ∧ NULLABLE(A) = false
NULLABLE(A) = NULLABLE(E B) ∨ NULLABLE(ε) = true
NULLABLE(B) = NULLABLE(+ A) ∨ NULLABLE(* A) = false
FIRST(E) = FIRST(n A) = {n}
FIRST(A) = FIRST(E B) U FIRST(ε) = FIRST(E) U Ø = {n} (because E is not NULLABLE)
FIRST(B) = FIRST(+ A) U FIRST(* A) = FIRST(+) U FIRST(*) = {+, *}
पहले पालन निर्धारित किया जाता है, उत्पादन E' -> E $ जोड़ा जाता है, जहां $ को "एंड-ऑफ-फाइल" गैर- टर्मिनल। तब अनुसरण निर्धारित होता है:
FOLLOW(E): Let β = $, so add the constraint that FIRST($) = {$} ⊆ FOLLOW(E)
Let β = B, so add the constraint that FIRST(B) = {+, *} ⊆ FOLLOW(E)
FOLLOW(A): Let β = ε, so add the constraint that FIRST(ε) = Ø ⊆ FOLLOW(A).
Because NULLABLE(ε), add the constraint that FOLLOW(E) ⊆ FOLLOW(A).
Let β = ε, so add the constraint that FIRST(ε) = Ø ⊆ FOLLOW(A).
Because NULLABLE(ε), add the constraint that FOLLOW(B) ⊆ FOLLOW(A).
Let β = ε, so add the constraint that FIRST(ε) = Ø ⊆ FOLLOW(A).
Because NULLABLE(ε), add the constraint that FOLLOW(B) ⊆ FOLLOW(A).
FOLLOW(B): Let β = ε, so add the constraint that FIRST(ε) = Ø ⊆ FOLLOW(B).
Because NULLABLE(ε), add the constraint that FOLLOW(A) ⊆ FOLLOW(B).
इन बाधाओं का समाधान कर रहा है (यह भी तय सूत्री यात्रा करके प्राप्त किया जा सकता है),
{+, *, $} ⊆ FOLLOW(E)
FOLLOW(E) ⊆ FOLLOW(A)
FOLLOW(A) = FOLLOW(B)
FOLLOW(E) = FOLLOW(A) = FOLLOW(B) = {+, *, $}.
अब प्रत्येक उत्पादन के लिए अग्रावलोकन निर्धारित किया जा सकता:
LOOKAHEAD(E -> n A) = FIRST(n A) = {n} because ¬NULLABLE(n A)
LOOKAHEAD(A -> E B) = FIRST(E B) because ¬NULLABLE(E B)
= FIRST(E) = {n} because ¬NULLABLE(E)
LOOKAHEAD(A -> ε) = FIRST(ε) U FOLLOW(A) because NULLABLE(ε)
= Ø U {+, *, $} = {+, *, $}
LOOKAHEAD(B -> + A) = FIRST(+ A) because ¬NULLABLE(+ A)
= FIRST(+) = {+} because ¬NULLABLE(+)
LOOKAHEAD(B -> * A) = {*} for the same reason
अंत में, लुकहाइड के लिए आर प्रत्येक गैर टर्मिनल निर्धारित किया जा सकता:
LOOKAHEAD(E) = LOOKAHEAD(E -> n A) = {n}
LOOKAHEAD(A) = LOOKAHEAD(A -> E B) U LOOKAHEAD(A -> ε) = {n} U {+, *, $}
LOOKAHEAD(B) = LOOKAHEAD(B -> + A) U LOOKAHEAD(B -> * A) = {+, *}
इस ज्ञान से हम तय कर सकते हैं कि इस व्याकरण डालूँगा नहीं है (1) क्योंकि अपने गैर टर्मिनलों अतिव्यापी अग्रदर्शी सेट हैं। (यानी, हम एक प्रोग्राम नहीं बना सकते हैं जो एक समय में एक प्रतीक पढ़ता है और जो उत्पादन का उपयोग करने के लिए अनजाने में निर्णय लेता है।)
सरल उत्तर है, "टोकन का सेट जिसे आप कुछ संदर्भ में अगली उम्मीद करते हैं"। –