पेशेवर नियमित अभिव्यक्ति शाब्दिक विश्लेषण

पाठ पार्सिंग हमेशा शाब्दिक विश्लेषण या टोकन के साथ शुरू होता है। नियमित अभिव्यक्ति का उपयोग करके लगभग किसी भी भाषा के लिए इस समस्या को हल करने का एक आसान तरीका है। अच्छा पुराने regexp का एक और उपयोग।

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

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

name = 'John' OR name = 'Michael' OR name = 'Bob' 

हम ऐसे अनुरोधों को प्रतिस्थापित करना चाहते थे

 name IN ('John', 'Michael', 'Bob') 

नियमित अभिव्यक्तियाँ अब सामना नहीं कर सकती हैं, लेकिन मैं AntLR का उपयोग करके एक पूर्ण SQL पार्सर बनाना नहीं चाहता था। बिना किसी विशेष टूल के पार्सिंग बनाने के लिए अनुरोध पाठ को टोकन में तोड़ना और सरल कोड का उपयोग करना संभव होगा।

नियमित अभिव्यक्ति की बुनियादी कार्यक्षमता का उपयोग करके इस समस्या को हल किया जा सकता है। आइए SQL क्वेरी को टोकन में विभाजित करने का प्रयास करें। हम एसक्यूएल के सरलीकृत संस्करण को देखेंगे ताकि विवरण के साथ पाठ को अधिभार न डालें। पूर्ण-स्तरीय SQL lexer बनाने के लिए, आपको थोड़े अधिक जटिल नियमित अभिव्यक्ति लिखने होंगे।

यहाँ मूल SQL भाषा टोकन के लिए भावों का एक समूह है:

 1. keyword : \b(?:select|from|where|group|by|order|or|and|not|exists|having|join|left|right|inner)\b 2. id : [A-Za-z][A-Za-z0-9]* 3. real_number : [0-9]+\.[0-9]* 4. number : [0-9]+ 5. string : '[^']*' 6. space : \s+ 7. comment : \-\-[^\n\r]* 8. operation : [+\-\*/.=\(\)] 

मैं कीवर्ड के लिए नियमित अभिव्यक्ति पर ध्यान देना चाहता हूं

 keyword : \b(?:select|from|where|group|by|order|or|and|not|exists|having|join|left|right|inner)\b 

इसकी दो विशेषताएं हैं।

1. उदाहरण के लिए, अंत में और अंत में \ b ऑपरेटर का उपयोग किया जाता है, ताकि शब्द संगठन से या उपसर्ग को काट न सकें, जो एक कीवर्ड है और जो कुछ regex इंजन \ b ऑपरेटर का उपयोग किए बिना एक अलग टोकन में अलग हो जाएगा।
2. सभी शब्दों को गैर-कैप्चरिंग ब्रैकेट द्वारा वर्गीकृत किया गया है (! :) जो मैच पर कब्जा नहीं करते हैं। इसका उपयोग भविष्य में किया जाएगा ताकि सामान्य अभिव्यक्ति के भीतर आंशिक नियमित अभिव्यक्तियों के अनुक्रमण का उल्लंघन न हो।

अब आप ग्रुपिंग और ऑपरेटर का उपयोग करके इन सभी भावों को एक ही में जोड़ सकते हैं |

 (\b(?:select|from|where|group|by|order|or|and|not|exists|having|join|left|right|inner)\b)|([A-Za-z][A-Za-z0-9]*)|([0-9]+\.[0-9]*)|([0-9]+)|('[^']*')|(\s+)|(\-\-[^\n\r]*)|([+\-\*/.=\(\)]) 

अब आप इस एक्सप्रेशन को SQL एक्सप्रेशन में लागू करने की कोशिश कर सकते हैं, उदाहरण के लिए

 SELECT count(id) -- count of 'Johns' FROM person WHERE name = 'John' 

यहाँ रेगेक्स परीक्षक पर परिणाम है । लिंक पर क्लिक करके आप अभिव्यक्ति और विश्लेषण के परिणाम के साथ खेल सकते हैं। यह देखा जा सकता है कि, उदाहरण के लिए, SELECT तुरंत 1-समूह से मेल खाता है, जो कीवर्ड प्रकार से मेल खाता है।

आप देख सकते हैं कि अनुरोध का पूरा पाठ सबस्ट्रिंग में विभाजित हो गया है और प्रत्येक एक निश्चित समूह से मेल खाता है। समूह संख्या के अनुसार, आप इसे टोकन (टोकन) के प्रकार के साथ सहसंबद्ध कर सकते हैं।

