👎🏻 👩🏾‍⚖️ 🤘🏼 लेक्सिकल विश्लेषण के बारे में थोड़ा 🍀 🈲 👏🏿

एक बार, जब आकाश नीला था, घास हरियाली थी और डायनासोर पृथ्वी पर घूमते थे ... नहीं, डायनासोर के बारे में भूल जाओ। खैर, सामान्य तौर पर, एक बार मानक वेब-प्रोग्रामिंग से ध्यान हटाने और कुछ अधिक पागल करने के लिए विचार आया। निश्चित रूप से, कुछ भी हो सकता है, लेकिन पसंद अपनी व्याख्या लिखने वाले पर गिर गई। मैं क्या कह सकता हूं ... कभी भी अपनी प्रोग्रामिंग लैंग्वेज न लिखें । लेकिन मुझे इस सब से कुछ अनुभव हुआ, इसलिए मैंने इसे साझा करने का फैसला किया। चलो बहुत नींव के साथ शुरू करते हैं - लेसर।

प्रस्तावना

इससे पहले कि आप समझने लगें कि "लेक्सर" किस प्रकार का जानवर है, यह पता लगाने के लायक है कि हांप किससे बना है।

आधुनिक दुनिया में, प्रत्येक संकलक / दुभाषिया / ट्रांसपिलर / कुछ-वहाँ-और-जैसे (चलो, मैं बस इसे आगे "संकलक" कहूँगा, प्रकारों के बीच अंतर के बिना) दो टुकड़ों में विभाजित किया गया है। स्मार्ट चाचाओं की शब्दावली में, ऐसे टुकड़ों को "फ्रंटेंड" और "बैकएंड" कहा जाता है। नहीं, यह बिल्कुल नहीं है कि वेब के साथ काम करते समय, हमें कॉल करने के लिए क्या उपयोग किया जाता है और सामने वाले को HTML के साथ JS में नहीं लिखा जाता है। हालांकि ... ठीक है।

रास्ते में सिंटैक्स (और कभी-कभी शब्दार्थ) की जाँच करते हुए पहले सीमांत का कार्य पाठ को लेना और इसे एएसटी (सार सिंटैक्स ट्री) में बदलना है। दूसरा बैकएंड का कार्य यह सब काम करना है। यदि कोड दुभाषिया के अंदर इकट्ठा होता है, तो एएसटी वर्चुअल प्रोसेसर (वर्चुअल मशीन) के लिए निर्देशों का एक सेट बनाता है, यदि कंपाइलर, तो असली प्रोसेसर के लिए निर्देशों का सेट। जीवन में, सब कुछ काफी अधिक जटिल है और काफी हद तक इसे लागू नहीं किया जा सकता है। उदाहरण के लिए, जीसीसी संकलक के मामले में, सब कुछ मिलाया जाता है, लेकिन क्लैंग पहले से अधिक विहित है, एलएलवीएम संकलक के लिए "बैकएंड" का एक विशिष्ट प्रतिनिधि है।

अब आइए जानते हैं कि फ्रंटेंड नामक एक टुकड़ा।

लेक्सिकल विश्लेषण

लेक्सर और लेक्सिकल विश्लेषण के चरण का कार्य प्रवेश द्वार पर कई, कई अक्षरों को प्राप्त करना और उन्हें कुछ श्रेणियों में समूहित करना है - "टोकन"। इसलिए, लेक्सिकल विश्लेषण को "टोकेनाइजेशन" भी कहा जाता है। यह टेक्स्ट प्रोसेसिंग का पहला चरण है जो हर मौजूदा कंपाइलर का उत्पादन करता है।

कुछ इस तरह:

$tokens = ['class', '\w+', '}', '{']; var_dump(lex('class Example {}', $tokens)); // array(4) { // [0] => string(5) "class" // [1] => string(7) "Example" // [2] => string(1) "{" // [3] => string(1) "}" // }

वैसे, यहां हमने पहले से ही जीवन को आसान बनाने के लिए उपकरणों का एक गुच्छा लिखा है। वही प्रीग फ़ंक्शंस जो हमने पार्सिंग टेक्स्ट के लिए उपयोग किए थे, इस कार्य के लिए काफी सक्षम हैं। हालांकि, इस मामले के लिए अधिक सुविधाजनक उपकरण हैं:

