रूबी के लिए आरएसी - एलएएलआर (1) पार्सर जनरेटर का व्यावहारिक उपयोग

कुछ एंटरप्राइज क्लास सिस्टम के लिए एक फ्रेमवर्क बनाने के हिस्से के रूप में, मुझे यूएमएल मॉडल का उपयोग करके स्वचालित कोड पीढ़ी के लिए एक उपयोगिता बनाने का काम मिला। रूबी और निर्मित ईआरबी टेम्पलेट इंजन को छोड़कर, समस्या के त्वरित और प्रभावी समाधान के लिए अधिक उपयुक्त कुछ भी हाथ से नहीं निकला।

UML मॉडलिंग वातावरण से प्रोजेक्ट फ़ाइल SQLite3 प्रारूप डेटाबेस थी, हालाँकि, इस डेटाबेस में कुछ जानकारी को BLOB फ़ील्ड में क्रमबद्ध ऑब्जेक्ट्स के रूप में संग्रहीत किया गया था। क्रमांकन प्रारूप पाठात्मक था, लेकिन XML, YAML जैसे किसी भी प्रसिद्ध के साथ संगत नहीं था, दूरस्थ रूप से JSON जैसा था। प्रकृति में विद्यमान पार्सर का उपयोग करना असंभव था।

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

यह वही है जो मूल क्रमबद्ध वस्तुओं जैसा दिखता है।
यह कार्य ऐरे और हैश के आधार पर एक एकीकृत रूबी ढांचे के रूप में प्राप्त करना है।

data.txt

7ghoJdyGAqACCgeT:"User":Class { FromEndRelationships=( <vdHoJdyGAqACCgfe>, <9bToJdyGAqACCgfF> ); _masterViewId="7ghoJdyGAqACCgeS"; pmLastModified="1355667704781"; pmAuthor="author"; Child=( {UwZoJdyGAqACCgei:"name":Attribute { visibility=71; pmLastModified="1355667655234"; pmAuthor="author"; type=<_n2oJdyGAqACCgXh>; pmCreateDateTime="1355667628234"; _modelViews=NULL; _modelEditable=T; }}, {9lZoJdyGAqACCgel:"created":Attribute { visibility=71; type_string="date"; pmLastModified="1355667655234"; pmAuthor="author"; pmCreateDateTime="1355667630703"; _modelViews=NULL; _modelEditable=T; }}, {nLFoJdyGAqACCgeo:"active":Attribute { visibility=71; pmLastModified="1355667655234"; pmAuthor="author"; type=<_n2oJdyGAqACCgXY>; pmCreateDateTime="1355667639609"; _modelViews=NULL; _modelEditable=T; }} ); pmCreateDateTime="1355667607671"; _modelViews=( {4QhoJdyGAqACCgeU:"View":ModelView { container=<hguoJdyGAqACCgeL>; view="7ghoJdyGAqACCgeS"; }} ); _modelEditable=T; } 

यदि हम मूल प्रारूप का विश्लेषण करते हैं, तो हम निम्नलिखित तत्वों को अलग कर सकते हैं जो स्पष्ट रूप से इसके व्याकरण को परिभाषित करते हैं:

• वस्तु। यह प्रारूप आईडी: "नाम" में एक पंक्ति के साथ शुरू होता है : प्रकार , और फिर घुंघराले कोष्ठक में विशेषताओं का एक सेट होता है।
• किसी वस्तु का गुण। उन्हें कुंजी = मूल्य , प्लस अर्धविराम के रूप में इंगित किया जाता है।
• गुण मान। यह एक स्ट्रिंग, संख्या, संदर्भ, अन्य ऑब्जेक्ट या सूचीबद्ध मूल्यों में से किसी का एक संग्रह हो सकता है।
• प्रत्येक प्रकार के लिए विशिष्ट संकेतन में मान निर्दिष्ट हैं। स्ट्रिंग उद्धरण चिह्नों में संलग्न है। ऑब्जेक्ट ब्रेसिज़ में संलग्न है। मानों का एक संग्रह अल्पविराम द्वारा अलग किए गए कोष्ठक में संलग्न है।

