MiniJava प्रोग्रामिंग भाषा संकलक

अपेक्षाकृत कम समय में प्रोग्रामिंग भाषा का कंपाइलर कैसे लिखें। ऐसा करने के लिए, विकास उपकरणों का उपयोग करें जो प्रक्रिया को स्वचालित करते हैं। मैं इस बारे में बात करना चाहूंगा कि मैंने .NET फ्रेमवर्क के लिए मिनीजाव प्रोग्रामिंग भाषा संकलक कैसे लिखा है।

कंपाइलर को संपूर्ण रूप में लिखने की पूरी प्रक्रिया को निम्न छवि में दिखाया गया है। MiniJava प्रोग्रामिंग भाषा में स्रोत कोड वाली एक फ़ाइल इनपुट को खिलाया जाता है। आउटपुट CLR द्वारा निष्पादन के लिए PE फ़ाइल है।



इसके बाद, मैं विवरण के व्यावहारिक भाग पर ध्यान केंद्रित करना चाहूंगा।

MiniJava प्रोग्रामिंग भाषा

MiniJava जावा प्रोग्रामिंग भाषा का एक सबसेट है। अधिभार की अनुमति नहीं है, कंसोल पर मुद्रण केवल System.out.println(...) विधि को कॉल करके पूर्णांकों द्वारा किया जाता है; e.length अभिव्यक्ति int[] सरणियों पर ही लागू होती है।
बेकस-नौर के रूप में व्याकरण का विवरण (भाषा परियोजना की साइट से लिया गया http://www.cambridge.org/us/features/052182060X/ ):

 Goal ::= MainClass ( ClassDeclaration )* <EOF> MainClass ::= "class" Identifier "{" "public" "static" "void" "main" "(" "String" "[" "]" Identifier ")" "{" Statement "}" "}" ClassDeclaration ::= "class" Identifier ( "extends" Identifier )? "{" ( VarDeclaration )* ( MethodDeclaration )* "}" VarDeclaration ::= Type Identifier ";" MethodDeclaration ::= "public" Type Identifier "(" ( Type Identifier ( "," Type Identifier )* )? ")" "{" ( VarDeclaration )* ( Statement )* "return" Expression ";" "}" Type ::= "int" "[" "]" | "boolean" | "int" | Identifier Statement ::= "{" ( Statement )* "}" | "if" "(" Expression ")" Statement "else" Statement | "while" "(" Expression ")" Statement | "System.out.println" "(" Expression ")" ";" | Identifier "=" Expression ";" | Identifier "[" Expression "]" "=" Expression ";" Expression ::= Expression ( "&&" | "<" | "+" | "-" | "*" ) Expression | Expression "[" Expression "]" | Expression "." "length" | Expression "." Identifier "(" ( Expression ( "," Expression )* )? ")" | <INTEGER_LITERAL> | "true" | "false" | Identifier | "this" | "new" "int" "[" Expression "]" | "new" Identifier "(" ")" | "!" Expression | "(" Expression ")" Identifier ::= <IDENTIFIER> 

यहां, व्याकरण को गैर-वर्णों को भाषा श्रृंखला में आउटपुट करने के नियमों द्वारा दर्शाया गया है।
एक टर्मिनल एक व्याकरण का अंतिम प्रतीक है। एक नॉनटर्मिनल एक व्याकरण का प्रतीक है, जिसके लिए टर्मिनलों और / या नॉनटर्मल के संयोजन की श्रृंखला में अनुवाद नियम है, अर्थात्। α → β∈, जहां α∈V, ∪ (N )V) *। N टर्मिनलों की वर्णमाला है, V गैर-टर्मिनलों की वर्णमाला है।
व्याकरण विवरण में सभी टर्मिनलों को दोहरे उद्धरण चिह्नों में वर्णों के अनुक्रम, वर्णों के अनुक्रम द्वारा गैर-टर्मिनलों और साथ ही कोण उद्धरणों में दर्शाया गया है। व्याकरण Goal - Goal ।
एक संकलक लिखने की प्रक्रिया पर विचार करें (आईएल-कोड की पीढ़ी तक) factorial.java प्रोग्राम के उदाहरण का उपयोग करते हुए जो मिनीजाव परियोजना वेबसाइट से लिए गए भाज्य की गणना करता है:

 class Factorial{ public static void main(String[] a){ System.out.println(new Fac().ComputeFac(10)); } } class Fac { public int ComputeFac(int num){ int num_aux ; if (num < 1) num_aux = 1 ; else num_aux = num * (this.ComputeFac(num-1)) ; return num_aux ; } } 

लेक्सिकल और पार्सिंग

