استكشاف محلل اندماجي مع الصدأ

مرحبا يا هبر! أقدم لكم ترجمة المقال "Learning Combinators Parser With Rust" .

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

من وجهة نظر المبتدئين

في حياة كل مبرمج ، يأتي وقت يحتاج فيه إلى محلل.

سوف يسأل مبرمج مبتدئ: "ما هو المحلل اللغوي؟"

سيقول مبرمج المستوى المتوسط: "الأمر بسيط ، سأكتب تعبيرًا منتظمًا."

سيقول المبرمج الرئيسي: "ابتعد ، أعرف lex و yacc".

مبتدئ يفكر أفضل من كل شيء.

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

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

كيفية العمل مع هذه المادة

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

تمت كتابة التعليمات البرمجية لإصدار rustc 1.34.0 باستخدام إصدار اللغة 2018 . يمكنك استخدام أي إصدار من المحول البرمجي ، تأكد من أنك تستخدم إصدارًا يدعم إصدار 2018 (تأكد من أن Cargo.toml يحتوي على edition = "2018" ). هذا المشروع لا يحتاج التبعيات الخارجية.

لإجراء الاختبارات المقدمة في المقالة ، كما هو متوقع ، cargo test .

لغة الترميز

سنقوم بكتابة محلل لإصدار مبسط من XML. يبدو مثل هذا:

 <parent-element> <single-element attribute="value" /> </parent-element> 

يتم فتح عناصر XML مع < حرف ومعرف يتكون من حرف متبوعًا بأي عدد من الأحرف والأرقام و - . يتبع ذلك مسافات وقائمة اختيارية من أزواج السمات: معرف آخر كما هو محدد مسبقًا ، متبوعًا بعلامة = وسلسلة في علامات اقتباس مزدوجة. أخيرًا ، يوجد إما رمز إغلاق /> للإشارة إلى عنصر واحد بدون أطفال ، أو > للإشارة إلى وجود السلسلة التالية من العناصر الفرعية ، وعلامة إغلاق تبدأ بـ </ ، متبوعة بمعرف يجب أن يتطابق مع علامة الفتح ، ورمز إغلاق > .

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

سنقوم بتحليل هذه العناصر إلى هيكل يشبه هذا:

 #[derive(Clone, Debug, PartialEq, Eq)] struct Element { name: String, attributes: Vec<(String, String)>, children: Vec<Element>, } 

لا توجد أنواع فاخرة ، مجرد سلسلة للاسم (هذا هو المعرف في بداية كل علامة) ، وسمات في شكل أزواج من السلاسل (المعرّف والقيمة) وقائمة بالأطفال الذين يشبهون الأصل تمامًا.

(إذا كنت تطبع ، فتأكد من تضمين قسم derive . ستحتاج إليه لاحقًا.)

تعريف المحلل

حسنًا ، لقد حان الوقت لكتابة المحلل اللغوي.

التحليل هو عملية الحصول على بيانات منظمة من دفق المعلومات. المحلل اللغوي هو ما يبرز هذا الهيكل.

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

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

دعنا اكتبها كنوع من الوظيفة.

 Fn(Input) -> Result<(Input, Output), Error> 

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

 Fn(&str) -> Result<(&str, Element), &str> 

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

قد يكون من &[u8] استخدام &[u8] (شريحة من البايتات تتطابق مع أحرف ASCII) كنوع إدخال ، خاصة وأن شرائح السلسلة تتصرف بشكل مختلف قليلاً عن معظم الشرائح - خاصة وأنك لا تستطيع فهرستها بواحد input[0] الأرقام input[0] ، يجب عليك استخدام جزء input[0..1] . من ناحية أخرى ، لديهم العديد من الطرق المفيدة لتحليل السلاسل التي لا تحتوي على شرائح بايت.

في الواقع ، سوف نعتمد على الأساليب ، وليس استخدام فهارس الحروف ، لأن يونيكود. في UTF-8 ، وجميع سلاسل Rust هي سلاسل UTF-8 صالحة ، هذه المؤشرات لا تتوافق دائمًا مع الأحرف الفردية ، ومن الأفضل لجميع الأطراف المهتمة أن تطلب من المكتبة القياسية العمل معها من أجلنا.

أول محلل لدينا

دعنا نحاول كتابة محلل يبحث فقط عن الحرف الأول في السلسلة
وتقرر ما إذا كانت الرسالة a .

 fn the_letter_a(input: &str) -> Result<(&str, ()), &str> { match input.chars().next() { Some('a') => Ok((&input['a'.len_utf8()..], ())), _ => Err(input), } } 

