نظرية اللغات الرسمية - Automaton

Question

أنا أتساءل عن اللغات الرسمية. لدي نوع من المحللين: إنه يقرأ بنية الأشجار المسلسلة التي تشبه XML وتحويلها إلى صفيف متعدد الأبعاد.

نقطتي هي أوجه التشابه بين الخوارزمية المستخدمة وأنواع الاختلاف من الأوتوماتين (مكدس آلات تورينج آلات الحالة ...).

لذا فإن السؤال هو: ما هو التلقائي الذي أستخدمه هنا ، ولأي لغات رسمية تتناسب مع عائلة اللغات الرسمية؟ وماذا عن العودية؟

ما أعنيه من خلال "Automaton أنا أستخدمه ضمنيًا" هو "وهو الحد الأدنى من الأوتوماتون للقيام بنفس الوظيفة".

هذا هو المصدر الكامل:

كلمات $ // مجموعة من علامة XMLu003Ctag> "،"u003C/tag> ومحتوى نص بسيط

$ tree = array ('type' => 'root' ، 'sub' => array ()) ؛

$ ptree = array (& $ tree) ؛

$ deep = 0 ؛

foreach (كلمات $ مثل $ elem) {

if ( preg_match($openTag, $elem) ) { // $elem is an open tag

    $pTree[$deep++]['sub'][] = array( // we add an element to the multidim array
        'type' => 'block',
        'content' => $elem,
        'sub' => array()
    );

    $size = sizeof($pTree[$deep - 1]['sub']);
    $pTree[$deep] = &$pTree[$deep - 1]['sub'][$size - 1]; // down one level in the tree

} elseif ( preg_match($closeTag, $elem) ) { // it is a close tag

    $deep--; // up in the tree 

} else { // simple element

    $pTree[$deep]['sub'][] = array(
        'type' => 'simple',
        'content' => $elem
    );

}

}

Answer 1

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

انطلاقا من اسم المتغير $deep, ، ربما ليست الدولة. الحالة الموجودة في Automaton هي عنصر في مجموعة خاصة بـ Automaton ؛ $deep يبدو أنه يمكن أن يحتوي على عمق ، أي عدد صحيح إيجابي. مرة أخرى ، من الصعب معرفة دون الكود.

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

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

باختصار ، إذا كنت تتطلع إلى استخدام أي نظرية رسمية ، فقم بكلمة أسئلتك بشكل أكثر رسمية.

---

تحرير (بعد رؤية الكود):

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

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

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