फलेक्स , निकिता पोपोव द्वारा लिखित।
होआ एक टूलकिट है जिसमें लेक्सर + पार्सर + ग्रामर शामिल है।
पोर्ट यैक , एंथोनी फेरारा द्वारा लिखित, जो एक जटिल टूलकिट भी है, और जिस पर प्रसिद्ध पोपोव पीएचपी पार्सर लिखा है, जो कोड विश्लेषण का उपयोग करने वाले टूल में लागू है।
Railt Lexer PHP 7.1+ के लिए मेरा कार्यान्वयन
पार्ले PHP के लिए एक विस्तार है जो पीसीआरई भावों का सीमित सेट (कोई लुक नहीं और कुछ अन्य सिंटैक्स निर्माण) की अनुमति देता है।
और अंत में, मानक php फ़ंक्शन token_get_all , जो सीधे PHP के शाब्दिक विश्लेषण के लिए अभिप्रेत है।

खैर, यह स्पष्ट है कि बहुत सारे गिज़्म हैं जो पाठ को टोकन से विभाजित कर सकते हैं, शायद मैं भी कुछ भूल गया हूं, जैसे कि डॉक्ट्रिन लेक्सर। लेकिन आगे क्या है?

लेकर्स के प्रकार

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

मल्टीस्टेट लेक्सर का कार्य पिछले राज्य के आधार पर विभिन्न टोकन प्रदर्शित करना है। ठीक है, उदाहरण के लिए, PHP में, ऐसे "संक्रमणकालीन" राज्य <? Php +?> टैग, लाइनों, टिप्पणियों, और HEREDOC / NowDOC निर्माणों का उपयोग करके बनाए जाते हैं।