मैंने कंपाइलर लिखने के इन दो चरणों को संयोजित किया, क्योंकि वे कंपाइलर जनरेटर का उपयोग करके किए गए थे। अब संकलक जनरेटर की पर्याप्त संख्या है, जैसे कि एएनटीएलआर , जीपीपीजी , कोको / आर , गोल्ड पार्सिंग सिस्टम और कई अन्य ।
मैंने ANTLR का उपयोग किया क्योंकि यह व्याकरण लिखने के लिए सुविधाजनक है, इसमें एक पाठ संपादक के साथ एक ग्राफिकल शेल है और अमूर्त वाक्यविन्यास पेड़ (ANTLRWorks 1.4.3 पर्यावरण) के दृश्य की अनुमति देता है, लेकिन संस्करण 2.0 साइट http://tunnelvisionlabs.com/products/demo पर पहले ही प्रकट हो चुका है / एंटर्वर्क्स )।
संकलक जनरेटर आपको व्याकरण के अनुरूप टोकन का एक सेट और एक सार सिंटेक्स ट्री (एएसटी) प्राप्त करने की अनुमति देता है।
बेकस-नौर के रूप में व्याकरण के विवरण से, मैंने ANLLR प्रसंस्करण के लिए एक व्याकरण फ़ाइल संकलित की। व्याकरण को LL दृश्य में कम करने, बाईं पुनरावृत्ति को हटाने और संबंधित भागों में C # में व्याकरण प्रतीकों के निर्माण को लिखने के बाद, मैंने आगे की कोड जनरेशन प्रक्रिया के लिए एक फ़ाइल तैयार की (परियोजना निर्देशिका में MiniJava.g व्याकरण फ़ाइल है, जिसका लिंक नीचे दिया गया है)।
इसलिए, उदाहरण के लिए, एक मुख्य वर्ग बनाना निम्नानुसार वर्णित है:

 mainClassDecl returns [NonTerm value] : CLASS^ id=ID LCURLY! PUBLIC! STATIC! VOID! MAIN! LPAREN! STRING! LBRACK! RBRACK! ID RPAREN! LCURLY! statement=stmtList RCURLY! RCURLY! { $value = NonTerm.CreateMainClassDecl(new Token(TokenType.ID, id.Text, id), statement.valueList); if (flagDebug) Console.WriteLine("mainClassDecl"); } ; 

यहाँ mainClassDecl मुख्य वर्ग के विवरण के अनुरूप नियम है, जो निम्नलिखित विवरण के लिए जिम्मेदार है:

 MainClass ::= "class" Identifier "{" "public" "static" "void" "main" "(" "String" "[" "]" Identifier ")" "{" Statement "}" "}" 

"^" साइन, नियम के रूट को CLASS टोकन बनाता है, "!" साइन अन्य टोकन के बाद, ANTLR को उनके सत्यापन की अनदेखी करने के लिए कहता है (यानी, एएसटी के निर्माण के दौरान बाहर रखा गया है)। उन नियमों को जिनके परिणामों को बचाया जाना चाहिए (मुख्य वर्ग ID का नाम और सूची stmtList ) को चर ( id और statement , क्रमशः) को सौंपा जाना चाहिए। यह ध्यान दिया जाना चाहिए कि ऊपरी मामले में टोकन लिखे गए हैं, और निचले मामले में नियम। $value वह $value है जो मूल नियम पर वापस आएगा। रिटर्न प्रकार को स्क्वायर ब्रैकेट्स में returns कीवर्ड (इस मामले में, NonTerm ) के बाद परिभाषित किया गया है।
आउटपुट फ़ाइल .NET (antlr-dotnet-tool-3.3.1.7705 के लिए इस्तेमाल किया गया था) के लिए ANTLR कंपाइलर कमांड का उपयोग करके बनाया गया है:

Antlr3.exe -o "___" "_____\MiniJava.g"


व्याकरण (सुविधा के लिए) में किए गए स्वयं के परिवर्तन:

• जोड़ा double प्रकार;
• printf(…) कंसोल पर कॉलिंग System.out.println(…) समान है;
• प्रत्येक प्रिंट के बाद, Console.Readkey() विधि को (डिबगिंग को आसान बनाने के लिए) कहा जाता है।