ऐसा व्याकरण संदर्भ-मुक्त है, इसे बैकस-नौर रूप का उपयोग करके आसानी से वर्णित किया जा सकता है। और विश्लेषण के लिए, ऊपर की ओर शिफ्ट / कनवल्शन एल्गोरिथ्म का उपयोग करें। इस श्रेणी में सबसे आम एल्गोरिदम एलएएलआर (1) है , यह इस तरह के प्रसिद्ध "संकलक संकलक" में Yacc / GNU बाइसन के रूप में उपयोग किया जाता है। रूबी प्लेटफ़ॉर्म के लिए एक कार्यान्वयन भी है जो हमें रुचता है - यह आरसीसी है । हम इसे अपने पार्सर बनाने के लिए उपयोग करेंगे।

अपवर्ड शिफ्ट / कनविक्शन एल्गोरिथ्म

हमारे भविष्य के पार्सर में बेसलाइन बनाने और उसके तत्वों को बनाने के लिए, ऊपर की ओर शिफ्ट / कनवल्शन एल्गोरिथ्म के संचालन के सिद्धांत को एक सरलीकृत रूप में प्रस्तुत करना पर्याप्त है।

मान लें कि हमारे पास एक इनपुट कैरेक्टर स्ट्रीम है:

+ +

हमारे पास व्याकरण नियम भी हैं:

+
+

इनकमिंग स्ट्रीम को एक मार्कर द्वारा दो भागों में विभाजित किया गया है: विश्लेषण किया हुआ बाएं, और बिना उलझा हुआ दाईं ओर। मार्कर नेत्रहीन रूप से '|' प्रतीक द्वारा दर्शाया गया है। एल्गोरिथ्म क्रमिक रूप से स्ट्रीम से एक वर्ण को पढ़ता है, यह एक शिफ्ट ऑपरेशन (Shift) है, जो मार्कर को एक स्थिति को दाईं ओर ले जाता है। अगला चरण, एल्गोरिथम व्याकरण के नियमों के अनुसार, मार्कर के बचे हुए भाग के लिए कम करता है। और इसलिए अंत तक, जब तक कि पात्र बाहर नहीं निकल जाते और सभी दृढ़ संकल्प संतुष्ट हो जाते हैं।

s: | + +
r: | + +
s: + | +
r: + | +
s: + | +
r: | +
s: + |
r: + |
s: + |
r: |

Racc स्थापित करें

रूब आधारित पार्सरों के लिए रनटाइम वातावरण पहले से ही रूबी में शामिल है। संस्करण 1.8.x से शुरू, आरएसी का उपयोग करके बनाया गया कोई भी पार्सर अतिरिक्त इशारों के बिना काम करेगा। हालांकि, अपने स्वयं के पार्सर बनाने में सक्षम होने के लिए, आपको पार्सर जनरेटर युक्त आरएसी पैकेज स्थापित करना होगा। यह मणि के माध्यम से मानक रूप से किया जाता है:

# gem install racc

Racc पर एक पार्सर बनाना

आरसीसी पार्सर जनरेटर के लिए स्रोत एक फ़ाइल है (आमतौर पर विस्तार के साथ।) जिसमें रूबी पार्सर वर्ग की परिभाषा होती है और इसमें अतिरिक्त आरसीसी निर्देश शामिल होते हैं। निम्नलिखित तत्व पार्सर परिभाषा में मौजूद होने चाहिए:

• टर्मिनल व्याकरण वर्ण की परिभाषाएँ - टोकन
• व्याकरण और दृढ़ संकल्प परिभाषाएँ
• लेक्सिकल विश्लेषक

टोकन

तो, पहली बात यह है कि व्याकरण में तथाकथित टर्मिनल प्रतीकों को भेद करना है - प्राथमिक कण जिसमें से अधिक जटिल निर्माण होते हैं, और उन्हें नाम देते हैं। हमें ऐसा कुछ मिलता है:

• T_OBJECTID - ऑब्जेक्ट पहचानकर्ता
• T_IDENTIFIER - विशेषता पहचानकर्ता
• T_STRING - टेक्स्ट स्ट्रिंग
• T_NUMBER - संख्या
• T_BOOLEAN - बूलियन मान
• T_NULL - खाली मान
• T_REFERENCE - लिंक
• T_LBR, T_RBR, T_LPAR, T_RPAR, T_EQ, T_COMMA, T_SEMICOLON - विराम चिह्न: विभिन्न कोष्ठक, समान चिह्न, अल्पविराम, अर्धविराम

Parser वर्ग परिभाषा में, टोकन के उपयोग से मान्य टोकन परिभाषित किए गए हैं।

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

अगला कदम एक शाब्दिक विश्लेषक बनाना है। इसके कार्यों में आने वाली धारा को स्कैन करना और इसमें टोकन की पहचान करना शामिल है। लेक्सिकल विश्लेषक को आने वाली धारा को लगातार टोकन के एक सेट में बदलना चाहिए। आरईसी, जब शिफ्ट ऑपरेशन करते हैं, तो आने वाले स्ट्रीम से एक नया टोकन प्राप्त करना चाहिए, जो कि लेक्सिकल एनालाइज़र द्वारा परिवर्तित किया गया है। वह पार्सर क्लास पर अगली_टोकन पद्धति को कॉल करके ऐसा करता है, जिसे टोकन के नाम और मूल्य वाली संरचना को वापस करना चाहिए:

 [:TOKEN_NAME, 'Token value'] 

स्ट्रीम के अंत के लिए एक लेबल के रूप में, मान है:

 [false, false] 

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

व्याकरण के नियम

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

 attribute: T_IDENTIFIER T_EQ value T_SEMICOLON { result = { val[0] => val[2] } }; 

नियम के बाद घुंघराले कोष्ठक में, एक रूबी अभिव्यक्ति निर्दिष्ट की जाती है, जिसे इस मामले में, विशेषता के रूप में, घोषित नॉनटर्मिनल से पहले पात्रों के दिए गए अनुक्रम को समझना चाहिए। वैरिएबल वैल और रिजल्ट आरसीई द्वारा पूर्वनिर्धारित हैं । वैल सरणी में बंधनेवाला अनुक्रम के मूल्य शामिल हैं, इस मामले में वैल [0] में वैल्यू T_IDENTIFIER, वैल [2] वैल्यू वैल्यू शामिल है। परिणाम चर को परिणाम चर में रखा गया है।

पार्सर शुरू करने के लिए, आपको do_parse विधि को कॉल करना होगा। इस पद्धति को आरएसी :: पार्सर वर्ग में परिभाषित किया गया है, जिससे हमारा पार्सर वर्ग विरासत में मिलेगा।

नीचे पार्सर परिभाषा के लिए पूर्ण स्रोत कोड है।

