قواعد التحليل - كيفية جعلها تعمل بشكل جيد معًا

Question

لذلك أقوم بعمل محلل، حيث أفضّل المرونة على السرعة، وأريد أن يكون من السهل كتابة القواعد النحوية، على سبيل المثال.لا توجد قواعد حل بديلة صعبة (قواعد زائفة لحل النزاعات وما إلى ذلك، كما يجب عليك فعله في yacc/bison وما إلى ذلك)

يوجد Lexer مشفر يدويًا مع مجموعة ثابتة من الرموز المميزة (على سبيل المثال.PLUS، وDECIMAL، وSTRING_LIT، وNAME، وما إلى ذلك) يوجد حاليًا ثلاثة أنواع من القواعد:

• قاعدة الرمز المميز:يطابق رمزًا معينًا
• قاعدة التسلسل:يطابق قائمة مرتبة من القواعد
• قاعدة المجموعة:يطابق أي قاعدة من القائمة

على سبيل المثال، لنفترض أن لدينا TokenRule 'varAccess'، الذي يطابق الرمز المميز NAME (تقريبًا /[A-Za-z][A-Za-z0-9_]*/)، وSequenceRule 'assistance'، الذي يطابق [ التعبير، TokenRule(PLUS)، التعبير].

التعبير عبارة عن GroupRule يطابق إما "المهمة" أو "varAccess" (مجموعة القواعد الفعلية التي أختبرها أكثر اكتمالًا بعض الشيء، ولكن هذا سيفي بالمثال)

ولكن الآن لنفترض أنني أريد التحليل

var1 = var2

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

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

حتى يتمكن من تحليل تعبيرات مثل

var1 = var2 = var3 = var4

مجرد حق =) الآن الأشياء المثيرة للاهتمام.هذا الرمز:

var1 = (var2 + var3)

لن تحلل.ما يحدث هو أنه يتم تحليل var1 (varAccess)، ويتم تطبيق التعيين فرعيًا، ويبحث عن تعبير، ويحاول "الأقواس"، ويبدأ، ويبحث عن تعبير بعد "("، ويجد var2، ثم يختنق على "+" 'لأنه كان يتوقع')'.

لماذا لا يتطابق مع 'var2 + var3'؟(ونعم، هناك قاعدة تسلسل "إضافة"، قبل أن تسأل).نظرًا لأن "الإضافة" ليست قاعدة جذر (لتجنب التكرار اللانهائي مع بداية التعبير التحليلي مع التعبير وما إلى ذلك) ولم يتم اختبار هذه الأوراق في SequenceRules وإلا فإنها ستحلل أشياء مثل

reader readLine() println()

مثل

reader (readLine() println())

(على سبيل المثال'1 = 3' هو التعبير المتوقع من خلال إضافة ورقة varAccess a)

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

(reader readLine()) println()

على أية حال، لدينا الآن هذه المشكلة وهي أننا يجب أن نكون قادرين على تحليل تعبير مثل '1 + 2' داخل SequenceRules.ما يجب القيام به؟أضف حالة خاصة عندما تبدأ SequenceRules بـ TokenRule، فسيتم اختبار GroupRules التي تحتوي عليها بحثًا عن الأوراق؟هل سيكون ذلك منطقيًا خارج هذا المثال بالذات؟أو هل ينبغي للمرء أن يكون قادرًا على التحديد في كل عنصر من عناصر SequenceRule ما إذا كان ينبغي اختباره بحثًا عن الأوراق أم لا؟أخبرني برأيك (بخلاف التخلص من النظام بأكمله - من المحتمل أن يحدث ذلك في غضون بضعة أشهر على أي حال)

ملاحظة:من فضلك، من فضلك، لا تجيب على شيء مثل "اذهب لقراءة هذا الكتاب المكون من 400 صفحة وإلا فأنت لا تستحق وقتنا حتى" إذا كنت تشعر بالحاجة إلى ذلك - فقط امتنع عن نفسك واذهب إلى Reddit.تمام؟شكرا لك مقدما.

Answer 1

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

YACC / LALR (1) النحو Aviod مشكلة العودية اليسرى، وهي خطوة كبيرة إلى الأمام. الأخبار السيئة هي أنه لا توجد لغات برمجة حقيقية (بخلاف باسكال ويرث الأصلية) التي هي Lalr (1). لذلك يمكنك اختراق قواعد اللغة الخاصة بك لتغييره من LR (K) إلى Lalr (1)، مما فبرك مرة أخرى أن تعاني من التجارب التي تعرض الحالات الغريبة، واختراق منطق الحد من القواعد في محاولة التعامل مع K-Lookaheads عند المحلل المولدات (YACC، BISON، ... تسميها) تنتج محللا 1 - Lookahead.

محلل GLR (http://en.wikipedia.org/wiki/glr_parser.) اسمح لك بتجنب كل هذا الهراء تقريبا. إذا كان بإمكانك كتابة محلل سياق مجاني، ضمن الظروف العملية، سيقوم محلل غاضب بتحليله دون جهد إضافي. هذا راحة هائلة عند محاولة كتابة قواعد النحوية التعسفية. وسوف تنتج محلل glr جيدة حقا شجرة مباشرة.

تم تعزيز Bison للقيام بتحليل GLR، ونوع من. لا يزال يتعين عليك كتابة منطق معقدا لإنتاج AST المطلوب، وعليك أن تقلق بشأن كيفية التعامل مع المحللين الفاشلين وتنظيف / حذف الأشجار المقابلة (الفاشلة). ال برامج DMS إعادة هندسة يوفر محلل GLR القياسي لأي قواعد اللغة الحرة السياق، وبناء ASTS تلقائيا دون أي جهد إضافي من جانبك؛ يتم بناء الأشجار الغامضة تلقائيا ويمكن تنظيفها عن طريق تحليل التحليل الدلالي بعد التحليل. لقد استخدمنا هذا للقيام بتحديد 30+ من قواعد النحوية للغة بما في ذلك C، بما في ذلك C ++ (والذي يعتقد على نطاق واسع أن يكون من الصعب تحليل [، من المستحيل تقريبا تحليل YACC] ولكنه واضح مع GLR الحقيقي)؛ يرى C +++ حافري نهاية الأمامي و AST Builder بناء على DMS.

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

Answer 2

أسلوب التحليل المفضل لدي هو إنشاء محلل عودي (RD) من المواصفات النحوية PEG.وعادة ما تكون سريعة جدًا وبسيطة ومرنة.إحدى المزايا الرائعة هي أنه لا داعي للقلق بشأن تمريرات الترميز المنفصلة، ​​كما أن القلق بشأن ضغط القواعد النحوية في بعض نماذج LALR غير موجود.تم إدراج بعض مكتبات PEG [هنا] [1].

عذرًا، أعلم أن هذا يقع في إطار التخلص من النظام، ولكنك بالكاد خرجت من المشكلة مع مشكلتك والتحول إلى محلل PEG RD، من شأنه أن يزيل صداعك الآن.