लेक्सिकल और पार्सिंग के परिणामों को एक्सएमएल फ़ाइल के रूप में प्रदर्शित किया जाता है।
लेक्सिकल विश्लेषण के परिणाम को प्रदर्शित करने के लिए निम्नलिखित Lexer वर्ग विधि का उपयोग किया जाता है।

 public void SaveToFile(string fileName) { List<IToken> tokens = TokenStream.GetTokens(); XElement xElement = new XElement("Lexer", from token in tokens select new XElement("Token", new XAttribute("Text", token.Text.TokenToString()), new XAttribute("TokenIndex", token.TokenIndex), new XAttribute("Type", token.Type), new XAttribute("Line", token.Line), new XAttribute("CharPositionInLine", token.CharPositionInLine), new XAttribute("StartIndex", token.StartIndex), new XAttribute("StopIndex", token.StopIndex) ) ); xElement.Save(fileName); } 

शाब्दिक विश्लेषण का परिणाम 152 टोकन है (पहले 30 यहाँ दिए गए हैं):

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



बेस क्लास BaseSymbol संयुक्त वर्णमाला से एक व्याकरण का प्रतीक है, Token - एक टोकन (टर्मिनल) और NonTerm - NonTerm इसे विरासत में मिला है। Nonterminals हैं: ProgramStatement - व्याकरण स्वयंसिद्ध, MainClassDecl - मुख्य वर्ग, ClassDecl - वर्ग, MethodDecl - विधि, ExtendsClause - वर्ग की विरासत, TypeDecl - प्रकार, VarDecl - चर, ExpressionDecl - अभिव्यक्ति, StatementDecl , StatementDecl , StatementDecl , StatementDecl । ऑपरेटर कक्षाएं: IfStatement एक स्टेटमेंट स्टेटमेंट है, while WhileStatement एक while स्टेटमेंट है, StatementList की एक सूची है, AssignVarStatement एक नए चर की घोषणा और असाइनमेंट है, AssignIdStatement पहचानकर्ता द्वारा पूर्व में घोषित किया गया एक वेरिएबल असाइनमेंट है।
एएसटी उत्पन्न करने के लिए एएनटीएलआर व्याकरण फ़ाइल में इन कक्षाओं का उपयोग किया जाता है।
पार्सिंग द्वारा उत्पन्न एएसटी प्रतिनिधित्व को ToXmlTree() बेस क्लास के पुनरावर्ती ToXmlTree() पद्धति का उपयोग करके xml फ़ाइल में सहेजा गया है। विधि केवल टोकन के लिए ओवरराइड की जाती है। बेस क्लास BaseSymbol विधि इस प्रकार है:

 public virtual XElement ToXmlTree() { XElement elements = new XElement(ToString()); Symbols.ForEach(symbol => { if (symbol != null) { XElement el = symbol.ToXmlTree(); elements.Add(el); } }); return elements; } 

वृक्ष निर्माण का परिणाम यहां प्रस्तुत है:

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

आईएल कोड पीढ़ी

पीढ़ी के लिए, मैंने फिर से पहिया को फिर से शुरू करने के लिए शुरू नहीं किया, लेकिन कोडप्रोजेक्ट http://www.codeproject.com/Articles/20921/RunSharp-Reflection-Emit-Has-Never-Been-Easier पर पोस्ट की गई मौजूदा RunSharp परियोजना का लाभ उठाया। RunSharp एक प्रोजेक्ट है जो System.Reflection.Emit नामस्थान से क्लास मेथड कॉल को एनकैप्सुलेट करता है, IL कोड जनरेट करने की प्रक्रिया को सरल करता है।
निम्नलिखित डेटा संरचनाएं कोड पीढ़ी के लिए उपयोग की जाती हैं: प्रोग्राम क्लास टेबल (कक्षाओं की कोड पीढ़ी के लिए और निर्भरता रिज़ॉल्यूशन के लिए, उदाहरण के लिए, जब एक क्लास का एक तरीका दूसरे और इसके विपरीत को संदर्भित करता है), प्रत्येक क्लास के तरीकों की एक सूची (कोड जेनरेशन ऑफ़ मेथड), स्थानीय चर की सूची (ट्रैकिंग लिंक के लिए) स्थानीय चर के अंदर if , while ब्लॉक और विधि का शरीर), स्थानीय चर के ढेर (एकता और द्विआधारी संचालन के लिए), वर्तमान विधि के औपचारिक मापदंडों की एक सूची।
एक कोड जेनरेशन कंट्रोल टेबल का भी उपयोग किया जाता है, जिसमें व्याकरण चिन्ह का नाम और विधि जो कोड प्रकट होने पर उत्पन्न करता है।
IL-code का जनरेशन मुख्य Generate(BaseSymbol root) पुनरावर्ती विधि Generate(BaseSymbol root) ।

 private void Generate(BaseSymbol root) { if (root == null) { return; } if (root.GrammarMember == GrammarMemberType.NonTerm) { NonTerm nonTerm = root as NonTerm; _compilerLogger.PrintGenerateNonTerm(nonTerm); if (_emitTableDictionary.ContainsKey(nonTerm.TypeNonTerm)) { _emitTableDictionary[nonTerm.TypeNonTerm](nonTerm); } else { root.Symbols.ForEach(Generate); } } } 