दिए गए एल्गोरिदम को किसी भी प्रोग्रामिंग भाषा में प्रोग्राम में बनाना जो नियमित अभिव्यक्ति का समर्थन करता है, मुश्किल नहीं है। यहां एक छोटा वर्ग है जो जावा में इसे लागू करता है।

 package org.example; import java.util.ArrayList; import java.util.Enumeration; import java.util.List; import java.util.regex.Matcher; import java.util.regex.Pattern; import java.util.stream.Collectors; /** *    . *   ,         . */ public class RegexTokenizer implements Enumeration<Token> { // ,      private final String content; //         private final ITokenType[] tokenTypes; private final Matcher matcher; //    private int currentPosition = 0; /** * @param content    * @param tokenTypes         */ public RegexTokenizer(String content, ITokenType[] tokenTypes) { this.content = content; this.tokenTypes = tokenTypes; //       List<String> regexList = new ArrayList<>(); for (int i = 0; i < tokenTypes.length; i++) { ITokenType tokenType = tokenTypes[i]; regexList.add("(?<g" + i + ">" + tokenType.getRegex() + ")"); } String regex = regexList.stream().collect(Collectors.joining("|")); Pattern pattern = Pattern.compile(regex, Pattern.CASE_INSENSITIVE); //    matcher = pattern.matcher(content); matcher.find(); } @Override public boolean hasMoreElements() { return currentPosition < content.length(); } @Override public Token nextElement() { boolean found = currentPosition > matcher.start() ? matcher.find() : true; int start = found ? matcher.start() : content.length(); int end = found ? matcher.end() : content.length(); if(found && currentPosition == start) { currentPosition = end; //  -   for (int i = 0; i < tokenTypes.length; i++) { String si = "g" + i; if (matcher.start(si) == start && matcher.end(si) == end) { return createToken(content, tokenTypes[i], start, end); } } } throw new IllegalStateException("      " + currentPosition); } /** *  -  ,    ,     , *            (, ) * @param content     * @param tokenType   * @param start      * @param end      * @return  - */ protected Token createToken(String content, ITokenType tokenType, int start, int end) { return new Token(content.substring(start, end), tokenType, start); } /** *     SQL */ public enum SQLTokenType implements ITokenType { KEYWORD("\\b(?:select|from|where|group|by|order|or|and|not|exists|having|join|left|right|inner)\\b"), ID("[A-Za-z][A-Za-z0-9]*"), REAL_NUMBER("[0-9]+\\.[0-9]*"), NUMBER("[0-9]+"), STRING("'[^']*'"), SPACE("\\s+"), COMMENT("\\-\\-[^\\n\\r]*"), OPERATION("[+\\-\\*/.=\\(\\)]"); private final String regex; SQLTokenType(String regex) { this.regex = regex; } @Override public String getRegex() { return regex; } } public static void main(String[] args) { String s = "select count(id) -- count of 'Johns' \n" + "FROM person\n" + "where name = 'John'"; RegexTokenizer tokenizer = new RegexTokenizer(s, SQLTokenType.values()); while(tokenizer.hasMoreElements()) { Token token = tokenizer.nextElement(); System.out.println(token.getText() + " : " + token.getType()); } } } /** * -  () */ public class Token { //   private final String text; //   private final ITokenType type; //      private final int start; public Token(String text, ITokenType type, int start) { this.text = text; this.type = type; this.start = start; } public String getText() { return text; } public ITokenType getType() { return type; } public int getStart() { return start; } } /** *     */ public interface ITokenType { /** *       */ String getRegex(); } 

इस वर्ग में, एल्गोरिथ्म को नामित समूहों का उपयोग करके कार्यान्वित किया जाता है, जो सभी इंजनों में मौजूद नहीं हैं। यह सुविधा आपको अनुक्रमणिका के आधार पर समूहों का उपयोग करने की अनुमति देती है, लेकिन नाम से, जो अनुक्रमणिका तक पहुँचने से थोड़ा अधिक सुविधाजनक है।

मेरे I7 2.3GHz पर, यह वर्ग 5-20 एमबी प्रति सेकंड (अभिव्यक्तियों की जटिलता के आधार पर) की विश्लेषण गति प्रदर्शित करता है। एल्गोरिथ्म को एक साथ कई फ़ाइलों का विश्लेषण करके समानांतर किया जा सकता है, जिससे काम की समग्र गति बढ़ जाती है।

मुझे नेटवर्क पर कई समान एल्गोरिदम मिले, लेकिन मेरे पास ऐसे विकल्प थे जो एक सामान्य नियमित अभिव्यक्ति नहीं बनाते हैं, लेकिन लाइन की शुरुआत के लिए प्रत्येक प्रकार के टोकन के लिए नियमित रूप से लगातार अभिव्यक्ति लागू करते हैं, फिर लाइन की शुरुआत से पाए गए टोकन को छोड़ दें और फिर से सभी regexps को लागू करने का प्रयास करें। यह लगभग 10-20 बार धीमा काम करता है, इसके लिए अधिक मेमोरी की आवश्यकता होती है और एल्गोरिथ्म अधिक जटिल होता है। मैंने केवल डीएफए ( निर्धारक परिमित राज्य मशीन) के आधार पर अपने नियमित अभिव्यक्ति कार्यान्वयन का उपयोग करके काम की अधिक गति प्राप्त की। रेगेक्स इंजनों में, एनकेए का आमतौर पर उपयोग किया जाता है - एक नॉनडेर्मिनिस्टिक परिमित राज्य मशीन)। डीएफए 2-3 गुना तेज है, लेकिन इसके लिए नियमित अभिव्यक्ति ऑपरेटरों के सीमित सेट के कारण लिखना अधिक कठिन है।

