محلل آلة الدولة المحدودة

Question

أود تحليل تنسيق ملف مصمم ذاتيًا مع محلل يشبه FSM في C ++ (هذا ال teach-myself-c++-the-hard-way-by-doing-something-big-and-difficult نوع المشروع :)). لديّ سلسلة رمزية مع خطوط جديدة تدل على نهاية خط EUH .... نرى هنا للحصول على مثال الإدخال. سيتم تصفية جميع التعليقات والخردة ، لذلك لدي سلسلة std :: مثل هذا:

global \n { \n SOURCE_DIRS src \n HEADER_DIRS include \n SOURCES bitwise.c framing.c \n HEADERS ogg/os_types.h ogg/ogg.h \n } \n ...

تفسير بناء الجملة:

• {} هي نطاقات ، والكلمات الرفاصية تشير إلى أن قائمة الخيارات/الملفات ستتبعها.
• n مهم فقط في قائمة الخيارات/الملفات ، مما يدل على نهاية القائمة.

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

1. هل يجب أن أستخدم enum أو ملخص class + مشتقات لدولتي؟ ربما يكون الأول أفضل لبناء بناء الجملة الصغير ، ولكن يمكن أن يصبح قبيحًا لاحقًا ، والثاني هو عكس ذلك تمامًا. أنا أميل إلى الأول ، من أجل بساطته. enum مثال و مثال الفصل. تحرير: ماذا عن هذا الاقتراح إلى عن على goto, ، اعتقدت أنهم كانوا شريرًا في C ++؟
2. عند قراءة قائمة ، أحتاج إلى عدم التجاهل \n. طريقتي المفضلة لاستخدام string عبر stringstream, ، سوف يتجاهل \n بشكل افتراضي. لذلك أنا بحاجة إلى طريقة بسيطة للقول (نفس الشيء!) stringstream لعدم تجاهل الخطوط الجديدة عند تمكين دولة معينة.
3. سوف بسيط enum تكفي الدول لتحليل متعدد المستويات (نطاقات داخل النطاقات {...{...}...}) أم أن ذلك يحتاج إلى تطبيقات اختراق؟
4. إليكم مسودة الدول التي أفكر فيها:
   • upper: يقرأ الأسماء العالمية ، exe ، lib+ المستهدف ...
   • normal: داخل النطاق ، يمكن قراءة المصادر ... ، إنشاء متغيرات المستخدم ...
   • list: يضيف عناصر إلى قائمة حتى يتم مواجهة سطر جديد.

سيكون لكل نطاق نوع من المشروط (على سبيل المثال Win32: Global {GCC: CFLAGS = ...}) وسيحتاج إلى التعامل مع نفس الموضة بالضبط (حتى في list الدولة ، لكل عنصر).

شكرا على أي مدخلات.

Answer 1

إذا كان لديك نطاقات تداخل ، فإن آلة الحالة المحدودة هي ليس الطريقة الصحيحة للذهاب ، ويجب أن تنظر إلى محلل نحوي خالٍ من السياق. و LL (1) محلل يمكن كتابتها كمجموعة من funcitons العودية ، أو لالر (1) محلل يمكن كتابتها باستخدام مولد محلل مثل البيسون.

إذا قمت بإضافة مكدس إلى FSM ، فأنت تدخل Pushdown Automaton إِقلِيم. تعادل Automaton غير المحدود الأوتوماتون معادًا لقواعد خالية من السياق (على الرغم من أ Pushdown Automaton الحتمية هو أقل قوة للغاية.) لالر (1) مولدات المحللات المحلي في الواقع تولد Automaton الحتمية داخليًا. سيغطي كتاب تصميم برنامج التحويل البرمجي الجيد الخوارزمية الدقيقة التي يتم من خلالها بناء Automaton Pushdown من القواعد النحوية. (بهذه الطريقة ، فإن إضافة مكدس ليس "اختراق".). هذا المقال ويكيبيديا يصف أيضًا كيفية إنشاء LR (1) Pushdown Automaton من قواعد اللغة ، ولكن IMO ، المقالة ليست واضحة قدر الإمكان.

إذا كان عش نطاقاتك عميقًا فقط (أي لديك upper, normal و list مستويات ولكن ليس لديك متداخل listS أو متداخلة normalS) ، ثم يمكنك استخدام FSM بدون مكدس.

Answer 2

هناك مرحلتان لتحليل دفق إدخال النص للحلية:

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

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

لذلك ردا على أسئلتك:

هل يجب أن أستخدم التعداد أو مشتقات فئة + مجردة لدولتي؟

لقد وجدت أنه بالنسبة إلى المميزات الصغيرة ، فإن مصفوفة قيم الحالة / الانتقال مناسبة ، شيء مثل next_state = state_transitions[current_state][current_input_char]. في هذه الحالة ، next_state و current_state هي بعض أنواع الأعداد الصحيحة (بما في ذلك ربما يكون نوعًا مكونًا). يتم اكتشاف أخطاء الإدخال عند الانتقال إلى حالة غير صالحة. يتم تحديد نهاية الرمز المميز استنادًا إلى تحديد الحالة لـ endstates الصالحة مع عدم وجود انتقال صالح متاح إلى حالة أخرى بالنظر إلى حرف الإدخال التالي. إذا كنت قلقًا بشأن المساحة ، فيمكنك استخدام متجه من الخرائط بدلاً من ذلك. إن جعل فصول الولايات ممكنة ، لكنني أعتقد أن هذا ربما يكون أكثر صعوبة مما تحتاجه.

عند قراءة قائمة ، أحتاج إلى عدم تجاهل n.

يمكنك إما إنشاء رمز رمزي يسمى " n" ، أو رمز هروب أكثر تعميمًا (معرف يسبقه رضاعة خلف في مصفوفة انتقال الحالة الخاصة بك (كن على دراية بالاختلاف بين استراحة خط UNIX و Windows ، ومع ذلك ، يمكنك إنشاء FSM تعمل على أي منهما).

هل ستكفي حالات التعداد البسيطة لتحليل متعدد المستويات (النطاقات داخل النطاقات {... {...} ...}) أم أن ذلك يحتاج إلى تطبيقات اختراق؟

هذا هو المكان الذي ستحتاج فيه إلى قواعد نحوية أو Automaton Pushdown ما لم تتمكن من ضمان أن التعشيش لن يتجاوز مستوى معين. حتى ذلك الحين ، من المحتمل أن تجعل FSM معقدة للغاية.

إليكم مسودة الدول التي أضعها في الاعتبار: ...

انظر بلدي على التحليل المعجمي والنحوي أعلاه.

Answer 3

للحجز ، أحاول دائمًا استخدام شيء ثبت بالفعل للعمل: Antlr مع Antlrworks وهو من مساعدة كبيرة لتصميم واختبار القواعد. يمكنك إنشاء رمز لـ C/C ++ (و لغات اخرى) ولكن تحتاج إلى بناء وقت تشغيل AntlR لتلك اللغات.

بالطبع إذا وجدت ثني أو الثور أسهل في الاستخدام ، يمكنك استخدامها أيضًا (أعرف أنهما يولدون فقط C و C ++ ، لكن قد أكون مخطئًا لأنني لم أستخدمها لبعض الوقت).