4 टोकन के साथ पिछले उदाहरण को याद रखें? आइए इसे थोड़ा समझें कि ये अवस्थाएँ क्या हैं:

 class Example { // class Example {} }

इस मामले में, अगर हमारे पास पीसीआर की व्यापक क्षमताओं के बिना सबसे सरल लेसर है, तो हमें टोकन के निम्नलिखित सेट मिलते हैं:

 var_dump(lex(...)); // array(9) { // [0] => string(5) "class" // [1] => string(7) "Example" // [2] => string(1) "{" // [3] => string(2) "//" // [4] => string(5) "class" // [5] => string(7) "Example" // [6] => string(1) "{" // [7] => string(1) "}" // [8] => string(1) "}" //}

जैसा कि आप देख सकते हैं, हमें 3-5 पर तत्वों पर पूरी तरह से प्रतिबंध जंब मिला है: टिप्पणी को अप्रत्याशित रूप से लिया गया था और टोकन में विभाजित किया गया था, हालांकि इसे एक पूरे टुकड़े के रूप में माना जाना चाहिए था।

बेशक, पीसीआरई कार्यात्मक के साथ, इस तरह के एक टोकन को एक नियमित नियमितता की मदद से फाड़ा जा सकता है " // [^ \ n] * \ n ", लेकिन अगर यह नहीं है? या हम इसे अपने हाथों से गश करना चाहते हैं? संक्षेप में, मल्टीस्टेट लेक्सर के मामले में - हम कह सकते हैं कि सभी टोकन समूह नंबर 1 में होने चाहिए, जैसे ही " // " टोकन पाया जाता है, तो समूह नंबर 2 में संक्रमण होना चाहिए। और दूसरे समूह के अंदर, रिवर्स संक्रमण, अगर टोकन " \ n " पाया जाता है, पहले समूह में वापस चला जाता है।

कुछ इस तरह:

 $tokens = [ 'group-1' => [ 'class', '\w+', '{', '}', '//' => 'group-2' //      2 ], 'group-2' => [ "\n" => 'group-1', //    1    '.*' ] ];

मुझे लगता है कि अब यह स्पष्ट हो गया है कि कुछ HEREDOC को कैसे पार्स किया जाता है, क्योंकि PCRE की सारी शक्ति के साथ भी, इस मामले के लिए नियमित रूप से लिखना बेहद समस्याग्रस्त है, यह देखते हुए कि यह HEREDOC सिंटैक्स वैरिएबल इंटरपोलेशन का समर्थन करता है। बिल्ट-इन token_get_all फ़ंक्शन (नोट> 12 टोकन) के साथ कुछ इस तरह पार्स करने का प्रयास करें:

 <?php $example = 42; $a = <<<EOL Your answer is $example !!! EOL; var_dump(token_get_all(file_get_contents(__FILE__)));

खैर, ऐसा लगता है कि हम अभ्यास शुरू करने के लिए तैयार हैं।

अभ्यास

आइए याद रखें कि ऐसी चीजों के लिए PHP में हमारे पास क्या है? खैर, बेशक, preg_match! ठीक है, नीचे आओ। Preg_match- आधारित एल्गोरिथ्म होआ में और फेल्सी के इस कार्यान्वयन में लागू किया गया है । इसका कार्य काफी सरल है:

हमारे पास स्रोत पाठ और नियमित की एक सरणी है।
हम तब तक मिलते हैं जब तक कि कुछ उपयुक्त नहीं मिल जाता।
जैसे ही आप एक टुकड़ा पाते हैं, इसे पाठ से बाहर काटें और आगे मेल करें।

कोड रूप में, यह कुछ इस तरह दिखाई देगा:

कोड शीट

 <?php class SimpleLexer { /** * @var array<string> */ private $tokens = []; /** * @param array<string> $tokens */ public function __construct(array $tokens) { foreach ($tokens as $name => $definition) { $this->tokens[$name] = \sprintf('/\G%s/isSum', $definition); } } /** * @param string $sources * @return iterable&\Traversable<string> * @throws RuntimeException */ public function lex(string $sources): iterable { [$offset, $length] = [0, \strlen($sources)]; while ($offset < $length) { [$name, $token] = $this->next($sources, $offset); yield $name => $token; $offset += \strlen($token); } } /** * @param string $sources * @param int $offset * @return array<string,string> * @throws RuntimeException */ private function next(string $sources, int $offset): array { foreach ($this->tokens as $name => $pcre) { \preg_match($pcre, $sources, $matches, 0, $offset); $token = \reset($matches); if (\count($matches) && \strpos($sources, $token, $offset) === $offset) { return [$name, $token]; } } throw new \RuntimeException('Unrecognized token at offset ' . $offset); } }

कोड शीट का उपयोग करना

 $lexer = new SimpleLexer([ 'T_CLASS' => 'class', 'T_CONST' => '\w+', 'T_BRACE_OPEN' => '{', 'T_BRACE_CLOSE' => '}', 'T_WHITESPACE' => '\s+', ]); echo \sprintf('| %-10s | %-20s |', 'VALUE', 'NAME') . "\n"; foreach ($lexer->lex('class Example {}') as $name => $token) { echo \sprintf('| %-10s | %-20s |', '"' . \trim($token, "\n") . '"', $name) . "\n"; }

यह दृष्टिकोण काफी तुच्छ है और कीबोर्ड के एक जोड़े को लेक्सर को अगले () विधि के क्षेत्र में संशोधित करने की अनुमति देता है, जो राज्यों के बीच एक संक्रमण को जोड़ता है और इस बाधा को एक आदिम बहुस्तरीय लेक्सर में बदल देता है। $ इस-> टोकन क्षेत्र में, बस $ कुछ इस तरह जोड़ें-> टोकन [$ यह-> राज्य] ।

हालांकि, प्राइमिटिविज्म के अलावा, एक और खामी है, घातक नहीं है क्योंकि यह बाहर निकल सकता है, लेकिन फिर भी ... इस तरह का कार्यान्वयन अविश्वसनीय रूप से धीमा है। I7 7600k पर, जिसके मालिक मैं संयोग से हुआ था - एक समान एल्गोरिथ्म लगभग 400 टोकन प्रति सेकंड की प्रक्रिया करता है, और उनकी विविधताओं में वृद्धि के साथ (यानी, परिभाषाएँ जो हम निर्माता के पास गए थे) - यह रूस में बदलते राष्ट्रपतियों की गति को धीमा कर सकता है ... अहम माफ कर दीजिए। मैं निश्चित रूप से कहना चाहता था कि यह बहुत धीमी गति से काम करेगा।

ठीक है, हम क्या कर सकते हैं? शुरुआत के लिए, आप समझ सकते हैं कि क्या गलत हो रहा है। तथ्य यह है कि हर बार जब हम भाषा के विल्स के अंदर प्रीग_मैच कहते हैं, तो उसके JIT नामक एक कंपाइलर PCRE उगता है (और PHP 7.3 के साथ, PCRE2 पहले से ही है)। हर बार वह नियमित रूप से खुद को तैयार करता है और उनके लिए एक पार्सर इकट्ठा करता है, जिसके साथ हम टोकन बनाने के लिए पाठ को पार्स करते हैं। यह थोड़ा अजीब और तनातनी लगता है। लेकिन संक्षेप में, प्रत्येक टोकन को 1 से एन नियमित रूप से संकलन की आवश्यकता होती है, जहां एन इन टोकन की परिभाषाओं की संख्या है। इसी समय, यह ध्यान देने योग्य है कि यहां तक कि कंस्ट्रक्टर में " \ " जी का उपयोग करके " S " ध्वज और अनुकूलन भी लागू होता है, जहां टोकन के लिए नियमित अभिव्यक्ति उत्पन्न होती हैं, मदद नहीं करते हैं।

इस स्थिति से केवल एक ही रास्ता है - आपको इस सभी पाठ को एक पास में पार्स करने की आवश्यकता है, अर्थात्। केवल एक preg_match फ़ंक्शन निष्पादित करके। यह दो समस्याओं को हल करने के लिए बनी हुई है:

यह कैसे इंगित करें कि नियमित अभिव्यक्ति N1 का परिणाम टोकन N2 से मेल खाता है? यानी कैसे इंगित करने के लिए कि " \ w + ", उदाहरण के लिए, T_CONST है ।
परिणामस्वरूप टोकन के अनुक्रम का निर्धारण कैसे करें। जैसा कि आप जानते हैं, preg_match या preg_match_all के परिणाम में सब कुछ मिश्रित होगा। और यहां तक कि चौथे तर्क के रूप में पारित झंडे की मदद से, स्थिति नहीं बदलेगी।

यहां आप थोडा रुक कर सोच सकते हैं। खैर या नहीं।

पहली समस्या के समाधान को पीसीआरई समूहों का नाम दिया गया है , जिन्हें "उपमाक्स" भी कहा जाता है। नियमों का उपयोग करना: " <! <T_WHITESPACE> \ s + | <T_WORD> \ w + | ...) " आप सभी टोकन को उनके नाम के साथ तुलना करके प्राप्त कर सकते हैं। मैच के परिणामस्वरूप, एक सहयोगी सरणी बनाई जाएगी, जिसमें " [TOKEN_NAME => TOKEN_VALUE] " जोड़े शामिल होंगे।

दूसरा थोड़ा अधिक जटिल है। लेकिन यहां आप एक सामरिक चाल लागू कर सकते हैं और preg_replace_callback फ़ंक्शन का उपयोग कर सकते हैं। इसकी ख़ासियत यह है कि दूसरे तर्क के रूप में पारित किया गया अनाम पहले से आखिरी तक प्रत्येक टोकन के लिए सख्ती से क्रमिक रूप से कहा जाएगा।

आदेश में कमी नहीं है - कार्यान्वयन इस प्रकार है:

कोड का एक और फ्लैप

 class PregReplaceLexer { /** * @var array<string> */ private $tokens = []; /** * @param array<string> $tokens */ public function __construct(array $tokens) { foreach ($tokens as $name => $definition) { $this->tokens[] = \sprintf('(?<%s>%s)', $name, $definition); } } /** * @param string $sources * @return iterable&\Traversable<string,string> */ public function lex(string $sources): iterable { $result = []; \preg_replace_callback($this->compilePcre(), function (array $matches) use (&$result) { foreach (\array_reverse($matches) as $name => $value) { if (\is_string($name) && $value !== '') { $result[] = [$name, $value]; break; } } }, $sources); foreach ($result as [$name, $value]) { yield $name => $value; } } /** * @return string */ private function compilePcre(): string { return \sprintf('/\G(?:%s)/isSum', \implode('|', $this->tokens)); } }

और इसका उपयोग पिछले संस्करण से अलग नहीं है। इसी समय, काम की गति 400 से 57,000 टोकन प्रति सेकंड तक बढ़ जाती है। यह वह एल्गोरिथ्म है जिसे मैंने अपने कार्यान्वयन में लागू किया था , होआ स्रोत कोड का पुनर्लेखन। वैसे, यदि आप पार्ले का उपयोग करते हैं, तो आप प्रति सेकंड 600,000 टोकन तक निचोड़ सकते हैं। और समग्र तस्वीर कुछ इस तरह दिखती है (PHP 7.1 में XDebug चालू होने के साथ, इसलिए संख्या कम है, लेकिन अनुपात लगभग प्रतिनिधित्व किया जा सकता है)।

येलो पारले का मूल विस्तार है।
ब्लू - पूर्व इकट्ठे नियमित के साथ preg_replace_callback के माध्यम से कार्यान्वयन।
लाल - सभी समान, लेकिन कॉल के दौरान उत्पन्न नियमितता के साथ preg_replace_callback के लिए ।
ग्रीन - preg_match के माध्यम से कार्यान्वयन।

क्यों?

खैर, यह सब, निश्चित रूप से, अद्भुत है, लेकिन अधीर लोगों को सवाल पूछने के लिए उत्सुक हैं: "इसे किसकी ज़रूरत है?" PHP की अमूर्त दुनिया में, जहां "अंजीर-अंजीर और साइट-तैयार" का सिद्धांत हावी है - ऐसे पुस्तकालयों की आवश्यकता नहीं है, हम ईमानदार होंगे। लेकिन अगर हम एक पूरे के रूप में पारिस्थितिकी तंत्र के बारे में बात करते हैं, तो हम सिम्फनी / यामल या डॉक्ट्रिन जैसे कुख्यात पुस्तकालयों को याद कर सकते हैं। सिम्फनी में एनोटेशन PHP के भीतर एक ही उप-भाषा है, जिसमें अलग-अलग लेक्सिकल और वाक्यविन्यास पार्सिंग की आवश्यकता होती है। इसके अलावा, पीएचपी में लिखे जाने वाले कॉफ़ीस्क्रिप्ट, लेस, और एससीएस / एसएएस ट्रांसपैरर्स भी थोड़ा कम प्रसिद्ध हैं। खैर, या या और इसके आधार पर प्रीप्रोसेस । मैं कोड विश्लेषण उपकरणों जैसे phpmd या phpcs का भी उल्लेख नहीं करूंगा। और phpDocumentnor या सामी जैसे प्रलेखन जनरेटर बहुत तुच्छ हैं। इनमें से प्रत्येक प्रोजेक्ट एक डिग्री या दूसरे में पार्सिंग टेक्स्ट / कोड के पहले चरण में लेक्सिकल विश्लेषण का उपयोग करता है।

यह परियोजनाओं की पूरी सूची नहीं है और शायद मुझे उम्मीद है कि मेरी कहानी आपको कुछ नया खोजने और इसे फिर से भरने में मदद करेगी।

अंतभाषण

आगे देखते हैं, अगर कोई भी पर्सर और कम्पाइलर के विषय में रुचि रखता है, तो इस विषय पर कुछ दिलचस्प रिपोर्टें हैं, विशेष रूप से जेटब्रेन के लोगों से:

वीडियो

फिर भी, निश्चित रूप से, आंद्रेई ब्रेसलेव ( अब्रेसलेव ) के अधिकांश प्रदर्शन, जो YouTube की विशालता पर पाए जा सकते हैं - मैं आपको देखने की सलाह देता हूं।

खैर, कल्पना के प्रशंसकों के लिए एक ऐसा संसाधन है जो व्यक्तिगत रूप से मेरे लिए बेहद उपयोगी था।

पोस्ट पोस्ट स्क्रिप्टम। यदि आप कहीं इस महाकाव्य की विशालता में सील हैं, तो आप लेखक को किसी भी रूप में आपके लिए सुविधाजनक रूप से सूचित कर सकते हैं।

एक बोनस के रूप में, मैं एक साधारण PHP lexer का उदाहरण देना चाहूंगा, ऐसा लगता है कि यह अब इतना डरावना नहीं है, और अब यह भी स्पष्ट है कि यह क्या करता है, है ना? यद्यपि मैं जिसे धोखा दे रहा हूं, वह आंखों को नियमित रूप से खून बह रहा है। =)

धन्यवाद!