एसक्यूएल के लिए मेरे उदाहरण में, मैंने नियमित अभिव्यक्तियों को थोड़ा सरल किया और परिणामी टोकन को SQL प्रश्नों का एक पूर्ण-लेक्सिकल विश्लेषक नहीं माना जा सकता है, लेकिन लेख का उद्देश्य सिद्धांत दिखाना है, और एक वास्तविक एसक्यूएल टोकन बनाना नहीं है। मैंने अपने अभ्यास में इस दृष्टिकोण का उपयोग किया और SQL, Java, C, XML, HTML, JSON, पास्कल और यहां तक ​​कि COBOL (मुझे इसके साथ टिंकर करना पड़ा) के लिए पूर्ण-विकसित लेक्सिकल विश्लेषक बनाया।

लेक्सिकल विश्लेषण के लिए नियमित अभिव्यक्ति लिखने के कुछ सरल नियम यहां दिए गए हैं।

1. यदि एक ही टोकन को विभिन्न प्रकारों को सौंपा जा सकता है (उदाहरण के लिए, किसी भी कीवर्ड को पहचानकर्ता के रूप में पहचाना जा सकता है), तो शुरुआत में एक संकीर्ण प्रकार को परिभाषित किया जाना चाहिए। फिर इसके लिए नियमित अभिव्यक्ति पहले लागू की जाएगी और यह टोकन के प्रकार को निर्धारित करेगा। उदाहरण के लिए, मेरे उदाहरण में, कीवर्ड आईडी से पहले परिभाषित किए गए हैं और चयनित टोकन को कीवर्ड के रूप में पहचाना जाएगा, आईडी नहीं
2. पहले टोकन को परिभाषित करें, फिर छोटे वाले। उदाहरण के लिए, आपको पहले <= , > = और फिर अलग करना होगा < , = , = इस मामले में, पाठ <= को कम या बराबर ऑपरेटर के एकल टोकन के रूप में सही ढंग से पहचाना जाएगा, और दो अलग टोकन < और = नहीं
3. लुकहेड और लुकबाइंड का उपयोग करना सीखें। उदाहरण के लिए, SQL में * वर्ण का गुणन ऑपरेटर और तालिका के सभी क्षेत्रों का अर्थ है। एक सरल खोज के प्रयोग से , आप इन दो मामलों को अलग कर सकते हैं, उदाहरण के लिए, यहाँ regexp ! <=! \ _ S। Select \ s ) * केवल "तालिका के सभी फ़ील्ड" मान में वर्ण * ढूँढता है।
4. पाठ में होने वाली त्रुटियों के लिए नियमित अभिव्यक्तियों को परिभाषित करना कभी-कभी उपयोगी होता है। उदाहरण के लिए, यदि आप वाक्य रचना हाइलाइटिंग करते हैं, तो आप अधूरे स्ट्रिंग टोकन के प्रकार को '[^\n\r]* रूप में परिभाषित कर सकते हैं। पाठ को संपादित करने की प्रक्रिया में, उपयोगकर्ता के पास स्ट्रिंग में उद्धरण चिह्न को बंद करने का समय नहीं हो सकता है, लेकिन आपका टोकन इस स्थिति को सही ढंग से पहचानने और इसे सही ढंग से उजागर करने में सक्षम होगा।

इन नियमों का उपयोग करना और इस एल्गोरिथ्म को लागू करना, आप पाठ को लगभग किसी भी भाषा के लिए टोकन में विभाजित कर सकते हैं।