الجزء الثاني من قصتي مترجم سويفت. سنبدأ في دراسة الواجهة الأمامية ، أو بالأحرى الأجزاء التي تكون مسؤولة عن التحليل والتحليل الأولي للشفرة المصدرية.

يمكن العثور على الجزء الأول من المقال هنا .

الواجهة الأمامية

مهمة الواجهة الأمامية هي توليد تمثيل وسيط من الكود المصدري ونقله إلى LLVM. يمكن تقسيم هذه العملية إلى 8 خطوات. يمكن عرض نتيجة كل منها تقريبًا بتمرير معلمة خاصة إلى المحول البرمجي.

أدناه ، سأوضح تنفيذ برنامج التحويل البرمجي لـ "لغة برمجة" بدائية تحتوي فقط على "نطاق" ورقم. وظيفتها الوحيدة هي إخراج الرقم (إن وجد) إلى وحدة التحكم. على سبيل المثال ، نتيجة لتنفيذ هذا "الرمز" ، سيتم عرض الرقم 678:

{{{678}}} 

هذا المحول البرمجي ضروري فقط لتسهيل فهم ما يحدث في المراحل المختلفة. يمكن رؤية تنفيذ لغة حقيقية ، ولكن بسيطة في مثال Kaledoscope .

يتكون كل نطاق من شريحة فتح ومحتوى وقوس إغلاق. هذا يمكن أن يكتب مثل هذا:

 scope ::= open_brace x close_brace open_brace ::= "{" close_brace ::= "}" 

قد تكون المحتويات هي نفس النطاق أو الرقم أو لا شيء موضح هنا :

 scope ::= open_brace x close_brace x ::= scope | number | <empty> open_brace ::= "{" close_brace ::= "}" 

الرمز | يعني "أو". يتكون الرقم من رقم واحد أو أكثر:

 scope ::= open_brace x close_brace x ::= scope | number | <empty> open_brace ::= "{" close_brace ::= "}" number ::= digit | number digit digit :: = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" 

يسمى هذا السجل نموذج Backus-Naur (BNF) ، ويطلق على جملة جميع القواعد قواعد اللغة أو بناء الجملة.

هناك أيضا تعزيز BPF (RBNF). تمت إضافة أحرف خاصة إضافية إليها ، على سبيل المثال ، أقواس للتجميع.

الأقواس المتعرجة تشير إلى التكرار. مثل هذا السجل يعني أن A إما فارغة أو مساوية لأي عدد من B:

 A ::= { B } 

تستخدم الأقواس المربعة للحوادث الشرطية. مثل هذا السجل يعني أن A إما فارغة أو تساوي B:

 A ::= [B] 

باستخدام RBNF النحوي للمترجم الأقواس ، يمكنك تحويله إلى هذا النموذج:

 scope ::= open_brace [scope | number] close_brace open_brace ::= "{" close_brace ::= "}" number ::= digit {digit} digit :: = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" 

بالإضافة إلى برنامج التحويل البرمجي للأقواس ، سأبين كيفية استخدام برنامج التحويل البرمجي Swift للحصول على نتائج كل خطوة من الخطوات باستخدام مثال لتعبير بسيط:

 let x = 16 

الكود بسيط للغاية لتسهيل فهمه. قواعد لغة البرمجة الحقيقية أكثر تعقيدًا مما ذكر أعلاه. يمكنك إلقاء نظرة على بناء جملة Swift على الموقع الرسمي.

ليكسر

من وجهة نظر المترجم ، يكون ملف التعليمات البرمجية المصدر دفقًا من الأحرف العشوائية ، وربما نوعًا من القمامة. لذلك ، تتمثل الخطوة الأولى في تحويل هذه الأحرف العشوائية إلى كلمات يمكن استخدامها بلغة برمجة.

يتم ذلك بواسطة محلل معجمي (lexer / tokenizer). تسمى الكلمات التي يبحث عنها الرموز أو الرموز (لن نخوض في التفاصيل غير الضرورية ونقبل هذه المصطلحات بشكل مترادف). لذلك ، تسمى هذه العملية أيضًا الرمز المميز.

يقوم lexer بإجراء التحليل وفقًا لقواعد اللغة. مسح الرمز بالرمز ، فإنه يعثر على مراسلات الكود المصدر والجانب الأيمن من السجل ، ثم ينشئ الرمز المميز المقابل من الجانب الأيسر.

مثال تنفيذ Lexer