parser.y

 class Parser token T_OBJECTID T_STRING T_REFERENCE T_IDENTIFIER T_NUMBER T_BOOLEAN T_NULL token T_LBR T_RBR T_LPAR T_RPAR T_EQ T_COMMA T_SEMICOLON start input rule input: object { @result = val[0] }; object: T_OBJECTID T_LBR attributes T_RBR { oid = val[0].split(':'); result = { :id => dequote(oid[0]), :name => convertNULL(dequote(oid[1])), :type => dequote(oid[2]) }.merge(val[2]) }; attributes: attribute { result = val[0] } | attributes attribute { result = val[0].merge(val[1]) } ; attribute: T_IDENTIFIER T_EQ value T_SEMICOLON { result = { val[0] => val[2] } }; values: value { result = [val[0]] } | values T_COMMA value { val[0] << val[2] } ; value: T_STRING { result = dequote(val[0]) } | T_REFERENCE { result = dequote(val[0]) } | T_NUMBER { result = val[0].to_i } | T_BOOLEAN { result = val[0] == 'T' } | T_NULL { result = nil } | T_LBR object T_RBR { result = val[1] } | T_LPAR values T_RPAR { result = val[1] } ; ---- header ---- require 'strscan' ---- inner ---- def tokenize(text) tokens = [] s = StringScanner.new(text) until s.eos? case when s.skip(/\s+/) next when s.scan(/\A[\w\.]+:\"*\w*\"*:\w+/) tokens << [:T_OBJECTID, s[0]] next when s.scan(/\A\{/) tokens << [:T_LBR, nil] next when s.scan(/\A\}/) tokens << [:T_RBR, nil] next when s.scan(/\A\(/) tokens << [:T_LPAR, nil] next when s.scan(/\A\)/) tokens << [:T_RPAR, nil] next when s.scan(/\A\=/) tokens << [:T_EQ, nil] next when s.scan(/\A\,/) tokens << [:T_COMMA, nil] next when s.scan(/\A\;/) tokens << [:T_SEMICOLON, nil] next when s.scan(/\w+/) if (s[0].match(/[0-9]+/)) tokens << [:T_NUMBER, s[0]] elsif (s[0].match(/\A[TF]{1}\Z/)) tokens << [:T_BOOLEAN, s[0]] elsif (s[0].match(/\ANULL\Z/)) tokens << [:T_NULL, nil] else tokens << [:T_IDENTIFIER, s[0]] end next when s.scan(/(["]).*?(?<!\\)\1/m) tokens << [:T_STRING, s[0]] next when s.scan(/\<.*?\>/) tokens << [:T_REFERENCE, s[0]] next else s.getch next end end tokens << [false, false] return tokens end def parse(text) @tokens = tokenize(text) do_parse return @result end def next_token @tokens.shift end def dequote(text) text.gsub(/\A["<]|[">]\Z/, '').strip end def convertNULL(text) text.upcase == "NULL" ? nil : text end 

.Y फ़ाइल अभी तक एक पार्सर नहीं है। रैसर उपयोगिता का उपयोग करके पार्सर को उत्पन्न करने की आवश्यकता है, और इसे .y में पार्सर परिभाषा को बदलने के बाद हर बार किया जाना चाहिए:

# racc parser.y -o parser.rb

पार्सर वर्ग के साथ परिणामी फ़ाइल को सामान्य तरीके से जोड़ा और उपयोग किया जा सकता है:

main.rb

 require 'pp' require './parser.rb' parser = Parser.new obj = parser.parse(File.read("data.txt")) puts obj.pretty_inspect 

यह पार्सर का परिणाम होगा - व्यापक रूबी संरचना:

उत्पादन

 { :id => "7ghoJdyGAqACCgeT", :name => "User", :type => "Class", "FromEndRelationships" => ["vdHoJdyGAqACCgfe", "9bToJdyGAqACCgfF"], "_masterViewId" => "7ghoJdyGAqACCgeS", "pmLastModified" => "1355667704781", "pmAuthor" => "author", "Child" => [ { :id => "UwZoJdyGAqACCgei", :name => "name", :type => "Attribute", "visibility" => 71, "pmLastModified" => "1355667655234", "pmAuthor" => "author", "type" => "_n2oJdyGAqACCgXh", "pmCreateDateTime" => "1355667628234", "_modelViews" => nil, "_modelEditable" => true }, { :id => "9lZoJdyGAqACCgel", :name => "created", :type => "Attribute", "visibility" => 71, "type_string" => "date", "pmLastModified" => "1355667655234", "pmAuthor" => "author", "pmCreateDateTime" => "1355667630703", "_modelViews" => nil, "_modelEditable" => true }, { :id => "nLFoJdyGAqACCgeo", :name => "active", :type => "Attribute", "visibility" => 71, "pmLastModified" => "1355667655234", "pmAuthor" => "author", "type" => "_n2oJdyGAqACCgXY", "pmCreateDateTime" => "1355667639609", "_modelViews" => nil, "_modelEditable" => true } ], "pmCreateDateTime" => "1355667607671", "_modelViews" => [ { :id => "4QhoJdyGAqACCgeU", :name => "View", :type => "ModelView", "container" => "hguoJdyGAqACCgeL", "view" => "7ghoJdyGAqACCgeS" } ], "_modelEditable" => true }