أولاً ، دعونا نلقي نظرة على أنواع المدخلات والمخرجات: نأخذ شريحة سلسلة كمدخلات Result مع (&str, ()) ، أو خطأ مع &str . الزوج (&str, ()) هو نقطة مثيرة للاهتمام: كما قلنا أنه يجب علينا إرجاع مجموعة من المحتوى التالي ،
تحليل النتيجة وبقية المدخلات. &str هو الإدخال التالي ، والنتيجة هي مجرد نوع كتلة () ، لأنه إذا كان هذا المحلل يعمل بنجاح ، فيمكن أن يكون له نتيجة واحدة فقط (وجدنا الحرف a ) ، ونحن لسنا بحاجة حقًا إلى العودة
الرسالة a في هذه الحالة نحتاج فقط إلى الإشارة إلى أننا تمكنا من العثور عليها.

لذلك ، دعونا ننظر إلى رمز المحلل اللغوي نفسه. لم نكن نكتفي بالاعتماد على المكتبة القياسية ، فيمكننا تجنب الصداع باستخدام Unicode: نحصل على مكرر على أحرف السلسلة باستخدام طريقة chars() ونأخذ الحرف الأول منها. سيكون هذا عنصرًا من النوع char ملفوفًا في Option ، والذي None يعني فيه وجود أننا نحاول سحب char من سلسلة فارغة.

ومما زاد الطين بلة ، char ليس بالضرورة ما تفكر فيه كحرف يونيكود. من المحتمل أن يكون هذا هو ما يسميه Unicode "مجموعة grapheme" ، والتي يمكن أن تتكون من عدة أحرف char ، والتي هي في الواقع "قيم عددية" ، والتي هي مستويين أدنى من مجموعات grapheme. ومع ذلك ، يؤدي هذا المسار إلى الجنون ، ولأغراضنا ، من غير المرجح أن نرى chars خارج chars ASCII ، لذلك دعونا نتوقف عند هذا الحد.

نقوم بالتعيين على نمط Some('a') ، وهي النتيجة المحددة التي نبحث عنها ، وإذا تطابق ذلك ، نرجع قيمة نجاحنا:
Ok((&input['a'.len_utf8()..], ())) . وهذا يعني أننا نزيل الجزء الذي قمنا بتحليله ( 'a' ) من شريحة السطر ونعيد الباقي إلى جانب قيمنا التي تم تحليلها ، والتي تكون خالية فقط
() . تذكر دائمًا وحش Unicode ، قبل القطع ، اكتشفنا الطول في UTF-8 للشخصية 'a' خلال المكتبة القياسية - إنها 1 (لكن لا تنسى وحش Unicode).

إذا حصلنا على Some(char) الأخرى Some(char) ، أو إذا حصلنا على None ، فإننا نرجع خطأً. كما تتذكر ، لدينا نوع من الخطأ هو مجرد شريحة سلسلة ، والتي مررنا بها input والتي لا يمكن تحليلها. لم تبدأ بـ ، لذلك هذا خطأنا. هذا ليس خطأً كبيراً ، لكنه على الأقل أفضل قليلاً من مجرد "شيء ما خطأ في مكان ما."

لا نحتاج حقًا إلى هذا المحلل اللغوي لتحليل XML ، ولكن أول شيء يتعين علينا فعله هو العثور على الحرف الافتتاحي ، لذلك نحن بحاجة إلى شيء مشابه جدًا. سنحتاج أيضًا إلى تحليل > و / و = وجه التحديد ، لذلك ربما يمكننا إنشاء دالة تقوم بإنشاء المحلل اللغوي للشخصية التي نريدها؟

