تحليل تعبيرات مع عدد غير محدد من الحجج

Question

أنا أحاول تحليل سلسلة في عصامي اللغة إلى نوع من الشجرة ، على سبيل المثال:

# a * b1 b2 -> c * d1 d2 -> e # f1 f2 * g

ينبغي أن يؤدي إلى:

# a
  * b1 b2
    -> c
  * d1 d2
    -> e
# f1 f2
  * g

#, * و -> هي رموز.a, b1, الخ.هي النصوص.

منذ اللحظة أنا أعرف فقط rpn طريقة تقييم التعبيرات و الحل الحالي هو على النحو التالي.إذا كنت تسمح فقط نص واحد المنوال بعد كل رمز لا يمكن بسهولة تحويل التعبير لأول مرة في RPN التدوين (ب = b1 b2;d = d1 d2;f = f1 f2) و تحليل من هنا:

أ ب ج -> * د ه -> * # f g * #

بيد أن دمج النص الرموز وأي شيء آخر يأتي يبدو أن إشكالية.كانت فكرتي في إنشاء علامة الرموز (م) ، حتى RPN تبدو مثل:

م b2 b1 م ج -> * M d2 d1 M e -> * # f2 f1 م ز * #

الذي هو أيضا parseable ويبدو أن حل المشكلة.

أنه قال:

1. هل من أحد لديه تجربة مع شيء من هذا القبيل و يمكن القول أنه أو أنها ليست حلا قابلا للتطبيق المستقبل ؟
2. هل هناك طرق أفضل من أجل تحليل تعبيرات مع غير معروف arity من المشغلين ؟
3. يمكن أن تشير لي في بعض الموارد ؟

ملاحظة.نعم, أعلم أن هذا المثال كثيرا لما يسب البادئة التدوين و ربما وسيلة للذهاب سيكون لإضافة بعض الأقواس, ولكن ليس لدي أي خبرة هنا.ومع ذلك ، فإن مصدر النص يجب أن لا تحتوي على أي الاصطناعي بين قوسين و أيضا أنا لست متأكدا ما يجب القيام به حول احتمال أقحم mixins مثل # * ب -> [إذا value1 = value2] ج -> د.

شكرا على أي مساعدة.

تحرير:يبدو أن ما أبحث عنه هي مصادر على postfix التدوين مع عدد متغير من الحجج.

Answer 1

لا أستطيع أن أفهم تماما على سؤالك, ولكن يبدو أن ما تريده هو النحوي تعريف محلل مولد.أقترح عليك أن نلقي نظرة على ANTLR, ، يجب أن تكون واضحة جدا مع ذلك تحديد قواعد اللغة إما الأصلي جملة أو RPN.

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

# a * b c d

والتي الثلاثة التالية هو متعارف عليه ؟

1. (a *(b ، c ، d))

2. (أ *(ب ، ج) د)

3. (a *(b), ج, د)

دون معرفة المزيد عن المشغلين ، فإنه من المستحيل أن أقول.بالطبع يمكنك تحديد نوع من greedyness من المشغلين ، على سبيل المثال* هو أكثر متعطشة من #, لذلك يلتهم كل الحجج.ولكن هذا من شأنه أن فاز الغرض من تدوين البادئة, لأنك ببساطة لن تكون قادرة على كتابة الخيار الثاني من فوق ثلاث ؛ لا يخلو additinonal النحوية العناصر.

الآن بعد أن أفكر في ذلك, وربما هو ليس من محض الصدفة أن أيا من لغات البرمجة أعلم الدعم مشغلي مع عدد متغير من الحجج فقط وظائف/الإجراءات.