خطوات ومشاركة تنفيذ محلل (في .NET - وفي هذه الحالة XPath 2.0)

Question

في عدم وجود أي تطبيقات XPath 2.0 مجانية جيدة لـ .NET بناء على LINQ إلى XML ، فكرت في تنفيذ بلدي (أيضًا للتجربة). ولكن لمجرد أن تكون واضحًا (وليس بناء شيء موجود) ، فهذه هي تطبيقات XPath 2.0 التي وجدتها:

• Saxon .net
• آلة الاستعلام - واجهت مشاكل مع هذا - استثناءات مع الأمثلة
• xqsharp - قد تكون جيدة ، ولكنها تجارية (مطور واحد ~ 300 دولار)

الآن ، أريد بعض الأفكار حول مدى صعوبة تنفيذ بعض اللغة مثل تعبيرات XPath 2.0. لقد وجدت هذا الرابط الذي يحتوي على EBNF لتعبير XPath 2.0: http://www.w3.org/tr/2007/rec-xpath20-20070123/#id-grammar وأنا أفكر في صنعه في F# مع مجموعة FSLEX/FSYACC.

خلفيتي (شخصي): لقد لعبت مع هذه الأدوات من قبل ، ولكن فقط لبعض التعبيرات البسيطة ولغة برمجة بسيطة للغاية. علاوة على ذلك ، لقد قرأت معظم كتاب Dragon Book وتنفيذ برنامج التحويل البرمجي الحديث في ML - لكن لسوء الحظ ، لم أضع النظرية في الممارسة العملية أثناء القراءة. لقد درست علوم الكمبيوتر في عام الآن حيث أكملت دورات مع النظرية حول EX finite automaton, CFL والخوارزميات لكنني كنت مطورًا لسنوات قبل الجامعة (بضع سنوات مع وظائف احترافية - في نهاية المواقع الإلكترونية بشكل رئيسي).

الآن ، خطوات التحليل وما أميل إلى تغطيته:

1. LEX - تحليل - التخفيضات: FSLEX/FSYACC. لن أغطي بشكل صحيح كل XPath 2.0 في البداية ولكن على الأقل كل ما يمكن أن يفعله XPath 1.0 أكثر قليلاً.
2. تحليل سيمي - لست متأكدًا من مقدار هذا
3. التحسين - أنا لا أميل إلى تغطية هذا (على الأقل ليس في البداية)
4. اجتياز فعلي وما إلى ذلك
5. ...?

الآن ، و أسئلة ملموسة بالإضافة إلى ما سبق:

1. ما مدى صعوبة جعل محلل من هذا الحجم؟ بناءً على خلفيتي ، هل يمكنني ذلك؟
2. هل هناك أي خطوات حاسمة فاتتها فيما يتعلق بـ XPath 2.0 على وجه الخصوص؟
3. هل هناك أي تقنية فاتني ؛ هل يجب علي تغطية أكثر من مجرد XPath 2.0 و XDocument وما إلى ذلك لتكون قادرا على صنع المحلل؟

أن تكون واضحا: أريد أن أجعل محلل تعبير XPath 2.0 و Traverse XDocument وما إلى ذلك مع هذا التعبير المحدود. الذي أعتقد أنه مجتمعة هو محرك الاستعلام.

تحديث: لقد وجدت هذا: http://www.w3.org/2007/01/applets/xpathapplet.html الذي يحتوي على رمز لتحليل واجتياز. أعتقد أنها ستكون بداية أو إشارة لطيفة :-)

ستكون إجاباتك موضع تقدير.

Answer 1

لقد قمت بتنفيذ محلل Xpath 2.0 بالكامل في XSLT 2.0 منذ ثلاثة أعوام.

لقد استخدمت بلدي إطار تحليل LR في FXSL ولم يكن هذا صعبًا للغاية. القواعد كبيرة جدًا - 209 قواعد ، إذا كنت أتذكر جيدًا. لقد استخدمت تعديل yacc (الذي قمت به) الذي أسميه yaccx لإنشاء جداول التحليل مثل XML. هذه هي المدخلات ل المحلل العام LR, ، مكتوبة في XSLT.

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

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