خلق محلل

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

 fn match_literal(expected: &'static str) -> impl Fn(&str) -> Result<(&str, ()), &str> { move |input| match input.get(0..expected.len()) { Some(next) if next == expected => { Ok((&input[expected.len()..], ())) } _ => Err(input), } } 

الآن يبدو مختلفا بعض الشيء.

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

وبالتالي ، بدلاً من أداء العمل في نص الوظيفة ، نرجع الإغلاق الذي يؤدي هذا العمل والذي يتوافق مع توقيع نوعنا للمحلل من السابق.

تبدو مطابقة الأنماط كما هي ، باستثناء أنه لا يمكننا مطابقة سلسلة حروفنا بشكل مباشر ، لأننا لا نعرف بالضبط ، لذلك نستخدم شرط المطابقة if next == expected . خلاف ذلك ، هو بالضبط نفس الشيء كما كان من قبل ، فقط داخل جسم الدائرة.

اختبار محلل لدينا

دعنا نكتب اختبارًا لهذا للتأكد من حصولنا عليه بشكل صحيح.

 #[test] fn literal_parser() { let parse_joe = match_literal("Hello Joe!"); assert_eq!( Ok(("", ())), parse_joe("Hello Joe!") ); assert_eq!( Ok((" Hello Robert!", ())), parse_joe("Hello Joe! Hello Robert!") ); assert_eq!( Err("Hello Mike!"), parse_joe("Hello Mike!") ); } 

أولاً نقوم بإنشاء محلل: match_literal("Hello Joe!") . يجب أن تستهلك السلسلة "Hello Joe!" وإرجاع بقية السلسلة ، أو فشل وإرجاع السلسلة بأكملها.

في الحالة الأولى ، نمررها بالصف الدقيق الذي نتوقعه ، ونرى أنه يعرض سلسلة فارغة والقيمة () ، مما يعني "لقد قمنا بتحليل السلسلة المتوقعة ، ولا تحتاج إلى إرجاعها."

في المجموعة الثانية ، نطعم السلسلة "Hello Joe! Hello Robert!" ونحن نرى أنه يستخدم حقًا السلسلة "Hello Joe!" وإرجاع ما تبقى من المدخلات: " Hello Robert!" (المسافة الرائدة وكل شيء آخر).

في الثالث ، ندخل الإدخال الخاطئ: "Hello Mike!" ولاحظ أنه يرفض حقا الإدخال مع وجود خطأ. ليس أن Mike مخطئ ، عادة ليس فقط ما كان يبحث عنه المحلل اللغوي.

محلل لشيء أقل تحديدا

وهذا يتيح لنا تحليل < ، > ، = وحتى </ و /> . لقد انتهينا تقريبا!

التالي بعد حرف الفتح < هو اسم العنصر. لا يمكننا القيام بذلك بمقارنة سلسلة بسيطة. ولكن يمكننا أن نفعل ذلك مع ريكس ...

... ولكن دعنا نقف. سيكون هذا تعبيرًا عاديًا سيكون من السهل جدًا نسخه في رمز بسيط ، ولهذا لا نحتاج إلى استخدام حزمة regex . دعونا نرى ما إذا كان بإمكاننا كتابة محلل اللغة الخاص بنا لهذا الغرض ، وذلك باستخدام مكتبة Rust القياسية فقط.

استرجع القاعدة الخاصة بمعرف اسم العنصر ، تبدو كما يلي: حرف أبجدي واحد ، متبوعًا بصفر أو أكثر من أي رمز أبجدي ،
حرف أو رقم أو اندفاعة.

 fn identifier(input: &str) -> Result<(&str, String), &str> { let mut matched = String::new(); let mut chars = input.chars(); match chars.next() { Some(next) if next.is_alphabetic() => matched.push(next), _ => return Err(input), } while let Some(next) = chars.next() { if next.is_alphanumeric() || next == '-' { matched.push(next); } else { break; } } let next_index = matched.len(); Ok((&input[next_index..], matched)) } 

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

مع وضع ذلك في الاعتبار ، نقوم أولاً بإنشاء String فارغة نسميها matched . ستكون هذه النتيجة. نحصل أيضًا على مكرر للأحرف في input ، والتي سنبدأ في تقسيمها.

الخطوة الأولى هي معرفة ما إذا كان هناك رمز في البداية. نقوم بسحب الحرف الأول من التكرار والتحقق مما إذا كان حرفًا: next.is_alphabetic() . بطبيعة الحال ، فإن مكتبة Rust القياسية ، ستساعدنا في Unicode - فهي تتوافق مع الأحرف في أي حروف أبجدية ، وليس فقط في ASCII. إذا كان خطابًا ، فسنضعه في سلسلتنا في المتغير matched ، وإذا لم يكن الأمر كذلك ، فنحن لا ننظر إلى معرف العنصر ونرجع فورًا مع وجود خطأ.

في الخطوة الثانية ، نستمر في سحب الأحرف من التكرار ، وإرسالها إلى السطر الذي is_alphanumeric() حتى is_alphanumeric() حرفًا لا يفي is_alphanumeric() يشبه is_alphabetic() باستثناء أنه يتضمن أيضًا أرقامًا في أي أبجدية) أو اندفاعة '-' .

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

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

تذكر أن بنية Element هي ما سنقوم بتحليل مستند XML الخاص به.

 struct Element { name: String, attributes: Vec<(String, String)>, children: Vec<Element>, } 

في الواقع ، لقد انتهينا للتو من محلل الجزء الأول ، حقل name . String التي ترجع المحلل اللغوي لدينا تذهب مباشرة إلى هناك. وهو أيضًا المحلل اللغوي الصحيح للجزء الأول من كل attribute .

دعونا التحقق من ذلك.

 #[test] fn identifier_parser() { assert_eq!( Ok(("", "i-am-an-identifier".to_string())), identifier("i-am-an-identifier") ); assert_eq!( Ok((" entirely an identifier", "not".to_string())), identifier("not entirely an identifier") ); assert_eq!( Err("!not at all an identifier"), identifier("!not at all an identifier") ); } 

نرى أنه في الحالة الأولى ، "i-am-an-identifier" تحليل السلسلة "i-am-an-identifier" تمامًا ، ولا تترك سوى سلسلة فارغة. في الحالة الثانية ، يقوم المحلل بإرجاع "not" كمعرف ، ويتم إرجاع بقية السلسلة كمدخلات متبقية. في الحالة الثالثة ، يفشل المحلل اللغوي على الفور ، لأن الحرف الأول الذي يعثر عليه ليس حرفًا.