विधि यह निर्धारित करती है कि क्या root नॉनटर्मिनल है, और यदि कंट्रोलर टेबल में नॉनटर्मिनल का प्रकार निहित है, तो कंट्रोल टेबल बनाने का तरीका निष्पादित किया जाता है, अन्यथा, root में निहित प्रत्येक व्याकरण वर्ण के लिए पीढ़ी पुनरावर्ती रूप से किया जाता है।
नियंत्रण तालिका में निम्नलिखित विधियाँ हैं जो निम्नलिखित व्याकरण वर्णों के लिए निर्देश उत्पन्न करती हैं:

• EmitMainClass - कार्यक्रम का मुख्य वर्ग;
• एमिटक्लास - कार्यक्रम का वर्ग (मुख्य एक को छोड़कर);
• EmitClassVar - वर्ग चर (निजी वर्ग क्षेत्र);
• एमिटमथोड - एक वर्ग विधि;
• EmitVarStatement - दाईं ओर एक नई अभिव्यक्ति चर का असाइनमेंट;
• EmitNewStatement - एक चर के लिए मेमोरी आवंटन;
• EmitNewArrayStatement - एक सरणी के लिए स्मृति का आवंटन;
• EmitIdStatement - दाईं ओर एक अभिव्यक्ति के लिए एक चर का असाइनमेंट;
• EmitArrayIdStatement - दाईं ओर अभिव्यक्ति की सरणी को असाइनमेंट;
• EmitArrayInduritiesStatement - ऐरे इंडेक्स द्वारा पहुंच;
• EmitMethodCallExpression - विधि कॉल;
• EmitBinaryExpression - बाइनरी ऑपरेशन;
• EmitUnaryExpression - एकतरफा संचालन;
• EmitPrintStatement - प्रिंट स्टेटमेंट;
• एमिटिफ़स्टेट - स्थिति;
• EmitWhileStatement - लूप करते समय;
• EmitLengthFunctionExpression - सरणी की लंबाई।

इन विधियों का एक भाग पुनरावर्ती विधि Generate() कहता है।
तो, विधि निर्देश उत्पन्न करने की विधि इस प्रकार है:

 private void EmitMethod(NonTerm nonTerm) { Token typeMethodDeclSimple; Token methodName; List<BaseSymbol> formalParametersList; BaseSymbol methodStatementList; BaseSymbol returnStatement; NonTermFactory.GetMethodDecl(nonTerm, out typeMethodDeclSimple, out methodName, out formalParametersList, out methodStatementList, out returnStatement); _currentFormalArgumentList.Clear(); foreach (BaseSymbol symbol in formalParametersList) { Token type; Token id; NonTermFactory.GetFormalArgumentDeclaration(symbol, out type, out id); _currentFormalArgumentList.Add(id.Value); } _compilerLogger.PrintRefreshFormalArgumentList(_currentFormalArgumentList); _currentMethod = _methodsTables[_currentClass.Name][methodName.Value]; _g = _currentMethod; GeneratePreInitLocalVariables(methodStatementList); Generate(methodStatementList); Type resultType = GetVariableType(typeMethodDeclSimple); string nameResult = AddTempLocalVariable(resultType); EmitExpression(returnStatement, resultType, nameResult); try { _g.Return(_currentOperandTempResult); } catch (InvalidCastException ex) { throw new CodeGenerationException(MessagesHelper.TypeMismatchEx, returnStatement.ToStringInfo(), ex); } ClearCurrentBlockLocalVariables(); } 