لذلك ، كن مستعدًا لكل هذه الصعوبات.

Answer 2

أنا أحد مطوري XQSharp ، لذلك لدي خبرة في هذا المجال. بدأت XQSharp في الواقع حياتها كتطبيق XPath قبل توسيعها لدعم Xquery.

استغرقنا تنفيذنا الأولي حوالي 6 أشهر ، على الرغم من أن هذا لم يكن الشيء الوحيد الذي كنا نعمل عليه في ذلك الوقت.

بعد هذا الوقت كان لدينا تطبيق كان مكتمل. كانت هناك العديد من المجالات التي لم تكن فيها هذا متطابقة تمامًا ، حيث لم تتصرف طرق .NET المعيارية تمامًا مثل المواصفات المطلوبة. بعض الأمثلة على ذلك هي مع تحويل القيم من وإلى السلاسل ، والتعبيرات العادية ، والكثير من الأشياء اليدوية ، والمشاكل مع تمثيل .NET لـ XML (على سبيل المثال معالجة XML: BASE) وما إلى ذلك.

كانت هناك العديد من المجالات التي يجب القيام بها لتنفيذ هذا:

تفسير: كان المحلل نفسه واضحًا ، ويولد في الغالب من EBNF في المواصفات. أود أن أقدر أن هذا يمثل في البداية عمل بضعة أسابيع.

نموذج البيانات: كيف يتم تمثيل البيانات. من أجل الحصول على تطبيق XPath الكامل ، هناك الكثير من أنواع البيانات الجديدة (مثل XS: GDAY) التي يجب تنفيذها. في حالتنا ، لدينا جميع عناصرنا المستمدة من نوع الأساس وستقوم جميع تعبيراتنا بإرجاع العدادات لهذه. يجب أيضًا أن تكون قادرًا على تحديد ما إذا كان نوع العنصر يتطابق مع نوع XPath معين. لقد دعمنا الكتابة الثابتة ووعي المخطط من البداية ، بدون هذه الميزات ، ربما يصبح هذا القسم تافهة ، لكنك ما زلت تبحث عن عمل عدة أسابيع.

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

المهامكما أشار المعلق السابق إلى أن مكتبة الوظائف لـ XPath كبيرة إلى حد ما. استغرقت مكتبة XPath بأكملها عدة أشهر لتنفيذها.

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

من المحتمل أن تنظر إلى العمل لمدة شهر آخر لجميع أجزاء العمل الإضافية التي لا تندرج مباشرة في هذه الفئات.

بعد كل هذا العمل ، تركنا مع تنفيذ وظيفي في الغالب من XPath ؛ ولكن كان من المفيد أن تبطئ استخدام العالم الحقيقي (ربما 100x أبطأ من XPath 1 في .NET). لذلك بعد ذلك يأتي العمل الممتع - التحسين.

إن رفع المحرك يصل إلى 100 ٪ من المطابقة وإضافة تحسينات ربما استغرق 12-18 شهورًا آخر (على الرغم من أننا ربما ذهبنا قليلاً مع التحسين!) ، ولكن بحلول هذه المرحلة ، قمنا بالفعل بالانتقال إلى أن يكون تطبيق Xquery.

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

تأكد من استخدام XPathNavigator لتمثيل العقدة الخاص بك ، حيث يحتوي على طرق مثل Selectchildren التي يمكن أن تأخذ مزايا الفهارس في التمثيلات الأساسية (على سبيل المثال xPathDocument).

Answer 3

لمعالجة سؤالك الخرساني الثالث ، لم يذكر كتاب Dragon NOLES عن تحليل قواعد التعبير (PEGS)/BACKRAT Parsers/LARSER COMBONATOR ، والتي أصبحت الآن الغضب الآن ، خاصةً عندما يتعلق الأمر باللغات الوظيفية. نرى fparsec, ، فمثلا.