combinators

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

 fn pair<P1, P2, R1, R2>(parser1: P1, parser2: P2) -> impl Fn(&str) -> Result<(&str, (R1, R2)), &str> where P1: Fn(&str) -> Result<(&str, R1), &str>, P2: Fn(&str) -> Result<(&str, R2), &str>, { move |input| match parser1(input) { Ok((next_input, result1)) => match parser2(next_input) { Ok((final_input, result2)) => Ok((final_input, (result1, result2))), Err(err) => Err(err), }, Err(err) => Err(err), } } 

يصبح الأمر أكثر صعوبة بعض الشيء هنا ، لكنك تعرف ما يجب فعله: ابدأ بالنظر في الأنواع.

بادئ ذي بدء ، لدينا أربعة أنواع من المتغيرات: P1 ، P2 ، R1 و R2 . هذه هي Parser 1 ، Parser 2 ، Result 1 Result 2 . P1 و P2 هي وظائف ، وستلاحظ أنها تتبع نمطًا ثابتًا من وظائف المحلل اللغوي: تمامًا مثل قيمة الإرجاع ، فإنها تأخذ &str كمدخلات وإرجاع. ينتج Result زوج المدخلات Result المتبقية ، أو خطأ.

لكن انظر إلى أنواع نتائج كل وظيفة: P1 هو المحلل اللغوي الذي يعطي R1 إذا نجح ، و P2 يعطي R2 أيضًا. وتكون نتيجة المحلل اللغوي الأخير الذي تم إرجاعه من (R1, R2) . وبالتالي ، فإن مهمة هذا المحلل هي أولاً بدء تشغيل المحلل P1 عند الإدخال ، وحفظ نتيجته ، ثم تشغيل P2 عند الإدخال الذي أعاد P1 ، وإذا P1 كلاهما ، فإننا نجمع بين النتيجتين في tuple (R1, R2) .

يظهر الرمز أن هذا هو بالضبط ما يفعله. نبدأ ببدء أول محلل عند المدخلات ، ثم بعد ذلك نحلل الثاني ، ثم نجمع بين النتيجتين في tuple ونعيده. إذا فشل أي من هذه المحللون ، فسوف نعود على الفور مع الخطأ الذي أصدره.

وبالتالي ، يجب أن نكون قادرين على الجمع بين match_literal ، match_literal ، من أجل match_literal الأول من علامة XML الأولى. دعنا نكتب اختبار لمعرفة ما إذا كان يعمل.

 #[test] fn pair_combinator() { let tag_opener = pair(match_literal("<"), identifier); assert_eq!( Ok(("/>", ((), "my-first-element".to_string()))), tag_opener("<my-first-element/>") ); assert_eq!(Err("oops"), tag_opener("oops")); assert_eq!(Err("!oops"), tag_opener("<!oops")); } 

يبدو أن العمل! لكن انظر إلى هذا النوع من النتائج: ((), String) . من الواضح أننا مهتمون فقط بالقيمة الصحيحة ، String . سوف يحدث هذا غالبًا - تتطابق بعض أدوات تحليلنا مع الأنماط في الإدخال دون إنتاج قيم ، وبالتالي يمكن تجاهل إنتاجها بأمان. للتكيف مع هذا النمط ، سنستخدم أداة دمج pair بنا لكتابة مجمعين آخرين: left ، والذي يتجاهل نتيجة المحلل اللغوي الأول ويعود فقط الثاني ، والعكس right . استخدمنا المحلل اللغوي في اختبارنا أعلاه ، والذي يتجاهل الجزء الأيسر ويحفظ فقط String لدينا ، بدلاً من pair .

مقدمة Functor

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

يحتوي هذا الموحد على مهمة واحدة: لتغيير نوع النتيجة.على سبيل المثال ، دعنا نقول أن لديك محللًا يُرجع ((), String)وترغب في تغييره بحيث يعود على سبيل المثال فقط String.

للقيام بذلك ، نقوم بتمريرها وظيفة تعرف كيفية تحويل النوع الأصلي إلى نوع جديد. في مثالنا، هو بسيط: |(_left, right)| right. بشكل أعم ، سيبدو Fn(A) -> Bالمكان A- نتيجة النوع الأصلي للمحلل - والنوع Bالجديد.

 fn map<P, F, A, B>(parser: P, map_fn: F) -> impl Fn(&str) -> Result<(&str, B), &str> where P: Fn(&str) -> Result<(&str, A), &str>, F: Fn(A) -> B, { move |input| match parser(input) { Ok((next_input, result)) => Ok((next_input, map_fn(result))), Err(err) => Err(err), } } 