सबसे पहले, हम विधि के लिए सभी आवश्यक डेटा प्राप्त करते हैं (रिटर्न प्रकार typeMethodDeclSimple , विधि का नाम formalParametersList , औपचारिक मापदंडों की सूची formalParametersList , विधि के ऑपरेटरों की सूची methodStatementList और रिटर्न एक्सप्रेशन रिटर्न returnStatement )। इसके बाद, औपचारिक चर की वर्तमान सूची भर दी जाती है, जिसके बाद चर _currentMethod एक ऑब्जेक्ट (जैसे कि RunSharp लाइब्रेरी से MethodGen) सौंपा जाता है, जो विधि उत्पन्न करने के लिए ज़िम्मेदार है। फिर, GeneratePreInitLocalVariables() विधि में, स्थानीय चर की सूची आबाद है और विधि की सामग्री को पुन: उत्पन्न किया जाता है, एक ऑपरेटर उत्पन्न होता है जो विधि परिणाम देता है, जो return कीवर्ड के बाद आता है, और अंत में ब्लॉक के स्थानीय चर की सूची साफ़ हो जाती है।
और चर असाइनमेंट ऑपरेशन को बनाने के लिए जिम्मेदार विधि निम्नानुसार है:

 private void EmitIdStatement(NonTerm nonTerm) { Token idToken; BaseSymbol expression; NonTermFactory.GetAssignIdStatement(nonTerm, out idToken, out expression); Operand operand; if (_currentFormalArgumentList.Contains(idToken.Value)) { operand = _g.Arg(idToken.Value); } else if (_localVariablesTable.ContainsKey(idToken.Value)) { operand = _localVariablesTable[idToken.Value]; } else { operand = _g.This().Field(idToken.Value); } _currentOperandTempResult = EmitExpression(expression, operand.Type, idToken.Value); try { _g.Assign(operand, _currentOperandTempResult); } catch (InvalidCastException ex) { throw new CodeGenerationException(MessagesHelper.AssignTypeMismatchEx, expression.ToStringInfo(), ex); } } 

यहां, पहले हमें एक टोकन मिलता है, जिसमें हम अभिव्यक्ति को सही ( idToken ) और स्वयं expression ( expression ) को असाइन करते हैं। अगला, हम यह निर्धारित करते हैं कि चर कहाँ से आया है: स्थानीय मापदंडों की तालिका ( _localVariablesTable ) या क्या यह एक वर्ग चर है, औपचारिक मापदंडों ( _currentFormalArgumentList ) की सूची से। उसके बाद, हम EmitExpression() विधि को कॉल करके दाईं ओर अभिव्यक्ति की गणना करते हैं, और असाइनमेंट उत्पन्न करते हैं।

इसी तरह, अन्य डिजाइनों की बारीकियों को ध्यान में रखते हुए, उनका कोड उत्पन्न होता है।

यहाँ हमारे भाज्य गणना कार्यक्रम के लिए कोड पीढ़ी के परिणाम का एक लॉग है।


एक कंसोल अनुप्रयोग कंपाइलर के लिए लिखा गया है जो निम्न कमांड लाइन तर्क लेता है:
-i < > [-o < >]

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

निष्कर्ष

कुल मिलाकर, मौजूदा विकास साधनों का उपयोग करके C # में .NET फ्रेमवर्क के लिए एक MiniJava प्रोग्रामिंग भाषा संकलक लिखने का एक तरीका चर्चा की गई। यहां, मैंने एक कंपाइलर लिखने के लिए आवश्यक उच्च-स्तरीय बिंदुओं पर ध्यान केंद्रित किया।
लिखित कंपाइलर मिनीजवा प्रोजेक्ट होम पेज से फैक्टरियल कैलकुलेशन, बाइनरी सर्च, बबल सॉर्टिंग, ट्री ट्रैवर्सल, क्विक सॉर्ट, लीनियर सर्च, लिंक लिस्ट बनाने, बाइनरी ट्री बनाने जैसे उदाहरणों को सफलतापूर्वक हैंडल करता है।
प्रोजेक्ट के लिए सोर्स कोड GitHub पर उपलब्ध है ।

सूत्रों का कहना है

सामान्य (सिद्धांत और व्यवहार)

• अहो, नेटवर्क, उलमैन। संकलनकर्ता। सिद्धांत, प्रौद्योगिकी, उपकरण।
• बेलौसोव, टकाचेव। असतत गणित।
• .NET फ्रेमवर्क के लिए एक भाषा संकलक बनाना http://msdn.microsoft.com/en-us/magazine/cc136755.bx

ANTLR

• ANTLR ट्यूटोरियल - अभिव्यक्ति भाषा http://meri-stuff.blogspot.ru/2011/09/antlr-tutorial-expression-language.html
• ANTLR http://club.shelek.ru/viewart.php?id=39 का उपयोग करके पार्सर्स लिखना
• ANTLR पर अच्छी परिचयात्मक प्रस्तुति http://fmt.cs.utwente.nl/courses/vertalerbouw/sheets/vb-04-antlr-1-4up.pdf

MiniJava

• MiniJava का अवलोकन http://www-cs-facademy.stanford.edu/~eroberts//papers/SIGCSE-2001/MiniJava.pdf
• MiniJava प्रकार प्रणाली http://www.cs.ucla.edu/~palsberg/course/cs132/miniJava-typesystem.pdf
• मिनीजवा सिंटैक्स http://www.cs.purdue.edu/homes/hosking/502/project/grammar.html