व्याकरण को ग्राफ संरचना के रूप में
एक कंपाइलर सोर्स कोड का अनुवाद पार्स ट्री बनाकर करता है — एक मूल वृक्ष जहां प्रत्येक नोड एक लागू व्याकरण नियम का प्रतिनिधित्व करता है, & प्रत्येक पत्ती एक टर्मिनल प्रतीक (चर नाम, शाब्दिक, ऑपरेटर) का प्रतिनिधित्व करता है।
वृक्ष ज्यामिति
n नोड्स & n−1 किनारों वाला एक वृक्ष। गहराई d: मूल से किसी भी पत्ती तक की अधिकतम दूरी। d की गहराई वाले संतुलित बाइनरी वृक्ष के लिए: 2^d तक पत्तियां & 2^(d+1)−1 कुल नोड्स।
विशिष्ट अभिव्यक्तियों के लिए पार्स ट्री संतुलित नहीं होते: ऑपरेटर प्राथमिकता दाएं-तिरछे या बाएं-तिरछे पेड़ों को बनाती है। A + B C एक ऐसा वृक्ष बनाता है जहां + से गहरा है, यह दर्शाता है कि * अधिक कसकर बंधता है।
BNF & ALGOL
Backus-Naur Form (BNF), ALGOL को निर्दिष्ट करने के लिए आविष्कृत, व्याकरण को उत्पादन नियमों के रूप में औपचारिक बनाता है:
``
<expr> ::= <term> | <expr> + <term>
<term> ::= <factor> | <term> * <factor>
<factor> ::= id | (<expr>)
``
प्रत्येक उत्पादन नियम वृक्ष का एक स्तर परिभाषित करता है। व्याकरण गैर-टर्मिनल प्रतीकों पर एक निर्देशित ग्राफ है; एक वाक्य को पार्स करना उस ग्राफ के माध्यम से शुरुआत प्रतीक से पत्तियों तक एक पथ का पता लगाता है।
पार्स ट्री की गहराई & अभिव्यक्ति की जटिलता
(A + B) * (C + D) अभिव्यक्ति के लिए, पार्स ट्री मानक ऑपरेटर प्राथमिकता के तहत एक विशिष्ट संरचना है।
पार्स ट्री की गहराई कंपाइलर के प्रदर्शन को प्रभावित करती है: गहरे पेड़ों को पुनरावर्ती अवरोही पार्सिंग के दौरान अधिक स्टैक फ्रेम की आवश्यकता होती है।
Shannon एंट्रॉपी & अतिरेक
Hamming ने नोट किया कि बोली जाने वाली भाषा ~60% अतिरेक है, लिखित भाषा ~40%। इसका एक सटीक सूचना-सैद्धांतिक अर्थ है।
Shannon एंट्रॉपी
{p₁, p₂, ..., pₙ} संभाव्यताओं के साथ वर्णमाला A से प्रतीक उत्पन्न करने वाले स्रोत के लिए:
H = −Σ pᵢ log₂(pᵢ) (प्रति प्रतीक बिट्स)
अधिकतम एंट्रॉपी: समान वितरण (सभी प्रतीक समान रूप से संभावित)। H_max = log₂(n) n प्रतीकों के लिए।
अतिरेक R: बिट्स का अंश जो कोई सूचना नहीं ले जाता है (संदर्भ से भविष्यवाणी की जा सकती है):
R = 1 − H / H_max
यदि R = 0.4 (40% अतिरेक): 40% बिट्स संदर्भ से भविष्यवाणी योग्य हैं। 8 बिट्स/वर्ण पर अंग्रेजी पाठ ले जाने वाली एक चैनल सूचना के लिए केवल 60% क्षमता का उपयोग कर रही है; 40% संरचना है जो प्राप्तकर्ता पहले से जानता है।
त्रुटि पहचान अतिरेक का उपयोग करती है: यदि 40% बिट्स भविष्यवाणी योग्य हैं, तो एक संचरण त्रुटि एक ऐसा अनुक्रम बना सकती है जो अतिरेक संरचना का उल्लंघन करता है — त्रुटि-सुधार कोड के बिना भी पता लगाया जा सकता है।
APL की लगभग-शून्य अतिरेक: एक एकल वर्ण परिवर्तन संदर्भ से लगभग कभी भी पता लगाने योग्य नहीं है। अंग्रेजी की 60% अतिरेक: आप अक्सर आसपास के संदर्भ से किसी शब्द को पुनर्निर्माण कर सकते हैं, भले ही एक अक्षर गायब हो या गलत हो।
अतिरेक की गणना
अंग्रेजी अक्षर आवृत्ति (अनुमानित): 'e' लगभग समय का ~12.7% दिखाई देता है; 'z' लगभग ~0.07% दिखाई देता है। अंग्रेजी की वास्तविक एंट्रॉपी लगभग H ≈ 1.0 बिट/वर्ण है (शब्द-स्तरीय संदर्भ को ध्यान में रखते हुए)। 26-अक्षर वर्णमाला के लिए अधिकतम एंट्रॉपी: H_max = log₂(26) ≈ 4.70 बिट्स/वर्ण।
वृद्धि वक्र ज्यामिति के रूप में
कंपाइलर एल्गोरिदम आकार n (टोकन, लाइनें, या नोड्स) के कार्यक्रमों को संसाधित करते हैं। एल्गोरिदम की पसंद निर्धारित करती है कि प्रोग्राम आकार के साथ संकलन समय कैसे बढ़ता है।
सामान्य जटिलता वर्ग
| वर्ग | रनटाइम | उदाहरण | |---|---|---| | O(n) | रैखिक | लेक्सिकल स्कैनिंग | | O(n log n) | अर्ध-रैखिक | इष्टतम सॉर्टिंग | | O(n²) | द्विघात | भोली डुप्लिकेट पहचान | | O(n³) | घन | मैट्रिक्स गुणा, CYK पार्सिंग | | O(2ⁿ) | घातांकीय | भोली प्रमेय प्रमाण |
ज्यामितीय चित्र: रनटाइम बनाम n की साजिश करें। O(n) एक पंक्ति है। O(n²) एक परवलय है। O(2ⁿ) एक घातांकीय वक्र है जो n=0 के पास सपाट दिखता है और n=50 के पास लगभग ऊर्ध्वाधर होता है।
सामान्य संदर्भ-मुक्त व्याकरण पार्सिंग (CYK एल्गोरिदम) O(n³) में चलता है। अधिकांश व्यावहारिक प्रोग्रामिंग भाषाओं के लिए, व्याकरण LR(1)-पार्सेबल होने के लिए डिज़ाइन किया गया है, O(n) पार्सिंग की अनुमति देता है। ALGOL का व्याकरण FORTRAN की तुलना में अधिक जटिल था, धीमे कंपाइलर्स में योगदान दे रहा था — एक व्यावहारिक घर्षण जो 1958 में मायने रखता था जब संकलन घंटों लगते थे।
क्रॉसओवर बिंदु
भोली प्रतीक-तालिका लुकअप n आइडेंटिफायर के साथ एक प्रोग्राम के लिए कुल O(n²) ऑपरेशन का उपयोग करता है (प्रत्येक n लुकअप के लिए रैखिक स्कैन)। एक हैश-तालिका प्रतीक तालिका O(n) अपेक्षित कुल ऑपरेशन का उपयोग करती है।
मान लीजिए: O(n²) एल्गोरिदम 1958 के हार्डवेयर पर 10⁶ ऑपरेशन/सेकंड पर चलता है। O(n) एल्गोरिदम समान गति पर चलता है लेकिन 100n सेटअप ऑपरेशन की आवश्यकता होती है (हैश तालिका निर्माण)।