ماذا تقول الأنواع؟ P- المحلل اللغوي لدينا. عوائد Aالنجاح. Fهي وظيفة سوف نستخدمها لعرضها Pكقيمة إرجاع لدينا ، والتي تبدو كما هي Pمع استثناء أن نوع النتيجة الخاص بها Bبدلاً من ذلكA

parser(input) , , result map_fn(result) , A B , .

, , map , Result :

 fn map<P, F, A, B>(parser: P, map_fn: F) -> impl Fn(&str) -> Result<(&str, B), &str> where P: Fn(&str) -> Result<(&str, A), &str>, F: Fn(A) -> B, { move |input| parser(input) .map(|(next_input, result)| (next_input, map_fn(result))) } 

— , «» Haskell , . A , map , A B , B , . Rust, Option , Result , Iterator Future , . : - Rust, , , , , map .

, , : Fn(&str) -> Result<(&str, Output), &str> . , , , , , , , .

, :

 type ParseResult<'a, Output> = Result<(&'a str, Output), &'a str>; 

, , , ParseResult<String> . , , Rust . , rustc , , .

'a , , .

. , , . , .

 trait Parser<'a, Output> { fn parse(&self, input: &'a str) -> ParseResult<'a, Output>; } 

: parse() , : , , .

, , :

 impl<'a, F, Output> Parser<'a, Output> for F where F: Fn(&'a str) -> ParseResult<Output>, { fn parse(&self, input: &'a str) -> ParseResult<'a, Output> { self(input) } } 

, , , Parser , .

, , . map , .

 fn map<'a, P, F, A, B>(parser: P, map_fn: F) -> impl Parser<'a, B> where P: Parser<'a, A>, F: Fn(A) -> B, { move |input| parser.parse(input) .map(|(next_input, result)| (next_input, map_fn(result))) } 

: , parser.parse(input) , , P , , Parser , , Parser . , . 'a' , , .

pair , :

 fn pair<'a, P1, P2, R1, R2>(parser1: P1, parser2: P2) -> impl Parser<'a, (R1, R2)> where P1: Parser<'a, R1>, P2: Parser<'a, R2>, { move |input| match parser1.parse(input) { Ok((next_input, result1)) => match parser2.parse(next_input) { Ok((final_input, result2)) => Ok((final_input, (result1, result2))), Err(err) => Err(err), }, Err(err) => Err(err), } } 

: parser.parse(input) parser(input) .

, pair , map .

 fn pair<'a, P1, P2, R1, R2>(parser1: P1, parser2: P2) -> impl Parser<'a, (R1, R2)> where P1: Parser<'a, R1>, P2: Parser<'a, R2>, { move |input| { parser1.parse(input).and_then(|(next_input, result1)| { parser2.parse(next_input) .map(|(last_input, result2)| (last_input, (result1, result2))) }) } } 

and_then Result map , , Result , Result . match . and_then , , map , left right .

Left Right

pair map , left right :

 fn left<'a, P1, P2, R1, R2>(parser1: P1, parser2: P2) -> impl Parser<'a, R1> where P1: Parser<'a, R1>, P2: Parser<'a, R2>, { map(pair(parser1, parser2), |(left, _right)| left) } fn right<'a, P1, P2, R1, R2>(parser1: P1, parser2: P2) -> impl Parser<'a, R2> where P1: Parser<'a, R1>, P2: Parser<'a, R2>, { map(pair(parser1, parser2), |(_left, right)| right) } 

pair , , map , .

, , .

, Parser ParseResult . match_literal :

 fn match_literal<'a>(expected: &'static str) -> impl Parser<'a, ()> { move |input: &'a str| match input.get(0..expected.len()) { Some(next) if next == expected => Ok((&input[expected.len()..], ())), _ => Err(input), } } 

, , — &'a str , rustc .