يسمح النحوي بثلاثة رموز: قوس فتح ، قوس إغلاق ، ورقم. يتم تقديمها باعتبارها تعداد. بالإضافة إلى قائمة الأخطاء المحتملة:

 enum Token: CustomStringConvertible { case openBraceToken case closeBraceToken case number(Int) var description: String { switch self { case .openBraceToken: return "openBraceToken" case .closeBraceToken: return "closeBraceToken" case .number(let value): return "\(value)" } } } enum LexerError: Error { case unexpectedCharacted case invalidNumber } 

في lexer نفسه ، يتم تخزين سلسلة الإدخال وفهرس الحرف الحالي:

 class Lexer { private let string: String private var index: String.Index private var currentCharacter: Character? { return index != string.endIndex ? string[index] : nil } init(string: String) { self.string = string index = string.startIndex } 

يتم بدء التحليل عن طريق استدعاء الأسلوب startAnalyze () . في ذلك ، يتم استدعاء طريقة في حلقة للحصول على الرمز المميز التالي ، الذي يتم إضافته إلى الصفيف. في النهاية - اعتراض أخطاء التعرف:

 func startAnalyzing() -> [Token] { var result: [Token] = [] do { while let token = try getNextToken() { result.append(token) } } catch LexerError.unexpectedCharacted { print("Unexpected character at index \(index.encodedOffset)") result = [] } catch LexerError.invalidNumber { print("Invalid number at index \(index.encodedOffset)") result = [] } catch { print("Unexpected error") result = [] } return result } 

يتكون الحصول على رمز مميز من التحقق من الحرف الحالي ونقل الفهرس إلى الأمام حرفًا واحدًا أو أكثر:

 private func getNextToken() throws -> Token? { guard let character = currentCharacter else { return nil } switch character { case "{": return getOpenBrace() case "}": return getCloseBrace() default: break } if let scalar = character.unicodeScalars.first, CharacterSet.decimalDigits.contains(scalar) { return try getNumber() } throw LexerError.unexpectedCharacted } private func getOpenBrace() -> Token { moveIndex() return Token.openBraceToken } private func getCloseBrace() -> Token { moveIndex() return Token.closeBraceToken } 

إذا تم العثور على رقم ، فسيتم استدعاء الأسلوب getNumber () لتحليله . إنه ببساطة يجمع كل الأرقام في سطر واحد ويحولها إلى كثافة العمليات:

 private func getNumber() throws -> Token { var numberString = "" while let character = currentCharacter, let scalar = character.unicodeScalars.first, CharacterSet.decimalDigits.contains(scalar) { numberString.append(character) moveIndex() } guard let number = Int(numberString) else { throw LexerError.invalidNumber } return Token.number(number) } 

لبدء lexer ، تحتاج إلى تمريره مع التعليمات البرمجية المصدر واستدعاء طريقة startAnalyze () :

 let lexer = Lexer(string: "{{5678}}") let tokens = lexer.startAnalyzing() 

النتيجة تلبي التوقعات:

 [openBraceToken, openBraceToken, 5678, closeBraceToken, closeBraceToken] 

في Swift ، يعد lexer جزءًا من المحلل اللغوي ، ولا يمكنك الحصول على قائمة الرموز المميزة المتوافقة مع الكود المصدر.

كود المصدر:

• Lexer.h
• Lexer.cpp

محلل

المحلل اللغوي يؤدي تحليل. يتم إرسال سلسلة من الرموز إلى المدخلات ، وتكون نتيجة العمل هي AST.

AST هو رسم بياني تكون فيه القمم مشغلة والأوراق هي معاملاتها. على سبيل المثال ، يتكون التعبير 1 + (2 * 3) من عاملين: الجمع والضرب. المعامل الأول للإضافة هو 1 ، والثاني هو نتيجة للمنتجين 2 و 3. لا تستخدم أقواس التجميع في AST ، لأنها ليست ضرورية. يحدد الرسم البياني نفسه تداخل العمليات:

يمكن تمثيل كل عقدة ، على سبيل المثال ، بواسطة بنية أو تعداد يحتوي على عناصر تابعة.

أثناء تكوين الشجرة ، يتحقق المحلل اللغوي من قواعد اللغة: ما إذا كان التسلسل الصحيح يتكون من "كلمات". على سبيل المثال ، سيتم تحليل السلسلة "{{}" بنجاح بواسطة lexer ، لكنها غير صحيحة لأن شريحة الإغلاق الثانية مفقودة.

محلل سويفت هو محلل تنازلي متكرر. وهذا يعني أنه يعثر أولاً على كيان خارجي ، ثم يحلل محتوياته بشكل متكرر. يعثر المحلل الصعودي أولاً على الكيان الأكثر تداخلًا ، ثم يرتفع.

مثال لتنفيذ المحلل اللغوي

هناك عدد كبير من أنواع وتنفيذ المحللون. فيما يلي أبسط تنفيذ لمحلل تنازلي وصاعد لإظهار الفرق بوضوح.

من الشائع بين كلا المحلل اللغوي أن يمثل تعداد يمثل أحد الأخطاء وعقدة AST:

 indirect enum ASTNode: CustomStringConvertible { case brace(childNode: ASTNode?) case number(value: Int) var description: String { switch self { case let .brace(childNode?): return "brace(\(childNode.description))" case .brace(nil): return "brace(nil)" case let .number(value): return "\(value)" } } } enum ParserError: Error { case expectedOpenBrace case expectedCloseBrace case expectedNumber case expectedEndOfArray } 

محلل تنازلي

محلل هبوطي يخزن مجموعة من الرموز المميزة وفهرس الرمز المميز الحالي:

 class TopDownParser { private let tokens: [Token] private var index: Int private var currentToken: Token? { return index != tokens.endIndex ? tokens[index] : nil } init(tokens: [Token]) { self.tokens = tokens index = tokens.startIndex } 

الطريقة العامة الوحيدة هي بدء التحليل. أولاً ، يتم استدعاء تحليل زوج من الأقواس. نظرًا لأن الكيان الجذر لا يمكن أن يكون سوى زوج من الأقواس (السلسلة "{} {}" غير مسموح بها) ، فهذا يكفي. سيتم إجراء مزيد من التحليل بشكل متكرر. يبقى فقط للتحقق من أن صفيف الرمز المميز فارغ وللاستثناء الاستثناءات:

 func startParsing() -> ASTNode? { var rootNode: ASTNode? do { rootNode = try parseBraces() guard currentToken == nil else { rootNode = nil throw ParserError.expectedEndOfArray } } catch ParserError.expectedCloseBrace { print("Expected close brace at index \(index)") } catch ParserError.expectedOpenBrace { print("Expected open brace at index \(index)") } catch ParserError.expectedEndOfArray { print("Expected end of tokens array at index \(index)") } catch { print("Unexpected error") } return rootNode } 

عند تحليل الأقواس ، يتم فحص شريحة الفتح أولاً ، ثم بشكل متكرر المحتويات داخل الزوج (إن وجدت) ، وفي نهاية قوس الإغلاق.

نقطة مهمة: بمجرد أن يرى المحلل القوس الافتتاحي ، فإنه يعتبر أنه عثر على الزوج التالي بنجاح ويمكنك متابعة تحليل المحتويات. هذا هو السبب في أنه ينتقل من الكيانات الخارجية إلى الكيانات الداخلية.

 private func parseBraces() throws -> ASTNode? { try consumeOpenBrace() print("Pair found") let node: ASTNode? if let currentToken = self.currentToken, case .openBraceToken = currentToken { node = .brace(childNode: try parseBraces()) } else if let currentToken = self.currentToken, case let .number(value) = currentToken { node = .brace(childNode: .number(value: value)) try consumeNumber() } else { node = .brace(childNode: nil) } try consumeCloseBrace() return node } 

يتكون المسح الضوئي من فحص الرمز المميز ونقل الفهرس الحالي:

 private func consumeOpenBrace() throws { if let currentToken = self.currentToken, case .openBraceToken = currentToken { print("Open brace found") moveIndex() } else { throw ParserError.expectedOpenBrace } } 

محلل تصاعدي

تطبيق محلل المنبع هو أكثر تعقيدا قليلا. إنه بحاجة إلى الحفاظ على حالته ومجموعة من الرموز وجدول تحويل بين الولايات.

يتم تقديم الحالة كتعداد. من الضروري مراعاة الرموز السابقة والرد بشكل صحيح على ظهور علامة جديدة. نظرًا لأن هذا المثال بسيط للغاية ، فقد تبين أنه في الحالة الأولى ، يقوم المحلل اللغوي بتوزيع أقواس الفتح ، وفي الحالة الثانية - الأقواس الختامية:

 class BottomUpParser { private enum State { case state1 case state2 } 

يتم تهيئة المحلل اللغوي بشكل مشابه للمحلل الأول. لا يوجد جدول انتقال ككيان منفصل. من أجل التبسيط ، سوف يلعب Switch دوره:

 private let tokens: [Token] private var index: Int private var state: State = .state1 private var stack: [Token] = [] private var rootNode: ASTNode? private var currentToken: Token? { return index != tokens.endIndex ? tokens[index] : nil } init(tokens: [Token]) { self.tokens = tokens index = tokens.startIndex } 

يتم تشغيل التحليل أيضًا باستخدام طريقة startParsing () . في ذلك ، تتم معالجة كل رمز رمزي بدوره ، وفي النهاية ، يتم استدعاء التحقق من أن المكدس فارغ ويتم استكمال التحليل بنجاح:

 func startParsing() -> ASTNode? { do { guard !tokens.isEmpty else { throw ParserError.expectedOpenBrace } while index != tokens.endIndex { try parseNextToken() moveIndex() } guard stack.isEmpty else { rootNode = nil throw ParserError.expectedCloseBrace } } catch ParserError.expectedCloseBrace { rootNode = nil print("Expected close brace at index \(index)") } catch ParserError.expectedOpenBrace { rootNode = nil print("Expected open brace at index \(index)") } catch ParserError.expectedEndOfArray { rootNode = nil print("Expected end of tokens array at index \(index)") } catch { rootNode = nil print("Unexpected error") } return rootNode } 

تتم معالجة الرمز المميز التالي للمفتاح مع مراعاة الحالة الحالية. إذا وصلت شريحة فتح وكانت الحالة 1 ، فسيتم إضافتها إلى المجموعة. في حالة الإغلاق ، يتحقق المحلل اللغوي لمعرفة ما إذا كان هناك قوس فتح على المكدس الخاص به ، ثم يزيله من المكدس ويتحول إلى الحالة 2. ويتم أيضًا الانتقال إلى الحالة الثانية عند العثور على رقم.

يستمر المحلل اللغوي في إزالة عنصر واحد من المكدس لكل قوس إغلاق. إذا جاءت شريحة أو رقم فتح في هذه اللحظة ، فهذا خطأ في صفيف الإدخال.

نقطة مهمة: يعتبر المحلل الصاعد أنه لم يعثر على الزوج إلا بعد الهبوط في التسلسل الهرمي ، حيث يرى قوس إغلاق ، بشرط أن يكون الفتح مفتوحًا في المجموعة. بعد ذلك فقط سيبحث عن الجوهر الذي يحتوي عليه ، وهكذا إلى الجذر. هذا هو السبب في أنه يسمى تصاعدي.

 private func parseNextToken() throws { guard let currentToken = currentToken else { return } switch (state, currentToken) { case (.state1, .openBraceToken): print("Open brace found") stack.append(.openBraceToken) case (.state1, .number(let value)): if stack.isEmpty { throw ParserError.expectedOpenBrace } else { consumeNumber(value: value) state = .state2 } case (.state1, .closeBraceToken): if stack.isEmpty { throw ParserError.expectedOpenBrace } else { consumeCloseBrace() state = .state2 } case (.state2, .closeBraceToken): if stack.isEmpty { throw ParserError.expectedEndOfArray } else { consumeCloseBrace() } case (.state2, .number), (.state2, .openBraceToken): if stack.isEmpty { throw ParserError.expectedEndOfArray } else { throw ParserError.expectedCloseBrace } } } private func consumeCloseBrace() { print("Close brace found") _ = stack.popLast() print("Pair found") if rootNode == nil { rootNode = .brace(childNode: nil) } else { rootNode = .brace(childNode: rootNode) } } private func consumeNumber(value: Int) { rootNode = .number(value: value) } 

لبدء كل من المحلل اللغوي ، تحتاج إلى تمرير مجموعة من الرموز المميزة المستلمة من lexer واستدعاء طريقة startParsing () :

 let parserTD = TopDownParser(tokens: tokens) let ast1 = parserTD.startParsing() let parserBU = BottomUpParser(tokens: tokens) let ast2 = parserBU.startParsing() 

كانت النتيجة لكل من المحلل اللغوي صحيحة:

 brace(brace(5678)) 

باستخدام محلل سويفت

لبدء محلل Swift ، تحتاج إلى تمرير إشارة -dump-parse إلى المحول البرمجي:

 swiftc -dump-parse main.swift 

يحتوي AST الحقيقي على بنية أكثر تعقيدًا من محلل الأقواس. ولكن نظرًا لكونها صغيرة ، يمكنك بسهولة اكتشافها وإيجاد العدد الصحيح الحرفي 16 والثابت x :

 (source_file (top_level_code_decl (brace_stmt (pattern_binding_decl (pattern_named 'x') (integer_literal_expr type='<null>' value=16)) )) (var_decl "x" type='<null type>' let storage_kind=stored)) 

هذا النوع من AST هو شجرة غير نمطية. لذلك ، لا يحتوي الثابت x على النوع type = '' المحدد. إذا حددتها بوضوح - دع x: Int = 16 ستتغير الشجرة ، ولكن لن يتم تسجيل النوع على أي حال:

 (source_file (top_level_code_decl (brace_stmt (pattern_binding_decl (pattern_typed (pattern_named 'x') (type_ident (component id='Int' bind=none))) (integer_literal_expr type='<null>' value=16)) )) (var_decl "x" type='<null type>' let storage_kind=stored)) 

كود المصدر:

• رؤوس المحلل
• ملفات تنفيذ المحلل

سما

الشجرة المستلمة من المحلل اللغوي صحيحة من الناحية النحوية ، لكن قد تظل هناك أخطاء فيها. على سبيل المثال ، أثناء التحليل ، يكون من المستحيل (غير مألوف) تحديد أن يتم الإعلان عن متغير قبل الاستخدام. يتم ذلك بواسطة المحلل الدلالي. يمر عبر الشجرة بأكملها ويقوم بتعيين أنواع للتعبيرات ، ويتحقق من دعم البروتوكول ، ويجمع أدوات التهيئة الافتراضية للهياكل ، وأكثر من ذلك بكثير.

باستخدام سويفت محلل الدلالية

لبدء محلل الدلالات ، استخدم العلم -dump-ast :

 swiftc -dump-ast main.swift 

نتيجة الأمر:

 (source_file (top_level_code_decl (brace_stmt (pattern_binding_decl (pattern_named type='Int' 'x') (call_expr implicit type='Int' location=main.swift:1:9 range=[main.swift:1:9 - line:1:9] nothrow arg_labels=_builtinIntegerLiteral: (constructor_ref_call_expr implicit type='(_MaxBuiltinIntegerType) -> Int' location=main.swift:1:9 range=[main.swift:1:9 - line:1:9] nothrow (declref_expr implicit type='(Int.Type) -> (_MaxBuiltinIntegerType) -> Int' location=main.swift:1:9 range=[main.swift:1:9 - line:1:9] decl=Swift.(file).Int.init(_builtinIntegerLiteral:) function_ref=single) (type_expr implicit type='Int.Type' location=main.swift:1:9 range=[main.swift:1:9 - line:1:9] typerepr='Int')) (tuple_expr implicit type='(_builtinIntegerLiteral: Int2048)' location=main.swift:1:9 range=[main.swift:1:9 - line:1:9] names=_builtinIntegerLiteral (integer_literal_expr type='Int2048' location=main.swift:1:9 range=[main.swift:1:9 - line:1:9] value=16)))) )) (var_decl "x" type='Int' interface type='Int' access=internal let storage_kind=stored)) 

الثابت له نوع type = 'Int' ، بالإضافة إلى مستوى الوصول. تهيئة الثابت أكثر تعقيدًا قليلاً. تمت إضافة استدعاء المنشئ _builtinIntegerLiteral . إذا كنت تمثل هذه الشجرة كرمز Swift ، فستحصل على:

 internal let x: Int = Int(_builtinIntegerLiteral: 16) 

المثال التالي يحتوي على خطأ:

 let x: Bool = 16 

إذا قمت بتمريرها إلى المحلل اللغوي ، فلن تكتشف أي انحرافات:

 (source_file (top_level_code_decl (brace_stmt (pattern_binding_decl (pattern_typed (pattern_named 'x') (type_ident (component id='Bool' bind=none))) (integer_literal_expr type='<null>' value=16)) )) (var_decl "x" type='<null type>' let storage_kind=stored)) 

لكن المحلل الدلالي سيشير إلى الخطأ في الكود الذي تم تمريره إليه:

 error: cannot convert value of type 'Int' to specified type 'Bool' let x: Bool = 16 

من الواضح أن الخطأ كان يحاول تعيين قيمة من النوع Int إلى ثابت من النوع Bool. سويفت لا يسمح بذلك. شكرا للمحلل الدلالي.

كود المصدر:

• سما

المستورد رنة

في هذه المرحلة ، نستورد وحدات Clang ونضع واجهات برمجة التطبيقات C و Objective-C في المكالمات المقابلة من Swift.

كود المصدر:

• المستورد رنة

الآن لدينا رمز مصدر محلول بالكامل اجتاز الاختبار الأولي. ولكن قبل الانتقال إلى إنشاء LLVM IR ، تحتاج إلى إجراء تحسينات محددة لـ Swift.

يمكن العثور على النسخة الكاملة من الكود المصدري في المستودع .