identifier , , , :

 fn identifier(input: &str) -> ParseResult<String> { 

. () . .

 #[test] fn right_combinator() { let tag_opener = right(match_literal("<"), identifier); assert_eq!( Ok(("/>", "my-first-element".to_string())), tag_opener.parse("<my-first-element/>") ); assert_eq!(Err("oops"), tag_opener.parse("oops")); assert_eq!(Err("!oops"), tag_opener.parse("<!oops")); } 

. < . ? .

, , . , .

, , - , : .

( ) . .

— , <element attribute="value"/> , . , , .

identifier , . , .

 fn one_or_more<'a, P, A>(parser: P) -> impl Parser<'a, Vec<A>> where P: Parser<'a, A>, { move |mut input| { let mut result = Vec::new(); if let Ok((next_input, first_item)) = parser.parse(input) { input = next_input; result.push(first_item); } else { return Err(input); } while let Ok((next_input, next_item)) = parser.parse(input) { input = next_input; result.push(next_item); } Ok((input, result)) } } 

, , , A , Vec<A> — A .

identifier . , , . , , .

, : ? :

 fn zero_or_more<'a, P, A>(parser: P) -> impl Parser<'a, Vec<A>> where P: Parser<'a, A>, { move |mut input| { let mut result = Vec::new(); while let Ok((next_input, next_item)) = parser.parse(input) { input = next_input; result.push(next_item); } Ok((input, result)) } } 

, , .

 #[test] fn one_or_more_combinator() { let parser = one_or_more(match_literal("ha")); assert_eq!(Ok(("", vec![(), (), ()])), parser.parse("hahaha")); assert_eq!(Err("ahah"), parser.parse("ahah")); assert_eq!(Err(""), parser.parse("")); } #[test] fn zero_or_more_combinator() { let parser = zero_or_more(match_literal("ha")); assert_eq!(Ok(("", vec![(), (), ()])), parser.parse("hahaha")); assert_eq!(Ok(("ahah", vec![])), parser.parse("ahah")); assert_eq!(Ok(("", vec![])), parser.parse("")); } 

: one_or_more , , zero_or_more , .

, , . one_or_more zero_or_more , - :

 fn one_or_more<'a, P, A>(parser: P) -> impl Parser<'a, Vec<A>> where P: Parser<'a, A>, { map(pair(parser, zero_or_more(parser)), |(head, mut tail)| { tail.insert(0, head); tail }) } 

Rust, cons Vec , , Lisp, , . , : .

, : , . : ( ). , , Clone , , , .

. , one_or_more , , , , , - , , RangeBound : range(0..) zero_or_more , range(1..) one_or_more , range(5..=6) , .

. zero_or_more one_or_more .

, — , Rc ?

, one_or_more zero_or_more .

, . , . , , , > /> . , . , , , , .

. .

-. match_literal , . ? - , Unicode, . Rust, , char is_whitespace , is_alphabetic is_alphanumeric .

-. , , is_whitespace , identifier .

-. , . any_char , char , , pred , , : pred(any_char, |c| c.is_whitespace()) . , , : .

any_char , , UTF-8.

 fn any_char(input: &str) -> ParseResult<char> { match input.chars().next() { Some(next) => Ok((&input[next.len_utf8()..], next)), _ => Err(input), } } 

pred , , . , . , true , . , .

 fn pred<'a, P, A, F>(parser: P, predicate: F) -> impl Parser<'a, A> where P: Parser<'a, A>, F: Fn(&A) -> bool, { move |input| { if let Ok((next_input, value)) = parser.parse(input) { if predicate(&value) { return Ok((next_input, value)); } } Err(input) } } 

, , :

 #[test] fn predicate_combinator() { let parser = pred(any_char, |c| *c == 'o'); assert_eq!(Ok(("mg", 'o')), parser.parse("omg")); assert_eq!(Err("lol"), parser.parse("lol")); } 

, whitespace_char :

 fn whitespace_char<'a>() -> impl Parser<'a, char> { pred(any_char, |c| c.is_whitespace()) } 

, whitespace_char , , , , , . space1 space0 .

 fn space1<'a>() -> impl Parser<'a, Vec<char>> { one_or_more(whitespace_char()) } fn space0<'a>() -> impl Parser<'a, Vec<char>> { zero_or_more(whitespace_char()) } 

? , , . identifier ( , any_char pred *_or_more ). match_literal("=") = . , . , , .

 fn quoted_string<'a>() -> impl Parser<'a, String> { map( right( match_literal("\""), left( zero_or_more(pred(any_char, |c| *c != '"')), match_literal("\""), ), ), |chars| chars.into_iter().collect(), ) } 

, , , , .

map - , , , , , : . map right , right — , : match_literal("\"") . .

right — . left , , left , , , match_literal("\"") — . , — .

pred any_char , , , zero_or_more , :

• ,

right left .

, . , zero_or_more ? Vec<A> A . any_char char . , , Vec<char> . map : , Vec<char> String , , String Iterator<Item = char> , vec_of_chars.into_iter().collect() , String .

, , , , , , , , .

 #[test] fn quoted_string_parser() { assert_eq!( Ok(("", "Hello Joe!".to_string())), quoted_string().parse("\"Hello Joe!\"") ); } 

, , , , .

,

, , = . , .

. , Vec<(String, String)> , (String, String) , zero_or_more . , .

 fn attribute_pair<'a>() -> impl Parser<'a, (String, String)> { pair(identifier, right(match_literal("="), quoted_string())) } 

! : pair , identifier , String , right = , , quoted_string , String .

zero_or_more , , .

 fn attributes<'a>() -> impl Parser<'a, Vec<(String, String)>> { zero_or_more(right(space1(), attribute_pair())) } 

: ,
. right .

.

 #[test] fn attribute_parser() { assert_eq!( Ok(( "", vec![ ("one".to_string(), "1".to_string()), ("two".to_string(), "2".to_string()) ] )), attributes().parse(" one=\"1\" two=\"2\"") ); } 

! !

, , rustc , , . , . , rustc, , , #![type_length_limit = "…some big number…"] , . , #![type_length_limit = "16777216"] , . , !

, , , , NP-. element: , , , zero_or_more , ?

, , . , , , : < , . , (String, Vec<(String, String)>) .

 fn element_start<'a>() -> impl Parser<'a, (String, Vec<(String, String)>)> { right(match_literal("<"), pair(identifier, attributes())) } 

, , .

 fn single_element<'a>() -> impl Parser<'a, Element> { map( left(element_start(), match_literal("/>")), |(name, attributes)| Element { name, attributes, children: vec![], }, ) } 

, , — Element !

.

 #[test] fn single_element_parser() { assert_eq!( Ok(( "", Element { name: "div".to_string(), attributes: vec![("class".to_string(), "float".to_string())], children: vec![] } )), single_element().parse("<div class=\"float\"/>") ); } 

… , .

single_element , , , . , , , — , — .

, , ...

- Rust, , , .

. , :

 enum List<A> { Cons(A, List<A>), Nil, } 

rustc , List<A> , List::<A>::Cons List<A> , . rustc, , , .

, Rust. , Rust, , , , . , .

, . , List::Cons A A , A A . , , , , List::Cons , . , Rust — Box .

 enum List<A> { Cons(A, Box<List<A>>), Nil, } 

Box , . , , Box<dyn Parser<'a, A>> .

. ? , - , , . : . . , , SIMD ( ).

, Parser Box , .

 struct BoxedParser<'a, Output> { parser: Box<dyn Parser<'a, Output> + 'a>, } impl<'a, Output> BoxedParser<'a, Output> { fn new<P>(parser: P) -> Self where P: Parser<'a, Output> + 'a, { BoxedParser { parser: Box::new(parser), } } } impl<'a, Output> Parser<'a, Output> for BoxedParser<'a, Output> { fn parse(&self, input: &'a str) -> ParseResult<'a, Output> { self.parser.parse(input) } } 

, , BoxedParser box . BoxedParser ( BoxedParser , ), BoxedParser::new(parser) , , Box . , Parser , .

Box , BoxedParser Parser , . , , , , , , , , . .

, , , .

, ? , , . quoted_string :

 fn quoted_string<'a>() -> impl Parser<'a, String> { map( right( match_literal("\""), left( zero_or_more(pred(any_char, |c| *c != '"')), match_literal("\""), ), ), |chars| chars.into_iter().collect(), ) } 

, . Parser ?

, , impl Trait , impl Trait .

… BoxedParser . , impl Parser<'a, A> , , BoxedParser<'a, A> .

, , , Parser .

map , Parser :

 trait Parser<'a, Output> { fn parse(&self, input: &'a str) -> ParseResult<'a, Output>; fn map<F, NewOutput>(self, map_fn: F) -> BoxedParser<'a, NewOutput> where Self: Sized + 'a, Output: 'a, NewOutput: 'a, F: Fn(Output) -> NewOutput + 'a, { BoxedParser::new(map(self, map_fn)) } } 

'a , , . , — , , impl Trait .

quoted_string :

 fn quoted_string<'a>() -> impl Parser<'a, String> { right( match_literal("\""), left( zero_or_more(pred(any_char, |c| *c != '"')), match_literal("\""), ), ) .map(|chars| chars.into_iter().collect()) } 

, , .map() right() .

pair , left right , , , , pair . , , map , .

— pred . Parser :

 fn pred<F>(self, pred_fn: F) -> BoxedParser<'a, Output> where Self: Sized + 'a, Output: 'a, F: Fn(&Output) -> bool + 'a, { BoxedParser::new(pred(self, pred_fn)) } 

quoted_string pred , :

 zero_or_more(any_char.pred(|c| *c != '"')), 

, , , zero_or_more — « any_char », . , zero_or_more one_or_more .

quoted_string , map single_element :

 fn single_element<'a>() -> impl Parser<'a, Element> { left(element_start(), match_literal("/>")).map(|(name, attributes)| Element { name, attributes, children: vec![], }) } 

element_start , , , . ...

… , . , .

map pred Box — !

. single_element , , > , /> . , , .

 fn open_element<'a>() -> impl Parser<'a, Element> { left(element_start(), match_literal(">")).map(|(name, attributes)| Element { name, attributes, children: vec![], }) } 

, ? , , , zero_or_more , ? , , — : , , .

, , : , , . , , , . , , , , , , .

 fn either<'a, P1, P2, A>(parser1: P1, parser2: P2) -> impl Parser<'a, A> where P1: Parser<'a, A>, P2: Parser<'a, A>, { move |input| match parser1.parse(input) { ok @ Ok(_) => ok, Err(_) => parser2.parse(input), } } 

element , , ( open_element , element ).

 fn element<'a>() -> impl Parser<'a, Element> { either(single_element(), open_element()) } 

. , , , . , ?

 fn close_element<'a>(expected_name: String) -> impl Parser<'a, String> { right(match_literal("</"), left(identifier, match_literal(">"))) .pred(move |name| name == &expected_name) } 

pred , ?

, :

 fn parent_element<'a>() -> impl Parser<'a, Element> { pair( open_element(), left(zero_or_more(element()), close_element(…oops)), ) } 

close_element ? , .

. , parent_element , open_element element parent_element , , XML.

, , and_then ? , . and_then : -, , , , . pair , , , , . , and_then Result Option , , , Result Option , , ( , )).

, .

 fn and_then<'a, P, F, A, B, NextP>(parser: P, f: F) -> impl Parser<'a, B> where P: Parser<'a, A>, NextP: Parser<'a, B>, F: Fn(A) -> NextP, { move |input| match parser.parse(input) { Ok((next_input, result)) => f(result).parse(next_input), Err(err) => Err(err), } } 

, , P , , A . F , map A B , , and_then A NextP , B . — B , , , NextP .

: , , , , f ( A ), , f(result) , B . . , , , B

: P , , f P , NextP , , .

Parser , map , .

 fn and_then<F, NextParser, NewOutput>(self, f: F) -> BoxedParser<'a, NewOutput> where Self: Sized + 'a, Output: 'a, NewOutput: 'a, NextParser: Parser<'a, NewOutput> + 'a, F: Fn(Output) -> NextParser + 'a, { BoxedParser::new(and_then(self, f)) } 

, , ?

, pair :

 fn pair<'a, P1, P2, R1, R2>(parser1: P1, parser2: P2) -> impl Parser<'a, (R1, R2)> where P1: Parser<'a, R1> + 'a, P2: Parser<'a, R2> + 'a, R1: 'a + Clone, R2: 'a, { parser1.and_then(move |result1| parser2.map(move |result2| (result1.clone(), result2))) } 

, : parser2.map() parser2 , Fn , FnOnce , parser2 , . , Rust. , , pair .

, Rust, close_element , , .

:

 fn parent_element<'a>() -> impl Parser<'a, Element> { pair( open_element(), left(zero_or_more(element()), close_element(…oops)), ) } 

, and_then , close_element .

 fn parent_element<'a>() -> impl Parser<'a, Element> { open_element().and_then(|el| { left(zero_or_more(element()), close_element(el.name.clone())).map(move |children| { let mut el = el.clone(); el.children = children; el }) }) } 

, and_then open_element() , , close_element . , open_element and_then . , Element open_element , , , .

, map , Element ( el ) . clone() , Fn . ( Vec<Element> ) Element , .

, , element , open_element parent_element , , , , !

"" ?

, , map «» Haskell?

and_then — , Rust, , map . flat_map Iterator , , .

— "". Thing<A> , and_then , A Thing<B> , Thing<B> — .

, , Option<A> , , Some(A) None , , Some(A) , Some(B)

. , Future<A> , and_then Future<B> , Future<B> Future<A> , Future<A> . Future<A> , — ¹ , Future<B> . , Future , and_then , Future , . , Future , .

, Rust , , , , , , , . .

, Redux

.

, XML, . , ( , , < div / > , ).

.

 fn whitespace_wrap<'a, P, A>(parser: P) -> impl Parser<'a, A> where P: Parser<'a, A>, { right(space0(), left(parser, space0())) } 

element , element , , , .

 fn element<'a>() -> impl Parser<'a, Element> { whitespace_wrap(either(single_element(), parent_element())) } 

!

, ! , .

 #[test] fn xml_parser() { let doc = r#" <top label="Top"> <semi-bottom label="Bottom"/> <middle> <bottom label="Another bottom"/> </middle> </top>"#; let parsed_doc = Element { name: "top".to_string(), attributes: vec![("label".to_string(), "Top".to_string())], children: vec![ Element { name: "semi-bottom".to_string(), attributes: vec![("label".to_string(), "Bottom".to_string())], children: vec![], }, Element { name: "middle".to_string(), attributes: vec![], children: vec![Element { name: "bottom".to_string(), attributes: vec![("label".to_string(), "Another bottom".to_string())], children: vec![], }], }, ], }; assert_eq!(Ok(("", parsed_doc)), element().parse(doc)); } 

, - , , :

 #[test] fn mismatched_closing_tag() { let doc = r#" <top> <bottom/> </middle>"#; assert_eq!(Err("</middle>"), element().parse(doc)); } 

, . , , , , . , , , , . , , , , , .

: , ! , , , ² .

, , . !

, , Rust , , - , , , .

, pom , , .

Rust nom , pom ( , ), , .

Rust combine , .

Haskell Parsec .

, « Haskell» , , Haskell.

رخصة

Bodil Stokke Creative Commons Attribution-NonCommercial-ShareAlike 4.0. , http://creativecommons.org/licenses/by-nc-sa/4.0/ .

1: .

2: , .

andreevlex funkill